Recursion — Halo, Mina, Nova

日期: 2026-12-08 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #Recursion #Nova #Mina #Halo

---

今日目标

---

一、为什么需要递归？

1.1 三大动机

1. IVC (Incremental Verifiable Computation)：长 trace 分步证（每步小 proof），最后 1 个 proof 涵盖全部
2. PCD (Proof-Carrying Data)：分布式计算，每个节点把上游 proof + 自己计算 fold 成新 proof
3. Rollup batching：每个 block 一个 proof, 终态合成单个 proof 上链

1.2 朴素递归的痛点

直接在电路 $C_2$ 内验证 proof $\pi_1$（生成自电路 $C_1$），需要把 verifier algorithm 编为电路。

• 若用 SNARK：verify 涉及 pairing → 大量 EC ops in scalar field → non-native arithmetic，膨胀 50-100x
• 若用 STARK：verify 涉及 hash + 小 field FFT → 较友好，但仍非平凡

→ 需要专门设计的递归友好 SNARK。

---

二、Cycle of Curves

2.1 定义

两条 elliptic curves $E_1 / \mathbb{F}_p$, $E_2 / \mathbb{F}_q$ 满足：

• $#E_1(\mathbb{F}_p) = q$（$E_1$ 群阶 = $E_2$ 域大小）
• $#E_2(\mathbb{F}_q) = p$（互换）

→ $E_1$ 的 scalar field = $E_2$ 的 base field，反之亦然。

2.2 已知 cycles

(BN254 + Grumpkin 是"half-cycle"：Grumpkin 的 scalar field = BN254 base field，但反向不成立)

2.3 Recursion 流程

   E_1 上电路 C_1 → proof π_1 (在 E_1)
                          │
                          ▼
   E_2 上电路 C_2 验证 π_1
   C_2 内 EC ops 在 E_2 base field = E_1 scalar field → native
                          │
                          ▼
   C_2 输出 proof π_2 (在 E_2)
                          │
                          ▼
   E_1 上电路 C_3 验证 π_2 (native)
        ... 无限交替

每层 proof "compress" 上层 + 自己电路。

---

三、Halo Accumulation (Halo 2019)

3.1 思路

完整 IPA verify 是 $O(N)$，太慢嵌入电路。Halo 的关键：

不每次完整 verify，而是 "accumulate" 到一个累加器。最后只 verify 一次累加器。

3.2 Accumulator 结构

每次有新 proof $\pi_i$ 时：

1. 部分 verify（cheap parts）— 链上 / 电路内做
2. 把 expensive parts（$O(N)$ MSM）"deferred" 到 accumulator
3. Accumulator 是几个 group elements，可被下一轮再 fold

最后调用一次 "decider" 验证 accumulator → 全 amortized $O(\log)$。

3.3 ECC 的 Halo2 实现

Pallas (over $F_p$) → 生成 proof 1 Vesta (over $F_q$) → verify proof 1 + 生成 proof 2 ... 交替

每条曲线的 accumulator state 各自维护，互相 fold。

---

四、Nova Folding Scheme (2021)

4.1 革命性洞察

不需要 SNARK 的 succinctness 来做 IVC。直接 fold relaxed R1CS instances，最后用一次 SNARK closes the loop。

4.2 Relaxed R1CS

标准 R1CS：$Az \circ Bz = Cz$。

Relaxed R1CS 引入 slack：

$$ Az \circ Bz = u \cdot Cz + E $$

其中 $u \in \mathbb{F}$ 是 scalar，$E$ 是 error 向量。当 $(u, E) = (1, 0)$ 退化为标准 R1CS。

4.3 Folding Two Instances

给两个 relaxed R1CS instances $(\vec{z}_1, u_1, E_1)$ 和 $(\vec{z}_2, u_2, E_2)$，folding 输出第三个 instance $(\vec{z}, u, E)$：

$$ \vec{z} = \vec{z}_1 + r \vec{z}_2, \quad u = u_1 + r u_2 $$

$$ E = E_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1 - u_1 C z_2 - u_2 C z_1) + r^2 E_2 $$

其中 $r$ 是 verifier challenge（FS）。

关键 Lemma：若两个原 instances 都 valid，且 prover 在挑战前 commit 到 cross-term $T$，则 folded instance 也 valid（with overwhelming prob）。

4.4 IVC via Nova

Step i:
   (acc_{i-1}, π_{i-1}) ← 已有累加 instance + commitment proof
   compute step i: z_{i-1} → z_i
   produce relaxed R1CS instance (z_i, 1, 0)
   fold (acc_{i-1}, new_instance) → acc_i
   commit to acc_i

每步 cost: $O(|C|)$ where $|C|$ = step circuit size。无需 SNARK！只 Pedersen commit + cross-term。

最后做 1 次 SNARK（如 Spartan）证明 final accumulator 是 valid → succinct closure。

4.5 复杂度

→ 适合长 trace（zkVM 跑 1B steps 之类）。

4.6 SuperNova / HyperNova

• SuperNova (2022): 支持多种 step circuits（"NIVC"），用 selector
• HyperNova (2023): 用 multilinear / sumcheck 替代 R1CS，更紧凑
• ProtoStar (2023): 通用化 folding

---

五、Mina — 22 KB 区块链

5.1 设计

每个 Mina 区块包含：

• 验证前一区块 SNARK proof
• 自身交易（用 SNARK 证）
• 输出 SNARK proof for "整个链 valid up to here"

→ 区块链 state size = 常数 ~22 KB（仅 final proof + state root）。

5.2 实现

• Pickles 系统：基于 Halo2-style PlonK + IPA + Pasta cycle
• 每个 block 一次递归
• Verifier (light client) 只需 22 KB 即可信任整条链

5.3 Trade-off

• 优势：极致 light client，端到端可验证
• 代价：每 block 一次完整 SNARK proving，prover throughput 低 → TPS 受限

---

六、应用对应

---

七、Recursion 设计选择对比

---

八、代码 — 简化 Nova Folding 演示

"""
nova_fold.py — 极简 Folding Scheme 教学
不含 EC, 不含 commitment; 演示 relaxed R1CS folding 的代数核心
"""
import secrets
import numpy as np

P = (1 << 31) - 1

def hadamard(a, b, mod=P):
    return (np.array(a) * np.array(b)) % mod

def fold_instances(A, B, C, inst1, inst2):
    """
    inst = (z, u, E)
    fold via random r
    """
    z1, u1, E1 = inst1
    z2, u2, E2 = inst2
    r = secrets.randbelow(P)
    
    # cross-term T
    Az1 = (A @ z1) % P
    Bz1 = (B @ z1) % P
    Az2 = (A @ z2) % P
    Bz2 = (B @ z2) % P
    Cz1 = (C @ z1) % P
    Cz2 = (C @ z2) % P
    T = (hadamard(Az1, Bz2) + hadamard(Az2, Bz1)
         - u1 * Cz2 - u2 * Cz1) % P
    
    # folded instance
    z = (np.array(z1) + r * np.array(z2)) % P
    u = (u1 + r * u2) % P
    E = (np.array(E1) + r * np.array(T) + (r * r) * np.array(E2)) % P
    
    # verify folded relaxed R1CS:  Az ∘ Bz == u·Cz + E
    Az = (A @ z) % P
    Bz = (B @ z) % P
    Cz = (C @ z) % P
    lhs = hadamard(Az, Bz)
    rhs = (u * Cz + E) % P
    valid = np.array_equal(lhs, rhs)
    return (z, u, E), r, valid

# Toy R1CS: x^2 = 9 (single constraint)
# vars: (1, x, x_sq), constraint: x*x = x_sq + boundary x_sq=9
# 简化: 一个约束 x*x = x_sq
def toy_r1cs():
    A = np.array([[0, 1, 0]])
    B = np.array([[0, 1, 0]])
    C = np.array([[0, 0, 1]])
    return A, B, C

if __name__ == "__main__":
    A, B, C = toy_r1cs()
    # 两个 valid instances
    z1 = np.array([1, 3, 9])  # 3^2 = 9
    z2 = np.array([1, 4, 16]) # 4^2 = 16
    inst1 = (z1, 1, np.array([0]))
    inst2 = (z2, 1, np.array([0]))
    
    folded, r, ok = fold_instances(A, B, C, inst1, inst2)
    print(f"Random challenge r = {r}")
    print(f"Folded z = {folded[0]}")
    print(f"Folded u = {folded[1]}")
    print(f"Folded E = {folded[2]}")
    print(f"Folded instance valid? {ok}")

预期 valid = True — 演示 folding 保持 relaxed R1CS satisfaction。

---

九、协议关系图

┌──────────────────────────────────────────────┐
│              Recursion Methods               │
├──────────────────────────────────────────────┤
│  1. Cycle of curves (Halo, Mina, Halo2)      │
│  2. Halo accumulation (defer expensive ops)  │
│  3. Nova folding (relaxed R1CS, no SNARK/step)│
│  4. STARK recursion (hash-friendly)          │
└──────────────────────────────────────────────┘
                  │
        ┌─────────┴───────────┐
        │                     │
   IVC: Step → Step      PCD: distributed
        │                     │
   Mina blocks            Filecoin sectors
   zkVM long trace        Multi-prover rollups

---

十、历史与论文

---

十一、常见陷阱

1. Cycle of curves 安全等级：Pasta ~125-bit；MNT4/MNT6 ~80-bit（不安全已弃用）
2. Non-native arithmetic 仍贵：某些 ops 仍需要在"另一个 field"模拟（如 hash 用 Poseidon over native field 而非 SHA）
3. Folding 不是 SNARK：Nova 每步无 succinct proof，要 final SNARK closure
4. Nova memory 大：witness $\vec{z}$ 在内存累积，长 trace 用 streaming 优化
5. PCD 的 trust assumption：多 prover 协作时每方 honesty 决定整体安全；恶意 prover 可"插入" fake 子计算
6. Recursion overhead：每次包装电路约 5-50K 约束（验证 inner proof），不可忽略

---

十二、关键速查

---

十三、面试题

Q1: Nova 的 folding scheme 为什么"不需要 SNARK per step"？

A1: 传统 IVC 每步用 SNARK proof (succinct) 验证上一步 + 新计算。Nova 观察：如果只想"最后一次 verify"，每步无需 succinct proof，只需 fold 两个 relaxed R1CS instances 成新 instance（保持 satisfiability）。每步 cost = Pedersen commit + cross-term，远小于一次 SNARK。最后做 1 次 SNARK closure 给 succinct final proof。

Q2: Cycle of curves 为什么对 recursion 关键？

A2: Recursion 电路要做 EC operations (ScalarMult, AddPoint) 验证 inner proof。这些 ops 在曲线 base field 中"native"。Cycle 让两条曲线交替，每层 proof verify 在另一层是 native arithmetic，避免 50x 开销 non-native simulation。Pasta cycle (Pallas + Vesta) 是 ECC 团队为 Halo2 / Mina 专门设计。

Q3: Mina 22 KB 区块链怎么做到的？

A3: 每个 block 包含：(a) 前一 block 的 SNARK proof，(b) 当前 block 交易的 SNARK proof，(c) 输出 single SNARK proof "整条链 up to here valid"。light client 只需保存最新 22 KB（最新 proof + state root），不需要历史 block。代价：prover throughput 低（每 block 全 recursion 耗时数分钟）→ TPS 限制。

Q4: Halo accumulation 与 Nova folding 区别？

A4: Halo accumulation: defer IPA verification（保留 expensive part 到累加器，最后 decider verify）；每步 cost 含 partial SNARK ops。Nova folding: 直接 fold R1CS instances（relaxed form），无 SNARK ops 在 step；每步 cost = MSM only。Nova 更轻，但需要 final SNARK closure；Halo 完成度高（直接出 SNARK），但 step 较重。

Q5: zkVM 用 recursion 的典型架构？

A5: (1) 把 RISC-V trace 分段，每段一个 small proof（STARK 或 R1CS）；(2) 用 Nova / STARK recursion 把多段 fold 成单 proof；(3) 最后用 outer Groth16 wrap 成 196-byte proof on-chain。Risc Zero 用 STARK + Groth16; Lasso/Jolt 用 sumcheck + Nova-style folding。这种 hybrid 平衡 prover 速度（fast inner）与 on-chain cost（cheap outer）。

---

十四、明日预告

Day 222 — Week 33 + 整个 ZK 理论复习：综合 Day 209-221，整理完整 ZK 理论笔记 — 这是 Phase 4 ZK 部分的总结。