Incrementally Verifiable Computation (IVC)

The defining property of IVC is that the proof size does not grow with the length of the computation. After each step, the prover updates a fixed-size proof that attests to the correctness of all previous steps. This is achieved through recursive proof composition, where the verification algorithm itself is expressed as a circuit. The verifier checks only the final proof, which is the same size whether the computation ran for 10 steps or 10 million steps.

Unlike monolithic proving systems that require the entire computation trace upfront, IVC allows the prover to generate proofs incrementally as each step executes. At step i, the prover takes the proof from step i-1 and the current step's witness, producing a new proof that covers steps 1 through i. This enables streaming computation verification and is essential for long-running processes like blockchain execution or ML training loops.

Modern IVC constructions like Nova use folding schemes to achieve efficient recursion. Rather than fully verifying a proof at each step, a folding scheme reduces two instances of a constraint system into a single instance. This defers expensive cryptographic operations, dramatically improving prover performance. Key concepts include:

• Relaxed R1CS: An extension of R1CS that admits efficient folding
• Committed Relaxed R1CS: Adds homomorphic commitments for non-interactive folding
• NIFS (Non-Interactive Folding Scheme): The core protocol that compresses two claims into one

Proof Carrying Data (PCD) extends IVC to distributed computations. Multiple provers can independently generate proofs for different branches of a computation, and these proofs are later merged into a single proof. This enables parallel proving architectures where:

• Each shard or thread produces its own proof
• A coordinator merges proofs without re-executing the underlying computation
• The final proof attests to the correctness of the entire distributed execution graph

IVC is critical for zero-knowledge machine learning where training or inference spans many sequential layers. Rather than proving the entire model execution in one massive circuit, IVC enables:

• Layer-by-layer proving: Each neural network layer generates an incremental proof
• Constant verification cost: Verifying a 1000-layer model costs the same as verifying a single layer
• Memory efficiency: The prover only holds the current proof and layer witness, not the entire trace Systems like Nova and Halo2 are used to build practical zkML provers.

Many IVC constructions require a cycle of elliptic curves to implement recursive verification. Since the verification circuit operates over a finite field, and the proof itself is defined over a different field, a pair of curves is needed where:

• Curve 1's base field equals Curve 2's scalar field
• Curve 2's base field equals Curve 1's scalar field This allows the verifier circuit to natively perform operations on the proof elements. Common cycles include Pasta curves (Pallas/Vesta) used in Halo2 and Nova.

A cryptographic primitive that generalizes IVC to distributed computations across multiple parties. Each participant receives an input and a proof of prior execution, performs their step, and produces a new proof attesting to the correctness of the entire lineage. Unlike IVC's single-prover sequential model, PCD handles branching and merging of computation paths, making it essential for verifying distributed ledgers and multi-agent workflows.

The core mechanism enabling IVC: the verifier algorithm itself is expressed as an arithmetic circuit, allowing a prover to generate a proof that attests to the validity of a previous proof. This creates a chain where each step proves 'the previous state was valid AND the current transition was correct.' The key engineering challenge is minimizing the recursive overhead—the cost of verifying a proof inside a circuit—which systems like Nova and Halo2 address through different cryptographic approaches.

A cryptographic technique that reduces the task of checking two instances of a constraint system into checking a single instance. Rather than verifying each step's proof in full, a folding scheme 'accumulates' the verification work, deferring expensive operations to the final step. This is the key insight behind Nova: by folding the witness at each step, the prover avoids the cost of full recursive verification, achieving near-native computation speeds for IVC.

A recursive zkSNARK proving system developed by the Electric Coin Company that eliminates the need for a trusted setup through inner product arguments. Halo2 achieves IVC by using a cycle of elliptic curves where the verifier circuit on one curve is natively verified on the other. Unlike Nova's folding approach, Halo2 performs full recursive verification at each step, making it more expensive per step but providing a different set of security and composability trade-offs.

The foundational representation of computation for all ZKP systems, including IVC. A directed acyclic graph expressing a computation as addition and multiplication gates over a finite field. For IVC, the step computation must be expressed as a circuit, and critically, the verification algorithm must also be circuitized. The efficiency of IVC depends heavily on how compactly the verification logic can be represented as gates—this is why STARK-friendly hash functions like Poseidon are preferred over SHA-256 in these systems.