Paper 2024/416

Mangrove: A Scalable Framework for Folding-based SNARKs

Wilson Nguyen, Stanford University
Trisha Datta, Stanford University
Binyi Chen, Stanford University
Nirvan Tyagi, Stanford University
Dan Boneh, Stanford University

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. Microbenchmarks indicate that proving time is competitive with leading monolithic SNARKs, and significantly faster than other streaming SNARKs. For $2^{24}$ ($2^{32}$) gates, the Mangrove prover is estimated to take $2$ minutes ($8$ hours) with peak memory usage approximately $390$ MB ($800$ MB) on a laptop.

Note: Full version of Crypto 2024 publication.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2024
Contact author(s)
wdnguyen @ cs stanford edu
tcdatta @ stanford edu
binyi @ cs stanford edu
tyagi @ stanford edu
dabo @ cs stanford edu
2024-05-30: last of 4 revisions
2024-03-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Wilson Nguyen and Trisha Datta and Binyi Chen and Nirvan Tyagi and Dan Boneh},
      title = {Mangrove: A Scalable Framework for Folding-based {SNARKs}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/416},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.