KZG多项式承诺

原文链接： KZG Polynomial Commitments

翻译：Star.LI @ Trapdoor Tech

简介

今天我想向你们介绍一下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)$，无非是一个函数 $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$点的取值，即计算$p(z)=\sum_{i=0}^{n} p_i z^i$）。
3. 该方案不隐藏多项式的任何部分 - 证明者一个系数接一个系数地发送完整的多项式。

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

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

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

椭圆曲线以及配对

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

假设$\mathbb G_1$和$\mathbb G_2$是两条满足$e: \mathbb G_1 \times \mathbb G_2 \rightarrow \mathbb G_T$的配对，假设p是$\mathbb G_1$和$\mathbb G_2$的阶，同时G和H是$\mathbb G_1$和$\mathbb G_2$的生成元。接下来，我们定义一个非常有效的速记符号：对于任意$x \in \mathbb F_p$ $\displaystyle [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$的，它是有限域$\mathbb 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$。实际上如果$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) \neq 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) \neq q(X)$。有一个非常著名的定理，即是任意非常数的$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 \approx 2^{256}$对比：攻击者设立的多项式$q(X)$来与$p(X)$尽可能多的重合，$n=2^{28}$个点，得到相同承诺（p(s)=q(s)）的概率是$2^{28}/2^{256} = 2^{28-256} \approx 2 \cdot 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$。

现在我们所缺少的就是两个多项式的乘法。如果我们做到乘法，就能利用多项式的性质打开更多酷炫玩法的大门。尽管椭圆曲线本身不允许作乘法，幸运的事我们可以通过配对解决这个问题：我们有

$\displaystyle e([a]_1, [b]_2) = e(G, H)^{(ab)} = [ab]_T$ 在这里介绍一个新的标识方法：$[x]_T = e(G, H)^x$。这样，尽管我们不能直接在椭圆曲线上直接将两个元素相乘得到它们的乘积，一个椭圆曲线元素（这就是所谓全同态加密/FHE的一个性质；椭圆曲线仅是加同态)。如果是在不同的曲线上（比如一个在$\mathbb G1$，另一个在$\mathbb G2$上）提交承诺，我们可以将两个字段元素相乘，这样所得到的输出就是一个$\mathbb 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$除，即：

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

这就等同于$q(X)(X-z) = p(X)-y$。

卡特证明

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

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

$\displaystyle e(\pi,[s-z]_2) = e(C-[y]_1, H)$ 注意验证者可以计算$[s−z]_2$，因为这仅是可信设置的元素$[s]_2$和多项式被计算的点$z$的一个组合。同样的，验证者已知了$y$是取值$p(z)$，所以他们也可以计算$[y]_1$。那么为什么上述证明能向验证者证明$p(z)=y$，或者更准确地说，$C$所提交的多项式在$z$点的取值是$y$？

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

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

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

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

$\displaystyle \pi_\text{Fake} = \frac{1}{s-z} (C-[y']_1)$ 一旦成立，那证明者就可以为所欲为了。感觉上这是很难做到的，你必须用和s相关的什么东西来求幂，但s又是未知的。为了严格证明，你需要针对证明和配对的一个密码学假设，即所谓的$q$-strong SDH假设 ³。

多重证明

为这里为止我们已经看到了如何在一个单点上证明一个多项式取值，这是已经是非常了不起的一件事：你可以仅靠发送单个的群元素（可以是48字节大小，例如BLS12_381）来证明任何次数的多项式 - 比如说$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_{j=0 \atop j \neq i}^{k-1} \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})$整除，我们将它们组合在一起，称为零多项式：

$\displaystyle Z(X) = (X-z_0) \cdot (X-z_1) \cdots (X-z_{k-1})$ 我们可以计算商值

$\displaystyle 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})$的卡特证明：$\pi=[q(s)]_1$ – 这仍然仅是一个群元素。

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

$\displaystyle e(\pi,[Z(s)]_2) = e(C-[I(s)]_1, H)$ 将该等式写成配对，我们可以像单点上的卡特证明一样简单地确认它是否能够成立：

$\displaystyle [q(s)\cdot 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$的一个多项式，我们知道这样一个多项式存在，并且可以通过拉格朗日插值来计算它：

$\displaystyle p(X) = \sum_{i=0}^{n-1} a_i \prod_{j=0 \atop j \neq i}^{n-1} \frac{X-j}{i-j}$ 使用这个多项式，我们可以就可以利用一个单一群元素来证明这个矢量中任意数量的元素！注意到比起默克尔树（在证明大小方面）这个方案更加高效：仅证明一个元素，默克尔证明就需要花费$\log n$大小的哈希！

延伸阅读

为了得到一个无状态版本的以太坊，我们正在积极探索卡特承诺的应用。在这里我强烈建议在ethresearch论坛中使用关键字Kate来搜索你感兴趣的话题。

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

1. https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf ↩

2. 这个结果经常被错误引用为代数基本定理。实际上代数基本理论是其反推的结论。该结论在代数封闭的域中才有:效。而代数基本定理是对于复数而言，所有n次的多项式都有n个线性因子。很可惜这个简单一点的版本没有简洁易记的名字，尽管它可以说比代数基本定理更基本一些。 ↩

3. https://www.cs.cmu.edu/~goyal/ibe.pdf ↩