Groth16 — 三元组与 Trusted Setup

日期: 2026-12-01 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #Groth16 #SNARK #pairing #setup-ceremony

---

今日目标

---

一、为什么 Groth16 是里程碑？

10年来仍是 proof size 最小的通用 SNARK，部署在 Tornado Cash、Filecoin、Zcash Sapling、Aztec V1。

---

二、Bilinear Pairings 速查

设 $G_1, G_2, G_T$ 是阶 $r$ 循环群，pairing $e: G_1 \times G_2 \to G_T$ 满足：

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

实例：BN254、BLS12-381（pairing crate / Arkworks）。

记 $[\alpha]_1 := g_1^\alpha \in G_1$，$[\beta]_2 := g_2^\beta \in G_2$。则 $e([\alpha]_1, [\beta]_2) = e(g_1, g_2)^{\alpha\beta}$。

---

三、QAP 复习

陈述 $x \in L \iff \exists \vec{z}$（含 public + private witness）使得：

$$ A(X) \cdot B(X) - C(X) = H(X) \cdot Z(X) $$

其中 $A, B, C$ 都是 witness $\vec{z}$ 的线性组合：

$$ A(X) = \sum_{j=0}^{n} z_j A_j(X) $$

类似 $B, C$。$Z(X) = \prod (X - r_i)$。

---

四、Groth16 协议

4.1 Trusted Setup (CRS Generation)

Toxic waste：随机选 $\alpha, \beta, \gamma, \delta, \tau \in \mathbb{F}_r$（5 个）。setup 完成后必须销毁。

CRS（Common Reference String）：

$\sigma_1 \in G_1^{\text{many}}$:

• $[\alpha]_1$
• $[\beta]_1$
• $[\delta]_1$
• ${[\tau^i]1}{i=0}^{m-1}$
• ${[\frac{\beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau)}{\gamma}]1}{j \in \text{public}}$
• ${[\frac{\beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau)}{\delta}]1}{j \in \text{private}}$
• ${[\frac{\tau^i Z(\tau)}{\delta}]1}{i=0}^{m-2}$

$\sigma_2 \in G_2^{\text{few}}$:

• $[\beta]_2$
• $[\gamma]_2$
• $[\delta]_2$
• ${[\tau^i]2}{i=0}^{m-1}$

Verifying key (vk) ⊂ CRS：

• $[\alpha]_1, [\beta]_2, [\gamma]_2, [\delta]_2$
• ${[\frac{\beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau)}{\gamma}]1}{j \in \text{public}}$

Proving key (pk)：CRS 中其余部分（含 $\delta$ 分母项 + $\tau^i$ 列）。

4.2 Prover

输入：witness $\vec{z}$（满足 QAP），以及 $H(X)$ 满足 $A(X)B(X) - C(X) = H(X)Z(X)$。

随机选 $\rho_A, \rho_B \in \mathbb{F}_r$（ZK 随机性）。

计算：

$$ [A]_1 = [\alpha]1 + \sum{j=0}^{n} z_j [A_j(\tau)]_1 + \rho_A [\delta]_1 $$

$$ [B]_2 = [\beta]2 + \sum{j=0}^{n} z_j [B_j(\tau)]_2 + \rho_B [\delta]_2 $$

$$ [B]_1 = [\beta]1 + \sum{j=0}^{n} z_j [B_j(\tau)]_1 + \rho_B [\delta]_1 $$

（$[B]_1$ 用于计算 $[C]_1$，不在 proof 中）

$$ [C]1 = \sum{j \in \text{private}} z_j \left[\frac{\beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau)}{\delta}\right]_1 + \left[\frac{H(\tau) Z(\tau)}{\delta}\right]_1 + \rho_B [A]_1 + \rho_A [B]_1 - \rho_A \rho_B [\delta]_1 $$

Proof $\pi = ([A]_1, [B]_2, [C]_1)$ — 3 group elements。

在 BLS12-381：$G_1 = 48$ bytes (compressed)，$G_2 = 96$ bytes → total = 48 + 96 + 48 = 192 bytes。

4.3 Verifier

输入：vk, public input $\vec{z}_{\text{pub}}$, proof $\pi = ([A]_1, [B]_2, [C]_1)$。

计算：

$$ [\text{IC}]1 := \sum{j \in \text{public}} z_j \left[\frac{\beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau)}{\gamma}\right]_1 $$

检查 pairing 等式：

$$ \boxed{e([A]_1, [B]_2) = e([\alpha]_1, [\beta]_2) \cdot e([\text{IC}]_1, [\gamma]_2) \cdot e([C]_1, [\delta]_2)} $$

3 个 pairing，1 个 group exponentiation per public input + 4 group additions。

4.4 正确性证明

代入 $A, B, C$ 的定义，所有交叉项被 $\alpha, \beta, \gamma, \delta$ "blind" 后只在合法 witness 时消去。具体展开（设 $\rho_A, \rho_B = 0$ 简化）：

LHS exponent = $(\alpha + \sum z_j A_j(\tau))(\beta + \sum z_j B_j(\tau))$ $= \alpha\beta + \alpha\sum z_j B_j(\tau) + \beta \sum z_j A_j(\tau) + (\sum z_j A_j)(\sum z_j B_j)$

RHS exponent = $\alpha\beta + \frac{\sum_{\text{pub}} z_j(\beta A_j + \alpha B_j + C_j)}{\gamma}\cdot\gamma + \frac{\sum_{\text{priv}} z_j(\beta A_j + \alpha B_j + C_j) + H(\tau)Z(\tau)}{\delta} \cdot \delta$

$\gamma, \delta$ 抵消后：

RHS = $\alpha\beta + \sum_{j} z_j(\beta A_j + \alpha B_j + C_j) + H(\tau)Z(\tau)$ = $\alpha\beta + \beta A(\tau) + \alpha B(\tau) + C(\tau) + H(\tau)Z(\tau)$

匹配 LHS 当且仅当 $A(\tau) B(\tau) = C(\tau) + H(\tau)Z(\tau)$ — 正是 QAP 关系在 $\tau$ 处求值！ ✓

4.5 ZK 性

随机 $\rho_A, \rho_B$ 让 $[A]_1, [B]_2$ 随机分布在 $G_1 \times G_2$（given verification check 仍能通过，唯一约束）。模拟器：在 trusted setup 中保留 $\tau$（program CRS），可不用 witness 构造 valid proof。

4.6 Knowledge Soundness

依赖 Knowledge of Exponent Assumption (KEA) 和 q-PKE / q-DLOG 假设。Groth 用 generic group model (GGM) 证明在 GGM 下 secure。

---

五、为什么只 3 个 group element？

5.1 Groth 的优化逻辑

前代 BCTV14 用 8 个 group element。Groth 16 的关键技巧：

1. 合并 alpha/beta/gamma/delta 为分母（$\gamma$ 隔离 public，$\delta$ 隔离 private + H）
2. Pairing 等式合并：把多个 check 压成一个 pairing 等式
3. $[C]_1$ 一次性 absorb 所有 private + H + ZK 项

5.2 不能再压缩了？

理论下界（Groth-Maller）：基于 KoE 的 SNARK proof ≥ 2 group element + 1 field element。Groth16 接近最优。

---

六、Trusted Setup Ceremony

6.1 单方 setup 的风险

如果一个人持有 toxic waste $\tau, \alpha, \beta$，可以任意伪造证明（破 soundness）。

6.2 MPC ceremony

多人接力，每人贡献个人 randomness $s_i$，最终 $\tau = \prod s_i$。只要至少一人诚实销毁 $s_i$，就安全。

历史 ceremony：

6.3 CRS 分两阶段

• Phase 1 (Powers of Tau): 通用，给定 ${[\tau^i]_1, [\tau^i]_2}$ 和 ${[\alpha\tau^i], [\beta\tau^i]}$
• Phase 2 (Circuit-specific): 针对具体电路，加 $\beta A_j + \alpha B_j + C_j$ 项；每电路重新做 phase 2

Phase 1 通用 → Phase 2 (per circuit) → CRS for circuit

---

七、CRS 大小估算

设电路有 $N$ 约束（$m \approx N$），$n$ 变量。

总 pk 大小：~$240 N$ bytes。$N = 10^6$ → 240 MB CRS。

---

八、代码 — Groth16 框架伪代码

"""
groth16_pseudo.py — 伪代码框架; 真实实现需要 BLS12-381 库 (py_ecc / arkworks)
"""

class Groth16:
    def __init__(self, curve_params):
        self.G1, self.G2, self.GT = curve_params

    def setup(self, qap):
        # qap: A_j, B_j, C_j polys, Z(X), public/private indices
        # 1. 选 toxic waste
        alpha, beta, gamma, delta, tau = [random_field() for _ in range(5)]

        # 2. CRS Phase 1 — Powers of Tau
        sigma1 = {
            "alpha": self.G1.mul(alpha),
            "beta": self.G1.mul(beta),
            "delta": self.G1.mul(delta),
            "tau_i": [self.G1.mul(tau**i) for i in range(qap.degree)],
        }
        sigma2 = {
            "beta": self.G2.mul(beta),
            "gamma": self.G2.mul(gamma),
            "delta": self.G2.mul(delta),
            "tau_i": [self.G2.mul(tau**i) for i in range(qap.degree)],
        }

        # 3. Phase 2 — circuit-specific
        for j in range(qap.n_vars):
            num = beta * qap.A[j].eval(tau) + alpha * qap.B[j].eval(tau) + qap.C[j].eval(tau)
            denom = gamma if j in qap.public else delta
            sigma1[f"ic_{j}"] = self.G1.mul(num / denom)

        # 4. H(X) basis
        for i in range(qap.degree - 1):
            sigma1[f"hz_{i}"] = self.G1.mul((tau**i * qap.Z.eval(tau)) / delta)

        # ⚠️ 销毁 alpha, beta, gamma, delta, tau
        del alpha, beta, gamma, delta, tau

        return (sigma1, sigma2), self._extract_vk(sigma1, sigma2, qap)

    def prove(self, pk, witness, qap):
        rho_A, rho_B = random_field(), random_field()

        A_pt = pk["alpha"] + sum(witness[j] * pk[f"A_j_{j}"] for j in range(qap.n_vars)) + rho_A * pk["delta"]
        B_pt = pk["beta_g2"] + sum(witness[j] * pk[f"B_j_g2_{j}"] for j in range(qap.n_vars)) + rho_B * pk["delta_g2"]
        # B in G1 (auxiliary, 不在 proof 中)
        B_pt_g1 = pk["beta_g1"] + sum(witness[j] * pk[f"B_j_g1_{j}"] for j in range(qap.n_vars)) + rho_B * pk["delta"]

        # H(X)
        H_poly = qap.compute_H(witness)
        HZ_pt = sum(H_poly.coeffs[i] * pk[f"hz_{i}"] for i in range(len(H_poly.coeffs)))

        # C
        C_pt = (sum(witness[j] * pk[f"ic_{j}_priv"] for j in qap.private)
                + HZ_pt
                + rho_B * A_pt + rho_A * B_pt_g1 - rho_A * rho_B * pk["delta"])

        return (A_pt, B_pt, C_pt)  # 3 group elements

    def verify(self, vk, public_input, proof):
        A_pt, B_pt, C_pt = proof
        IC = sum(public_input[j] * vk[f"ic_{j}_pub"] for j in range(len(public_input)))
        # 3 pairings
        lhs = pairing(A_pt, B_pt)
        rhs = pairing(vk["alpha"], vk["beta"]) * pairing(IC, vk["gamma"]) * pairing(C_pt, vk["delta"])
        return lhs == rhs

真实实现见 arkworks-rs/groth16 或 iden3/snarkjs。

---

九、协议关系图

   Trusted Setup (one-time per circuit)
        │
        │ choose τ, α, β, γ, δ; compute CRS
        ▼
   ┌─────────┐                         ┌─────────┐
   │   pk    │                         │   vk    │
   │ ~240 N B│                         │ small   │
   └────┬────┘                         └────┬────┘
        │                                    │
   prover (witness)                    verifier (public input)
        │                                    │
        ▼                                    │
   π = (A, B, C)  ───── 192 bytes ─────────▶ │
                                             ▼
                                   3 pairings + few muls
                                       output 0/1

---

十、历史与论文

---

十一、应用对应

EVM precompile 0x06/0x07/0x08 直接支持 BN254 pairing → Groth16 verify on-chain ~ 200K gas。

---

十二、常见陷阱

1. Toxic waste 泄露：单方持有 = 全 broken。MPC ceremony 必须
2. Per-circuit setup 烦：每改电路重做 phase 2 → 推动 PlonK universal setup
3. Public input 顺序敏感：vk 与 prover 必须一致
4. Malleability：原始 Groth16 是 malleable（可改 proof 仍 valid for same statement）；签名/绑定 sender 修复
5. Curve security：BN254 估算 ~100-bit security（去年降级），新项目用 BLS12-381 (~128-bit)
6. G2 mul 慢：prover bottleneck 之一；MSM (multi-scalar mult) 优化关键

---

十三、关键速查

---

十四、面试题

Q1: Groth16 proof 为什么只有 3 个 group element？

A1: Groth 通过分母变量 $\gamma, \delta$ 把 public/private/QAP-residual 项分隔到不同 component，然后 absorb 进 single $C$；ZK 随机性 $\rho_A, \rho_B$ 通过 cross-term 修正 $C$ 维持 verification eq；最终 $A \in G_1, B \in G_2, C \in G_1$ 即可。这接近 SNARK 理论下界。

Q2: Trusted setup 的 toxic waste 泄露后果？

A2: 任何人持有 $(\tau, \alpha, \beta)$ 可任意伪造 proof（无视 witness）—— 破坏 soundness。zk 仍保留（因为 verifier 只看 proof）。但 Bitcoin/Ethereum 上 zk-rollup 完全失去信任根基。MPC ceremony 让 "至少一人诚实" 即可。

Q3: Groth16 vs PlonK 对比？

A3: Groth16 — proof 更小（192 vs ~400 bytes），verify 更快（3 pairings vs ~6），但 per-circuit setup；PlonK — universal setup（一次 phase 1 通用），custom gates 表达力强，prover 更快（不需 R1CS-QAP）。Tornado Cash 用 Groth16，Aztec/Polygon zkEVM 用 PlonK。

Q4: 为什么 Groth16 是 "argument" 而不是 "proof"？

A4: Groth16 succinctness（proof < witness）只能在计算受限对手下保证（Gentry-Wichs 2011：信息论 succinct ZK 不可能）。安全性依赖 KEA/q-PKE 等假设，对计算无界 prover 不安全 → 是 argument。

Q5: Trusted setup ceremony 的工程难点？

A5: (1) 每参与者需安全机器，OS 隔离、电磁屏蔽防 side-channel；(2) attestation 链：每人发布对前一步的 transcript 和自己的 contribution，公开可验证；(3) 时间窗口管理（Aztec 用了几个月）；(4) 销毁 randomness 的物理证据（烧硬盘、broadcast 销毁视频）；(5) Phase 2 per-circuit 重做的 ceremony 协调成本大。

---

十五、明日预告

Day 215 — Week 32 复习：整合 SNARK 基础（ZK 定义 → Σ → FS → R1CS → QAP → Groth16），写一篇 SNARK 综述笔记。