05. PLONK 完整协议：quotient、linearization 与 KZG openings

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

作者 Chen Xichao

12 分钟阅读

说明：本篇以原始三列 PLONK 的简化一致版本推导。论文修订版和工程实现会改变盲化次数、opening aggregation 与 proof layout；这些差异不改变分层逻辑。

1. 公开预处理

给定最大 degree 的 universal KZG SRS：

\[\left(g_1^{\tau^0},\ldots,g_1^{\tau^D}; g_2,g_2^\tau\right).\]

对具体 circuit，公开计算：

domain $H=\langle\omega\rangle$；
selectors $Q_L,Q_R,Q_M,Q_O,Q_C$；
wiring polynomials $S_{\sigma,1},S_{\sigma,2},S_{\sigma,3}$；
public-input layout；
上述 fixed polynomials 的 commitments；
domain size、quotient degree、opening scheme 等元数据。

这些组成 proving key / verification key。circuit-specific key derivation不需要知道 $\tau$。

flowchart LR
    S["universal powers-of-tau SRS"] --> PK["proving key<br/>含 fixed polys / 辅助表"]
    S --> VK["verification key<br/>含 fixed commitments"]
    C["circuit selectors + permutation"] --> PK
    C --> VK

2. witness polynomials 与零知识盲化

prover 先完成电路赋值，插值得到

\[A_0(\omega^i)=a_i,\quad B_0(\omega^i)=b_i,\quad C_0(\omega^i)=c_i.\]

为隐藏随机点 evaluations，取随机低次 masks $r_A,r_B,r_C$：

\[\begin{aligned} A(X)&=A_0(X)+Z_H(X)r_A(X),\\ B(X)&=B_0(X)+Z_H(X)r_B(X),\\ C(X)&=C_0(X)+Z_H(X)r_C(X). \end{aligned}\]

在 $H$ 上取值不变，故 gate/copy semantics 不变；在 $\zeta\notin H$ 上被随机化。

实际协议会规定每个 mask 的精确 degree 与随机标量数，并对 permutation accumulator $Z$、quotient chunks 使用相应 blinding。随机性不足会泄露，多一项则可能越过 SRS degree；不可凭经验随意修改。

3. Round 1：先绑定 witness

prover 发送

\[[A],\quad[B],\quad[C].\]

这里

\[[A]=g_1^{A(\tau)}\]

等。transcript 吸收 VK digest、public input、三个 commitments 后产生

\[\beta,\gamma.\]

现在 prover 不能再针对 permutation compression 改 witness。

4. Round 2：构造 permutation accumulator

在每个 $x=\omega^i$ 计算

\[N(x)= (A(x)+\beta x+\gamma) \cdot(B(x)+\beta k_1x+\gamma) \cdot(C(x)+\beta k_2x+\gamma),\]

并计算

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

由

\[Z(\omega x)=Z(x)\frac{N(x)}{D(x)}, \qquad Z(1)=1\]

得到 $Z$ 在 $H$ 上的 values，再插值并按协议盲化。发送

\[[Z].\]

transcript 随后产生约束合并挑战 $\alpha$。

4.1 工程上的 batch inversion

逐行求 $D(x)^{-1}$ 做 $n$ 次昂贵求逆。常用 Montgomery batch inversion：

计算 prefix products；
对总乘积求一次逆；
反向恢复每个 factor 的逆。

这样把 $n$ 次 inverse 变成一次 inverse + $O(n)$ 次 multiplication。它只优化 honest prover，不改变 polynomial identity。

5. Round 3：在扩展 coset 上构造 quotient

定义简化的约束 numerator：

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

合法 witness 保证

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

所以

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

5.1 prover 不在 $H$ 上做这个除法

在 $H$ 上 $Z_H=0$。prover 选择 disjoint enlarged coset $D_{\mathrm{quot}}$：

把 witness/fixed/accumulator polynomials FFT-evaluate 到 $D_{\mathrm{quot}}$；
逐点计算 $P_{\mathrm{all}}(x)$；
逐点除以非零的 $Z_H(x)$；
IFFT 得到 $t$ 的系数，或保持合适点值表示用于分块/承诺。

flowchart TB
    H["H 上 witness values"] --> I["IFFT 得到系数"]
    I --> E["在 quotient coset 上 FFT"]
    F["fixed polynomials"] --> E
    E --> N["逐点算 P_all(x)"]
    N --> D["除以 Z_H(x)"]
    D --> T["quotient t(X)"]

6. quotient 分块

若 $\deg t<kn$，写成

\[t(X)= t_0(X)+X^nt_1(X)+\cdots+X^{(k-1)n}t_{k-1}(X),\]

其中 $\deg t_j<n$。prover 发送

\[[t_0],\ldots,[t_{k-1}].\]

transcript 产生 evaluation challenge

\[\zeta\leftarrow\mathbb F,\qquad \zeta\notin H\]

（实际由 hash-to-field 取得，落到禁用集合时按规范处理）。

随机点上的完整 quotient value 可重组：

\[t(\zeta)= \sum_{j=0}^{k-1} \zeta^{jn}t_j(\zeta).\]

7. 随机点需要哪些 evaluations

约束中出现两类点：

当前点 $\zeta$：$A,B,C,Z$、selectors、permutation polynomials、quotient chunks；
rotated point $\omega\zeta$：至少有 $Z(\omega\zeta)$。

若 custom gates 使用更多 rotations，还会出现 $\omega^r\zeta$。lookup 也会增加 opening sets。

最直接的方案是把所有多项式逐一打开，但 proof 太大。PLONK 用两层压缩：

linearization：把非线性 constraint 在已声称的 scalar evaluations 处线性化；
random batching：把同一点的多个 polynomial openings 合成一个。

8. Linearization polynomial

在 $\zeta$，prover 声称

\[a=A(\zeta),\quad b=B(\zeta),\quad c=C(\zeta),\]

以及

\[s_1=S_{\sigma,1}(\zeta),\quad s_2=S_{\sigma,2}(\zeta),\quad z_\omega=Z(\omega\zeta).\]

8.1 gate 部分

把 witness evaluations 当 scalar，gate expression 对 fixed selector polynomials 变成线性：

\[R_{\mathrm{gate}}(X) = aQ_L(X)+bQ_R(X)+abQ_M(X) +cQ_O(X)+Q_C(X).\]

它在 $X=\zeta$ 恰等于 gate expression。

8.2 permutation 部分

令

\[n_\zeta= (a+\beta\zeta+\gamma) \cdot(b+\beta k_1\zeta+\gamma) \cdot(c+\beta k_2\zeta+\gamma).\]

把 $S_{\sigma,1},S_{\sigma,2}$ 的 evaluations 固定后，

\[\begin{aligned} R_{\mathrm{perm}}(X) ={}& z_\omega \cdot(a+\beta s_1+\gamma) \cdot(b+\beta s_2+\gamma)\\ &\cdot(c+\beta S_{\sigma,3}(X)+\gamma) -Z(X)n_\zeta. \end{aligned}\]

它对尚未 evaluation 的 $S_{\sigma,3}(X)$ 和 $Z(X)$ 都是线性的。

8.3 quotient 与 boundary

再加入

\[\alpha^2L_0(\zeta)(Z(X)-1)\]

和

\[-Z_H(\zeta) \sum_j\zeta^{jn}t_j(X).\]

得到 schematic linearization polynomial

\[R(X) =R_{\mathrm{gate}}(X) +\alpha R_{\mathrm{perm}}(X) +\alpha^2L_0(\zeta)(Z(X)-1) -Z_H(\zeta)\sum_j\zeta^{jn}t_j(X) +PI(\zeta).\]

合法 proof 要求

\[R(\zeta)=0.\]

8.4 为什么 verifier 无需新 commitment

KZG 线性同态：

\[[uF+vG]=[F]^u[G]^v\]

（乘法群记法）。verifier 已有 fixed commitments、$[Z]$ 和 $[t_j]$，可用公开 scalars 直接组合出 $[R]$。linearization 因而把大量 fixed-polynomial openings 压成一个派生 commitment。

上述公式刻意展示结构而不规定某一版 proof encoding。不同 PLONK 版本会把常数项移到 claimed evaluation、改变正负号或使用不同 linearization set；实现必须与其 specification 完全一致。

9. 同点 random batching

设在 $\zeta$ 需打开 polynomial 列表

\[F_0,\ldots,F_{m-1}\]

及声称值 $y_i=F_i(\zeta)$。在全部 evaluations 进入 transcript 后采样 $v$：

\[F_\zeta(X) =\sum_{i=0}^{m-1}v^iF_i(X), \qquad y_\zeta =\sum_{i=0}^{m-1}v^iy_i.\]

生成一个 KZG quotient：

\[W_\zeta(X) =\frac{F_\zeta(X)-y_\zeta}{X-\zeta}, \qquad \pi_\zeta=[W_\zeta].\]

对 $\omega\zeta$ 的 opening set 同样得到 $\pi_{\omega\zeta}$。

10. 两点 KZG pairing 检查

分别检查：

\[e\left( [F_\zeta]/g_1^{y_\zeta},g_2 \right) \stackrel?= e\left( \pi_\zeta, g_2^\tau/g_2^\zeta \right),\]

以及 rotated point 的对应式。

先把两个 opening-proof 群元素 $\pi_\zeta,\pi_{\omega\zeta}$ 都吸收进 transcript，再取得随机 $u$，可把两条等式放进一个 pairing product check：

\[\begin{aligned} e(& ([F_\zeta]/g_1^{y_\zeta}) \cdot ([F_{\omega\zeta}]/g_1^{y_{\omega\zeta}})^u, g_2)\\ \stackrel?={}& e(\pi_\zeta,g_2^\tau/g_2^\zeta) \cdot e(\pi_{\omega\zeta}^{\,u}, g_2^\tau/g_2^{\omega\zeta}). \end{aligned}\]

这不是把不同点粗暴当成同一点；右侧仍保留各自 $\tau-z$ factor。$u$ 不能在第二个 opening proof 之前采样，否则 prover 可在看到权重后选择 $\pi_{\omega\zeta}$，破坏“随机合并两条已固定 pairing claims”的归约前提。

11. 完整 transcript 总览

sequenceDiagram
    participant P as Prover
    participant T as Fiat-Shamir Transcript
    participant V as Verifier
    P->>T: VK digest + public inputs
    P->>T: [A],[B],[C]
    T-->>P: β,γ
    P->>T: [Z]
    T-->>P: α
    P->>T: [t_0]...[t_k]
    T-->>P: ζ
    P->>T: evaluations at ζ and ωζ
    T-->>P: batching challenge v
    P->>T: opening proofs at ζ and ωζ
    T-->>P: two-point challenge u
    P->>V: serialized proof
    V->>V: 重放 transcript、检查 identity 与 pairings

上图采用原始 PLONK Round 5 的依赖关系：先输出并绑定 $([W_\zeta],[W_{\omega\zeta}])$，再令 $u=H(\mathrm{transcript})$。某些 multi-opening 协议会使用不同 proof layout、只发送一个最终 proof，或先发送辅助 commitment；此时必须逐项遵守相应 specification。普遍原则仍是：每个 batching challenge 必须晚于它所压缩的全部 claims。

12. verifier 的逻辑分成两层

12.1 Scalar identity

用 proof 中的 evaluations 重算：

\[R(\zeta)\stackrel?=0\]

或等价 quotient identity。这一步证明“如果这些 evaluations 真实，它们满足电路约束”。

12.2 PCS consistency

用 KZG pairings 检查所有 batched evaluations 确实来自已承诺 polynomials。这一步证明“这些标量不是 prover 临时编的”。

flowchart TB
    E["claimed evaluations"] --> S["scalar PLONK identity"]
    C["commitments"] --> K["KZG batch openings"]
    E --> K
    S --> A["约束成立"]
    K --> B["evaluations 真实"]
    A --> OK["接受"]
    B --> OK

任一层缺失都能作弊：

只有 KZG：证明了一些真实 evaluations，但没证明它们满足 circuit；
只有 scalar identity：可随意捏造一组满足单点等式的 scalars。

13. prover 成本来自哪里

对 $n$ 行电路，典型瓶颈：

多次 size-$n$ 或 larger coset FFT/IFFT；
对 witness、accumulator、quotient chunks 做 KZG MSM；
grand product 的逐行 field work 与 batch inversion；
custom gates / lookups 的 extended-domain evaluation；
内存保存多列点值与系数表示。

原始论文的优势之一是 universal setup 与较低 group-exponentiation 开销。现代硬件上 FFT、MSM、memory bandwidth 谁占主导，取决于 curve、circuit size、并行度和是否有 GPU。

14. verifier 与 proof size 不是 PLONK 的固定常数

原始三列 KZG-PLONK 通常只有常数个 commitments、evaluations 和 opening proofs；但具体字节数随：

curve point / scalar 编码；
quotient chunks；
advice/fixed/instance query 数；
rotations；
permutation column sets；
lookup arguments；
multi-opening protocol；
是否 batch 多 instances；

变化。Halo 2、UltraPLONK、Kimchi 的 proof layout 不应套用原始 PLONK 的元素计数。

15. 换成 IPA 或 FRI 后什么不变

不变：

witness table；
selector/custom gate semantics；
permutation grand product 的核心思想；
quotient/vanishing identity；
Fiat–Shamir 的 challenge dependency。

改变：

commitment 表示；
degree proof；
opening aggregation；
transcript rounds；
proof size/verifier cost；
trusted setup 与量子假设；
recursion 的 field/curve/hash 成本。

例如：

Halo 2：PLONKish + IPA-style commitment/multi-opening；
Plonky2：PLONKish ideas + FRI-based commitment；
HyperPlonk：连 polynomial space 与 PIOP 都换成 multilinear + sumcheck，已不只是“换 PCS”。

16. KZG 特有的安全边界

SRS ceremony 与 contribution verification 是否正确？
SRS degree 是否覆盖盲化后的所有 polynomials？
verifier 是否拒绝非规范、非曲线、非正确 subgroup 的点？
pairing product 是否包含所有 opening claims，随机 batch scalar 是否绑定完整列表？
常数 polynomial commitment、point at infinity 等边界是否按规范处理？
prover/verifier 是否对同一 curve scalar field 做 polynomial arithmetic？
toxic waste 泄露后的处置策略是什么？
安全证明使用的 knowledge/degree-binding 假设与部署模型是否匹配？

17. 通用 PLONK 审计边界

public input/VK/protocol version 是否进入 transcript？
challenge 顺序是否与依赖图一致？
quotient coset 是否与 $H$ 分离，$Z_H(x)$ 是否永不为零？
quotient chunks 重组的 $\zeta^{jn}$ powers 是否正确？
linearization 正负号、$\alpha$ powers、rotation evaluations 是否完全匹配 prover？
未打开的 polynomial 是否真的只线性出现在 $R(X)$？
batching list 的顺序、重复项和长度是否 canonical？
reserved/blinding rows 对 gate、permutation、lookup 是否一致关闭？
mask degree 是否同时满足 ZK 与 SRS/quotient bounds？
proof parser 是否拒绝 trailing/ambiguous encodings？

18. 自测

为什么 quotient 必须在 disjoint coset 上逐点除？
推导 $t(\zeta)=\sum_j\zeta^{jn}t_j(\zeta)$。
解释 linearization 如何利用 KZG commitment 的线性同态。
为什么 permutation 中通常可只打开 $S_{\sigma,1},S_{\sigma,2}$，把 $S_{\sigma,3}(X)$ 留在线性化多项式中？
写出两个多项式在同一点的 batched KZG opening。
为什么不同点的两个 opening 不能只把 commitments 相加后用同一个 $\tau-\zeta$ 检查？

参考

Gabizon、Williamson、Ciobotaru，PLONK
Kate、Zaverucha、Goldberg，Polynomial Commitments
Halo 2 Book：Vanishing Argument
Halo 2 Book：Multipoint Opening Argument
Halo 2 Book：Polynomial Commitment via IPA

上一篇：PLONK 算术化 · 下一篇：PLONKish 自定义门与 lookup · 返回：总目录

zero-knowledge, stark

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