The conversion from STARK to SNARK begins with the construction of recursive circuits. These recursive circuits are designed to compress the original large STARK proof into a smaller SNARK proof. The process involves several key components: the root circuit, the aggregation circuit, and the block circuit. Below is an introduction to the roles of each of these circuits:

1. Root Circuit

The root circuit is the core component for compressing STARK proofs. It aggregates recursive proofs from multiple tables and ultimately generates a SNARK proof. The root circuit collects recursive proofs from all tables and ensures that their public inputs meet the required conditions.

Code implementation:

/// The ZKVM root circuit, which aggregates the (shrunk) per-table recursive proofs.
#[derive(Eq, PartialEq, Debug)]
pub struct RootCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // Root circuit data
    proof_with_pis: [ProofWithPublicInputsTarget<D>; NUM_TABLES],  // Recursive proof for each table
    index_verifier_data: [Target; NUM_TABLES],  // Index data for verification
    public_values: PublicValuesTarget,  // Public inputs
    cyclic_vk: VerifierCircuitTarget,  // Verifier key for cyclic verification
}

The key to the root circuit is how it compresses each table’s recursive proof into a final proof and checks their consistency. In this structure, proof_with_pis stores each table’s recursive proof, while index_verifier_data and public_values are used to verify these proofs.

2. Aggregation Circuit

The purpose of the aggregation circuit is to compress two proofs into one. During the STARK-to-SNARK conversion, the aggregation circuit is typically used to merge the root circuit proof with other intermediate proofs into the final proof. By aggregating multiple recursive proofs, it reduces the overall proof size.

Code implementation:

/// Data for the aggregation circuit, which is used to compress two proofs into one.
#[derive(Eq, PartialEq, Debug)]
pub struct AggregationCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // Aggregation circuit data
    lhs: AggregationChildTarget<D>,  // Left-side aggregation sub-circuit
    rhs: AggregationChildTarget<D>,  // Right-side aggregation sub-circuit
    public_values: PublicValuesTarget,  // Public inputs
    cyclic_vk: VerifierCircuitTarget,  // Verifier key for cyclic verification
}

The aggregation circuit compresses two proofs into a single final proof using lhs and rhs sub-circuits. Each sub-circuit can either be a ZKVM root proof or another aggregated proof. In implementation, lhs and rhs represent the left and right sides of the aggregation, respectively.

3. Block Circuit

The block circuit is similar in function to the aggregation circuit, but it not only compresses proofs — it also verifies the consistency between two proofs (e.g., an aggregation proof and a parent block proof). This circuit ensures blockchain validity and consistency.

/// Data for the block circuit, which verifies an aggregation root proof and a previous block proof.
#[derive(Eq, PartialEq, Debug)]
pub struct BlockCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // Block circuit data
    has_parent_block: BoolTarget,  // Whether a parent block exists
    parent_block_proof: ProofWithPublicInputsTarget<D>,  // Parent block proof
    agg_root_proof: ProofWithPublicInputsTarget<D>,  // Aggregation root proof
    public_values: PublicValuesTarget,  // Public inputs
    cyclic_vk: VerifierCircuitTarget,  // Verifier key for cyclic verification
}

When processing proofs, the block circuit verifies both the parent block proof and the aggregation root proof. If there is no parent block proof available, a dummy parent proof is used instead.

Next, we focus on the process of compressing each STARK proof into a single SNARK proof. This includes determining the recursive circuit chain (i.e., the order in which recursive proofs are performed), handling the challenge sets and public inputs, and finally executing the conversion from a STARK proof to a SNARK proof, as follows:

3.1 Step-by-Step Compression of the Recursive Circuit Chain

The key to the recursive circuit chain is the step-by-step compression of each table’s recursive proof. Each table’s recursive circuit contains multiple sub-circuits, with the degree of each decreasing progressively until it reaches a preset threshold THRESHOLD_DEGREE_BITS.

#[derive(Eq, PartialEq, Debug)]
pub struct RecursiveCircuitsForTable<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
    C::Hasher: AlgebraicHasher<F>,
{
    by_stark_size: BTreeMap<usize, RecursiveCircuitsForTableSize<F, C, D>>,  // Recursive circuit chain per table
}

impl<F, C, const D: usize> RecursiveCircuitsForTable<F, C, D>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
    C::Hasher: AlgebraicHasher<F>,
{
    pub fn new<S: Stark<F, D>>(
        table: Table,
        stark: &S,
        degree_bits_range: Range<usize>,
        all_ctls: &[CrossTableLookup<F>],
        stark_config: &StarkConfig,
    ) -> Self {
        let by_stark_size = degree_bits_range
            .map(|degree_bits| {
                (
                    degree_bits,
                    RecursiveCircuitsForTableSize::new::<S>(
                        table,
                        stark,
                        degree_bits,
                        all_ctls,
                        stark_config,
                    ),
                )
            })
            .collect();
        Self { by_stark_size }
    }
}

RecursiveCircuitsForTable constructs a recursive circuit chain for each table, where each circuit in the chain has a different size. The recursion ends once the size of the circuit falls below the preset threshold THRESHOLD_DEGREE_BITS. This chain is implemented through RecursiveCircuitsForTableSize.

3.2 Handling of Challenge Sets and Public Inputs

In each recursive step, the challenge set and public inputs are used to ensure the validity of the proof. The public inputs provide verification data for each proof, while the challenge set is used to verify the challenge values of each proof. With the help of RecursiveChallenger, we can observe and verify these challenge values.

let mut challenger = RecursiveChallenger::<F, C::Hasher, D>::new(&mut builder);
for pi in &pis {
    for h in &pi.trace_cap {
        challenger.observe_elements(h);  // Observe public inputs
    }
}

let ctl_challenges = get_grand_product_challenge_set_target(
    &mut builder,
    &mut challenger,
    stark_config.num_challenges,
);

During each recursive step, RecursiveChallenger is used to observe the challenge values in the public inputs and ensure their consistency. This guarantees that each proof is valid and eligible for further compression.

3.3 Final Conversion from STARK to SNARK

Once all recursive steps are completed, the final conversion from STARK to SNARK is achieved by progressively compressing the STARK proof into a smaller SNARK proof through multiple recursive circuit chains. The proof for each table is gradually reduced and eventually merged into a single root proof.

pub fn prove_root(
    &self,
    all_stark: &AllStark<F, D>,
    kernel: &Kernel,
    config: &StarkConfig,
    timing: &mut TimingTree,
) -> anyhow::Result<(ProofWithPublicInputs<F, C, D>, PublicValues)> {
    let all_proof = prove::<F, C, D>(all_stark, kernel, config, timing)?;
    verify_proof(all_stark, all_proof.clone(), config).unwrap();
    let mut root_inputs = PartialWitness::new();

    // Process the proof for each table
    for table in 0..NUM_TABLES {
        let stark_proof = &all_proof.stark_proofs[table];
        let shrunk_proof = self.by_table[table]
            .by_stark_size
            .get(&stark_proof.proof.recover_degree_bits(config))
            .unwrap()
            .shrink(stark_proof, &all_proof.ctl_challenges)?;
        root_inputs.set_proof_with_pis_target(&self.root.proof_with_pis[table], &shrunk_proof);
    }

    // Set public inputs and generate the root proof
    set_public_value_targets(
        &mut root_inputs,
        &self.root.public_values,
        &all_proof.public_values,
    )?;

    let root_proof = self.root.circuit.prove(root_inputs)?;
    Ok((root_proof, all_proof.public_values))
}

In the final conversion, prove_root processes each table’s proof one by one, compresses them using the shrink method, and generates the final SNARK proof by setting the public inputs.

The core function of shrink is to compress a large STARK proof into a smaller one suitable for recursive verification, while preserving the original proof’s integrity and soundness. This not only reduces proof complexity but also improves the efficiency of subsequent recursive circuits. The process involves the following steps:

1. First, shrink calls the proving function within the initial_wrapper to perform an initial compression of the STARK proof. This crucial step maps the original large proof into a smaller circuit.
2. Then, it iteratively calls each recursive circuit in the shrinking_wrappers to further compress the initially shrunk proof, until the proof’s size fits the target circuit constraints (e.g., the recursive gate size defined by THRESHOLD_DEGREE_BITS).
3. Finally, it returns a compressed ProofWithPublicInputs structure that contains the public inputs and the compressed proof, which can be directly consumed by smaller recursive circuits.

fn shrink(
    &self,
    stark_proof_with_metadata: &StarkProofWithMetadata<F, C, D>,
    ctl_challenges: &GrandProductChallengeSet<F>,
) -> anyhow::Result<ProofWithPublicInputs<F, C, D>> {
    let mut proof = self
        .initial_wrapper
        .prove(stark_proof_with_metadata, ctl_challenges)?;
    for wrapper_circuit in &self.shrinking_wrappers {
        proof = wrapper_circuit.prove(&proof)?;
    }
    Ok(proof)
}

‍

Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions about the article, you can contact the ZKM team on discord: discord.com/zkm