论文精读 #2 — PlonK

日期: 2027-01-21 方向: 零知识证明 / 论文精读 阶段: Phase 4 - 密码学工程 (Day 264-267 论文精读系列) 标签: #ZK #PlonK #paper-reading #universal-setup #permutation-argument

---

今日目标

---

〇、为什么要"精读" PlonK？

PlonK 是 Groth16 之后最被广泛部署的 SNARK：Aztec V2/V3、Polygon zkEVM (Hermez)、Mina (Halo2 也是 PlonKish 派系)、zkSync Era 内部、Scroll 内部、Espresso、Penumbra、ZkBNB……几乎现代每一个高 throughput zkRollup 都基于 PlonK 或其变体（Plonky2、Halo2、Honk）。

而 Groth16 的两大痛点——circuit-specific setup 和 不支持 lookup——正是 PlonK 直接攻克的目标。

精读到位的指标：

• 不看论文能写出 PlonK 的 5 类 gate identity（add/mul/const/output 选择子方程）。
• 不看论文能解释 "permutation argument via grand product $Z(X)$"。
• 能讲清 quotient polynomial $t(X)$ 是怎么把多个约束打包到一个多项式 identity 的。
• 能在 30 分钟内讲完 prover / verifier 流程。

---

一、论文基本信息

取名彩蛋：作者承认论文标题是"硬凑出来的"——"Oecumenical" (oikoumene-: 普世的) 是为了凸显 universal setup。"Lagrange-bases" 是技术核心。整体呈现"虽然技术名字花哨但论文很实用"的定位。

---

二、历史定位 — 在 SNARK 演化树上的坐标

2.1 universal setup 演化路线

Groth16'16 (circuit-specific setup) -- 痛点：每电路一次 ceremony
            │
            ▼
Sonic'19 (Maller et al.) — 第一个 universal updatable，但效率不高
            │
            ├──► PlonK'19 (今日精读) — 高效 universal + 简洁 IR
            │           │
            │           ├──► UltraPlonk (Aztec) — 加 lookup
            │           ├──► plookup'20 — lookup argument
            │           ├──► Halo2 (Zcash, 2020) — Plonkish + IPA + recursion
            │           ├──► Plonky2 (Mir, 2022) — Plonkish + FRI + recursion
            │           └──► Honk (Aztec, 2024) — sumcheck-based PlonK
            │
            ▼
Marlin'19 (Chiesa et al.) — universal AHP framework

2.2 与 Sonic 的差异

2.3 为什么 PlonK 在 2020-2026 大爆发？

1. Universal setup：一次 Powers of Tau 全行业共享，省下数百次 ceremony。
2. Updatable：新参与者可以加进 ceremony 增强信任，旧 CRS 不作废。
3. Custom gates 友好：自定义 gate 只是在 selector polynomial 加一项，开发者门槛低。
4. 可加 lookup：plookup/Halo2-lookup 直接接入。
5. Recursion 友好：Halo2 / Plonky2 都基于 Plonkish。

---

三、核心贡献 — 三句话版本

PlonK 的核心是把电路约束化为：

1. gate identity: $q_L \cdot a + q_R \cdot b + q_O \cdot c + q_M \cdot ab + q_C = 0$（5 个 selector 描述电路结构）
2. permutation identity: 用 grand product polynomial $Z(X)$ 证明 wire 之间的 copy constraint
3. quotient polynomial $t(X)$: 把上述所有约束打包成 1 个多项式 identity，KZG commit 后用 1 次开点验证

由此实现 universal setup（CRS 只依赖 $n$ 不依赖电路）+ 通用 IR（PlonKish）。

---

四、逐节精读

4.1 Section 1: Introduction & Overview

PlonK 论文 Intro 给出了三个动机：

"We obtain efficient SNARKs with universal and updatable structured reference string."

第一段提出关键观察：只要把所有约束转成 polynomial identity over a multiplicative subgroup，就可以用 KZG commitment 实现 universal setup。

Section 1 的对比表（论文 Table 1）：

PlonK 在三项里都最佳，特别是 prover G operations。

4.2 Section 2: Preliminaries

4.2.1 KZG Polynomial Commitment

KZG (Kate-Zaverucha-Goldberg 2010) 是 PlonK 的基础原语：

Setup: 选 trapdoor $\tau$，CRS = ${[1]_1, [\tau]_1, [\tau^2]_1, \dots, [\tau^d]_1, [\tau]_2}$。

Commit $f(X)$: $[f(\tau)]_1 = \sum f_i \cdot [\tau^i]_1$。

Open $f(z) = y$: 计算 $q(X) = (f(X) - y) / (X - z)$，输出 $\pi = [q(\tau)]_1$。

Verify: $e(\pi, [\tau - z]_2) \stackrel{?}{=} e([f(\tau)]_1 - [y]_1, [1]_2)$

这是 universal & updatable 的 commitment——CRS 只依赖最大次数 $d$，不依赖具体电路。

4.2.2 Lagrange Basis & Roots of Unity

PlonK 工作在 multiplicative subgroup $H = {1, \omega, \omega^2, \dots, \omega^{n-1}}$ 上，$\omega$ 是 $n$-th root of unity。

Lagrange basis：$L_i(X)$ 满足 $L_i(\omega^j) = \delta_{ij}$。

任意函数 $f: H \to \mathbb{F}$ 可以唯一插值为 $f(X) = \sum_{i=0}^{n-1} f(\omega^i) L_i(X)$。

Vanishing polynomial: $Z_H(X) = X^n - 1$，在 $H$ 的每个点都为 0。

4.3 Section 3: Constraint System — Plonkish IR

4.3.1 算术电路的"Plonkish 化"

每一行（每个 gate）有 3 个 wire：left $a$, right $b$, output $c$，加上 5 个 selector：

$$ 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) \stackrel{!}{=} 0 \quad \text{on } H $$

即在 $H$ 的每个点 $\omega^i$ 都成立：

$$ q_L(\omega^i) a(\omega^i) + q_R(\omega^i) b(\omega^i) + q_O(\omega^i) c(\omega^i) + q_M(\omega^i) a(\omega^i) b(\omega^i) + q_C(\omega^i) = 0 $$

5 种基础 gate 模板：

严格说 PlonK 原论文只提了 add/mul/const，但工业界（Aztec / Halo2）很快加入更多 custom gates（如 SHA256 round, ECC point addition, range check）。

4.3.2 Copy Constraint — 为什么需要 Permutation Argument？

电路里同一个 signal 可能被多个 gate 用到（e.g., output of gate-1 是 input of gate-3）。怎么强制 $a_3 = c_1$？

朴素办法：复制 wire 值，但因为 $a, b, c$ 是独立的多项式，没有内置约束。

PlonK 的办法：定义一个 permutation $\sigma: [3n] \to [3n]$，把所有应该相等的 wire position 连成 cycle。然后用 grand product argument 证明 $(a, b, c)$ 在 $\sigma$ 下是自身的 permutation。

4.4 Section 5 (在论文中) — Permutation Argument

这是 PlonK 论文最 elegant 的部分。

4.4.1 Grand Product Polynomial

设有两个序列 ${f_i}, {g_i}$，要证明 $g$ 是 $f$ 的 permutation。

定理（已是经典）: ${f_i} = {g_i}$ as multisets $\iff$ $\prod_i (X - f_i) = \prod_i (X - g_i)$ as polynomials in $X$。

降维到一个 challenge $\beta$: $\prod_i (\beta + f_i) = \prod_i (\beta + g_i)$ 以高概率成立 iff multisets 相等。

PlonK 用此原理：

1. 把 $a, b, c$ 三个 wire 拼成一个长 $3n$ 序列 $f$。
2. 应用 $\sigma$ 得到 $g$。
3. 证明 $\prod (\beta + f_i + \gamma \cdot \text{position}_i) = \prod (\beta + g_i + \gamma \cdot \text{position}_i)$（用两个 challenge $\beta, \gamma$ 增强 soundness）。

4.4.2 Z(X) 的递推定义

定义 grand product polynomial $Z(X)$，在 $H$ 上递推：

$$ Z(\omega^0) = 1, \quad Z(\omega^{i+1}) = Z(\omega^i) \cdot \frac{(a_i + \beta \omega^i + \gamma)(b_i + \beta k_1 \omega^i + \gamma)(c_i + \beta k_2 \omega^i + \gamma)}{(a_i + \beta \sigma_a(i) + \gamma)(b_i + \beta \sigma_b(i) + \gamma)(c_i + \beta \sigma_c(i) + \gamma)} $$

其中 $k_1, k_2$ 是 coset shift（保证 $\omega^i, k_1 \omega^i, k_2 \omega^i$ 三组不重叠），$\sigma_a, \sigma_b, \sigma_c$ 是 $\sigma$ 在 $a, b, c$ 三段上的值。

正确性：如果 wire 满足 copy constraint，则 $Z(\omega^n) = Z(\omega^0) = 1$（环回起点）；否则不会闭合。

编码成 polynomial identity： $$ \begin{aligned} &Z(X) \cdot \prod_{w\in{a,b,c}} (w(X) + \beta \cdot \text{id}w(X) + \gamma) \ &= Z(X \omega) \cdot \prod{w\in{a,b,c}} (w(X) + \beta \cdot \sigma_w(X) + \gamma) \quad \text{on } H \setminus {\omega^{n-1}} \end{aligned} $$

加上边界条件 $Z(\omega^0) = 1$。

4.5 Section 5/6: Quotient Polynomial $t(X)$

PlonK 把上述所有约束（gate identity + permutation identity + boundary）合并为一个多项式 identity。

4.5.1 拆分成 4 个子约束

4.5.2 用 challenge $\alpha$ 线性合并

引入 random challenge $\alpha$，定义：

$$ T(X) = \text{(gate identity)} + \alpha \cdot \text{(perm step)} + \alpha^2 \cdot \text{(perm init)} $$

要求：$T(X) \equiv 0 \pmod{Z_H(X)}$，即 $T(X) = t(X) \cdot Z_H(X)$。

Prover 计算 $t(X) = T(X) / Z_H(X)$（degree 约 $3n$），把它拆成 3 段 $t_{lo}, t_{mid}, t_{hi}$（每段 degree < $n$）以 commit。

4.6 Section 7: Prover & Verifier

4.6.1 Prover 算法（5 round + Fiat-Shamir）

Round 1: prover 计算 a(X), b(X), c(X) 多项式，commit [a]_1, [b]_1, [c]_1
Round 2: 接收 challenge β, γ；计算 Z(X)，commit [Z]_1
Round 3: 接收 challenge α；计算 t(X) 并拆分成 t_lo, t_mid, t_hi，
         commit [t_lo]_1, [t_mid]_1, [t_hi]_1
Round 4: 接收 challenge ζ；计算开点
         a(ζ), b(ζ), c(ζ), Z(ζω), σ_a(ζ), σ_b(ζ), t(ζ)
Round 5: 接收 challenge v；构造 KZG opening proofs W_ζ(X), W_{ζω}(X)
         commit [W_ζ]_1, [W_{ζω}]_1

所有 challenge 用 Fiat-Shamir 从 transcript hash 派生（论文 Section 7 假定 random oracle）。

4.6.2 Proof 结构

最终 proof 大小：

$$ \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, \ \quad a(\zeta), b(\zeta), c(\zeta), Z(\zeta\omega), \sigma_a(\zeta), \sigma_b(\zeta), t(\zeta)) $$

9 个 G1 element + 7 个 field element。

BLS12-381 上：

• 9 × 48 = 432 bytes (G1)
• 7 × 32 = 224 bytes (Fr)
• 总 656 bytes（实际可以通过 batching 压到 ~480 bytes）

4.6.3 Verifier 算法

Verifier 检查：

1. 重新派生所有 challenges $(\beta, \gamma, \alpha, \zeta, v, u)$。
2. 计算 lagrange evaluation $L_0(\zeta)$, vanishing $Z_H(\zeta) = \zeta^n - 1$。
3. 核心 KZG batched verify：

$$ e\left([W_\zeta]1 + u [W{\zeta\omega}]_1, [\tau]2\right) \stackrel{?}{=} e\left(\zeta [W\zeta]1 + u\zeta\omega [W{\zeta\omega}]_1 + [F]_1 - [E]_1, [1]_2\right) $$

其中 $[F]_1$ 和 $[E]_1$ 是从 commitment 和 evaluation 重组的复合表达。

总开销：2 个 pairing + 约 18 次 G1 scalar mul + 多次 Fr 算术。

4.7 Section 8: 安全性

PlonK 在 AGM (Algebraic Group Model) 下证明 knowledge soundness。AGM 比 GGM 弱：允许 adversary 看到 group elements 的 algebraic 表达，但要求每个输出元素都伴随其线性组合 representation。

KZG 已被证明在 AGM + DLOG 下 binding。Permutation argument 的 soundness 来自 Schwartz-Zippel：

$$ \Pr[\text{multiset 不同但 polynomial identity 在随机 } \beta \text{ 处成立}] \le \frac{n}{|\mathbb{F}|} $$

对 BN254/BLS12-381（$|\mathbb{F}| \approx 2^{255}$），$n \le 2^{30}$ 时 soundness error 可忽略。

---

五、关键数学速查（白板版）

5.1 Gate Identity（5-selector 形式）

$$ q_L \cdot a + q_R \cdot b + q_O \cdot c + q_M \cdot ab + q_C \stackrel{H}{=} 0 $$

5.2 Grand Product 递推

$$ Z_{i+1} = Z_i \cdot \frac{(a_i + \beta\omega^i + \gamma)(b_i + \beta k_1\omega^i + \gamma)(c_i + \beta k_2\omega^i + \gamma)}{(a_i + \beta\sigma_a(i) + \gamma)(b_i + \beta\sigma_b(i) + \gamma)(c_i + \beta\sigma_c(i) + \gamma)} $$

5.3 Quotient 拆分

$$ T(X) = \alpha^0 \cdot \text{gate}(X) + \alpha^1 \cdot \text{perm-step}(X) + \alpha^2 \cdot \text{perm-init}(X) $$ $$ t(X) = T(X) / Z_H(X), \quad Z_H(X) = X^n - 1 $$

5.4 KZG Open & Verify

Open: $f(z) = y$, witness $\pi = [(f(\tau) - y)/(\tau - z)]_1$ Verify: $e(\pi, [\tau]_2 - [z]_2) = e([f]_1 - [y]_1, [1]_2)$

---

六、直觉理解 — 为什么 universal setup 能成立？

6.1 Trapdoor 泛化

Groth16 的 CRS 把电路特定的多项式 $u_i, v_i, w_i$ evaluate 在 trapdoor $x$ 上："$\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}$"——这些值电路一改就全废。

PlonK 的 CRS 只是 KZG 的 [1, τ, τ², ..., τ^d]_1, [τ]_2——只依赖最大 degree $d$，不依赖具体的多项式 $u_i, v_i, w_i$。

具体的电路特定信息（selector、permutation）作为 prover 输入，是 prover 自己 commit 的——CRS 不参与。

6.2 Updatability 来自 KZG

KZG 的 setup 是 universal 的，因此可以 multi-party update：每个新参与者用自己的 $\tau_i$ 把 CRS 乘进去，原 CRS 旧元素被消费但不需要作废。这就是 ceremony 的"加人就更安全"性质。

6.3 Permutation Argument 的几何直觉

把所有 wire position 想成 $3n$ 个槽位。Copy constraint 说"槽位 5 和槽位 12 必须相等"——这等于说 multiset ${x_1, x_2, ..., x_{3n}}$ 在某 permutation 下不变。

Grand product 把这个 multiset 等式 lift 到一个 polynomial $\prod (X - x_i)$，再 evaluate 在随机 $\beta$ 上——这是密码学里"multiset commitment"的标准技术（已被 plookup, lasso, lookup arguments 大量复用）。

---

七、实施考量 — Aztec / Polygon zkEVM / Halo2

7.1 Aztec V1/V2/V3

UltraPlonk 中 selector 数量从 5 个扩展到 ~10+ 个（包括 elliptic curve operations、range check），每个 custom gate 自己一行 selector polynomial。

Aztec Noir DSL：开发者写 Noir 代码 → 编译到 ACIR (Abstract Circuit IR) → 后端用 Barretenberg 生成 PlonK proof。

7.2 Polygon zkEVM (Hermez)

• 使用 PlonK + 自定义 gates 实现 EVM opcode
• 每个 opcode（如 ADD/MUL/MLOAD/JUMP）对应一组 selector
• TVL：$200M+ (2026)
• proof generation：~10 min/批 EVM 交易（GPU 集群）
• L1 verify：用一层 Groth16 包装来压缩 PlonK proof，节省 gas

7.3 Mina Protocol

• 使用 Halo2（PlonKish 派系，IPA 替代 KZG）
• 每个区块只 22 KB，靠 recursive proof 压缩
• TVL/市值：~$300M (2026)

7.4 Halo2（Zcash 实现）

Halo2 不是严格的 PlonK，而是 "PlonKish IR + IPA + recursion"：

• 替换 KZG → IPA：消除 trusted setup
• 把 selector 推广为 "advice / fixed / instance" 三类列
• 加 lookup table 原生支持（halo2-lookup, plookup 风格）
• recursion friendly（详见 Day 267）

7.5 真实 prover 性能数据（2026）

共同特点：prover 时间 dominated by MSM (multi-scalar multiplication) 和 NTT/FFT。GPU 加速比 CPU 快 5-10x。

---

八、被使用的真实案例

8.1 Aztec Connect（已退役 2024 但是经典案例）

• 私密 ETH ↔ DeFi bridge
• 每笔私密交易 ~600 bytes proof
• 用户 hot wallet 客户端 ~5-10 sec proof generation
• 累计交易 $1B+

8.2 Polygon zkEVM (Mainnet Beta 2023)

• EVM 等价 Type 2
• TVL: $200M+ (2026)
• 每批 ~500 笔交易合并到 1 个 PlonK proof
• L1 verify ~600K gas（PlonK + Groth16 wrap）

8.3 Mina

• 22 KB blockchain（单 block 大小不变）
• Halo2 recursion 支持 light client
• Zk app: zkLogin, age proof, KYC 等

8.4 Espresso (sequencer marketplace, 2024)

• HotShot consensus + PlonK proof
• 用 PlonK 证明 sequencer 行为正确
• 与 EigenLayer / Restaking 集成

8.5 Penumbra (private DEX, 2024)

• Cosmos zone, all-private DEX
• 使用 Halo2 + Poseidon hash
• 用户在客户端做 PlonK proof，~3 sec on laptop

---

九、局限性 — 推动 plookup / Plonky2 / Halo2

9.1 Proof size 仍较大

PlonK proof 约 600 bytes，比 Groth16 的 192 bytes 大 3 倍。L1 verify gas 因此从 ~113K 涨到 ~300K（每个 pairing precompile + 每个 G1 scalar mul）。

应对：

• L1 用 Groth16 包装 PlonK（recursion）
• 或用 IPA-based PCS（Halo2）

9.2 不支持原生 lookup

PlonK 的 gate identity 是 polynomial identity，对"$x \in {0, 1, ..., 255}$"这样的 range check 必须分解成 8 bit XOR 链——extremely 不效率。

应对：

• plookup'20 (Gabizon-Williamson)：在 PlonK 框架内加 lookup argument
• Halo2-lookup：升级版的 lookup
• LogUp / Lasso (2023)：更高效的 lookup argument

9.3 后量子安全性弱

依赖 BLS12-381 / BN254 ECDLP，量子计算机可破。

应对：Plonky2 用 FRI（Reed-Solomon）替换 KZG，达到后量子安全（详见 Day 266）。

9.4 Recursion 不直接

Pairing-based recursion 需要 cycle of pairing-friendly curves（如 MNT4/MNT6），效率较低。

应对：

• Halo (Bowe-Grigg-Hopwood 2019)：IPA + cycle of curves（Pasta）
• Plonky2：FRI + Goldilocks field，无需 pairing

---

十、关键速查表

10.1 PlonK 数字事实（BLS12-381）

10.2 与 Groth16 / Marlin / Halo2 对比

---

十一、面试题

Q1: 为什么 PlonK 能 universal 而 Groth16 不能？

答：Groth16 的 CRS 把电路特定的多项式 $u_i, v_i, w_i$ evaluation 在 trapdoor $x$ 上 commit 进 CRS——电路一改这些值全废。PlonK 用 KZG，CRS 只是 ${[\tau^i]_1}$ 这样纯依赖 degree 的元素；电路特定信息（selector + permutation）作为 prover 输入，由 prover commit。所以 CRS 在所有电路间共享，且新参与者可以 update 旧 CRS。

Q2: 详细解释 grand product permutation argument。

答：

1. 目标：证明 ${a_i, b_i, c_i}_{i=0}^{n-1}$ 这 $3n$ 个 wire 在某固定 permutation $\sigma$ 下是自身的 permutation（即满足 copy constraint）。
2. 用两个 verifier challenge $\beta, \gamma$ 把每个 wire 映射成 $(\text{wire-value} + \beta \cdot \text{position} + \gamma)$。
3. 定义 grand product $Z(\omega^i) = \prod_{j<i} \frac{f_j}{g_j}$，其中 $f_j$ 是原始 position 对应项，$g_j$ 是 permuted position 对应项。
4. 如果 multiset 相等，$Z$ 在 $\omega^n$ 处闭合回 1；否则不会。
5. 把这个 cyclic 关系编码成 polynomial identity，交给 quotient $t(X)$。

Q3: PlonK 的 5 个 selector 各做什么？

答：$q_L, q_R, q_O$ 是左/右/输出 wire 的线性系数；$q_M$ 是乘法系数；$q_C$ 是常数项。所有 gate 类型都能用这 5 个 selector 的不同组合表达：

• ADD: $q_L = q_R = 1, q_O = -1$
• MUL: $q_M = 1, q_O = -1$
• CONST: $q_L = 1, q_C = -k$
• 等等

UltraPlonk 加了更多 selector（如 $q_{\text{ECC}}, q_{\text{lookup}}$）支持 custom gates。

Q4: KZG 的 trusted setup ceremony 与 Groth16 的 phase 2 有何不同？

答：

• Groth16 phase 2 必须为每个电路重跑，因为 CRS 包含电路特定 $u_i, v_i, w_i$ evaluation。
• KZG (PlonK) ceremony 一次性生成 universal CRS（只包含 $[\tau^i]$），所有电路共享。
• Updatability：KZG ceremony 可以无限加人（每人乘自己的 trapdoor share），旧 CRS 不作废。Groth16 phase 2 一旦完成就固定。
• 后果：Ethereum 社区只需要跑一次 Powers of Tau ceremony（KZG 兼容），所有 PlonK 项目共用——这是 PlonK 工业化采用的关键。

Q5: 为什么 PlonK proof 比 Groth16 大 3 倍，工业界仍倾向 PlonK？

答：

1. Setup ceremony 成本：每电路一次 ceremony 协调成本极高（人月级），universal setup 节省巨大。
2. 可扩展性：custom gates、lookup arguments 都基于 Plonkish IR；Groth16 改动困难。
3. L1 gas 差距可弥补：用 Groth16 wrap PlonK proof（一层 recursion），L1 verify 仍是 ~113K gas，proof size 在 L2 内部不影响 L1 gas。
4. 生态：Halo2 / Plonky2 / Honk 等扩展都基于 Plonkish；社区 momentum 巨大。

Q6: PlonK 如何引入 lookup argument？

答：plookup (2020, Gabizon-Williamson)：把 lookup table $T$ 和 wire values $w$ 都视为 multiset，证明 $w \subseteq T$ 通过 grand product polynomial 类似 permutation argument 的方式。具体用 random challenge $\beta$ 形成多项式 $\prod (\beta + t_i)$ 和 $\prod (\beta + w_i)$，再加上 multiplicity 的处理。Halo2-lookup 是升级版。

LogUp (2022) 进一步用 logarithmic derivatives 替代 grand product，支持任意 multiset inclusion 且更高效。

---

十一·五、补充：PlonK 完整 prover/verifier pseudocode

下面给出能直接对照 Aztec Barretenberg 实现的 pseudocode（简化版）：

A. Prover (5-round Fiat-Shamir flat)

Input:  witness vector w (length 3n: a, b, c segments)
        circuit selectors q_L, q_R, q_O, q_M, q_C, σ_a, σ_b, σ_c
        SRS [τ^i]_1 for i=0..d

# Round 1: commit to wire polynomials
a(X) := interpolate(w[0..n])     # over H = <ω>
b(X) := interpolate(w[n..2n])
c(X) := interpolate(w[2n..3n])

[A]_1 := Σ a_i [τ^i]_1     # KZG commit
[B]_1 := Σ b_i [τ^i]_1
[C]_1 := Σ c_i [τ^i]_1
transcript ← [A]_1, [B]_1, [C]_1

# Round 2: permutation polynomial
β, γ ← FiatShamir(transcript)
Z(X) := build grand product polynomial
[Z]_1 := KZG commit Z
transcript ← [Z]_1

# Round 3: quotient polynomial
α ← FiatShamir(transcript)
T(X) := gate_identity(X) + α·perm_step(X) + α²·perm_init(X)
t(X) := T(X) / Z_H(X)            # Z_H = X^n - 1
split t = t_lo + X^n · t_mid + X^{2n} · t_hi  (each degree < n)
[T_lo]_1, [T_mid]_1, [T_hi]_1 := KZG commits
transcript ← [T_lo]_1, [T_mid]_1, [T_hi]_1

# Round 4: evaluate at random point ζ
ζ ← FiatShamir(transcript)
ā := a(ζ), b̄ := b(ζ), c̄ := c(ζ)
σ̄_a := σ_a(ζ), σ̄_b := σ_b(ζ)
z̄_ω := Z(ζ·ω)
t̄ := t_lo(ζ) + ζ^n · t_mid(ζ) + ζ^{2n} · t_hi(ζ)
transcript ← ā, b̄, c̄, σ̄_a, σ̄_b, z̄_ω, t̄

# Round 5: KZG opening proofs
v ← FiatShamir(transcript)
W_ζ(X)  := build batch opening for {a, b, c, σ_a, σ_b, t_lo, t_mid, t_hi} at ζ
W_ζω(X) := build opening for Z at ζω
[W_ζ]_1, [W_ζω]_1 := KZG commits

return π = ([A], [B], [C], [Z], [T_lo], [T_mid], [T_hi], [W_ζ], [W_ζω],
            ā, b̄, c̄, σ̄_a, σ̄_b, z̄_ω)

B. Verifier

Input:  proof π, public input PI, verifier preprocessed data (q_L, q_R, ..., σ_a, σ_b, σ_c commitments + Lagrange basis at ζ)

# Re-derive challenges
β, γ ← FiatShamir([A], [B], [C])
α ← FiatShamir(β, γ, [Z])
ζ ← FiatShamir(α, [T_lo], [T_mid], [T_hi])
v ← FiatShamir(ζ, ā, b̄, c̄, σ̄_a, σ̄_b, z̄_ω)
u ← FiatShamir(v, [W_ζ], [W_ζω])

# Compute public input contribution at ζ
PI(ζ) := Σ public_input_i · L_i(ζ)

# Compute target evaluation r(ζ) (linearisation polynomial value)
r(ζ) := compute_linearisation(ā, b̄, c̄, σ̄_a, σ̄_b, z̄_ω, α, β, γ, PI(ζ))

# Construct combined commitment [F]_1 and combined evaluation E
[F]_1 := q_L_comm·ā + q_R_comm·b̄ + q_O_comm·c̄ + q_M_comm·(ā·b̄)
       + q_C_comm + α·... (permutation terms)
       + α²·L_0(ζ)·[Z]_1
       - Z_H(ζ)·([T_lo] + ζ^n·[T_mid] + ζ^{2n}·[T_hi])

E := -r(ζ) + v·ā + v²·b̄ + ... (batched)

# Final pairing check
check  e([W_ζ]_1 + u·[W_ζω]_1, [τ]_2)
       == e(ζ·[W_ζ]_1 + u·ζ·ω·[W_ζω]_1 + [F]_1 - [E]_1·[1]_1, [1]_2)

只剩 2 个 pairing（在 batched 形式下），约 18 次 G1 scalar mul 和 1 次 multi-scalar mul over public input。

Aztec 的 Barretenberg 实现把 verifier 写成 ~3000 行 C++ + 复杂 ASM 优化。对应的 Solidity verifier 大约 ~600 行，gas ~280K。

---

十一·六、补充：Plonkish 风格电路工程模式

A. 何时用 Vanilla PlonK vs UltraPlonk vs Halo2-Plonkish？

B. 自定义 Gate 设计模式

设计 custom gate 时关注三点：

1. Selector 复用：同一个 selector 可激活多个约束方程。例如一个 "EC point add" gate 同时强制 $x_3 = \lambda^2 - x_1 - x_2$ 和 $y_3 = \lambda(x_1 - x_3) - y_1$。
2. Rotation cost：使用 Rotation::next() 引用下一行的 wire 值是免费的（不增加列数），但增加 quotient degree。
3. Degree budget：custom gate degree $\le D$（一般 $D=6, 9$ 等），degree 越高 quotient 拆得越多段，prover 越慢。

经典 case：Aztec Barretenberg 的 ECC point-doubling gate 用 4 个 advice column + degree-6 expression，把 8 个 constraint 压缩到 1 行。

C. Lookup Table 设计模式

Halo2 与 UltraPlonk 共享 lookup 设计哲学：

• Range check: 把 $a \in [0, 2^k)$ 表达为 lookup 进 size-$2^k$ table $T = [0, 1, ..., 2^k-1]$
• XOR table: 256x256 = 65536 行 table，每行 (a, b, a XOR b)
• SHA256 round constants: 64 行 lookup
• EC scalar multiplication windowed: 把 4-bit window 的 scalar mul 预计算

plookup 复杂度：lookup 多个 wire 进 size-$N$ table，prover 开销 $O(N + n)$，$n$ 是 lookup 次数。Lasso/Jolt (2023) 进一步降到 $O(\sqrt{N})$，是当前 SOTA。

D. 真实 PlonK 部署 gas 拆分

以 Polygon zkEVM PlonK verifier 合约为例（约 280K gas）：

把 PlonK 包进 Groth16 (recursion):

• L1 verify gas → ~113K（Groth16 wrapper）
• 节省 ~150K gas/批，但增加 prover 时间 ~5%

这就是为什么大型 zkRollup 都做"PlonK 内部 + Groth16 wrap 上链"。

---

十二、明日预告

明天 Day 266 我们换轨道，进入 后量子 + transparent 阵营 —— 精读 STARK / FRI 论文：

• Ben-Sasson et al., "Scalable, transparent, and post-quantum secure computational integrity" (ePrint 2018/046)
• "Fast Reed-Solomon Interactive Oracle Proofs of Proximity" (ECCC 2017)

预告核心问题：

• 为什么 STARK 不需要 trusted setup？
• FRI 的 fold 操作如何在 $\log n$ 轮内 commit 到一个 low-degree polynomial？
• AIR (Algebraic Intermediate Representation) 与 PlonkIsh 的对比？
• StarkNet 和 Plonky2 在生产中的工程权衡？

---

今日心得：精读 PlonK 后最大的洞察是——universal setup 的代价只是 KZG commitment 多一次 evaluation。Groth16 把电路特定信息预编译进 CRS，省 verifier 时间但牺牲灵活性；PlonK 把电路特定信息留给 prover 自己 commit，多花一点 verifier 时间换来无穷的 IR 扩展性。10 年的工业级 SNARK 演化几乎都是在 PlonK 架构下做加法（plookup, custom gates, recursion, GPU 加速）——这就是好抽象的生命力。