# [译]理解 PLONK

By [DavidCai.eth](https://paragraph.com/@davidcai) · 2022-02-20

---

最近，Ariel Gabizon，Zac Williamson 和 Oana Ciobotaru 公布了一个新的普遍用途的零知识证明算法 [PLONK](https://eprint.iacr.org/2019/953.pdf) ，全称为普遍用途的非交互式知识论证的拉格朗日基排列（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）。虽然普遍用途的[零知识证明](https://arxiv.org/abs/1903.12243)协议的[进步与研究](https://eprint.iacr.org/2016/260.pdf)已经进行[持续](https://dci.mit.edu/zksharks)了[许多年](https://eprint.iacr.org/2017/1066)，PLONK（以及早先更复杂 [SONIC](https://www.benthamsgaze.org/2019/02/07/introducing-sonic-a-practical-zk-snark-with-a-nearly-trustless-setup/) 和最近的 [Marlin](https://eprint.iacr.org/2019/1047.pdf)）为这类证明带来了在可用性上的可观进步。

第一个进步是，PLONK 虽然像 Zcash 的 SNARKs 一样，也要求一个类似的初始可信设置（trusted setup），但是 PLONK 的设置是普适且可更新（universal and updateable）的。这意味着两点，首先，无需再为每一个程序单独配置初始可信设置，对于任意程序都可以使用同一个设置（在设置时会有最大上限）。其次是允许多方一同参与可信设置，只要其中有任意一方是诚实的，那么可信设置就是安全的。这个过程是连续的：第一方参与，然后第二方，第三方...总共的参与方不需要提前预知，新的参与方仅需把自己添加到末尾。在实践环境中，这使得拥有大量参与者的初始可行设置过程变得更加安全。

第二个进步依赖于“奇特的密码学”，即多项式承诺。PLONK 使用了基于椭圆曲线对的 [Kate 承诺](https://ethresear.ch/t/a-non-interactive-proof-of-custody-using-polynomial-commitments/5692)。承诺是可替换的，你也可以替换为例如 FRI 承诺（会将 PLONK 变成某一种 STARK）或者 DARK 承诺（基于隐阶组（hidden-order groups））。这意味着，基于不同的承诺选择，PLONK 可以在证明大小与安全性上进行调整。

1

这意味着，对于不同的证明大小与安全性假设（或者是对于问题有不同立场的开发者），都仍可以共享大部分相同的“算术”工具（即把一个程序转换成一组多项式，然后通过多项式承诺检验它们）。如果这项被广泛接受，那么由于上述共享大量“算术”工具的特征，我们可以预期 PLONK 将会快速优化与发展。

PLONK 是如何工作的
------------

让我们开始解释 PLONK 是如何工作的，我们先聚焦于多项式等式的形式，随后再解释这些等式是如何被验证的。PLONK 的一个关键组成部分（正如 [QAPs 被运用在 SNARKs](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) 一样），就是需要一个过程，将“有一个特定的程序 P，给我一个输入值 X，会输出一个特定的输出值 Y”，转化为一个“给我一组值，满足一组数学等式”问题。程序 P 可以有很多表示。例如，可以是“输出一个数独的答案”，你可以将 P 设置为一个数独验证器，并放上一些初始化值，然后将 Y 设置为 1 ，然后 X 就是解决这个数独的一个合法输入。这可以通过将 P 表示为一个包含加法门与乘法门，然后线都是值，并且每一个门都是等式的电路来实现（例如，乘法是 x6 = x4 \* x7，加法是 x8 = x5 + x9）。

以下是 P(x) = x^3 + x + 5 = 35 （答案为 3） 的电路例子：

2

我们可以为电路标上门与线：

3

在门与线上，我们有两种约束：门约束（连接到相同门的线所对应的等式，例如 a1 \* b1 = c1）和复制约束（电路中连接到同一位置的线都相等，例如 a0 = a1 = b1= b2 = a3 或 c0 = a1）。我们将会构建一个基于少量多项式等式的结构化系统，来表示上述两种约束。

在 PLONK 中，这些等式会以如下形式构建（L = 左，R = 右，O = 输出，M = 乘，C = 常量）：

![4](https://storage.googleapis.com/papyrus_images/2ca604817d7665ec31fef8f7dacd38d57ff5208543792f7700447ed8ad27982c.png)

4

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

![5](https://storage.googleapis.com/papyrus_images/db24a97ffc80a667dbe00d8bdf8148f38a22667569a5fa236c4cb614533b518e.png)

5

将输入常量带入等式，我们可得 ai + bi - ci = 0（即 ai + bi = ci）。如果是一个乘法门，我们设置：

![6](https://storage.googleapis.com/papyrus_images/5fcb56d145c973c4d46d219daa341fbc3013e5b5c415011d6739bd275e7b90f0.png)

6

如果是一个将 ai 设置为某个常量 x ，我们设置：

![7](https://storage.googleapis.com/papyrus_images/8c0c5e8343a7bced78999188daa023a67afb3133d3e9adcd1d632f5fc75fe81c.png)

7

你也许已经注意到，线的两端，值都是相同的（例如 x），即都等于一个独立的变量。目前为止，我们还没有提出一个门的输出需要等于另一个门的输入（我们称之为“复制约束”），PLONK 当然也实现了复制约束，我们会在稍后提及。现在，我们的问题转变为了：证明者拥有一系列 Xai，Xbi 与 Xci ，它们都可以满足一系列相同形式的等式。所以相比于“为这个程序找到合适的输入”，我们已经有了一个更具象的问题，并且我们随后可以使用数学工具继续“压缩”它。

从线性系统到多项式
---------

如果你阅读过 STARKs 或 QAPs 相关的文章，那么这个章节你或许会觉得比较熟悉，如果你还没阅读过的话，也没有关系。核心观点是，以多项式为一种数学工具，将大量的值封装到一个单一对象中。通常，我们以“系数形式”来表达一个多项式，例如：

![8](https://storage.googleapis.com/papyrus_images/718424e5af729bec27b6bcddce99e9c3387fdfd80c319799d256e37e5ec7c720.png)

8

我们也可以通过“点值形式”来表示一个多项式，例如，上述多项式也可以描述为是一个在 x 为 (0, 1, 2, 3) 处， y 值为 (-2, 1, 0, 1)，且度数小于 4 的多项式：

9

下一步，一个拥有多个同样形式方程组的系统，可以被重新解释为一个单一的多项式等式。例如我们有一个方程组系统：

![10](https://storage.googleapis.com/papyrus_images/cc2c07203d97d7fbd8acdb96811ff6f6385ef797dbc5af5bd57fb7146391a338.png)

10

让我们定义 4 个多项式等式：L(x) 是一个度数小于 3 ，且在 x 为 (0, 1, 2) 处，y 值为 (2, 1, 8) 的多项式。同样的 x 值，M(x) 的 y 值为 (-1, 4, -1)，R(x) 的 y 值为 (3, -5, -1)，O(x) 的 y 值为 (8, 5, -2)。这么定义多项式也是完全可以的，后续可以通过[拉格朗日插值法](https://en.wikipedia.org/wiki/Lagrange_polynomial)将多项式从点值形式转换为系数形式。现在，考虑下面这个等式：

![11](https://storage.googleapis.com/papyrus_images/f65fa7ea93d0e36b3dafcf685dca005361d83b3412ca3bb3332e8e8e72a2b5fc.png)

11

在上述公式中，Z(x) 是 (x - 0) \* (x - 1) \* (x - 2) 的缩写，是一个在 x 为 (0, 1, 2) 时，y 值为 0 的最简多项式。这个等式的一个解（例如 x1 = 1，x2 = 6，x3 = 4，H(x) = 0）（译者注：带入上述等式后，可得 L(x) + 6 \* M(x) + 4 \* R(x) - O(x) = 0 ，这个等式在 L(x)，M(x)，R(x)，O(x) 在 x 为 (0, 1, 2) 处都成立），同样也是上述方程组系统的一个解。有一点值得注意，在上述等式中，H(x) 恰好很方便地为 0 ，但在更复杂的例子中，H(x) 可能为非零。

所以我们知道了我们可以将一组很大的输入数据限制在一个多项式中。不过上述我们用来描述门线约束的例子中， x1, x2 与 x3 ，其实都是变量，在不同的等式中都是不同的，我们可以将变量也转换为多项式：

![12](https://storage.googleapis.com/papyrus_images/e8c195369bb52d969f96fa93dc9417a302beb404e1e699c8fcd1308a18c89c50.png)

12

和之前一样，Q 多项式都是从程序生成的已验证参数，a，b，c 多项式都是用户提供的参数。

复制约束
----

现在，让我们回到电路中线的“连接”问题。目前为止，我们有了一组不同的值来满足一组不同的等式。常量门可以通过将值设置为常量来满足，加法和乘法门可以通过设置所有的非必要线为 0 来满足。为了让问题更具挑战性（并且能更贴切地表达我们最初的电路），我们需要验证“复制约束”：例如 a(5) = c(7)，c(10) = c(12) 。这需要一些巧妙的设计。

我们的策略是实现一个“坐标对聚合器（coordinate pair accumulator）”，一个多项式 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，至少在 (0, 1, 2, 3) 域内使用 p(0) = 1 和 p(x + 1) = p(x) \* (v1 + X(x) + v2 \* Y(x)) 来构造 p(x) 。

例如，若 v1 = 3，v2 = 2，我们可以得到：

![13](https://storage.googleapis.com/papyrus_images/56afb210deb6fcaee767535e2d1514370932d2f7ec286731513f4b4dab5896f9.png)

13

我们关心的结果是 p(4) = -240 。现在，我们把 X(x) = x 替换成 X(x) = (2/3) \* x^3 - 4 \* x^2 + (19/3) \* x （这个多项式在 x 值在 (0, 1, 2, 3) 处的 y 值为 (0, 3, 2, 1)）。如果你用这个 X(x) 再次运行上述公式，那么你还是会得到 p(4) = -240 ，这不是巧合（事实上，你可以尝试在一个很大的域里随机选取 v1，v2，这几乎不会发生）。这是因为 Y(1) = Y(3)（译者注：都为 1），所以你将 (1, 1) 和 (3, 1) 的 x 坐标交换后，得到的还是这两个点，并没有改变预设点的集合。所以，我们的聚合器最后得到的结果一致（由于乘法交换律）。

现在，我们学习到了一些用于证明复制约束的基础知识。首先，先考虑一条线的两个值的复制约束（例如 a(1) = a(3)）。我们将创造两个坐标对聚合器：在第一个中， X(x) = x，并且 Y(x) = a(x) ，第二个中，依然是 Y(x) = a(x) ，不过其中 X‘(x) 的值为第一个聚合器中 X(x) 值的重新排列。第一个聚合器将会压缩点集合 ((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 坐标中的一段值（例如 Xa(x) = x，Xb(x) = n + x，Xc(x) = 2n + x）。为了证明电路中线两端的复制约束，“新的 X 坐标“可以理解成是上述三个点集切片的组合。如果我们想要证明当 n = 5 时 a(2) = b(4) ，那么 X’(a) 会有定值 01934 ，X‘(b) 会有定值 56782 （注意 9 和 2 的位置调换了，因为 9 表示 b(4) 线）（译者注：索引从 0 开始）。

我们将不会像之前那样仅检查一个方程的聚合器（如之前检查 p(4) = p’(4)），我们将检查三个聚合器的乘积：

![14](https://storage.googleapis.com/papyrus_images/1e58b2dbe4ce2446ab57d7a6c0c20a293f7999537ae5cac2cc363ac8b6e31534.png)

14

两侧的三个 p(n) 的乘积，将会聚合 a，b 和 c 中的所有坐标点，这使得我们可以不仅三条线 a，b 和 c 内部的一对复制约束。同样也可以用于检查一线与另一线之间的复制约束（例如 a(2) = b(4)）。

汇总
--

现实中，这些数学计算都不是通过整数的，而是通过素数域。可以参阅[这篇文章](https://vitalik.ca/general/2017/11/22/starks_part_2.html)中的模块化数学部分来了解素数域。此外，出于数学上的原因，最好是用[快速傅里叶变换（FFT）](https://vitalik.ca/general/2019/05/12/fft.html)来阅读和理解这篇文章。我们将会使用 ω：1，ω，ω^2...ω^n-1 的幂来表示线的索引（其中 ω 是域中的一个高阶单元根（high-order root-of-unity）），而不是整数 x = 0 ... n-1 。这些不会在数学层面有什么变化，仅仅是将坐标对聚合器的等式从 p(x + 1) = p(x) \* (v1 + X(x) + v2 \* Y(x)) 变为了 p(ω \* x) = p(x) \* (v1 + X(x) + v2 \* Y(x)) ，并且将 x 坐标索引从 0..n-1, n..2n-1, 2n..3n-1 变为了 ω^i，g \* ω^i 和 g^2 \* ω^i （g 为域中一些随机高阶值）。

现在让我们来写些所有需要检验的等式。首先，主体的门约束检查：

![15](https://storage.googleapis.com/papyrus_images/bce7e0fec9aac0ec213d37e1e9d3a9cc8736d252b35b05aa2deeeeab599ac397.png)

15

然后是多项式聚合器状态转化约束（可以将“Z(x) \* H(x)”理解为“仅在我们关心的坐标上等于零，在其他坐标上，等于零是非必要的”）：

![16](https://storage.googleapis.com/papyrus_images/535764b1d99e68d72db383895d024ebda89a836d5af680c9744e9f1570ef2646.png)

16

随后是多项式聚合器开始、结束约束（复制约束）：

![17](https://storage.googleapis.com/papyrus_images/5add6fc0e7a023afe26e5c85c0ae27f370c202e3769ee61f03887702e9e7da79.png)

17

用户提供的多项式是：

*   电路线赋值（wire assignments）：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) 编码为公共输入，所以它可能在运行时有所变化）
    
*   排列多项式 σ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 。

这里有一个细微差别：Pa(ω^(i+1)) 与 Pa(ω^i) 之间的约束，不能够在 ω 的全部幂的取值环上都为真。当当前坐标为 ω^(n-1) 且下一个坐标为 ω^n = 1 时（即回到了聚合器的起始位置），总是为假。为了修复这个问题，我们将约束修改为，要么约束为真，要么 x = ω^(n-1) 。我们可以通过把 x - ω^(n-1) 放进 Z(x) 约束中来做到，这样一来，在这个点的值就为零。

v1，v2 唯一的限制是：用户必须不能在知道 v1，v2 之后，再去选择 a(x)、b(x) 和 c(x) 。我们可以通过从 a(x)、b(x) 和 c(x) 的多项式承诺的哈希来计算 v1，v2，做到这个限制。

目前为止，我们已经把一个程序问题，转化为了一个多项式等式满足问题。PLONK 中还有许多优化，能够允许我们再去掉上述的一部分多项式，但是为了简单起见，这里不再讨论。但是多项式本身（不论是代表程序还是用户输入），目前来说都是很大的。下一个问题是，我们如果绕过这个问题，使得证明变得简短。

多项式承诺
-----

多项式承诺是一个对应多项式的简短“代表”，通过它，不必知晓多项式中的所有数据，也可以验证对应多项式的计算。这意味着，如果有个人给了你一个多项式 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 ，代入每个多项式计算出一个新结果，我们边可以用这个新结果来替换原来的多项式了。那么，多项式承诺是如何运作的呢？

上述过程包含了两个部分，首先是一个多项式承诺 P(X) -> c ，和多项式的任意一个点 z（P(z)）进行的打开（opening）。目前有很多算法可以用于构建一个多项式承诺，例如 [FRI](https://vitalik.ca/general/2017/11/22/starks_part_2.html) ，还有下面将会提到的 Kate 。为了证明一个打开，有一个简单而通用的减除（subtract-and-divide）技巧：为了证明 P(z) = a，你需证明：

![18](https://storage.googleapis.com/papyrus_images/3d3eacb69a3a49939f02769b9ba912c06f97a1c9becf66820f3b03f8253cc628.png)

18

也是一个多项式（使用另一个多项式承诺）。这是因为如果商是一个多项式（即除法的结果不是分数），那么 (x - z) 就是 P(x) - a 的一个因子，所以 (P(x) - a)(z) = 0，所以 P(z) = a。还有一个值得注意的普适优化：为了在同一时间证明多个多项式的打开，在提交输出后，对多项式和输出的随机线性组合可以执行减除技巧。

所以，承诺本身是如何工作的？幸运的是，Kate 承诺的算法比 FRI 简单许多。通过初始可信设置，会生成一组椭圆曲线点 G, G \* s, G \* s^2 … G \* s^n 以及 G2 \* s。其中 G 和 G2 是两个椭圆曲线生成器（generators），s 是一个计算后就会被遗忘的密码（如果是多方生成，只要有一方遗忘了密码，那么这个过程就是安全的）。这些椭圆曲线点会被公开，然后被认为是“证明秘钥（the proving key）”。任何想要创建多项式承诺的人，都需要用到这些点。通过将椭圆曲线点钟的前 d + 1 个点乘以多项式中的响应系数，并将结果累加，就可以得到一个 d 阶多项式的承诺。

注意，这里在无需知道 s （已被遗忘）的情况下，得出了一个有关 s 信息的多项式。例如，x^3 + 2x^2 + 5 将会由 (G \* s^3) + 2 \* (G \* s^2) + 5 \* G 来表示。我们可以用符号 \[P\] 来表示以这种方式（即 G \* P(s)）编码的多项式 P 。在使用减除技巧时，你可以通过[椭圆曲线配对](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)来验证两个多项式是否符合关系要求：将检查 e(\[P\] - G \* a, G2) = e(\[Q\], \[x\] - G2 \* z) 来作为 P(x) - a = Q(x) \* (x - z) 的代理检查。

最近也出现来一些其他的多项式承诺算法。一个新的方案成为 DARK （丢番图知识论证（Diophantine arguments of knowledge）），使用了例如[类组（class groups）](https://blogs.ams.org/mathgradblog/2018/02/10/introduction-ideal-class-groups/)的隐阶组（hidden order groups）来实现了多项式承诺。隐藏组是唯一的，通过使用它们，将会允许你压缩任意大的数字压入组中的元素中，即使数字比组中的元素大得多。从 VDFs 到[聚合器](https://ethresear.ch/t/rsa-accumulators-for-plasma-cash-history-reduction/3739)再到多项式承诺，都可以基于此来进行构造，另一种算法是子弹证明（bulletproofs），它使用常规的椭圆曲线组，代价是验证所需的时间要长得多。因为多项式承诺比完全零知识证明方案要简单得多，我们可以期望将来会有更多这样的方案被创建出来。

总结
--

让我们来总结一下。给定一个程序 P ，将其转换为电路后，生产一组如下形式的等式：

![19](https://storage.googleapis.com/papyrus_images/fee83fb76b4d859e725c5b1b2bbee9bb5eb3fe688b9f529cacdcc463b1834a97.png)

19

然后将这组等式转化为单个多项式：

![20](https://storage.googleapis.com/papyrus_images/fbf3eb2ee0483e37bea1880aec180651564f7b56e27d386b057c42c213e4b3dd.png)

20

然后还需要从电路中生成复制约束，你会生成三个多项式 σa(x)，σb(x)，σc(x) 用于表示置换线（permuted wire）上的索引。为了生成一个证明，你计算了线上的所有值，然后将它们转换为了三个多项式 a(x)，b(x)，c(x)。作为置换检查参数的一部分，你还需要计算六个坐标对聚合器（coordinate pair accumulator）多项式。最后，计算辅因子 Hi(x) 。

在多项式之间，还有一组方程需要被检查。你可以通过创建这些多项式的多项式承诺，在一些随机点 z 进行打开，然后在这些打开结果上运行方程，而不是在原始的多项式上。所以证明本身就是一些能被一组方程检查的多项式承诺和打开。

原文链接
----

[https://vitalik.ca/general/2019/09/22/plonk.html](https://vitalik.ca/general/2019/09/22/plonk.html)

---

*Originally published on [DavidCai.eth](https://paragraph.com/@davidcai/plonk)*