GKR+Groth16与Groth16验证MiMC哈希的验证时间比较

原文标题:Prover time comparison of GKR+Groth16 vs. Groth16 for proving MiMC hashes 原文链接:https://ethresear.ch/t/prover-time-comparison-of-gkr-groth16-vs-groth16-for-proving-mimc-hashes/8373 作者:Olivier Begassat, Alexandre Belling, Gautam Botrel, Nicolas Liochon, Thomas Piellard 翻译:Ada 根据此处的建议41,我们介绍了针对MiMC7实施GKR + Groth16的结果。 这篇文章使用两种方法比较了2 ^ 23(〜8M)个MiMC哈希的验证时间: 1.使用Gnark 10在Groth16中实现简单的哈希电路(从2 ^ 17哈希的证明时间推算得出) 2.我们的GKR + Groth16方法:生成GRK证明,将其提供给嵌入Groth16 SNARK电路中的GKR验证器,并使用Gnark生成相关的SNARK证明。 The latter is 27 times faster than the former, i.e. 3 minutes for GKR+Groth16 vs. 1 hour and 24 minutes for Groth16 only. 后者比前者快27倍,即对于GKR+Groth16为3分钟,而对于Groth16仅为1小时和24分钟。 ###电路 GKR电路对MiMC排列BN256标量场进行检查(与我们最初的建议用gMiMC7进行检查相反)。它由91层组成,具有相同的结构,但使用层特定的圆常数。每一层由以下类型的门组成: 复制输出其左入口值的门(忽略右入口的值)。 复制(vl,vr)= vl。 非线性门  nonlin(vl,vr)=vl+(vr+c)7 最终回合非线性门fnonlin(vl,vr)=(vr+c)7 (确切地说:除最后一层外,每一层都包含复制和非线性门,而最后一层仅包含最终的圆非线性门。) 基本电路由91层组成,每层都有两个输入,比方说v = [v0,v1],并产生两个输出(最后一层除外,仅产生一个)。 基本电路有2bN个(例如223个)并行副本。 在每个中间层,基本电路的输出为[nonlin(v1,v0),copy(v1,v0)]。 在最后的(输出)层中,基本电路仅输出[fnonlin(vl,vr)]。 请注意,本文中描述的MiMC舍入函数的形式为x→(x + c + k)7。 流水线操作x→x7,x→x + c和x→x + k的结果是vr的度数为1。 这样可以节省证明者的大量时间。 但是,重要的是在第一层中预先添加v0 = v0 + v1,并在最后一层中使用最终的圆形非线性门。 ###结果 我们在32个核心AWS c5.24xlarge实例上对实现进行了基准测试。 我们的基准测试包括生成GKR证明所需的时间和构建用于验证GKR证明的电路的SNARK证明所需的时间。 它还包括这两个步骤的分配时间。 对于基准,我们将bN设置为23(即:证明8M哈希值) 对于基线,我们对任务的运行时间和验证MIMC的gnark电路的验证时间进行基准测试。由于SNARK电路无法在bn256曲线上验证8M的哈希值,所以我们只能用更少的哈希值来推断结果。我们对2^17散列进行了基准测试,并将结果扩展到2^23。 我们实施了以下电路9来衡量Gnark的性能。 | 运维|运算时间 | | :------------: | :------------: | | Groth16 Prover-2 ^ 15哈希值 | 20.2 | | Groth16 Prover-2 ^ 17哈希值 | 78.2 | |外推到2 ^ 22哈希 | 2587 | | 外推到2 ^ 23哈希 | 5006.3 | 我们实施了7个GKR证明者和Groth16证明证明电路。 使用2 ^ 22(〜4M)哈希值: ##观察和可能的改进 ###每秒约束 当我们查看“每秒约束数量”度量时,MiMC哈希的Gnark性能远远优于GKR证明检查器的Gnark性能。 下表显示,与验证MiMC哈希的电路相比,GKR证明验证电路中的导线更多。 换句话说,约束的数量不是预期性能的不完美指标。 | 电路 | 约束数量 | 系数数量 | 电线数量 | | :------------: | :------------: | :------------: | :------------: | | SNARK MiMC-2 ^ 17哈希值 |47841280 | 93 | 47972353 | | SNARK GKR-2 ^ 23哈希值 | 32506244 | 95 | 49311227 | ###验证时间对哈希数的影响 使用简单的Groth16证明者,证明时间随哈希数线性增长。 Groth16 + GKR具有次线性(对数)的开销,因此,验证的散列越多,这种方法就越有趣。 ###未来工作 可以将这种方法应用于其他类型的哈希函数(例如Poseidon)以及完全不同的用途(例如签名验证)。 GKR路径未完全优化。 对实现进行专业化处理,再加上各种优化措施,应该会导致> 30倍的改进。

区块技术花

2021.01.27
945
收藏

个评论:

发表评论

感谢您的善举,每一次解答会成为新人的灯塔。回答被采纳后获得20算力和相应LK币奖励。

关闭