关于Plonk，你想知道的一切

介绍

零知识证明，也称为 ZKP，由于其在将计算委托给不受信任的服务器以及解决去中心化账本中的可扩展性问题方面的众多应用而变得越来越流行。通过使用 ZKP，我们可以证明给定计算的有效性，而无需泄露敏感信息，并且证明是简洁且可快速验证的。STARK（可扩展的透明知识论证）和 SNARK（简洁的非交互式知识论证）是密码学原语，允许我们将计算机程序转换为多项式之间的关系并证明其正确执行，并在去中心化金融、治理和计算中具有众多应用。有关这些主题的更多背景信息，你可以查看我们之前关于 STARKs 和 SNARKs 的帖子。

由于其效率和灵活性，PLONK 是零知识 (ZK) 社区中流行的密码学证明系统，具有 Halo2 和 Kimchi 等定制版本。它能够通过将程序转换为电路表示来验证由不受信任方执行的复杂计算。该系统依赖于算术化，它将逻辑电路转换为多项式表达式。算术化的主要思想是将计算表示为一组多项式方程。这些方程的解对应于电路的输出。在本节中，我们将深入研究 PLONK 中的算术化是如何工作的，以及用于生成和验证证明的协议。

原始论文可以在这里找到

符号

在本文中，我们将使用以下符号。如果你不熟悉其中一些概念，你可以查看我们的数学生存工具包。

符号 $\mathbb{F}$ 表示一个有限域。它一直都是固定的。符号 $\omega$ 表示 $\mathbb{F}$ 中的本原单位根，即 $\omega^n = 1$ 并且对于 $0<k<n$，$\omega^k \neq 1$。

所有多项式的系数都在 $\mathbb{F}$ 中，并且变量通常用 $X$ 表示；我们将此集合表示为 $\mathbb{F}[X]$。我们用单个字母（如 $p, a, b, z$）表示多项式。我们只在想强调它是 $X$ 中的多项式或我们需要从另一个多项式显式定义一个多项式时才将其标记为 $z(X)$。例如，当将多项式 $z$ 与多项式 $\omega X$ 组合时，结果表示为 $z' := z(\omega X)$。符号 $'$ 不 用于表示导数。

在域 $H = {h_0, \dots, h_n} \subset \mathbb{F}$ 中进行插值时，符号 $L_i$ 表示拉格朗日基。也就是说，$L_i$ 是这样的多项式：对于所有 $j \neq i$，有 $L_i(h_j) = 0$，并且 $L_i(h_i) = 1$。

如果 $M$ 是一个矩阵，则 $M_{i,j}$ 表示第 $i$ 行和第 $j$ 列的值。

想法和组成部分

程序。我们的玩具示例

为了更清楚起见，我们将在本文中使用以下玩具程序。

INPUT:
  x

PRIVATE INPUT:
  e

OUTPUT:
  e * x + x - 1

观察者会注意到，我们可以将这个程序写成 $(e+1) \times x - 1$，这更有意义。但现在编写的方式有助于我们更好地解释 PLONK 的算术化。所以我们坚持这样做。

这个想法是验证者持有一些值 $x$，比如 $x=3$。他把它交给证明者。她使用她选择的值 $e$ 执行程序，并发送输出值（比如 $8$），以及证明 $\pi$，证明程序的正确执行并获得正确的输出。

在 PLONK 的上下文中，程序的输入和输出都被认为是 公开输入。这听起来可能很奇怪，但这是因为这些是验证算法的输入。在这种情况下，验证算法接受元组 $(3, 8, \pi)$，如果玩具程序使用输入 $x=3$、一些未向验证者透露的私有值 $e$ 执行，并且输出为 $8$，则输出 Accept。否则，它输出 Reject。

PLONK 可用于将程序执行委托给不受信任的各方，但它也可用于作为知识证明。证明者可以使用我们的程序来证明她知道有限域中某个值 $x$ 的乘法逆，而无需透露它。她可以通过向验证者发送元组 $(x, 0, \pi)$ 来做到这一点，其中 $\pi$ 是执行我们的玩具程序的证明。

这在我们的玩具示例中毫无意义，因为任何验证者都可以有效地执行字段元素的求逆。但是将我们的程序更改为以下内容，你将获得 SHA256 摘要的 pre-image 的知识证明。

PRIVATE INPUT:
  e

OUTPUT:
  SHA256(e)

这里除了证明者的私有输入外，没有其他输入。正如我们提到的，程序的输出 $h$ 随后成为验证算法的输入的一部分，在这种情况下，验证算法接受 $(h, \pi)$。

PLONK 算术化

这个过程采用了特定程序的电路，并产生了一组数学工具，我们可以使用这些工具来生成和验证执行证明。最终结果将是一组八个多项式。要计算它们，我们首先需要定义两个矩阵。我们称它们为 $Q$ 矩阵和 $V$ 矩阵。多项式和矩阵仅取决于程序，而不取决于任何特定的执行。因此，它们可以计算一次并用于每个执行实例。为了理解它们有什么用处，我们需要从 执行轨迹 开始。

电路和执行轨迹

将程序视为一系列门，这些门具有左操作数、右操作数和一个输出。两个最基本的门是乘法门和加法门。在我们的示例中，一种看待我们的玩具程序的方式是将其看作是三个门的组合。

门 1：左：$e$，右：$x$，输出：$u = e \times x$

门 2：左：$u$，右：$x$，输出：$v = u + x$

门 3：左：$v$，右：$1$，输出：$w = v - 1$

在执行电路时，所有这些变量都将采用具体的值。我们可以将所有这些信息以表格形式表示。它将是一个矩阵，包含所有门的左值、右值和输出值——每个门一行。我们称这个矩阵的列为 $L, R, O$。让我们为 $x=3$ 和 $e=2$ 构建它们。我们得到 $u=6$, $v=9$ 和 $w=5$。所以第一个矩阵是：

A	B	C
2	3	6
6	3	9
9	-	8

最后一个门减去一个常数值，常数值是程序的一部分，而不是变量。所以它只有一个输入而不是两个输入。输出是从它减去 $1$ 的结果。这就是它与第二个门的处理方式略有不同的原因。$R$ 列中的符号 "-" 是由此产生的。有了它，我们的意思是“任何值”，因为它不会改变结果。在下一节中，我们将看到我们如何实现这一点。在这里，当任何值都可以放在那里时，我们将使用这种符号。如果我们必须选择一些，我们将默认为 $0$。

我们得到的是一个有效的执行轨迹。并非所有这种形状的矩阵都将是程序执行的轨迹。$Q$ 矩阵和 $V$ 矩阵将是区分有效和无效执行轨迹的工具。

$Q$ 矩阵

正如我们所说，它只取决于程序本身，而不取决于任何特定的评估。它为每个门都有一行，它的列称为 $Q_L, Q_R, Q_O, Q_M, Q_C$。它们对行的门类型进行编码，并且被设计为满足以下条件。

声明： 如果列 $L, R, O$ 对应于电路的有效评估，则对于所有 $i$，以下等式成立 $Ai Q{Li} + Bi Q{Ri} + A_i Bi Q{Mi} + Ci Q{Oi} + Q_{Ci} = 0$

通过示例可以更好地理解这一点。该行表示一个乘法门：

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
0	0	1	-1	0

并且在跟踪矩阵中对应于该门执行的行是

A	B	C
2	3	6

该行声明中的等式是 $2 \times 0 + 3 \times 0 + 2 \times 3 \times 1 + 6 \times (-1) + 0$，等于 $0$。下一个是加法门。该行表示：

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
1	1	0	-1	0

跟踪矩阵中对应的行是

A	B	C
6	3	9

并且声明的等式是 $6 \times 1 + 3 \times 1 + 2 \times 3 \times 0 + 9 \times (-1) + 0$，总和为 $0$。我们的最后一行是添加常数的门。该行可以表示添加常量 $C$

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
1	0	0	-1	C

在我们的例子中，$C = -1$。执行轨迹中相应的行是

A	B	C
9	-	8

并且声明的等式是 $9 \times 1 + 0 \times 0 + 9 \times 0 \times 0 + 8 \times (-1) + C$。这也是零。

总而言之，整个 $Q$ 矩阵是

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
0	0	1	-1	0
1	1	0	-1	0
1	0	0	-1	-1

我们看到声明对于我们的特定执行是真的：

$2 \times 0 + 3 \times 0 + 2 \times 3 \times 1 + 6 \times (-1) + 0 = 0$

$6 \times 1 + 3 \times 1 + 6 \times 3 \times 0 + 9 \times (-1) + 0 = 0$

$9 \times 1 + 0 \times 0 + 9 \times 0 \times 0 + 8 \times (-1) + (-1) = 0$

对于我们的示例来说不是至关重要的，但是乘以常量 $C$ 可以用以下方法表示：

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
C	0	0	-1	0

你可能已经注意到，在某些情况下，有几种表示相同门的方法。我们稍后会利用这一点。

$V$ 矩阵

前一节中的声明不是“当且仅当”的声明，因为以下跟踪列确实满足方程式，但不对应于有效的执行：

A	B	C
2	3	6
0	0	0
20	-	19

$V$ 矩阵编码了结果从一个门到后续门的右操作数或左操作数的传递。这些被称为 连线。像 $Q$ 矩阵一样，它与单独的评估无关。它由所有输入和中间变量的索引组成。在这种情况下，该矩阵是：

L	R	O
0	1	2
2	1	3
3	-	4

这里 $0$ 是 $e$ 的索引，$1$ 是 $x$ 的索引，$2$ 是 $u$ 的索引，$3$ 是 $v$ 的索引，$4$ 是输出 $w$ 的索引。现在我们可以更新声明以具有“当且仅当”声明。

声明： 设 $T$ 为具有列 $A, B, C$ 的矩阵。当且仅当以下情况时，它对应于电路的正确评估

1. 对于所有 $i$，以下等式成立 $Ai Q{Li} + Bi Q{Ri} + A_i Bi Q{Mi} + Ci Q{Oi} + Q_{Ci} = 0$，
2. 对于所有 $i, j, k, l$ 使得 $V{i,j} = V{k,l}$，我们有 $T{i,j} = T{k,l}$。

所以现在，我们格式错误的示例未通过第二个检查。

自定义门

我们的矩阵现在很好，但是可以对其进行优化。让我们这样做以展示 PLONK 的这种灵活性并减小我们示例的大小。

PLONK 可以将五个列组合起来构建更复杂的门。因此，可以用多种方式表达相同的程序。在我们的例子中，我们可以将所有三个门合并为一个自定义门。$Q$ 矩阵最终成为一行。

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
0	1	1	-1	-1

以及 $V$ 矩阵

L	R	O
0	1	2

此表示形式的跟踪矩阵只是

A	B	C
2	3	8

我们检查它是否满足等式

$2 \times 0 + 3 \times 1 + 2 \times 3 \times 1 + 8 \times (-1) + (-1) = 0$

当然，我们不能总是将整个程序压缩到单个门中。

公共输入

除了执行程序操作的门之外，还必须将其他行合并到这些矩阵中。这是因为证明者不仅必须证明她运行了程序，还必须证明她使用了适当的输入。此外，该证明必须包括对输出值的断言。因此，需要一些额外的行。在我们的例子中，这些是前两个和最后一个。原始的一个现在位于第三行。

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
-1	0	0	0	3
-1	0	0	0	8
1	1	1	-1	1
1	-1	0	0	0

这是更新后的 $V$ 矩阵

L	R	O
0	-	-
1	-	-
2	0	3
1	3	-

第一行强制索引为 $0$ 的变量取值 $3$。类似地，第二行强制索引为 $1$ 的变量取值 $8$。这两个将是验证者的公共输入。最后一行检查程序的输出是否为声明的输出。

精明的观察者会注意到，通过合并这些新行，$Q$ 矩阵不再独立于特定的评估。这是因为 $Q_C$ 列的前两行包含特定于特定执行实例的具体值。我们可以删除这些值，并将它们视为一个额外的单列矩阵 $PI$（代表公共输入）的一部分，以保持独立性。此列在所有与公共输入无关的行中都包含零。我们在 $Q_C$ 列中放置零。证明者和验证者负责填写 $PI$ 矩阵。在我们的示例中，它是

$PI$
3
8
0
0

最终的 $Q$ 矩阵是

$Q_L$	$Q_R$	$Q_M$	$Q_O$	$Q_C$
-1	0	0	0	0
-1	0	0	0	0
1	1	1	-1	1
1	-1	0	0	0

我们最终得到两个仅取决于程序的矩阵 $Q$ 和 $V$，以及两个取决于特定评估的矩阵，即 $ABC$ 和 $PI$ 矩阵。声明的更新版本如下：

声明： 设 $T$ 为具有列 $A, B, C$ 的矩阵。当且仅当以下情况时，它对应于电路的评估

1. 对于所有 $i$，以下等式成立 $Ai Q{Li} + Bi Q{Ri} + A_i Bi Q{Mi} + Ci Q{Oi} + Q_{Ci} + PI_i = 0$，
2. 对于所有 $i, j, k, l$ 使得 $V{i,j} = V{k,l}$，我们有 $T{i,j} = T{k,l}$。

从矩阵到多项式

上一节介绍了 PLONK 中算术化过程的工作原理。对于具有 $n$ 个公共输入和 $m$ 个门的程序，我们构造了两个矩阵 $Q$ 和 $V$，其大小分别为 $(n+m+1) \times 5$ 和 $(n+m+1) \times 3$，并且满足以下条件。设 $N = n + m + 1$。

声明： 设 $T$ 为具有列 $A, B, C$ 的 $N \times 3$ 矩阵，$PI$ 为 $N \times 1$ 矩阵。当且仅当以下条件成立时，它们对应于公共输入由 $PI$ 给出的有效执行实例

1. 对于所有 $i$，以下等式成立 $Ai Q{Li} + Bi Q{Ri} + A_i Bi Q{Mi} + Ci Q{Oi} + Q_{Ci} + PI_i = 0$，
2. 对于所有 $i, j, k, l$ 使得 $V{i,j} = V{k,l}$，我们有 $T{i,j} = T{k,l}$
3. 对于所有 $i > n$，$PI_i = 0$。

现在输入多项式来压缩大多数这些方程式。我们将条件 (1) 和 (2) 中的所有方程式转换为仅几个多项式方程式。

设 $\omega$ 为本原 $N$ 次单位根，设 $H = {\omega^i : 0 \leq i < N}$。设 $a, b, c, q_L, q_R, q_M, q_O, q_C, pi$ 为在域 $H$ 中插值列 $A, B, C, Q_L, Q_R, Q_M, Q_O, Q_C, PI$ 的次数至多为 $N$ 的多项式。这意味着例如，对于所有 $i$，$a(\omega^i) = A_i$，对于所有其他列也是如此（有关插值的示例，请参见我们先前关于 STARK 的帖子）。

这样，声明的条件 (1) 等效于对于 $H$ 中的所有 $x$，$a(x)q_L(x) + b(x)q_R(x) + a(x)b(x)q_M(x) + c(x)q_O(x) + q_c(x) + pi(x) = 0$。这仅通过多项式的定义得出。但是在多项式领域中，这也等效于：

1. 存在一个多项式 $t$，使得 $aq_L + bq_R + abq_M + cq_O + q_c + pi = z_H t$，其中 $z_H$ 是多项式 $X^N - 1$。

为了将条件 (2) 简化为多项式方程式，我们必须引入排列的概念。排列是对集合的重新排列，通常表示为 $\sigma$。对于有限集合，它是从集合到自身的一个映射，它采用所有值。在我们的例子中，集合将是所有对的集合

$I = {(i, j): \text{ 使得 } 0 \leq i < N, \text{ 且 } 0 \leq j < 3}$

矩阵 $V$ 导出了此集合的排列，其中 $\sigma((i, j))$ 等于位置 $(i, j)$ 处的值的 下一个 出现的索引。如果你已经处于最后一次出现，请转到第一次出现。通过 下一个，我们的意思是以下出现，就好像这些列堆叠在彼此之上。(Let's see how this works in the example circuit. Recall $V$ is

L	R	O
0	-	-
1	-	-
2	0	3
1	3	-

在这种情况下，置换是映射 $\sigma((0, 0)) = (2, 1)$، $\sigma((0, 1)) = (0, 3)$، $\sigma((0, 2)) = (0, 2)$، $\sigma((0, 3)) = (0, 1)$، $\sigma((2, 1)) = (0, 0)$، $\sigma((3, 1)) = (2, 2)$، $\sigma((2, 2)) = (3, 1)$。具有 - 值的位置现在无关紧要。

不难看出，条件 (2) 等价于：对于所有 $(i, j) \in I$，$T{i,j} = T{\sigma((i,j))}$。

稍微不太明显的是，反过来，此条件等效于检查以下集合 $A$ 和 $B$ 是否相等

$A = {((i, j), T_{i,j}) : (i, j) \in I}$

$B = {(\sigma((i, j)), T_{i,j}) : (i, j) \in I}$.

此等价性的证明很简单。尝试一下！

在我们的示例中，有问题的集合分别是

${((0, 0), T{0,0}), ((0, 1), T{0,1}), ((0, 2), T{0,2}), ((0, 3), T{0,3}), ((2, 1), T{2,1}), ((3, 1), T{3,1}), ((2, 2), T_{2,2})}$

和

${((2, 1), T{0,0}), ((0, 3), T{0,1}), ((0, 2), T{0,2}), ((0, 1), T{0,3}), ((0, 0), T{2,1}), ((2, 2), T{3,1}), ((3, 1), T_{2,2})}$,

你可以通过检查来检查这些集合是否一致。回想一下我们的跟踪矩阵 $T$ 是

A	B	C
3	-	-
8	-	-
2	3	8
8	8	-

检查这些集合的相等性可以简化为多项式方程式。这是 PLONK 使用的一种非常好的方法。为了更好地理解它，让我们从一个更简单的情况开始。

集合的相等性

假设我们有两个集合 $A = {a_0, a_1}$ 和 $B = {b_0, b_1}$，它们是 $\mathbb{F}$ 中的两个字段元素。我们有兴趣检查它们是否相等。

我们可以做的一件事是计算 $a_0 a_1$ 和 $b_0 b_1$ 并比较它们。如果集合相等，那么这些元素必定是相同的。

但是，反之则不然。例如，集合 $A = {4, 15}$ 和 $B = {6, 10}$ 的元素乘积的结果都是 $60$。但是它们不相等。所以这对于检查相等性不好。

多项式在这里可以解救我们。我们可以做的是考虑以下 多项式 集合 $A' = {a_0 + X, a_1 + X}$, $B' = {b_0 + X, b_1 + X}$。当且仅当集合 $A'$ 和 $B'$ 相等时，集合 $A$ 和 $B$ 才相等。这是因为多项式的相等性归结为它们系数的相等性。但是 $A'$ 和 $B'$ 之间的区别在于，元素乘积的方法现在有效。也就是说，当且仅当 $(a_0 + X)(a_1 + X) = (b_0 + X)(b_1 + X)$ 时，$A'$ 和 $B'$ 才相等。这不是很明显，但是由多项式具有的称为 唯一分解 的属性得出。这里重要的是线性多项式就像素因子一样。无论如何，你可以认为这是理所当然的。这个技巧的最后一部分是使用 Schwartz-Zippel 引理并返回到字段元素的土地。这意味着，如果对于某个随机元素 $\gamma$，我们有 $(a_0 + \gamma)(a_1 + \gamma) = (b_0 + \gamma)(b_1 + \gamma)$，那么以极大的概率，等式 $(a_0 + X)(a_1 + X) = (b_0 + X)(b_1 + X)$ 成立。

总而言之，如果对于某个随机元素 $\gamma$，我们有 $(a_0 + \gamma)(a_1 + \gamma) = (b_0 + \gamma)(b_1 + \gamma)$，那么集合 $A$ 和 $B$ 相等。当然，这也适用于具有两个以上元素的集合。让我们记下来。

事实： 设 $A = {a0, \dots, a{k-1}}$ 和 $B = {b0, \dots, b{k-1}}$ 为字段元素的集合。如果对于某个随机 $\gamma$，以下等式成立

$\prod_{i=0}^{k-1} (ai + \gamma) = \prod{i=0}^{k-1} (b_i + \gamma)$,

那么以极大的概率，$A$ 等于 $B$。

这是一个将此检查简化为多项式方程式的技巧。设

$H$ 为 ${1, \omega, \dots, \omega^{k-1}}$ 形式的域，其中 $\omega$ 是本原 $k$ 次单位根。设 $f$ 和 $g$ 是在 $H$ 中插值以下值 的多项式。

$(a0 + \gamma, \dots, a{k-1} + \gamma)$,

$(b0 + \gamma, \dots, b{k-1} + \gamma)$,

那么 $\prod_{i=0}^{k-1} (ai + \gamma)$ 等于 $\prod{i=0}^{k-1} (b_i + \gamma)$ 当且仅当存在一个多项式 $Z$，使得

$Z(\omega^0) = 1$

对于所有 $h \in H$，$Z(h) f(h) = g(h) Z(\omega h)$

让我们看看为什么。假设 $\prod_{i=0}^{k-1}(ai+\gamma)$ 等于 $\prod{i=0}^{k-1}(b_i+\gamma)$。构造 $Z$ 作为插值以下值的多项式 $(1,\frac{a_0+\gamma}{b_0+\gamma},\frac{(a_0+\gamma)(a_1+\gamma)}{(b_0+\gamma)(b1+\gamma)},\dots,\prod{i=0}^{k-2}\frac{a_i+\gamma}{b_i+\gamma}),(1,\frac{a_0+\gamma}{b_0+\gamma},\frac{(a_0+\gamma)(a_1+\gamma)}{(b_0+\gamma)(b1+\gamma)},\dots,\prod{i=0}^{k-2}\frac{a_i+\gamma}{bi+\gamma})$, 在与$f$和$g$相同的域中。这样可行。反过来，假设存在这样的多项式$Z$。通过在$1,\omega,\dots,\omega^{k-2}$处计算方程$Z(X)f(X)=g(X)Z(\omega X)$，并使用递归，我们得到$Z(\omega^{k-1})=\prod{i=0}^{k-2}(ai+\gamma)/\prod{i=0}^{k-2}(b_i+\gamma)$。此外，在$\omega^{k-1}$处计算它，我们得到$Z(\omega^{k-1})f(\omega^{k-1})g(\omega^{k-1})=Z(\omega^k)=Z(w_0)=1$。

第二个等式成立是因为$\omega^k=\omega0$，因为它是一个$k$次单位根。用$f,g$和$Z$的值展开，得到$\prod{i=0}^{k-1}(ai+\gamma)/\prod{i=0}^{k-1}(b_i+\gamma)$等于$1$。这正是我们想要的。

总结一下。我们证明了以下内容：

事实： 设$A={a0,\dots,a{k-1}}$和$B={b0,\dots,b{k-1}}$是域元素的集合。设$\gamma$是一个随机域元素。设$\omega$是一个本原$k$次单位根，且$H={1,\omega,\omega^2,\dots,\omega^{k-1}}$。设$f$和$g$分别是在$H$处插值${a0+\gamma,\dots,a{k-1}+\gamma}$和${b0+\gamma,\dots,b{k-1}+\gamma}$值的多项式。如果存在一个多项式$Z$使得

$Z(\omega_0)=1$

$Z(X)f(X)=g(X)Z(\omega X)$

对于所有$h\in H$，那么以压倒性的概率，集合$A$和$B$相等。

元组集合

在前一节中，我们看到了如何使用多项式方程来检查两个域元素的集合是否相等。为了在我们的上下文中使用它，我们需要将其扩展到域元素元组的组。这非常简单。

让我们从简单的情况开始。设$A={(a_0,a_1),(a_2,a_3)}$和$B={(b_0,b_1),(b_2,b_3)}$是两组域元素对。也就是说，对于所有$i$，$a_i,b_i\in F$。诀窍与前一节非常相似。

$A'={a_0+a_1Y+X,a_2+a_3Y+X}$

$B'={b_0+b_1Y+X,b_2+b_3Y+X}$

就像之前一样，通过观察系数，我们可以看到集合$A$和$B$相等当且仅当$A'$和$B'$相等。

请注意，这些是多项式的集合：我们摆脱了元组！现在，情况与前一节非常相似。我们有$A'$和$B'$相等当且仅当它们元素的乘积重合。这也是真的，因为两个变量中的多项式是一个唯一的因子分解域。因此，和之前一样，我们可以使用Schwartz-Zippel引理。准确地说，如果对于随机的$\beta,\gamma$，元素

$(a_0+\beta a_1+\gamma)(a_2+\beta a_3+\gamma)$,

和

$(b_0+\beta b_1+\gamma)(b_2+\beta b_3+\gamma)$

重合，那么$A$和$B$以压倒性的概率相等。

以下是包含超过两对域元素的集合的语句。

事实： 设$A={\bar{a}0,\dots,\bar{a}{k-1}}$和$B={\bar{b}0,\dots,\bar{b}{k-1}}$是域元素对的集合。因此$\bar{a}i=(a{i,0},a_{i,1})$，$\bar{b}_i$也一样。设$\beta,\gamma$是随机域元素。设$\omega$是一个$k$次单位根，且$H={1,\omega,\omega^2,\dots,\omega^{k-1}}$。设$f$和$g$分别是在$H$处插值以下值的多项式：

${a{i,0}+a{i,1}\beta+\gamma,\dots,a{k-1,0}+a{k-1,1}\beta+\gamma}$,

和

${b{i,0}+b{i,1}\beta+\gamma,\dots,b{k-1,0}+b{k-1,1}\beta+\gamma}$,

如果存在一个多项式$Z$使得

$Z(\omega_0)=1$

$Z(X)f(X)=g(X)Z(\omega X)$

对于所有$h\in H$，那么以压倒性的概率，集合$A$和$B$相等。

回到我们的例子

回想一下，我们想用多项式来复述条件(b)。我们已经看到条件(b)等价于$A$和$B$相等，其中

$A={((i,j),T_{i,j}):(i,j)\in I}$

和

$B={(\sigma((i,j)),T_{i,j}):(i,j)\in I}$.

我们不能直接使用前几节的事实，因为我们的集合不是域元素的集合，也不是域元素对的集合。它们是包含索引$(i,j)$（位于第一个坐标）和一个域元素$v$（位于第二个坐标）的对的集合。因此，解决方案是将它们转换为域元素对的集合，并应用前一节的结果。我们如何将形式为$((i,j),v)$的元素映射为形式为$(a_0,a_1)$且$a_0$和$a_1$是域元素的元素？第二个坐标很简单：我们可以保持$v$不变，并取$a_1=v$。索引对$(i,j)$有多种方法。这里要实现的重要事情是，不同的对被映射到不同的域元素。回想一下，$i$的范围是从$0$到$N-1$，$j$的范围是从$0$到$2$。一种方法是取一个$3N$次本原单位根$\eta$，并定义$a_0=\eta^{3i+j}$。将它们放在一起，我们将对$((i,j),v)$映射到对$(\eta^{3i+j},v)$上，这是一个域元素对。现在我们可以考虑集合

$A={(\eta^{3i+j},T_{i,j}):(i,j)\in I}$

和

$B={(\eta^{3k+l},T_{i,j}):(i,j)\in I,\sigma((i,j))=(k,l)}$.

我们有条件(b)等价于$A$和$B$相等。

将上一节的方法应用于这些集合，我们得到以下结果。

事实： 设$\eta$是$3N$次单位根，而$\beta$和$\gamma$是随机域元素。设$D={1,\eta,\eta^2,\dots,\eta^{3N-1}}$。设$f$和$g$分别是在$D$处插值以下值的多项式：

${T_{i,j}+\eta^{3i+j}\beta+\gamma:(i,j)\in I}$,

和

${T_{i,j}+\eta^{3k+l}\beta+\gamma:(i,j)\in I,\sigma((i,j))=(k,l)}$,

假设存在一个多项式$Z$使得

$Z(\eta_0)=1$

$Z(d)f(d)=g(d)Z(\eta d)$,

对于所有$h\in D$。

那么集合$A={((i,j),T{i,j}):(i,j)\in I}$和$B={(\sigma((i,j)),T{i,j}):(i,j)\in I}$以压倒性的概率相等。

最后一个定义。请注意，$\omega=\eta^3$是一个本原$N$次单位根。设$H={1,\omega,\omega^2,\dots,\omega^{N-1}}$。

定义$S_{\sigma_1}$为

${\eta^{3k+l}:(i,0)\in I,\sigma((i,0))=(k,l)}$

在$H$处的插值。

类似地，定义$S_{\sigma2}$和$S{\sigma_3}$为以下值集合在$H$处的插值

${\eta^{3k+l}:(i,1)\in I,\sigma((i,1))=(k,l)}$,

${\eta^{3k+l}:(i,2)\in I,\sigma((i,2))=(k,l)}$,

这些将在协议期间用于处理这些多项式$Z$和上述方程。

更紧凑的形式

最后一个事实等价于以下内容。这里没有新的想法，只是相同事物的一种更紧凑的形式，它允许多项式$Z$的次数最多为$N$。

事实： 设$\omega$是一个$N$次单位根。设$H={1,\omega,\omega^2,\dots,\omega^{N-1}}$。设$k_1$和$k_2$是两个域元素，使得对于所有$i,j,l$，$\omega^i\neq\omega^jk_1\neq\omega^lk_2$。设$\beta$和$\gamma$是随机域元素。设$f$和$g$分别是在$H$处插值以下值的多项式：

${(T{0,j}+\omega^i\beta+\gamma)(T{1,j}+\omega^ik1\beta+\gamma)(T{2,j}+\omega^ik_2\beta+\gamma):0\leq i<N}$,

和

${(T{0,j}+S{\sigma1}(\omega^i)\beta+\gamma)(T{0,j}+S_{\sigma2}(\omega^i)\beta+\gamma)(T{0,j}+S_{\sigma_3}(\omega^i)\beta+\gamma):0\leq i<N}$,

假设存在一个多项式$Z$使得

$Z(\omega_0)=1$

$Z(d)f(d)=g(d)Z(\omega d)$,

对于所有$h\in D$。

那么集合$A={((i,j),T{i,j}):(i,j)\in I}$和$B={(\sigma((i,j)),T{i,j}):(i,j)\in I}$以压倒性的概率相等。

常见的预处理输入

我们已经得到了我们在开头提到的八个多项式：

$q_L,q_R,q_M,q_O,qC,S{\sigma1},S{\sigma2},S{\sigma_3}$.

这些被称为常见的预处理输入。

总结

让我们总结一下目前为止我们所拥有的。我们从一个程序开始。它可以被看作是一个包含左值、右值和输出值的门序列。这被称为电路。由此，可以计算出两个矩阵$Q$和$V$来捕获门逻辑。

执行电路会留下矩阵$T$和$PI$，分别称为迹矩阵和公共输入矩阵。我们想要证明的一切都归结为验证这些矩阵是否有效。我们有以下结果。

事实： 设$T$是一个具有列$A,B,C$的$N\times3$矩阵，$PI$是一个$N\times1$矩阵。当且仅当

1. 对于所有$i$，以下等式成立$AiQ{Li}+BiQ{Ri}+A_iBiQ{Mi}+CiQ{Oi}+Q_{Ci}+PI_i=0$，
2. 对于所有$V{i,j}=V{k,l}$的$i,j,k,l$，我们有$T{i,j}=T{k,l}$，c) 对于所有$i>n$，$PI_i=0$。

它们对应于由$PI$给出的公共输入的有效执行实例。

然后，我们从矩阵$Q$和$V$构造多项式$q_L,q_R,q_M,q_O,qC,S{\sigma1},S{\sigma2},S{\sigma_3}$，$f$，$g$。它们是由在域$H={1,\omega,\omega^2,\dots,\omega^{N-1}}$（对于某个$N$次本原单位根）和一些随机值处进行插值产生的。我们还从矩阵$T$和$PI$构造多项式$a,b,c,pi$。上述事实可以用多项式方程的形式重新表示如下。

事实： 设$z_H=X^N-1$。设$T$是一个具有列$A,B,C$的$N\times3$矩阵，$PI$是一个$N\times1$矩阵。当且仅当

1. 存在一个多项式$t_1$使得以下等式成立$aq_L+bq_R+abq_M+cq_O+q_C+pi=z_Ht_1$,

2. 存在多项式$t_2,t_3$，$z$使得$zf-gz'=z_Ht_2$和$(z-1)L_1=z_Ht_3$，其中$z'(X)=z(X\omega)$

它们对应于由$PI$给出的公共输入的有效执行实例。

你可能想知道多项式$t_i$从何而来。回想一下，对于一个多项式$F$，当且仅当对于某个多项式$t$，$F=z_Ht$时，对于所有$h\in H$，我们有$F(h)=0$。

最后，如果我们引入更多的随机性，条件(a)和(b)都等价于一个单一的方程(c)。这就是：

3. 设$\alpha$是一个随机域元素。存在一个多项式$t$使得

$z_Ht=aq_L+bq_R+abq_M+cq_O+q_C+pi=\alpha(gz'-fz)=\alpha^2(z-1)L_1$

最后一步不是很明显。你可以查看论文以查看证明。无论如何，这就是你将在下面的协议描述中识别出的方程式。

随机性是一个微妙的问题，协议的一个重要部分是它来自何处，由谁选择它以及何时选择它。我们现在准备好进入协议。

协议

细节和技巧

多项式承诺方案

多项式承诺方案（PCS）是一种密码学工具，它允许一方承诺一个多项式，并在以后证明该多项式的某些属性。

这种承诺多项式隐藏了原始多项式的系数，并且可以公开共享，而不会泄露有关原始多项式的任何信息。

稍后，该方可以使用该承诺来证明多项式的特定属性，例如它满足某些约束或在特定点评估为特定值。

目前，我们只需要了解以下内容：

它由一个有限群$G$和以下算法组成：

• Commit(f)：此算法采用一个多项式$f$，并生成群$G$的一个元素。它被称为$f$的承诺，用$[f]$表示。它是同态的，因为$[f+g]=[f]+[g]$。前一个和是多项式的加法。后一个是群$G$中的加法运算。
• Open(f,$\zeta$): 它接受一个多项式$f$和一个域元素$\zeta$，并生成群$G$的一个元素$\pi$。此元素是$f(\zeta)$的打开证明。它是在$\zeta$处评估的$f$给出$f(\zeta)$的证明。
• Verify([f], $\pi$, $\zeta$, $y$): 它接受群元素$[f]$和$\pi$，以及域元素$\zeta$和$y$。以压倒性的概率，如果$f(z)=y$，则输出Accept，否则输出Reject。

通过更改PCS，你可以获得不同版本的PLONK，每种版本都有其优点和缺点（例如，更短的证明，可能具有后量子安全性，缺少可信设置等）。

盲化

正如你将在协议中看到的那样，证明者揭示了一堆多项式在随机$\zeta$处取的值。为了使协议为诚实验证者零知识，这些多项式必须是盲化的。此过程通过强制它们具有一定的次数来使这些多项式在$\zeta$处的值看起来是随机的。这是它的工作原理。

让我们以证明者构造的多项式$a$为例。这是通过在域$H$处插值得到迹矩阵$T$的第一列获得的。

该矩阵包含所有门的全部左操作数。证明者希望对其进行保密。

假设迹矩阵$T$具有$N$行，因此$H$是${1,\omega,\omega^2,\dots,\omega^{N-1}}$。证明者无法违反的不变量是，对于所有$i$，$a{blinded}(\omega^i)$必须取值$T{0,i}$。这就是插值多项式$a$满足的条件，并且是具有这种性质的次数最高为$N-1$的唯一这样的多项式。但是对于更高的次数，存在许多这样的多项式。

盲化过程采用$a$和所需的次数$M\geq N$，并生成一个次数恰好为$M$的新多项式$a{blinded}$。对于所有$i$，此新多项式满足$a{blinded}(\omega^i)=a(\omega^i)$。但是在$H$之外，$a_{blinded}$与$a$不同。

这似乎很难，但是非常简单。设$z_H$为多项式$z_H=X^N-1$。如果$M=N+k$，其中$k\geq0$，则采样随机值$b_0,\dots,b_k$并定义

$a_{blinded}:=(b_0+b_1X+\cdots+b_kX^k)z_H+a$

这样做是因为对于所有$i$，$z_H(\omega^i)=0$。因此，添加的项在$H$处消失，并且使$a$在$H$处的值保持不变。

线性化技巧

这是PLONK中的一种优化，可以减少验证者的检查次数。

PLONK中的主要检查之一归结为检查$p(\zeta)=z_H(\zeta)t(\zeta)$，其中$p$是诸如$p=aq_L+bq_R+abq_M+\cdots$的多项式等等。特别是，验证者需要从某个地方获得值$p(\zeta)$。

为简单起见，在本节中，假设$p$恰好是$aq_L+bq_R$。证明者在此处秘密地仅持有$a,b$。验证者也知道多项式$q_L$和$q_R$。验证者将已经拥有承诺$[a],[b],[q_L]$和$[q_R]$。因此，证明者可以仅发送$a(\zeta)$，$b(\zeta)$及其打开证明，并让验证者自己计算$q_L(\zeta)$和$q_R(\zeta)$。然后，通过所有这些值，验证者可以计算$p(\zeta)=a(\zeta)q_L(\zeta)+b(\zeta)q_R(\zeta)$。并且还可以使用他的承诺来验证$a(\zeta)$和$b(\zeta)$的打开证明。

这样做的问题是计算$q_L(\zeta)$和$q_R(\zeta)$非常昂贵。相反，证明者可以发送$q_L(\zeta),q_R(\zeta)$以及打开证明来节省验证者的计算量。由于验证者事先已经拥有承诺$[q_L]$和$[q_R]$，因此他可以检查证明者是否作弊，并可以轻易地确信所声明的值是$q_L(\zeta)$和$q_R(\zeta)$。这好得多。它涉及检查四个打开证明并从从证明者那里收到的值计算$p(\zeta)$。但是可以如下所述进一步改进。

和以前一样，证明者发送$a(\zeta),b(\zeta)$以及打开证明。她构造多项式$f=a(\zeta)q_L+b(\zeta)q_R$。她发送值$f(\zeta)$以及$f(\zeta)$的打开证明。请注意，$f(\zeta)$的值恰好是$p(\zeta)$。验证者可以通过计算$a(\zeta)[q_L]+b(\zeta)[q_R]$来自己计算$[f]$。验证者拥有检查所有三个打开所需的一切，并确信所声明的值$f(\zeta)$为真，并且此值为$p(\zeta)$。因此，这意味着验证者不再需要做更多的工作。整个过程简化为三个打开。

这称为线性化技巧。多项式$f$称为$p$的线性化。

设置

有一个一次性设置阶段，用于计算对于任何特定电路的执行和证明都通用的一些值。准确地说，计算并发布以下承诺。

$[q_L],[q_R],[q_M],[q_O],[qC],[S{\sigma1}],[S{\sigma2}],[S{\sigma_3}]$

证明算法

接下来，我们描述一个大小为$N$（包括公共输入）的程序的证明算法。设$\omega$是一个本原$N$次单位根。设$H={1,\omega,\omega^2,\dots,\omega^{N-1}}$。定义$Z_H:=X^N-1$。

假设已经给出了公共预处理输入的八个多项式。

证明者计算迹矩阵$T$，如第一节所述。这意味着第一行对应于公共输入。它应该是一个$N\times3$矩阵。

第一轮

将以下内容添加到记录中：

$[S_{\sigma1}],[S{\sigma2}],[S{\sigma_3}],[q_L],[q_R],[q_M],[q_O],[q_C]$

计算多项式$a',b',c'$作为$T$的列在域$H$处的插值多项式。

采样随机数$b_1,b_2,b_3,b_4,b_5,b_6$

设

$a:=(b_1X+b_2)Z_H+a'$

$b:=(b_3X+b_4)Z_H+b'$

$c:=(b_5X+b_6)Z_H+c'$

计算$[a],[b],[c]$并将它们添加到记录中。

第二轮

从记录中采样$\beta,\gamma$。

设$z_0=1$，并递归定义$0\leq k<N$：

$z_{k+1}=z_k\frac{(a_k+\beta\omega^k+\gamma)(b_k+\beta\omega^kk_1+\gamma)(c_k+\beta\omega^kk_2+\gamma)}{(ak+\beta S{\sigma_1}(\omega^k)+\gamma)(bk+\beta S{\sigma_2}(\omega^k)+\gamma)(ck+\beta S{\sigma_3}(\omega^k)+\gamma)}$

计算多项式$z'$，作为值$(z0,\dots,z{N-1})$在域$H$处的插值多项式。

采样随机值$b_7,b_8,b_9$，并设$z=(b_7X^2+b_8X+b_9)Z_H+z'$。

计算$[z]$并将它添加到记录中。

第三轮

从记录中采样$\alpha$。

设$pi$为公共输入矩阵$PI$在域$H$处的插值。

设

$p_1=aq_L+bq_R+abq_M+cq_O+q_C+pi$ $p_2=(a+\beta X+\gamma)(b+\beta k_1X+\gamma)(c+\beta k2X+\gamma)z-(a+\beta S{\sigma1}+\gamma)(b+\beta S{\sigma2}+\gamma)(c+\beta S{\sigma_3}+\gamma)z(\omega X)$ $p_3=(z-1)L_1$

并定义$p=p_1+\alpha p_2+\alpha^2p_3$。计算$t$使得$p=tZH$。写成$t=t'{lo}+X^{N+2}t'{mid}+X^{2(N+2)}t'{hi}$，其中$t'{lo},t'{mid}$和$t'_{hi}$是次数最多为$N+1$的多项式。

采样随机数$b{10},b{11}$并定义

$t{lo}=t'{lo}+b{10}X^{N+2}$ $t{mid}=t'{mid}-b{10}+b{11}X^{N+2}$ $t{hi}=t'{hi}-b{11}$ 计算$[\texttt{tlo}]$，$[\texttt{tmid}]$，$[\texttt{thi}]$并将它们添加到记录中。

第四轮

从记录中采样$\zeta$。

计算$\bar{a}=a(\zeta)$，$\bar{b}=b(\zeta)$，$\bar{c}=c(\zeta)$，$\bar{s}_{\sigma1}=S{\sigma1}(\zeta)$，$\bar{s}{\sigma2}=S{\sigma2}(\zeta)$，$\bar{z}\omega=z(\zeta\omega)$并将它们添加到记录中。

第五轮

从记录中采样$\upsilon$。

设

$\hat{p}_{nc1}=\bar{a}q_L+\bar{b}q_R+\bar{a}\bar{b}q_M+\bar{c}q_O+qC$ $\hat{p}{nc2}=(\bar{a}+\beta\zeta+\gamma)(\bar{b}+\beta k_1\zeta+\gamma)(\bar{c}+\beta k2\zeta+\gamma)z-(\bar{a}+\beta\bar{s}{\sigma1}+\gamma)(\bar{b}+\beta\bar{s}{\sigma2}+\gamma)\beta\bar{z}\omega S_{\sigma3}$ $\hat{p}{nc3}=L_1(\zeta)z$

定义

$p{nc}=\hat{p}{nc1}+\alpha\hat{p}{nc2}+\alpha^2\hat{p}{nc3}$ $t{partial}=t{lo}+\zeta^{N+2}t{mid}+\zeta^{2(N+2)}t{hi}$

下标$nc$表示“非常数”，因为它是由非常数因子组成的$p$的线性化部分。下标“partial”表示它是$t$在$\zeta$处的偏评估。Partial表示只有$X$的一些幂被$\zeta$的幂代替。因此特别是$t_{partial}(\zeta)=t(\zeta)$。

设$\pi{batch}$为多项式$f{batch}$在$\zeta$处的打开证明，定义为

$t{partial}+\upsilon p{nc}+\upsilon^2 a+\upsilon^3 b+\upsilon^4 c+\upsilon^5 S_{\sigma1}+\upsilon^6 S{\sigma_2}$

设$\pi_{single}$为多项式$z$在$\zeta\omega$处的打开证明。

计算$\bar{p}{nc}:=p{nc}(\zeta)$和$\bar{t}=t(\zeta)$。

证明

证明是：

$[a]$，$[b]$，$[c]$，$[z]$，$[\texttt{tlo}]$，$[\texttt{tmid}]$，$[\texttt{thi}]$，$\bar{a}$，$\bar{b}$，$\bar{c}$，$\bar{s}_{\sigma1}$，$\bar{s}{\sigma2}$，$\bar{z}\omega$，$\pi{batch}$，$\pi{single}$，$\bar{p}_{nc}$，$\bar{t}$

验证算法

记录初始化

第一步是按照证明者的方式初始化记录，并将以下元素添加到其中。

$[S_{\sigma1}]$，$[S{\sigma2}]$，$[S{\sigma_3}]$，$[q_L]$，$[q_R]$，$[q_M]$，$[q_O]$，$[q_C]$

提取值和承诺

挑战

首先，验证者需要计算所有挑战。为此，他执行以下步骤：

• 将$[a]$，$[b]$，$[c]$添加到记录中。
• 采样两个挑战$\beta, \gamma$。
• 将$[z]$添加到记录中。
• 采样一个挑战$\alpha$。
• 将$[\texttt{tlo}]$，$[\texttt{tmid}]$，$[\texttt{thi}]$添加到记录中。
• 采样一个挑战$\zeta$。
• 奖$\bar{a}$，$\bar{b}$，$\bar{c}$，$\bar{s}_{\sigma1}$，$\bar{s}{\sigma2}$，$\bar{z}\omega$添加到记录中。
• 采样一个挑战$\upsilon$。

计算$pi(\zeta)$

此外，他需要计算所有这些数据的一些值。首先，他使用公共输入和输出计算$PI$矩阵。他需要计算$pi(\zeta)$，其中$pi$是$PI$在域$H$处的插值。但是他不需要计算$pi$。他可以计算$pi(\zeta)$作为

$\sum_{i=0}^n L_i(\zeta)PI_i$,

其中$n$是公共输入的数量，$L_i$是域$H$处的拉格朗日基。

计算声明的值 $p(\zeta)$ 和 $t(\zeta)$

他计算 $\bar{p}c:=pi(\zeta)+\alpha\bar{z}\omega(\bar{c}+\gamma)(\bar{a}+\beta\bar{s}_{\sigma1}+\gamma)(\bar{b}+\beta\bar{s}{\sigma_2}+\gamma)-\alpha^2L_1(\zeta)$

这是 $p$ 线性化的常量部分。因此，将其添加到证明者声明的 $\bar{p}_{nc}$ 中，他得到

$p(\zeta)=\bar{p}c+\bar{p}{nc}$

关于 $t(\zeta)$，这实际上已经是 /bart/bart。

计算 $[t{partial}]$ 和 $[p{nc}]$

他计算证明中承诺的这些值如下：

$[t_{partial}]=[\texttt{tlo}]+\zeta^{N+2}[\texttt{tmid}]+\zeta^{2(N+2)}[\texttt{thi}]$

对于 $[p_{nc}]$，首先计算

$[\hat{p}_{nc1}]=\bar{a}[q_L]+\bar{b}[q_R]+(\bar{a}\bar{b})[q_M]+\bar{c}[q_O]+[qC]$ $[\hat{p}{nc2}]=(\bar{a}+\beta\zeta+\gamma)(\bar{b}+\beta k_1\zeta+\gamma)(\bar{c}+\beta k2\zeta+\gamma)[z]-(\bar{a}+\beta\bar{s}{\sigma1}+\gamma)(\bar{b}+\beta\bar{s}{\sigma2}+\gamma)\beta\bar{z}\omega[S_{\sigma3}]$ $[\hat{p}{nc3}]=L_1(\zeta)[z]$

然后 $[p{nc}]=[\hat{p}{nc1}]+[\hat{p}{nc2}]+[\hat{p}{nc3}]$.

计算声明的值 $f{batch}(\zeta)$ 和 $[f{batch}]$

计算 $f_{batch}(\zeta)$ 为

$f{batch}(\zeta)=\bar{t}+\upsilon\bar{p}{nc}+\upsilon^2\bar{a}+\upsilon^3\bar{b}+\upsilon^4\bar{c}+\upsilon^5\bar{s}_{\sigma1}+\upsilon^6\bar{s}{\sigma_2}$

同样，多项式 $f_{batch}$ 的承诺是

$[f{batch}]=[t{partial}]+\upsilon[p{nc}]+\upsilon^2[a]+\upsilon^3[b]+\upsilon^4[c]+\upsilon^5[S{\sigma1}]+\upsilon^6[S{\sigma_2}]$

证明检查

现在验证者拥有进行检查的所有必要值。

• 检查 $p(\zeta)$ 是否等于 $(\zeta^N-1)t(\zeta)$。
• 验证 $f{batch}$ 在 $\zeta$ 处的打开。也就是说，检查 Verify($[f{batch}]$, $\pi{batch}$, $\zeta$, $f{batch}(\zeta)$) 的输出是否为 Accept。
• 验证 $z$ 在 $\zeta\omega$ 处的打开。也就是说，使用承诺 $[z]$ 和值 $\bar{z}\omega$ 检查证明 $\pi{single}$ 的有效性。

也就是说，检查 Verify($[z]$, $\pi{single}$, $\zeta\omega$, $\bar{z}\omega$) 的输出是否为 Accept。

如果所有检查都通过，则输出 Accept。否则，输出 Reject。

总结

在这篇文章中，我们介绍了 PLONK 的工作原理和协议基础，PLONK 是一种常用的 ZK-SNARK。我们了解了如何将计算转换为计算轨迹元素上的一组多项式约束。然后，我们了解了如何强制执行这些约束以及如何使用置换参数来证明正确的线路连接。在接下来的文章中，我们将介绍对基本协议的优化，包括自定义门、查找表、折叠方案和其他承诺方案。

• 原文链接： blog.lambdaclass.com/all...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～