Srinath Setty
March 29, 2023 at 11:00 AM on Zoom / Soda Hall
High-speed proof systems for general-purpose computation
Abstract:
Proof systems, such as zkSNARKs, are now widely used in decentralized systems to provide scalability and privacy. For example, in rollups, an untrusted entity processes a batch of blockchain transactions and produces a zkSNARK proving the correct execution of transactions, and the blockchain simply checks that the execution was correct by verifying the provided zkSNARK. Since verifying a zkSNARK is substantially cheaper than executing the original computation, rollups achieve lower per-transaction costs. Some major open problems in this space include achieving better prover efficiency and to scale the prover to handle large-scale statements.
This talk will present Nova (CRYPTO'22) and SuperNova (ePrint 2022/1758), and time permitting, some ongoing efforts in this line of work. Nova provides a new approach to build prover-efficient and recursive zkSNARKs, especially for proving large program executions that can be decomposed into multiple steps. In particular, Nova introduces a new and inexpensive mechanism, called a folding scheme, to (recursively) transform the task of proving N steps of a program execution into the task of proving a single step of the program execution. It then applies a general-purpose zkSNARK to prove that single step. Compared to directly employing a general-purpose zkSNARK, Nova’s approach is substantially cheaper. Furthermore, Nova's proof generation is incremental, so it offers a better path to parallelizing proof generation than with non-recursive zkSNARKs.
SuperNova extends Nova to produce proofs of program executions on a stateful machine with a particular instruction set (e.g., EVM, RISC-V). A distinguishing aspect of SuperNova is that the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step. This is a stark departure from prior works that employ universal circuits where the cost of proving a program step is proportional at least to the sum of sizes of circuits representing each supported instruction—even though a particular program step invokes only one of the supported instructions. Naturally, SuperNova can support a rich instruction set without affecting the per-step proving costs.
Bio: Srinath Setty is a Principal Researcher at Microsoft Research. His research interests are in systems, security, and cryptography. His recent work is focused on high-speed proof systems, rollback protection for confidential computing, and preventing order manipulation in distributed systems. His honors include paper awards at OSDI (2020) and USENIX Security (2017), MSR Redmond lab rockstar award (2018), and the Bert Kay best dissertation award from UT Austin (2014). He received his PhD in computer science from UT Austin.