Plonky3-recursion

KO | EN

gitlite — search

#javascript #react #ai #typescript #go #golang #machine-learning #rust #docker #windows #awesome #cli #vue #mcp

Plonky3-recursion

(★ 27)

Plonky3 native support for p3-uni-stark and p3-batch-stark recursion... and more

Plonky3-recursion Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Plonky3-recursion

Plonky3 native support for recursive STARK verification, enabling proof composition and multi-layer recursion.

## Overview

This library provides a **fixed recursive verifier** for Plonky3 STARK (both `p3-uni-stark` and `p3-batch-stark` proofs), allowing you to verify proofs inside circuits and compose proofs recursively. The recursive verifier is implemented as a circuit itself, which can be proven and verified in subsequent layers.

### Key Features

- **Recursive STARK Verification**: Verify Plonky3 STARK proofs inside circuits
- **Batch STARK Support**: Verify multiple proofs in a single batch
- **Modular Circuit Builder**: Build circuits with primitive operations (add, mul, etc.) and non-primitive operations (Poseidon2)
- **FRI-based PCS**: Full support for FRI (Fast Reed-Solomon Interactive) polynomial commitment scheme verification in-circuit
- **ZK support**: Full support for Zero-Knowledge.

## Production Use

**⚠️ This codebase is under active development and hasn't been audited yet.** As such, we do not recommend its use in any production software.

[![Coverage](https://github.com/Plonky3/Plonky3-recursion/actions/workflows/coverage.yml/badge.svg)](https://plonky3.github.io/Plonky3-recursion/coverage/) (_updated weekly_)

## Quick Start

### Unified recursion API

#### Recursive verification

For most use cases, use the **unified API**: a single entry point works for both uni-stark (e.g. Keccak) and batch-stark (e.g. Fibonacci) proofs. Implement [`FriRecursionConfig`] for your config (or a wrapper that holds FRI verifier params), then call [`prove_next_layer`] in a loop.

[`FriRecursionConfig`]: https://docs.rs/p3-recursion/latest/p3_recursion/trait.FriRecursionConfig.html
[`prove_next_layer`]: https://docs.rs/p3-recursion/latest/p3_recursion/fn.prove_next_layer.html

```rust
use p3_recursion::{
    FriRecursionBackend, FriRecursionConfig, ProveNextLayerParams, RecursionInput, RecursionOutput,
    prove_next_layer,
};

// First layer: recurse on a uni-stark proof (e.g. Keccak)
let input = RecursionInput::UniStark {
    proof: &base_proof,
    air: &keccak_air,
    public_inputs: pis.clone(),
    preprocessed_commit: None,
};
let backend = FriRecursionBackend::new(poseidon2_config);
let params = ProveNextLayerParams { table_packing, constraint_profile };
let (verification_circuit, verifier_result) = build_next_layer_circuit(&input, &config, &backend)?;
let output = prove_next_layer(
    &input,
    &verification_circuit,
    &verifier_result,
    &config,
    &backend,
    &params,
    None,
)?;

// Next layers: recurse on the previous batch proof
let input = output.into_recursion_input::<BatchOnly>();
let (verification_circuit, verifier_result) = build_next_layer_circuit(&input, &config, &backend)?;
let output = prove_next_layer(
    &input,
    &verification_circuit,
    &verifier_result,
    &config,
    &backend,
    &params,
    None,
)?;
```

`RecursionOutput` is `(BatchStarkProof, Rc<CircuitProverData>)`; use `into_recursion_input::<BatchOnly>()` to chain further layers.

#### Recursive aggregation

This library also supports 2-to-1 recursive aggregation by building circuits verifying possibly different circuits (for instance 
`RecursionInput::UniStark` as left child and `RecursionInput::BatchStark` as right child).

```rust
let input_1 = RecursionInput::UniStark {
    proof: &base_proof_1,
    air: &air_1,
    public_inputs: pis_1.clone(),
    preprocessed_commit: None,
};
let input_2 = RecursionInput::UniStark {
    proof: &base_proof_2,
    air: &air_2,
    public_inputs: pis_2.clone(),
    preprocessed_commit: None,
};

let backend = FriRecursionBackend::new(poseidon2_config);
let params = ProveNextLayerParams { table_packing, constraint_profile };
let output = build_and_prove_aggregation_layer(
    &input_1,
    &input_2,
    &config,
    &backend,
    &params,
    None,
)?;
```

### Low-level API

For fine-grained control, you can build the verification circuit and run the prover pipeline yourself via `verify_p3_batch_proof_circuit` (batch) or `verify_p3_uni_proof_circuit` (uni-stark):

```rust
use p3_recursion::verifier::verify_p3_batch_proof_circuit;
use p3_recursion::public_inputs::BatchStarkVerifierInputsBuilder;
use p3_circuit::CircuitBuilder;

// Build a verification circuit
let mut circuit_builder = CircuitBuilder::new();
circuit_builder.enable_poseidon2_perm::<Config, _>(trace_generator, poseidon2_perm);

let (verifier_inputs, mmcs_op_ids) = verify_p3_batch_proof_circuit::<
    MyConfig,
    HashTargets<F, DIGEST_ELEMS>,
    InputProofTargets<F, Challenge, RecValMmcs<...>>,
    InnerFri,
    LogUpGadget,
    WIDTH,
    RATE,
    TRACE_D,
>(
    &config,
    &mut circuit_builder,
    &batch_stark_proof,
    &fri_verifier_params,
    common_data,
    &lookup_gadget,
    Poseidon2Config::BabyBearD4Width16,
)?;

// Build and run the circuit
let circuit = circuit_builder.build()?;
let mut runner = circuit.runner();

// Pack public inputs using the builder
let public_inputs = verifier_inputs.pack_public_values(&pis, &batch_proof, common_data);
runner.set_public_inputs(&public_inputs)?;

// Set MMCS private data (Merkle paths)
set_fri_mmcs_private_data(&mut runner, &mmcs_op_ids, &proof.opening_proof)?;

let traces = runner.run()?;
```

### Examples

All examples use the unified API (`prove_next_layer`, `RecursionInput`, `FriRecursionBackend`):

- **`recursive_fibonacci.rs`**: Base layer is a batch-stark circuit (Fibonacci); recursive layers use `into_recursion_input::<BatchOnly>()` and `prove_next_layer`.
  ```bash
  cargo run --profile optimized --example recursive_fibonacci -- --field koala-bear --n 1000 --num-recursive-layers 5
  ```

- **`recursive_keccak.rs`**: Base layer is a uni-stark Keccak proof; layer 1 uses `RecursionInput::UniStark`, then further layers use `into_recursion_input::<BatchOnly>()` and `prove_next_layer`.
  ```bash
  cargo run --profile optimized --example recursive_keccak -- --field koala-bear --n 100 --num-recursive-layers 5
  ```

- **`recursive_aggregation.rs`**: Base layer are dummy batch-stark circuits; recursive layers use `into_recursion_input::<BatchOnly>()` and `build_and_prove_aggregation_layer` to fold 2 proofs into 1.
  ```bash
  cargo run --profile optimized --example recursive_aggregation -- --field koala-bear --num-recursive-layers 4
  ```

All three examples take `--field <koala-bear|baby-bear|goldilocks>`, `--quintic` (KoalaBear only), and `--hash <poseidon2|poseidon1>` (default `poseidon2`):
```bash
cargo run --profile optimized --example recursive_fibonacci -- --field baby-bear --hash poseidon1 --n 1000
```

## API Overview

### Circuit Builder

The `CircuitBuilder<F>` provides a modular API for building circuits:

**Primitive Operations** (always available):
- `define_const(val)` - Add a constant
- `public_input()` - Allocate a public input
- `mul(a, b)` - Multiply two expressions
- `add(a, b)` / `sub(a, b)` - Arithmetic operations
- `connect(a, b)` - Constrain two expressions to be equal

**Non-primitive Operations** (require explicit enablement):
- `enable_poseidon2_perm()` - Enable Poseidon2 permutation operations
- Operations must be explicitly enabled via `enable_poseidon2_perm()` before use

### Public Inputs

Public inputs must be provided in the **exact order** the circuit allocated them. Use the builder APIs to ensure correctness:

```rust
use p3_recursion::public_inputs::PublicInputBuilder;

let mut builder = PublicInputBuilder::new();
builder
    .add_proof_values(proof_values)
    .add_challenge(alpha)
    .add_challenges(betas);
let public_inputs = builder.build();
```

For batch verification, use `BatchStarkVerifierInputsBuilder::pack_public_values()` which handles the packing automatically.

## Architecture

### Components

1. **Circuit Builder** (`p3_circuit`): Expression graph builder with primitive and non-primitive operations
2. **Circuit Prover** (`p3_circuit_prover`): Generates STARK proofs for circuits
3. **Recursive Verifier** (`p3_recursion::verifier`): Verifies STARK proofs inside circuits
4. **FRI PCS** (`p3_recursion::pcs::fri`): FRI polynomial commitment scheme verification in-circuit

### Recursion Flow

1. **Base Layer**: Prove a computation using Plonky3 STARK
2. **Recursive Layer**: Build a verification circuit that checks the base proof
3. **Prove Recursive Layer**: Prove the verification circuit itself
4. **Repeat**: Continue recursion for additional layers

Each recursive layer verifies the previous layer's proof, creating a chain of proofs.

## Performance Considerations

### Table Packing

The `TablePacking` configuration significantly impacts performance.
Choose lane counts that fit best your circuit size:

```rust
TablePacking::new(2, 5)  // public, alu lanes
```

### FRI Parameters

FRI parameters affect proof size and verification cost:
- `log_blowup`: LDE blowup factor (typically 3)
- `max_log_arity`: Maximum folding arity (typically 4)
- `log_final_poly_len`: Final polynomial size (typically 5)
- `query_pow_bits`: PoW bits for query phase (typically 16)

For intermediate recursive layers, consider relaxed parameters (fewer queries, higher PoW bits).

## Build Profiles and Compile Features

### Build profiles

Two custom profiles are defined in the workspace `Cargo.toml`:

| Profile | Based on | Description |
|---------|----------|-------------|
| `optimized` | `release` | Maximum performance: thin LTO, single codegen unit, `opt-level = 3`. Use for all benchmarks and production runs. |
| `profiling` | `release` | Like `release` but with debug symbols (`debug = true`) for CPU profilers (`perf`, Instruments, `samply`). |

```bash
cargo run --profile optimized --example recursive_fibonacci --features parallel
cargo run --profile profiling  --example recursive_fibonacci --features parallel
```

### Compile features

| Crate | Feature | Description |
|-------|---------|-------------|
| `p3-circuit` | `debugging` | Allocation logging — every witness slot records the operation and scope that created it. |
| `p3-circuit` | `profiling` | Operation-count profiling (implies `debugging`) — tracks `add`/`mul`/`const`/NPO counts globally and per named scope via `OpCounts`. |
| `p3-circuit-prover` | `parallel` | Multi-threaded trace generation via Rayon. Strongly recommended for benchmarks and production. |

See [Debugging](https://Plonky3.github.io/Plonky3-recursion/advanced_topics/debugging.html) in the book for full details.

## Current Limitations

- **Fixed Configurations**: Field extensions are currently not fully parametrizable.

## Documentation

Documentation is still incomplete and will be improved over time.

- **[Plonky3 Recursion Book](https://Plonky3.github.io/Plonky3-recursion/)**: Comprehensive walkthrough of the recursion approach
- **API Documentation**: `cargo doc --open` for full API reference
- **Examples**: See `recursion/examples/` for working code

## Modular Circuit Builder

The `CircuitBuilder<F>` supports both primitive and non-primitive operations. Primitive ops like `Const`, `Public`, `Add` are always available.

Non-primitive operations (e.g. Poseidon2 permutations) must be explicitly enabled on the builder before use. Attempting to use a non-primitive operation that hasn't been enabled will result in a runtime error.

## License

Licensed under either of

* Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
* MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Plonky3-recursion

Plonky3-recursion Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Plonky3-recursion

Plonky3-recursion Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README