Recursive Proving

Understanding RISC Zero’s recursive proving system for unbounded computation and proof aggregation

Recursive Proving

RISC Zero’s zkVM uses recursive proving to achieve:

• Unbounded computation size through continuations
• Constant proof size regardless of program complexity
• Proof aggregation combining multiple proofs
• Proof composition for modular verification

Overview

Recursive proving allows the zkVM to prove that it correctly verified another proof. This enables:

1. Breaking large computations into segments
2. Verifying each segment independently
3. Combining segment proofs into a single proof
4. Compressing the final proof for efficient on-chain verification

The Prover::prove_with_opts method allows choosing between composite, succinct, or Groth16 receipts.

Recursive Proving Process

The end-to-end proving process consists of several stages:

1. Execution
2. The program executes in the zkVM, producing a collection of Segments. Programs are automatically split into segments if they exceed the segment size limit.
3. Segment Proving
4. Each segment is proven independently, generating a SegmentReceipt. This uses the RISC-V circuit to prove correct execution.
5. Lifting
6. Each SegmentReceipt is lifted to the recursion circuit, producing a SuccinctReceipt. This is the first recursion step.
7. Joining
8. Pairs of SuccinctReceipts are joined together repeatedly until only one SuccinctReceipt remains. This aggregates all segments into a single proof.
9. Identity Transform
10. The final SuccinctReceipt is passed through identity_p254, which prepares it for Groth16 proving using the Poseidon254 hash function.
11. Compression (Optional)
12. The SuccinctReceipt is compressed into a Groth16Receipt (~200 bytes) for efficient on-chain verification.

Circuit Architecture

RISC Zero’s zkVM consists of three circuits:

1. RISC-V Circuit

A STARK circuit that proves correct execution of RISC-V programs. This is the main circuit that executes your guest code.

2. Recursion Circuit

A separate STARK circuit optimized for:

• Verifying other STARK proofs
• Cryptographic operations
• Integrating custom accelerator circuits

The Recursion Circuit has:

• Fewer columns than the RISC-V circuit
• Instruction set optimized for cryptography
• Same underlying proof system as RISC-V circuit

3. STARK-to-SNARK Circuit

An R1CS circuit (Groth16) that verifies proofs from the Recursion Circuit, producing tiny proofs suitable for blockchain verification.

The Recursion Circuit is like a specialized CPU designed specifically for verifying cryptographic proofs efficiently.

Recursion Programs

The Recursion Circuit supports several programs used internally:

Lift

Verifies a STARK proof from the RISC-V circuit using the Recursion circuit. This produces a proof with constant verification time regardless of the original segment length.

// Automatically used by the prover
let segment_receipt = prover.prove_segment(segment)?;
let succinct_receipt = lift(segment_receipt)?;

Join

Verifies two STARK proofs from the Recursion circuit, combining them into one. By repeated application, any number of receipts can be compressed into a single receipt.

// Automatically applied to combine segments
let receipt1 = lift(segment1)?;
let receipt2 = lift(segment2)?;
let combined = join(receipt1, receipt2)?;

Identity_p254

Verifies a STARK proof using the Poseidon254 hash function. This is the last step before Groth16 proving, ensuring compatibility with the SNARK circuit.

// Prepares for Groth16 compression
let prepared = identity_p254(succinct_receipt)?;
let groth16 = compress(prepared)?;

Resolve

Used for proof composition to remove assumptions from receipt claims, enabling modular proof verification.

Receipt Types

CompositeReceipt

Contains all segment receipts without any recursion. Fastest to generate but largest in size.

• Size: ~200 KB per segment
• Use case: Development, local testing
• Verification: Verify each segment independently

use risc0_zkvm::{default_prover, ExecutorEnv, ProverOpts, ReceiptKind};

let env = ExecutorEnv::builder().build().unwrap();
let opts = ProverOpts::default().with_receipt_kind(ReceiptKind::Composite);
let receipt = default_prover().prove_with_opts(env, GUEST_ELF, &opts)?;

SuccinctReceipt

Fully recursed STARK proof, constant size regardless of program complexity.

• Size: ~200 KB (constant)
• Use case: Off-chain verification, proof aggregation
• Verification: Single constant-time verification

let opts = ProverOpts::default().with_receipt_kind(ReceiptKind::Succinct);
let receipt = default_prover().prove_with_opts(env, GUEST_ELF, &opts)?;

Groth16Receipt

SNARK proof suitable for on-chain verification.

• Size: ~200 bytes
• Use case: Blockchain verification
• Verification: Verify on-chain via RISC Zero verifier contract

let opts = ProverOpts::default().with_receipt_kind(ReceiptKind::Groth16);
let receipt = default_prover().prove_with_opts(env, GUEST_ELF, &opts)?;

// Convert to Groth16 if you already have a SuccinctReceipt
let groth16_receipt = receipt.compress()?;

Groth16 compression requires additional setup and is significantly slower than generating a SuccinctReceipt. Only use it when you need on-chain verification.

Practical Examples

Basic Recursive Proving

use risc0_zkvm::{default_prover, ExecutorEnv, ProverOpts};

// Build execution environment
let env = ExecutorEnv::builder()
    .write(&input_data).unwrap()
    .build()
    .unwrap();

// Prove with default options (Succinct receipt)
let receipt = default_prover().prove(env, GUEST_ELF)?;

// The receipt is automatically:
// 1. Segmented during execution
// 2. Each segment proven
// 3. Lifted to recursion circuit
// 4. Joined into single proof

// Verify the receipt
receipt.verify(GUEST_ID)?;

Aggregating Multiple Proofs

use risc0_zkvm::recursion::Prover;
use risc0_zkvm::sha::Digest;

// Prove multiple independent computations
let receipt1 = default_prover().prove(env1, GUEST_ELF_1)?;
let receipt2 = default_prover().prove(env2, GUEST_ELF_2)?;

// Extract claims (commitments to the computation)
let claim1 = receipt1.get_claim()?;
let claim2 = receipt2.get_claim()?;

// Create aggregated proof
let digest1 = claim1.digest();
let digest2 = claim2.digest();

let aggregated = Prover::new_test_recursion_circuit(
    [&digest1, &digest2],
    ProverOpts::default()
)?.run()?;

// The aggregated proof proves both computations were correct

Controlling Segment Size

let opts = ProverOpts::default()
    .with_segment_limit_po2(20); // 2^20 cycles per segment

let receipt = default_prover().prove_with_opts(env, GUEST_ELF, &opts)?;

Segment size affects:

• Smaller segments: More segments, more join operations, slower overall
• Larger segments: Fewer segments, higher memory usage, may exceed GPU memory

Default segment size (2^22 = 4M cycles) works well for most applications. Adjust only if you encounter memory issues or need fine-tuning.

Performance Considerations

Proving Time Breakdown

For a typical program with 4 segments:

Stage	Time (relative)	Notes
Execution	1x	Fast, single-threaded
Segment proving	40x	Parallelizable, benefits from GPU
Lifting	4x	One per segment
Joining	6x	Log(N) joins needed
Identity_p254	4x	Required for Groth16
Groth16 compress	60x	Only if on-chain verification needed

With GPU acceleration, segment proving time can be reduced by 10-20x. See GPU Acceleration.

Optimization Strategies

1. Optimize guest code first: See Optimization Guide
2. Use GPU acceleration: 10-20x speedup for proving
3. Skip Groth16 compression: Use SuccinctReceipts for off-chain verification
4. Parallelize segment proving: Segments can be proven concurrently
5. Cache receipts: Reuse proofs for identical computations

Continuations

Continuations allow programs to run indefinitely by splitting execution into segments:

// Guest code automatically continues across segments
fn main() {
    // This loop can run for any number of iterations
    for i in 0..1_000_000 {
        // Computation that may span many segments
        heavy_computation(i);
    }
}

The zkVM automatically:

1. Saves state when segment limit is reached
2. Creates a continuation point
3. Resumes execution in the next segment
4. Joins segment proofs together

See the continuations blog post for details.

Advanced: Custom Recursion

For advanced use cases, you can use the recursion circuit directly:

use risc0_zkvm::recursion::Prover;

// Create custom recursion proof
let recursion_prover = Prover::new_test_recursion_circuit(
    digests, // Array of digests to aggregate
    ProverOpts::default()
)?;

let receipt = recursion_prover.run()?;

Direct use of the recursion circuit is an advanced feature. Most applications should use the standard proving APIs.

Next Steps

• Learn about GPU Acceleration to speed up proving
• Explore Performance Optimization for guest code
• Understand Proof Composition for modular proofs
• Read about On-chain Verification with Groth16