Awesome-Folding

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)
  • Prequels
    • Arithmetization
    • Spartan
    • IVC and PCD
    • Halo
    • Aggregation schemes
  • Accumulation schemes
  • Classic Nova
  • Nova Extensions (without high-degree gates)
  • HyperNova / ProtoStar : The next generation (with high-degree gates)
  • Deep Space Nine (New commitment schemes, new lookup & proof arguments)
• Code (software repositories)
  • Reference implementations
  • Teaching / experimental implementations
  • Code Explorations
• Other resources (podcasts, etc)
  • Podcast episodes
  • Talks & Lectures
    • Zuzalu talks
    • Articles
  • Forums
• Applications

Writings (papers, blog posts, etc)

Prequels

Arithmetization

A gentle introduction to Plonk-like arithmetization, lookup arguments and the birth of lookup arguments in the Plonk world.

• From AIRs to RAPs
• A Brief history of lookup arguments
• Multiset checks in PLONK and Plookup

Spartan

The final SNARK used in Nova (only using MSMs)

• Spartan: Efficient and general-purpose zkSNARKs without trusted setup

IVC and PCD

• 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.

Halo

The prototype of the delayed proving approach which Nova puts on steroids.

• Recursive Proof Composition without a Trusted Setup

Aggregation schemes

Aggregation schemes show how to extend the aggregation ideas in Halo to any additively-homomorphic PC scheme, and construct PCD from these.

• Halo Infinite: Recursive zk-SNARKs from any Additive Polynomial Commitment Scheme
  • Presentation

Accumulation schemes

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.

• Proof-Carrying Data from Accumulation Schemes
  • Presentation
• Proof-Carrying Data without Succinct Arguments
  • Presentation

Classic Nova

Classic works on the Nova proof system, including seminal papers and accompanying presentations.

• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
  • Presentation
• SuperNova: Proving universal machine executions without universal circuits
  • Presentation
• Sangria: a Folding Scheme for PLONK
  • Presentation
• 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.
• Reverie: an end-to-end accumulation scheme from Cyclefold
  • "In this technical note, we propose an informal notion of an end-to-end IVC scheme, which means that the amount of data that the prover needs exchange with the previous prover to continue the computation is small. We explore the existing design space from this point of view, and suggest an approach to constructing such a scheme by combining the PlonK proof system with the recent Cyclefold construction."

Nova Extensions (without high-degree gates)

Extensions to the Nova proof system that explore PCS in terms of linear codes, folding, and other concepts.

• Linear algebra and zero-knowledge (paper)
• Origami – A Folding Scheme for Halo2 Lookups
  • Folding Custom Gates with Verifier Input
• Folding for Arbitrary Polynomial Custom Gates and Lookups
• Folding endgame

HyperNova / ProtoStar : The next generation (with high-degree gates)

• 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.
• KiloNova: Non-Uniform PCD with Zero-Knowledge Property from Generic Folding Schemes This paper build a non-uniform ZK-PCD scheme (KiloNova) from the generic folding scheme and improve its performance with some optimization techniques, such as circuit aggregation and decoupling.
  • Presentation
• Proof-Carrying Data from Multi-folding Schemes This paper generalizes HyperNova to support folding multiple instances of CCS and multiple instance of LCCS into 1 LCCS, in contrast to the original work which folds 1 CCS and 1 LCCS into 1 LCCS.
• 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.
  • Presentation
• 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.
  • Presentation

Deep Space Nine (New commitment schemes, new lookup & proof arguments)

• LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems The first lattice-based folding scheme that leads to post-quantum secure IVC/PCD/SNARKs. Surprisingly, we estimate the performance to be competitive with top pre-quantum folding schemes.
  • Presentation
• Proofs for Deep Thought: Accumulation for large memories and deterministic computations We break through the "witness barrier" and go beyond the "lookup singularity". We show how to do reads AND writes to memory by committing to just 4 small elements. We also show how to avoid committing to intermediate witnesses.
• Mangrove: A Scalable Framework for Folding-based SNARKs We develop a new "uniformizing" compiler for NP statements that converts any poly-time computation to a sequence of identical simple steps
• Accumulation without Homomorphism We construct an accumulation scheme from non-homomorphic vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees).

Code (software repositories)

Reference implementations

• microsoft/nova
• lurk-lab/arecibo: This repository is a fork of the original. It's an incubator for experimenting with more advanced variants of the original software and working out the kinks in them

Teaching / experimental implementations

• nova-study: Implementation of Nova using arkworks-rs just forlearning purposes.
• supernova: Experimental implementation of the SuperNova protocol
• multifolding-poc: Experimental implementation of HyperNova
• microsoft/nova hypernova experimental PR: Experimental implementation of HyperNova in reference implementation
• ccs-hack: a hack implementation of CCS generic implementation
• protogalaxy-poc: Proof of concept implementation of ProtoGalaxy
• pse/nova experimental ParaNova PR: Experimental implementation of ParaNova
• pse/folding-schemes: Experimental arkworks library for accommodating different folding schemes
• snarkify/sirius: open-source constraint-system-agnostic folding framework for Incrementally Verifiable Computation
• PayneJoe/PNova: Our target is to implement a plonkish versioned NOVA, folding multiple Customer Gate/Lookup instances into one respectively.

Code Explorations

Code implementations and explorations related to the Nova proof system, including benchmarks, specifications, and experimental versions.

• Nova benchmarks
• Nova benchmarks (native SHA256)
• Nova wishlist and next steps
• Nova-based ZKVM spec
• Origami-benchmarks
• Notes on ProtoGalaxy
• Halo2 + Protostar

Other resources (podcasts, etc)

Podcast episodes

• 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

Talks & Lectures

• 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: SBC'23 Session 4: Efficient SNARKs From Folding Schemes
• Talk: ZKP MOOC Lecture 10: Recursive SNARKs
• Talk: ZK Summit 10: "Recent advances in folding schemes" (Liam Eager)
• Talk: ZK Summit 10: "Visual ProtoStar" (Adrian Hamelink)

Zuzalu talks

• 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)

Articles

• Article: Parallelizing Nova - Visualizations and Mental Models behind Paranova
• Article: Towards a Nova-based ZK-VM
• Article: Nova: from IVC to general PCD for zkMapReduce
• Article: An incomplete guide to Folding: Nova, Sangria, SuperNova, HyperNova, Protostar
• Article: Diagonal folding: Folding protocols with a large amount of rounds using 2-round Protostar

Forums

• Forum: Privacy Scaling Explorations Discord Server
• Forum: Lurk Lab Zulip Server

Applications

• 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
• Zator: Verified inference of a 512-layer neural network using recursive SNARKs
• Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs
  • A system for generating zero-knowledge proofs that a committed document matches or does not match a regular expression.
  • Github repo