论文精读 #1 — Groth16

日期: 2027-01-20 方向: 零知识证明 / 论文精读 阶段: Phase 4 - 密码学工程 (Day 264-267 论文精读系列) 标签: #ZK #Groth16 #paper-reading #pairing-based-SNARK #trusted-setup

---

今日目标

---

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

Day 214 已经覆盖了 Groth16 的高层结构。今天这一篇是逐节、逐公式地走完 Groth 2016 这篇 11 页（含 appendix 17 页）的 EUROCRYPT 论文，目标是能在白板上独立推导完整 setup / prover / verifier 算法。

精读和速览的差别：速览能告诉你"3 个 group element"；精读能告诉你为什么必须是 3 个，且每一个里都装着什么 monomial。

判断"精读到位"的硬指标：

• 不看论文，能写出 CRS 的 13 类元素中的至少 10 类。
• 不看论文，能从 QAP 推到 verifier 的 1 个 pairing 等式。
• 能独立解释 $\gamma, \delta$ 为什么必须存在（不是冗余）。
• 能讲 trusted setup ceremony 的 phase 1 / phase 2 区别。

---

一、论文基本信息

历史趣闻：Groth 在论文 Section 1 末尾写了一句话："The argument size we achieve is essentially optimal for SNARKs based on bilinear groups under reasonable assumptions." 这句话在 2016 年是 conjecture，2017 年才由 Groth–Maller、2020 年由 Bellare 等人陆续证明：在 SE-NIZK 模型下，3 个 group element 是 Pareto-optimal lower bound。

---

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

2.1 SNARK 进化路线

              Pinocchio'13 (8 group elt)
                       │
              GGPR'13 / BCTV'14 (7-9 elt)
                       │
                  ▼
        ┌──────► Groth16'16 (3 elt, circuit-specific) ◄── 今日精读
        │                  │
        │                  │ 推动 universal setup 需求
        │                  ▼
        │          Sonic'19 (universal updatable)
        │                  │
        │                  ▼
        └─── PlonK'19 / Marlin'19 (universal + custom gates)
                            │
                            ▼
                   Plonky2 / Halo2 (recursion)

2.2 与前作的关系

2.3 为什么 2017–2022 在以太坊上是事实标准？

1. Proof size 最小：链上每 byte 都贵。192 bytes 比 PlonK 的 ~500 bytes 省 60%+ gas。
2. Verifier 最简：3 个 pairing + 1 个 multi-scalar-mul，EVM precompile (ecPairing at 0x08) 直接支持，gas 成本约 113K。
3. 协议先行：Tornado Cash (2019)、Zcash Sapling (2018)、Filecoin (2020) 都早于 PlonK 落地，已经"先到先得"。
4. Setup ceremony 工业化：Powers of Tau (2017) + Hermez ceremony (2020) 把信任假设公开化。

何时不再是首选？ —— 见 §九、十"局限性"。

---

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

Groth16 把 NIZK 的 proof size 压缩到了 3 个 group element（两个 G1 + 一个 G2），verifier 只需要 3 个 pairing + O(public input) 的 EC operations，但代价是每个新电路都要跑一次 trusted setup。

拆开成 4 个技术贡献：

---

四、逐节精读

4.1 Section 1: Introduction — 关键观察

Groth 在 Intro 里抛出了三个 motivating questions：

Q1: 在 pairing 模型下，proof size 的 lower bound 是多少？ Q2: 能不能在 group element 数等于 lower bound 的同时，保留 SE（simulation extractability）？ Q3: 如何让 verifier 等式数从 PHGR'13 的 11 个 pairing 降到 1 个等式？

Groth16 的答案：3 个 group element，1 个 pairing 等式（含 4 个 pairing），SE 在 GGM 下成立。

Intro 中关键一句（论文 p.2）：

"The asymptotic argument size of our SNARK is 2 elements in $G_1$ and 1 element in $G_2$, which we conjecture to be optimal."

Groth 在 Section 1.3 比较表 (Table 1) 中给出了对比（这里整理后版本）：

| Scheme | $|σ|_1$ | $|σ|_2$ | Prover G_1 mul | Verifier pairing | |--------|---------|---------|----------------|------------------| | Pinocchio | $7m+n$ | $m$ | $7m$ | 11 | | GGPR | $6m+n$ | $m+n$ | $6m$ | 12 | | BCTV | $6m+n$ | $m+n$ | $6m$ | 12 | | Groth16 | $\mathbf{m + 2n}$ | $\mathbf{n}$ | $\mathbf{3m}$ | 3 |

这里 $m$ = constraints, $n$ = wires。可以看出 CRS size 也是 Groth16 最小。

4.2 Section 2: Preliminaries

2.1 Bilinear Groups

设三元组 $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T)$ 都是阶 $p$ 的循环群，$g_1, g_2$ 是生成元，pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ 满足：

• Bilinearity: $e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$
• Non-degeneracy: $e(g_1, g_2) \neq 1$
• Efficiency: 多项式时间可计算

记号约定（论文 §2.1）： $$ [a]_1 := g_1^a \in \mathbb{G}_1, \quad [b]_2 := g_2^b \in \mathbb{G}_2, \quad [a]_1 \cdot [b]_2 := e(g_1^a, g_2^b) = [ab]_T $$

这套加法记号在后面非常省力。

2.2 QAP (Quadratic Arithmetic Program)

R1CS 约束 $A \vec{z} \circ B \vec{z} = C \vec{z}$ 通过 Lagrange 插值变成 QAP：

$$ \sum_{i=0}^{m} z_i u_i(X) \cdot \sum_{i=0}^{m} z_i v_i(X) - \sum_{i=0}^{m} z_i w_i(X) = h(X) \cdot t(X) $$

其中：

• $u_i, v_i, w_i$ 是 degree $< n$ 的多项式
• $t(X) = \prod_{j=1}^{n} (X - r_j)$ 是 vanishing polynomial
• $h(X)$ 是 prover 计算的 quotient

关键性质：QAP 把 $n$ 个约束打包成 1 个多项式恒等式，这是 Groth16 能做到 1 个 pairing 等式的根本。

2.3 NILP (Non-Interactive Linear Proof) 抽象

Groth 引入了 NILP 作为分析工具：

• prover 输出的每个 element 都是 setup 中 trapdoor 的线性组合
• 在 GGM 下，attacker 也只能做线性组合
• 因此 soundness 可以约简为代数 system 的解空间分析

这是论文的方法论核心：把"密码学攻击"翻译成"代数推导"。

4.3 Section 3: Construction — 核心算法

这是论文最关键的一节，下面逐字推导。

4.3.1 Setup（CRS 生成）

Trusted setup 选取随机 trapdoor： $$ \alpha, \beta, \gamma, \delta, x \xleftarrow{$} \mathbb{F}_p^* $$

CRS 包含 13 类元素（论文 p.7 displayed equation）：

$$ \sigma = \left( \begin{aligned} &[\alpha]_1, [\beta]_1, [\delta]_1, \ &{[x^i]1}{i=0}^{n-1}, \ &\left{\left[\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right]1\right}{i=0}^{\ell}, \ &\left{\left[\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}\right]1\right}{i=\ell+1}^{m}, \ &\left{\left[\frac{x^i \cdot t(x)}{\delta}\right]1\right}{i=0}^{n-2}, \ &[\beta]_2, [\gamma]_2, [\delta]_2, \ &{[x^i]2}{i=0}^{n-1} \end{aligned} \right) $$

记号说明：

• $\ell$ = public input 个数
• $m$ = 总 wire 数
• $n$ = constraint 个数（也是 vanishing polynomial degree）
• 第 4 行（$i=0..\ell$）是 public input 部分，用 $\gamma$ 屏蔽
• 第 5 行（$i=\ell+1..m$）是 private witness 部分，用 $\delta$ 屏蔽
• 这两个屏蔽 trapdoor 是 Groth16 区别于 Pinocchio 的关键设计

Toxic waste：$\alpha, \beta, \gamma, \delta, x$ 必须被销毁，否则 prover 可以伪造证明。

CRS 大小：$m + 2n$ 个 G1 + $n$ 个 G2，约束 1M 时约 96 MB（BLS12-381）。

4.3.2 Prover 算法

Prover 已知 witness $\vec{z} = (z_0, ..., z_m)$（含 $z_0 = 1$），首先计算多项式：

$$ A(X) = \sum_{i=0}^{m} z_i u_i(X), \quad B(X) = \sum_{i=0}^{m} z_i v_i(X), \quad C(X) = \sum_{i=0}^{m} z_i w_i(X) $$

Quotient: $h(X) = (A(X) B(X) - C(X)) / t(X)$。

随机选 blinding $r, s \xleftarrow{$} \mathbb{F}_p$。然后计算三个 group element：

$$ \boxed{ \begin{aligned} A &= [\alpha]1 + \sum{i=0}^{m} z_i [u_i(x)]_1 + r [\delta]_1 \ B &= [\beta]2 + \sum{i=0}^{m} z_i [v_i(x)]_2 + s [\delta]2 \ C &= \frac{1}{\delta}\left[\sum{i=\ell+1}^{m} z_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x) t(x)\right]_1 \ &\quad + s A + r B - r s [\delta]_1 \end{aligned} } $$

直觉：

• $A$ 编码 left QAP 多项式，加上 $\alpha$ shift 防 forgery，加上 $r\delta$ 是 zero-knowledge blinding。
• $B$ 类似，但在 $\mathbb{G}_2$。
• $C$ 是 "胶水"——它把 $\alpha$ shifted 的 $A$ 和 $\beta$ shifted 的 $B$ 中产生的 cross terms 全部抵消。

注意 $C$ 中的 $sA + rB - rs[\delta]_1$ 这一行是为了 zero-knowledge 引入的"cross blinding"，让攻击者无法从 $A, B, C$ 中提取 witness。

Prover 主要开销：

• $A, B, C$ 各需要约 $m$ 次 group MSM
• $h(x)$ 计算：$O(n \log n)$ FFT
• 总复杂度 $O(m + n \log n)$，10M 约束典型耗时 30-60 秒（单机）

4.3.3 Verifier 算法

Verifier 收到 $(A, B, C)$，已知 public input $a_0=1, a_1, ..., a_\ell$。

核心 1 个 pairing 等式：

$$ \boxed{ e(A, B) \stackrel{?}{=} e([\alpha]_1, [\beta]2) \cdot e\left(\sum{i=0}^{\ell} a_i \left[\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right]_1, [\gamma]_2\right) \cdot e(C, [\delta]_2) } $$

简记为： $$ e(A, B) = e([\alpha]_1, [\beta]_2) \cdot e(I, [\gamma]_2) \cdot e(C, [\delta]_2) $$

其中 $I = \sum_{i=0}^{\ell} a_i \cdot [\dots]_1$ 是 public input 的线性组合。

总共 4 个 pairing 计算（左 1 + 右 3），但 verifier 一般会预计算 $e([\alpha]_1, [\beta]_2)$ 作为电路常数，所以实际只算 3 个 pairing（这就是常说的"3 pairing verifier"）。

4.4 Section 4: Security — Knowledge Soundness in GGM

Groth 在 GGM (Generic Group Model) 下证明 knowledge soundness。

4.4.1 GGM 假设

在 GGM 中，attacker 只能通过 oracle access 做 group operation；任何 group element 都是 trapdoor 的已知线性组合。这让 attacker 可被一个 polynomial-time 的"代数 adversary"取代。

4.4.2 Soundness 推导骨架

假设 attacker 输出 $(A^, B^, C^*)$ 通过 verify。在 GGM 中，attacker 必须给出表达式：

$$ A^* = \sum_j a_j \cdot \tau_j, \quad B^* = \sum_k b_k \cdot \tau_k, \quad C^* = \sum_l c_l \cdot \tau_l $$

其中 $\tau_j$ 是 CRS 中所有 monomial（如 $\alpha, \beta, \alpha x^i, \beta x^i / \delta, \dots$）。

代入 verifier 等式后，两边都变成 trapdoor 的多项式。两边相等当且仅当每个 monomial 的系数相等。

Groth 在 Theorem 1 (p.10) 系统化分析了这些系数等式，结论是：要满足所有等式，attacker 必须实际拥有满足 QAP 的 witness $\vec{z}$——这就是 knowledge soundness。

4.4.3 为什么需要 $\gamma$ 和 $\delta$？

关键观察：如果没有 $\gamma$，attacker 可以把 public input slot 偷换成 private witness slot；如果没有 $\delta$，attacker 可以用 $h(x)t(x)$ 项里的 trapdoor 重组其他 monomials。

具体来说，$\gamma$ 把 public input 的 CRS 元素 "锁" 在 verifier 端的 $e(I, [\gamma]_2)$ 配对里——prover 没有 $[1/\gamma]_2$，所以无法用这些元素去构造 $A, B, C$。

类似地，$\delta$ 锁住 $h(x)t(x)$ 系数和 private witness 部分。

没有 $\gamma$/$\delta$ 的版本叫 "Pinocchio-light"，已知有 malleability 攻击（Bowe & Gabizon 2018）。

4.5 Section 5: Optimizations

论文 Section 5 给了几个工程优化：

1. Multi-exp: prover 的 $\sum z_i [u_i(x)]_1$ 用 Pippenger / BDLO12 算法，加速 5-10x。
2. FFT for QAP: 把多项式计算从 $O(n^2)$ 降到 $O(n \log n)$。
3. Batch verification: 多个 proof 合并成一次 multi-pairing，验证速度 2-3x。
4. Aggregated Groth16 (后续工作 Bunz-Maller-Vesely 2019): 把 $k$ 个 proof 聚合到 $O(\log k)$ size。

---

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

5.1 Setup CRS（13 类元素）

总计 G1: $m + 2n + \mathcal{O}(1)$；G2: $n + 3$。BLS12-381 上 G1 = 48 B, G2 = 96 B。

5.2 Prover (A, B, C) 三元组

A = [α]_1 + Σ z_i · [u_i(x)]_1 + r · [δ]_1                    ∈ G1
B = [β]_2 + Σ z_i · [v_i(x)]_2 + s · [δ]_2                    ∈ G2
C = (1/δ) · [Σ_{i>ℓ} z_i (β u_i + α v_i + w_i) + h(x)t(x)]_1
    + s·A + r·B - r·s·[δ]_1                                    ∈ G1

Proof: $\pi = (A, B, C)$，$2 \times 48 + 96 = \mathbf{192\ \text{bytes}}$（BLS12-381）。

5.3 Verifier 1-pairing 等式

$$ e(A, B) = e([\alpha]_1, [\beta]2) \cdot e(I\ell, [\gamma]_2) \cdot e(C, [\delta]_2) $$

其中 $I_\ell = \sum_{i=0}^{\ell} a_i \cdot \mathrm{IC}_i$，$\mathrm{IC}_i$ 是 CRS 第 5 类元素。

---

六、直觉理解 — 为什么三元组就够？

6.1 从 QAP 到 3 元组的"凝聚"

QAP 等式 $A B - C = h t$ 中，$A, B, C$ 是 prover 已知的多项式。在指数上做 commitment：

• $[A(x)]_1$, $[B(x)]_2$ 用来形成 $e(A,B) = [A B]_T$（左半边）
• $[C(x)]_1$ 携带右半边 $C(x) + h(x) t(x)$ 信息

Pinocchio 之所以需要 8-9 个元素，是因为它分别 commit $A, B, C, H$ 还要单独提交 KEA（Knowledge of Exponent）proof。Groth 的洞察是：用 $\alpha, \beta$ shift 把所有 KEA 性质编码进 single pairing 等式，省掉额外 element。

6.2 $\gamma, \delta$ 的精确职责

$\gamma, \delta$ 看似冗余（PHGR 没有），但它们是 Groth16 把 verifier 等式从 11 个降到 1 个的结构性代价。

6.3 Zero-Knowledge 来自哪里？

Prover 选随机 $r, s$，使 $A, B, C$ 在保留 verifier 等式的同时，分布与"模拟器输出"不可区分。

• $A$ 加 $r[\delta]_1$ 后，仍满足 $A B = \dots$（因为 verifier 等式右边的 $e(C, [\delta]_2)$ 吸收了对应项）
• $B$ 加 $s[\delta]_2$ 同理
• $C$ 中 $sA + rB - rs[\delta]_1$ 项是为了消掉因 $r, s$ 引入的 cross terms

模拟器（无 witness）：随机选 $A^, B^$，按 verifier 等式倒推 $C^*$，输出分布与真 prover 完全一致——完美 zero-knowledge。

---

七、实施考量 — Trusted Setup Ceremony

7.1 为什么"trusted"是难题？

CRS 中所有 trapdoor $(\alpha, \beta, \gamma, \delta, x)$ 必须有人生成又必须无人知道。如果有人保留这些 trapdoor，他可以为任意 statement 伪造 proof（包括偷 Tornado Cash 全部 TVL）。

7.2 多方计算（MPC）解决方案

关键属性："只要至少一个参与者诚实地销毁了自己的 share，整体 trapdoor 就是安全的"——这叫 1-of-N trust assumption。

实现方式：每个参与者 $i$ 选自己的 $\tau_i$，把 $\tau_i$ "乘"进 CRS，然后销毁本地 share。最终 trapdoor $\tau = \prod \tau_i$，没人知道 $\tau$。

7.3 Phase 1 vs Phase 2

Groth16 ceremony 实际上分两阶段（这是部署中的关键工程细节）：

Phase 1: Powers of Tau (universal)

只生成与电路无关的部分： $$ {[x^i]1}{i=0}^{2n-2}, \quad {[x^i]2}{i=0}^{n-1}, \quad [\alpha x^i]_1, [\beta x^i]_1, [\beta x^i]_2 $$

可以所有 Groth16 电路共享，因此 Ethereum 社区 2017 年跑了一次 87 人的 Powers of Tau ceremony，输出可被 Tornado Cash / Zcash / Filecoin / Aztec 等所有项目复用。后续 2019-2022 又有 Hermez (171 人)、Perpetual Powers of Tau (170+ 人) 接力。

Phase 2: Circuit-specific

每个电路单独跑一次，生成与电路相关的 $\beta u_i + \alpha v_i + w_i$ 等元素。这是 Groth16 的痛点：

• Tornado Cash 升级一次合约要重跑 phase 2
• Zcash Sapling → NU5 因为电路改了，phase 2 完全作废
• DApp 团队必须协调 50+ 参与者，时间+协调成本高

这个痛点直接催生了 PlonK (universal & updatable)——不需要 phase 2。详见 Day 265。

7.4 真实 ceremony 数据

Tornado Cash 创新：用浏览器跑 ceremony，让普通用户参与，达到 1000+ 参与者规模。

---

八、被使用的真实案例 — Groth16 在生产中

8.1 Tornado Cash（Ethereum L1 隐私混币器）

• 使用：每次存款验证 Merkle tree inclusion proof
• 电路 size：约 80K constraints
• proof on-chain：192 bytes（Groth16）
• verifier gas cost：~580K gas（含 ecPairing precompile + 公开输入处理）
• TVL 峰值：~$1B (2022)

8.2 Zcash Sapling

• 使用：屏蔽交易（Spend + Output）
• 电路 size：~76K constraints (Spend), ~2K (Output)
• proof time on phone：约 5 秒（2018 数据，移动端 Sapling 优化）
• TVL/市值：Zcash 市值峰值 ~$10B (2018)
• 后续：NU5 (2022) 引入 Halo2 替代 Groth16，消除 trusted setup

8.3 Filecoin

• 使用：PoRep（Proof of Replication）+ PoSt（Proof of Spacetime）
• 电路 size：单一 sector 约 1.4 亿 constraints（这是 Groth16 跑过的最大电路之一）
• prover time：单 sector 约 1-2 小时（GPU 加速）
• 网络规模：截至 2026，存储 30+ EiB（exbibyte）

8.4 Semaphore

• 使用：匿名信号广播（投票、whistleblowing）
• 电路 size：~10K constraints
• 集成：World ID、Worldcoin 等大规模身份系统

8.5 Aztec V1

• 使用：私密 ERC-20 转账（Aztec 1.0 协议）
• proof on-chain：每笔交易 ~580 bytes（含 Pedersen commitment + Groth16）
• 2022 转向：Aztec V2 切换到 PlonK（Honk），原因就是 Groth16 phase 2 太麻烦

---

九、局限性 — 为什么 PlonK 终于把 Groth16 替换了

这些局限直接对应了后续 SNARK 的设计目标：

• PlonK: 解决 universal setup
• PlonKish + custom gates: 支持 lookup
• Plonky2/STARK: 后量子 + transparent
• Halo2: trusted setup 完全消除 + recursion

---

十、关键速查表（面试可直接背）

10.1 Groth16 数字事实

10.2 与同类 SNARK 对比

---

十一、面试题（精读后能答得上来）

Q1: 为什么 Groth16 的 proof 必须有 3 个元素，不是 2 个？

答：Knowledge soundness 要求 proof 至少包含 $A, B$（来自 QAP 左右两侧）才能形成 $e(A, B) = [\dots]$。但只用 $A, B$ 时，verifier 等式右边出现 $h(x) t(x)$ 项无法仅靠 CRS 公开元素表达——必须引入 $C$ 来携带 $h(x)t(x) / \delta$ 部分。Groth–Maller'17 证明在 SE-NIZK 模型下 3 个元素是 lower bound。

Q2: 解释 $\gamma$ 和 $\delta$ 各自防御什么攻击。

答：

• $\gamma$ 防 public input 篡改攻击：把 public input CRS 元素 $\frac{\beta u_i + \alpha v_i + w_i}{\gamma}$ 锁在 verifier 的 $e(I, [\gamma]_2)$ 配对中。Prover 没有 $[1/\gamma]_2$，无法把这些元素纳入 $A, B, C$。
• $\delta$ 防 mauler 攻击：把 prover-only 元素和 $h(x)t(x)$ 系数用 $\delta$ 屏蔽。如果没有 $\delta$，attacker 可以把已有 proof 改造成新 statement 的 proof（malleability）。

Q3: 为什么 phase 1 ceremony 可以复用，phase 2 不行？

答：Phase 1 只生成与电路无关的 powers $[x^i]_1, [x^i]_2$ 和 $\alpha, \beta$ shift——这些只依赖 $n$（最大约束数），不依赖具体 $u_i, v_i, w_i$。Phase 2 要把 phase 1 的输出和具体电路的 $u_i, v_i, w_i$ 多项式 evaluation 组合，生成 $\frac{\beta u_i + \alpha v_i + w_i}{\gamma}$ 等"电路特定"元素——电路一改，这些元素就全废。

Q4: 模拟器（simulator）如何在没有 witness 的情况下产生 valid proof？

答：模拟器拥有 trapdoor（这是 ZK 定义中允许的）。给定要 simulate 的 statement 和 public input $a_0, ..., a_\ell$：

1. 随机选 $A^* \in \mathbb{G}_1, B^* \in \mathbb{G}_2$
2. 用 trapdoor $\delta$ 解出 $C^* = \frac{1}{\delta}\left[ \log A^* \cdot \log B^* - \alpha\beta - \sum a_i (\beta u_i + \alpha v_i + w_i) \right]$ 对应的 G1 element
3. 输出 $(A^, B^, C^*)$

这个 proof 满足 verifier 等式（按构造），且分布与真 prover 完全相同（因为真 prover 也是先选 $r, s$ 决定 $A, B$，再算 $C$）。

Q5: 如果 Tornado Cash 想把电路从 80K 升级到 200K constraints，需要做什么？

答：

1. Phase 1 通常不需要重跑：Powers of Tau 通常已经预生成到 $2^{21}$ 或更高，足够覆盖 200K（< $2^{18}$）。
2. Phase 2 必须重跑：电路改了，$u_i, v_i, w_i$ 全部变化，新的 phase 2 ceremony 不可避免。
3. 协调多个参与方：通常 50–500 人，浏览器 + CLI 混合方式，持续 1-3 个月。
4. 新合约部署：用新 verifier 合约（含新 CRS hash），旧合约的 anonymity set 与新合约不再兼容——这是用户体验大问题，是 Tornado Cash 长期不升级电路的原因之一。

---

十二、彩蛋 — Groth 的下一步与对 Web3 的影响

Groth 在论文末尾写道：

"It is an interesting open problem whether we can match these efficiency parameters while having a universal common reference string."

这句"open problem"在 2019 年被 Sonic / PlonK 解答。十年后看，整个 SNARK 生态的演化路径几乎完全沿着 Groth16 的"局限性"推进：

Groth16 (2016): 3 element, circuit-specific
   → universal setup 需求 → Sonic'19 → PlonK'19
   → no setup 需求       → Halo'19, STARK'18
   → recursion 需求      → Halo2, Plonky2
   → custom gates        → Plonky2, Plonkish IR
   → lookup arguments    → plookup, lookup tables, lasso

但 Groth16 因为 192 bytes 的极简 proof 和 113K gas 的极低 verify 成本，在 EVM L1 上仍然是 2026 年的事实最优 SNARK——zkSync / Scroll / Linea 都用 PlonK 或 Halo2 在 L2 内部，但最终上链 L1 verify 时套一层 Groth16 包装（recursion proof composition）。

也就是说：Groth16 永远不会在 Ethereum 上消失——它是 ZK 大栈的最后一公里。

---

十二·五、补充：Groth16 完整代数推导走查（白板版）

下面把 verifier 等式从 prover 三元组到 1-pairing identity 的代数推导完整走一遍——这是面试中"在白板上推一遍 Groth16"题的标准答案。

A. 把 Prover 三元组在指数上展开

记 $A = [a]_1, B = [b]_2, C = [c]_1$，其中：

$$ a = \alpha + \sum_i z_i u_i(x) + r\delta $$ $$ b = \beta + \sum_i z_i v_i(x) + s\delta $$ $$ c = \frac{1}{\delta}\left(\sum_{i>\ell} z_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x) t(x)\right) + s a + r b - r s \delta $$

B. 计算 $a \cdot b$（左 pairing 的展开）

$$ ab = \left(\alpha + \sum z_i u_i + r\delta\right) \cdot \left(\beta + \sum z_i v_i + s\delta\right) $$

展开成 9 项：

$$ ab = \alpha\beta + \alpha \sum z_i v_i + \alpha s \delta + \beta \sum z_i u_i + \left(\sum z_i u_i\right)\left(\sum z_j v_j\right) + s\delta \sum z_i u_i + r\delta\beta + r\delta \sum z_j v_j + rs\delta^2 $$

C. 计算 $c \cdot \delta$（右 pairing 的展开）

$$ c\delta = \sum_{i>\ell} z_i (\beta u_i + \alpha v_i + w_i) + h(x) t(x) + sa\delta + rb\delta - rs\delta^2 $$

把 $sa\delta + rb\delta$ 展开：

$$ sa\delta = s\delta\alpha + s\delta \sum z_i u_i + rs\delta^2 $$ $$ rb\delta = r\delta\beta + r\delta \sum z_i v_i + rs\delta^2 $$

合并：

$$ c\delta = \sum_{i>\ell} z_i (\beta u_i + \alpha v_i + w_i) + h(x) t(x) + s\delta\alpha + s\delta \sum z_i u_i + r\delta\beta + r\delta \sum z_i v_i + rs\delta^2 $$

D. 计算 $I \cdot \gamma$（public input 部分）

$$ I = \sum_{i=0}^{\ell} z_i \cdot \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} $$

$$ I\gamma = \sum_{i=0}^{\ell} z_i (\beta u_i + \alpha v_i + w_i) $$

E. 验证等式 $ab = \alpha\beta + I\gamma + c\delta$

代入：

$$ \alpha\beta + I\gamma + c\delta = \alpha\beta + \sum_{i=0}^{\ell} z_i(\beta u_i + \alpha v_i + w_i) + \sum_{i>\ell} z_i (\beta u_i + \alpha v_i + w_i) + h(x)t(x) + s\delta\alpha + s\delta \sum z_i u_i + r\delta\beta + r\delta \sum z_i v_i + rs\delta^2 $$

化简 public + private 求和：

$$ \sum_{i=0}^{m} z_i(\beta u_i + \alpha v_i + w_i) = \beta \sum z_i u_i + \alpha \sum z_i v_i + \sum z_i w_i $$

由 QAP 关系：$\sum z_i u_i \cdot \sum z_i v_i - \sum z_i w_i = h(x) t(x)$

代入：

$$ \sum z_i w_i = \sum z_i u_i \cdot \sum z_i v_i - h(x)t(x) $$

所以 RHS 变成：

$$ \alpha\beta + \beta \sum z_i u_i + \alpha \sum z_i v_i + \left(\sum z_i u_i\right)\left(\sum z_j v_j\right) - h(x)t(x) + h(x)t(x) + s\delta\alpha + s\delta \sum z_i u_i + r\delta\beta + r\delta \sum z_i v_i + rs\delta^2 $$

$h(x)t(x)$ 消掉，剩下的项与 $ab$ 展开完全一致——验证等式成立。

F. 关键观察

• $\alpha\beta$ 来自 prover 端的 $\alpha, \beta$ shift
• public input 部分通过 $\gamma$ 隔离到 verifier 单独 pairing
• private witness + h(x)t(x) 通过 $\delta$ 隔离到第三个 pairing
• $r, s$ blinding 项在 $sa\delta + rb\delta - rs\delta^2$ 中正好闭合，不引入新项

这就是为什么 Groth16 的 1-pairing identity is exact——任何不满足 QAP 的 witness 在代数上必然破坏这个 identity。

---

十二·六、补充：Groth16 真实部署的工程坑

A. Trusted Setup 操作流程（DApp 团队视角）

假设你要为一个新 ZK app（80K constraints）部署 Groth16，phase 2 ceremony 实际操作步骤：

1. Phase 1 选取：从 Powers of Tau 仓库（如 Hermez 171 人 ceremony）下载已生成的 universal CRS。文件大小 ~14 GB（支持到 $2^{28}$）。
2. Phase 2 init：用 snarkjs groth16 setup 命令把 phase 1 + 你的 R1CS → 初始 phase 2 zkey 文件
3. 协调参与者：通常 50-500 人；准备 Web UI + CLI 双通道。每人下载当前 zkey、贡献自己的 trapdoor、上传新 zkey。
4. 签名公开 attestation：每人公开签名说"我做了贡献并销毁了 trapdoor"。Twitter/GitHub 留 hash。
5. Verify all contributions：snarkjs zkey verify 检查从 init 到最终 zkey 的链是否有效。
6. 导出 verifier: snarkjs zkey export solidityverifier 生成 ~600 行 Solidity 合约
7. 部署 + 公布: 把 final zkey 哈希、所有签名 attestation、verifier 合约地址公开

关键风险：

• 如果所有参与者都串通，trapdoor 被合伙保留 → 全 TVL 风险
• 1-of-N 假设要求至少一人诚实，Web UI 让普通用户参与就是为了扩大 N
• Tornado Cash 用浏览器 ceremony，达到 1114 参与者，是历史上最大规模

B. 常见 Groth16 实现陷阱

陷阱 1: 公开输入顺序错位

Solidity verifier 合约里 public input 数组顺序必须和电路 signal input 顺序严格一致。曾有项目把 nullifier 和 commitment 顺序搞反，导致 verifier 始终拒绝有效 proof（早期 Tornado Cash 修过此 bug）。

陷阱 2: Field 不一致

电路在 BN254 编译，但 Solidity 端用了 BLS12-381 verifier 模板 → 必然不通过。BN254 是 EVM precompile (0x06, 0x07, 0x08) 内置的曲线，Groth16 部署 EVM 上几乎都用 BN254 而非 BLS12-381。

陷阱 3: 端序问题

groth16 proof 在不同语言（Rust/Go/JS）序列化方式不同：big-endian vs little-endian + compressed vs uncompressed。必须确保 prover 和 verifier 用同一格式。Aztec 早期就因端序错误浪费了数周调试。

陷阱 4: Powers of Tau 不够大

如果电路 constraints > $2^{28}$，需要更大的 phase 1。Hermez 是 $2^{28}$；Filecoin 自己跑了 $2^{28}$；想要 $2^{30}$ 必须自己跑或等社区 ceremony。

陷阱 5: Witness Generation 慢

Groth16 prover 时间：witness 生成 + multi-scalar mul + FFT。witness 生成（即 R1CS 求解）有时被忽视——大电路下可能占 prover 时间 30%+。circom_runtime 后来增加 C++ witness generator 来加速。

C. Solidity Verifier 合约结构

最小 Groth16 verifier 合约（基于 BN254）：

contract Verifier {
    using Pairing for Pairing.G1Point;
    
    struct VerifyingKey {
        Pairing.G1Point alpha;
        Pairing.G2Point beta;
        Pairing.G2Point gamma;
        Pairing.G2Point delta;
        Pairing.G1Point[] IC;  // size = ℓ+1
    }
    
    struct Proof {
        Pairing.G1Point A;
        Pairing.G2Point B;
        Pairing.G1Point C;
    }
    
    function verifyProof(
        uint[2] memory a,
        uint[2][2] memory b,
        uint[2] memory c,
        uint[ℓ] memory input
    ) public view returns (bool) {
        // 1. Compute IC linear combination
        Pairing.G1Point memory vk_x = vk.IC[0];
        for (uint i = 0; i < input.length; i++) {
            vk_x = vk_x.addition(vk.IC[i+1].scalar_mul(input[i]));
        }
        
        // 2. Pairing check: e(A, B) = e(α, β) · e(IC, γ) · e(C, δ)
        return Pairing.pairingProd4(
            proof.A.negate(), proof.B,
            vk.alpha, vk.beta,
            vk_x, vk.gamma,
            proof.C, vk.delta
        );
    }
}

pairingProd4 调用 EVM precompile 0x08 (ecPairing)，把 4 个 pairing 一次算完，gas ~113K。

把 verifier 编译后 deploy bytecode ~20-30 KB。

D. 历史教训：Zcash Sapling Counterfeiting Bug (2018)

2018 年 4 月，Zcash 团队发现 Sapling 之前的 Sprout（基于 BCTV14, Groth16 的前身）存在 counterfeiting vulnerability——攻击者理论上可以无限增发 Zcash 而不被发现。

根因：BCTV14 在 phase 2 setup 中遗漏了一个 element 验证步骤。

修复：紧急升级到 Groth16（已在论文中修复此问题），重做 trusted setup ceremony。

教训：

• trusted setup 是 attack surface：不仅要相信参与者，还要审计 ceremony 软件本身
• 论文 bug 可能潜伏多年：BCTV14 漏洞在被发现前已经被 Zcash 用了 2 年
• Groth16 在论文层面已修复，但 Sprout 用户必须迁移到 Sapling

这是 Groth16 严肃工程化的一个里程碑事件——之后所有 ZK 项目都更重视 ceremony 软件审计。

---

十三、明日预告

明天 Day 265 我们继续精读 SNARK 三大经典之二：PlonK (Gabizon-Williamson-Ciobotaru, ePrint 2019/953)。

预告核心问题：

• 为什么 PlonK 能做到 universal & updatable setup？
• Permutation argument 的 grand product polynomial 长什么样？
• Lookup argument（plookup）如何嵌入？
• 真实部署：Aztec / Polygon zkEVM / Mina 各做了什么改动？

---

今日心得：精读 Groth16 后最大的收获，是从"3 个 element 真神奇"到"3 个 element 是 QAP × pairing × ZK 三角约束下的必然"。Groth 没有发明 QAP，没有发明 pairing，没有发明 NILP——但他把这些零件组装成了 EUROCRYPT 2016 那篇 11 页的 paper。架构师式的精读就是把"魔法"还原成"必然"。