Lasso, Jolt, and the Lookup Singularity, Part I
SNARKs are a core primitive that permits applications to build on and update so-called layer-1 blockchains like Ethereum. In this presentation, Justin Thaler (a16z cyrpto) presents a fundamentally new approach to SNARK design, called Lasso and Jolt. Lasso that has a much faster prover than prior lookup arguments, a central primitive in modern SNARK design. Lookup arguments allow an untrusted prover to commit to a vector of values and prove that every entry of the vector resides in a predetermined table of values. A distinguishing feature of Lasso is that it applies even to tables that are far too large for anyone to materialize in full. Justin explains how this property offers a new approach to the design of SNARKs for CPU abstractions (also known as zkVMs). The basic idea is to turn each primitive instruction for the CPU into a single lookup into the evaluation table of the function (i.e., the gigantic table that stores the instruction’s output when run on every possible input to the instruction). He also describes a SNARK called Jolt, which instantiates this approach for the RISC-V instruction set.
This is joint work with Arasu Arun, Srinath Setty, Riad Wahby, Sam Ragsdale, and Michael Zhu.
About the speaker
Justin is Research Partner at a16z crypto and an Associate Professor in the Department of Computer Science at Georgetown University. His research interests include verifiable computing, complexity theory, and algorithms for massive data sets. In 2011, he produced the first implementation of a general-purpose interactive proof system. He is the author of a comprehensive survey on SNARKs, “Proofs, Arguments, and Zero-Knowledge,” and a co-creator of Apache DataSketches, an open-source library of production-quality streaming algorithms.Before joining a16z crypto and Georgetown, Justin was a Research Scientist at Yahoo Labs. Before that he completed her PhD in Computer Science at Harvard University.
About a16z crypto research
a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet. More about us: a16z.com/2022/04/21/announcing-a16z-crypto-research