PLONK 算术化

PLONK v.s. Halo

相似之处： 证明系统，使用多项式承诺方案，相同的约束系统（约束多项式，BG12 排列，查找表，自定义门）

不同之处： PLONK 需要可信设置（trusted-setup），PLONK 使用配对（pairings），Halo 具有证明递归（椭圆曲线群的 2 周期），PLONK 使用类似 Kate 的 PCS，Halo 使用类似 Hyrax 的 PCS

时间线：

[标准] PLONK (2019 年 8 月) - 通过使用单个可更新的可信设置的多项式承诺的证明系统。使用配对，非 R1CS 约束系统，BG12 排列证明和类似 Kate 的多项式承诺。

Halo (2019 年 9 月) - 通过椭圆曲线周期进行证明递归，无需配对，无需可信设置，类似 Hyrax 的 PCS。

TurboPLONK (2019 年末/2020 年初) - 具有自定义门/约束的 PLONK。

plookup (2020 年 11 月) - 使用查找表扩展 PLONK（用键值映射替换昂贵的计算，以查找输入上计算的输出，当前查找表侧重于替换按位运算，例如按位与和异或）。

UltraPLONK (2020 年末) - 具有自定义门和查找表的 PLONK，即结合了 TurboPLONK 和 plookup（使许多对 SNARK 不友好的算法更加友好）。附注：使用查找表和自定义门可以有效地在小于 PLONK 域的域中进行模块化算术，这可以允许无需椭圆曲线周期即可进行递归证明（即，多个基域和标量域）。附注 #2：UltraPLONK 中的 Pedersen 哈希的效率与 Poseidon 大致相同。

Halo2 (2020 年末) - 结合了 UltraPLONK，一种不需要可信设置的 PCS，以及用于递归的椭圆曲线周期。

问题： PLONK 中的验证时间是恒定的，但在 Halo/Halo2 中不是，因为 Halo 的证明大小随计算大小而变化？Zcash 将依靠批量交易验证来实现接近简洁性的效果。

标准 PLONK 算术化

算术化 - 将通用计算分解为一系列步骤。

示例：

$a*b+23==100$:

算术化将通用计算转换为多项式系统（一组相互依赖的多项式），其中每个多项式都约束为一个值。通用计算的多项式集合是其约束系统。每个多项式都具有相同的形式。

标准 PLONK 使用约束多项式：

$s_l x_l + s_r x_r + s_m x_l x_r = s_o x_o + c$

• $s_l, s_r, s_o, s_m \in {0,1}$ 是布尔选择器
• $x_l, x_r, x_o \in F$ 是算术中使用的值
• $c \in F$ 是一个可选常量，用于将约束系统值分配给常量（公共输入）

它可以编码加法、乘法和常数赋值。

		约束
加法	$l+r=o$	$1x_l + 1x_r + 0x_l x_r = 1x_o + 0$
乘法	$l*r=o$	$0x_l + 0x_r + 1x_l x_r = 1x_o + 0$
指定常量 <br> (公共输入)	$l=5$<br>$r=5$<br>$l+r=5$<br>$l*r=5$	$1x_l + 0x_0 + 0x_l x_r = 0x_o + 5$<br>$0x_l + 1x_r + 0x_l x_r = 0x_o + 5$<br>$1x_l + 1x_r + 0x_l x_r = 0x_0 + 5$<br>$0x_l + 0x_r + 1x_l x_r = 0x_o + 5$
指数	$(lr)r=o$	$(0)0x_l + 0x_r + 1x_l x_r = 1x_o(1)0x_l + 0x_r + 1x_o(0)x_r = 1x_o$

注意： 约束可以引用来自另一个约束的值，例如指数。这是通过排列参数（permutation argument）强制执行的，而不是使用约束。

TODO：

$s_l, s_r, s_o, s_m, c$ 值定义了计算。

$x_l, x_r, x_o$ 值由知道计算如何进行的人填写（每个门的输入和输出）。

我们可以将计算的约束系统视为矩阵：

$\boldsymbol{x_l}$	$\boldsymbol{x_r}$	$\boldsymbol{x_o}$	$\boldsymbol{s_l}$	$\boldsymbol{s_r}$	$\boldsymbol{s_m}$	$\boldsymbol{s_o}$	$\boldsymbol{c}$
$x_l(1)$	$x_r(1)$	$x_o(1)$	$s_l(1)$	$x_r(1)$	$s_m(1)$	$s_o(1)$	$c(1)$
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
$x_l(n)$	$x_r(n)$	$x_o(n)$	$s_l(n)$	$x_r(n)$	$s_m(n)$	$s_o(n)$	$c(n)$

其中证明者用值（witness) 填充列

$\boldsymbol{x_l}$，

$\boldsymbol{x_r}$，和

$\boldsymbol{x_o}$，以满足每个约束。

示例：

$a*b+23==100$ (续)

这些

s 的和相等约束定义了计算，

c 的给出了计算实例；证明者填写

x 的值以表明他们知道计算的进行方式。

	$\boldsymbol{x_l}$	$\boldsymbol{x_r}$	$\boldsymbol{x_o}$	$\boldsymbol{s_l}$	$\boldsymbol{s_r}$	$\boldsymbol{s_m}$	$\boldsymbol{s_o}$	$\boldsymbol{c}$
$a*b=c$	$x_l(1)$	$x_r(1)$	$x_o(1)$	0	0	1	1	0
$d=23$	$x_l(2)$	$x_r(2)$	$x_o(2)$	1	0	0	0	23
$c+d=e$	$x_l(3)$	$x_r(3)$	$x_o(3)$	1	1	0	1	0
$f=100$	$x_l(4)$	$x_r(4)$	$x_o(4)$	1	0	0	0	100

相等约束：$x_o(1) = x_l(3)$ $x_l(1) = x_r(3)$ $x_o(3) = x_o(4)$

压缩约束检查

我们希望用某种形式的单个检查来代替

$n$ 个约束检查（即，

$\forall i \in [n]$，第

$i$ 个约束是否满足？）。我们通过将约束系统转换为一个多项式表达式来实现这一点，该表达式当且仅当约束系统得到满足时才为真。

拉格朗日插值

拉格朗日插值将函数的求值形式

${(x_1, y_1), \dots, (x_n, y_n)}$ 转换为通过每个点的多项式。

拉格朗日插值用于将每一列表示为一个多项式：

$x_l(X), x_r(X), x_o(X), s_l(X), s_r(X), s_m(X), s_o(X), c(X)$，其中每一列的多项式在第

$i$ 个输入处输出该列在第

$i$ 行中的值。

我们将每个矩阵行

$i \in [n]$ 与一个唯一值

$\omega_i$ 相关联，其中与所有行关联的值的集合为

$H = {\omega_1, \dots, \omega_n}$。将此输入集合与列

$zip(H, column) = {(\omega_1, a_1), \dots, (\omega_n, a_n)}$ 压缩在一起，可以得到一个多项式的求值形式，该多项式在行

$i$ 的输入

$\omega_i$ 上输出第

$i$ 列的值。对每一列的求值形式执行拉格朗日插值，会生成一个多项式，该多项式将每一行的输入

$\omega_i$ 映射到该行中列的值

$a_i$。例如，要将列

$\boldsymbol{x_l}$ 插值为

$x_l(X)$，我们使用求值形式

${(\omega_1, x_l(1)), \dots, (\omega_n, x_l(1))}$。

H	$\boldsymbol{x_l}$	$\boldsymbol{x_r}$	$\boldsymbol{x_o}$	$\boldsymbol{s_l}$	$\boldsymbol{s_r}$	$\boldsymbol{s_m}$	$\boldsymbol{s_o}$	$\boldsymbol{c}$
$\omega_1$	$x_l(1)$	$x_r(1)$	$x_o(1)$	$s_l(1)$	$x_r(1)$	$s_m(1)$	$s_o(1)$	$c(1)$
⋮
$\omega_n$	$x_l(n)$	$x_r(n)$	$x_o(n)$	$s_l(n)$	$x_r(n)$	$s_m(n)$	$s_o(n)$	$c(n)$

将约束检查重写为多项式表达式

给定一组插值多项式，我们使用约束方程来编写一个对每个输入

$\omega_i \in H$ 都成立的表达式：

$s_l(\omega_i) x_l(\omega_i) + s_l(\omega_i) x_l(\omega_i) + s_m(\omega_i) x_l(\omega_i) x_r(\omega_i) = s_o(\omega_i) x_o(\omega_i) + c(\omega_i)$ 将右侧移到左侧，我们将以上内容重写为：

$s_l(\omega_i) x_l(\omega_i) + s_l(\omega_i) x_l(\omega_i) + s_m(\omega_i) x_l(\omega_i) x_r(\omega_i) - s_o(\omega_i) x_o(\omega_i) - c(\omega_i) = 0$。我们可以将以上等式的左侧写成多项式：

$s_l(X) x_l(X) + s_l(X) x_l(X) + s_m(X) x_l(X) x_r(X) - s_o(X) x_o(X) - c(X)$，它在每个输入

$\omega_i$ 处都输出

$0$，即具有根

$\omega_1, \dots, \omega_n$。我们知道多项式的某些根，因此我们知道其线性分解的一部分包含 1 次项

$(X - \omega_1) \dots (X - \omega_n)$：

$s_l(X) x_l(X) + s_l(X) x_l(X) + s_m(X) x_l(X) x_r(X) - s_o(X) x_o(X) - c(X) = (X - \omega_1) \dots (X - \omega_n) h(X)$。我们称

$(X - \omega_1) \dots (X - \omega_n)$ 为消失多项式

$V(X)$，它在每个输入

$\omega_i$ 上都输出

$0$：

$V(X) = \prod_{i \in [n]} (X - \omega_i)$ 在

$n$ 阶循环乘法群中，可以简化为：

$V(X) = X^n - 1$ $V(\omega_i) = (\omega_i)^n - 1 = \omega_i^n \mod n - 1 = \omega^0 - 1 = 1 - 1 = 0$ 以及

$h(X)$ 它的余因子多项式。因此，我们可以将约束系统多项式写为相等形式：

$s_l(X) x_l(X) + s_l(X) x_l(X) + s_m(X) x_l(X) x_r(X) - s_o(X) x_o(X) - c(X) = V(X) h(X)$。

如果约束系统多项式表示

$s_l(X) x_l(X) + \dots - c(X)$ 可被

$V(X)$ 整除而没有余数，则该约束系统被满足。

$V(X) | s_l(X) x_l(X) + s_l(X) x_l(X) + s_m(X) x_l(X) x_r(X) - s_o(X) x_o(X) - c(X)$ 因此，我们可以使用单个多项式除法检查来执行

$n$ 个约束检查。

排列表示法

一个排列

$\sigma$，用于混排

$n$ 个元素的数组

$\sigma((a_1, \dots, a_n)) = (b_1, \dots, b_n)$ 可以写成：

$\sigma = (\sigma_1, \dots, \sigma_n)$ 其中

$\sigma_1 = 2$ 表示

$a_2 \mapsto b_1$。

相等约束

多项式除法检查确保证明者知道每个门的满足输入和输出，但不确保连线正确，例如，一个门的输出是另一个门的输入。

示例： 我知道

$(a, b)$ 使得

$a+b=a*b$。

在两个门上应用除法检查证明我知道每个门单独的满足输入和输出，即我知道

$(a, b, c, d, e, f)$ 使得

$a+b=e$ 和

$c*d=f$：

添加复制约束证明左侧输入相等，右侧输入相等且输出相等，即我知道

$(a, b)$ 使得

$a+b=a*b$：

为了证明导线的相等性，我们在约束系统值

$\boldsymbol{x_l}, \boldsymbol{x_r}, \boldsymbol{x_o}$ 上应用排列检查。我们将三个列中的每一个合并成一个长度为

$3n$ 的单个数组：

$\boldsymbol{u} = \boldsymbol{x_l} | \boldsymbol{x_r} | \boldsymbol{x_o} = (x_l(1), \dots, x_l(n), x_r(1), \dots, x_r(n), x_o(1), \dots, x_o(n))$。并创建一个排列

$\sigma \in S_{3n}$，其作用于

$\boldsymbol{u}$ 以产生一个数组

$\boldsymbol{v} = \sigma(\boldsymbol{u}) = (u_{\sigma1}, \dots, u{\sigma_{3n}})$。我们选择

$\sigma$ 使得复制值的每个子集形成一个循环，即，复制的值仅与其副本进行排列。

附注： 排列循环

给定一个排列

$\sigma \in S_6$，其中：

$\sigma = [1 2 3 4 5 6 \ 2 1 4 6 5 3]$ 我们可以用循环表示法编写

$\sigma$：

$\sigma = (1 2)(3 4 6)(5)$ 或简写为

$(1 2)(3 4 6)$。一个

$m$-循环是一个

$m$ 个元素的子集，这些元素在

$\sigma$ 的

$m$ 次应用后重复，例如，

2-循环

$(1 2)$ 映射

$1 \rightarrow 2$，然后

$2 \rightarrow 1$。

示例： 约束系统值的排列

给定一个

$n=3$ 个约束的约束系统：

$\boldsymbol{x_l} = (x_l(1), x_l(2), x_l(3))$ $\boldsymbol{x_r} = (x_r(1), x_r(2), x_r(3))$ $\boldsymbol{x_l} = (x_o(1), x_o(2), x_o(3))$ $\boldsymbol{u} = \boldsymbol{x_l} | \boldsymbol{x_r} | \boldsymbol{x_l} = (x_l(1), x_l(2), x_l(3), x_r(1), x_r(2), x_r(3), x_o(1), x_o(2), x_o(3))$ $1 2 3 4 5 6 7 8 9$ 和连线：

$x_l(1) = x_l(2)$ $x_o(1) = x_r(2) = x_l(3)$ 我们创建一个排列

$\sigma$，它作用于包含

$| \boldsymbol{u} | = 3n$ 个元素的集合，使得每组复制的约束系统值形成一个循环：

$\sigma = (x_l(1) x_l(2))(x_l(3) x_r(2) x_o(1))$ 使用

$\boldsymbol{u}$ 中的索引以一种不太繁琐的方式写为：

$\sigma = (1 2)(3 5 7)$。排列后的向量

$\boldsymbol{v} = \sigma(\boldsymbol{u}) = (u_{\sigma1}, \dots, u{\sigma_{3n}})$ 为：

$\boldsymbol{v} = (x_l(2), x_l(1), x_o(1), x_r(1), x_l(3), x_r(3), x_r(2), x_o(2), x_o(3))$ $2 1 7 4 3 6 5 8 9$。

未排列的数组

$\boldsymbol{u}$ 被编码为多项式：

$u(X) = \prod_{i \in [3n]} (iX + u_i)$ 排列后的数组

$\boldsymbol{v}$ 被编码为多项式：

$v(X) = \prod_{i \in [3n]} (\sigma_i X + v_i)$。其中

$\sigma_i$ 是

$\boldsymbol{u}$ 中排列成

$v_i$ 的索引，即

$vi = u{\sigma_i}$ 和

$\boldsymbol{v} = \sigma(\boldsymbol{u}) = (u_{\sigma1}, \dots, u{\sigma_{3n}})$。此外，令

$u_i(X)$ 和

$v_i(X)$ 分别表示

$u(X)$ 和

$v(X)$ 的第

$i$ 项：

$u_i(X) = (iX + u_i)$ $v_i(X) = (\sigma_i X + v_i)$。

请注意，对于

$v(X)$ 中的每一项

$v_i(X)$，在

$u(X)$ 中都有一个完全相同的项

$u_{\sigma_i}(X)$，因此，尽管它们的第

$i$ 项可能不同，多项式

$u(X)$ 和

$v(X)$ 是相同的：

如果 $i \neq \sigma_i$，则 $u_i(X) \neq vi(X)$ $u{\sigma_i}(X) = vi(X) \Rightarrow \prod{i \in [3n]} ui(X) = \prod{i \in [3n]} v_i(X)$ 因此，以下关系成立：

$\frac{u(X)}{v(X)} = \frac{\prod_{i \in [3n]} (iX + ui)}{\prod{i \in [3n]} (\sigma_i X + vi)} = \frac{\prod{i \in [3n]} ui(X)}{\prod{i \in [3n]} v_i(X)} = 1$。

可以使用 Schwartz-Zippel 检验表示数组的多项式与表示数组排列的多项式之间的这种关系：给定一个随机输入

$\beta$，$\frac{u(\beta)}{v(\beta)} = 1$ 的概率可以忽略不计。

附注： PLONK 使用稍微不同的关系。

PLONK 实际上定义了

$u(X) = \prod_{i \in [3n]} (iX + u_i + \gamma)$ 和

$v(X) = \prod_{i \in [3n]} (\sigma_i X + v_i + \gamma)$ 其中验证者选择一个随机的

$\gamma$ 并将其发送给证明者（它们通过右移 Schwartz-Zippel 引理等效），因此实际上，以上表达式为：

$\frac{u(X)}{v(X)} = \frac{\prod_{i \in [3n]} (iX + ui + \gamma)}{\prod{i \in [3n]} (\sigma_i X + v_i + \gamma)} = 1$。

附注： 运行乘积的轨迹。

运行乘积的轨迹是一个数组

$\boldsymbol{s}$，其第一个元素为

$1$，并包含每次乘法运算后的乘积值，例如

$\prod_{i \in [3]} x_i$ $\boldsymbol{s} = (1, 1x_1, 1xx_2, 1xx_2x_3)$

验证者选择一个随机的

$\beta$，供证明者评估

$\frac{u(\beta)}{v(\beta)}$，并且证明者构造一个大乘积数组

$\boldsymbol{s} = (s1, \dots, s{3n})$，表示

$\frac{u(\beta)}{v(\beta)}$，即，

$\boldsymbol{s}$ 是乘积

$\frac{u(\beta)}{v(\beta)}$ 的轨迹：

$s_1 = 1$ $s_2 = s_1 \frac{u_1(\beta)}{v_1(\beta)} = (1) \frac{u_1(\beta)}{v_1(\beta)}$ $s_3 = s_2 \frac{u_2(\beta)}{v_2(\beta)} = (1 \frac{u_1(\beta)}{v_1(\beta)}) \frac{u_2(\beta)}{v2(\beta)}$ $\vdots$ $s{3n} = s{3n-1} \frac{u{3n-1}(\beta)}{v_{3n-1}(\beta)} = (1 \frac{u_1(\beta)}{v1(\beta)} \dots \frac{u{3n-2}(\beta)}{v{3n-2}(\beta)}) \frac{u{3n-1}(\beta)}{v_{3n-1}(\beta)}$

$\boldsymbol{s}$ 是递归的，因为它的第

$i$ 个元素等于前一个元素乘以

$\frac{u{i-1}(\beta)}{v{i-1}(\beta)}$：

$si = s{i-1} \frac{u{i-1}(\beta)}{v{i-1}(\beta)}$ 其中：$i \in [2, 3n]$。

请注意，

$\frac{u(\beta)}{v(\beta)}$ 可以从

$\boldsymbol{s}$ 计算得出，方法是将其最后一个元素乘以

$\frac{u(\beta)}{v(\beta)}$ 中的最后一项乘积：

$\frac{u(\beta)}{v(\beta)} = \prod_{i \in [3n]} \frac{u_i(\beta)}{vi(\beta)} = s{3n} \frac{u{3n}(\beta)}{v{3n}(\beta)} = s_{3n+1}$

证明者使用拉格朗日插值在公开已知的一组

$3n$ 个输入

$H = \langle \omega \rangle = {\omega1, \dots, \omega{3n}} \subset F$ 和图像

$\boldsymbol{s}$ 上创建一个多项式

$s(X)$，使得：

$\forall i \in [3n]: s(\omega_i) = s_i$。注意，对于一对相邻输入

$\omega_i$ 和

$\omega_{i+1}$，以下关系成立：

$s_{i+1} = s_i \frac{u_i(\beta)}{vi(\beta)} \Rightarrow s(\omega{i+1}) = s(\omega_i) \frac{u_i(\beta)}{v_i(\beta)}$。

给定

$s(X)$，验证者想要检查

$\boldsymbol{v}$ 是否是根据

$\sigma$ 的

$\boldsymbol{u}$ 的排列。验证者检查排列标识在

$\boldsymbol{s}$ 中的最后一个元素上是否成立：

$\frac{u(\beta)}{v(\beta)} =? 1 \Rightarrow s(\omega{3n}) \frac{u{3n}(\beta)}{v_{3n}(\beta)} =? 1$ 以及

$\boldsymbol{s}$ 是否是正确构造的运行乘积

$si = s{i-1} \frac{u{i-1}(\beta)}{v{i-1}(\beta)}$：

$s(\omega{3n}) =? s(\omega{3n-1}) \frac{u{3n-1}(\beta)}{v{3n-1}(\beta)}$ $\vdots$ $s(\omega_2) =? s(\omega_1) \frac{u_1(\beta)}{v_1(\beta)}$ $s(\omega_1) =? 1$。

如果在随机挑战

$\beta$ 处 $\frac{u(\beta)}{v(\beta)} = 1$，则

$u(X) = v(X)$，这意味着

$\boldsymbol{v} = \sigma(\boldsymbol{u})$。

通过随机化集合差异证明子数组（未完成）

注意： “有序多重集” == “数组”

注意： “子数组” == “保留顺序的数组子集”

PLONK 定义了一个有序多重集

$\boldsymbol{a} = (a_1, \dots, a_n)$ 的集合差

$\boldsymbol{a'}$ 为

$\boldsymbol{a}$ 的相邻元素之间的差：

$\boldsymbol{a'} = (a_{i+1} - ai){i \in [n-1]}$ 例如 $\boldsymbol{a} = (2, 6, 4)$ $\boldsymbol{a'} = (6-2, 4-6) = (4, -2)$。

给定数组

$\boldsymbol{a}$ 和

$\boldsymbol{b}$，如果

$\boldsymbol{b}$ 是

$\boldsymbol{a}$ 的子数组，则

$sorted(\boldsymbol{a} | \boldsymbol{b})$ 的集合差包含 $| \boldsymbol{b} |$ 个零，因为每个

$b_i$ 都插入到具有相同值的

$a_j$ 旁边：

例如 $\boldsymbol{a} = (1, 3, 4, 7)$ $\boldsymbol{b} = (1, 7)$ $\boldsymbol{c} = sorted(\boldsymbol{a} | \boldsymbol{b}) = (1, 1, 3, 4, 7, 7)$ $\boldsymbol{c'} = (0, 2, 1, 3, 0)$ $\boldsymbol{c'}$ 包含 $| \boldsymbol{b} | = 2$ 个零。但是，仅凭这一点并不能证明数组是

bolda 的子数组，因为我们可以找到一个数组

$\boldsymbol{f} \nsubseteq \boldsymbol{a}$，其中

$sorted(\boldsymbol{a} | \boldsymbol{f})$ 的集合差包含 $| \boldsymbol{f} |$ 个零：

例如 $\boldsymbol{a} = (1, 1)$ $\boldsymbol{f} = (3, 3)$ $\boldsymbol{g} = sorted(\boldsymbol{a} | \boldsymbol{f}) = (1, 1, 3, 3)$ $\boldsymbol{g'} = (0, 0)$ $\boldsymbol{g'}$ 包含 $| \boldsymbol{f} | = 2$ 个零。

但是，给定一个随机值

$\gamma$，我们可以通过将所有元素移动

$\gamma$ 来测试（w.h.p.）数组

$\boldsymbol{b}$ 是否是数组

$\boldsymbol{a}$ 的子数组：

例如 $\boldsymbol{a} + \gamma = (a_1 + \gamma, \dots, a_n + \gamma)$ $\boldsymbol{b} + \gamma = (b_1 + \gamma, \dots, b_m + \gamma)$ $\boldsymbol{c} = sorted(\boldsymbol{a} | \boldsymbol{b}) = (1, 1, 3, 4, 7, 7)$ $\boldsymbol{c'} = (0, 2, 1, 3, 0)$ $\boldsymbol{c'}$ 包含 $| \boldsymbol{b} | = 2$ 个零。

多集检查（右移施瓦茨-齐佩尔）

给定两个长度相等的数组

$\boldsymbol{a}$ 和

$\boldsymbol{b}$

$n$，如果

$\boldsymbol{a}$ 和

$\boldsymbol{b}$ 都包含相同的元素，而不管它们的顺序如何，则数组元素的乘积将相等：

$\boldsymbol{a} = (x, y, z)$ $\boldsymbol{b} = (x, z, y) = \sigma(\boldsymbol{a})$ $a_1 a_2 a_3 = b_1 b_2 b_3$。但是，两个[等长的]数组的元素的乘积相等并不能保证

$\boldsymbol{a}$ 和

$\boldsymbol{b}$ 包含相同的元素，例如

$\gamma$:

$\boldsymbol{a} = (x, y, z)$ $\boldsymbol{b} = (x, z, y)$ $(a_1 + \gamma)(a_2 + \gamma)(a_3 + \gamma) = (b_1 + \gamma)(b_2 + \gamma)(b_3 + \gamma) \Longrightarrow \boldsymbol{b} = \sigma(\boldsymbol{a})$。

## 背景

### 线性因子包含根

一个单变量多项式

$f(X)$ 拥有

$n$ 个根

$\{a_1, \dots, a_n\}$ 可以唯一地写成

$n$ 个 1 次多项式：

$f(X) = c(X - a_1) \dots (X - a_n)$ $roots(f) = \{a_1, \dots, a_n\}$ 其中

$c$ 是一个常数。如果我们不关心根的符号，我们可以写成：

$f(X) = c(X + a_1) \dots (X + a_n)$ $roots(f) = \{-a_1, \dots, -a_n\}$。

具有线性因子

$(iX - a)$ 的多项式在

$a_i$ 处有一个根：

$f(X) = \prod_{i \in [n]} (iX - a_i) = c(X - a_{11}) \dots (X - a_{nn})$ 其中：$c = 1 * \dots * n$ $roots(f) = \{a_{11}, \dots, a_{nn}\}$。

### 将集合和数组编码为多项式

我们可以将一组值

$\{a_1, \dots, a_n\}$ 编码为一个唯一的多项式：

$f(X) = \prod_{i \in [n]} (X - a_i)$ $roots(f) = \{a_1, \dots, a_n\}$。

我们可以将一个数组

$(a_1, \dots, a_n)$ 编码为一个唯一的多项式，其中每个根编码一个数组元素及其位置：

$f(X) = \prod_{i \in [n]} (iX - a_i)$ $roots(f) = \{a_{11}, \dots, a_{nn}\}$。

**旁注：** 如果一个数组是另一个数组的排列，例如

$\boldsymbol{a} = (a_1, \dots, a_n)$ 且

$\boldsymbol{b} = (b_1, \dots, b_n) = \sigma(\boldsymbol{a})$ 其中

$\sigma = (\sigma_1, \dots \sigma_n)$ 是一个排列，则以下等式成立：

$\prod_{i \in [n]} (iX - a_i) = \prod_{i \in [n]} (\sigma_i X - b_i)$ 例如

$\boldsymbol{a} = (5, 6, 7)$ 且

$\boldsymbol{b} = (6, 7, 5) = \sigma(\boldsymbol{a})$：

$a_1 \rightarrow b_3$ $(\sigma_3 = 1)$ $a_2 \rightarrow b_1$ $(\sigma_1 = 2)$ $a_3 \rightarrow b_2$ $(\sigma_2 = 3)$。

### Schwartz-Zippel 引理

设 $\mathbb{F}$ 是一个域。设 $f(X_1, \dots, X_n) \in \mathbb{F}[X_1, \dots, X_n]$ 是一个在 $\mathbb{F}$ 上的 $n$ 个变量中的非零多项式，总次数为 $d \geq 0$。设 $S \subset \mathbb{F}$ 是一个有限子集，并设 $x_1, \dots, x_n$ 是从 $S$ 中独立且均匀随机选择的。那么

$Pr[f(x_1, \dots, x_n) = 0] \leq \frac{d}{|S|}$。

换句话说，如果一个多项式不是零多项式，那么它只有很小的概率在随机点上求值为零。我们可以用这个引理来证明两个数组是否相同。

设 $f(X_1, \dots, X_n)$ 是一个多项式，如果 $f(X_1, \dots, X_n)$ 是零多项式，那么 $f(x_1, \dots, x_n) = 0$，对于所有的 $x_1, \dots, x_n$。

所以 $Pr[f(X_1, \dots, X_n) \text{ 是零多项式}] = 1 - Pr[f(x_1, \dots, x_n) = 0]$。

对于数组验证，这意味着当我们用一个随机值移动一个数组的所有元素来保证唯一性时，如果乘积匹配，那么数组是相同的，而如果数组不相同，那么乘积匹配的概率很小。

### 低度扩展

给定一个数组

$\\boldsymbol{a}=(a_1,…,a_n) \in \mathbb{F}^n$ 和一个子集

$S=\{s_1,…,s_n\} \subset \mathbb{F}$，那么

$\\boldsymbol{a}$ 的低度扩展是插值多项式

$a(X)$，其次数为

$d=n-1$，通过点

$\{(s_1,a_1),…,(s_n,a_n)\}$：

$\forall i \in [n]: a(s_i)=a_i$。

### 陪集（待办）

我们将约束系统中的每个值与

$\mathbb{F}$ 中的一个唯一值相关联：

$\\boldsymbol{x_l} \rightarrow H_1 \quad \forall i \in [n]: x_l(i) \rightarrow \omega_i$
$\\boldsymbol{x_r} \rightarrow H_2 \quad \forall i \in [n]: x_r(i) \rightarrow 2\omega_i$
$\\boldsymbol{x_o} \rightarrow H_3 \quad \forall i \in [n]: x_o(i) \rightarrow 3\omega_i$ 其中

$H_1, H_2, H_3 < \mathbb{F}$ 是不相交的子群，且

$\omega_i \in H$。然后我们将标签连接成一个长度为

$3n$ 的数组：

$\\boldsymbol{u}=(\omega_1,…,\omega_n,2\omega_1,…,2\omega_n,3\omega_1,…,3\omega_n)$

>- 原文链接： [hackmd.io/@jake/plonk-ar...](https://hackmd.io/@jake/plonk-arithmetization)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～