Recursive proofs explained: proof aggregation, Halo and Nova-style folding
Post254 words
A recursive proof verifies another proof inside it, compressing many verifications into one. Covers classic verify-a-proof-in-a-proof recursion and IVC or folding schemes like Nova.
Key claims
Without recursion you verify N proofs, with recursion you verify one that attests to the other N
𝗪𝗧𝗙 𝗮𝗿𝗲 "𝗿𝗲𝗰𝘂𝗿𝘀𝗶𝘃𝗲 𝗽𝗿𝗼𝗼𝗳𝘀"?
A recursive proof is a proof that verifies another proof inside it. In zk terms, the outer proof says: “I verified a valid inner proof (or a whole chain of proofs), therefore the underlying computation is correct.” Halo (from the Zcash ecosystem) describes this idea as “recursive proof composition.”
Recursive proofs don’t “prove a new kind of truth.” They prove the same things as normal zk-proofs, but in a compressed form:
➀ Correctness of computation/state transitions (e.g., a rollup block transition was valid).
➁ Correctness of verification of other proofs (e.g., I checked N proofs, all valid).
That’s why recursion is commonly used for proof aggregation: bundle many proofs into one to reduce verification cost on-chain.
A nice mental model: without recursion, you verify N proofs (where N>1). With recursion, you verify 1 proof that attests it verified the other N.
There are two common patterns:
Ⓐ “Verify-a-proof inside a proof” (classic recursion)
➤ Build a circuit/program that runs the verifier for the proof system.
➤ Generate an outer proof that attests “the verifier accepted the inner proof.” Halo’s work is a well-known example of making recursive composition practical (and avoiding some trusted setup constraints depending on construction).
Ⓑ Incrementally Verifiable Computation (IVC) / folding (Nova-style recursion)
Instead of proving one huge computation at once, you prove it step by step and “carry forward” a small proof object. Nova frames this as proving incremental computations where each step is checked and folded into a running proof, enabling long-running/stateful computation proofs.
1 image on X