Proof Aggregation

With aggregation, multiple proofs can be combined together into a single aggregated proof by verifying each proof generated by Ziren inside the Ziren zkVM. A toy example of using aggregation for Fibonacci proofs can be found in Ziren’s examples directory here.

In this example, multiple proofs proving the execution of a Fibonacci sequence for different values of n are combined into a single higher-level “aggregated” proof. This higher-level proof proves that the collection of all the other Fibonacci individual proofs are valid.

Instead of verifying each proof one by one, a verifier only needs to check a single aggregated proof. The batching of many small computations into a single proof reduces verification costs and enable applications such as block aggregation, where many transactions in a block can be proven with one single succinct proof.

The host generates individual proofs, the guest recursively verifies them, and the final outputted aggregation proof can be cheaply verified.

The following is the guest program implementation in the example:

guest > main.rs:

//! A simple program that aggregates the proofs of multiple programs proven with the zkVM.

#![no_main]
zkm_zkvm::entrypoint!(main);

use sha2::{Digest, Sha256};

pub fn main() {
    // Read the verification keys.
    let vkeys = zkm_zkvm::io::read::<Vec<[u32; 8]>>();

    // Read the public values.
    let public_values = zkm_zkvm::io::read::<Vec<Vec<u8>>>();

    // Verify the proofs.
    assert_eq!(vkeys.len(), public_values.len());
    for i in 0..vkeys.len() {
        let vkey = &vkeys[i];
        let public_values = &public_values[i];
        let public_values_digest = Sha256::digest(public_values);
        zkm_zkvm::lib::verify::verify_zkm_proof(vkey, &public_values_digest.into());
    }

    // TODO: Do something interesting with the proofs here.
    //
    // For example, commit to the verified proofs in a merkle tree. For now, we'll just commit to
    // all the (vkey, input) pairs.
    let commitment = commit_proof_pairs(&vkeys, &public_values);
    zkm_zkvm::io::commit_slice(&commitment);
}

pub fn words_to_bytes_le(words: &[u32; 8]) -> [u8; 32] {
    let mut bytes = [0u8; 32];
    for i in 0..8 {
        let word_bytes = words[i].to_le_bytes();
        bytes[i * 4..(i + 1) * 4].copy_from_slice(&word_bytes);
    }
    bytes
}

/// Encode a list of vkeys and committed values into a single byte array. In the future this could
/// be a merkle tree or some other commitment scheme.
///
/// ( vkeys.len() || vkeys || committed_values[0].len as u32 || committed_values[0] || ... )
pub fn commit_proof_pairs(vkeys: &[[u32; 8]], committed_values: &[Vec<u8>]) -> Vec<u8> {
    assert_eq!(vkeys.len(), committed_values.len());
    let mut res = Vec::with_capacity(
        4 + vkeys.len() * 32
            + committed_values.len() * 4
            + committed_values.iter().map(|vals| vals.len()).sum::<usize>(),
    );

    // Note we use big endian because abi.encodePacked in solidity does also
    res.extend_from_slice(&(vkeys.len() as u32).to_be_bytes());
    for vkey in vkeys.iter() {
        res.extend_from_slice(&words_to_bytes_le(vkey));
    }
    for vals in committed_values.iter() {
        res.extend_from_slice(&(vals.len() as u32).to_be_bytes());
        res.extend_from_slice(vals);
    }

    res
}

The guest first reads a list of verification keys and public values for each individual proof, supplied by the host. For each verification key and public value pair, the program will:

• Hash the public values with SHA-256 to obtain a fixed-size digest.
• Call zkm_zkvm::lib::verify::verify_zkm_proof(vkey, &public_values_digest.into()) to recursively check the individual proof against its associated verification key and digest.

After verifying all individual proofs, the guest commits to the entire batch of verification keys and public values pairs to build a combined byte string. This commitment becomes the public output of the aggregated proof.

The following is the host program implementation in the example:

host > main.rs:

//! A simple example showing how to aggregate proofs of multiple programs with ZKM.

use zkm_sdk::{
    include_elf, HashableKey, ProverClient, ZKMProof, ZKMProofWithPublicValues, ZKMStdin,
    ZKMVerifyingKey,
};

/// A program that aggregates the proofs of the simple program.
const AGGREGATION_ELF: &[u8] = include_elf!("aggregation");

/// A program that just runs a simple computation.
const FIBONACCI_ELF: &[u8] = include_elf!("fibonacci");

/// An input to the aggregation program.
///
/// Consists of a proof and a verification key.
struct AggregationInput {
    pub proof: ZKMProofWithPublicValues,
    pub vk: ZKMVerifyingKey,
}

fn main() {
    // Setup the logger.
    zkm_sdk::utils::setup_logger();

    // Initialize the proving client.
    let client = ProverClient::new();

    // Setup the proving and verifying keys.
    let (aggregation_pk, _) = client.setup(AGGREGATION_ELF);
    let (fibonacci_pk, fibonacci_vk) = client.setup(FIBONACCI_ELF);

    // Generate the fibonacci proofs.
    let proof_1 = tracing::info_span!("generate fibonacci proof n=10").in_scope(|| {
        let mut stdin = ZKMStdin::new();
        stdin.write(&10);
        client.prove(&fibonacci_pk, stdin).compressed().run().expect("proving failed")
    });
    let proof_2 = tracing::info_span!("generate fibonacci proof n=20").in_scope(|| {
        let mut stdin = ZKMStdin::new();
        stdin.write(&20);
        client.prove(&fibonacci_pk, stdin).compressed().run().expect("proving failed")
    });
    let proof_3 = tracing::info_span!("generate fibonacci proof n=30").in_scope(|| {
        let mut stdin = ZKMStdin::new();
        stdin.write(&30);
        client.prove(&fibonacci_pk, stdin).compressed().run().expect("proving failed")
    });

    // Setup the inputs to the aggregation program.
    let input_1 = AggregationInput { proof: proof_1, vk: fibonacci_vk.clone() };
    let input_2 = AggregationInput { proof: proof_2, vk: fibonacci_vk.clone() };
    let input_3 = AggregationInput { proof: proof_3, vk: fibonacci_vk.clone() };
    let inputs = vec![input_1, input_2, input_3];

    // Aggregate the proofs.
    tracing::info_span!("aggregate the proofs").in_scope(|| {
        let mut stdin = ZKMStdin::new();

        // Write the verification keys.
        let vkeys = inputs.iter().map(|input| input.vk.hash_u32()).collect::<Vec<_>>();
        stdin.write::<Vec<[u32; 8]>>(&vkeys);

        // Write the public values.
        let public_values =
            inputs.iter().map(|input| input.proof.public_values.to_vec()).collect::<Vec<_>>();
        stdin.write::<Vec<Vec<u8>>>(&public_values);

        // Write the proofs.
        //
        // Note: this data will not actually be read by the aggregation program, instead it will be
        // witnessed by the prover during the recursive aggregation process inside Ziren itself.
        for input in inputs {
            let ZKMProof::Compressed(proof) = input.proof.proof else { panic!() };
            stdin.write_proof(*proof, input.vk.vk);
        }

        // Generate the plonk bn254 proof.
        client.prove(&aggregation_pk, stdin).plonk().run().expect("proving failed");
    });
}

In the host program, during the setup, the host will compile and load two guest programs as compiled ELF binaries: the AGGREGATION_ELF (representing the aggregation guest program) and FIBONACCI_ELF, whose corresponding guest program implementation can be found here. These programs are passed to client.setup() to generate the proving and verifying keys and to client.prove() to execute inside the zkVM and generate proofs. In this example, the host generates three compressed proofs proving the correct computation of Fibonacci for inputs n=10, 20, 30.

The host then prepares inputs corresponding to each Fibonacci proof for the aggregaton guest. Specifically, the host feeds the verification key hashes and raw public values as inputs and supplies the compressed proofs and full verification keys as witness data. The guest hashes the public values to a digest and calls verify_zkm_proof(vk_hash, digest) to check each proof. After all pass, the guest commits to the batch. That commitment becomes the public output of the aggregated proof.

The aggregation program is ran inside the zkVM and generates a Plonk proof (representing the aggregated proof) that certifies the validity of the three individual Fibonacci proofs.

As an overview what aggregation entails in Ziren:

• Generate individual proofs.
• Collect the verification keys and public outputs of the individual proofs.
• Inside another zkVM program (the aggregation guest), recursively verify all proofs.
• Commit to the batch as a single public commitment and generate a succinct new proof proving the correct execution of all individual proofs (the aggregated proof).

For computationally heavy applications, proving logic can be divided into multiple proofs and later aggregated into a single proof. In block-level aggregation, instead of re-executing transactions individually on-chain (which can incur high gas costs), a succinct proof attesting to the validity of all transactions in a block can be generated off-chain and verified on-chain. The aggregated proof can also be in other proof formats, such as STARK or Groth16. In addition to verification via smart contract deloyment, the aggregated proof can be verified off-chain using Ziren's WASM verifier.