risc0-circuit-recursion

Recursion circuit for proof compression and composition

risc0-circuit-recursion

The risc0-circuit-recursion crate implements the recursion circuit used by RISC Zero to compress and compose proofs through recursive verification.

Installation

[dependencies]
risc0-circuit-recursion = { version = "1.3.0", features = ["prove"] }

Overview

The recursion circuit is a specialized virtual machine optimized for algebraic operations, particularly STARK verification. It enables:

• Proof Compression: Combine multiple segment proofs into one succinct proof
• Proof Composition: Verify receipts within proofs (compositional proving)
• Constant Size: Final proofs are constant size regardless of program complexity

This is a low-level circuit implementation. Most users should use risc0-zkvm which handles recursion automatically.

Feature Flags

prove · feature

Enables proof generation functionality.

• Implies: std
• Enables: Recursion prover, HAL implementations

cuda · feature

Enables CUDA GPU acceleration.

• Implies: prove

metal · feature

Enables Metal GPU acceleration (macOS).

• Implies: prove

dual · feature

Enables dual CPU/GPU proving mode.

• Implies: cuda

std · feature

Enables standard library support.

test · feature

Enables test utilities.

Constants

LIFT_PO2_RANGE · const

Valid power-of-2 range for lift operations.

pub const LIFT_PO2_RANGE: RangeInclusive<usize> = 12..=24;

Range: 2^12 (4096) to 2^24 (16M) cycles

REGISTER_GROUP_ACCUM · const

Register group for accumulator.

pub const REGISTER_GROUP_ACCUM: usize = 0;

REGISTER_GROUP_CODE · const

Register group for code.

pub const REGISTER_GROUP_CODE: usize = 1;

REGISTER_GROUP_DATA · const

Register group for data.

pub const REGISTER_GROUP_DATA: usize = 2;

Circuit Implementation

CircuitImpl · struct

The recursion circuit implementation.

pub struct CircuitImpl;

impl CircuitImpl {
    pub const fn new() -> Self;
}

Implements constraint system for recursive STARK verification.

CIRCUIT · const

Global circuit instance.

pub const CIRCUIT: CircuitImpl = CircuitImpl::new();

Recursion Programs

The recursion VM runs specialized programs:

Lift

Lift Program

Converts a segment receipt into a recursion receipt.

• Input: Segment receipt (RV32IM proof)
• Output: Lifted receipt (recursion proof)
• Purpose: Entry point for compression

Join

Join Program

Combines two recursion receipts into one.

• Input: Two recursion receipts
• Output: Single joined receipt
• Purpose: Binary tree reduction

Resolve

Resolve Program

Resolves assumptions in a receipt.

• Input: Receipt with assumptions, assumption receipts
• Output: Unconditional receipt
• Purpose: Compositional verification

Identity

Identity Program

Verifies a receipt without transformation.

• Input: Receipt
• Output: Verified receipt
• Purpose: Re-verification, format conversion

Control IDs

control_id · module

Control IDs for recursion programs.

pub mod control_id {
    // Control IDs for each recursion program
    pub const LIFT: &[Digest];
    pub const JOIN: &[Digest];
    pub const RESOLVE: &[Digest];
    pub const IDENTITY: &[Digest];
}

Layout

layout · module

Memory layout for recursion circuits.

Defines register layouts, memory regions, and constraint system structure.

Proving (with prove feature)

prove · module

Recursion proof generation.

pub mod prove {
    pub struct RecursionProver<H: Hal> {
        // ...
    }
}

Polynomial Extensions

poly_ext · module

Polynomial extension field operations.

Optimized operations over extension fields used in FRI protocol.

Examples

Understanding Recursion Flow

// Conceptual flow (handled automatically by risc0-zkvm):

// 1. Execute program, generate segment receipts
let segments: Vec<SegmentReceipt> = execute_and_prove(elf, input);

// 2. Lift each segment to recursion
let lifted: Vec<RecursionReceipt> = segments
    .iter()
    .map(|seg| lift(seg))
    .collect();

// 3. Join recursively in binary tree
let mut current = lifted;
while current.len() > 1 {
    current = current
        .chunks(2)
        .map(|pair| {
            if pair.len() == 2 {
                join(&pair[0], &pair[1])
            } else {
                identity(&pair[0])
            }
        })
        .collect();
}

// 4. Final succinct receipt
let succinct = current[0].clone();

Circuit Constants

use risc0_circuit_recursion::{
    LIFT_PO2_RANGE,
    REGISTER_GROUP_ACCUM,
    REGISTER_GROUP_CODE,
    REGISTER_GROUP_DATA,
};

fn check_po2(po2: usize) -> bool {
    LIFT_PO2_RANGE.contains(&po2)
}

fn register_groups() {
    println!("Accum group: {}", REGISTER_GROUP_ACCUM);
    println!("Code group: {}", REGISTER_GROUP_CODE);
    println!("Data group: {}", REGISTER_GROUP_DATA);
}

Recursion VM Architecture

The recursion VM is optimized for:

1. Field Arithmetic: Baby Bear field operations
2. Extension Fields: 4-element extension for FRI
3. Poseidon2: Hash function for Merkle trees
4. FRI Verification: STARK verification within STARK

Non-Turing-Complete

The recursion VM is intentionally non-Turing-complete:

• No Loops: Only bounded iteration
• Predictable: All operations have known bounds
• Efficient: Optimized for algebraic constraints

Performance

Recursion performance characteristics:

Operation	Cycles	Time (CPU)	Time (GPU)
Lift	~1M	~1s	~100ms
Join	~1M	~1s	~100ms
Resolve	~1M	~1s	~100ms

Actual times vary based on hardware and proof size.

Memory Layout

Register groups organize circuit state:

• Accum (Group 0): Accumulator registers
• Code (Group 1): Instruction/control registers
• Data (Group 2): Data registers

Taps

taps · module

Register tap definitions.

pub static TAPSET: &TapSet = /* ... */;

Defines which registers are accessible at which cycle offsets.

Info

info · module

Circuit information and metadata.

Provides details about circuit size, layout, and capabilities.

GPU Acceleration

The recursion circuit benefits significantly from GPU acceleration:

// Automatically uses GPU if available
let prover = default_prover();
let receipt = prover.prove_with_opts(
    env,
    elf,
    &ProverOpts::succinct(),
)?;

CUDA

With CUDA enabled:

• 10-100x faster than CPU
• Parallel field operations
• Optimized FFT implementation

Metal

On Apple Silicon:

• Automatic detection and use
• Optimized for M-series chips
• Energy efficient

Debugging

Enable test utilities for debugging:

[dependencies]
risc0-circuit-recursion = { 
    version = "1.3.0", 
    features = ["prove", "test"] 
}

Security Considerations

The recursion circuit maintains the security properties of the base STARK:

• Soundness: Inherited from base proof system
• Zero-Knowledge: Proofs reveal nothing about execution
• Compression: Constant size regardless of input

Links

• docs.rs
• GitHub
• Crate
• Recursion Paper