几种通用的zk-SNARKs 实现的比较
zk-SNARK 是一个快速发展的领域,仅在过去的两个月里, 就宣布了数个突破性的 zk-SNARK 实现。曾经必须的可信设置现在已经是冗余的了,这意味着可以使用任何计算。然而关于这些 新的 zk-SNARK 实现的资料很难找到。在这篇文章中,我将比较这些新出现的 zk-SNARK 实现,并在以后不定期更新。
像 zk-SNARK 这样的零知识证明有很多应用:Zcash 利用零知识证明 来保护隐私,Coda 和 Mir 利用零知识证明将整个区块链压缩到只有 几 K 字节,0x 和 Matter 则利用零知识证明将许多交易封装为以太坊 上的单一证明。如果你还不了解零知识证明,可以看一下这里的 解释。
传统的zk-SNARK,例如Groth16有一个主要的缺点:依赖于一个公共的参考字符串,该字符串使用一次性可信设置创建。该设置创建一个供证明方和验证方同时使用的参考字符串。这里面有三个主要的问题:
新的zk-SNARK实现解决了对可信设置的要求,这意味着像智能合约等任意代码可以作为 zk-SNARK 运行。目前有两个不同的方法:
设置创建一个共用的参考字符串,公开并且不会创建有毒废料。 这和zk-STARK的机制类似。Fractal、Halo 和 SuperSonic-CG使用的就是透明设置。这种方法的缺点在于证明数据量会很大。Fractal和zk-STARK证明数据能达到250KB,这对于区块链应用是不现实的。Fractal团队告诉我,他们正在解决证明数据量过大的问题。Halo和SuperSonic的证明要小一些, 不到10KB。
这种设置创建一个结构化参考字符串,也会产生有毒废料,不过 设置不再局限于单一电路,一个参考字符串可以用于无限的任意电路中。 例如Marlin、SuperSonic-RSA和Plonk。这三种实现生成的参考字符串可以升级,以便提高安全性。如果当前的有毒废料泄露,那么只需要升级设置就可以再次保障系统的安全。
如何比较新出现的zk-SNARK?在证明者方面,为每种zk-SNARK实现生成一个证明需要O(n log n)时间。区别主要在于证明的数据量大小、验证时间以及参考字符串的大小。
下面的分类基于Alessandro Chiesa在旧金山ZKSummit上的演讲。
所有这些zk-SNARKS使用的编译器可以分为三类:预处理、DARK和传统的SNARK(非通用):
作为参考,我将介绍三种已有的实现。Groth16是非通用的,它依赖于一次性 不可升级的设置,Sonic是一个通用的zk-SNARK。
Groth16:Groth16是目前最快、数据量最小的zk-SNARK,被用于Zcash等。Groth16不是通用的, 其设置需要绑定到一个特定的电路。由于其速度和证明的小数据量,因此常常被新的 zk-SNARK拿来比较性能。Groth16论文链接:https://eprint.iacr.org/2016/260
Sonic:Sonic是一个早期的通用zk-SNARK协议。论文发表于2019年1月。Sonic支持 通用、可升级的参考字符串。Sonic的证明大小固定,但是验证成本高。理论上 可以将多个证明分批验证以获得更好的性能。下面列举的许多新的zk-SNARK 都是基于Sonic。Sonic论文链接:https://eprint.iacr.org/2019/099
Fractal:Fractal 是一种允许递归的zk-SNARK。通过对电路的预处理实现了透明设置。 证明最大250KB,这笔其他实现生成的证明都要大的多。Fractal论文链接: https://eprint.iacr.org/2019/1076
Halo:Halo支持递归证据组织,无需可信设置。与其他新的zk-SNARK实现不同,Halo 的验证时间是线性的。Halo论文链接: https://eprint.iacr.org/2019/1021
SuperSonic:SuperSonic 是Sonic的改进版,是第一个在验证时间和证明数据量方面实用化 的透明zk-SNARK。SuperSonic论文链接: https://eprint.iacr.org/2019/1229
Marlin:Marlin 是Sonic的改进版,证明时间缩短10倍,验证时间缩短4倍。 Marlin论文链接: https://eprint.iacr.org/2019/1047
Plonk:Plonk也是Sonic的改进,证明时间缩短5倍。 Plonk论文链接: https://eprint.iacr.org/2019/953
一个大问题是:如何比较这些不同zk-SNARK实现的性能?不幸的是,我不知道zk-SNARK有任何基准测试,不过即使有的话,也不是所有的新实现都有一个参考实现。因此下面表格中的数字请不要过于较真,它们是基于论文中的基准指标,或者基于发明者提供的估算。
通过查看证明的大小、证明运行时间、验证运行时间,有一些方面是值得注意的:
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!