比较通用zk-SNARK-Coinmonks
zk-SNARK空间的移动速度如此之快,难以跟上。就在最后两个月,宣布了许多新的突破性zk-SNARK结构。新功能是臭名昭著的“可信设置”现在是多余的,这意味着现在可以使用任何任意计算(您好,智能合约)。但是,很难找到关于这些新结构的容易理解的信息。在这篇博客文章中,我比较了新结构。这些构造背后的多个团队已经分享了即将进行的进一步改进。收到新信息后,我将更新此博客文章
像zk-SNARKs这样的零知识证明具有广泛的应用范围:Zcash使用零知识来保护隐私,Coda和Mir将整个区块链压缩到仅几千字节,0x和Matter将许多交易汇总到以太坊上的单个证明。 (对于那些不了解零知识证明的人,请参阅以下说明)
像Groth16这样的传统zk-SNARK具有一个主要缺点:它们依赖于使用一次性可信设置创建的公共参考字符串。此设置将创建一个证明字符串,供证明者和验证者使用。存在三个主要问题:
新的zk-SNARK构造解决了设置限制,这意味着像智能合约这样的任意代码都可以作为zk-SNARK运行。有两种不同的方法:
新的zk-SNARK如何比较?在证明方方面,为每个zk-SNARK构造创建证明需要O(n log n)时间。差异主要是证明大小,验证时间和参考字符串的大小。
以下分类基于亚历山德罗·基耶萨(Alessandro Chiesa)在旧金山的ZKSummit zk0x04上的演讲。前导是在设置中创建的参考字符串的类型。 (请注意,基于静态电路特定参考字符串的Zk-SNARK构造不是通用的,但包含在其中用于比较。)
根据参考字符串的类型对zk-SNARK进行分类三种类型的zk-SNARK编译器(颜色与上表中的zk-SNARK匹配)。
所有这些zk-SNARK都在内部使用以下三种类型的编译器之一:预处理,DARK和传统(非通用)SNARK。审阅者注意:可以改进三个编译器的命名。欢迎提出建议。
作为参考,我将介绍三个现有结构。一个(Groth16)是通用的,它依赖于特定电路的一次性不可更新设置。第二个是Sonic,它是通用的zk-SNARK。
目前已知最快和最小的zk-SNARK。它在Zcash等中使用。 Groth16是非通用的;设置总是与一个特定的电路绑定。由于速度快,证明量小,因此经常将新的zk-SNARKS与Groth16进行比较。
论文:https://eprint.iacr.org/2016/260
Sonic是早期的通用zk-SNARK协议。该论文于2019年1月发布,距离撰写本博文还不到10个月,这是zk-SNARK时代的永恒。 Sonic支持通用且可更新的通用参考字符串。音速校样是恒定大小的,但验证成本很高。从理论上讲,可以批量验证多个证明以实现更好的性能。下面列出的许多新zk-SNARK都是基于Sonic的。
论文:https://eprint.iacr.org/2019/099
Fractal是一种zk-SNARK,可以进行递归,而无需配对友好的椭圆曲线。通过对电路进行预处理,可以进行透明设置的简洁验证。目前,证明大小高达250 kB,并且明显大于其他构造。大小将在即将进行的更新中减小。
论文:https://eprint.iacr.org/2019/1076
Halo是zk-SNARK,无需受信任的设置即可支持递归证明合成。递归使用“嵌套摊销”进行工作:在椭圆曲线的周期内将多个证明反复折叠在一起。
与其他新结构不同,Halo的验证时间是线性的,这使其成为唯一一个简洁的新结构。但是,即将有改进。
论文:https://eprint.iacr.org/2019/1021
正如您已经猜到的,SuperSonic是对Sonic的改进。 SuperSonic是第一个透明的zk-SNARK,具有实用的证明者时间以及渐近对数证明的大小和验证时间。
论文:https://eprint.iacr.org/2019/1229
Marlin是对Sonic的改进,其证明时间缩短了10倍,验证时间缩短了4倍。
论文:https://eprint.iacr.org/2019/1047
Plonk是对Sonic的改进,证明时间缩短了5倍。
论文:https://eprint.iacr.org/2019/953
最大的问题是:如何在性能方面进行比较?不幸的是,我不知道zk-SNARK的任何基准,即使有基准,也不是所有的新构造都具有参考实现。确实具有参考实现的构造毫无例外地未经优化。因此,下表中的数字应与一粒SALT一起使用。它们基于论文中的基准,或者基于发明人提供的估计。
查看证明大小,棒球场证明者运行时和棒球场验证运行时,值得注意的是:
当出现新信息或改进结构时,我将更新此博客文章。我很想听听您关于zk-SNARK的了解。为工程师介绍zk-SNARKs?递归zk-SNARKs?在评论中让我知道或给我发送电子邮件。
非常感谢加州大学伯克利分校的Dev Ojha不懈地解释了Fractal和其他项目的细节。感谢Howard Wu,J Ayo Akinyele和Lorenz Breidenbach的校对并提供反馈。
如果您是Rust学习者,并且对学习zk-SNARK感兴趣(但不一定具有zk-SNARKS的经验):Starling Protocol正在招聘中。 Starling是基于加州伯克利市的可编程简洁第一层协议。 Starling协议是一个多元化且包容的工作场所。我们鼓励有色人种,LGBTQ个人和女性申请。电子邮件ronald@starlingprotocol.com了解更多信息。