Proof Composition: Unlocking Recursion and Modularity for ZK Developers

Last week, we released v0.20 of the RISC Zero zkVM, which includes a new feature, proof composition

Proof composition makes it possible to verify proofs inside a zkVM program. This feature unlocks limitless possibilities in terms of what you can prove. Using proof composition, you can create a proof that attests to anything that has previously been proven. If Alice produces a proof of assets for her ETH account and her BTC account, she could compose them to produce a proof of combined assets. The path to maximal interchain operability has arrived: users can generate proofs about activity on any chain, they can aggregate as many proofs as they want into a single succinct proof, and they can verify the result on any chain. 

With RISC Zero, you can write native Rust, and import Rust crates to quickly develop your application. Over 700 of the most popular 1000 Rust crates are compatible with our zkVM, and we run nightly compatibility testing to monitor.  Using zk DSLs is slow and cumbersome, leading to higher development costs and longer timelines, plus the applications are not modular. Now, you can flexibly compose proofs from various zkVM programs into a more complex application , using Rust as the foundation.

We’re on a mission to make ZK production ready, at the fingertips of every Web3 developer. Enabling developers to flexibly leverage the Rust ecosystem was our first major contribution to making zk application development easy. Now, you can also flexibly leverage the RISC Zero ecosystem. 

Ready to start building? Visit RISC Zero's Docs.

What is proof composition?

RISC Zero’s Proof Composition feature allows any developer to access a powerful technique called recursive proving. Recursive proving is the gold standard in ZK, and one of the hardest things to achieve in a production environment, allowing existing proofs to be verified inside of new ones,  which allows for step function increases in scale, expressivity and cost reduction. 

To date, recursion has been extremely difficult to achieve, and limited in terms of user-facing functionality and generalizability. While a few teams have achieved recursion, it’s locked inside their own tech, not available for general utilization.

RISC Zero’s proofs are packaged into an object called a receipt. Composition allows users to verify a receipt inside a zkVM program. The result is a proof that a given receipt was verified. You can then repeat this process infinitely to build more and more complex applications that meet different requirements. 

What does proof composition enable?

This feature opens the door to a huge variety of new applications that can be developed quickly and easily with no prior knowledge of cryptography. 

Privacy preservation - Preserve privacy and data ownership by splitting a program into multiple parts, proven privately by the parties that hold the sensitive data.

  • E.g. Produce a proof that a ciphertext is a correct encryption of some value to a valid public key.
  • E.g. Produce a proof for a database query by joining receipts from the query over each privately held shard.

Proof aggregation - Aggregating many proofs into one for efficient batch verification.

  • E.g. Produce a proof for a block of transactions, where each transaction is itself verified by a receipt.

Modular guest programs - Create a single receipt for a workflow split into many different operations or modules, unlocking gains in prover efficiency and maintainability.

  • E.g. Produce a single receipt for the result of an image processing pipeline, where different filters are in their own guests.

Implications for Privacy

Privacy is a cornerstone of zero knowledge proofs, but being able to customize privacy options is challenging. Developers and users need customizable options depending on their needs. With composition, users can generate proofs about their private data, then have those proofs composed. This gives users maximal flexibility over how they handle their private data. 

How can I use it?

If you’ve already gotten started building a zkVM application and want to use composition, all you’ll need to do is run the env::verify() function inside your application. See the guest module of the risc0-zkvm crate for documentation, and check out this example for a practical demo. 

If you’re just getting started, check out the zkVM Quick Start page.

How does it work under the hood?

When env::verify() is called, the receipt isn’t verified right away. Instead, it appends to the receipt an “assumption”. If a receipt contains one or more assumptions, those assumptions must be resolved before receipt verification will pass.  

The term “assumption” is used similarly in plain English. Consider this sentence: “this shape is a rectangle assuming it's a square”. If we don’t know the shape is a square, we can’t decide whether it's a rectangle. We refer to receipts with unresolved assumptions as “conditional”.

On the receipt, an assumption represented by the hash of a receipt claim. The receipt claim contains all the public details of a zkVM execution, and most notably contains the journal and image ID. With this we can represent any statement verifiable by a computer. We could write a program that verifies a given shape is a square, and produces a receipt proving this to be the case. We can pass the claim from that receipt as input to a program that verifies a given shape is a rectangle by assuming it’s a square. We now have a conditional receipt that the given shape is a rectangle.

If there exists a receipt that proves this assumption to be valid, then the prover can use the RISC Zero recursion circuit to remove the assumption from the conditional receipt. This works by having the recursion circuit:

  • verify a receipt for the assumption, proving the assumption to be true, and also 
  • verifying the conditional receipt

If statement B is true, and statement A is true assuming B, then clearly A is true. Using that same logic, the recursion circuit converts the conditional receipt to an unconditional receipt by removing the assumption. Now this receipt will be accepted by any verifier.

The recursion circuit actually isn’t new. It’s the same system we use to unlock executions of unbounded length through continuations. It’s also extremely efficient, taking less than 2s on an NVIDIA GPU or Apple’s Metal accelerator. By using the assumptions system to offload receipt verification to our optimized prover, using composition has very little overhead. It also integrates with Bonsai’s highly parallel proving engine to further push the scale of computation possible in ZK.

Get Started