Zero Knowledge Canon, part 1 & 2

Editor’s note: a16z crypto has had a long series of the “canons”, from our DAO Canon last year to our NFT Canon earlier (and before that our original Crypto Canon). So below, we’ve now culled a set of resources for those seeking to understand, go deeper, and build with all things zero knowledge: powerful, foundational technologies that hold the keys to blockchain scalability, and which represent the future of privacy-preserving applications — including applications in crypto/web3 — and countless other innovations to come. 

And these innovations have been a long time coming: Zero-knowledge proof systems were introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985, and had a transformative effect on the field of cryptography; they were recognized by the ACM Turing Award awarded to Goldwasser and Micali in in 2012. Since this work has been decades in the making, especially in moving from theory to practice — we also share, for the first time in our canons series, a part two: a reading list annotated by Justin Thaler, organized by topic and chronology — following part one below…

Be sure to sign up for our web3 weekly newsletter for more updates as well as other curated resources. If you have suggestions for other high-quality pieces to add, let us know @a16zcrypto and/or @smc90.

[Acknowledgements: Thanks also to Michael Blau, Sam Ragsdale, and Tim Roughgarden. (As well as to Pratyush Mishra, Ittai Abraham, and others for their further suggestions via Twitter, which we’ve added below!)]

Some of these papers are also more about cryptography generally (not all zero knowledge per se), including outlining problems or key advances that are addressed by zero knowledge proofs today: how to ensure privacy and authentication in open networks.

New directions in cryptography (1976)
by Whitfield Diffie and Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

A method for obtaining digital signatures and public-key cryptosystems
by Ronald Rivest, Adi Shamir, Leonard Adelman
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

Protocols for public key cryptosystems (1980)
by Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Secure communications over insecure channels (1978)
by Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Use of elliptic curves in cryptography (1988)
by Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

The knowledge complexity of interactive proof-systems (1985)
by Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Computationally sound proofs (2000)
by Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

From extractable collision resistance to succinct non-interactive arguments of knowledge [SNARKs], and back again (2011)
by Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Efficient zero-knowledge argument for correctness of a shuffle (2012)
by Stephanie Bayer and Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Succinct non-interactive zero knowledge for a von Neumann Architecture (2013)
by Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza
https://eprint.iacr.org/2013/879.pdf

Verifying computations without re-executing them (2015)
by Michael Walfish and Andrew Blumberg
https://cacm.acm.org/magazines/2015/2/182636-verifying-computations-without-reexecuting-them/

Scalable, transparent, and post-quantum secure computational integrity (2018)
by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Public-coin zero-knowledge arguments with (almost) minimal time and space overheads (2020)
by Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum, and Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Proofs, arguments, and zero-knowledge

— An overview of verifiable computing and interactive proofs and arguments, cryptographic protocols that enable a prover to provide a guarantee to a verifier that the prover performed a requested computation correctly, including zero-knowledge (where proofs reveal no information other than their own validity). Zk arguments have a myriad of applications in cryptography and have made the jump from theory to practice over the past decade.
by Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

An evolution of models for zero-knowledge proofs — A review of zero-knowledge proofs, where Meiklejohn (University College London, Google) looks at the applications that are driving their development, the different models that have emerged to capture these new interactions, the constructions that we can achieve, and the work left to do.
by Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

ZK whiteboard sessions — introductory modules
with Dan Boneh et al
https://zkhack.dev/whiteboard/

Security and privacy for crypto with zkps — pioneering the zero-knowledge proof in practice; what zkps are and how they work… including live stage “demo”
by Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Top tech topics, explained — including definitions and implications of zero knowledge in general
by Joe Bonneau, Tim Roughgarden, Scott Kominers, Ali Yahya, Chris Dixon
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

Zero knowledge, explained — at 5 levels of difficulty
with Amit Sahai, Wired
https://youtu.be/fOGdb1CTu5c

How the coming privacy layer will fix a broken web
by Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Using ZK proofs to fight disinformation
by Trish Datta and Dan Boneh
https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f

Introduction to zkSNARKs
with Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Why and how zk-SNARK Works: a definitive explanation
by Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

An introduction to zero-knowledge proofs
by Fredrik Harrysson and Anna Rose
https://www.zeroknowledge.fm/21 [+ summary writeup elsewhere here]

Zk-SNARKs: under the hood
by Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
part 1, part 2, part 3

Decentralized speed — on advances in zero knowledge proofs, decentralized hardware
by Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Cutting edge zk research — with zk researcher at Ethereum Foundation
with Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Exploring zk research — with director of research at DFINITY; also behind advances like Groth16
with Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK research & pedagogy — with one of the co-founders of ZCash and Starkware
with Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Interactive proofs

— chapter 8 from Computational Complexity: A Modern Approach
by Sanjeev Arora and Boaz Barak
https://theory.cs.princeton.edu/complexity/book.pdf

Foundations of probabilistic proofs — a course with 5 units from interactive proofs and more
by Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

9th BIU Winter School on Cryptography — from the Center for Research in Applied Cryptography & Cyber Security
by Yehuda Lindell, Benny Pinkas with Eli Ben-Sasson, Jens Groth, Carmit Hazay, Yuval Ishai, Alon Rosen, Ron Rothblum
https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/

Interactive proofs and zero knowledge — from Stanford CSS 355 Topics in Cryptography (2018)
by Henry Corrigan-Gibbs, Sam Kim, David Wu
https://crypto.stanford.edu/cs355/18sp/lec3.pdf

Interactive demonstration of the zero knowledge proof protocol for 3-colorable graphs — permits one to convince a verifier of the truth of a fact (namely, that a graph is three colorable), without revealing the actual three coloring of the graph
http://web.mit.edu/~ezyang/Public/graph/svg.html [see also for more]

A simple and succinct zero knowledge proof — presents a simple proof system that can provide an introduction and intuition to this space
by Ittai Abraham and Alin Tomescu
https://decentralizedthoughts.github.io/2020-12-08-a-simple-and-succinct-zero-knowledge-proof/

SNARK (PLONK) compiler, prover, and verifier in Python — intended for educational value
by Vitalik Buterin
https://github.com/ethereum/research/tree/master/py_plonk

SNARK design, part 1 — survey, use in rollups, more
by Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, part 2 — rollups, performance, security
by Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

STARKs — part I, II, III
by Vitalik Buterin
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html

Anatomy of a STARK — a six-part tutorial explaining the mechanics of a STARK proof system
by Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Measuring SNARK performance — frontends, backends, more
by Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Understanding PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

The PLONK zero-knowledge proof system — series of 12 short videos on how PLONK works
by David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

From AIRs to RAPs — how PLONK-style arithmetization works
by Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset checks in PLONK and Plookup
by Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 design — from ECC
https://zcash.github.io/halo2/design.html

Plonky2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Applied zk

— learning resources, adding materials for bringing engineers without a formal mathematics background up to speed to a solid understanding of the underlying theory
by 0xPARC
https://learn.0xparc.org/materials/intro

An online development environment for zkSNARKs — zkREPL, a new set of tools for interacting with the Circom toolstack in-browser
by Kevin Kwok
https://zkrepl.dev (+ explainer thread here)

Quadratic arithmetic programs from zero to hero
by Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

On zkEVMs
with Alex Gluchowski and Anna Rose
https://zeroknowledge.fm/175-2/

Different types of zkEVMs
by Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

ZK machine learning — tutorial & demo for putting a neural net into a SNARK
by Horace Pan, Francis Ho, and Henri Palacci
https://0xparc.org/blog/zk-mnist

On ZK languages
with Alex Ozdemir and Anna Rose
https://zeroknowledge.fm/172-2/

Arkworks — Rust ecosystem for developing and programming with zkSNARKs
https://github.com/arkworks-rs

Dark Forest — applying zk cryptography to games — a fully decentralized and persistent RTS (real-time strategy) game
https://blog.zkga.me/announcing-darkforest

ZKPs for engineers — a look at the Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

A dive into zero knowledge
with Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Zero-knowledge information sharing
by Sam Ragsdale and Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Using ZK proofs to fight disinformation
by Trish Datta and Dan Boneh
https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f

Privacy-protecting crypto airdrops with zero knowledge proofs
by Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

ZK Hack — puzzles, more
https://zkhack.dev/events/mini.html#puzzles

On-chain trusted setup ceremonies —
by Valeria Nikolaenko and Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Crypto regulations, illicit finance, privacy, and beyond – includes section on zero knowledge in regulatory/ compliance contexts; difference between “privacy-preserving” vs obfuscating technologies
with Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

zkMesh newsletter

— a monthly newsletter sharing the latest in decentralized privacy-preserving technologies, privacy protocol development, and zero knowledge systems
https://zkmesh.substack.com/

Zero Knowledge podcast — on the latest zk research & zk applications and experts building cryptography-enabled privacy tech
with Anna Rose
https://zeroknowledge.fm/

ZK Jobs Board
https://jobsboard.zeroknowledge.fm/

…an annotated reading list, by topic and chronology, by Justin Thaler:

SNARKs from Linear PCPs (a.k.a. SNARKs with circuit-specific setup)

Efficient Arguments without Short PCPs (2007)

by Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky

Prior to about 2007, SNARKs were primarily designed via the Kilian–Micali paradigm, of taking a “short” probabilistically checkable proof (PCP) and “cryptographically compiling” it into a succinct argument via Merkle hashing and the Fiat-Shamir transformation. Unfortunately, short PCPs are complicated and impractical, even today. This paper (IKO) showed how to use homomorphic encryption to obtain succinct (non-transparent) interactive arguments from “long but structured” PCPs. These can be much simpler than short PCPs, and the resulting SNARKs have much shorter proofs and faster verification. These arguments were first recognized as having the potential for practical efficiency, and refined and implemented, in Pepper. Unfortunately, IKO’s arguments have a quadratic-time prover and quadratic-size structured reference string, so they do not scale to large computations.

Quadratic Span Programs and Succinct NIZKs without PCPs (2012)
by Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova

This breakthrough paper (GGPR) reduced the prover costs of IKO’s approach from quadratic in the size of the circuit to quasilinear. Building on earlier work of Groth and Lipmaa, it also gave SNARKs via pairing-based cryptography, rather than interactive arguments as in IKO. It described its SNARKs in the context of what is now referred to as rank-1 constraint satisfaction (R1CS) problems, a generalization of arithmetic circuit-satisfiability.

This paper also served as the theoretical foundation of the first SNARKs to see commercial deployment (e.g., in ZCash) and directly led to SNARKs that remain popular today (e.g., Groth16). Initial implementations of GGPR’s arguments came in Zaatar and Pinocchio, and later variants include SNARKs for C and BCTV. BCIOP gave a general framework that elucidates these linear-PCPs-to-SNARK transformations (see also Appendix A of Zaatar) and describes various instantiations thereof.

On the Size of Pairing-based Non-interactive Arguments (2016)
by Jens Groth

This paper, colloquially referred to as Groth16, presented a refinement of GGPR’s SNARKs that achieves state-of-the-art concrete verification costs even today (proofs are 3 group elements, and verification is dominated by three pairing operations, at least assuming the public input is short). Security is proved in the generic group model.

SNARKs with universal trusted setup

PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019)

by Ariel Gabizon, Zachary Williamson, and Oana Ciobotaru

Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS (2019)
by Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas Ward

Both PlonK and Marlin replace the circuit-specific trusted setup in Groth16 with a universal setup. This comes at the expense of 4x-6x larger proofs. One can think of PlonK and Marlin as taking the circuit-specific work during the trusted setup in Groth16 and predecessors and moving it into a pre-processing phase that happens after the trusted setup, as well as during SNARK proof-generation.

The ability to process arbitrary circuits and R1CS systems in this manner is sometimes called holography or computation commitments, and was also described in Spartan (discussed later in this compilation). Because more work happens during proof generation, PlonK and Marlin’s provers are slower than Groth16 for a given circuit or R1CS instance. However, unlike Groth16, PlonK and Marlin can be made to work with more general intermediate representations than R1CS.

Polynomial commitment schemes, a key cryptographic primitive in SNARKs

Constant-Size Commitments to Polynomials and Their Applications (2010)

by Aniket Kate, Gregory Zaverucha, and Ian Goldberg

This paper introduced the notion of polynomial commitment schemes. It gave a scheme for univariate polynomials (commonly called KZG commitments) with constant-size commitments and evaluation proofs. The scheme uses a trusted setup (i.e., structured reference string) and pairing-based cryptography. It remains extremely popular in practice today, and is used in SNARKs including PlonK and Marlin discussed above (and Groth16 uses extremely similar cryptographic techniques).

Fast Reed-Solomon Interactive Oracle Proofs of Proximity (2017)
by Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Gives an interactive oracle proof (IOP) for Reed-Solomon testing — that is, proving that a committed string is close to the evaluation table of a univariate polynomial. Combined with Merkle-hashing and the Fiat-Shamir transformation, this yields a transparent polynomial commitment scheme with polylogarithmic-sized evaluation proofs (see VP19 for details). Today, this remains the shortest amongst plausibly post-quantum polynomial commitment schemes.

Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017)
by Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam

Similar to FRI, this work gives an IOP for Reed-Solomon testing, but with square root proof length rather than polylogarithmic. Theoretical works showed that, by swapping out the Reed-Solomon code for a different error-correcting code with faster encoding, one can obtain a linear-time prover that moreover works natively over any field. This approach has been refined and implemented in Brakedown and Orion, yielding state-of-the-art prover performance.

Bulletproofs: Short Proofs for Confidential Transactions and More (2017)
by Benedikt Bunz, Jonathan Bootle, Dan Boneh , Andrew Poelstra, Pieter Wuille, and Greg Maxwell

Refining prior work by BCCGP, Bulletproofs gives a transparent polynomial commitment scheme (in fact, a generalization called an inner product argument) based on the hardness of computing discrete logarithms with logarithmic proof size but linear verifier time. The scheme remains popular today due to its transparency and short proofs (e.g., it is used in ZCash Orchard and Monero).

Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments (2020)
by Jonathan Lee

Dory reduces the verifier time in Bulletproofs from linear to logarithmic, while preserving transparency and logarithmic-size proofs (albeit concretely larger than Bulletproofs) and transparency. Uses pairings and is based on the SXDH assumption.

Interactive Proofs, multi-prover interactive Proofs, and associated SNARKs

Delegating Computation: Interactive Proofs for Muggles (2008)

by Shafi Goldwasser, Yael Tauman Kalai, and Guy Rothblum

Prior to this paper, general-purpose interactive proofs required a superpolynomial-time prover. This paper gives an interactive proof protocol, commonly called the GKR protocol, with a polynomial time prover and quasilinear time verifier, for any problem possessing an efficient parallel algorithm (equivalently, the interactive proof applies to any arithmetic circuit with small depth).

Practical verified computation with streaming interactive proofs (2011)
by Graham Cormode, Michael Mitzenmacher, Justin Thaler

This paper (sometimes called CMT) reduced the prover time in the GKR protocol from quartic in the size of the circuit to quasilinear. Produced the first implementation of a general-purpose interactive proof. A line of subsequent works (Allspice, Thaler13, Giraffe, and Libra) reduced the runtime of the prover further, from quasilinear to linear in the size of the circuit.

vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases (2017)
by Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, and Charalampos Papamanthou

Although the title refers to a specific application area (databases), the contributions of this paper are more general. Specifically, it observed that one can obtain succinct arguments for circuit-sastisfiability by combining interactive proofs with polynomial commitment schemes (for multilinear polynomials).

Later works rendered the arguments zero-knowledge and introduced different commitment schemes for multilinear polynomials.

Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2019)
by Srinath Setty

Obtains SNARKs for circuit-satisfiability and R1CS by combining multi-prover interactive proofs (MIPs) with polynomial commitment schemes, building on earlier work on concretely-efficient MIPs called Clover. The effect is to obtain SNARKs with shorter proofs than those derived from interactive proofs such as the GKR protocol discussed above. Analogous to PlonK and Marlin, Spartan also shows how to process arbitrary circuits and R1CS systems via pre-processing and SNARK proof-generation.

Spartan used a polynomial commitment scheme from Hyrax. Subsequent works called Brakedown and Orion combine Spartan’s MIP with other polynomial commitment schemes to yield the first implemented SNARKs with a linear-time prover.

Short PCPs with Polylog Query Complexity (2005)

by Eli Ben-Sasson and Madhu Sudan

 This theoretical work gave the first probabilistically checkable proof (PCP) with proof length quasilinear in the size of the computation to be verified and polylogarithmic query cost (though linear verifier time). Following the Kilian-Micali transformation of PCPs into SNARKs, this was a step toward SNARKs with quasi-linear time prover and polylogarithmic-time verifier.

Later theoretical work reduced the verifier time to polylogarithmic. Subsequent practically-focused work refined this approach, but short PCPs remain impractical today. To obtain practical SNARKs, later works turned to an interactive generalization of PCPs called interactive oracle proofs (IOPs). These efforts led to and build on FRI, a popular polynomial commitment scheme discussed in the polynomial commitments section of this compilation.

Other works in this category include ZKBoo and its descendants. These do not achieve succinct proofs, but they have good constant factors and hence are attractive for proving small statements. They have led to families of post-quantum signatures such as Picnic that have been optimized in several works. ZKBoo is presented as following a distinct design paradigm called MPC-in-the-head, but it yields an IOP.

Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008)

by Paul Valiant

This work introduced the fundamental notion of incrementally verifiable computation (IVC), in which are prover runs a computation and maintains at all times a proof that the computation so far has been correct. It constructed IVC via recursive composition of SNARKs. Here, the knowledge-soundness property of SNARKs is essential to establishing soundness of recursively-composed non-interactive arguments. This paper also gave an extremely efficient knowledge-extractor for PCP-derived SNARKs (as per the Kilian-Micali paradigm).

Scalable Zero Knowledge via Cycles of Elliptic Curves (2014)
by Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza

Following theoretical work, this paper used recursive application of a variant of GGPR’s SNARK, to provide the first implementation of IVC for a simple virtual machine (TinyRAM, from the SNARKs for C paper).

Also introduced the notion of cycles of elliptic curves, which are useful for recursively composing SNARKs that make use of elliptic curve cryptography.

Recursive Proof Composition without a Trusted Setup (2019)
by Sean Bowe, Jack Grigg, and Daira Hopwood

This work (called Halo) studies how to recursively compose transparent SNARKs. This is more challenging than composing non-transparent ones because the verification procedure in transparent SNARKs can be much more expensive.

This then sparked a line of work that has culminated in systems such as Nova achieving state-of-the-art IVC performance, superior even to that obtained by composition of non-transparent SNARKs such as Groth16.

Zerocash: Decentralized Anonymous Payments from Bitcoin (2014)

by Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Building on prior work including Zerocoin (and with Pinnochio Coin as concurrent work), this paper uses GGPR-derived SNARKs to design a private cryptocurrency. Led to ZCash.

Geppetto: Versatile Verifiable Computation (2014)
by Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur

Geppetto arguably pre-dates the explosion of interest in private smart-contract execution, having been written roughly one year after the creation of Ethereum. Hence, it is not presented in the context of private smart-contract execution. However, it uses bounded-depth recursion of SNARKs to allow an untrusted prover to execute any private (committed/signed) computer program on private data, without revealing information about the program being run or the data it is run on. Accordingly, it is a predecessor of work on private smart-contract platforms, such as Zexe [described below].

Verifiable ASICs (2015)
by Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

This paper considers the problem of how to safely and fruitfully use an ASIC manufactured in an untrusted foundry (in 2015, there were only five nations with top-end foundries). The approach is to have the fast but untrusted ASIC prove the correctness of its output to a verifier that runs on a slower-but-trusted ASIC. The solution is interesting so long as the total execution time of the system (i.e., the sum of the prover and verifier runtimes plus any data transmission costs) is less than the naive baseline: the time required to run the computation in full on the slower-but-trusted ASIC. Using a variant the GKR/CMT/Allspice interactive proofs, the paper indeed beats the naive baseline for a number of fundamental problems, including number-theoretic transforms, pattern matching, and elliptic curve operations. This work suggests that some proof systems are more suited for hardware implementation than others. Optimizing proof systems for hardware implementation is now receiving considerable attention, but much remains to be explored.

Verifiable Delay Functions (2018)
by Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch

Introduced the notation of verifiable delay functions (VDFs), a cryptographic primitive that is widely useful in blockchain applications, e.g., in mitigating possible manipulation of proof-of-stake consensus protocols. SNARKs (especially for Incrementally Verifiable Computation) offer a route to state-of-the-art VDFs.

Zexe: Enabling Decentralized Private Computation (2018)
by Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, and Howard Wu

Zexe is a design for a private smart-contract platform. One can view Zexe as an extension of Zerocash (described above). Zerocash enables a single application to be run on-chain (enabling users to transfer tokens) while protecting the privacy of user data, e.g., who they are sending tokens to, receiving tokens from, the amount of tokens transferred, etc. Zexe allows many different applications (smart contracts) to run on the same blockchain and interact with each other. Transactions are executed off-chain, and proofs of correct execution are posted on-chain. Not only is data privacy protected, so is function privacy. This means the proof associated with each transaction does not even reveal which application(s) the transaction pertains to. A more general engineering contribution of Zexe is that it introduced BLS12-377, an elliptic curve group that is useful for efficient depth-1 composition of pairing-based SNARKs.

Replicated state machines without replicated execution (2020)
by Jonathan Lee, Kirill Nikitin, and Srinath Setty

This is one of the few academic papers on rollups for blockchain scalability. It does not use the term rollups, because it pre-dates or is contemporaneous with the concept being introduced outside of the academic literature.

Front-ends (efficient transformations from computer programs to intermediate representations such as circuit-satisfiablity, R1CS, and more)

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems (2012)

by Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer

From a modern perspective, this is an early work on practical computer-program-to-circuit-SAT transformations for a virtual machine (VM) abstraction. Building on works from the late-1970s through 1990s (e.g., work of Robson) this paper spells out a deterministic reduction from executing a VM for T steps to the satisfiability of a circuit of size O(T*polylog(T)).

Subsequent papers, e.g., SNARKs for C and BCTV, continued to develop front-ends via a VM abstraction, and modern instantiations include projects such as Cairo, RISC Zero, and Polygon Miden.

Taking proof-based verified computation a few steps closer to practicality (2012)
by Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew Blumberg, and Michael Walfish

This paper, referred to as Ginger, is another early contribution to practical front-end techniques. Ginger introduced gadgets for general programming primitives like conditionals and logical expressions, comparisons and bitwise arithmetic via bit splitting, primitive floating point arithmetic, etc. It used these gadgets to provide the first implemented front-end from a high-level language to low-degree arithmetic constraints (similar to what is now known as R1CS), an intermediate representation (IR) to which a SNARK back-end can be applied.

Whereas the “Fast Reductions” paper and its descendants use a “CPU-emulator” approach in producing IRs (i.e., the IR enforces that the prover correctly ran a particular program by applying the transition function of the CPU for a specified number of steps), Ginger and its descendents take a more ASIC-like approach, producing IRs that are tailored to the computer program that the prover is claiming to correctly execute.

For example, Buffet shows that it’s possible to handle complex control flow in the ASIC model, by turning such control flow into a finite-state machine tailored to the program being executed, and that this approach can be significantly more efficient than building a general-purpose CPU emulator. xJsnark gives an efficient construction for multi-precision arithmetic, optimizations for RAMs and ROMs, and exposes a Java-like high-level language to a programmer, which remains popular today. CirC observes that compiling computer programs to R1CS is closely related to well known techniques from program analysis and builds a compiler construction toolkit incorporating ideas from both communities (“LLVM for circuit-like representations”). Earlier works making contributions to ASIC-style front-ends include Pinocchio and Geppetto.

The “Fast-Reductions” paper used a complicated and expensive construction called “routing networks” for so-called memory-checking (i.e., ensuring that the untrusted prover is correctly maintaining the VM’s random access memory throughout the execution of the VM whose correctness is being proved). This choice was made because early works such as this one were seeking to obtain a PCP, which required the front-end to be both non-interactive and information-theoretically secure. Later work called Pantry (a predecessor of the Buffet work mentioned above) used Merkle-trees in place of routing networks, achieving efficiency by compiling an algebraic (i.e., “SNARK-friendly”) hash function, due to Ajtai, into constraints. This resulted in “computationally secure” front-ends. Today, there is a large research literature on SNARK-friendly hash functions, with examples including Poseidon, MiMC, Reinforced Concrete, Rescue, and more.

State-of-the-art techniques for ensuring that the prover is maintaining RAM correctly rely on so-called “permutation-invariant fingerprinting” methods dating back at least to Lipton (1989) and used for memory-checking by Blum et al (1991). These techniques inherently involve interaction between a prover and verifier, but can be rendered non-interactive with the Fiat-Shamir transformation.  As far as we are aware, they were introduced to the literature on practical SNARK front-ends by a system called vRAM.

Permutation-invariant fingerprinting techniques are now used in many front-ends and SNARKs for virtual machine abstractions, including for example Cairo. Closely related ideas reappeared in related contexts in the two works below, which are used widely in practice today.

Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution (2018)
by Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen, and Mary Maller

Plookup: A simplified polynomial protocol for lookup tables (2020)
by Ariel Gabizon and Zachary Williamson

Early works on front-ends represented “non-arithmetic” operations (such as range checks, bitwise operations, and integer comparisons) inside circuits and related IRs by breaking field elements into bits, performing the operations on these bits, and then “packing” the result back into a single field element. In terms of the size of the resulting circuit, this results in a logarithmic overhead per operation.

The above two works (BCGJM and Plookup) give influential techniques (based on so-called “lookup tables”) for more efficiently representing these operations inside circuits, in an amortized sense. Roughly speaking, for some parameter B chosen by the front-end designer, these reduce the number of gates required to represent each non-arithmetic operation in the circuit by a factor logarithmic in B, at the cost of the prover cryptographically committing to an extra “advice” vector of length roughly B.