Mangrove: A Scalable Framework for Folding-Based SNARKs

Mangrove: A Scalable Framework for Folding-Based SNARKs

发表信息

• 原文链接

作者

• Wilson Nguyen
• Trisha Datta
• Binyi Chen
• Nirvan Tyagi
• Dan Boneh

笔记

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 The full version of this work is available online at [43].).

我们提出了一个构建高效折叠基础SNARK（简洁非交互式知识论证）框架。首先，我们开发了一种新的“统一化”编译器，用于NP（非确定性多项式）语句，它将任何多项式时间计算转换为一系列相同的简单步骤。生成的统一计算特别适合通过折叠基础的IVC（交互式验证计算）方案进行处理。其次，我们对折叠基础的IVC进行了两项优化。第一项优化通过重组折叠应用的关系，减少了IVC的递归开销。第二项优化采用了“承诺与折叠”（commit-and-fold）策略，进一步简化了关系。综合来看，这些优化使得折叠基础的SNARK具有若干吸引人的特性。首先，该方案使用固定大小的透明公共参考字符串（CRS）。其次，证明者具有（i）低内存占用，（ii）仅对数据进行两次遍历，（iii）高度可并行化，以及（iv）具体效率高的优点。微基准测试表明，证明时间与领先的单体SNARK具有竞争力，并且显著快于其他流式SNARK。对于$2^{24}$（$2^{32}$）个门，Mangrove证明者在一台笔记本电脑上的估计时间为2分钟（8小时），峰值内存使用约为390 MB（800 MB）。