Recursive proofs are zero-knowledge proofs that take other ZK proofs as inputs and prove their validity — enabling hierarchical proof composition where the “statement being proved” is itself “this set of proofs is valid.” This creates exponential compression: instead of settling 100 proofs individually on Ethereum (100 × 200,000 gas = 20M gas), generate one recursive proof proving all 100 are valid and settle that single proof (1 × 200,000 gas = 200,000 gas — 100× cheaper). Recursive proving is conceptually simple but technically challenging: the circuit that verifies a ZK proof is itself a large ZK circuit (100,000-1,000,000 constraints to encode a verifier), requiring efficient inner recursion. Modern approaches include accumulation schemes (Halo), folding schemes (Nova/SuperNova), recursive STARKs (StarkWare’s SHARP), and recursive PLONK (Plonky2). Recursion enables theoretically unlimited horizontal scalability — any number of transactions can be aggregated into a single proof of fixed verification cost.
Why Recursion Is Needed
Without recursion:
- 1,000 L2 transactions → 1,000 individual proofs → 1,000 × 200K gas = 200M gas (prohibitive)
With recursion:
- 1,000 transactions → 1 aggregate proof → 1 × 200K gas = 200K gas
- 1,000,000 transactions: same 200K gas! (via recursive tree)
Recursive Proving Architectures
Recursive Tree (simple):
“`
Proof₁ + Proof₂ → Proof₁₂ (proves both are valid)
Proof₁₂ + Proof₃₄ → Proof₁₂₃₄
… continues until single root proof
“`
Accumulation Scheme (Halo):
- Don’t immediately verify inner proofs
- Accumulate pending verification checks into a growing accumulator
- Single efficient check at the end of the accumulation chain
- Enables linear recursion without exponential overhead
Folding Scheme (Nova):
- Fold two proof instances into one “running instance”
- Halves the statement size at each fold
- Enables efficient SNARK recursion without large verifier circuits
Production Recursive Systems
| System | Method | Used By | Throughput |
|---|---|---|---|
| SHARP | Recursive STARK | StarkNet, StarkEx | Multiple apps |
| Plonky2 | Recursive PLONK | Polygon Zero | 170ms/proof |
| Boojum | Recursive PLONK | zkSync Era | GPU-optimized |
| Halo2 | IPA accumulation | Scroll, Zcash | Trustless |
| Nova | Folding | Research, Lurk | Fastest folding |
Nova and Folding Schemes
Nova (Microsoft Research, 2021) introduced folding schemes — a fundamentally different approach:
- Fold two instances of an NP relation into one “relaxed” instance
- The relaxed instance is provably equivalent to proving both original instances
- After many folds: one small proof (IVC — Incrementally Verifiable Computation)
- Nova is extremely fast for repeated computation patterns (like rollup state transitions)
Related Terms
Sources
- “Recursive Proof Composition Without Trusted Setup” — Bowe, Grigg, Hopwood (Zcash ECC, 2019). The Halo paper — introducing accumulation-based recursive proof composition that eliminates the need for a trusted setup in recursive zkSNARKs, foundational to modern Halo2 and Halo accumulation schemes.
- “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes” — Kothapalli, Setty, Tzialla (Microsoft Research, 2021/2022). The paper introducing Nova — a radically efficient IVC (Incrementally Verifiable Computation) scheme based on folding NP relations rather than proving verifier circuits recursively.
- “SHARP: StarkWare’s Shared Prover for Recursive STARK Aggregation” — StarkWare (2022). Operational documentation of SHARP — StarkWare’s production recursive proving infrastructure that aggregates proofs from multiple StarkEx applications and StarkNet into single Ethereum settlements.
- “Plonky2: Fast PLONK-Based Recursive Proving” — Polygon Zero Team (2022). Introduction of Plonky2 — Polygon Zero’s custom recursive proof system achieving 170ms recursive proof generation by combining PLONK with FRI polynomial commitments over the Goldilocks field.
- “IVC and NIVC: Incrementally Verifiable Computation for Blockchain” — Kothapalli, Setty (2022). Survey of IVC schemes and their blockchain application — examining how incrementally verifiable computation enables arbitrary-length computation proofs with fixed verification cost.