Recursive ZK Proofs: Proving Proofs for Scalability

Recursive ZK proofs are proofs that verify other proofs. This seemingly circular concept enables remarkable scalability: compress unlimited computation into a single, constant-size proof.

The Recursion Concept

Consider a chain of proofs:

• Proof₁ verifies computation C₁
• Proof₂ verifies C₂ AND that Proof₁ is valid
• Proof₃ verifies C₃ AND that Proof₂ is valid
• ...

The final proof verifies the entire chain. A verifier checking Proof₃ confirms C₁, C₂, and C₃—all at once, in constant time.

How It Works

The circuit for recursive verification:

template RecursiveStep() {
  // Previous proof (public)
  signal input previousProof;
  signal input previousPublicInputs;

  // New computation (private)
  signal private input newComputation;

  // Output
  signal output newAccumulatedState;

  // 1. Verify previous proof
  component verifier = Verifier();
  verifier.proof <== previousProof;
  verifier.publicInputs <== previousPublicInputs;
  verifier.valid === 1;

  // 2. Execute new computation
  component step = ComputationStep();
  step.previousState <== previousPublicInputs.state;
  step.input <== newComputation;

  // 3. Output new state
  newAccumulatedState <== step.newState;
}

Technical Challenges

Verification Circuit Size

The SNARK verifier itself must be expressed as a circuit. For SNARKs with pairing operations, this is expensive.

Solutions:

• Cycles of curves (one curve's verifier efficient in another)
• Accumulation schemes (defer verification)
• Folding schemes (combine instances without full verification)

Accumulation and Folding

Modern approaches avoid full verification at each step:

Accumulation: Collect verification obligations, check all at end

Folding: Combine multiple instances into one of same size

These dramatically reduce per-step overhead.

Applications

Blockchain Scaling (Rollups)

• Aggregate thousands of transactions
• Single proof posted to main chain
• Constant verification regardless of batch size

Incrementally Verifiable Computation (IVC)

• Long-running computations with periodic checkpoints
• Anyone can verify current state quickly
• No need to re-execute entire history

Proof Aggregation

• Combine proofs from different sources
• Single verification confirms all
• Efficient for batch verification

Notable Systems

• Nova: Efficient folding scheme for R1CS
• Halo: Recursive proofs without trusted setup
• Plonky2: Very fast recursive proofs
• Mina: Constant-size blockchain using recursion

Performance

Recursive proof systems achieve:

• Each step: ~1-10 seconds proving time
• Final verification: milliseconds (constant)
• Proof size: constant regardless of depth

Recursive ZK proofs unlock unlimited scalability. Verify a billion operations with the same cost as verifying one.