paradigm where a long computation is broken into steps, and each step produces a cryptographic proof that
the previous step's proof was valid
one more unit of computation was performed correctly
enables verification of an arbitrarily long computation by checking only the final proof
key insight: the verifier never needs to see intermediate states, only the succinct proof at the end
prover at step i takes
the proof from step i-1
current input
produces a new proof that covers all steps 1..i
foundational construction for recursive proof composition
closely related to proof-carrying data which generalizes IVC from chains to DAGs
relies on folding as the efficient mechanism to absorb a proof into an accumulator rather than fully verifying it at each step
constructions
Nova: first practical folding scheme for R1CS, achieves IVC without SNARKs at each step
SuperNova: extends Nova to support multiple instruction types (non-uniform IVC)
HyperNova: generalizes folding to customizable constraint systems (CCS)
Protostar: non-uniform IVC with support for high-degree gates and lookups
applications in cyber
verifiable cybergraph state transitions: prove a chain of cyberlink insertions is valid
incremental relevance machine updates: each rank recomputation proves correctness of the previous one
light client protocols: a neuron can verify the full history of a shard by checking one proof
scalable validator pipelines: validators fold block proofs instead of re-executing all transactions
properties
succinctness: proof size is constant or logarithmic regardless of computation length
incrementality: each step adds only marginal cost over a single proof
composability: IVC proofs can be further composed with proof-carrying data for DAG-structured computations
related