Folding schemes and Nova: introduction to incrementally verifiable computation
Thread194 words
Short primer on folding schemes for incrementally verifiable computation. A folding scheme reduces checking two instances to one, so Nova can fold N circuit executions such as 10 signature checks into a single instance.
Key claims
Nova avoids a SNARK proof at each step by deferring proof construction
Folding reduces the check of two relation instances to a single instance
0/ 馃殌 THE ZK ENDGAME - FOLDING
brief introduction to the concept of folding in the context of zero knowledge proofs
馃У (0/6)
1/ folding schemes are a revolutionary approach to incrementally verifiable computation (IVC), fundamental to efficient and correct execution of computational steps in zk proofs
2/ a folding scheme for a relation R is a protocol that reduces the task of checking two instances in R to the task of checking a single instance in R
3/ the folding scheme in "Nova" for instance, enables recursive proof generation for zk arguments, providing a means to demonstrate the execution of a specific set of circuit instructions N times while eliminating redundant steps
4/ this approach offers significant efficiency gains. Let's consider a scenario where there are 10 signatures to be verified. Instead of running the circuit ten times and generating ten zk proofs for verification, Nova folds the circuit computation into single instance
5/ Nova adopts a deferred approach in constructing an Incrementally Verifiable Computation (IVC), which eliminates the need for SNARK proofs at each step
6/ by leveraging this approach, the verification process is streamlined, resulting in enhanced efficiency and computational performance.