Halo2 — No Trusted Setup + IPA

日期: 2026-12-04 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #Halo2 #IPA #PLONKish #无可信setup

---

今日目标

---

一、Halo2 vs PlonK

Halo2 = "PLONK + IPA + recursion"。由 ECC（Electric Coin Co., Zcash 团队）开发。

---

二、Inner Product Argument (IPA)

2.1 问题

证明：$\langle \vec{a}, \vec{b} \rangle = c$（向量内积），$\vec{a}, \vec{b} \in \mathbb{F}^n$，承诺 $P = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + c \cdot U$（向量 commit）。

2.2 Bulletproofs/IPA 思路（Bowe-Grigg-Hopwood, "Halo" 2019）

每轮把向量长度减半，最终降到 $n=1$。

Round (对长度 $n$)：

1. Prover 计算 $L = \langle \vec{a}_L, \vec{b}_R \rangle U + \vec{a}_L \cdot \vec{G}_R + \vec{b}_R \cdot \vec{H}_L$，$R$ 类似（hi/lo 交叉）
2. 发 $L, R$ 给 Verifier
3. Verifier 给 challenge $u$
4. Prover 缩小向量：$\vec{a}' = \vec{a}_L + u \vec{a}_R$，$\vec{b}' = \vec{b}_L + u^{-1} \vec{b}_R$
5. 缩小 generator：$\vec{G}' = \vec{G}_L + u^{-1} \vec{G}_R$，$\vec{H}' = \vec{H}_L + u \vec{H}_R$
6. 新 $P' = u^2 L + P + u^{-2} R$

经过 $\log n$ 轮，向量缩到长度 1，prover 直接发 $(a, b)$。

2.3 Proof size & Verifier cost

• Proof: $2 \log n$ group elements + 2 field elements
• Verifier: $O(n)$（必须算最终 $\vec{G}{\text{final}}, \vec{H}{\text{final}}$）

→ 相比 KZG 大 ~10x，但无 trusted setup且 recursion friendly（pairing-free，可在椭圆曲线 base field 内高效验证）。

2.4 在多项式承诺中的用途

把多项式系数 $\vec{f} = (f_0, ..., f_{n-1})$ 视为向量，commit $[f] = \sum f_i G_i$（vector Pedersen）。Open at $z$：

• $f(z) = \sum f_i z^i = \langle \vec{f}, (1, z, z^2, ..., z^{n-1}) \rangle$
• 用 IPA 证明

→ 非 KZG 的 Polynomial Commitment Scheme (PCS)。

---

三、Halo2 PLONKish 架构

3.1 Table 结构

| Advice | Advice | Advice | Fixed | Fixed | Selector | Instance |
|   a    |   b    |   c    |  q_M  |  q_C  |   s_1    |  pub_in  |
| ...    | ...    | ...    | ...   | ...   |  ...     |  ...     |

• Advice columns: prover 填充（witness）
• Fixed columns: setup 时定（电路常量、selectors）
• Instance columns: public inputs
• Selector columns: 简单 binary selector（fixed 的子集，但效率优化）

3.2 Custom Gate Expression

Halo2 用 expression DSL 让用户写 gate constraint：

meta.create_gate("multiply", |meta| {
    let s = meta.query_selector(s_mul);
    let lhs = meta.query_advice(a, Rotation::cur());
    let rhs = meta.query_advice(b, Rotation::cur());
    let out = meta.query_advice(c, Rotation::cur());
    vec![s * (lhs * rhs - out)]
});

可访问相对 row（Rotation::next(), Rotation::prev()）→ multi-row gates。

3.3 Permutation argument

类似 PlonK 的 grand product，但 Halo2 选择 column 子集做 permutation（"equality columns"）。这降低 cost。

3.4 Lookup Argument

Halo2 lookup 比 plookup 更通用：可对任意表达式lookup（不限于 advice 列原值）。

meta.lookup("range_check", |meta| {
    let v = meta.query_advice(a, Rotation::cur());
    vec![(v, table_col)]
});

支持 multi-column lookup table（如 SHA256 SBox）。

---

四、Halo / Halo2 Recursion (Cycle of Curves)

4.1 问题

要在电路内验证另一个 proof（recursive proof），需要 verify circuit 在某域 $\mathbb{F}_q$，但 proof 涉及 $\mathbb{F}_p$ 的 EC operations → 域不匹配 → 巨大开销。

4.2 Cycle of Curves

两条曲线 $E_1, E_2$ 满足：

• $E_1$ 的 base field = $E_2$ 的 scalar field
• $E_2$ 的 base field = $E_1$ 的 scalar field

例：Pasta cycle（Pallas + Vesta），由 ECC 设计：

• Pallas: $\mathbb{F}_p$ scalar, $\mathbb{F}_q$ base
• Vesta: $\mathbb{F}_q$ scalar, $\mathbb{F}_p$ base

4.3 Recursion 流程

每个 proof 用一条曲线生成，验证电路用另一条曲线。两条曲线交替：

Proof_1 (Pallas)  ──verified by──▶  Circuit on Vesta
                                          │
                                          ▼
Proof_2 (Vesta)  ───verified by──▶  Circuit on Pallas
                                          │
                                          ▼
                                    ... 无限递归

→ 每层 proof "compress" 上一层 + 新计算。

4.4 Halo Innovation: No Trusted Setup + Sublinear Verifier (amortized)

Halo (2019) 的核心：

• IPA 验证 $O(n)$ 慢，但每次递归 fold proofs，amortize 到 $O(\log n)$
• "Accumulation scheme" 把多个 IPA 检查累积成一个，每层只需做 "mock" verify + 推迟到最后

→ 无 setup + 实用 recursion。Halo2 把这个思路嵌入 PLONK 框架。

---

五、协议关系图

   Halo2 IOP rounds
        │
   ┌───── Phase 1: commit advice cols (witness)
   │
   ├───── Phase 2: get challenge β,γ for permutation
   │      commit z(X) (grand product)
   │
   ├───── Phase 3: get α; commit lookup polys, quotient t(X)
   │
   ├───── Phase 4: get evaluation point ζ
   │      reveal evals
   │
   └───── Phase 5: IPA opening proof
        │
        ▼
   π = (commits, evals, ipa_proof)  ≈ 3-10 KB

   Verifier:
     - rebuild challenges (FS)
     - check polynomial identity at ζ
     - run IPA verify O(n) OR accumulate (Halo)

---

六、与其他系统的对比

---

七、代码 — IPA 简化教学实现

"""
ipa.py — IPA Vector Inner Product Argument 教学实现
不含 ZK; 演示算法骨架
"""
import secrets

# 简化: 在 Z_p 上, "群元素" 即标量 (实际应是 EC 点)
P = (1 << 64) - 59  # toy prime

def vec_inner(a, b):
    return sum(ai * bi for ai, bi in zip(a, b)) % P

def vec_add(a, b):
    return [(x + y) % P for x, y in zip(a, b)]

def vec_scalar(s, a):
    return [(s * x) % P for x in a]

def commit(a, G, b, H, c, U):
    """P = <a, G> + <b, H> + c·U  (用标量乘代替 EC 加)"""
    return (vec_inner(a, G) + vec_inner(b, H) + c * U) % P

def ipa_prove(a, b, G, H, U):
    """递归减半"""
    proof_L, proof_R = [], []
    while len(a) > 1:
        n = len(a)
        half = n // 2
        a_L, a_R = a[:half], a[half:]
        b_L, b_R = b[:half], b[half:]
        G_L, G_R = G[:half], G[half:]
        H_L, H_R = H[:half], H[half:]

        c_L = vec_inner(a_L, b_R)
        c_R = vec_inner(a_R, b_L)
        L = (vec_inner(a_L, G_R) + vec_inner(b_R, H_L) + c_L * U) % P
        R = (vec_inner(a_R, G_L) + vec_inner(b_L, H_R) + c_R * U) % P
        proof_L.append(L); proof_R.append(R)

        u = secrets.randbelow(P - 1) + 1  # FS challenge in real protocol
        u_inv = pow(u, -1, P)

        a = vec_add(a_L, vec_scalar(u, a_R))
        b = vec_add(b_L, vec_scalar(u_inv, b_R))
        G = vec_add(G_L, vec_scalar(u_inv, G_R))
        H = vec_add(H_L, vec_scalar(u, H_R))
    return proof_L, proof_R, a[0], b[0]

def ipa_verify(P_init, proof_L, proof_R, a_final, b_final, G, H, U):
    """在最后一步检查 P_final = a·G + b·H + ab·U"""
    P_curr = P_init
    # 注: 实际中 verifier 自己重算 challenges, 这里简化
    # 略
    return True

if __name__ == "__main__":
    n = 8
    a = [secrets.randbelow(P) for _ in range(n)]
    b = [secrets.randbelow(P) for _ in range(n)]
    G = [secrets.randbelow(P) for _ in range(n)]
    H = [secrets.randbelow(P) for _ in range(n)]
    U = secrets.randbelow(P)
    c = vec_inner(a, b)
    P_init = commit(a, G, b, H, c, U)
    proof_L, proof_R, af, bf = ipa_prove(a, b, G, H, U)
    print(f"Proof has {len(proof_L)} L's and {len(proof_R)} R's (expect {n.bit_length() - 1} = log_2(n))")
    print(f"Final scalars: a={af}, b={bf}")

---

八、历史与论文

---

九、应用对应

---

十、常见陷阱

1. IPA 验证 $O(n)$：单 proof 验证比 KZG 慢 10 倍以上；用 Halo accumulation 才 amortize
2. Cycle of curves 复杂性：写电路时要清楚自己在哪条曲线上；non-native 算术（用一条曲线模拟另一条）开销大
3. Pasta 不是 EVM-friendly：BN254 / BLS12-381 才是 precompile 兼容；Scroll 选了 BN254
4. Lookup 表大：未优化 lookup 大表（如 SHA256 全表）让 prover 内存爆炸
5. Selector 列优化：Halo2 的 selectors 必须 binary{0,1} → 工具会"selector compression" 多个 selector 合并到 fixed 列
6. Region API 易错：Halo2 region 是 thread-local，wire layout 越界 panic 不易调试

---

十一、关键速查

---

十二、面试题

Q1: Halo2 相对 PlonK 的核心优势？

A1: (1) 无 trusted setup（IPA 替代 KZG）；(2) recursion friendly（cycle of curves + accumulation）；(3) 更通用的 lookup（任意表达式）；(4) Halo accumulation 把 IPA 验证 amortize 到 $O(\log)$。代价：单 proof 验证 cost 高、size 大约 5-10x。

Q2: IPA 的 proof size 为什么 $O(\log n)$ 但 verify $O(n)$？

A2: Prover 每轮发 2 个 group elements，共 $\log n$ 轮 → proof $O(\log n)$。但 verifier 必须重新算最终 generator $\vec{G}_{\text{final}}$（受所有 challenges $u_i$ 调制），这一步是 $O(n)$ 标量乘。Halo accumulation 通过 deferred verification 让多 proof 共享这个 cost。

Q3: cycle of curves 是什么？为什么 recursion 需要它？

A3: 两条曲线 $E_1, E_2$ 互换 base/scalar field（$\text{base}(E_1) = \text{scalar}(E_2)$ 等）。Recursion 要在电路内做 EC ops，这些 ops 在曲线 base field 中"原生"高效；但 prover 算术在 scalar field。两层 proof 用两条曲线交替 → 每层都是 native ops。Pallas/Vesta (Pasta) 是 ECC 专为此设计。

Q4: Halo2 的 selector vs fixed column 区别？

A4: 都是 setup-time 固定的列。Selector 是 binary 简化情况（0/1），实现上可压缩多个 selector 进同一 fixed 列（"selector compression"）以减小 commitment cost。Fixed 列可填任意 $\mathbb{F}_p$ 值（如 PoseidonRound constants）。

Q5: 为什么 zkSync / Scroll 选 Halo2？

A5: (1) 无 trusted setup → 治理简化（无 ceremony，链升级只改电路）；(2) recursion 灵活，便于 batch 多 block；(3) 开源生态成熟（halo2 crate 文档好）；(4) BN254 friendly fork（Scroll）→ EVM precompile 兼容。代价是 verifier on-chain gas 比 Groth16 高 ~3x。

---

十三、明日预告

Day 218 — STARK 基础：Reed-Solomon + FRI + hash-based commitments，无 setup、后量子安全。StarkNet 的核心。