Examples

The three recursive examples select their polynomial commitment scheme with --pcs fri|whir (default fri). WHIR supports BabyBear, KoalaBear, and Goldilocks with either --hash poseidon2 or --hash poseidon1, retaining the same base computations and configurable recursion depth. KoalaBear also supports its quintic challenge extension with --pcs whir --quintic and either hash family. --zk, --disable-recompose-npo, and aggregation's --arity4 require FRI.

cargo run --release --example recursive_fibonacci -- --pcs whir --n 1000 --num-recursive-layers 2
cargo run --release --example recursive_keccak -- --pcs whir --num-hashes 100 --num-recursive-layers 2
cargo run --release --example recursive_aggregation -- --pcs whir --num-recursive-layers 2

For WHIR, --log-blowup controls the starting inverse rate, --query-pow-bits controls the maximum PoW budget, and --whir-folding-factor controls the number of variables folded per round (default 4). --security-level defaults to 64 for WHIR and 124 for FRI. FRI's --max-log-arity, --log-final-poly-len, and --commit-pow-bits do not configure WHIR.

This section walks through the three provided examples to illustrate common recursion patterns.

Recursive Keccak — verifying a uni-STARK proof

Source: recursion/examples/recursive_keccak.rs

This example starts from a standard Plonky3 uni-STARK proof of the Keccak AIR, then recursively verifies it through multiple layers.

Flow:

1. Generate a Keccak trace and prove it with p3_uni_stark::prove.
2. Wrap the resulting Proof<SC> in a RecursionInput::UniStark.
3. Call build_and_prove_next_layer — this builds a verification circuit that checks the Keccak proof, runs it, and produces a batch-STARK proof.
4. For subsequent layers, convert the output with output.into_recursion_input::<BatchOnly>() and repeat.

The key point: the first recursive layer handles a uni-STARK proof (potentially large, depending on the AIR width). After that, every layer verifies the previous layer's batch-STARK proof, which has a predictable, smaller structure. This is why layer 1 is typically slower than layers 2+.

cargo run --release --example recursive_keccak -- \
    --field koala-bear --num-hashes 1000 --num-recursive-layers 3

Recursive Fibonacci — verifying a batch-STARK proof

Source: recursion/examples/recursive_fibonacci.rs

This example builds a Fibonacci circuit from scratch using CircuitBuilder, proves it with BatchStarkProver, then recurses.

Flow:

1. Build the circuit: CircuitBuilder::new(), add constants, public inputs, arithmetic, connect, build.
2. Run and prove the base circuit with BatchStarkProver.
3. Wrap the output in RecursionOutput (since it's already a batch proof), then use into_recursion_input::<BatchOnly>().
4. Call build_and_prove_next_layer in a loop for each recursive layer.

This example demonstrates how to use the CircuitBuilder for your own computations and then feed the resulting proof into the recursion pipeline.

cargo run --release --example recursive_fibonacci -- \
    --field koala-bear --n 10000 --num-recursive-layers 3

Recursive Aggregation — 2-to-1 proof merging

Source: recursion/examples/recursive_aggregation.rs

This example produces multiple independent base proofs and aggregates them pairwise in a binary tree.

Flow:

1. Produce 2^depth independent base proofs (each proving a different constant).
2. At each tree level, pair up proofs and call build_and_prove_aggregation_layer on each pair.
3. Repeat until a single root proof remains.

The aggregation circuit verifies two proofs in a single circuit — left and right children — producing one output proof. The two inputs may be different kinds of RecursionInput (e.g., one UniStark and one BatchStark), though in this example they are all BatchStark.

# 4 base proofs, 2 aggregation levels
cargo run --release --example recursive_aggregation -- \
    --field koala-bear --num-recursive-layers 2

Common CLI flags

All three examples accept the same selectors for the recursive verifier's field and hash:

• --field <koala-bear|baby-bear|goldilocks> — base field (default koala-bear).
• --quintic — use the quintic (D = 5) challenge extension (KoalaBear only).
• --hash <poseidon2|poseidon1> — permutation backing the Fiat-Shamir challenger and MMCS (default poseidon2).

cargo run --release --example recursive_fibonacci -- \
    --field baby-bear --hash poseidon1 --n 10000 --num-recursive-layers 3

Common patterns across examples

All three examples share the same setup pattern:

1. Config wrapper: A ConfigWithFriParams struct that wraps a StarkConfig and adds FriVerifierParams. It implements StarkGenericConfig (by delegating) and FriRecursionConfig.

2. Backend creation: FriRecursionBackend::<WIDTH, RATE>::new(poseidon2_config).

3. Table packing: Adjusted per layer — the first layer may need different packing than subsequent layers because the verification circuit has a different shape.

4. Verification after proving: Each example verifies the proof it just produced, using BatchStarkProver::verify_all_tables.

See the Integration Guide for how to adapt this pattern to your own project.