本文修正了 KZG 多项式承诺 中一些描述不好的部分，并添加一些相关知识的引用。

简介

今天我想向你们介绍一下 Kate，Zaverucha 和 Goldberg 发表的 多项式承诺方案。这篇文章并不涉及复杂的数学及密码学理论知识，仅作为一篇简介。

该方案通常被称作卡特（Kate，读作 kah-tay）多项式承诺方案。在一个多项式承诺方案中，证明者计算一个多项式的承诺（commitment）, 并可以在多项式的任意一个点进行打开（opening）：该承诺方案能证明多项式在特定位置的值与声称的数值一致。

之所以被称为承诺，是因为当承诺值（椭圆曲线上的一个点）发送给某对象（验证者）后，证明者无法改变当前计算的多项式。他们只能为一个多项式提供有效的证明，如果他们试图作弊，他们将无法产生证明，或者证明将被验证者拒绝。

预备知识

如果你对 有限域、椭圆曲线 和 配对 这几个话题不是很熟悉的话，非常推荐去读一读 Vitalik Buterin 的博客：探索椭圆曲线配对 。

默克尔树对比

如果你已经熟知默克尔树，我想将之与卡特承诺进行对比。默克尔树即是密码学家所说的矢量承诺：使用深度为 $d$ 的默克尔树，你可以计算出对一个矢量（即固定长度的元素列表）$a_0, \ldots, a_{2^d-1}$ 的承诺。运用熟知的默克尔证明，你可以用 $d$ 个哈希来提供证明元素 $a_i$ 存在于这个矢量的位置 $i$ 。

事实上，我们可以用默克尔树来构造多项式承诺：回忆一下，一个 $n$ 次的多项式 $p(X)$ ，不过是一个函数 $\displaystyle p(X) = \sum_{i=0}^{n} p_i X^i$ ，其中 $p_i$ 是该多项式的系数。

通过设置 $a_i=p_i$，我们可以计算这一系列系数的默克尔树根，从而比较容易地对一个 $n = 2^d -1$ 次的多项式进行承诺。证明一个取值，意味着证明者想要向验证者展示对于某个值 z，$p(z)=y$。为达到这个目的，证明者可以向验证者发送所有的 $p_i$，然后验证者计算 $p(z)$ 是否等于 $y$。

当然，这是一个极度简单化的多项式承诺，但它能帮助我们理解真实的多项式承诺的益处。让我们一起回顾多项式承诺的性质：

  1. 承诺的大小是一个单一哈希（默克尔树根）。一个足够安全的加密散列一般需要 256 位，即 32 字节。
  2. 为了证明一个取值，证明者需要发送所有的 $p_i$，所以证明的大小和多项式次数是线性相关的。同时，验证者需要做同等的线性量级的计算（他们需要计算多项式在 z 点的取值，即计算 $\displaystyle p(z)=\sum_{i=0}^{n} p_i z^i$。
  3. 该方案未隐藏多项式的任何部分 - 证明者一个系数接一个系数地发送完整的多项式。

现在让我们一起来看看卡特方案是如何达成以上要求的：

  1. 承诺大小是一个支持配对的椭圆曲线群元素。比如说对于 BLS12_381 曲线，大小应是 48 字节。
  2. 证明大小独立于多项式大小，永远是一个群元素。验证同样独立于多项式大小，无论多项式次数为多少都只要两次群乘法和两次配对。
  3. 大多数时候该方案隐藏多项式 - 事实上，无限多的多项式将会拥有完全一样的卡特承诺。但是这并不是完美隐藏：如果你能猜到多项式（比如说该多项式过于简单，或者可能的多项式集合很小），你就可以找到这个被承诺的多项式。

还有一点，在一个承诺中合并任意数量的取值证明是可行的。这些性质使得卡特方案对于零知识证明系统来说非常具有吸引力，例如 PLONK 和 SONIC。同时对于一些更日常的目的，或者简单的作为一个矢量承诺来使用也是非常有趣的场景，接下来的文章中我们就会看到。

椭圆曲线以及配对

正如之前所提到的预备知识所说，我强烈推荐 Vitalik Buterin 的博客：探索椭圆曲线配对。它包含了理解本文所需的背景知识：特别是 有限域，椭圆曲线 和 配对 相关知识。

假设 $G_1$ 和 $G_2$是两条椭圆曲线，并满足配对 $e: \mathbb G_1 \times \mathbb G_2 \rightarrow \mathbb G_T$ ，假设 $p$ 是 $G_1$ 和 $G_2$ 的阶，$G$ 和 $H$ 是 $G_1$ 和 $G_2$ 的生成元。接下来，我们定义一个非常有效的速记符号， $\forall x \isin F_p$:

$$ [x]_1 = x G \in \mathbb G_1 \text{ and } [x]_2 = x H \in \mathbb G_2 $$

可信设置

假设我们已有一个可信设置，使得对于一个秘密 $s$，其子元素 $[s^i]_1$ 和 $[s^i]_2$ （ $i=0, \ldots, n-1$ ）对于任意的证明者和验证者都可用。

有一种方法能够获得这种可信设置：我们用离线计算机生成一个随机数 $s$，计算所有的群元素 $[s^i]_x$，并通过电线传输出去（不包括 $s$）, 然后烧掉这部计算机。当然这并不是一个好的解决方案，你必须相信计算机的操纵者没有通过其他渠道泄露这个秘密 $s$。

在实际应用中，这种设置通常采用安全多方计算（MPC），使用一组计算机来创建这个群元素，而没有任何单一计算机知道秘密 $s$，这样只有挟持了整组计算机才能知道 $s$。

注意这里有一件事是不可能的：你不能仅仅选择一个随机群元素 $[s]_1$（其中 $s$ 是未知的）然后通过它计算其他的群元素。不知道 $s$ 是无法计算 $[s^2]_1$ 的。

好了，椭圆曲线密码学基础告诉我们通过可信设置的群元素是无法破解 $s$ 的，它是有限域 $F_p$ 中的一个数字，但证明者无法找出它的具体数值。他们只能在给定的元素上做一些特定的计算。举个例子，他们可以用椭圆曲线乘法轻易地计算 $c [s^i]_1 = c s^i G = [cs^i]_1$，或者说将椭圆曲线点值相加算出 $ c [s^i]_1 + d [s^j]_1 = (c s^i + d s^j) G = [cs^i + d s^j]_1 $ 。实际上如果 $\displaystyle p(X)=\sum_{i=0}^{n} p_i X^i $ 是一个多项式，证明者可以计算：$\displaystyle[p(s)]_1 = [\sum_{i=0}^{n} p_i s^i]_1 = \sum_{i=0}^{n} p_i [s^i]_1$。

这就显得非常有趣 – 通过使用这套可信设置，任何人都可以计算出一个多项式在一个谁也不知道的秘密点 s 上的值。只是他们得到的输出值不是一个自然数，而是一个椭圆曲线点 $[p(s)]_1 = p(s) G$ ，这已经足够有用。

卡特承诺

在卡特承诺方案中，元素 $C=[p(s)]_1$ 是多项式 $p(X)$ 的承诺。

这样你可能会问了，有没有可能：证明者在不知道 $s$ 的情况下找到另一个有相同承诺的多项式 $q(X)≠p(X)$，使得 $[p(s)]_1=[q(s)]_1$？我们假设这个推理成立，那么就是说 $[p(s)−q(s)]_1=[0]_1$，即 $p(s)-q(s)=0$ 。

我们知道多项式 $r(X)=p(X) - q(X)$ 不是常数，因为 $p(X)≠q(X)$。有一个 非常著名的定理（Schwartz-zippel Lemma）证明，即是任意非常数的 $n$ 次多项式至多可以有 $n$ 个零点，这是因为如果 $r(z)=0$，$r(X)$ 就可以被线性因子 $X−z$ 整除；因为每一个零点都意味着可以被一个线性因子整除，同时每经过一次除法会降低一阶，所以推理可知至多存在 $n$ 个零点。

因为证明者不知道 $s$，他们只能通过在尽可能多的地方让 $p(X)−q(X)=0$ 来使得 $p(s)−q(s)=0$。如上所证，他们只能在至多 $n$ 个点上使 $p(s)−q(s)=0$，那么成功的可能性就很小，因为 $n$ 比起曲线的次数 $p$ 要小很多，$s$ 被选中成为 $p(X)=q(X)$ 成立点的概率是微乎其微的。来感受一下这个概率的大小，假设我们采用现有最大的可信设置，当 $n=2^{28}$，把它来和椭圆曲线的阶 $p≈2^{256}$ 对比：攻击者精心制作的多项式 $q(X)$ 来与 $p(X)$ 尽可能多的重合 $n=2^{28}$ 个点，得到相同承诺 $(p(s)=q(s))$ 的概率是 $2^{28}/2^{256}=2^{28−256}≈2⋅10^{−69}$。这是一个非常低的概率，在现实中意味着攻击者没有办法施行该攻击。

多项式相乘

目前为止我们学习了在一个秘密点 $s$ 的多项式取值是可以计算的，这就使得我们可以对一个独一无二的多项式进行承诺 - 对于同一个承诺 $C=[p(s)]_1$ 存在多个多项式，但是在实践中它们其实是无法计算的，密码学家称之为绑定（computationally binding）。

但是，我们仍缺少在不发送给验证者完整多项式的情况下“打开”这个承诺的能力。为此，我们需要使用配对。如上所述，我们可以对这个秘密进行线性操作；举个例子，我们可以计算 $p(X)$ 的承诺 $[p(s)]_1$，也可以将 $p(X)$ 和 $q(X)$ 的两个承诺相加来计算 $p(X)+q(X) $ 的联合承诺：$[p(s)]_1+[q(s)]_1=[p(s)+q(s)]_1$。

现在我们所缺少的就是两个多项式的乘法（译注：为什么会得出这个结论？）。做到这一点就能利用多项式的性质打开更多酷炫玩法的大门。尽管椭圆曲线本身不允许作乘法，幸运的是我们可以通过配对解决这个问题：

$$e([a]_1,[b]_2)=e(G,H)^{(ab)}=[ab]_T$$

在这里介绍一个新的标识方法 $[x]_T=e(G,H)^x$ 。这样，尽管我们不能直接在椭圆曲线上直接将两个点的乘积作为一个椭圆曲线点（这就是所谓 全同态加密/FHE 的一个性质；椭圆曲线仅是加同态），但如果是在不同的曲线上提交承诺（比如一个在 $G_1$，另一个在 $G_2$ 上），我们可以将两个域元素相乘，这样所得到的输出就是一个 $G_T$ 元素。

这让我们深入到卡特证明的核心。记得我们之前提到的线性因子的说法：如果一个多项式在 $z$ 处有零点，那么它就可以被 $X−z$ 整除。同理反向可证 - 如果多项式可以被 $X−z$ 整除，那么它必在 $z$ 处有零点。可被 $X−z$ 整除，意味着对于某个多项式 $q(X)$ 我们可得 $p(X)=(X−z)⋅q(X)$，并且很明显在 $X=z$ 处得到零点。

现在假设我们想要证明 $p(z)=y$。我们使用多项式 $p(X)−y$， 明显该多项式在 $z$ 处达到零点，这样我们就可以应用线性因子的知识。设多项式 $q(X)$ 等于 $p(X)−y$ 除以线性因子 $X−z$ ：

$$q(X)=\frac{p(X)−y}{X−z}$$

译注：这被称为“商多项式”，请注意，只有当 $p(z)=y$ 时，$q(X)$ 才存在。因此，这个商多项式的存在就是取值的证明。

等同于 $q(X)(X−z)=p(X)−y$ 。

卡特证明

定义 $p(z)=y$ 的卡特证明为 $π=[q(s)]_1$，记得多项式 $p(X)$ 的承诺是 $C=[p(s)]_1$.

验证者用如下等式来确认这个证明：

$$e(π,[s−z]_2)=e(C−[y]_1,H)$$

证明一下这个公式的推导： $$ \begin{aligned} &e(π,[s−z]_2) \\ &\Rightarrow e(π,(s-z)H) \\ &\Rightarrow e((s-z)π,H) \\ &\Rightarrow e([s-z][q(s)]_1,H) \\ &\Rightarrow e([s-z]q(s)G,H) \\ &\Rightarrow e((p(s)-y)G,H) \\ &\Rightarrow e(p(s)G-yG,H) \\ &\Rightarrow e([p(s)]_1-yG,H) \\ &\Rightarrow e(C-[y]_1,H) \\ \end{aligned} $$

注意验证者可以计算 $[s−z]_2$ ，因为这仅是椭圆曲线 $G_2$ 上两个点（可信设置的元素 $[s]_2$ 和点 $z$）之间的加法运算。同样的，验证者已知了 $y$ 是取值 $p(z)$，所以他们也可以计算 $[y]_1$。那么为什么上述证明能向验证者证明 $p(z)=y$ ，或者更准确地说，$C$所提交的多项式在 $z$ 点的取值是 $y$ ？

这里我们需要考证两个性质：正确性和可靠性。正确性指的是如果证明者遵循我们定义的步骤，他们就可以产出一个能被验证的证明。这个通常难度不大。还有就是可靠性，这个性质是指证明者不会产出一个“不正确”的证明 – 比如说，他们不会欺骗验证者对于某个 $y’≠y，p(z)=y’$。

接下来我们先写出配对组的对应等式 $[q(s)⋅(s−z)]_T=[p(s)−y]_T$ 正确性非常一目了然 – 这就是等式 $q(X)(X−z)=p(X)−y$ 在一个没人知道的随机点 $s$ 的取值。

那么，我们怎么才能知道它的可靠性，证明者不会创建假的证明呢？让我们从多项式的角度来看待这个问题。如果证明者想依循我们的方法来构建一个证明，他们就需要用 $X−z$ 来除 $p(X)−y’$。但是 $p(z)−y’$并不为零，无论怎么除都会有一个余数，所以他们就无法进行这个多项式除法。这样一来，证明者就无法用这个方法进行伪造了。

剩下的就只能直接在椭圆群中想办法了：如果说对于某个承诺 $C，他们可以计算椭圆群元素

$$π_{Fake}=\frac{1}{s−z}(C−[y′]_1)$$

一旦成立，那证明者就可以为所欲为了。感觉上这是很难做到的，你必须用和 s 相关的什么东西来求幂，但 s 又是未知的。为了严格证明，你需要配对证明的一个密码学假设，即所谓的 q-strong SDH 假设 。

多重证明

为这里为止我们已经展示了如何证明多项式取值在单个点的取值，这是已经非常了不起：仅靠发送单个群元素（例如 BLS12_381 中是 48 字节）来证明任何度（比如说 $2^{28}$）的多项式在任意点的取值。作为对比，如果使用默克尔树用作多项式承诺，我们需要发送 $2^{28}$ 个元素，即这个多项式所有的系数。

更进一步，我们来看看如何仅使用一个群元素，来计算并证明一个多项式在任意多个点的取值。首先我们需要了解一个新概念：插值多项式。有一个包含 k 个点的列表 $(z_0,y_0),(z_1,y_1),\ldots,(z_{k−1},y_{k−1})$，我们随时都可以找到一个次数小于 $k$ 的多项式来经过这些点。利用拉格朗日插值我们可以得到该多项式的公式 $I(X)$：

$$ I(X)=\sum_{i=0}^{k−1} y_i \prod^{k−1}_{\substack{j=0 \\ j≠i}}\frac{X−z_j}{z_i−z_j} $$

现在我们假设已知 $p(X)$ 经过了所有的点，那么多项式 $z_0,z_1,\ldots,z_{k−1}$ 都是零点。这就意味着多项式可被所有的线性因子：$(X−z_0),(X−z_1),\ldots(X−z_{k−1})$ 整除，我们将它们组合在一起，称为零多项式： $$ Z(X)=(X−z_0)⋅(X−z_1)\ldots(X−z_{k−1}) $$

我们可以计算商值

$$ q(X)=\frac{p(X)−I(X)}{Z(X)} $$ 注意，因为 $p(X)−I(X)$ 能被 $Z(X)$ 所有的线性因子整除，所以它能被 $Z(X)$ 本身整除。

现在我们可以定义 $(z_0,y_0),(z_1,y_1),\ldots,(z_{k−1},y_{k−1})$ 的卡特证明：$π=[q(s)]_1$ – 这仍然仅是一个群元素。

为了验证这个证明，验证者同样需要计算插值多项式 $I(X)$ 和零多项式 $Z(X)$，使用这些结果他们可以计算 $[Z(s)]_2$ 和 $[I(s)]_1$ ，然后就可以确认配对等式：

$$ e(π,[Z(s)]_2)=e(C−[I(s)]_1,H) $$

将该等式写成配对，我们可以像单点上的卡特证明一样简单地确认它是否能够成立：

$$ [q(s)⋅Z(s)]_T=[p(s)−I(s)]_T $$

这就非常酷炫了：仅仅提供一个群元素，你就能证明任何数量的计算，甚至是百万个！这相当于通过 48 个字节来证明海量的计算。

将卡特作为矢量承诺来使用

尽管卡特承诺被设计成多项式承诺，但它作为矢量承诺来使用也大有用处。回忆一下，一个矢量承诺是针对矢量 $a_0,\ldots,a_{n−1}$ 的承诺，并且允许你证明任意位置 $i$ 对应 $a_i$。我们可以使用卡特承诺的方案来重现这一场景：$p(X)$ 是对所有的 $i$ 计算 $p(i)=a_i$ 的一个多项式，我们知道有这样一个多项式，并且可以通过拉格朗日插值来计算它：

$$ p(X)=\sum_{i=0}^{n-1} a_i \prod_{\substack{j=0 \\ j≠i}}^{n-1} \frac{X−j}{i−j} $$

使用这个多项式，我们只用一个群元素就可以证明这个矢量中任意数量的元素！注意到比起默克尔树（在证明大小方面）这个方案更加高效：默克尔证明仅证明一个元素就需要花费 $log_n$ 次的哈希！

延伸阅读

我们目前正在探索使用 Kate 承诺实现无状态版本的以太坊。因此，我强烈建议在 ethresearch 论坛中使用关键字 Kate 来搜索你感兴趣的话题。

另一篇很赞的博文是 Vitalik 的 introduction to PLONK，其中大量运用到了多项式承诺，其中卡特方案就是多项式承诺实现的主要方案。

Next