PlonK — Universal Setup + Custom Gates

日期: 2026-12-03 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #PlonK #SNARK #PIOP #Lookup

---

今日目标

---

一、PlonK 的革命

PlonK = Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

---

二、Plonkish Arithmetization

2.1 Trace 表

整个电路视为 $n$ 行 × 多列的表（"execution trace"），列分为：

• Wire columns：$a, b, c$（每 gate 的左输入、右输入、输出）
• Selector columns：$q_L, q_R, q_O, q_M, q_C$（gate 的常数系数，区分 + 还是 ×）

2.2 通用 Gate 等式

每行满足：

$$ q_L(X) a(X) + q_R(X) b(X) + q_O(X) c(X) + q_M(X) a(X) b(X) + q_C(X) = 0 $$

通过设置 selectors，单行可表达：

2.3 Custom Gates

PlonK 标准 gate 限于 deg-2，但可以扩展加 selector $q_{\text{custom}}$ 和高阶项，例如：

• Boolean check $q_{\text{bool}}(X) \cdot a(X) (a(X) - 1) = 0$
• XOR table lookup（plookup gate）
• Poseidon round（高 deg gate, 一次 round 一行）

zkSync Era 的 boojum 框架定义了几十个 custom gates。

2.4 Copy Constraints (Permutation Argument)

电路中 wire 在不同位置出现需要"相等"。例：第 5 行 $a$ = 第 17 行 $b$（同一信号）。

PlonK 用 grand product argument 表达：定义置换 $\sigma$，证明 $z(X) := \prod \frac{(a + \beta x + \gamma)(b + \beta k_1 x + \gamma)(c + \beta k_2 x + \gamma)}{(a + \beta \sigma_1 + \gamma)(b + \beta \sigma_2 + \gamma)(c + \beta \sigma_3 + \gamma)} = 1$ at $X = \omega^n$。

直觉：累乘比值要等于 1 ⟺ "重排前后两个集合相等"⟺ permutation 正确。

---

三、PlonK 协议（核心步骤）

3.1 公共参数

• 群 $G_1, G_2$，pairing $e$
• 阶 $r$ 的 unity roots $\omega$
• KZG SRS：${[\tau^i]1}{i=0}^{N}, [\tau]_2$（universal，与具体电路无关）

3.2 Setup (per-circuit, lightweight)

输入：电路（selectors $q_L, ..., q_C$ 和 permutation $\sigma$）。

输出：

• vk: $[q_L]_1, [q_R]_1, [q_O]_1, [q_M]_1, [q_C]_1, [\sigma_1]_1, [\sigma_2]_1, [\sigma_3]_1, [x]_2$
• pk: 上述多项式的明文系数

3.3 Prover

Round 1：对 wire columns 插值得 $a(X), b(X), c(X)$，commit：$[a]_1, [b]_1, [c]_1$。

Round 2：FS 得 challenge $\beta, \gamma$。计算 grand product accumulator $z(X)$，commit：$[z]_1$。

Round 3：FS 得 challenge $\alpha$。计算 quotient polynomial $t(X)$ 满足： $$ t(X) Z_H(X) = \text{gate}(X) + \alpha \cdot \text{perm}1(X) + \alpha^2 \cdot \text{perm}2(X) $$ 其中 $Z_H(X) = X^n - 1$（vanishing on subgroup $H$）。把 $t$ 拆 3 段（避 deg 超过 SRS）：$t{lo}, t{mid}, t_{hi}$。Commit。

Round 4：FS 得 evaluation point $\zeta$。计算 $a(\zeta), b(\zeta), c(\zeta), \sigma_1(\zeta), \sigma_2(\zeta), z(\zeta\omega)$ 等。

Round 5：FS 得 $v$。聚合所有 evaluation 为 single linearization poly $r(X)$，用 KZG 一次 batch open。

Proof = 9 group elements + several field elements： $$ \pi = ([a]_1, [b]_1, [c]_1, [z]1, [t{lo}]1, [t{mid}]1, [t{hi}]1, [W\zeta]1, [W{\zeta\omega}]_1) $$

• field evals。

总 size ≈ ~400 bytes（依 curve）。

3.4 Verifier

1. 重算 challenges $\beta, \gamma, \alpha, \zeta, v, u$（FS）
2. 重建 linearization commitment $[D]_1$（用 vk 中的 selector commitments）
3. 检查 batch KZG opening：1-2 pairings

Verifier 总 cost：~6 pairings + few muls ≈ ~10 ms。

---

四、KZG Polynomial Commitment

PlonK 用 KZG（Kate-Zaverucha-Goldberg 2010）：

• Commit $[f]_1 = \sum f_i [\tau^i]_1 = [f(\tau)]_1$（$f(\tau)$ 在 exponent）
• Open at $z$: prover 计算 $q(X) = (f(X) - f(z))/(X - z)$，发送 $[q]_1$
• Verifier check: $e([f]_1 - f(z)\cdot [1]_1, [1]_2) = e([q]_1, [\tau - z]_2)$

→ commit/open 都在 $O(N)$；verify 1-2 pairings。

支持 batch opening：多个 $f_i$ 在同一点 $z$ 用 random combo $\sum v^i f_i$ 合并成一个 KZG opening。

---

五、plookup — Lookup Argument

5.1 问题

证明 ${a_i} \subseteq T$（一个表，例如 SBox / range table ${0, ..., 2^8 - 1}$）。直接约束需要 $2^8$ 行 + branch — 巨大。

5.2 plookup 思路 (Gabizon-Williamson 2020)

定义辅助序列 $s = \text{sort}({a_i} \cup T)$（含 $a$ 与 $T$ 排序后），grand product 论证：

$$ \prod_i (1 + \beta) (\gamma + a_i) (\gamma + t_i (1 + \beta)) = \prod_i (\gamma(1+\beta) + s_i + \beta s_{i+1}) \cdot ??? $$

精确公式见原论文 (ePrint 2020/315)。核心是一种 multiset equality argument。

5.3 用途

• SHA-256 / Keccak round（用 8-bit XOR table）
• ECDSA / Schnorr verify（point doubling table）
• Range check（$0 \leq x < 2^k$）

→ 让一次 hash 从数千约束降到 ~100 约束。

---

六、PlonK vs Groth16 对比

---

七、协议关系图

   Universal SRS  ←─── one-time MPC (Powers of Tau)
        │
        │ + circuit (selectors, permutation)
        ▼
   ┌─────────┐                         ┌─────────┐
   │   pk    │                         │   vk    │
   └────┬────┘                         └────┬────┘
        │                                    │
   prover (witness)                    verifier (public input)
        │                                    │
   IOP rounds:                               │
    1. wire commits  [a],[b],[c]             │
    2. FS β,γ                                │
    3. permut commit [z]                     │
    4. FS α                                  │
    5. quotient commits [t_lo],[t_mid],[t_hi]│
    6. FS ζ                                  │
    7. evals + opening proofs                │
        │                                    │
        ▼                                    ▼
   π ≈ 9 G1 + few F  ─── ~400 B ─────▶  6 pairings, output 0/1

---

八、代码 — KZG Commitment 框架

"""
plonk_kzg.py — KZG commitment 教学伪代码
真实实现见 arkworks-rs / barretenberg
"""

class KZG:
    def __init__(self, srs):
        # srs = {[tau^i]_1 for i=0..N}, [tau]_2
        self.srs = srs

    def commit(self, poly):
        # [f]_1 = Σ f_i · [tau^i]_1
        return sum(c * pt for c, pt in zip(poly.coeffs, self.srs.g1_powers))

    def open(self, poly, z):
        f_z = poly.eval(z)
        # q(X) = (f(X) - f(z)) / (X - z)
        q = (poly - Polynomial.constant(f_z)).div_linear(z)
        proof = self.commit(q)
        return f_z, proof

    def verify(self, commitment, z, f_z, proof):
        # e([f]_1 - f(z)·[1]_1, [1]_2) == e([q]_1, [tau - z]_2)
        lhs = pairing(commitment - f_z * G1, G2)
        rhs = pairing(proof, self.srs.g2_tau - z * G2)
        return lhs == rhs

    def batch_open(self, polys, z, v):
        # 多个 poly 在同一 z 处 opening
        # F(X) = Σ v^i f_i(X), f_z's accordingly
        F = sum(v**i * p for i, p in enumerate(polys))
        F_z = sum(v**i * p.eval(z) for i, p in enumerate(polys))
        return self.open(F, z)

---

九、历史与论文

---

十、应用对应

---

十一、常见陷阱

1. Universal SRS 只解决 Phase 1：每电路仍要做 selector commitment（不需 ceremony，但要 deterministic）
2. KZG SRS 大小限制：SRS 上限 $N$ → 电路约束数受限。Powers of Tau 当前到 $2^{28}$ ≈ 256M
3. Custom gate 设计陷阱：deg 太高让 quotient poly $t$ 拆段过多，prover 慢
4. plookup table 过大：lookup 列长度 ≈ table 大小 + 用量；SHA256 表 ~$2^{32}$ 不可行 → 分段 lookup
5. FS 实现陷阱：所有 commit/eval 必须按 spec 顺序进 transcript（Frozen Heart 攻击）
6. 公开输入位置：vk 必须固定 PI 在某些 row；prover/verifier 一致

---

十二、关键速查

---

十三、面试题

Q1: PlonK 相对 Groth16 的核心创新？

A1: (1) Universal SRS：一次 ceremony 通用所有电路，新电路无需新 ceremony；(2) Custom gates：一行可表达复杂多项式约束（不限于 rank-1 quadratic），表达力强；(3) plookup：$O(1)$ 的 lookup table 让哈希等"非线性"操作高效；(4) Permutation argument 替代 wire equality（grand product accumulator）。

Q2: PlonK 中 grand product 论证的直觉？

A2: 累乘 $\prod_i \frac{(a_i + \beta\sigma_i + \gamma)}{(a_i + \beta i + \gamma)} = 1$ at end iff ${a_i}$ 与 ${a_{\sigma(i)}}$ 是同一 multiset 的重排。这给出"两个 wire 必须相等"的约束 — 因为重排后形式上要满足等式。

Q3: KZG 为什么需要 trusted setup？

A3: KZG SRS = ${[\tau^i]_1}$，knowledge of $\tau$ = 任意伪造 commitment（可让任意 poly commit 到特定值）。所以 $\tau$ 必须 toxic。但 SRS 通用所有电路 → 一次 MPC 永久使用，远比 Groth16 per-circuit 友好。

Q4: PlonK 的 quotient polynomial 为什么要分段？

A4: $t(X) = \text{stuff}(X) / Z_H(X)$，deg 可达 $3n$（gate deg 2 × wire + perm deg）。SRS 上限 $N$，所以拆 $t = t_{lo} + X^n t_{mid} + X^{2n} t_{hi}$，每段 deg < $n$，分别 commit。Verifier 重组时要做 degree shift。

Q5: plookup 如何降低 SHA256 电路大小？

A5: SHA256 一轮包含若干 8-bit XOR / AND。用 plookup 表 $T = {(a, b, a \oplus b): 0 \leq a, b < 256}$，每次 lookup 1 行约束 + 共享 table cost。原本每个 XOR ~32 bit-ops × R1CS 行；plookup 后每 XOR ~3 行。SHA256 单次从 ~25K 约束降到 ~5K。

---

十四、明日预告

Day 217 — Halo2：no-trusted-setup + IPA + 自定义 gate + recursion-friendly。zkSync / Scroll 的核心。