Vitalik ：理解新型通用零知识证明方案PLONK

注：原文作者是以太坊联合创始人Vitalik Buterin

以下是译文：

最近，Ariel Gabizon、Zac Williamson和Oana Ciobotaru公布了一种新的通用零知识证明方案PLONK，其全称是笨拙的“Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”。虽然（研究者们）对通用零知识证明协议的改进研究已进行了多年，但PLONK（以及更早但更复杂的SONIC以及最近的Marlin）带来的是一系列的改进，这些改进可能会总体上大大提高这类证明的可用性及进展。

第一个改进：虽然PLONK仍需要一个类似Zcash SNARKs的可信设置过程，但它是一个“通用且可更新”的可信设置。这意味着两件事：首先，不需要为每一个你想证明的程序都设置一个单独的可信设置，而是为整个方案设置一个单独的可信设置，之后你可以将该方案与任何程序一起使用（在进行设置时可选择最大大小）。第二，有一种方法可以让多方参与可信设置，这样只要其中任何一方是诚实的，那这个可信设置就是安全的，而且这种多方过程是完全连续的：首先是第一个人参与，然后是第二个人，然后是第三个……参与者们甚至不需要提前知道，新的参与者可以把自己添加到最后。这使得可信设置很容易拥有大量参与者，从而在实践中确保设置是非常安全的。

第二个改进是它所依赖的“奇特密码学”是一个单一的标准化组件，称为“polynomial commitment”（多项式承诺）。PLONK使用基于可信设置和椭圆曲线对的“Kate commitments”（Kate承诺），但你也可以用其它方案替换它，例如FRI（这将使PLONK变成一种STARK）或者DARK（基于隐藏顺序组）。这意味着该方案在理论上与证明大小和安全性假设之间的任何（可实现的）权衡兼容。

这意味着需要在证明大小与安全性假设之间进行不同权衡的用例（或者对这个问题有不同思想立场的开发人员），仍然可以为“算术化”共享大部分相同的工具（把一个程序转换成一组多项式方程的过程，然后用多项式承诺来检验）。如果这种方案被广泛采用，那我们可期待在改进共享算术化技术方面的快速进展。

 

PLONK是如何工作的

 

让我们从解释PLONK的工作原理开始，我们只关注多项式方程而不立即解释如何验证这些方程。PLONK的一个关键组成部分，就像SNARKs中使用的QAP一样，这是一个转换问题的过程，形式是“给我一个值X，我给你一个特定的程序P，这样当X作为输入进行计算时，给出一些具体的结果Y，” 放到问题“给我一组满足一组数学方程的值”当中。程序p可以表示很多东西，例如，问题可能是“给我一个数独的解决方案”，你可以通过将P设置为数独验证器加上一些编码的初始值并将Y设置为1 （即“是的，这个解决方案是正确的”）来对其进行编码，一个令人满意的输入X将是数独的有效解决方案。这是通过将P表示为一个带有逻辑门的加法和乘法电路，并将其转换为一个方程组来完成的，其中变量是所有线上的值，每个门有一个方程（例如，乘法为x6 = x4 * x7，加法为x8 = x5 + x9）。

下面是一个求x问题的例子，这样P(x) = x**3 + x + 5 = 35 (提示: x = 3):

我们按如下方式给门和线贴上标签：

在门和线上，我们有两种类型的约束：门约束（连接到相同门之间线的方程，例如a1 * b1 = c1）和复制约束（关于电路中任何位置的不同线相等的声明，例如a0 = a1 = b1 = b2 = a3 或者c0 = a1）。我们需要创建一个结构化的方程组，它最终将减少到一个非常少数量的多项式方程组，来表示这两个方程组。

在PLONK中，这些方程的设置和形式如下（其中，L = 左，R=右，O=输出，M=乘法，C=常数）：

每个Q值都是一个常数，每个方程中的常数（和方程数）对于每个程序都是不同的。每个小写字母值都是一个变量，由用户提供：ai 是第i个门的左输入线，bi是右输入线，ci是第i个门的输出线。对于加法门，我们设置：

将这些常数插入方程并进行简化，得到ai+bi-oi=0，这正是我们想要的约束条件。对于乘法门，我们设置：

对于将ai设置为某个常数x的常数门，我们设置：

你可能已注意到线的每一端，以及一组线中的每根线，显然必须具有相同的值（例如x）对应于一个不同的变量；到目前为止，没有什么能强迫一个门的输出与另一个门的输入相同（我们称之为“复制约束”）。PLONK当然有一种强制复制约束的方法，我们稍后会讨论这个问题。所以现在我们有一个问题，证明者想要证明他们有一堆Xai, Xbi以及Xci值满足了一堆相同形式的方程。这仍然是一个大问题，但不像“找到这个计算机程序的一个令人满意的输入”，这是一个非常结构化的大问题，我们有数学工具可用于“压缩”它。

 

从线性系统到多项式

 

如果你了解过STARKs或QAPs，下一节中描述的机制会让人觉得有些熟悉，但如果你没有，那也没有关系。这里的主要内容是将多项式理解为一种数学工具，用于将大量值封装到单个对象中。通常，我们是以“系数形式”来看待多项式，即如下表达式：

但我们也可用“定值形式”来看待多项式。例如，我们可以认为上面是在坐标（0，1，2，3）处分别定值（-2，1，0，1）的“度数<4”的多项式。

下面是下一步。许多形式相同的方程组可重新解释为多项式上的一个方程组。例如，假设我们有一个系统：

我们用定值形式定义四个多项式：L(x)是在坐标 (0, 1, 2)处定值为（2，1，8）的度数< 3的多项式，在同样的坐标系下，M(x) 定值为 (-1, 4, -1)， R(w)定值为(3, -5, -1) 以及O(x)定值为(8, 5, -2)（用这种方法直接定义多项式是可以的，可以使用拉格朗日插值来转换成系数形式）。现在，考虑下面这个等式：

在这里，Z(x)是 (x-0) * (x-1) * (x-2) 的简写，它是在定值域 (0, 1, 2)上返回零的最小（非零）多项式。这个方程的解 (x1 = 1, x2 = 6, x3 = 4, H(x) = 0)也是原方程组的解，只是原方程组不需要H(x)。还要注意，在这种情况下，H(x)很方便为零，但在更复杂的情况下，H可能需要为非零。

所以现在我们知道，我们可以在少数数学对象（多项式）中表示一个大的约束集。但在我们上面建立的表示门线约束的方程中，x1, x2, x3变量在每个方程中是不同的。我们可以用同样的方法使变量本身成为多项式而不是常数来处理这个问题。所以我们得到：

如前所述，每个Q多项式是由正在验证的程序生成的参数，a, b, c多项式是用户提供的输入。

 

复制约束(Copy constraints)

 

现在，让我们回到“连接”线上。到目前为止，我们所拥有的是一组关于不相交值的不相交方程，这些方程独立且易于满足：常数门可通过将值设置为常数来满足，加法和乘法门可通过将所有线设置为零来满足！为了使问题具有实际的挑战性（并实际表示原始电路中编码的问题），我们需要添加一个验证“复制约束”（如a(5) = c(7), c(10) = c(12)等约束）的等式，这需要一些巧妙的技巧。

我们的策略是设计一个“坐标对累加器”，一个多项式p(x) 的工作原理如下：首先，让X(x)和Y(x)两个多项式表示一组点的x和y坐标（例如表示集合((0, -2), (1, 1), (2, 0), (3, 1)), 你可设置X(x) = x以及Y(x) = x^3 – 5x^2 + 7x – 2)。我们的目标是让p(x) 代表所有点，直到（但不包括）给定的位置，所以 p(0)从1开始，p(1)只代表第一个点，p(2)是第一个点和第二个点，诸如此类。我们将通过“随机”选择两个常数v1和v2，并使用约束p(0) = 1以及p(x+1) = p(x) * (v1 + X(x) + v2 * Y(x)) 构造p(x)，至少在域（0，1，2，3）内。例如，让v1=3和v2=2，我们得到：

注意（除了第一列）每个p(x) 值，等于它左边的值乘以它左上面的值。

我们关心的结果是p(4) = -240 。现在，考虑这样的情况，我们设置X(x) = 2⁄3 x^3 – 4x^2 + 19⁄3 x（即，在坐标（0，1，2，3）处定值为（0，3，2，1）的多项式） ，而不是X(x) = x。

如果你运行同样的过程，你会发现你也会得到p(4) = -240。

这不是巧合（事实上，如果你随机从一个足够大的域中选择v1和v2，则几乎永远不会巧合地发生）。相反，这是因为 Y(1) = Y(3)，所以如果你“交换”点 (1, 1) 和（3，1）的X坐标，你就不会改变点的集合，并且因为累加器对集合进行编码（因为乘法不关心顺序），所以最后的值将是相同的。

现在，我们可以开始了解我们将用来证明复制约束的基本技术。首先，考虑一个简单的例子，我们只想证明在一组线中的复制约束（例如，我们想证明a（1）=a（3））。我们将生成两个坐标累加器：一个是X(x) = x 和Y(x) = a(x)，另一个是Y(x) = a(x)，而X’(x)是对每个复制约束中的值的翻转排列（或重新排列）定值的多项式。在a(1) = a(3)的情况下，这意味着排列将开始于0 3 2 1 4…. 第一个累加器将压缩 ((0, a(0)), (1, a(1)), (2, a(2)), (3, a(3)), (4, a(4))…，第二个压缩（（0，A（0）），（3，A（1）），（2，A（2）），（1，A（3）），（4，A（4））……只有当a(1) = a(3)时，两者才能给出相同的结果。

为了证明a，b和c之间的约束，我们使用了相同的过程，但是我们将所有三个多项式的点“累加”在一起。我们给a, b, c赋值一些X坐标（例如a为Xa(x) = x 即0...n-1, b为Xb(x) = n+x，即n…2n-1，c 为Xc(x) = 2n+x，即2n…3n-1。为了证明在不同线集之间跳跃的复制约束，“替换”X坐标将是所有三个集合上的排列片段。例如，如果我们想用n = 5 证明a（2）=b（4），那么X’a(x) 将有定值0 1 9 3 4，X’b(x)将有定值5 6 7 8 2（注意2和9翻转，其中9对应于b4线）。 然后，我们将不再像以前那样检查一次过程中的相等性（即检查p(4) = p’(4)），而是检查每侧三次不同运行的乘积：

两边的三个 p(n)定值的乘积将a、b和c中的所有坐标对累加在一起，因此这允许我们像以前一样进行检查，除此之外，我们现在不仅可检查三组线A、B或C中一组内的位置之间的复制约束，还可以检查一组线与另一组线之间的复制约束（例如，在a(2) = b(4)中）。

就这些了！

 

把所有东西放到一起

 

实际上，所有这些数学运算都不是在整数上进行的，而是在素数域上进行的；请检查此处的“模块化数学插曲”部分，以了解素数域是什么。此外，出于数学上的原因，最好是用快速傅里叶变换（FFT）实现来阅读和理解这篇文章，而不是用x=0....n-1表示线指数，我们将使用ω：1，ω，ω^2….ω^n-1的幂, 其中ω是域中的一个高次单位根。这与数学无关，只是坐标对累加器约束检查方程从p(x + 1) = p(x) * (v1 + X(x) + v2 * Y(x)) 更改为p(ω * x) = p(x) * (v1 + X(x) + v2 * Y(x))，而不是使用0..n-1, n..2n-1, 2n..3n-1作为坐标，我们使用ω^i,g * ω^i,其中g可以是域中的某些随机高阶元素。

现在让我们写出所有需要检查的方程式。首先，主门约束满足性检查：

然后是多项式累加器转换约束：

然后多项式累加器开始和结束约束：

用户提供的多项式是：

 

1. 线分配 a(x), b(x), c(x)；
2. 坐标累加器Pa(x), Pb(x), Pc(x), Pa’(x), Pb’(x), Pc’(x)；
3. 商H(x)和H1(x)…H6(x)；

证明者和验证者需要提前计算的程序特定多项式为：

1. QL(x), QR(x), QO(x), QM(x), QC(x)，它们共同代表电路中的门（注意QC(x) 编码公共输入，因此可能需要在runtime对其进行计算或修改）；
2. “排列多项式”σa(x), σb(x) 和 σc(x)，它们编码a, b和c线之间的复制约束；

注意，验证者只需要存储这些多项式的承诺（commitments）。上述方程中仅存的多项式是Z(x) = (x – 1) * (x – ω) * … * (x – ω^(n-1)) ，其设计目的是在所有这些点上计算为零。幸运的是，可以选择ω使这个多项式很容易计算：通常的方法是选择ω来满足ω^n=1 , 在这种情况下Z(x) = x^n – 1。

对v1和v2的唯一限制是，在v1和v2已知之后，用户不能选择a(x), b(x)或 c(x)，所以我们可通过计算a（x）、b（x）和c（x）的承诺哈希的v1和v2来满足这个要求。。

所以现在我们已经把程序满足问题，变成了用多项式满足几个方程的简单问题，PLONK中有一些优化，其可以允许我们去掉上面方程中的很多多项式，为了简单考虑，我将不再讨论这些。但是多项式本身（无论是程序特定的参数还是用户输入），都是很大的。

所以下一个问题是，我们如何绕过这个问题，才能让证明变简短？

 

多项式承诺

 

多项式承诺（polynomial commitment）是一个短对象，其“代表”一个多项式，并允许你验证该多项式的计算，而不需要实际包含多项式中的所有数据。也就是说，如果有人给你一个代表P(x)的承诺c，他们可以给你一个证明，然后说服你对于某个特定的z，P(z) 值是多少。还有一个进一步的数学结果表明，在一个足够大的域上，如果关于在随机z上定值的多项式的某些类型的方程（在z已知之前选择）是真的，那么这些相同的方程对整个多项式也是真的。例如，如果P(z) * Q(z) + R(z) = S(z) + 5，那么我们知道P(x) * Q(x) + R(x) = S(x) + 5通常是极有可能的。使用这样的多项式承诺，我们可以很容易地检查上面所有的多项式方程。作出承诺，使用它们作为输入生成z，证明在z上每个多项式的定值是什么，然后用这些定值来运行方程，而不是原来的多项式。那这些承诺是如何运作的呢？

有两部分：对多项式P(x) -> c的承诺，以及在某个z处对值P(z)的opening。而要作出承诺，有很多技术，一个例子是FRI，另一个是Kate承诺，我将在下面描述。为了证明一个 opening，有一个简单的通用“减除”技巧：为了证明P(z) = a，你要证明

也是一个多项式（使用另一个多项式承诺）。这是因为如果商是一个多项式（即它不是分数），那么x - z是P(x) - a的一个因子，所以(P(x) - a)(z) = 0，所以 P(z) = a。用一些多项式试试，比如P(x) = x^3 + 2*x^2+5 (z=6，a=293),然后试试 (z = 6, a = 292)，看看它是如何失败的（如果你很懒，可以看看WolframAlpha给出的结果：（1），（2））

另请注意一个一般优化：为了同时证明多个多项式的多个opening，在提交输出后，对多项式和输出的随机线性组合执行减除技巧。

那么，承诺本身是如何运作的呢？幸运的是，Kate 承诺要比FRI简单得多。可信设置过程生成一组椭圆曲线点G, G * s, G * s^2 …. G * s^n，以及G2 * s，其中G 和G2是两个椭圆曲线组的生成器，而s则是一个一旦程序完成就会被遗忘的秘密（注意，这个设置有多个版本，它是安全的，只要至少有一个参与者忘记了他们分享的秘密）。这些点会被公布，并被认为是方案的“证明关键”，任何需要作出多项式承诺的人都需要使用这些点。通过将证明密钥中的前d+1个点中的每一点乘以多项式中的相应系数，并将结果相加，对d次多项式作出承诺。

注意，这提供了在s处的多项式的“定值”，而不知道s。例如，x^3 + 2x^2+5 将由(G * s^3) + 2 * (G * s^2) + 5 * G表示。我们可以用符号[P]来表示用这种方式（即G * P(s)）编码的P。在做减除技巧时，可以使用椭圆曲线对来证明这两个多项式实际上满足关系：检查e([P] - G * a, G2) = e([Q], [x] - G2 * z)是否作为检查P(x) - a = Q(x) * (x - z)的代理。

但最近也出现了其他类型的多项式承诺。一个新的方案被称为DARK（“丢番图知识论证”）使用了“隐序组”如类组（class groups）来实现另一种多项式承诺。隐藏顺序组是唯一的，因为它们允许你将任意大的数字压缩到组元素当中，甚至可以压缩比组元素大得多的数字，这样就不会被“欺骗”。从VDF到累加器，从范围证明到多项式承诺的构造，都可在此基础上构建。另一种选择是使用防弹证明（bulletproofs），使用常规的椭圆曲线组，代价是验证所需的时间要长得多。因为多项式承诺比完全零知识证明方案要简单得多，我们可以期望将来会有更多这样的方案被创建出来。

 

概括

 

最后，我们再讨论一下这个方案，给定一个程序P，将其转换为一个电路，并生成一组如下所示的方程：

然后将这组方程转换为一个多项式方程：

你还可以从回路中生成复制约束的列表。从这些复制约束生成表示排列线指数的三个多项式：σa(x), σb(x), σc(x)。要生成证明，需要计算所有线的值，并将其转换为三个多项式：a(x), b(x), c(x)。作为置换检查参数的一部分，你还可以计算六个“坐标对累加器”多项式。最后计算辅因子Hi(x)。

多项式之间有一组方程需要检查，你可以通过对多项式作出承诺，在某些随机z处打开它们（同时证明这些opening是正确的），并在这些求值结果上运行方程，而不是在原始多项式上运行方程来完成这项工作。证明本身只是一些承诺和opening，可以用几个方程式来检查，就是这些啦。