Recursive Proof

Definition

A recursive proof is a cryptographic proof that verifies one or more other proofs inside the computation it proves. It lets a system replace many separate proofs with a smaller final proof whose verifier checks that the earlier proofs were valid. The final proof can attest to a long computation without making the on-chain verifier repeat every original step.

The phrase does not mean that any proof system can verify itself without special design. The circuit, proof format, cryptographic curve or field, and verifier must be chosen so that proof verification can be represented efficiently inside another proof.

How It Works

First, a prover creates proofs for smaller statements. For a rollup, each statement might say that a batch of transactions followed the rollup rules and changed state from one valid root to another. A recursive circuit takes several of those proofs as inputs. It runs their verification logic and checks that their public inputs connect correctly, such as ensuring one batch's ending state root is the next batch's starting root.

The prover then generates an outer proof for that recursive circuit. To a final verifier, the outer proof is evidence that all inner proofs verified and that their inputs formed a valid sequence. The system can repeat the process in a tree: combine many leaf proofs into intermediate proofs, then combine those into one root proof.

Proof size and verification cost can stay relatively small as the number of underlying transactions grows, depending on the proof system. Proving work does not disappear. It shifts to the party generating the proofs and can increase because verifying proofs inside a circuit is itself expensive.

Concrete Example

Assume a rollup creates one proof for each batch of 1,000 transactions. Batch 1 proves a state transition from root A to root B. Batch 2 proves a transition from root B to root C. Batch 3 and Batch 4 continue the same pattern.

A recursive aggregator receives the four proofs and their public state roots. It verifies each proof in a circuit and checks that A leads to B, B to C, and so on. It produces one aggregation proof stating that 4,000 transactions correctly changed the rollup state from A to E. The base chain verifies that single proof and updates its recorded rollup state from A to E.

Without recursion, the base chain could verify all four batch proofs separately. With recursion, it verifies one proof instead. For a larger system, aggregation can happen over many levels, so the base chain receives one proof covering thousands of batch proofs. The exact proof size, proving time, and cost depend on the selected system and implementation.

Limitations and Risks

Recursive proof systems are difficult to implement correctly. The inner verifier must be expressed as an arithmetic circuit or equivalent constrained computation. A mismatch between the native proof verifier and its in-circuit version can invalidate proofs or introduce a security flaw. Public inputs must be bound carefully, or a proof may establish a weaker statement than intended.

Proving can require substantial hardware, memory, and time. Recursive verification adds constraints, and aggregation can bottleneck during high activity. A compact proof is not automatically cheap on every chain.

The security result also depends on the inner proofs, outer proof system, trusted setup where applicable, implementation, and the statement being proved. Recursion cannot correct a faulty rollup circuit or dishonest data source. If the underlying transaction data is unavailable, a valid proof of a state transition may not let users reconstruct their balances or exit safely.

Relevant Distinctions

Proof aggregation combines several independent proofs into one proof. Recursive composition is a common way to do that, but systems can aggregate proofs through other techniques. Incremental verifiable computation is a related pattern where each new proof extends a running proof of a computation, rather than aggregating a fixed batch tree.

Recursive proofs are distinct from zero knowledge. Zero knowledge hides a witness, such as a private balance or secret key. Recursion proves that verification work occurred. A recursive proof can be public and reveal all its inputs, or it can be combined with zero-knowledge properties to hide selected inputs.

SNARKs and STARKs are proof-system families, not synonyms for recursion. Some constructions are designed to support efficient recursion, while others need additional curve cycles, folding schemes, or verifier optimizations. The relevant question is whether a specific system can efficiently verify its target proofs inside the outer circuit.