第十四章：零知识证明简介

一. 什么是零知识证明

零知识证明简单来说就是一个人可以向他人证明他知道的某个东西，而无需向他人透露这个东西。为了方便理解零知识证明，阿里巴巴有一个非常经典的例子。阿里巴巴能够向窃贼证明他知道这个神奇的词，而无需透露它。

斯坦福教授 Dan Boneh 的讲座视频时，说了一个描述零知识证明的生动例子：Dan 教授试图向幼儿园的孩子们介绍零知识证明，使用游戏——“沃尔多在哪里”。Waldo 在哪里是一款经典的棋盘游戏，要求玩家在一张挤满了人的图片中找到一个特定的角色——Waldo。如下图所示：

如何使用零知识证明来证明你知道 Waldo 在哪里？

首先，你需要一把剪刀。接下来，转身从背后剪下沃尔多的身影，让挑战者看不到它。然后撕开板的其余部分。并将沃尔多形象交给挑战者。这完美地证明了你知道沃尔多的位置而不暴露它。此示例中使用的知识称为“Waldo 的位置”。

二. 零知识证明的流派

1.常见零知识证明流派

在介绍零知识证明流派之前，大家要注意我们常说的 ZK-SNARK 不是一种算法，而是一种流派。ZK-STARK 是一种具体零知识算法的名字。

1.1 STARK 与 SNARK

只需快速说一下，零知识证明技术就可以让一方向另一方证明他们知道某事，而证明者不必自己传达信息来证明他们的知识。它们既是一种隐私增强技术，因为它们减少了需要在用户之间提供的信息量，也是一种扩展技术，因为它们可以让证明以更快的速度得到验证，因为它们不包含全部数量非私有系统的信息。

当今市场上最引人注目的两种零知识技术是 zk-STARKs 和 zk-SNARKs。两者都是双方证明自己知识的方法的缩写：zk-STARK代表零知识可扩展透明知识论证，zk-SNARK代表零知识简洁非交互式知识论证。这篇文章将深入探讨从文化和技术角度探讨这两种不同的零知识技术之间的核心差异。此外，这两种零知识技术本质上都是非交互的，这意味着代码可以自主部署和行动。下面，我们有几个表格描述了这两种技术之间的一些高级差异。我们还将深入研究段落格式的差异。

1.2. SNARK

2012 年 1 月，加州大学伯克利分校的一位名叫 Alessandro Chiesa 的教授与人合作了一篇论文，为他们首次构建的零知识证明创造了 zk-SNARK 一词。Zk-SNARK 在其基础上的安全性依赖于椭圆曲线。密码学中的椭圆曲线在基本假设下运行，即找到随机椭圆曲线元素相对于公知基点的离散对数是不可行的。

虽然关于椭圆曲线随机数生成器是否存在后门一直存在重大争议，但该算法作为一个整体通常仍然是安全的。尽管边信道攻击中有几个流行的漏洞，但它们很容易通过多种技术得到缓解。量子攻击确实笼罩着基于椭圆曲线的密码学，但打破其安全模型所需的量子计算尚未广泛使用。

除了基于椭圆曲线之外，zk-SNARKs 还需要一个可信的设置。可信设置是指用于创建私人交易所需证明和验证这些证明的密钥的初始创建事件。最初，当创建这些密钥时，验证密钥和发送私人交易的密钥之间存在一个隐藏参数。如果用于在可信设置事件中创建这些密钥的秘密没有被破坏，则这些秘密可用于通过虚假验证来伪造交易，从而使持有者能够执行诸如凭空创建新令牌并使用它们之类的操作用于交易。由于 zk-SNARK 的隐私特性，无法验证凭空创建的代币实际上是无中生有。话虽这么说，但最初只需要受信任的设置。

因此，基于 SNARK 的网络的用户必须依赖于可信设置正确执行的事实，这意味着与可信设置密钥相关的秘密已被破坏，并且没有被监督仪式的个人持有。对可信设置的依赖一直是 SNARK 批评者最关心的领域之一。话虽如此，开发人员只需要最初使用受信任的设置，而不是持续使用。

SNARK 的另一个重要批评领域是它们不具备量子抗性。一旦量子计算在很大程度上可用，SNARK 背后的隐私技术就会被打破。当然，SNARK 的支持者正确地指出，当使用量子计算机时，我们将面临更多问题，例如 RSA 和大多数钱包基础设施的破坏。

话虽如此，尽管存在与可信设置相关的问题，但 SNARK 的采用速度实际上比 STARK 快得多，原因有很多。SNARK 比 STARK 早几年被发现，这使该技术在采用方面取得了显着的领先优势。Zcash 是较老的数字资产项目之一，在区块链开发社区中推广了 SNARK 的使用。由于 Zcash 和其他 SNARKs 的采用者，SNARKs 拥有最多的开发人员库、已发布的代码、项目和积极致力于该技术的开发人员。除了 Zcash，新兴的 DEX Loopring 也使用了 SNARK。如果开发人员想开始使用零知识技术，他们在使用 SNARK 方面将获得比 STARK 更多的支持。

此外，据估计，SNARK只需要 STARK 所需气体的 24%，这意味着与 SNARK 进行交易对最终用户来说要便宜得多。最后，SNARKs 的证明大小比 STARKs 小得多，这意味着它需要更少的链上存储。

1.3. STARKs

虽然 SNARKs 在文档和开发人员支持方面比 STARKs 具有一些明显的优势，但 STARKs 确实提供了一些独特的优势。但首先，让我们从技术角度深入了解一下 STARK 是什么。 Eli Ben-Sasson、Iddo Bentov、Yinon Horeshy 和 Michael Riabzev 在2018 年撰写了第一篇描述 STARK 的论文。与 SNARK 不同，STARK 的基础技术依赖于哈希函数。马上，依赖散列函数提供了一些好处，例如抗量子。此外，开始在网络中使用 STARK 不需要任何受信任的设置。

话虽如此，STARKs 的证明尺寸比 SNARKs 大得多，这意味着验证 STARKs 比 SNARKs 需要更多时间，并且还会导致 STARKs 需要更多 gas。此外，由于缺乏开发人员文档和社区，开发人员将很难使用 STARK。虽然有一些项目创建了基于 STARK 的扩展解决方案，例如STARKWARE，但 SNARKs 社区仍然大得多。虽然两个开发者社区都支持 SNARK 和 STARK，但以太坊基金会特别表示支持使用 Starks 的 STARKware。事实上，以太坊基金会向 STARKware 提供了 1200 万美元的赠款，清楚地体现了他们对新兴技术的投入。

1.4. ZK-SNARK

我们最常见的可能是 ZK-SNARK。SNARK 的缩写是 succinct non-interactive arguments of knowledge。SNARK 最特殊的点在于他的 N，非交互性。 - 简洁性（Succinct）：验证所需要的计算资源远远小于重新跑一遍需要证明的程序 - 非交互性（Non-interactive）：证明者和验证者不需要每一轮都沟通。他们只需要在一开始完成可信初始化（Trust Setup）。其他验证者也可以在可信初始化之后加入验证 - Argument：如果证明者有着无比强大的算力，那么他可以生成假证明。如果这种情况发生，主流的公私钥加密模式也不再安全 - 知识（Knowledge）：证明者需要知道一些其他人不知道的秘密，才能生成证明

ZK-SNARK 最大的问题在于它需要可信初始化。可信初始化会生成参考字符串（Reference String）。如果 RS 被泄露，那么任何人都可以生成虚假证明。此外，如何设计多人参与的可信初始化也很具有挑战性。RS 还只能被用于置顶的程序。对于其他的程序，我们需要另外的可信初始化。因此 ZK-SNARK 不可能用于通用计算。另外一点，RS 不能升级。如果我们升级了程序，可信初始化要重新运行。 ZK-SNARK 的问题是信任建立阶段。信任建立阶段会产生参考字符串。如果参考字符串被泄露，任何人都可以做一个假证明。此外，如何在多方之间协调这种信任设置阶段也很复杂。参考字符串只能在一个程序（电路）中使用。因此，在一般的计算中，不可能有 ZK-SNARK 的单一信任设置。另一个问题是，参考字符串是不可升级的。如果我们升级程序，我们需要重新运行信任设置阶段

为了解决这一系列的问题，科学家们找到了两个方向

Transparent Setup：可信初始化生成公共参考字符串（Common Reference String）。CRS 是公开的，不需要保密。Fractal，Halo，ZK-STARK，SuperSonic 都是采取了这一条路线。这一条路线的问题是生成的证明占用太多的存储，来到了 kB 的量级。对于区块链来说，存储是非常昂贵的。
Universal Setup：可信初始化生成了结构化参考字符串（Structure Reference String），但它需要保密。SRS 让可信初始化可以用于不同的程序，这让通用计算的证明可能实现。Marlink，SuperSonic-RSA 和 Plonk 都采用了这条路线。

三. 常见的零知识证明算法

Groth16：Zcash 一开始使用了这种算法。它是零知识证明中的跑分对照组，因为它具有证明快，生成的证明小的特点。它的缺点是需要可信初始化，并且一次可信初始化只能针对一个程序
Sonic：支持 universal setup. SRS 的大小和程序大小成线性关系。生成的证明是固定大小，但是验证需要消耗很多的计算资源。Sonic 让通用计算的零知识证明变为可能
Fractal：支持递归（Recursion）。生成的证明占用较多空间
Halo：支持递归，但并不满足简洁性（Succinct）因为证明时间是非线性的
SuperSonic：第一个实际的，可以应用的 Transparent ZK-SNARK
Marlin：程序可以升级。性能处于 Sonic 和 Groth16 之间
Plonk：程序可以升级；参与者按照顺序加入可信初始化。这让举行有很多人参与的可信初始化不那么复杂；Plonk 使用 Kate commitments 而不是多项式承诺。（ZK-SNARK 的第一步是将计算问题转化为多项式问题）