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.
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.