Optimizing ZKP Sizes

This article presents an official optimization method for a Zero Knowledge Proof (ZKP) system known as Risc0. The method reduces the ZKP sizes, making it an ideal solution for Blockchain applications.

The target audience of this article are primarily developers with a Rust background who are either already using Risc0 or have prior hands-on experience with other ZKP systems.

Risc0 Introduction

Risc0 is a Zero Knowledge Virtual Machine (ZKVM) that utilizes RISC-V architecture to ship a verifiable computation environment. This means, that every instruction executed by the RISC-V CPU is proven cryptographically, therefore the output of a program is correct for the composition of its instructions.

Compared to other Zero Knowledge Proof systems, Risc0 offers a developer-friendly alternative, because it ships a Rust toolchain alongside it’s zkVM. Therefore the execution of any program written in Rust can be verified. Rust developers won’t have to leave their comfort zone to implement Zero Knowledge solutions, which is an advantage that is not to be underestimated when comparing zkVMs like Risc0 to languages like Circom or Noir.

Wrapper proofs

Even though Risc0’s zkVM offers great developer experience, there are downsides to relying on it. The size of any proof of computation grows with the associated Rust program thereby quickly exceeding Blockchain space constraints. During development of a proof of concept Zero Knowledge Rollup system, a conjunction of basic operations quickly exceeded a receipt size of several MB. When executing Smart Contracts on the Casper blockchain (V 1.5.x), the maximum amount of RAM available for a WASM session is 4 MB. It can be concluded that a means of compressing Risc0 proofs is necessary to unleash its potential in Blockchain applications.

This is where “wrapper proofs” enter the scene. Instead of committing a large proof to a Blockchain, a more concise proving system e.g. a SNARK (Succinct Non-Interactive Argument of Knowledge) prover like Groth16 is used to generate a “wrapper proof” over the Risc0 STARK (Scalable Transparent Argument of Knowledge) proof. An introduction to the differences between STARKs and SNARKs can be found here. The Risc0 team have successfully implemented a universal Circom circuit that can be used to wrap any Risc0 proof generated with the Risc0 default prover in a succinct Groth16 proof.

Basic benchmark: SHA256

For the sake of demonstrating the succinctness of Groth16 wrapper proofs, we will use a Risc0 guest program that utilizes SHA256 hashing and generate a compressed proof. The related code can be found here.

Take a look at the code in the Risc0 guest program. This will compute the same hash n times and commit each hash to the public output / the proof journal:

...
#[derive(Serialize, Deserialize)]
struct Output {
    sha256_hashes: Vec<Digest>,
}
fn main() {
    // read the input
    let rounds: u32 = env::read();
    let mut output_hashes: Vec<Digest> = Vec::new();
    for i in 0..rounds {
        let sha_input = [1u8; 32];
        let sha_hash: Digest = *Impl::hash_bytes(&sha_input);
        output_hashes.push(sha_hash);
    }
    let output: Output = Output {
        sha256_hashes: output_hashes,
    };
    env::commit(&output);
}

And the host function that uses the guest program code to generate a compressed Groth16 proof of computation.:

...
#[cfg(feature = "groth16")]
fn snark2stark(rounds: u32) {
    let env = ExecutorEnv::builder()
        .write(&rounds)
        .unwrap()
        .build()
        .unwrap();
    let mut exec = ExecutorImpl::from_elf(env, RISC0SHA_ELF).unwrap();
    let session = exec.run().unwrap();
    let opts = ProverOpts::default();
    let ctx = VerifierContext::default();
    let prover = get_prover_server(&opts).unwrap();
    let receipt = prover.prove_session(&ctx, &session).unwrap();

    let claim = receipt.get_claim().unwrap();
    let composite_receipt = receipt.inner.composite().unwrap();
    let succinct_receipt = prover.compress(composite_receipt).unwrap();
    let journal = session.journal.unwrap().bytes;

    println!("identity_p254");
    let ident_receipt = identity_p254(&succinct_receipt).unwrap();
    let seal_bytes = ident_receipt.get_seal_bytes();

    println!("stark-to-snark");
    let seal = stark_to_snark(&seal_bytes).unwrap().to_vec();

    println!("Receipt");
    let receipt = Receipt::new(
        InnerReceipt::Compact(CompactReceipt { seal, claim }),
        journal,
    );
    let receipt_serialized = bincode::serialize(&receipt);
    println!("Proof size: {:?}", &receipt_serialized.unwrap().len());
    let output = receipt.verify(RISC0SHA_ID).unwrap();
}

In order to run the prover with Groth16 optimization, it is required that an instance of Docker is running so that the risc0-groth16 image can be pulled.

Currently it is only possible to run risc0-groth16 on x86-* architecture, therefore ensure that your machine or virtual environment meet this requirement.

To run the SHA256 Benchmark, pull the repository:

git clone git@github.com:cspr-rad/sha256-zk-benchmark
cd sha256-zk-benchmark
cd risc0-sha256
cargo run --features groth16

Example output:

773 is the size of the optimized proof in bytes.

In addition to this Risc0-Groth16 benchmark, I prepared a comparison of proving time and proof size for Risc0, Risc0-Groth16 and a new ZKVM named SP1. Note that SP1 currently depends on curve25519-dalek v4.1.2 which does not properly build on x86–64 architecture. Read more on this issue here. Since Risc0-Groth16 only builds on x86–* architecture, I had to use different machines for the benchmarks and chose an M2 MacBook Air with 8GB of Ram for SP1 and an Ubuntu x86–64 8-core with 32 GB of Ram for Risc0. Comparing proving speed between Risc0, Risc0-groth16 and SP1 based on the data is therefore not sensible.

The proof size benchmarks however are expected to be consistent throughout different architectures:

Having run the Risc0 Benchmark on the M2 MacBook Air as well, I found that the proof generation was indeed faster than with SP1. This could be related to the sub-circuit implementation of SHA256 for Risc0 and SP1 respectively.

For details see SP1 precompiles and Risc0 guest optimization.

Please note that the journal was purposefully included in the proof size since this benchmark compares the proof size for the same set of public inputs / outputs for each iteration of sha256. The conditions for each proving system are equal therefore the relative growth in proof size is meaningful in a smart contract context.

Limitation: Trusted Setup

The utilization of Groth16 introduces a new limitation, known as “trusted setup.” Before one can leverage Groth16 for optimization, a randomness-inducing ceremony must be held. An introduction to this topic is located in Circom’s documentation.

Circom is a zero-knowledge language and compiler (not ZKVM!) that leverages Groth16 to generate proofs. The trusted setup is a separate challenge and not part of this example. For a production system, one would have to ensure that the ceremony is set up correctly and that randomness is properly introduced to the Groth16 prover.