A curated list of awesome resources related to zero-knowledge folding schemes. Folding schemes are a revolutionary approach to incrementally verifiable computation (IVC), fundamental to efficient and correct execution of computational steps in Zero-Knowledge Proofs.
- Writings (papers, blog posts, etc)
- Code (software repositories)
- Other resources (podcasts, etc)
- Applications
A gentle introduction to Plonk-like arithmetization, lookup arguments and the birth of lookup arguments in the Plonk world.
The final SNARK used in Nova (only using MSMs)
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
- The paper that introduced incrementally-verifiable computation and the notion of recursive composition of proofs.
- Proof-Carrying Data and Hearsay Arguments from Signature Cards
- The paper that introduced proof-carrying data, a generalization of incrementally-verifiable computation to arbitrary graphs (IVC considers only a chain of computation)
- Recursive composition and bootstrapping for SNARKS and proof-carrying data
- This paper provides firm theoretical foundations for PCD and IVC.
- Scalable Zero Knowledge via Cycles of Elliptic Curves
- This paper introduces the notion of pairing-friendly cycles of curves, and shows how to use these to construct the first concretely efficient IVC/PCD scheme.
The prototype of the delayed proving approach which Nova puts on steroids.
Aggregation schemes show how to extend the aggregation ideas in Halo to any additively-homomorphic PC scheme, and construct PCD from these.
Accumulation schemes are a generalization of both Halo-style aggregation and Nova-style folding schemes that allow analyzing these ideas in a single system. The papers below show how to use efficient accumulation schemes for certain predicates (e.g., polynomial commitments) to construct efficient PCD schemes.
Classic works on the Nova proof system, including seminal papers and accompanying presentations.
- Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
- SuperNova: Proving universal machine executions without universal circuits
- Sangria: a Folding Scheme for PLONK
-
Revisiting the Nova Proof System on a Cycle of Curves
- Presentation
- This paper analyzes the security of the Nova proving system when implemented on a cycle of curves.
The paper exploits a soundness bug in the original implementation (since patched) and produces a
convincing proof of
$2^{75}$ rounds of the Minroot VDF in 1.46 seconds. A new optimized and secure system is introduced together with a formal security proof.
-
CycleFold: Folding-scheme-based recursive arguments over a cycle of elliptic curves
- CycleFold uses the second curve in the cycle to merely represent a single scalar multiplication ( 1,000--1,500 multiplication gates). CycleFold then folds invocations of that tiny circuit on the first curve in the cycle. This is nearly an order of magnitude improvement over the prior state-of-the-art in terms of circuit sizes on the second curve.
Extensions to the Nova proof system that explore PCS in terms of linear codes, folding, and other concepts.
- Linear algebra and zero-knowledge
- Origami – A Folding Scheme for Halo2 Lookups
- Folding for Arbitrary Polynomial Custom Gates and Lookups
- Folding endgame
- Customizable constraint systems for succinct arguments This paper introduces customizable constraint system (CCS), a generalization of R1CS that can simultaneously capture R1CS, Plonkish, and AIR without overheads.
- HyperNova: Recursive arguments for customizable constraint systems This paper introduces HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS. The prover’s cost at each step is dominated by a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme.
- ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols We provide a generic, efficient accumulation scheme for any (2k-1)-move special-sound protocol with a verifier that checks l degree-d equations. The accumulation verifier only performs k+2 elliptic curve multiplications and k+d+O(1) field/hash operations.
- ProtoGalaxy: Efficient ProtoStar-style folding of multiple instances Building on ideas from ProtoStar, we construct a folding scheme where the recursive verifier's "marginal work", beyond linearly combining witness commitments, consists only of a logarithmic number of field operations and a constant number of hashes. Moreover, our folding scheme performs well when folding multiple instances at one step.
- nova-study: Implementation of Nova using arkworks-rs just forlearning purposes.
- supernova: Experimental implementation of the SuperNova protocol
- multifolding-poc: Experimental implementation of HyperNova
- ccs-hack: a hack implementation of CCS generic implementation
- protogalaxy-poc: Proof of concept implementation of ProtoGalaxy
Code implementations and explorations related to the Nova proof system, including benchmarks, specifications, and experimental versions.
- Podcast: ZK-Podcast Episode 277: Nova and beyond with Srinath Setty
- Podcast: ZK-Podcast Episode 280: ProtoStar with Benedikt Bünz and Binyi Chen
- Podcast: Zk-Podcast Episode 281: Exploring Lurk: a new Language for Recursive zk-SNARKs with Chhi'mèd Künzang and François Garillot
- Talk: ZK Study Club: SuperNova with Srinath Setty
- Talk: CCS & HyperNova with Srinath - Folding Schemes FTW
- Talk: Advances in the Efficiency of Succinct Proofs (Ying Tong Lai)
- Talk: Folding Circom circuits: A ZKML case study (Cathie So)
- Talk: ZK Study Club: Protostar with Binyi Chen
- Talk: (Super)Nova (Scotia): Unpacking Nova
- Talk: Folding Scheme Math Buildding Blocks (Ying Tong Lai)
- Talk: SuperNova and Parallelizing Nova (Carlos Perez, Nalin Bardaj)
- Talk: Nova Track Ad-Hoc Session: ZK Week Research Projects Discussion (Barry Whitehat, Justin Drake, Nalin Bardaj)
- Talk: Ad-Hoc Session on Goblin PLONK + Nova (Zachary Williamson)
- Forum: Privacy Scaling Explorations Discord Server
- Forum: Lurk Lab Zulip Server
- Nova-Scotia
- This repository provides necessary middleware to take generated output of the Circom compiler (R1CS constraints and generated witnesses) and use them with Nova as a prover.
- Lurk
- Lurk is a Turing-complete programming language for recursive zk-SNARKs. It is a statically scoped dialect of Lisp, influenced by Scheme and Common Lisp.
- Youtube account
- Talks: ZK Summit 9, ZKProof workshop
- Nova-SHA256
- This repository provides a SHA-256 implementation utilizing Nova to repeatedly apply the SHA-256 compression function at each step.
- The implementation utilizes SHA-256 from the bellperson library