这篇文章上次修改于 210 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

程序可以转换为电路，电路上有门和线，所有会有门约束和线约束两种等式，这些等式可以限定电路的形状。

门约束用来检查电路的运算是否对，线约束是限制某个门的输入必须等于另一个门的输入和或输出，也称拷贝约束。其中，门约束比较容易理解，而线约束会比较绕。

约束太多的话会导致证明和验证的开销比较大，所有会把多个约束放到一个等式中。

prover 和 verifier 之间通过多项式承诺来完成等式的证明。

1 门约束

门会有两个输入 a, b 和一个输出 c，可以执行加法和乘法运算。引入门的选择子 $Q=(q_L, q_R, q_O, q_M, q_C)$，分别为左、右、输出、乘法、常数选择子，就可以将所有的门用一个同一个式子表示：

$$ （q_L)_i \cdot a_i + (q_R)_i \cdot b_i + (q_O)_i \cdot c_i + (q_M)_i \cdot (a_ib_i) + (q_C)_i = 0 $$

为了减少约束的数量，一组门约束可以化成一个式子，只需要将上述式子中的每项化成一个多项式即可，可通过拉格朗日插值法或 FFT 解决。最终得到三端口 $a(x), b(x), c(x)$ 多项式的门约束系统（过程比较简单，略）：

$$ Q_L(x) \cdot a(x) + Q_R(x) \cdot b(x) + Q_O(x) \cdot c(x) + Q_M(x) \cdot a(x)b(x) + Q_C(x) = 0 $$

可改写为：

$$ Q_L(x) \cdot a(x) + Q_R(x) \cdot b(x) + Q_O(x) \cdot c(x) + Q_M(x) \cdot a(x)b(x) + Q_C(x) = Z(x)H(x) $$

其中，$Z(x)= (x-1)(x-w)(x-w^2)...(x-w^{n-1})$ ，n 是电路中门的数量，$H(x)$ 是商多项式。 如果选择 $w^n = 1$，那么有 $Z(x) = x^n - 1$

2 线约束

2.1 大数上的线约束

怎样才能约束一个值等于另一个值呢？如果一个个值去比较，就太麻烦了，如果将各个值累乘起来，结果不变，就可以一次性验证多个值是否相等。

先理解置换，比如对于一个排列 $(a_1, a_2, a_3, a_4)$，将 $a_1$ 和 $a_4$ 调换后得到 $(a_4, a_2, a_3, a_1)$，调换前后的两个排列是相等的，则说明 $a_1$ 和 $a_4$ 对应的值是相等的。可以用置换函数$\sigma_a(x)$ 表示 a 的置换关系。

如何比较方便地比较两个排列是相等的？可使用“坐标累加器（感觉叫坐标累乘器更好些）”。假设 $X(x), Y(x)$ 分别是表示 x 和 y 的多项式，例如对于横坐标 $x=(0, 1, 2, 3)$，纵坐标 $y=(-2, 1, 0, 1)$，可得到 $x$ 的多项式 $X(x) = x$，$y$ 的表达式 $Y(x) = x^3 - 5x^2 + 7x - 2$。再定义 $p(x)$ 为前几个坐标的累加（不包含当前点），可得到递推式 $p(x+1) = p(x) \cdot (v_1 + X(x) + v_2 \cdot Y(x))$，$v_1, v_2$ 是随机值。要验证两个排列相等，只需要验证 $p(n) = p'(n)$ 相等即可，因为乘法满足交换律。

a, b, c 之间也可能存在线约束，比如 $a_1 = b_2$，为了用一维表示三维，可为 a, b, c 都分配一段 X 坐标，比如 $X_a(x) = x \space, X_b(x) = n + x, \space X_c(x) = 2n + x$，替换后的坐标可能是跨越所有 3 个集合的排列。然后检查三个不同式子的乘积是否相等（终点约束）：

$$ p_a(n) \cdot p_b(n) \cdot p_c(n) = p_a'(n) \cdot p_b'(n) \cdot p_c'(n) $$

不过，在电路中，横坐标不是用 $x=0,...n-1$ 表示，为了使用 FFT 快速运算，采用 n 次单位根 $w^n = 1$，横坐标用 $w: 1, w, w^2...w^{n-1}$ 表示，所以需要将 $p(x+1) = p(x) \cdot (v_1 + X(x) + v_2 \cdot Y(x))$ 改为 $p(w \cdot x) = p(x) \cdot (v_1 + X(x) + v_2 \cdot Y(x))$，每段坐标范围从 $0..n-1, n..2n-1, 2n..3n-1$ 改为 $w^i, g \cdot w^i, g^2 \cdot w^i$

最终得到

$$ \begin{align} & P_a(wx) - P_a(x)(v_1 + x + v_2a(x)) = Z(x)H_1(x) \\ & P_a'(wx) - P_a'(x)(v_1 + \sigma_a(x) + v_2a(x)) = Z(x)H_2(x) \\ & P_b(wx) - P_b(x)(v_1 + x + v_2b(x)) = Z(x)H_3(x) \\ & P_b'(wx) - P_b'(x)(v_1 + \sigma_b(x + v_2b(x)) = Z(x)H_4(x) \\ & P_c(wx) - P_c(x)(v_1 + x + v_2a(x)) = Z(x)H_5(x) \\ & P_c'(wx) - P_c'(x)(v_1 + \sigma_c(x) + v_2c(x)) = Z(x)H_6(x) \\ \end{align} $$

其中，$Z(x)= (x-1)(x-w)(x-w^2)...(x-w^{n-1})$ ，$H(x)$ 是商多项式。 对于 $w^n = 1$，有 $Z(x) = x^n - 1$

还有起点和终点约束：

$$ \begin{align} & P_a(1) = P_b(1) = P_c(1) = P_a'(1) = P_b'(1) = P_c'(1) = 1 \\ & P_a(w^n)P_b(w^n)P_c(w^n) = P_a'(w^n)P_b'(w^n)P_c'(w^n) \end{align} $$

2.2 乘法群上的线约束

阶为 n 的群 G，生成元为 g，$\left\{L_i \right\}_{i \in [n]}$ 是群 G 上的拉格朗日基

$$ \begin{align} & L_i(g^j) = 1, i=j \\ & L_i(g^j) = 0, i \neq j \\ \end{align} $$

对于 $f, h \in F_{<n}[X]$，置换 $\sigma: [n] \rightarrow [n]$，如果对于 $i \in [n]$，有 $h(g^i) = f(g^{\sigma(i)})$，则记为 $h=\sigma(f)$，多项式 $h$ 是多项式 $f$ 的一个置换。

多项式预处理：（双方都知道的线）在域 $F_{<n}[X]$ 上的多项式 $S_{ID}(g^i) = i, S_{\sigma}(g^i) = \sigma(i), i \in [n]$。在某个 $i$ 和 $\sigma(i)$ 处是相等的，是一个置换关系

输入多项式：（证明方知道保密数据多项式）$f, h \in F_{<n}[X]$，证明方需要证明 $f, h$ 是置换关系

验证方：选择并发送随机数 $\beta, \gamma$，也可以由证明方根据 transcript 算出

证明方：多项式 $f'(g^i) = f(g^i) + \beta \cdot i + \gamma, \space h'(g^i) = h(g^i) + \beta \cdot \sigma(i) + \gamma$ ，计算

$$ Z(g^{i}) = \prod_{1 \le j < i}\frac{f'(g^j)}{h'(g^j)} $$

证明 $(a_1, a_2, a_3, a_4) = (a_3, a_1, a_2, a4)$

与下标发生联系 $[(a_1, 1), (a_2, 2), (a_3, 3), (a_4, 4)] = [(a_3, 1), (a_2, 2), (a_1, 3), (a_4, 4)]$

推广 $(a_i, i) = (a', \sigma(i))$

可以把元组折叠成一个值 $a_i + \beta i, \space a_i' + \beta \sigma(i)$

其中 $Z(g) = 1$，将累加器值 $Z$ 发送给可信第三方 $I$ （可通过多项式承诺去掉可信第三方）

验证方：对于所有 $a \in G$，检查如下式子是否满足

$$ \begin{align} & L_1(a)(Z(a) - 1) = 0 \\ & Z(a)f'(a) = h'(a)Z(a \cdot g) \end{align} $$

第一个式子是起始约束，第二个式子是递归约束。如果校验通过，就可以确信 $h$ 确实是 $f$ 的一个置换，因为可以推出 $\prod^n_{i=1}\frac{f'(g^i)}{h'(g^i)} = 1$，推导如下：

  • 第一个式子

    如果 $a = g^1$，则 $L_1(g^1) = 1$，则 $L_1(g)(Z(g)-1) = 0 \rightarrow Z(g) = 1$

    如果 $a=g^i, i \in [2,n]$，则 $L_1(g^i) = 0$，第一个式子一定成立

  • 第二个式子

    群 G 的阶为 n，则 $g = g^{n+1}$

    第二个式子变形，得到 $Z(a \cdot g) =Z(a) \frac{f'(a)}{h'(a)}$，相当于是 $Z(g^{a+1}) =Z(g^a) \frac{f'(g^a)}{h'(g^a)}$

    所以

    $$ \begin{align} & 1 = Z(g) = Z(g^{n+1}) = Z(g^n)\frac{f'(g^n)}{h'(g^n)} \\ & = Z(g^{(n-1)})\frac{f'(g^{(n-1)})f'(g^n)}{h'(g^{(n-1)})h'(g^n)} \\ & = ... \\ & = Z(g)\prod^n_{i-1}\frac{f'(g^i)}{h'(g^i)} \\ & = \prod^n_{i=1}\frac{f'(g^i)}{h'(g^i)} \\ \end{align} $$

3 多项式承诺

多项式承诺可以用更短的结构来代表一个多项式，在不需要包含多项式所有数据的情况下，证明知道该多项式。也就是说，如果某人给了你一个承诺 $c$，相当于给了一个证明，知道对于某处 $z$，其值为 $f(z)$。简单理解，是用某个随机点来代表整个多项式。

会包含两部分，承诺 $C = f(s) \cdot g$ 和在随机点 $z$ 处打开多项式得到值 $f(z)$

Kate 承诺使用一些椭圆曲线点来生成承诺，椭圆曲线点通过一个秘密值 $s$ 生成。

打开承诺时，如果要证明 $f(z) = a$，只需要证明

$$ h(x) = \frac{f(x) - a}{x-z} $$

是一个多项式。因为如果商是一个多项式，说明 $x-z$ 是 $f(x)-a$ 的因子，说明 $z$ 是 $f(x) - a = 0$ 的解，即 $f(z) = a$

算出商多项式的承诺 $W = h(s) \cdot g$

将 $(z, f(z), W)$ 发送给 verifier

verifier 在验证时，需要借助双线性映射 $e(C, g) = e(W, sg-zg) \cdot e(g, g)^{f(z)}$ ，如果通过，说明商多项式存在，说明 $f(z) = a$

更详细的介绍见：https://aping-dev.com/index.php/archives/464/

4 PLONK 协议

得到公共预处理信息，包括门的系数 $Q_L(x), Q_R(x), Q_M(x), Q_O(x), Q_C(x)$ 和置换函数 $S_{\sigma1(x)}, S_{\sigma2(x)}, S_{\sigma3(x)}$

公共处理中的知识：

$q(x) = q_0L_0(x) + q_1L_1(x) + ... + q_{n-1}L_{n-1}(x)$

$L_i(w_i) = 1,\space L_i(w_j) = 0(j \ne i)$

$x=w_0 \rightarrow q(x) = q_0; \space x=w_i \rightarrow q(x) = q_i$ ，相当于是找到了一条线，将所有的点都穿起来了

Prover 过程：

  1. 门多项式承诺。算出 a(x)，b(x) 和 c(x) 的多项式形式，输出承诺 $([a]_1, [b]_1, [c]_1)$
  2. 线多项式承诺。算出线约束多项式 d(x) ，输出承诺 $([d]_1)$

  3. 保密数据满足门约束和线约束。算出商多项式 $t(x) = f(x) / Z_H(x)$，其中，f(x) 如下

    $$ \begin{align} f(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)) \\ &+ \alpha(L_0(x)(d(x) - 1)) \\ &+ \alpha^2(d(wx)f_d(x) - d(x)g_d(x)) \\ &= t(x)Z_H(x) \end{align} $$

    t(x) 是核心，将门约束多项式，线约束多项式融合成了一个多项式：第 1 行是门约束，剩下的是线约束，包括线约束的递归约束和起点约束。

    因为 t(x) 的阶比较高，所以分解 3 个多项式 $t(x) = t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)$，输出承诺 $([t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1)$。

  4. 多项式求值。根据随机数 $z = H(transcript)$ 输出 $(a(z), b(z), c(z), S_{\sigma1}(z), S_{\sigma2}(z), S_{\sigma3}(z), d(wz))$ 。

  5. 多项式随机打开点。

    如果想证明 $f(z)=t(z) \cdot Z_H(z) $，可以证明 $z$ 是 $h(x) = f(x) - t(x) \cdot Z_H(z)$ 的根

    正常情况下，应该直接证明 $z$ 是 $h(x) = f(x) - t(x) \cdot Z_H(z) = f(x) - [t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)] \cdot Z_H(z)$ 的根，但 $x^n, x^{2n}$ 无法被承诺，因为承诺的取值是在 $x^n$ 内，可以先把定点 z 带进去：

    $$ r(x) = f(x) - [t_{lo}(x) + z^n \cdot t_{mid}(x) + z^{2n} \cdot t_{hi}(x)] \cdot Z_H(z) $$

    这样 r 就是线性的了，没有乘积的关系。

    根据 2 个打开的随机点算出 2 个商多项式，得到 2 个承诺 $([W_z]_1, [W_{wz}]_2)$

最终得到 $\pi_{SNARK} = ([a]_1, [b]_1, [c]_1, [d]_1, [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1, [W_z]_1, [W_{wz}]_2, a(z), b(z), c(z), S_{\sigma1}(z), S_{\sigma2}(z), S_{\sigma3}(z), d(wz))$

Verifier 过程：

进行一些数据的检查，然后从第 8 步开始

  1. 计算辅助多项式 r。因为无法直接重构 $h(x)= f(x) - t(x) \cdot Z_H(z) = f(x) - [t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)] \cdot Z_H(z) $ 的承诺，所以先把 $z$ 代进去，算出多项式 $r(x) = f(x) - t(x) \cdot Z_H(z) = f(x) - [t_{lo}(x) + z^n \cdot t_{mid}(x) + z^{2n} \cdot t_{hi}(x)] \cdot Z_H(z) $
  2. 基于多项式的值和 r，计算批量多项式承诺的第一步分 $[D]_1$

  3. 基于多项式的值和 $[D]_1$，计算多项式承诺的线性组合

    $[F]_1 = [D_1] + v \cdot [a]_1 + v^2 \cdot [b]_1 + v^3 \cdot [c]_1 + v^4 \cdot [S_{\sigma1}]_1 + v^5 \cdot [S_{\sigma2}]_1$

  4. 计算函数值

    $[E]_1 = [-r_0 + va(z) + v^2b(z) + v^3c(z) + v^4S_{\sigma1}(z) + v^5S_{\sigma2}(z) + ud(wz))]_1$

  5. 基于双线性进行验证 $e([W_z]_1 + u \cdot [W_{wz}]_1, \space [x]_2) = e(z \cdot [W_z]_1 + uzw \cdot [W_{wz}]_1 + [F]_1 - [E]_1, \space [1]_2) $，如果通过，说明前面的打开点正确，说明商多项式 t(x) 正确，说明门约束和线约束成立。

    公式推导：

    已知

    $$ \begin{align} & W_z(x) = \frac{f(x) - f(z)}{x - z} \\ & W_{wz}(x) = \frac{f'(x) - f'(wz)}{x - wz} \\ & F = f(x) + uf'(x) \\ & E = f(z) + uf'(zw) \\ \end{align} $$

    所以

    $$ \begin{align} & e([W_z]_1 + u \cdot [W_{wz}]_1, \space [x]_2) \\ & = e(\frac{f(x) - f(z)}{x - z} \cdot g_1 + u \cdot \frac{f'(x) - f'(wz)}{x - wz} \cdot g_1 , \space x \cdot g_2) \\ & = e(x \cdot \frac{f(x - f(z))}{x - z} \cdot g_1 + ux \cdot \frac{f'(x) - f'(wz)}{x - wz} \cdot g_1 , \space g_2) \\ &\\ & = e(z \cdot [W_z]_1 + uzw \cdot [W_{wz}]_1 + [F]_1 - [E]_1, \space [1]_2) \\ & = e(z \cdot \frac{f(x - f(z))}{x - z} \cdot g_1 + uwz \cdot \frac{f'(x) - f'(wz)}{x - wz} \cdot g_1 + [F]_1 - [E]_1, \space g_2) \\ &\\ & e([W_z]_1 + u \cdot [W_{wz}]_1, \space [x]_2) \space / \space e(z \cdot [W_z]_1 + uzw \cdot [W_{wz}]_1 + [F]_1 - [E]_1, \space [1]_2) \\ & = e((x-z)\cdot \frac{f(x) - f(z)}{x-z} \cdot g_1 + u(x-wz) \cdot \frac{f'(x) - f(wz)}{x - zw} \cdot g_1 + [E]_1 - [F]_1, \space g_2)) \\ & = e((f(x) - f(z) + u(f'(x)-f'(wz))) \cdot g_1 + [E]_1 - [F]_1, \space g_2) \\ & = e((f(x) - f(z) + u(f'(x)-f'(wz))) \cdot g_1 + (f(z) + uf'(wz)) \cdot g_1 - (f(x) + uf'(x)) \cdot g_1, \space g_2) \\ & = e(0, g_2) \\ & = 1 \end{align} $$

参考

PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

https://github.com/sCrypt-Inc/awesome-zero-knowledge-proofs#plonk