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（基于隐藏顺序组）。这意味着该方案在理论上与证明大小和安全性假设之间的任何（可实现的）权衡兼容。

p1

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



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):

p2

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

p3

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

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

p4

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

p5

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

p6

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

p7

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



从线性系统到多项式


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

p8

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

p9

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

p10

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

p11

在这里，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变量在每个方程中是不同的。我们可以用同样的方法使变量本身成为多项式而不是常数来处理这个问题。所以我们得到：

p12

如前所述，每个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，我们得到：

p13

p14

注意（除了第一列）每个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)），而是检查每侧三次不同运行的乘积：p15

两边的三个 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可以是域中的某些随机高阶元素。

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

p16

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

p17

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

p18用户提供的多项式是：



线分配 a(x), b(x), c(x)；
坐标累加器Pa(x), Pb(x), Pc(x), Pa’(x), Pb’(x), Pc’(x)；
商H(x)和H1(x)…H6(x)；
证明者和验证者需要提前计算的程序特定多项式为：

QL(x), QR(x), QO(x), QM(x), QC(x)，它们共同代表电路中的门（注意QC(x) 编码公共输入，因此可能需要在runtime对其进行计算或修改）；
“排列多项式”σ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中有一些优化，其可以允许我们去掉上面方程中的很多多项式，为了简单考虑，我将不再讨论这些。但是多项式本身（无论是程序特定的参数还是用户输入），都是很大的。

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



多项式承诺，就是这些啦。

来源：区块链新闻  www.liandongfang.com