译自 halo2 book：background/plonkish.md

[WIP] PLONKish 算术化(arithmetization)

我们把电路所定义于其上的域称为 $\mathbb{F}={\mathbb{F}}_p$。

设 $n=2^k$，并假定 $\omega$ 是 ${\mathbb{F}}^{\times }$ 中 $n$ 阶的本原单位根，使得 ${\mathbb{F}}^{\times }$ 有一个乘法子群 $\mathcal{H}=\{1,\omega ,{\omega }^2,\cdots ,{\omega }^{n-1}\}$。这构成一个对应于该子群中元素的拉格朗日基(Lagrange basis)。

多项式规则(Polynomial rules)

一条多项式规则定义了一个约束，该约束必须在每一行（即在乘法子群中的每个元素处）于其指定的各列之间成立。

例如：

a * sa + b * sb + a * b * sm + c * sc + PI = 0

列(Columns)

• 固定列(fixed columns)：对某个特定电路的所有实例都是固定的。这包括选择子列(selector columns)，它们把多项式规则的某些部分"打开"或"关闭"以形成一个"自定义门(custom gate)"。它们也可以包含任何其他固定数据。
• 辅助列(advice columns)：在电路的每个实例中分配的可变值。对应于证明者的秘密见证(secret witness)。
• 公开输入(public input)：类似于辅助列，但是公开已知的值。

每一列都是一个由 $n$ 个值组成的向量，例如 $\mathbf{a}=[a_0,a_1,\cdots ,a_{n-1}]$。我们可以把这个向量看作列多项式 $a(X),X\in \mathcal{H}$ 的求值形式。要恢复系数形式，我们可以使用 拉格朗日插值(Lagrange interpolation)，使得 $a({\omega }^i)=a_i.$

相等性约束(Equality constraints)

• 在一组列之间定义置换(permutation)，例如 $\sigma (a,b,c)$
• 断言这些列中特定单元格之间的相等性，例如 $b_1=c_0$
• 构造置换后的列，它们应当求值为与原始列相同的值

置换总乘积(Permutation grand product)

$$Z({\omega }^i):=\prod _{0\le j\le i}\frac{C_k({\omega }^j)+\beta {\delta }^k{\omega }^j+\gamma }{C_k({\omega }^j)+\beta S_k({\omega }^j)+\gamma },$$ 其中 $i=0,\cdots ,n-1$ 在乘法子群的大小上索引，$k=0,\cdots ,m-1$ 在参与置换的辅助列上索引。这是一个滚动乘积(running product)，其中每一项都包含其之前各项的累积乘积。

TODO：$\delta$ 是什么？保持各列线性无关

检查约束：

1. 第一项等于一 $${\mathcal{L}}_0(X)\cdot (1-Z(X))=0$$

2. 滚动乘积构造良好。对每一行，我们检查下式成立： $$Z({\omega }^i)\cdot (C({\omega }^i)+\beta S_k({\omega }^i)+\gamma )-Z({\omega }^{i-1})\cdot (C({\omega }^i)+{\delta }^k\beta {\omega }^i+\gamma )=0$$ 重新整理得到 $$Z({\omega }^i)=Z({\omega }^{i-1})\frac{C({\omega }^i)+\beta {\delta }^k{\omega }^i+\gamma }{C({\omega }^i)+\beta S_k({\omega }^i)+\gamma },$$ 这正是我们最初定义总乘积多项式的方式。

查找(Lookup)

参考：Generic Lookups with PLONK (DRAFT)

消失论证(Vanishing argument)

我们想要检查由门约束(gate constraints)、置换约束(permutation constraints)和查找约束(lookup constraints)所定义的表达式，在乘法子群的所有元素处求值都为零。为此，证明者把所有表达式坍缩(collapse)成一个多项式 $$H(X)=\sum _{i=0}^e{y}^i{E}_i(X),$$ 其中 $e$ 是表达式的个数，$y$ 是一个用于保持各约束线性无关的随机挑战。然后证明者把它除以消失多项式（见小节：消失多项式(Vanishing polynomial)），并对所得的商承诺

$$\text{Commit}(Q(X)),\text{where }Q(X)=\frac{H(X)}{Z_H(X)}.$$

验证者以一个随机求值点 $x$ 回应，对此证明者回复声称的求值 $q=Q(x),\{e_i{\}}_{i=0}^e=\{E_i(x){\}}_{i=0}^e.$ 现在，验证者剩下要检查的就是这些求值是否满足

$$q\stackrel{?}{=}\frac{{\sum }_{i=0}^e{y}^i{e}_i}{Z_H(x)}.$$

注意我们还没有检查所承诺的多项式在 $x$ 处确实求值为所声称的值，即 $x,q\stackrel{?}{=}Q(x),\{e_i{\}}_{i=0}^e\stackrel{?}{=}\{E_i(x){\}}_{i=0}^e.$ 这个检查由多项式承诺方案处理（在下一节描述）。