8种zk-SNARK构建的比较

傷城~ 2022-08-29 05:51 64阅读 0赞

zk-SNARK是一个快速发展的领域，仅在过去的两个月里， 就宣布了数个突破性的zk-SNARK构建。曾经必须的可信设置 现在已经是冗余的了，这意味着可以使用任何计算。然而关于这些 新的zk-SNARK构建的资料很难找到。在这片文章中，我将比较 这些新出现的zk-SNARK构建，并在以后不定期更新。

像zk-SNARK这样的零知识证明有很多应用：Zcash利用零知识证明 来保护隐私，Coda和Mir利用零知识证明将整个区块链压缩到只有 几K字节，0x和Matter则利用零知识证明将许多交易封装为以太坊 上的单一证明。如果你还不了解零知识证明，可以看一下这里的 [解释][Link 1]。

## 1、可信设置 ##

传统的zk-SNARK，例如Groth16有一个主要的缺点：依赖于一个公共 的参考字符串，该字符串使用一次性可信设置创建。该设置创建一个 供证明方和验证方同时使用的参考字符串。这里面有三个主要的问题：

*  可信设置生成的“有毒废料”，如果泄露的话，可以被用于生成无法 检测的伪造证明。多方计算通常会忽略这个问题，但是仪式的协调 异常复杂。
 *  可信设置创建的参考字符串通常绑定到一个电路（基本上就是程序）。 不可能为任何计算创建一个单独的可信设置，这使得很多应用都不可行， 例如智能合约。
 *  可信设置是一次性的，生成的参考字符串不可升级，这意味着如果 Zcash需要修复其zk-SNARK电路中的哪怕一个很小的bug，也需要一个 新的仪式来部署修复。

## 2、通用zk-SNARK ##

新的zk-SNARK构建解决了对可信设置的要求，这意味着像智能合约等 任意代码可以作为zk-SNARK运行。目前有两个不同的方法：

*  透明设置

设置创建一个共用的参考字符串，公开并且不会创建有毒废料。 这和zk-STARK的机制类似。Fractal、Halo和SuperSonic-CG使用的就是 透明设置。这种方法的缺点在于证明数据量会很大。Fractal和zk-STARK证明 能达到250KB，这对于区块链应用是不现实的。Fractal团队告诉我，他们 正在解决证明数据量过大的问题。Halo和SuperSonic的证明要小一些， 不到10KB。

*  通用设置

这种设置创建一个结构化参考字符串，也会产生有毒废料，不过 设置不再局限于单一电路，一个参考字符串可以用于无限的任意电路中。 例如Marlin、SuperSonic-RSA和Plonk。这三种构建生成的参考字符串可以 升级，以便提高安全性。如果当前的有毒废料泄露，那么只需要升级设置 就可以再次保障系统的安全。

## 3、zk-SNARK分类 ##

如何比较新出现的zk-SNARK？在证明人侧，为每种zk-SNARK构建生成一个 证明需要O(n log n)时间。区别主要在于证明的数据量大小、验证时间以及 参考字符串的大小。

下面的分类基于Alessandro Chiesa在旧金山ZKSummit上的[演讲][Link 2]：

![zk-snark构建比较][zk-snark]

所有这些zk-SNARKS使用的编译器可以分为三类：预处理、DARK和传统的SNARK（非通用）：

![zk-snark构建比较][zk-snark 1]

## 4、已有的zk-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

## 5、新的zk-SNARK构建 ##

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

## 6、zk-SNARK构建的性能比较 ##

一个大问题是：如何比较这些不同zk-SNARK构建的性能？不幸的是，我不知道zk-SNARK有 任何基准测试，不过即使有的话，也不是所有的新构建都有一个参考实现。因此下面表格 中的数字请不要过于较真，它们是基于论文中的基准指标，或者基于发明者提供的估算。

通过查看证明的大小、证明运行时间、验证运行时间，有一些方面是值得注意的：

*  使用透明设置的构建通常由较大的证明数据量
 *  Halo的验证时间不恒定，这和其他新的zk-SNARK构建不同
 *  在证明数据量尺寸和运行速度方面，Groth16仍然是无敌的

![zk-snark构建比较][zk-snark 2]

--------------------

原文链接：[Comparing General Purpose zk-SNARKs][]

[Link 1]: https://towardsdatascience.com/what-are-zero-knowledge-proofs-7ef6aab955fc
[Link 2]: https://www.youtube.com/watch?v=-EkUn4iD8Z8
[zk-snark]: /images/20220829/22ccc604cf214cf9a12a90fd8f9b8ff7.png
[zk-snark 1]: /images/20220829/956eaad742c741229ff4c8fd10d0f95e.png
[zk-snark 2]: /images/20220829/b8a67737842b425896784628c025e309.png
[Comparing General Purpose zk-SNARKs]: https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd