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
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
- HyperNova: Recursive arguments for customizable constraint systems
- ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
- 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
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
- Talk: ZK Study Club: SuperNova with Srinath Setty
- Talk: CCS & HyperNova with Srinath - Folding Schemes FTW
- Forum: Privacy Scaling Explorations Discord Server
- Forum: Lurk Lab Zulip Server
- Talk: Advances in the Efficiency of Succinct Proofs (Ying Tong)
- 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