International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mangrove: A Scalable Framework for Folding-based SNARKs

Authors:
Wilson Nguyen , Stanford University
Trisha Datta , Stanford University
Binyi Chen , Stanford University
Nirvan Tyagi , Stanford University
Dan Boneh , Stanford University
Download:
DOI: 10.1007/978-3-031-68403-6_10 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: We present a framework for building efficient folding-based SNARKs. First we develop a new ``uniformizing'' compiler for NP statements that converts any poly-time computation to a sequence of identical simple steps. The resulting uniform computation is especially well-suited to be processed by a folding-based IVC scheme. Second, we develop two optimizations to folding-based IVC. The first reduces the recursive overhead of the IVC by restructuring the relation to which folding is applied. The second employs a ``commit-and-fold'' strategy to further simplify the relation. Together, these optimizations result in a folding-based SNARK that has a number of attractive features. First, the scheme uses a constant-size transparent common reference string (CRS). Second, the prover has (i) low memory footprint, (ii) makes only two passes over the data, (iii) is highly parallelizable, and (iv) is concretely efficient. Proving time is comparable to leading monolithic SNARKs, and is significantly faster than other streaming SNARKs. For example, for proving $2^{24}$ constraints, we estimate that a Mangrove prover takes about $64$ seconds, $10$ times faster than Spartan SNARK, while using less than 160MB of memory.
BibTeX
@inproceedings{crypto-2024-34389,
  title={Mangrove: A Scalable Framework for Folding-based SNARKs},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68403-6_10},
  author={Wilson Nguyen and Trisha Datta and Binyi Chen and Nirvan Tyagi and Dan Boneh},
  year=2024
}