原文标题：《重大突破：路印协议将交易成本再降 15 倍！》（Loopring’s zkSNARK Prover Optimizations） 本文详细说明了路印协议在 zkSNARK 证明生成上的一些优化措施，我们成功地将生成零知识证明的成本降低为每笔交易仅 0.03 分 RMB （100 万笔交易成本大约 300RMB），与目前我们线上的版本相比，成本降低了 15 倍。再加上其他一些优化手段，最终路印协议每笔撮合交易总成本仅仅只需 0.09 分 RMB （100 万笔交易成本大约 900RMB）。 原文由路印协议首席架构师 Brecht Devos 发表在官方博客 1 上，本文由路印协议 CTO 郭雄辉翻译。 约 2 个多月前，我们分享了路印协议在 WeDEX Beta 版本上实际运营的成本数据 2 ，那个时候链上 GAS 费用和链下计算成本都还相对较高。降低链上 GAS 费用有一个很显然的方法，那就是通过聚合更多笔交易并且采用聚合验证的方式，就可以轻松把链上成本降低 10 倍（初始版本最多只聚合了 128 笔交易，最新版本我们能聚合最高 1024 笔交易），但是越大笔数的聚合交易通常意味着零知识证明生成成本也变得更高。如何降低链下计算成本，尤其是降低零知识证明生成成本，就变得对运营基于路印协议的去中心化交易所3 至关重要。 目前路印协议是在 ethsnarks 4 和 libsnark 5 的基础库上开发遵循 Groth16 零知识证明协议电路代码，而 libsnark 相比于另外一个常用零知识证明库 bellman 6 来说效率有点不够高，我们也考虑过是不是要切换到 bellman 基础库，但考虑到我们的电路用 libsnark 就能很好的描述，同时我们递交到链上的数据中只包含了必须要用到的一些状态变量，而没有包含证明中一些其他变量，比如门限制计算的中间值。另外，bellman 库本身也还有进一步的优化空间，我们也没理由相信 libsnark(C++代码) 就一定会比 bellman(Rust 代码) 慢。 生成零知识证明需要超大量的内存，大约每 100 万个门限制电路就要 5GB 内存。对我们路印协议来说，最大 1024 笔撮合交易的电路就会需要 6400 万个门限制，这意味着需要一个超级强劲超大内存的服务器才能生成出证明。 如果不做优化的话，基本就意味着不太可能实际使用，因此我们决定去优化 libsnark 库。我们尝试了很多种优化方法，有大有小，最终取得的成果还是挺不错的。因此我们很高兴的在这分享给大家，希望能对大家有些帮助。话不多说，我们先来看最终效果！ 优化结果 我们现在只用少于 1GB 的内存，就可以同时处理 100 万个门限制电路，而且能达到一个 CPU 核每秒为 4 万个门限制电路生成证明的效果。一笔基于 ZK Rollup 的转账大约需要 3 万个门限制，一笔基于路印协议的交易需要约 6 万个门限制，因此，一个 16 核的 CPU 每秒就能处理 20 笔转账或者 10 笔交易。 比如，现在只要用 55GB 的内存，16 核的 CPU 就可以在 104 秒内生成一个有 6400 万个门限制电路的证明 (路印协议所设计的最大容纳 1024 笔交易的电路)。也就是，只需要消费者级别的电脑，就可以每秒为 635,000 个门限制电路生成证明，而 1 台 16 核 CPU 加 64GB 内存的电脑也就大约 7000RMB。这也就意味着购买一些普通机器来生成电路证明具有可行性，这种方式非常适用于我们路印去中心化交易所，应该也能适用于任何基于零知识证明的去中心化解决方案。 当然，使用云计算也是另外一种可选项。在 AWS 上我们就可以用每小时 10.5RMB 的价格租一台 c5.9xlarge 型号专门适用于计算的云机器 (18 核 CPU 和 72GB 内存)，同时我们发现租用 m5 型号云机器也能达到同样的性能表现。这台 c5.9xlarge 云机器就可以每小时为 35,000 笔交易生成零知识证明，换算下来也就是 1 笔交易仅花费 0.03 分 RMB(100 万笔交易也就 300RMB)。正如路印协议的设计文档7所解释的，每笔交易的链上成本最低可以到 375 个 GAS，如果以以太坊 1500RMB 的价格计算，同时采用 1Gwei 的 GAS 价格，那么链上每笔交易成本仅仅为 0.06 分 RMB(100 万笔交易也就 600RMB)。链上和链下两项成本加起来也就才 0.09 分 RMB(100 万笔交易也就 900RMB)。
就像下图所揭示的，生成证明的性能先是随着 CPU 核数线性增长，但超过 16 核之后性能提升就不明显了 (我们后续还会进一步研究为什么超过 16 核就不起作用了)。
以上数据是在 c5.9xlarge 云机器上调整 CPU 的核数而采样得到的，16 核下性能数据稍微有点出入，是因为测试时没有打开 CPU 的超线程功能。 同样地，在处理门限制电路的性能上也呈现出线性增长，这个有一点点奇怪，因为理论上快速傅立叶变换 FFT 算法复杂度是 O(n*log(n))，但实际采样是线性增长的。下面的数据是在 c5.9xlarge 云机器上采用 16 核但禁止了 CPU 超线程功能而测得的。
指数运算乘积 (multiexp) 计算占了生成证明中 75% 的工作量，下面的饼图显示了具有 6400 万门限制的电路计算中的工作量占比，更小一点的电路也基本具有同样的占比。
我们没有继续拿未改动过的 libsnark 和 bellman 做对比实验。未改动过的 libsnark 有挺多问题的，和其比对没有意义，但粗略地计算，我们的优化在 16 核 CPU 的机器上能达到 15 倍性能的提升。同时根据一些项目的公开数据表明，和 bellman 相比，也有 4 倍性能的提升。在内存消耗上，我们的方案仅仅只是原来的 1/5。 举个更有趣也更实际一点的例子，我们来算算如果要在以太坊网络上达到 VISA 同等级别的性能指标 (2000 TPS) 的话，会需要多少成本。一笔转账在链上大约消耗 200 个 GAS，根据以上的数据就可以计算得到我们只需要 100 台 16 核 CPU 的机器，以及使用 50% 左右的以太坊总容量。如果是租用 AWS 机器的话，使用成本大约是每笔转账 0.042 分 RMB(100 万笔转账 420RMB)。但如果采用一次性购买全部机器的话，总成本是 70 万 RMB，如果不计算其他运营成本比如电费的话，使用独立机器的成本大约是每笔转账 0.028 分 RMB(100 万笔转账 280RMB)。 优化细节 基本上生成零知识证明是在执行两种操作：快速傅立叶变换 (FFT) 和指数运算乘积。之前大部分项目的优化重心也都是放在优化这两种操作上，但是减小内存占用也非常重要 (尤其对那些拥有很多门限制的电路来说)。当然，除了优化内存分配，减少不必要的计算也都是需要的。 FFT
FFT 算法可能是已被研究的最多的一个算法，因此我们可以利用很多现有的知识去得到一个比较好的实现版本，我们也正是这么去做的。我们提供了一种新的 FFT 算法的实现版本，它的实现方式和著名的快速 FFT 库比较接近。尽管这个版本可能还不是那么完美，肯定也还有进一步的优化空间，但是它已经比 libsnark 里面的实现 (和 libsnark 类似的 bellman 里面的实现) 要更高效些。 零知识证明中 FFT 算法是作用在域元素上的，每个元素都占用 32 个字节，这比常规的 FFT 算法中的浮点数或者整数大多了，因此在其上的操作也都更慢。最开始我们都不太确定常规的快速 FFT 算法是否能直接应用，但幸运的是，它还是能用的上。 FFT 算法本质上是一个递归算法，因此我们的实现采用深度优先的递归算法。之所以选用深度优先，是因为这种方式能最大程度的利用好 CPU 的缓存机制，从而达到性能最优的效果。 FFT 中的旋转因子只需要事先计算一次然后就能被重复使用。两个域元素的乘法是很耗时的操作，如果可能的话就应该尽量重复使用旋转因子。而要把旋转因子放到内存或者缓存中去又会进一步加大内存消耗，因此我们需要把 FFT 算法划分成不同的阶段，而每个阶段都要尽量保证能在连续的内存中访问使用到的旋转因子，这样的内存排布就很适合 CPU 缓存预取。 针对目前的划分阶段，我们支持 2 分法或者 4 分法。通常来说，越大的分法越好，但是在特定场景下，4 分法需要比 2 分法多一次额外的域乘法操作。因此 4 分法在大部分场景下是更高效些，但不是所有情况都更好，需要在递归次数和域乘法之间取得一个平衡。我们也很期待在更大的分法下会是什么情况，但到了 8 分法，事情就已经变得很复杂了。 我们会把树根据 CPU 核数目拆分成相对应的多棵子树，这样每一个 CPU 核就只需要采用深度优先去处理一棵子树。每个阶段上我们都会把最顶层的树按这种方式去水平切割。 指数运算乘积 libsnark 和 bellman 库虽然具体的实现方式不太一样，但都是用了 Pippenger 算法来实现指数运算乘积。 这个算法最基本的一个操作是椭圆曲线加法，因此能快速实现椭圆曲线加法就特别重要，这个是我们所做的最重要也最直观的第一个优化。我们切换到使用 MCL 库9 来实现椭圆曲线加法，从而极大地提升性能 (这一点上我们要感谢安比实验室，是他们的早期工作让我们想到这个优化点)。 接下来的一个优化是参考 bellman 的代码在 libsnark 上采用相对应的实现，通常就是改变下访问数据的方式。但这个改动也带来一些有意思的结果。我们将指数 (一个 254 位的域元素) 分成 c 份，然后用多线程去处理，这样一个线程只需要处理其中的一份。具体拆分成多少份是会直接影响算法效率，同时也会影响到在多核机器上的性能表现。在我们的测试中发现取 c=16 是最佳的，这个发现也决定了我们最多只需采用 16 核的 CPU。它是恰到好处的一个值，乘以 16 大于 254 的数中最小的一个数正好也是 16(c*16=256>254)。后面更进一步的优化可以是，在每一份内部再划分成更小的片，从而能利用更多的核，而不用再去调整 c 的值。但很难预测调整 c 值和拆分成更小的片，哪种方式能更优。 另外一个 bellman 实现中比较好的点在于：预先读取特定的一些数据，而这些数据 CPU 是无法提前预取到缓存中的，因为这个模式完全依赖于数据自身。这个预取动作非常重要，而预取到 CPU 要用的正确数据也很重要。预取多少数据也是要根据 CPU 去调整的，这个值可以通过在实际硬件上反复测试得到一个最佳经验值。因此这个值要做成一个可配置项，从而能在不同系统上达到最佳性能表现。另外一个小的优化点是去配置预取的缓存逻辑 (配置为 1 就表现不错) 和预取更多的数据 (两次循环迭代似乎效果最好)。 内存优化 内存消耗大户有两个：证明钥和电路。电路是最占用内存的，证明钥占用的内存是每 100 万个门限制小于 512MB，相比电路来说，它看起来没那么吃内存。 用一个扁平的列表结构来表示所有的门限制是需要很大内存的。尤其我们路印协议中是用的 Poseidon 哈希函数，它的门限制个数是最少的，这点很棒；但是它需要用到大量的线性组合，从而需要更多的内存。 一个降低内存消耗最容易的改动点是不要独立的存储系数，转而建立一个能被重复使用的系数池，在门限制中则只存储一个指向实际系数的池子下标。显而易见，存储一个下标 (4 个字节) 要比存储系数 (32 个字节) 更省内存。比如，我们的一个有 6400 万门限制的电路存储了 10 亿 (你没看错，就是 10 亿) 个系数，而其中只有 20569 个不同的系数，其他很多系数是重复的。 但是即使我们做了这个优化，门限制扁平的列表结构中仍然还有很多重复数据。在我们的电路结构中大部分门限制是 Hash 函数，比如 Poseidon 和 SHA256。尽管这些 Hash 函数被用来处理不同的数据，但在电路中其实就是在不停的重复出现，只是作用于不同的变量而已。为了充分利用这个特征，我们改变了这种简单的扁平结构，尽管表现上仍然是一个列表，但每个门限制可以实现自己特定的逻辑，从而能更加有效的存储在内存中。我们目前为每种门限制只存储一次 (放到不同的面包板中)，在电路中则直接重复使用已建立好的门限制。而传递给电路的变量则需要在运行时处理一下，转译为指向当前第几个实例的变量。 还是以 6400 万门限制的电路为例，即使单独为每个门限制存储一个指针 (8 个字节)，也需要 512MB 内存，因此彻底改变之前用的扁平的列表结构是势在必行的。 还有一些其他零散的小点也都在消耗内存。比如，证明钥有一份完整电路的拷贝，而这个很明显是可以丢弃掉的。libsnark 有很多其他的地方也都在重复构造数据，即使数据本身可能只有很小一部分是不同的。 值得注意的是证明钥目前仍然是全部加载到内存中的，而所有的这些改动都可能带来一些微小的影响性能的变化。 其他优化 我们设计了一个生成零知识证明的服务器模式，该模式下会先提前一次性准备好所有必要的数据，这样不需要动态的去搭建电路和加载证明钥，尽管这两步的性能我们也已经有一些优化手段。 我们删除了一些 groth16 协议中和零知识相关的计算部分，因为我们路印协议主要把 zkSnark 用于链下扩容，所以这些相关的计算是无关紧要的 (这里要特别感谢 Kobi Gurkan 帮我们指出这一点)。 我们删除在证明函数中几乎所有的内存分配，因为动态分配内存也是很慢的，我们可以采用更快的提前分配内存的方法来改进这一点。 我们在 libsnark 里面采用了更多的并行化，有些耗时久的函数之前没有充分利用多核性能。 我们现在支持给不同的硬件机器配置不同的参数，尽管默认的值可能已经工作的挺好了，但最好还是特定机器采用专门针对该机器调整过的一套最优参数。如果最终决定用一台机器来不停的生成证明的话，我们给出的建议是最好要自己花些时间去调优到最佳参数。我们实现了测评模式，在该模式下，你就很容易地能比对不同参数配置下的性能数据，从而找出针对特定机器的最优参数配置。 结论 我们对目前优化的效果很满意，但毋庸置疑还能更进一步的提升。采用最新的证明生成优化方案，链下计算部分的成本已经极大地降低了，目前只占到总成本的 1/3 了。更快地生成证明也就意味着，任何的状态更新也都能更快地被在链上确认，这也能降低在 Layer1 做聚合 ZK Rollup 10的成本。同时我们也很期待 groth16 的进一步发展，能带来比其他零知识证明协议更高的性价比。 目前的方案都是 100% 基于 CPU 的，而我们也尝试过用 GPU 去加速证明的生成，有些其他项目也在用 GPU 做加速。但是 GPU 加速更困难一些，尤其考虑到云计算上，租用 GPU 的机器普遍都价格很贵。我们觉得可能用多 CPU 并行会比用 GPU 来加速更节约成本一些。 我们希望这些优化手段也能给其他运用零知识证明的项目带来一些帮助，尽管我们是在 groth16 的 libsnark 实现版本基础上做的优化，但是其核心优化思想应该也能运用到其他零知识证明的实现框架上。我们所有的优化代码都已开源，如果你有任何优化的想法或者疑问的话，欢迎随时联系我们！你能在下面一些项目上找到这些优化： https://github.com/Loopring/libfqfft/tree/opthttps://github.com/Loopring/libff/tree/opthttps://github.com/Loopring/libsnark/tree/opthttps://github.com/Loopring/ethsnarks/tree/opthttps://github.com/Loopring/protocol3-circuits/tree/opt路印交易所 路印协议已上线公测版本，大家可以去 体验。如果一切顺利的话，我们会在 2 个月内把我们做的优化方案更新到线上运行。 路印交易所是一个高性能、非托管、基于订单模式的以太坊上的去中心化交易所，欢迎关注我们的微信公众号路印 Loopring，访问我们的 官网 ，或者直接去 交易所网站体验。
来源链接：medium.com —- 编译者/作者：路印 Loopring 玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。 |
如何将链下交易成本降低至 1/5？看看路印协议首席架构师技术详解
2020-03-11 路印 Loopring 来源：链闻
使用 AWS 生成证据每笔交易成本
生成证明工作量占比
FFT 算法概要
LOADING...
相关阅读：
- 以色列将启动区块链平台2020-08-05
- Chromia为期权交易孵化DeFi项目“Hedget去中心化协议”2020-08-04
- Reddit的“扩展烘烤竞赛”以22个项目的申请结束2020-08-04
- MEW创始人表示，ICO崩溃教的项目如何避免报复2020-08-04
- 律动NEXT开始第三期助力，新增 6 个新项目2020-08-04