理解 PLONK（二）：多项式编码

在上篇文章里，我们可以把电路的计算的「合法性检查」转换成一组加法/乘法约束。假如总共有 N 个约束，那么Prover 可以通过多项式编码的方式把多个约束压缩成一个约束，让 Verifier 轻松检查。

多项式的概率检查

把多个约束验证合并的神奇能力来自于「多项式随机挑战」。如果有两个多项式 $f (X)$ 和 $g (X)$ 同为两个次数不超过 $d$ 的多项式。那么 Verifier 只需要给出一个随机挑战值 $ζ \in F$ ，计算 $f (ζ)$ 是否等于 $g (ζ)$ 即可大概率得知 $f (X) = g (X)$ ，其中出错的概率 $\leq \frac{d}{∣ F ∣}$ 。只要保证 $F$ 足够大，那么检查出错的概率就可以忽略不计。

这个原理被称为 Schwartz-Zippel 定理。

假如要验证两个向量 $a + b$ 是否等于 $c$ ，为了可以一步挑战验证，我们要先把三个向量编码成多项式。

一种最直接的方案是把向量当作多项式的「系数」进行编码

$a (X) b (X) c (X) = a_{0} + a_{1} X + a_{2} X^{2} + \dots + a_{n - 1} X^{n - 1} = b_{0} + b_{1} X + b_{2} X^{2} + \dots + b_{n - 1} X^{n - 1} = c_{0} + c_{1} X + c_{2} X^{2} + \dots + c_{n - 1} X^{n - 1}$

显然，如果 $a_{i} + b_{i} = c_{i}$ ，那么 $a (X) + b (X) = c (X)$ 。然后我们可以通过挑战一个随机数 $ζ$ 来检验三个多项式在 $X = ζ$ 处的取值，验证：

$a (ζ) + b (ζ) = ? c (ζ)$

如果上式成立，那么 $a + b = c$ 。

Lagrange 插值与 Evaluation Form

假如我们要验证 $a \circ b = ? c$ ，用系数编码的方式就不容易处理了，因为 $a (X) \cdot b (X)$ 会产生很多的交叉项。并且 $a_{i} \cdot b_{i}$ 和 $c_{i}$ 的项并不对应到 $X^{i}$ 的系数，比如 $a_{1} \cdot b_{1}$ 的系数出现在 $X^{2}$ 上，但同时 $X^{2}$ 项的系数组成还有 $a_{0} \cdot b_{2}$ 和 $a_{2} \cdot b_{0}$ 。而 $c_{1}$ 是 $X^{1}$ 的系数。

我们需要另一种多项式编码方案，利用 Lagrange Basis。如果我们要构造多项式 $a (X)$ ，使得它在定义域 $H = (w_{0}, w_{1}, \dots w_{N - 1})$ 上的取值为 $a$ ，即

$a (w_{0}) a (w_{1}) a (w_{N - 1}) = a_{0} = a_{1} ⋮ = a_{N - 1}$

插值需要用到一组插值多项式： ${L_{i} (X)}_{i \in [0, N - 1]}$ ，其中 $L_{i} (w_{i}) = 1$ ，并且 $L_{i} (w_{j}) = 0 (j \neq = i)$ 。然后 $a$ 可以按如下方式编码：

$a (X) = a_{0} \cdot L_{0} (X) + a_{1} \cdot L_{1} (X) + a_{2} \cdot L_{2} (X) + \dots + a_{N - 1} \cdot L_{N - 1} (X)$

可以简单心算一下，当 $X = w_{0}$ 时，等式右边除了第一项之外，其他项都等于零，于是 $a (w_{0}) = a_{0}$ 。看起来 $L_{i} (X)$ 像是一个选择器，这组多项式又被称为 Lagrange Polynomials。

我们用同样的方法来编码 $b (X)$ 和 $c (X)$ ：

$b (X) = b_{0} \cdot L_{0} (X) + b_{1} \cdot L_{1} (X) + b_{2} \cdot L_{2} (X) + \dots + b_{N - 1} \cdot L_{N - 1} (X) c (X) = c_{0} \cdot L_{0} (X) + c_{1} \cdot L_{1} (X) + c_{2} \cdot L_{2} (X) + \dots + c_{N - 1} \cdot L_{N - 1} (X)$

如果 $a_{i} \cdot b_{i} = c_{i}$ 成立，那么 $a (w_{i}) \cdot b (w_{i}) = c (w_{i})$ 。如果 $a \circ b = c$ ，那么

$a (X) \cdot b (X) = c (X), \forall X \in H$

我们现在已经把两个向量的按位乘积问题转换到了三个多项式之间的关系，接下来的问题是如何进行随机挑战验证。

我们发现：如果直接让 Verifier 发送随机数 $ζ$ 挑战上面的等式，那么 $ζ$ 只能属于 $H$ 。如果只存在一个 $j$ 使得 $a_{j} \cdot b_{j} \neq = c_{j}$ ，那么 Verifier 的一次挑战能发现这个错误的概率只有 $\frac{1}{∣ n ∣}$ ，这样 Verifier 需要挑战多次才能缩小检测出错的概率。不过这样不满足我们的要求，我们希望只通过一次挑战来检测出 Prover 的作弊行为。

我们可以把上面的等式的 $X$ 取值范围去除，换成下面的等式：

$a (X) \cdot b (X) - c (X) = q (X) \cdot z_{H} (X), \forall X \in F$

这个等式在整个 $F$ 定义域上都成立。这是为何？

首先我们看等式左边的多项式： $a (X) \cdot b (X) - c (X)$ ，不妨定义为 $f (X)$ 。我们可以看到 $f (X)$ 在 $X \in H$ 上等于零，那么意味着 $H$ 恰好是 $f (X)$ 的「根集合」。于是 $f (X)$ 可以按照下面的方式进行因式分解：

$f (X) = (X - w_{0}) (X - w_{1}) (X - w_{2}) \dots (X - w_{N - 1}) \cdot q (X)$

换个说法， $f (X)$ 可以被多项式 $z_{H} (X) = (X - w_{0}) (X - w_{1}) (X - w_{2}) \dots (X - w_{n - 1})$ 整除，并得到一个商多项式 $q (X)$ 。零多项式 $z_{H} (X)$ 又被称为 Vanishing Polynomial。

如果我们让 Prover 计算出这个 $q (X)$ ，并且发送给 Verifier，又因为 $H$ 是已知的系统参数，Verifier 可以自行计算 $z_{H} (X)$ ，那么 Verifier 只需要一次随机检测即可判断 $a (X) \cdot b (X) - c (X)$ 是否在 $H$ 处等零。

$a (ζ) \cdot b (ζ) - c (ζ) = ? q (ζ) \cdot z_{H} (ζ)$

进一步，如果我们使用多项式承诺（Polynomial Commitment），Verifier 可以让 Prover 来帮忙计算这些多项式在 $X = ζ$ 处的取值，发送并证明这些值的正确性，这样能最大限度地减少 Verifier 的工作量。

但是， Verifier 计算 $z_{H} (ζ)$ 需要 $O (n)$ 的计算量。

那能否让 Verifier 继续减少工作量？答案是可以的，只要我们选择特殊的 $H \subset F$ 。

单位根 Roots of Unity

如果我们选择单位根作为 $H$ ，那么 $z_{H} (ζ)$ 的计算量会降为 $O (lo g n)$ 。

对于任何有限域 $F_{p} = (0, 1, \dots, p - 1)$ ，其中阶数 $p$ 为素数。那么去除零之后剩下的元素构成了乘法群 $F_{p}^{*} = (1, \dots, p - 1)$ ，阶数为 $p - 1$ 。由于 $p - 1$ 一定为偶数，那么 $p - 1$ 的乘法因子中一定包含若干个 $2$ ，假设记为 $λ$ 个 $2$ 。那么 $F_{p}^{*}$ 一定包含一个阶数为 $2^{λ}$ 的乘法子群。不妨设 $n = 2^{k}, k \leq λ$ ，那么一定存在一个阶数为 $n$ 的乘法子群，记为 $H$ 。该乘法子群必然含有一个生成元，记为 $ω$ ，并且 $ω^{N} = 1$ 。这相当于把 $1$ 开 $N$ 次方根，因此被称为单位根。不过单位根不只有一个 $ω$ ，我们会发现 $ω^{2}, ω^{3}, \dots, ω^{N - 1}$ 都满足单位根的特性，即 $(ω^{k})^{N} = 1, k \in (2, 3, \dots, N - 1)$ 。那么所有这些由 $ω$ 产生的单位根就组成了乘法子群 $H$ ：

$H = (1, ω, ω^{2}, ω^{3}, \dots, ω^{N - 1})$

这些元素满足一定的对称性：比如 $ω^{\frac{N}{2}} = - 1$ ， $ω = - ω^{\frac{N}{2} + 1}$ ， $ω^{i} = - ω^{\frac{N}{2} + i}$ 。又比如把所有的单位根求和，我们会得到零：

$i = 0 \sum N - 1 ω^{i} = 0$

举一个简单的例子，我们可以在 $F_{13}$ 中找到一个阶数为 $4$ 的 $H$ 。

$F_{13} = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)$

其中乘法群的生成元为 $g = 2$ 。由于 13-1=3*2*2，所以存在一个阶数为 $4$ 的乘法子群，其生成元为 $ω = 5$ ：

$H = (ω^{0} = 1, ω^{1} = 5, ω^{2} = 12, ω^{3} = 8)$

而 $ω^{4} = 1 = ω^{0}$ 。

在实际应用中，我们会选择一个较大的有限域，它能有一个较大的 Powers-of-2 乘法子群。比如椭圆曲线 BN254 的 Scalar Field，含有一个阶数为 $2^{28}$ 的乘法子群，BLS-12-381 的Scalar Field 含有一个阶数为 $2^{32}$ 的乘法子群。

在乘法子群 $H$ 上，具有下面的性质：

$z_{H} (X) = i = 0 \prod N - 1 (X - ω^{i}) = X^{N} - 1$

我们可以进行简单的推导，假设 $N = 4$ ，由于 $ω^{i}$ 的对称性，这个计算过程可以不断化简：

$= = = = = (X - ω^{0}) (X - ω^{1}) (X - ω^{2}) (X - ω^{3}) (X - 1) (X - ω) (X + 1) (X - ω^{3}) (X^{2} - 1) (X - ω) (X + ω) (X^{2} - 1) (X^{2} - ω^{2}) (X^{2} - 1) (X^{2} + 1) (X^{4} - 1)$

Lagrange Basis

对于 Lagrange 多项式， $L_{i} (w_{i}) = 1$ ，并且 $L_{i} (w_{j}) = 0, (j \neq = i)$ 。接下来，我们给出 $L_{i} (X)$ 的构造。

为了构造 $L_{i} (X)$ ，先构造不等于零的多项式部分。由于 $L_{i} (ω_{j}) = 1, j = i$ ，因此他一定包含 $\prod_{j, j \neq = i} (X - ω_{j})$ 这个多项式因子。但该因子显然在 $X = ω_{i}$ 处可能不等于 $1$ ，即可能 $\prod_{j, j \neq = i} (ω_{i} - ω_{j}) \neq = 1$ 。然后，我们只要让该因子除以这个可能不等于 $1$ 的值即可，于是 $L_{i} (X)$ 定义如下：

$L_{i} (X) = \frac{\prod _{j \in H ∖ {i}} ( X - ω _{j} )}{\prod _{j \in H ∖ {i}} ( ω _{i} - ω _{j} )} = j \in H ∖ {i} \prod \frac{X - ω _{j}}{ω _{i} - ω _{j}}$

不难发现， $L_{i} (X)$ 在 $X = ω_{i}$ 处等于 $1$ ，其它位置 $X = ω_{j}, j \neq = i$ 处等于 $0$ 。

对于任意次数小于 $N$ 的多项式 $f (X)$ ，那么它都可以唯一地表示为：

$f (X) = a_{0} \cdot L_{0} (X) + a_{1} \cdot L_{1} (X) + a_{2} \cdot L_{2} (X) + \dots + a_{N - 1} \cdot L_{N - 1} (X)$

我们可以用多项式在 $H$ 上的值 $(a_{0}, a_{1}, a_{2}, \dots, a_{N - 1})$ 来表示 $f (X)$ 。这被称为多项式的求值形式（Evaluation Form），区别于系数形式（Coefficient Form）。

两种形式可以在 $H$ 上可以通过 (Inverse) Fast Fourier Transform 算法来回转换，计算复杂度为 $O (N lo g N)$ 。

多项式的约束

利用 Lagrange Basis 我们可以方便地对各种向量计算进行约束。

比如我们想约束 $a = (h, a_{1}, a_{2}, \dots, a_{N - 1})$ 向量的第一个元素为 $h$ 。那么我们可以对这个向量进行编码，得到 $a (X)$ ，并且进行如下约束：

$L_{0} (X) (a (X) - h) = 0, \forall X \in H$

Verifier 可以挑战验证下面的多项式等式：

$L_{0} (X) (a (X) - h) = q (X) \cdot z_{H} (X)$

再比如，我们想约束 $a = (h_{1}, a_{1}, a_{2}, \dots, a_{N - 2}, h_{2})$ 向量的第一个元素为 $h_{1}$ ，最后一个元素为 $h_{2}$ ，其它元素任意。那么 $a (X)$ 应该满足下面两个约束。

$L_{0} (X) \cdot (a (X) - h_{1}) L_{N - 1} (X) \cdot (a (X) - h_{2}) = 0, \forall X \in H = 0, \forall X \in H$

那么通过 Verifier 给一个随机挑战数（ $α$ ），上面两个约束可以合并为一个多项式约束：

$L_{0} (X) \cdot (a (X) - h_{1}) + α \cdot L_{n - 1} (X) \cdot (a (X) - h_{2}) = 0, \forall X \in H$

接下来，Verifier 只要挑战下面的多项式等式即可：

$L_{0} (X) \cdot (a (X) - h_{1}) + α \cdot L_{n - 1} (X) \cdot (a (X) - h_{2}) = q (X) \cdot z_{H} (X)$

如果想验证 $a$ 和 $b$ 两个等长向量除第一个元素之外，其它元素都相等，那要如何约束呢？假设 $a (X)$ 和 $b (X)$ 为两个向量的多项式编码，那么它们应该满足：

$(X - ω^{0}) (a (X) - b (X)) = 0$

当 $X = ω^{0}$ 时，左边多项式的第一个因子等于零，而 $X \in H ∖ {ω^{0}}$ 时，则左边第二因子等于零，即表达了除第一项可以不等之外，其它点取值都必须相等。

可以看出，采用 Lagrange 多项式，我们可以灵活地约束多个向量之间的关系，并且可以把多个约束合并在一起，让 Verifier 仅通过很少的随机挑战就可验证多个向量约束。

Coset

在素数有限域的乘法群中，对于每一个乘法子群 $H$ ，都有多个等长的陪集（Coset），这些 Coset 具有和 $H$ 类似的性质，在 Plonk 中也会用到 Coset 的概念，这里只做部分性质的介绍。

还拿 $F_{13}$ 为例，我们取 $H = (1, 5, 12, 8)$ ，并且乘法群的生成元 $g = 2$ 。于是我们可以得到下面两个 Coset：

\begin{split} H_1 &= g\cdot H = (g, g\omega, g\omega^2, g\omega^3) &= (2,10,11,3) \ H_2 &= g^2\cdot H = (g^2, g^2\omega, g^2\omega^2, g^2\omega^3) &= (4,7,9,6) \ \end{split}

可以看到 $F_{13}^{*} = H \cup H_{1} \cup H_{2}$ ，并且它们交集为空，没有任何重叠。并且它们的 Vanishing Polynomial 也可以快速计算：

$z_{H_{1}} (X) = X^{N} - g^{N}, z_{H_{2}} (X) = X^{N} - g^{2 N}$

References

Schwartz–Zippel lemma. https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

World of Z2O-K7E