04. PLONK 算术化：门约束、wiring permutation 与 grand product

发表于 2026/07/29 更新于 2026/07/29

作者 Chen Xichao

13 分钟阅读

1. 把电路排成三列

原始 PLONK 用 $n$ 行、三条 witness wires：

row $i$	left $a_i$	right $b_i$	output $c_i$
0	$a_0$	$b_0$	$c_0$
1	$a_1$	$b_1$	$c_1$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n-1$	$a_{n-1}$	$b_{n-1}$	$c_{n-1}$

每行有五个 fixed selector：

\[q_{L,i},q_{R,i},q_{M,i},q_{O,i},q_{C,i},\]

并要求

\[q_{L,i}a_i +q_{R,i}b_i +q_{M,i}a_ib_i +q_{O,i}c_i +q_{C,i}=0.\]

同一个通用公式可表达：

门	$q_L$	$q_R$	$q_M$	$q_O$	$q_C$
$c=a+b$	1	1	0	-1	0
$c=ab$	0	0	1	-1	0
$a=k$	1	0	0	0	$-k$
noop	0	0	0	0	0

因此 selector 是“电路程序”，witness columns 是“这次执行的数据”。

2. 从逐行门到 polynomial identity

取

\[H=\{1,\omega,\ldots,\omega^{n-1}\}.\]

插值 witness：

\[A(\omega^i)=a_i,\quad B(\omega^i)=b_i,\quad C(\omega^i)=c_i,\]

以及 fixed selectors：

\[Q_L(\omega^i)=q_{L,i},\ldots, Q_C(\omega^i)=q_{C,i}.\]

定义 gate polynomial

\[\begin{aligned} G(X) ={}&Q_L(X)A(X) +Q_R(X)B(X)\\ &+Q_M(X)A(X)B(X) +Q_O(X)C(X) +Q_C(X). \end{aligned}\]

所有门成立当且仅当

\[G(h)=0\qquad\forall h\in H,\]

也就是

\[Z_H(X)=X^n-1 \quad\text{整除}\quad G(X).\]

2.1 public input

可定义一个 public-input polynomial $PI(X)$，在使用公开输入的行取约定的正/负值，其余行为 0，并把

\[G(X)\leftarrow G(X)+PI(X).\]

不同实现对符号和 public input 所在列的约定不同；安全要求只有两条：

public values 确实进入 vanishing identity；
它们及其顺序进入 Fiat–Shamir transcript。

3. 门约束没有解决 wiring

考虑两行：

第 0 行计算 $c_0=a_0b_0$；
第 1 行计算 $c_1=a_1+7$；
电路希望 $a_1=c_0$。

每行 gate equation 分别成立，不能证明 $a_1$ 与 $c_0$ 是同一个 wire。若不加 copy constraint，prover 可为两格填不同值。

R1CS 常通过同一变量索引表达 wiring；PLONK 把每个 cell 先视作独立位置，再用一个全局 permutation 编码哪些位置属于同一 wire。

flowchart LR
    A0["row 0: a_0"] --> M["乘法门"]
    B0["row 0: b_0"] --> M
    M --> C0["row 0: c_0"]
    C0 -. "copy constraint" .-> A1["row 1: a_1"]
    A1 --> ADD["加常数门"]
    K["7"] --> ADD
    ADD --> C1["row 1: c_1"]

4. 给每个 cell 一个唯一标签

选择 $k_1,k_2\in\mathbb F^*$，使三个 cosets

\[H,\qquad k_1H,\qquad k_2H\]

两两不交。定义 identity polynomials

\[\operatorname{id}_1(X)=X,\qquad \operatorname{id}_2(X)=k_1X,\qquad \operatorname{id}_3(X)=k_2X.\]

于是第 $i$ 行三个 cell 的标签是

\[\omega^i,\qquad k_1\omega^i,\qquad k_2\omega^i.\]

所有 $3n$ 个标签互异。

4.1 wiring permutation

把属于同一逻辑 wire 的 cell 连成 cycle，得到标签集合上的 permutation $\sigma$。例如只要求 $c_0=a_1$，可有二环

\[k_2\omega^0 \;\xleftrightarrow{\ \sigma\ }\; \omega^1.\]

未参与 copy 的位置可为 fixed points。

将 permutation 在三列上的像插值为：

\[\begin{aligned} S_{\sigma,1}(\omega^i)&=\sigma(\omega^i),\\ S_{\sigma,2}(\omega^i)&=\sigma(k_1\omega^i),\\ S_{\sigma,3}(\omega^i)&=\sigma(k_2\omega^i). \end{aligned}\]

这些是 circuit-fixed polynomials，可进入 verification key。

5. 从 copy constraints 到 multiset equality

把所有 cells 统一记为 label $\ell$ 与 value $w_\ell$。copy constraints 意味着

\[w_\ell=w_{\sigma(\ell)} \qquad\forall\ell.\]

采样随机 $\beta,\gamma$，比较两个 multisets：

\[\left\{ w_\ell+\beta\ell+\gamma \right\}_{\ell}\]

与

\[\left\{ w_\ell+\beta\sigma(\ell)+\gamma \right\}_{\ell}.\]

若 value 沿每个 permutation cycle 相同，第二个 multiset 只是第一个重排。故总乘积相同：

\[\prod_\ell (w_\ell+\beta\ell+\gamma) = \prod_\ell (w_\ell+\beta\sigma(\ell)+\gamma).\]

反向上，若 copy constraint 被破坏，随机 $\beta,\gamma$ 让错误 multisets 仍具有相同压缩乘积的概率很小。$\beta$ 把 label 和 value 绑定；$\gamma$ 起随机平移和批处理防退化作用。

6. 三列形式的 numerator 与 denominator

对 $X\in H$，定义 identity-side product

\[\begin{aligned} N(X) ={}& \bigl(A(X)+\beta X+\gamma\bigr)\\ &\cdot \bigl(B(X)+\beta k_1X+\gamma\bigr)\\ &\cdot \bigl(C(X)+\beta k_2X+\gamma\bigr), \end{aligned}\]

和 permutation-side product

\[\begin{aligned} D(X) ={}& \bigl(A(X)+\beta S_{\sigma,1}(X)+\gamma\bigr)\\ &\cdot \bigl(B(X)+\beta S_{\sigma,2}(X)+\gamma\bigr)\\ &\cdot \bigl(C(X)+\beta S_{\sigma,3}(X)+\gamma\bigr). \end{aligned}\]

目标是证明

\[\prod_{x\in H}N(x) = \prod_{x\in H}D(x).\]

直接验证两个大乘积是 $O(n)$。grand product polynomial 把它改写为局部递推。

7. Grand product polynomial $Z(X)$

定义 accumulator：

\[Z(1)=1,\]

并对 $x=\omega^i$ 递推

\[Z(\omega x) =Z(x)\frac{N(x)}{D(x)}.\]

于是

\[Z(\omega^i) = \prod_{j=0}^{i-1} \frac{N(\omega^j)}{D(\omega^j)}.\]

走完一圈：

\[Z(\omega^n)=Z(1)=1\]

当且仅当 numerator/denominator 总乘积闭合。

7.1 不用除法写成约束

协议实际约束

\[P_{\mathrm{perm}}(X) = Z(\omega X)D(X)-Z(X)N(X)\]

在 $H$ 上为零，并约束起点

\[L_0(X)\bigl(Z(X)-1\bigr)=0,\]

其中 $L_0$ 是 $X=1$ 对应的 Lagrange basis。

flowchart LR
    ZI["Z(ω^i)"] --> R["乘 N(ω^i)"]
    DI["除 D(ω^i)"] --> R
    R --> ZN["Z(ω^(i+1))"]
    ZN --> C["走完 n 行回到 Z(1)=1"]

使用 polynomial identity 而非真的在 verifier 中逐行除法，也避免把 “某个 factor 为 0” 直接当未定义。随机 $\beta,\gamma$ 使异常退化事件概率很小；具体 completeness/ZK 处理依实现的 reserved rows 而异。

8. 把 gate 与 permutation 合成一个 vanishing identity

在 witness commitments 绑定后取得 $\beta,\gamma$，构造/承诺 $Z$；再取得随机 $\alpha$，定义简化 numerator：

\[\begin{aligned} P_{\mathrm{all}}(X) ={}&G(X)\\ &+\alpha\,P_{\mathrm{perm}}(X)\\ &+\alpha^2L_0(X)\bigl(Z(X)-1\bigr). \end{aligned}\]

若所有约束成立，

\[Z_H(X)\mid P_{\mathrm{all}}(X).\]

所以存在 quotient

\[t(X)=\frac{P_{\mathrm{all}}(X)}{Z_H(X)}.\]

随后只需在随机点 $\zeta$ 检查

\[P_{\mathrm{all}}(\zeta) \stackrel?= t(\zeta)Z_H(\zeta),\]

并用 PCS 证明所有 evaluations 对应先前 commitments。

8.1 challenge 顺序

sequenceDiagram
    participant P as Prover
    participant T as Transcript
    P->>T: commit A,B,C
    T-->>P: β,γ
    P->>T: commit Z
    T-->>P: α
    P->>T: commit quotient chunks
    T-->>P: ζ
    P->>T: evaluations 与 opening proof

若 $\beta,\gamma$ 在 $A,B,C$ 前产生，prover 可针对压缩随机数选 witness；
若 $\alpha$ 在 $Z$ 前产生，prover 可让 permutation error 与其他约束抵消；
若 $\zeta$ 在 quotient commitment 前产生，prover 可只拟合一个点。

9. Degree 为什么导致 quotient 分块

在无 blinding 的简化三列版本中：

$\deg A,B,C,Z<n$；
$N,D$ 的 degree 最多约 $3(n-1)$；
$Z(\omega X)D(X)$ 最多约 $4(n-1)$；
除以 degree $n$ 的 $Z_H$ 后，$t$ 可能接近 degree $3n$。

如果 PCS/SRS 只高效承诺 degree $<n$ 的 pieces，可写

\[t(X) =t_0(X)+X^nt_1(X)+X^{2n}t_2(X)+\cdots,\]

每个 $t_j$ 次数 $<n$，分别承诺。在随机点：

\[t(\zeta) =t_0(\zeta)+\zeta^nt_1(\zeta) +\zeta^{2n}t_2(\zeta)+\cdots.\]

原始 PLONK 常见 low/mid/high 三块；具体块数会因 blinding degree、custom gate、lookup 与实现 max degree 改变，不能硬编码为“PLONK 永远三个”。

10. permutation soundness 的核心条件

grand product 不是无条件的集合定理。可靠性依赖：

标签唯一：$H,k_1H,k_2H$ 两两不交；
witness 先绑定：$A,B,C$ commitments 早于 $\beta,\gamma$；
permutation 固定：$S_{\sigma,j}$ 来自 circuit key，不能由 prover 临时改；
随机压缩域足够大：错误 multiset 通过随机 identity 的概率可忽略；
起点/闭合被约束：只检查递推而不约束 boundary 会留下自由 scaling；
degree bound 被证明：否则 prover 可提交只在 $H$ 上拟合递推的高次对象。

10.1 为什么必须有 $Z(1)=1$

若 $Z$ 满足递推，则对任意常数 $c$，$cZ$ 也满足同次递推。boundary 消除这个 scaling freedom，并与绕一圈闭合共同绑定总乘积。

11. 一个两格 copy 的微型例子

设 permutation 只有二环

\[\ell_1\leftrightarrow\ell_2\]

而两格值为 $u,v$。对应两边乘积包含：

\[\begin{aligned} L&=(u+\beta\ell_1+\gamma) (v+\beta\ell_2+\gamma),\\ R&=(u+\beta\ell_2+\gamma) (v+\beta\ell_1+\gamma). \end{aligned}\]

相减可因式分解：

\[L-R=\beta(u-v)(\ell_2-\ell_1).\]

标签互异且 $\beta\ne0$ 时，$L=R$ 强制 $u=v$。大 permutation 可视为这个机制的随机多项式推广。

12. 从原始 PLONK 到 PLONKish

现代 PLONKish 一般把电路视为矩阵，列分三类：

fixed columns：selector、常量表、电路结构；
advice columns：prover witness 与辅助值；
instance columns：public input/output。

约束可读取相对 rotation：

\[q(X)\cdot P\bigl( A_0(\omega^{-1}X), A_1(X), A_2(\omega X) \bigr)=0.\]

copy constraints 只对明确启用 equality 的列建立 permutation。lookup 则是另一个 argument。

flowchart TB
    F["fixed columns<br/>selectors / tables"] --> G["custom gate expressions"]
    A["advice columns<br/>witness"] --> G
    I["instance columns<br/>public values"] --> G
    A --> P["equality permutation"]
    F --> L["lookup tables"]
    A --> L
    G --> V["vanishing argument"]
    P --> V
    L --> V

Halo 2 的 regions、chips、floor planner 是构造这张矩阵的工程抽象；底层仍是列多项式、rotation、selector、permutation 和 lookup。

13. Custom gate 的 degree 代价

例如要检查

\[y=x^5,\]

可以：

用若干乘法门和中间 cells，增加 rows；
用一个高次 custom gate，减少 rows 但提高 quotient degree。

这里必须把 selector 也计入 formal degree。若未启用的行靠 selector $q$ 关闭，实际约束是

\[q(X)\bigl(Y(X)-X_{mathrm{wit}}(X)^5\bigr)=0.\]

$Y-X_{mathrm{wit}}^5$ 的 witness-expression degree 是 5，但把 fixed column $q$ 也作为一个多项式 factor 后，完整约束的 formal degree 通常是 6，而不是 5。只有协议用其他机制消去 selector、或该约束在所有行恒启用时，才能按 degree 5 记账。

在单变量 PLONK 中，$d$ 必须定义为乘上所有 selectors 后的完整约束次数。代入 degree $<n$ 的 fixed/witness columns 后，numerator degree 可达约 $d(n-1)$（再按实际常数项和边界项精确计算）。这可能：

增加 quotient chunks；
扩大 SRS degree / FFT domain；
增加 prover MSM 与 FFT。

HyperPlonk 把这一问题移到 multilinear hypercube 与 sumcheck，是后续演进的重要动机。

14. Reserved / blinding rows

理论简化版让 permutation 走完全部 $H$ 并 wrap。实际 ZK PLONKish 系统常保留：

unusable row；
last row selector；
若干 blinding rows。

然后只在 usable rows 启用 gate/permutation recurrence，并单独约束 accumulator 的末端。这样可给 witness columns 填随机盲值。

因此看到实现中的

\[q_{\mathrm{last}},\quad q_{\mathrm{blind}}\]

不要把它们误认为多余优化；它们影响 completeness、ZK 和 boundary semantics。应按该实现 specification 推导，不能混用原始 PLONK 的 wraparound 公式。

15. 本篇与 PCS 无关的部分

到目前为止只得到一个 polynomial IOP：

prover 声称若干 polynomials；
verifier 发送 $\beta,\gamma,\alpha,\zeta$；
最终检查若干 random-point identities。

尚未指定这些 polynomials 如何 commitment/open。因此可选择：

KZG：短 proof、pairing、universal SRS；
IPA：无 structured toxic waste、对数 opening；
FRI/WHIR：透明 hash-based、proof 较大；
其他 multilinear PCS：若先改变 arithmetization/PIOP。

这就是“PLONK 不等于 KZG”的精确原因。

16. 边界与常见陷阱

selector 是否在 padding/unusable rows 正确关闭？
三组 identity labels 是否真正互异？
wiring permutation 是否覆盖每个 equality-enabled cell 且形成双射？
$S_{\sigma,j}$ 是否绑定在 circuit key，而非 prover input？
$\beta,\gamma$ 是否晚于全部 witness commitments？
grand product 是否同时有 recurrence 与正确 boundary/closure？
public inputs 是否进入 gate identity 与 transcript？
quotient degree/chunks 是否包含 permutation、blinding、lookup 的最高次数？
rotation 是否在边界发生意外 wrap，selector 是否关闭？
custom gate 降行数时，是否把 degree/PCS 成本转移算清？

17. 自测

为 $c=a-b$、$a\in{0,1}$ 分别给出 selector 或 custom constraint。
证明 $H,k_1H,k_2H$ 不交时所有 $3n$ 个 cell labels 互异。
推导两格 copy 例子中的 $L-R=\beta(u-v)(\ell_2-\ell_1)$。
从 grand product recurrence 推导总乘积 equality。
为什么只检查 $Z(\omega X)D-ZN=0$ 而没有 $Z(1)=1$ 不够？
一个 degree-7 custom gate 对 quotient degree 有何粗略影响？

参考

上一篇：多项式承诺与 Fiat–Shamir · 下一篇：PLONK 完整协议与 KZG · 返回：总目录

zero-knowledge, stark

本文由作者按照 CC BY 4.0 进行授权