Recursive Zero-Knowledge Proofs and Proof Aggregation

Updated on Sep 28, 2026

10 min read

Zero-knowledge systems can prove that a computation was correct without making every verifier repeat that computation. As rollups and zkVMs process larger workloads, however, verifying each small proof separately can become costly. Recursive zero-knowledge proofs and proof aggregation address that scaling problem by letting one proof carry evidence about earlier proofs. This explainer covers how composition works, what it does and does not improve, and how developers can reason about the resulting trust and performance trade-offs.

Why Recursive Proofs Are Getting Attention

A rollup may execute thousands of transactions off-chain and submit a validity proof to a settlement contract. As workloads grow, proving is often split into smaller jobs that can run in parallel, while a final verifier still needs a compact way to accept the combined result. Recursive proof composition can make a later proof attest both to a new computation and to the validity of earlier proofs.

This creates a useful bridge between parallel proving and succinct verification: workers can produce proofs for separate segments, then combine them into a proof of a larger statement. Ethereum’s overview of zero-knowledge rollups describes the underlying rollup pattern: execute off-chain, publish data and commitments, and use a validity proof to check state transitions. Recursion is one way proving systems can organize that validity work as it scales; it is not a requirement of every rollup.

What Are Recursive Zero-Knowledge Proofs?

A zero-knowledge proof lets a prover convince a verifier that a statement is true without exposing the private witness used to establish it. A recursive proof is a proof whose computation includes checking one or more earlier proofs. Instead of a verifier checking every original computation directly, it checks a new proof that attests that the earlier proofs were valid and that their results were combined according to defined rules.

For example, a first proof might establish that a transaction batch transforms state root A into state root B. A second proof can verify that first proof and establish the next transition, from B to C. A final proof can then cover the entire chain of transitions. The verifier needs to check the final proof and its public output, rather than independently verifying every batch proof.

Proof aggregation is the broader goal of combining evidence about multiple proofs or computations into a smaller verification task. Recursive composition is one way to do it: a proof circuit verifies previous proofs while producing the aggregate proof. Some systems use “aggregation” and “recursion” interchangeably, while others distinguish proof composition, batch verification, and folding schemes. The useful question is what the final verifier checks and what statement the resulting proof actually guarantees.

The Halo paper on recursive proof composition is an influential example of this design space. It presents a way to compose proofs recursively without requiring a trusted setup for the composition system. The Mina recursion tutorial provides a practical example in which a program verifies an earlier proof and constrains a new public result.

The Problem It Solves

Without composition, a verifier may need to process many independent proofs. On a blockchain, each verification can consume execution resources, increase settlement costs, and add complexity to contracts and interfaces. Sending every proof separately can also make a final result harder to package for another system.

Recursive composition lets a prover combine those checks off-chain. The final verifier can receive one proof and a concise public statement, such as the initial and final state roots. This can reduce repeated verification work and make proof-producing workloads easier to split across machines.

The trade-off is that the proving system takes on extra work. It must implement the earlier verifier inside a new proof computation, preserve the meaning of every intermediate result, and ensure that state transitions connect correctly. A smaller or simpler verification step does not mean the underlying computation became free.

How Proof Composition Works

A typical recursive pipeline has four stages:

Prove smaller computations. A prover creates proofs for individual transactions, batches, or program segments. Each proof exposes only the public inputs and outputs needed for composition.
Check continuity. The next computation verifies the prior proof and constrains its starting state to match the earlier proof’s ending state. This prevents a valid proof for one state from being attached to an unrelated transition.
Build an aggregate statement. An aggregation circuit or proof program verifies one or more earlier proofs and proves that their public outputs satisfy the required relationship.
Verify the final proof. A contract, node, or application verifies the final proof against a verification key and consumes its public result.

The exact layout varies. Proofs can be joined in a chain, combined in a tree, or accumulated in stages. A tree can reduce the depth of a large aggregation job, while a chain may be simpler when each new proof naturally extends the previous state. Either way, every level must bind the inputs and outputs so proofs cannot be reordered, omitted, or replayed for a different statement.

Approach	What the verifier checks	Main benefit	Important limitation
Independent proofs	Each proof separately	Simple boundaries between jobs	Verification cost grows with proof count
Batch verification	Several proofs in one verifier operation	Shares some verification overhead	Does not necessarily create one reusable aggregate proof
Recursive composition	One proof that verifies earlier proof(s) and new work	Compact final verification and layered proving	The outer proof must faithfully encode the inner verifier
Proof folding	An accumulated relation that is finalized later	Efficient incremental accumulation in suitable systems	The accumulated instance is not always a final proof by itself

These terms are not perfectly standardized across implementations. Compare the actual proof statement, verifier interface, setup assumptions, and public inputs rather than assuming that every product called an “aggregator” works the same way.

Key Components and Design Choices

Base proofs establish local statements, such as a program segment’s output or a batch’s state transition. Their public inputs are the interface between layers; excessive public data can make proofs larger or more expensive to compose.

The recursive verifier checks earlier proofs inside the next proving computation. Proof systems must make this verifier efficient to represent. Some designs use compatible or “cycle” curves so the arithmetic used by one proof system can verify proofs from another without prohibitive overhead. Other systems specialize their proof systems or use different composition techniques.

State commitments and ordering connect the pieces. A rollup proof should bind the previous and next state roots, chain or application context, and any relevant batch identifier. Without these constraints, a final proof may verify while describing a discontinuous or incorrectly ordered sequence.

The final verifier and trust model determine the actual system guarantee. The on-chain verifier must use the correct verification key and public inputs. A trusted setup, where required, is a separate assumption from recursion itself; recursive composition does not automatically remove it. Nor does it eliminate the need to audit circuits, verifier code, and upgrade processes.

Real-World Uses

Rollup batch composition: A rollup can prove smaller transaction batches independently and recursively combine their state transitions before settlement. This can reduce the number of proof verifications at the destination, though data publication and availability remain separate requirements.
zkVM execution: A virtual machine can divide a long program into segments, prove each segment, and compose the results into evidence for the complete execution. This helps parallelize work while preserving one final program result.
Incremental applications: An application that updates a state over time can maintain a proof of its history, then extend that proof as new valid updates arrive. Mina’s tutorial demonstrates a simplified version of this idea by recursively verifying a previous proof.
Proof networks and shared verification: An aggregator can combine proofs produced by different workers or applications, but it must enforce compatible statement formats, verification rules, and security assumptions. A common verifier does not make the underlying proof systems interchangeable.

These patterns primarily reduce verification and coordination overhead at the composition boundary. They do not, by themselves, make transaction data available, guarantee that a prover is always online, or make a computation private if its public inputs reveal the information.

Getting Started with a Recursive Proof

For a guided implementation, Mina’s official recursion tutorial uses o1js and the SelfProof type to pass an earlier proof into a later method. The tutorial’s starter commands are:

npm install -g zkapp-cli
zk project 09-recursion

Inside a ZkProgram, a recursive step can verify its prior proof and constrain the new public state. This TypeScript method is a fragment to place in the program’s methods object:

addNumber: {
  privateInputs: [SelfProof, Field],
  async method(
    newState: Field,
    previousProof: SelfProof<Field, void>,
    amount: Field,
  ) {
    previousProof.verify();
    newState.assertEquals(previousProof.publicInput.add(amount));
  },
},

The important pieces are the SelfProof input, the explicit verification call, and the constraint linking the new state to the previous proof’s public input. In a real rollup, the public state would usually be a commitment such as a state root, and the circuit would also bind chain context and batch ordering. The tutorial continues through compiling and verifying the final proof; use that complete example rather than treating this fragment as a production rollup.

Before adopting a recursive design, measure the whole pipeline: proving time and memory, proof size, aggregation depth, final verification cost, and recovery behavior if an aggregation worker fails. Verify the final proof independently and test negative cases, including a wrong previous state, reordered proofs, and a mismatched verification key. Keep data availability, prover liveness, and upgrade controls explicit in the system design.

Common Misconceptions

“Aggregation always means one proof.”

Batch verification may process several proofs more efficiently without creating a single proof that can be passed to another verifier. Recursive composition usually produces a proof of an outer statement, but specific aggregation designs differ. Inspect the output format and its verification contract.

“A recursive proof makes proving cheap.”

Recursion moves verification work into another proving computation. That can reduce repeated work for the final verifier, but the prover may need substantial additional compute, memory, or specialized hardware. The right comparison is end-to-end cost and latency, not only final proof size.

“A valid aggregate proves the data is available or private.”

A proof establishes only the statement encoded by its circuit. It cannot prove that users can retrieve omitted transaction data unless the protocol separately provides and enforces an availability guarantee. Likewise, zero knowledge hides witness data only when the protocol is designed to do so; public inputs and outputs remain visible.

“All proof systems compose in the same way.”

Proof formats, verifier circuits, security assumptions, and setup requirements vary. Composing proofs across systems requires explicit compatibility and security analysis, not simply concatenating proof bytes.

Changelog

2026-09-28: Initial publication.