Proof Composition

Combine multiple zkVM proofs into a single verifiable computation

The Composition example demonstrates how to verify RISC Zero receipts inside a guest program, allowing multiple zkVM programs to be composed into a single proof.

What You’ll Learn

• How to verify receipts inside the zkVM
• How to use add_assumption() in the host
• How to use env::verify() in the guest
• Real-world applications of proof composition

Overview

Composition enables you to:

• Split programs into multiple parts proven by different parties
• Aggregate many proofs into one for efficient batch verification
• Create single receipts for multi-step workflows
• Preserve privacy by distributing computation across parties

How It Works

This example builds on the Hello World example by adding an RSA-like encryption step that requires proof of knowing the modulus factorization.

1. Step 1: Generate Initial Proof
2. Alice proves she knows a factorization of a composite number (similar to RSA keygen):
3. // Alice picks two numbers and multiplies them
   let (multiply_receipt, n) = multiply(17, 23);
   

4. Step 2: Add Assumption
5. The host adds the multiply receipt as an assumption that can be verified by the guest:
6. let env = ExecutorEnv::builder()
       // add_assumption makes the receipt available to the prover
       .add_assumption(multiply_receipt)
       .unwrap()
       .write(&(n, 9u64, 100u64))
       .unwrap()
       .build()
       .unwrap();
   

7. Step 3: Verify in Guest
8. The guest verifies that n has a known factorization, then performs modular exponentiation:
9. use hello_world_methods::MULTIPLY_ID;
   use risc0_zkvm::{guest::env, serde};
   
   fn main() {
       let (n, e, x): (u64, u64, u64) = env::read();
   
       // Verify that n has a known factorization
       env::verify(MULTIPLY_ID, &serde::to_vec(&n).unwrap()).unwrap();
   
       // Commit n, e, and x^e mod n
       env::commit(&(n, e, pow_mod(x, e, n)));
   }
   
   /// Compute x^e (mod n)
   pub fn pow_mod(x: u64, mut e: u64, n: u64) -> u64 {
       let mut x = x as u128;
       let n = n as u128;
       let mut z = 1u128;
   
       // Exponentiation by squaring
       while e > 0 {
           if e % 2 == 1 {
               z = (z * x) % n
           }
           e >>= 1;
           x = (x * x) % n;
       }
       return z as u64;
   }
   

10. Step 4: Verify Final Receipt
11. The final receipt proves both computations with a single verification:
12. receipt.verify(EXPONENTIATE_ID).unwrap();
    
    let (n, e, c): (u64, u64, u64) = receipt.journal.decode().unwrap();
    
    println!("{c} is the result of exponentiation by {e} under composite {n} with known factors");
    

What Gets Proven?

The final receipt proves two things simultaneously:

1. The modulus n has a known factorization (verified via composition)
2. The ciphertext c is the result of x^e mod n for some secret x

This is analogous to verifiable encryption - proving that a ciphertext is valid encryption to a public key that has a known secret key.

Running the Example

cargo run --release

Output:

43 is the result of exponentiation by 9 under composite 391 with known factors

Use Cases

Composition is powerful for multi-party computation and privacy-preserving workflows.

Privacy-Preserving Data Sharing

Produce a proof for a database query by joining receipts from queries over each privately-held shard. No single party sees the complete data.

Batch Verification

Aggregate many transaction proofs into one:

Tx1 Receipt + Tx2 Receipt + ... + TxN Receipt → Single Block Receipt

Image Processing Pipeline

Create a single receipt for a workflow with different filters:

Grayscale → Blur → Edge Detection → Single Receipt

Verifiable Encryption

Prove a ciphertext is valid encryption to a legitimate public key:

Proof of Key Validity + Proof of Encryption → Combined Receipt

Key Methods

add_assumption() (Host)

Makes a receipt available for verification in the guest:

let env = ExecutorEnv::builder()
    .add_assumption(prior_receipt)
    .unwrap()
    .build()
    .unwrap();

env::verify() (Guest)

Verifies a receipt inside the zkVM:

env::verify(IMAGE_ID, &journal_data).unwrap();

The Image ID ensures you’re verifying the expected program, and the journal data must match what was committed in the original proof.

Performance Considerations

• Composition adds overhead but provides powerful capabilities
• The final receipt size is constant regardless of composition depth
• Verification time is constant - verifying a composed proof is as fast as verifying a single proof

Next Steps

• Explore cryptographic signatures
• Learn about blockchain integration
• Build complex workflows with composition