比较通用zk-SNARK-Coinmonks

罗纳德·曼纳克

zk-SNARK空间的移动速度如此之快,难以跟上。就在最后两个月,宣布了许多新的突破性zk-SNARK结构。新功能是臭名昭著的“可信设置”现在是多余的,这意味着现在可以使用任何任意计算(您好,智能合约)。但是,很难找到关于这些新结构的容易理解的信息。在这篇博客文章中,我比较了新结构。这些构造背后的多个团队已经分享了即将进行的进一步改进。收到新信息后,我将更新此博客文章

像zk-SNARKs这样的零知识证明具有广泛的应用范围:Zcash使用零知识来保护隐私,Coda和Mir将整个区块链压缩到仅几千字节,0x和Matter将许多交易汇总到以太坊上的单个证明。 (对于那些不了解零知识证明的人,请参阅以下说明)

像Groth16这样的传统zk-SNARK具有一个主要缺点:它们依赖于使用一次性可信设置创建的公共参考字符串。此设置将创建一个证明字符串,供证明者和验证者使用。存在三个主要问题:

  • 该设置会产生“有毒废物”,如果泄漏,可用于生成无法检测到的伪造证据。多方计算(通常称为仪式)在很大程度上抵消了该问题,但是协调此类仪式非常复杂。
  • 受信任的设置创建的参考字符串始终绑定到一个电路(基本上是程序)。一个单一的设置不可能进行任何任意的计算。这使得许多应用程序成为不可能,例如智能合约。
  • 该设置是一次性事件,并且生成的参考字符串不可升级。这就是说,例如,如果Zcash需要修复zk-SNARK电路中的一个小错误,则需要进行新的仪式来部署该错误修复。
  • 新的zk-SNARK构造解决了设置限制,这意味着像智能合约这样的任意代码都可以作为zk-SNARK运行。有两种不同的方法:

  • 透明设置:该设置会创建一个通用参考字符串,是公共的,不会产生有毒废物。这类似于zk-STARK(带有T)的工作方式。分形,光晕和SuperSonic-CG使用透明设置。这种方法的缺点是证明大小可能很大。分形和zk-STARK证明可能高达250kB,这对于区块链应用来说可能是不切实际的。分形团队告诉我,他们正在努力减少证明的大小。 Halo和SuperSonic具有10 kB或更小的证明尺寸。 (注意:zk-STARK是特定的零知识构造的名称,类似于Groth16或Fractal。另一方面,zk-SNARKs是一类构造的名称。这就是为什么Fractal称为zk-SNARK的原因。 ,而不是zk-STARK)
  • 通用设置:该设置会创建一个结构化参考字符串,会产生有毒废物,但该设置不仅限于一个电路。相反,一个参考字符串可以与无限数量的任意电路(具有一定的最大大小)一起使用。例如Marlin,SuperSonic-RSA和Plonk。仪式结束后,可以更新这三个构造的参考字符串,以提高安全性:万一当前有毒废物泄漏,只需更新设置即可再次确保系统安全。 (一些通用的zk-SNARK,例如AuroraLight和Libra使用静态的不可更新的通用设置。我们不在此博文中介绍这些内容)。
  • 新的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一起使用。它们基于论文中的基准,或者基于发明人提供的估计。

    查看证明大小,棒球场证明者运行时和棒球场验证运行时,值得注意的是:

  • 具有透明设置的构造通常具有更大的证明大小
  • 与其他新构造不同,Halo中的验证时间不是恒定的
  • 就证明大小和运行时间而言,Groth16仍然是无与伦比的
  • 当出现新信息或改进结构时,我将更新此博客文章。我很想听听您关于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了解更多信息。

    你可能还喜欢