Week 32 复习 — SNARK 基础整合

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

---

今日目标

---

一、SNARK 全景图

                    ZK 定义 (Day 209)
                Completeness/Soundness/ZK
                          │
                          ▼
              Σ-协议 (Day 210)
              Schnorr ID, 3-round, HVZK, Special Sound
                          │
                          ▼
              Fiat-Shamir (Day 211)
              交互 → 非交互 (NIZK), ROM
                          │
       ┌─────────────────┴────────────────┐
       │                                  │
   特殊语言                          通用 NP 语言
   (DL, RSA, ...)                   (任意电路)
       │                                  │
       ▼                                  ▼
   Schnorr Sig                    R1CS / 算术电路 (Day 212)
   Ring sig                              │
                                         ▼
                              QAP — Lagrange (Day 213)
                              A(X)B(X) - C(X) = H(X)Z(X)
                                         │
                                         ▼
                              Groth16 (Day 214)
                              3-element proof, pairings

---

二、知识链路（10 步）

1. ZK 定义：完备 + 可靠 + 模拟器范式（GMR 1985）
2. HVZK：仅诚实 verifier 时可模拟；Σ-协议自然满足
3. Σ-协议：3 轮 (commit, challenge, respond) + special soundness
4. Schnorr：DL 上的 Σ-协议；nonce 重用 = 私钥泄露
5. Fiat-Shamir：用 $H(\cdot)$ 替 verifier 随机 → NIZK；ROM 下 secure
6. Forking Lemma：FS 安全归约到 special soundness（Pointcheval-Stern）
7. 算术电路：变量在 $\mathbb{F}_p$；门 ∈ {+, ×}；可表达任意 NP
8. R1CS：每行一个 rank-1 quadratic constraint
9. QAP：Lagrange 插值把 R1CS 矩阵变多项式；整除关系替代 m 个标量约束
10. Groth16：QAP + pairing + trusted setup → 192-byte proof, 3-pairing verify

---

三、术语速查

---

四、一句话回答 5 大问题

Q1: ZK 是什么？

A: 一个交互式协议让 prover 向 verifier 证明 $x \in L$，同时 verifier "学不到 $x \in L$ 之外任何信息"——形式化为模拟器范式：存在 PPT 模拟器在不知 witness 的情况下生成不可区分的 view。

Q2: 怎么把交互协议变非交互？

A: Fiat-Shamir 变换：用密码哈希 $H(\text{statement} | \text{commitment})$ 代替 verifier 的真随机 challenge。在 Random Oracle Model 下安全（forking lemma）。

Q3: 怎么证 NP 的任意陈述？

A: 把陈述编码为算术电路，flatten 为 R1CS，Lagrange 插值变 QAP，最终用 pairing-based commitment 做 succinct proof。

Q4: Groth16 为什么 192 bytes？

A: 3 个 group element：$A \in G_1$ (48B), $B \in G_2$ (96B), $C \in G_1$ (48B)。通过 $\alpha\beta\gamma\delta$ 分母变量把 public/private/H 项 absorb 进 $C$。

Q5: trusted setup 安不安全？

A: 单方 setup 危险（toxic waste 泄露 = soundness 破）。MPC ceremony（多方接力 + 公开 transcript）让"1-of-N 诚实"即够，已成业界标准（Powers of Tau, Aztec MPC, Filecoin）。

---

五、SNARK 系统对比预览

（详见 Day 219）

---

六、自检题（10 道）

1. Statistical ZK 与 Computational ZK 区别？哪个更强？ 2. Soundness 与 Knowledge Soundness 的差别？SNARK 需要哪个？ 3. 为什么 Schnorr 协议只 3 轮？4 轮可以吗？ 4. Fiat-Shamir 中 weak FS 攻击的本质？ 5. R1CS 中"每行一个乘法门"为什么充分？ 6. QAP 中目标多项式 $Z(X)$ 的根是什么？degree 多少？ 7. Groth16 verifier 检查的 pairing 等式？ 8. 为什么 Groth16 proof 需要 $\alpha, \beta$ 项？ 9. trusted setup ceremony 的 1-of-N 诚实假设含义？ 10. R1CS witness 中的 "1" 占位符为什么必要？

简答

1. Statistical 即使无限计算 verifier 也学不到；Computational 仅 PPT verifier 不可区分。前者更强。
2. Soundness 只保证 $x \in L$；KS 保证 prover 知道 witness。SNARK 都需要 KS（zk-rollup 必须 prover 真"知道" state transition）。
3. 3 轮够：commit → challenge → respond。Special soundness 需要"同一 commitment, 不同 challenge"两份 transcript。多轮可降可靠性，但增加交互成本。
4. weak FS 漏掉 commitment / statement 进哈希 → 攻击者后选 $a$ 反推 witness（HVZK 模拟器变 forger）。Frozen Heart attack 2022 真实案例。
5. 任意算术电路可 flatten 成 SSA：每行 $a \cdot b = c$。加法/线性组合不增行（embed 进 A, B, C 行向量）。
6. $Z(X) = \prod_i (X - r_i)$，根是 $r_1, ..., r_m$（evaluation points），degree = $m$（约束数）。
7. $e(A, B) = e(\alpha, \beta) \cdot e(\sum_{\text{pub}} z_j \cdot \text{IC}_j, \gamma) \cdot e(C, \delta)$（in $G_T$）
8. $\alpha, \beta$ 是 "consistency check"：保证 prover 用了正确的 $A_j, B_j, C_j$ 组合（来自 setup），而不是任意构造的 $A, B, C$。这就是 Groth16 防止"non-malicious-but-wrong" prover 的核心。
9. 至少一个参与者诚实销毁了自己的 randomness $s_i$。即使 N-1 人合谋，仍无法重构总的 toxic waste $\tau = \prod s_i$。
10. R1CS 中常数项（如 "1*x = w" 中的 "1"）需要被 $\vec{z}$ 表达；约定 $z_0 = 1$ 让常数变成 "$z_0 \cdot x$"，统一写成线性组合。

---

七、概念地图（mermaid）

flowchart TB
  A[ZK 三性质] --> B[Σ-协议]
  B --> C[Schnorr ID]
  C --> D[Fiat-Shamir]
  D --> E[Schnorr Signature]
  D --> F[Generic NIZK]
  G[算术电路] --> H[R1CS]
  H --> I[QAP via Lagrange]
  I --> J[Groth16]
  F -.- J
  J --> K[Tornado Cash, Filecoin, Zcash]

---

八、面试热点速答

"Walk me through how Groth16 works, end-to-end":

1. PM/Dev 写电路（Circom 等 DSL）
2. 编译为 R1CS 矩阵 $(A, B, C)$
3. 通过 Lagrange 插值得到 QAP ${A_j(X), B_j(X), C_j(X), Z(X)}$
4. Trusted setup ceremony 生成 CRS：随机 $\tau, \alpha, \beta, \gamma, \delta$，发布 powers $[\tau^i]_{1,2}$ 和组合项
5. Prover 给定 witness $\vec{z}$：构造 $A(X), B(X), C(X), H(X)$，commit 到 CRS 给出 $\pi = ([A]_1, [B]_2, [C]_1)$
6. Verifier 用 vk 检查 $e(A, B) = e(\alpha, \beta) \cdot e(\text{IC}, \gamma) \cdot e(C, \delta)$
7. 该等式 hold iff QAP 关系在 $\tau$ 处满足 → Schwartz-Zippel 给可靠性 (negl error)
8. proof 大小 192 bytes, on-chain verify ~200K gas

---

九、常见误解清单

---

十、推荐进一步阅读

---

十一、明日预告

Day 216 — PlonK：universal setup, custom gates, plookup — 继 Groth16 之后的"第二代"通用 SNARK，目前最流行。