Incrementally verifiable computation (IVC) lets a program prove its own execution one step at a time, so a verifier checks one short proof instead of replaying every step. Blockchains benefit directly, because nodes download and validate the full history before trusting the current state. Incrementally verifiable computation replaces the history with a proof of fixed length, and each new block updates the proof without enlarging it.
Researchers at Microsoft Research, Carnegie Mellon University and New York University introduced a fast construction named Nova in 2021, and later schemes extend the approach to virtual machines and customizable constraint systems.
Why Chain History Burdens Verifiers
A full node validates every block from genesis, which forces each new participant to replay the entire ledger. Zero-knowledge proofs shorten the check of one computation, yet a list of independent proofs still gains one entry per block.
Concatenating n proofs produces a certificate n times longer than one proof, so verification time grows with the block count.
Recursive composition removes the growth: the prover takes the proof covering the first steps, executes one more step, and outputs a proof covering every step so far. The work of each update stays independent of the steps already executed, and the verifier’s work stays independent of the step count.

A verifier in an incrementally verifiable computation system holds a verification key, the claimed initial and current states, and the proof. The check confirms the current state results from applying the step function the stated number of times to the initial input.
For a blockchain, the step function is the block validity rule: it checks signatures, applies transactions to the ledger state and tests consensus conditions. Recursive zero-knowledge proofs make the construction practical, although early recursive systems embed a full SNARK verifier inside the circuit of the next proof, and the embedded verifier dominates the cost of every step.
Nova Folds Two Instances Into One at Every Step
Nova realizes incrementally verifiable computation with a folding scheme, a protocol reducing the check of two NP instances to the check of one.
Plain R1CS constraints are quadratic, so combining two witnesses with a random scalar produces cross terms between them. Nova adds an error vector and a scalar to the constraint relation, producing relaxed R1CS, where the error vector absorbs the cross terms and the relation stays closed under random linear combination.
At each step the prover runs the step function with a small folding verifier, packaged as an augmented circuit. The augmented circuit folds the new instance into a running instance and outputs a hash of the step count, the initial input, the current state and the running instance.
Each step costs the prover two multiexponentiations sized to the step circuit, and the recursion overhead stays constant at about 10,000 multiplication gates, dominated by two group scalar multiplications.

Nova needs no trusted setup and no fast Fourier transforms, and a compressing SNARK based on Spartan reduces the final proof to a logarithmic number of group elements.
Proof size depends on the step circuit and never on the number of steps, which gives a succinct chain its constant-size proof and keeps incrementally verifiable computation affordable for verifiers.
SuperNova and HyperNova Widen the Step Function
SuperNova generalizes incrementally verifiable computation into non-uniform IVC, where each step invokes one of several circuits, including the instructions of the EVM or RISC-V. Earlier designs wrap every instruction in a universal circuit, so the prover pays for the combined size of all instruction circuits at each step.
SuperNova charges the prover only for the circuit of the invoked instruction, and the recursion overhead matches Nova’s. A machine with a single instruction reduces SuperNova to Nova.
HyperNova applies incrementally verifiable computation to customizable constraint systems (CCS), a format generalizing Plonkish, R1CS and AIR without overhead. The prover’s cryptographic cost per step falls to a single multi-scalar multiplication sized to the number of variables, the optimum for commitments built on multi-scalar multiplication.
One MinRoot iteration needs three R1CS constraints but only one degree-5 Plonkish constraint, and CCS keeps the shorter form. HyperNova also folds several instances in one step and randomizes proofs with folding, reaching zero-knowledge without zkSNARKs.

Curve Cycles and CycleFold Carry the Recursion
A folding verifier performs elliptic-curve scalar multiplications, and the arithmetic of a curve runs over a field different from the field of the circuit proving it.
A cycle of elliptic curves resolves the mismatch: the scalar field of the first curve equals the base field of the second, and the reverse holds, so each curve’s circuit checks the other curve’s group operations.
The Nova reference implementation supports Pallas/Vesta, BN254/Grumpkin and secp/secq. Pallas and Vesta, together called the Pasta curves, come from the Electric Coin Company’s Halo 2 work for Zcash, and Mina adopted the same pair. Nova requires about 10,000 multiplication gates on both curves of the cycle to express the folding verifier as a circuit.

The CycleFold technique shrinks the circuit on the second curve to one scalar multiplication of roughly 1,000 to 1,500 gates and folds invocations of the small circuit on the first curve, a reduction of nearly one order of magnitude.
The Halo proof system, published in 2019 by Sean Bowe, Daira Hopwood and Jack Grigg, had already demonstrated recursive proof composition without a trusted setup over ordinary curve cycles by amortizing the verification of inner product arguments.
Constant-Size Chains Move Into Production Tooling
Mina Protocol applies recursive proving, a close relative of incrementally verifiable computation, to a layer-1 blockchain, and its Pickles recursion layer, built on the Kimchi proof system, holds the chain at a fixed 22 KB regardless of transaction history. The proof certifies well-formed, signed transactions and compliance with consensus rules.
Pickles uses SNARK-based recursion rather than folding, so Mina serves as a deployed reference for the size target Nova-style schemes pursue with the smallest recursion overhead reported in the literature.
A folding-based design would work the same way: each block header carries the running instance, each new block folds one step into it, and validators store only the compressed proof, the verification key and the latest block.
A final decider converts the running instance into a short SNARK, and an Ethereum smart contract can verify the decider’s proof. The Sonobe library, built by 0xPARC and Privacy and Scaling Explorations, implements Nova, HyperNova, ProtoGalaxy and CycleFold with Groth16 and KZG backends and generates Solidity verifier contracts for Nova with CycleFold.
How a folding-based chain stays constant-size
- Carry the running instance. Each block header holds the running instance that summarizes all earlier blocks.
- Run the step function. The prover checks the new block against the validity rule: signatures, transactions applied to the ledger state and consensus conditions.
- Fold the new instance. The augmented circuit folds the new instance into the running instance and outputs a hash of the step count, the initial input, the current state and the running instance.
- Store only the essentials. Validators keep the compressed proof, the verification key and the latest block.
- Convert with a decider. A final decider turns the running instance into a short SNARK.
- Verify on-chain. An Ethereum smart contract checks the decider’s proof.
Total proving time grows linearly with the block count, since every step requires one fold, while per-step proving cost and verification cost stay flat.
Incrementally verifiable computation shifts the burden from verifiers to provers, and folding schemes keep the prover’s burden at a few multiexponentiations per block. Chains built on incrementally verifiable computation would verify unlimited history with storage fixed by the step circuit.
Pros
- Proof size depends on the step circuit and never on the number of steps.
- Verifier work stays independent of the step count.
- Nova needs no trusted setup and no fast Fourier transforms.
- The prover pays only a few multiexponentiations per block, with a constant recursion overhead of about 10,000 gates.
What to watch out for
- Total proving time grows linearly with the block count, because every block adds one fold.
- The burden shifts from verifiers to provers.
- The folding verifier needs a cycle of elliptic curves. Nova uses about 10,000 gates on both curves, and CycleFold reduces the second-curve circuit.
- Tooling is still young. The maintainers of Sonobe label the library experimental.
FAQ
What is incrementally verifiable computation?
Incrementally verifiable computation is a cryptographic technique in which a prover updates a proof after each step of a long computation. The updated proof covers every step executed so far, and a verifier checks it at a cost independent of the step count.
How does Nova keep proof size from growing?
Nova folds each new step into a running relaxed R1CS instance instead of verifying a full SNARK inside the circuit. The running instance has a size tied to the step circuit, so proof size stays constant as the number of steps rises.
What does SuperNova add to Nova?
SuperNova supports non-uniform IVC, where each step invokes one of several circuits, including individual EVM or RISC-V instructions. The prover pays only for the invoked instruction circuit instead of a universal circuit covering every instruction.
Why do folding schemes use a cycle of elliptic curves?
A folding verifier performs scalar multiplications on a curve whose base field differs from the field of the circuit. A cycle of curves aligns the fields in both directions, and CycleFold limits the second-curve circuit to one scalar multiplication of roughly 1,000 to 1,500 gates.
Can a blockchain keep a constant size with unlimited history?
Verification data stays constant: Mina Protocol holds its chain at about 22 KB with recursive SNARKs. Total proving work still grows linearly with the block count, because each block adds one recursive step.

Isai Alexei is a journalist and financial analyst covering cryptocurrency markets and traditional securities for Blockchaindose. He has spent ten years analyzing digital assets, trading activity, and market structure.








