Wilson Nguyen
March 13, 2024 at 11:00 AM on Zoom / Soda Hall
Mangrove: A Scalable Framework for Efficient SNARKs
Abstract: We present a framework for building efficient folding-based SNARKs by first developing a new “uniformizing” compiler for NP statements that converts any poly-time computation into a sequence of identical simple steps. This results in a uniform computation that is particularly well-suited for processing by a folding-based IVC scheme. We then introduce two optimizations to the folding-based IVC: the first reduces the recursive overhead by restructuring the relation to which folding is applied, and the second employs a “commit-and-fold” strategy to further simplify the relation. These optimizations yield a folding-based SNARK with several attractive features: a constant-size transparent common reference string (CRS), a prover with a low memory footprint that makes only two passes over the data, is highly parallelizable, and is concretely efficient. The proving time is comparable to leading monolithic SNARKs and significantly faster than other streaming SNARKs. For instance, on a laptop, proving 2^24 (2^32) constraints takes about 60s (4hr) while using less than 110 MB (220 MB) of memory. Furthermore, we provide a variety of tunable parameters to trade off between proving time and memory usage.
Bio: Wilson Nguyen is a CS PhD candidate (advised by Dan Boneh) in Applied Cryptography Group at Stanford.