15. 递归、累积与折叠：Halo、Nova、HyperNova、ProtoStar

发表于 2026/07/29 更新于 2026/07/29

作者 Chen Xichao

17 分钟阅读

1. 五个经常混用的概念

1.1 Aggregation

把 $m$ 个独立 proofs

\[\pi_1,\ldots,\pi_m\]

压成一个 proof $\Pi$，证明所有 statements 成立。它不一定有时间顺序。

1.2 Recursive proof composition

外层 proof 的 relation 包含

\[\mathsf{Verify}_{\mathrm{inner}} (vk,x,\pi)=1.\]

也就是“证明一个 verifier 接受了另一个 proof”。

1.3 IVC

Incrementally Verifiable Computation 对状态转移

\[z_i=F(z_{i-1},u_i)\]

维护一个可增量更新的 proof。每来一步，只增加近似一步的工作。

1.4 PCD

Proof-Carrying Data 允许一个节点依赖多个 parent proofs，形成 DAG，而非单链。

1.5 Accumulation / Folding

不是马上验证两个完整 proofs，而是把两个待验证 claims 压成一个 accumulator claim，最后由 decider 检查。folding 通常是对某个代数 relation 的实例和 witness 做线性组合，是 accumulation 的结构化特例。

flowchart TB
    A["独立 proofs"] --> AG["aggregation"]
    R["proof 验证 proof"] --> RC["recursive composition"]
    S["状态 z_0 → z_1 → ..."] --> I["IVC"]
    D["多父节点 DAG"] --> P["PCD"]
    C["两个未决 claims"] --> F["accumulate / fold"]
    F --> O["一个未决 claim"]
    O --> DEC["最终 decider"]

2. 朴素递归：把 verifier 放进 circuit

第 $i$ 步可以证明：

\[\begin{cases} z_i=F(z_{i-1},u_i),\\ \mathsf{Verify}(vk,z_{i-1},\pi_{i-1})=1. \end{cases}\]

新 proof $\pi_i$ 因而覆盖前 $i$ 步。

sequenceDiagram
    participant P0 as Proof π_0
    participant C1 as Step circuit 1
    participant P1 as Proof π_1
    participant C2 as Step circuit 2
    participant P2 as Proof π_2
    P0->>C1: 在 circuit 内验证
    C1->>P1: 证明 step 1 + Verify(π_0)
    P1->>C2: 在 circuit 内验证
    C2->>P2: 证明 step 2 + Verify(π_1)

问题是 inner verifier 可能包含：

大字段/曲线 arithmetic；
pairing；
hash/transcript；
MSM；
proof parsing 与 subgroup checks。

若 outer circuit 的原生 field 不匹配，所有运算变成 expensive non-native arithmetic。

3. Curve cycle 与 field alignment

椭圆曲线 $E_1$ 定义在 base field $\mathbb F_{p_1}$，其 scalar field 为 $\mathbb F_{r_1}$。用 $E_1$ 的 SNARK，电路通常原生运行在 $\mathbb F_{r_1}$。

若要在另一条曲线 $E_2$ 的 circuit 中原生验证 $E_1$ 运算，希望

\[p_1=r_2,\qquad p_2=r_1.\]

这构成 curve cycle。Pallas/Vesta 是常见实例。

KZG 还需要 pairing-friendly structure，构造高效 cycle 更困难；IPA 只需普通 curve arithmetic，所以 Halo 系列能避免 pairing cycle。

4. Halo：累积昂贵的 opening checks

Halo 的关键观察不是“免费验证整个 proof”，而是把 verifier 分成：

可便宜放进 circuit 的 scalar/transcript 部分；
昂贵的 IPA / group opening check。

后者通过 accumulation 被折成一个新的 opening claim，而不是每一步在 circuit 内完全执行。最终一次检查 accumulated claim。

若 additive PCS commitments 满足

\[\operatorname{Com}(f_1+\rho f_2) = \operatorname{Com}(f_1) +\rho\operatorname{Com}(f_2),\]

随机 $\rho$ 可把两个 linear verification claims 压成一个。

flowchart LR
    P1["opening claim 1"] --> A["随机线性 accumulation"]
    P2["opening claim 2"] --> A
    A --> C["单个 accumulator"]
    C --> N["下一递归步继续累积"]
    N --> D["最终 decider"]

Halo 因而实现无 trusted setup 的实用 recursive composition；Halo Infinite 进一步用 additive polynomial commitments 组织 PCD/accumulation。其基础仍依赖椭圆曲线离散对数，不是后量子路线。

5. Hash-based / STARK recursion

STARK verifier 主要是：

small-field arithmetic；
Merkle/hash verification；
FRI folds；
Fiat–Shamir transcript。

把这些写进 AIR/PLONKish circuit，可得到 recursive STARK。若内外层使用 recursion-friendly field/hash，成本比 non-native pairing 更可控。

常见架构是树形聚合：

flowchart TB
    L1["base STARK 1"] --> R1["recursive proof A"]
    L2["base STARK 2"] --> R1
    L3["base STARK 3"] --> R2["recursive proof B"]
    L4["base STARK 4"] --> R2
    R1 --> ROOT["root recursive proof"]
    R2 --> ROOT
    ROOT --> W["可选：短 pairing-SNARK wrapper"]

最后可：

原生验证 root STARK；
再用 KZG/Groth16 类 wrapper 压成适合链上 pairing 预编译的短 proof。

wrapper 改变最终 setup/量子属性：内层透明不意味着整个发布 proof stack 仍 transparent 或 post-quantum。

6. Plonky2 / Plonky3 的位置

Plonky2 把 PLONKish ideas 与 FRI-based commitment、Goldilocks field 结合，以快速递归著称。其官方仓库截至本资料快照已标注弃用并建议迁移到 Plonky3。其 verifier-in-circuit、Merkle cap、固定高元 FRI 与 cyclic recursion 详见Plonky2 递归引擎。

Plonky3 是模块化 polynomial-IOP toolkit，包含 AIR、FRI、Circle、WHIR、lookup、sumcheck 等 primitives；它不是“Plonky2 proof 格式的简单第三版”。截至 2026-07-29，官方组织还有独立 Plonky3-recursion 项目：把固定 Plonky3 Uni/Batch-STARK verifier 编译为多 chip circuit，再用 Plonky3 Batch-STARK 证明，因而不再依赖 Plonky2 wrapper。该递归仓库仍明确标注 active development、未审计且不建议生产使用。

另有 QED Protocol 的 plonky2.5 2024 prototype，具体含义是在 Plonky2 circuit 中验证当时的 Plonky3 Uni-STARK proof；它是第三方固定 bridge，不是当前 Plonky3 的通用 proof version。详见Plonky2.5 跨系统递归桥与Plonky3 原生递归。

描述具体系统时仍需写清：

\[(\text{AIR/PLONKish},\text{PCS},\text{field}, \text{hash},\text{recursion protocol}).\]

S-two/SHARP 一类系统则走 Circle STARK 与递归聚合路线。项目状态、启用的 ZK 与 verifier generation 应以对应版本文档为准。

7. Nova 的起点：R1CS 是二次关系

R1CS instance 给出矩阵 $A,B,C$，要求 witness/public vector $\mathbf z$ 满足

\[A\mathbf z\circ B\mathbf z =C\mathbf z,\]

其中 $\circ$ 是 Hadamard product。

若两个合法 witnesses $\mathbf z_1,\mathbf z_2$，朴素地取

\[\mathbf z=\mathbf z_1+r\mathbf z_2\]

通常不再合法，因为

\[\begin{aligned} A\mathbf z\circ B\mathbf z ={}&A\mathbf z_1\circ B\mathbf z_1\\ &+r( A\mathbf z_1\circ B\mathbf z_2 +A\mathbf z_2\circ B\mathbf z_1)\\ &+r^2A\mathbf z_2\circ B\mathbf z_2. \end{aligned}\]

右侧 $C\mathbf z$ 只有关于 $r$ 的一次项，无法吸收 cross terms。

8. Relaxed R1CS

Nova 放宽 relation：

\[A\mathbf z\circ B\mathbf z =u\,C\mathbf z+\mathbf E.\]

标准 R1CS instance 是 $u=1,\mathbf E=\mathbf0$；
relaxed instance 允许 scalar $u$ 与 error vector $\mathbf E$；
这不是忽略错误，而是把 error 作为被 commitment 且受后续关系约束的状态。

设两个 relaxed instances：

\[A\mathbf z_i\circ B\mathbf z_i =u_iC\mathbf z_i+\mathbf E_i, \quad i=1,2.\]

定义 folded values：

\[\mathbf z=\mathbf z_1+r\mathbf z_2, \qquad u=u_1+ru_2.\]

展开

\[uC\mathbf z =u_1C\mathbf z_1 +r(u_1C\mathbf z_2+u_2C\mathbf z_1) +r^2u_2C\mathbf z_2.\]

令 cross term

\[\begin{aligned} \mathbf T ={}& A\mathbf z_1\circ B\mathbf z_2 +A\mathbf z_2\circ B\mathbf z_1\\ &-u_1C\mathbf z_2-u_2C\mathbf z_1, \end{aligned}\]

并定义

\[\boxed{ \mathbf E =\mathbf E_1+r\mathbf T+r^2\mathbf E_2. }\]

则逐项相减可得

\[A\mathbf z\circ B\mathbf z =uC\mathbf z+\mathbf E.\]

这就是 folding 公式的代数核心。

9. Folding protocol 的 challenge 顺序

prover 对 witnesses/errors 有 additive commitments：

\[W_i=\operatorname{Com}(\mathbf w_i),\qquad C_{E_i}=\operatorname{Com}(\mathbf E_i).\]

prover 先计算并承诺

\[C_T=\operatorname{Com}(\mathbf T),\]

transcript 再产生随机 $r$。双方公开更新：

\[\begin{aligned} W&=W_1+rW_2,\\ C_E&=C_{E_1}+rC_T+r^2C_{E_2},\\ u&=u_1+ru_2. \end{aligned}\]

若 $r$ 在 $C_T$ 前产生，作弊 prover 可针对 $r$ 选择 cross term，随机多项式 soundness 消失。

sequenceDiagram
    participant P as Prover
    participant T as Transcript
    P->>T: 两个 instances 与 commitments
    P->>T: cross-term commitment C_T
    T-->>P: random r
    P->>P: z=z_1+r z_2
    P->>P: E=E_1+rT+r²E_2
    P->>T: folded instance / witness commitment

10. Nova 如何得到 IVC

维护：

一个 running relaxed instance，表示此前所有 steps；
一个 fresh standard R1CS instance，表示新一步 $F$。

每轮：

step circuit 检查当前状态转移；
folding scheme 把 running instance 与 fresh instance 折成新的 running instance；
recursive circuit 只需检查 folding 的轻量 consistency，而不是完整 SNARK verifier。

flowchart LR
    A0["running relaxed instance U_i"] --> F["fold"]
    S["fresh step instance u_(i+1)"] --> F
    F --> A1["running relaxed instance U_(i+1)"]
    A1 --> N["下一步"]

原始 Nova 的 running relaxed accumulator 只携带常数个 relation instances/commitments，因此它的结构大小不随 step 数增长；这正是 folding 避免线性证明链的意义。但未压缩 IVC 仍不对 step circuit 的变量/约束规模 succinct：running witness、最终 satisfiability/decider 工作以及相关 commitment opening 成本仍依赖该 circuit size。

可再用 Spartan 类 SNARK 做 compression，使最终 proof 与 verifier/decider 对 step circuit size 也 succinct，并按所用后端获得相应 ZK 性质。应区分：

每步 folding 成本；
running accumulator 对 step count 的常数性；
未压缩 witness/decider 对 step circuit size 的依赖；
最终 compression prover；
final verifier/decider。

11. 为什么 folding 不等于“验证两个证明”

folding 输出的是：

一个新的 instance，如果它最终被证明/decide 为满足 relaxed relation，则除小概率外，两个输入 instances 也不能含未被发现的错误。

它通常不立即给出一个独立、公开可短验证的 SNARK proof。accumulator 把验证债务向后传，最终必须有 decider 或 compression proof。

忘记 final decider，相当于永远没有结算累计的代数声明。

12. HyperNova：从 R1CS 到 CCS

Customizable Constraint Systems 用多个 matrices $M_j$ 与集合 $S_i$ 表达

\[\sum_{i=1}^{q} c_i \left( \bigcirc_{j\in S_i}M_j\mathbf z \right) =\mathbf0.\]

它可无本质开销表示：

R1CS 的 quadratic term；
PLONKish custom gates；
AIR-style constraints。

HyperNova 给出 CCS folding：

支持 high-degree/custom constraints；
可一次 multifold 多个 instances；
prover cryptographic cost 以一个与变量数同阶的 MSM 为主；
支持 non-uniform IVC，让不同指令使用不同小 circuits，而非每步支付最大 universal circuit。

其底层用 multilinear polynomial/sumcheck 处理高次 cross terms，而不是为 degree $d$ 手工列出所有二项展开。

13. ProtoStar：从 special soundness 得到通用 accumulation

ProtoStar 观察到许多 polynomial protocols 是 special-sound public-coin protocols。它给出 generic accumulation compiler，把多个 transcript/claims 压成一个。

对 PLONKish：

支持 high-degree gates；
支持 vector lookup；
recursive circuit 主要依赖 protocol rounds 与 verifier equation degree，而非完整 proof size；
不要求 trusted setup/pairing；
per-step prover 不需要 FFT。

它与 Nova 的差别：

Nova 首先为 relaxed R1CS/CCS 构造 relation-specific folding；
ProtoStar 从 special-sound protocol 的 algebraic verification equations 构造 accumulation；
两者都把昂贵“现在验证”改为便宜“压成一个待决 claim”。

14. Halo、Nova、HyperNova、ProtoStar 对比

方案	被压缩对象	主要代数工具	每步避免了什么	最终仍需要
Halo	PCS opening / verifier claims	IPA、additive commitments	完整 group opening check	accumulator decider
Nova	relaxed R1CS instances	cross-term folding	circuit 内完整 SNARK verifier	可选 SNARK compression
HyperNova	relaxed CCS instances	multilinear sumcheck + folding	universal max-size step circuit	decider/compression
ProtoStar	special-sound protocol claims	generic accumulation	proof-size相关递归 verifier	decider
recursive STARK	整个 inner verifier	AIR/FRI/hash	依实现，常靠 field/hash alignment	root verifier 或 wrapper

15. Non-uniform IVC 的意义

zkVM 有许多 instructions：

\[F_{\mathrm{add}},F_{\mathrm{mul}},F_{\mathrm{load}},\ldots\]

朴素 uniform IVC 把所有指令放进一个大 step circuit，通过 selector 启用一个分支；每一步都为最大 circuit 付费。

non-uniform IVC 允许每步选择一个小 circuit，并证明：

被选 circuit 属于允许集合；
上一步状态与这一步输入链接；
running accumulator 覆盖所有异构步骤。

这与 AIR 的 opcode selectors、lookup-based VM 是另一种计算组织方式。

16. 递归里的 zero-knowledge

递归/折叠首先解决完整性与增量成本，不自动提供隐私：

running accumulator 可能是 witness 的线性函数；
relaxed error commitment 可能在多步间关联；
inner proof 的 public inputs 可能泄露中间状态；
deterministic folding randomness 会链接 sessions。

ZK IVC 通常需要：

hiding vector commitments；
随机 instance folding / rerandomization；
final ZK compression；
对整条状态链定义清楚哪些状态公开。

“最终 proof 很短”与“中间状态被隐藏”完全是两件事。

17. Soundness 与实现边界

17.1 base case

递归链必须有明确 genesis：

\[\mathsf{base}=1\]

时不验证 previous proof，但要约束 initial state。若 selector 未约束为 boolean，prover 可混合 base/recursive 分支。

17.2 state continuity

必须证明

\[z_{\mathrm{out},i} =z_{\mathrm{in},i+1}.\]

只证明每个 step 独立有效，不能证明它们组成同一执行。

17.3 deferred checks

所有 accumulated equations 必须进入下一 accumulator，最终 decider 必须验证正确 VK/domain。漏一项会形成“永不结算的债务”。

17.4 nested transcripts

inner/outer proof 的：

protocol IDs；
recursion depth；
VK digests；
accumulator types；
public states；

必须 domain-separated。避免把 inner proof bytes 在外层以含糊方式重解释。

17.5 field/curve edge cases

non-native modular reduction、incomplete elliptic formulas、point at infinity、subgroup checks和 scalar decomposition 都是高风险区域。递归 circuit 中的 curve checker 必须与 native verifier 接受集合完全一致。

18. 选型视角

长期顺序计算、每步 circuit 稳定：Nova 类 IVC。
多种小指令 circuits：HyperNova/non-uniform folding。
已有 PLONKish special-sound protocol，需 lookup/high-degree gate folding：ProtoStar 类。
IPA-PLONKish stack：Halo accumulation。
AIR/hash stack、批量 block proofs：recursive STARK tree。
只需一次性 batch 多个 proofs：aggregation 可能比 IVC 更简单。

19. 边界与审计清单

目标是 aggregation、IVC 还是 PCD，安全 statement 写清了吗？
base case selector 是否 boolean，initial state 是否绑定？
step-to-step public state 是否连续？
cross-term commitment 是否早于 folding challenge？
relaxed error/accumulator 是否每轮完整携带？
最终 decider/compression 是否真实执行？
inner verifier 与 recursive circuit 的接受条件是否 bit-for-bit 等价？
curve points、subgroups、infinity 和 non-native reductions 是否完整约束？
inner/outer transcripts 是否 domain-separated 并绑定 VK/depth/state？
ZK 是否覆盖 running accumulator 与中间 states？
failure probability 随 steps/树节点如何组合？
wrapper 是否改变 setup 与 post-quantum 安全结论？

20. 自测

展开 $A(z_1+rz_2)\circ B(z_1+rz_2)$ 并推导 $\mathbf T$。
为什么 relaxed error $\mathbf E$ 不是“允许不满足约束”？
folding challenge 为何必须晚于 cross-term commitment？
区分 running accumulator 与最终 succinct proof。
Halo accumulation 与 Nova folding 分别压缩什么对象？
recursive STARK 外包一层 KZG-SNARK 后，哪些安全属性发生改变？

参考

Bowe、Grigg、Hopwood，Halo
Bowe 等，Halo Infinite
Kothapalli、Setty、Tzialla，Nova
Kothapalli、Setty，HyperNova
Chen、Bünz，ProtoStar
Microsoft Nova 官方仓库
Plonky2 官方仓库及弃用说明
Plonky3 官方仓库
Starknet 文档：SHARP

上一篇：Circle STARK 与现代哈希型 PCS · 下一篇：Plonky 系列对照与迁移 · 返回：总目录

zero-knowledge, stark

本文由作者按照 CC BY 4.0 进行授权