Folding Scheme

In technical terms, a folding scheme is a method for recursive proof composition. It operates on two Relaxed R1CS (Rank-1 Constraint System) instances, which represent computational claims. The prover takes these two instances and generates a single, new folded instance that is a commitment to both original ones. Crucially, the verifier's work to check the folded instance is significantly less than checking the two original instances separately, enabling efficient verification of long-running computations. This process is a core component of Nova, a prominent recursive SNARK.

The power of folding lies in its incrementally verifiable computation (IVC). In IVC, a prover executes a function step-by-step. After each step, it uses the folding scheme to combine the proof for the new step with the accumulated proof for all previous steps. This creates a single, constantly updated proof that attests to the correct execution of the entire sequence. Unlike traditional SNARKs that prove the entire computation at once, folding allows the proof to be built incrementally, which can be more memory-efficient for very long computations.

Folding schemes are distinguished from SNARKs (Succinct Non-interactive Arguments of Knowledge) by their lack of a succinct verification key and their non-succinct proof size. The output of a folding step is not a succinct proof itself but a folded instance that must still be proven. Therefore, a folding scheme is typically paired with a final, dedicated SNARK (like a Spartan-based proof) to compress the final folded instance into a single, small proof for practical use. This two-stage approach—folding for incremental computation and a final SNARK for succinctness—defines the architecture of Nova-like systems.

Key properties of a secure folding scheme include knowledge soundness (a prover can only create a valid folded instance if they know valid witnesses for the original instances) and zero-knowledge (the folded instance reveals no information about the witnesses). These properties are maintained recursively throughout the IVC process. The technique enables powerful scalability applications, such as proving the correct execution of a zkVM (zero-knowledge virtual machine) over millions of steps or creating parallelizable proof generation where different parts of a computation can be folded together.

A folding scheme is a cryptographic protocol that allows a prover to combine, or "fold," two instances of a computational statement (e.g., two Non-deterministic Polynomial (NP) statements) into a single new instance. Crucially, this new folded statement is of the same size and structure as the original inputs. The verifier's work is reduced to checking this single combined claim, along with a small, constant amount of auxiliary data. This process does not itself generate a zero-knowledge proof; instead, it accumulates computation in a compressed form, dramatically reducing the cost of eventual final proof generation.

The core mechanism relies on a commitment to a witness for each computation. In a typical step, the prover holds two Relaxed R1CS instances—a generalization of standard rank-1 constraint systems that includes an error term and a scalar. The folding verifier performs a simple, fast operation (often just elliptic curve additions and multi-scalar multiplication) to combine these into one new Relaxed R1CS instance. This iterative folding creates a recursive structure: the output of one fold becomes an input to the next, enabling the incremental processing of a long-running computation or a large batch of transactions.

The primary advantage of folding is its asymptotic efficiency. Unlike proving systems that require a monolithic proof for the entire computation, folding breaks the work into small, incremental steps with minimal verifier overhead. This makes it ideal for scenarios like incremental verifiable computation (IVC) and parallel proof generation. After many folding steps, a single, efficient zk-SNARK proof is created for the final folded statement, which validates the entire accumulated history. This two-phase approach—cheap folding followed by one final proof—is far more scalable for persistent state updates.

Nova, the seminal folding scheme, implements this using the Cycle of Curves technique. It uses two elliptic curves (e.g., Pasta curves or BN254/Grumpkin) where the scalar field of one matches the base field of the other. This allows the recursive circuit that performs the folding verification to be expressed efficiently without unbounded overhead, making the recursion non-trivial. Subsequent schemes like SuperNova extend this to support different virtual machines or functions at each step, called Nova-like or folding-based proof systems.

In practice, folding schemes are foundational for building high-throughput Layer 2 blockchains and co-processing engines. They enable a blockchain to maintain a succinct cryptographic commitment to its entire state history, where each new block is "folded" into this commitment. This allows for extremely lightweight clients to verify the chain's validity without re-executing all transactions, providing a powerful alternative to traditional rollup architectures by minimizing on-chain verification costs and enabling parallel proof construction.

A folding scheme is a cryptographic protocol that allows a prover to combine two instances of a computational statement into one, creating a single, smaller statement that maintains the validity of the original claims. This process, often visualized as 'folding' two pieces of paper into one, is the foundational mechanism behind Nova and other incrementally verifiable computation (IVC) systems. Unlike a zero-knowledge proof that verifies a single execution, a folding scheme recursively aggregates the work of many steps, enabling efficient proof generation for long-running computations like blockchain state transitions or machine learning training.

The core mechanism involves two primary components: a Relaxed R1CS (Rank-1 Constraint System) instance, which is a generalized form of a standard R1CS that can absorb errors or 'slack', and a folding verifier. In each iteration, the prover presents two instances: one representing the accumulated computation so far (the running instance) and one for the next step (the incremental instance). The folding verifier performs a low-cost, public-coin interaction, resulting in a single new relaxed R1CS instance. Critically, the verifier's work is minimal—requiring only a handful of group operations—shifting the heavy cryptographic lifting to the prover.

To visualize the process, consider proving the correct execution of a program with 1,000 steps. Instead of generating one massive proof, a folding scheme starts with Step 1. It then 'folds' Step 2 into the result of Step 1, creating a compact statement for Steps 1-2. This new statement is then folded with Step 3, and so on. After 1,000 folds, the prover holds a single relaxed R1CS instance representing the entire computation. A final, standalone zk-SNARK proof is then generated for this final folded instance, providing a succinct certificate of correctness for the whole sequence with minimal verification overhead.