零知识证明引论（一）

这篇文章中，Cyte 会 和大家介绍 零知识证明 (ZKP)的 定义，并将零知识证明与 SNARK 和 STARK 这两个概念进行辨析。

ZKP、SNARK 和 STARK 等这些密码学概念随着最近区块链的兴起变得热⻔起来。但是，它们经常会被误解和混用。其实，所有这些概念都属于一个更广义的范畴，叫做证明系统 (Proof System)，或者叫做密码学证明（Cryptographic Proof）。零知识证明和 SNARK、STARK 之间都有交叉的部分，但并不相互包含。它们之间的关系可以用一张图来表示。

本文将首先介绍证明系统的定义，并讨论证明系统的各类性质，重点讨论「零知识性」、「知识证明」、「简洁性」和「非交互性」。特别的，如果一个证明系统具有「零知识性」，那么它就被称为一个「零知识证明」。最后，文章会讨论 SNARK 和 STARK 的定义并将其进行比较。

证明系统

一个证明系统 (Proof System)是一个交互式协议，包含两个参与方 Prover 和 Verifier，以及一个算法 Setup。证明系统的作用是让 Prover 说服 Verifier 相信一 件事，我们把这件事叫做一个陈述 (Statement)。

协议开始前，需要由某人调用 Setup 算法。Setup 算法接受一些公共参数作为输入，并输出 Prover 和 Verifier 所需的 Setup 信息，其中 Verifier 获知的信息记为 ，Prover 获知的信息记为 SetupP 。SetupP 和 SetupV 的公共部分称为公共参考字符串 (Common Reference String, CRS)。具体由谁、在什么时候调用 Setup 算法，取决于证明系统的设计。

协议一开始，Prover 和 Verifier 同时得到输入陈述 x。Prover 相对于 Verifier 必然要有一些额外的优势，例如更强大的计算能力，或者得到了一些额外的输入 w。除此之外，Prover 和 Verifier 还分别获知了 SetupP 和 SetupV。Setup 信息获取的时间取决于证明系统的设计。例如，有可能是 Prover 和 Verifier 早就下载好存在各自硬盘里可以反复使用的，也可能是协议开始前当场输入的。

然后 Prover 和 Verifier 开始执行证明系统规定的协议。如果 Prover 和 Verifier 都是诚实的，那么它们都严格遵守协议执行。不过，也有可能某一方是恶意的，没有按照协议规定来执行，此时会发生什么事情，取决于证明系统的安全性。如果两方都是恶意的，它们都不遵守协议，那就和这个证明系统没关系了。

最后，Verifier 输出 accept 或 reject，表示是否相信陈述 x。

一个证明系统需要满足两个性质：

完整性 (Completeness)：如果陈述 x 是正确的，而 Prover 和 Verifier 都遵守这个协议，那么 Verifier 以至少 1- εc 的概率输出 accept，这里 εc 被称为证明系统的完整性误差 (Completeness error)

可靠性 (Soundness)：如果陈述 x 是不正确的，此时 Prover 必然是不诚实的，而 Verifier 遵守协议，那么任何 Prover 都不能让 Verifier 输出 accept 的概率超过 εs，这个 εs 被称为证明系统的可靠性误差 (Soundness error)

这两个要求是使得一个证明系统成立的最基本的要求。少了哪个要求，我们都可以得到符合条件但完全没用的证明系统。例如，如果我们只要求完整性，那就无论 Prover 做什么，Verifier 永远只输出 accept 就好了；如果只要求可靠性，那就让 Verifier 永远只输出 reject。此外，一般希望 εs 和 εc都不超过 ，并且加起来小于 ，否则这个证明系统误差太大，也近乎无用。

如果将一个证明系统的可靠性只对任何计算能力受限的 Prover 成立，也就是说，计算能力无限的敌手是有可能欺骗 Verifier 的，此时这个证明系统只有计算可靠性 (Computational Soundness)，这样的系统又称为论证系统 (Argument System)。相比之下，对任何 Prover 都安全的可靠性被称为统计可靠性 (Statistical Soundness)。

证明系统的其他性质

一个证明系统还可以满足一些其他 (并非必需的) 性质

• CRS 模型 (CRS model)：如果 Setup 信息是对所有人公开可见的，即 Setup=SetupP=SetupV，称这个证明系统是在 CRS 模型下的

• 交互 (Interactive) / 非交互 (Non-interactive)：如果整个交互过程只有 Prover 向 Verifier 发送一条信息，就称这个系统是非交互证明系统；否则这个系统就是交互式证明系统

• 可迁移 (Transferable) / 可抵赖 (Deniable)：如果陈述 x 是正确的，并且把交互过程发送给其他 Verifier，也能够让其他 Verifier 相信陈述 x 的正确性，这个证明系统就是可迁移的；否则这个证明系统就是可抵赖的

• 公开可验证 (Public Verifiable) / 特定验证者 (Designated Verifier)：如果 SetupV 是对所有人公开可见的，即任何人都可以成为 Verifier，这个零知识证明系统就是公开可验证的。否则这个系统就是针对特定验证者的

• 公开随机 (Public coin)：如果 Verifier 的所有消息的选取都均匀随机且独立于 Prover 的消息，就称这个系统是公开随机的

• 零知识 (Zero-Knowledge)：在陈述 x 是正确的情况下，如果除了 x 的正确性，Verifier 无法从交互中获取任何其他「知识」，就称这个系统是零知识的

• 简洁性 (Succinctness)：如果这个证明系统是用来证明 NP 语言的，并且证明系统的通信量比证据 w 还要小，那么这个证明系统就具有简洁性

例：证明两个球的颜色不同

Setup 信息：有两个球

陈述 x ：这两个球颜色不同

Verifier 计算能力受限 (蒙上双眼)，Prover 具有正常的视力

1. Verifier 左右手各持一个球，展示给 Prover 看。

2. Verifier 把双手放到背后，接着 (在心里) 随机抛硬币，如果是正面朝上，就交换左右手里的球，否则不交换。

3. Verifier 把球拿出来给 Prover 看。

4. Prover 告诉 Verifier 两个球有没有交换。

结果：如果 Prover 猜对了，Verifier 输出 accept，否则 Verifier 输出 reject。

重要性质

上文中我们给出了证明系统的定义，样例和性质。接下来我们讨论证明系统的几个重要的性质。

零知识性

零知识性用来保护诚实的 Prover 不被恶意的 Verifier 欺骗而泄露证明所需的秘密证据。

上文中已经提到了证明系统的零知识性，将其简单描述为 Verifier 无法从交互中获取任何「知识」。这个描述是不确切的，因为它并没有给出一个严格的判断标准。

零知识性的定义本身是违直觉的：Prover 明明发送了一些比特数据给 Verifier，为什么这个系统会是「零知识」的呢？

实际上，「信息」并不等同于「知识」。如果 Verifier 获取了信息，但获得这些信息并不能让 Verifier 计算出更多结果，或者说这些信息是 Verifier 自己就能够计算出来的，那么 Verifier 就没有获取任何「知识」。

在一个证明系统的执行过程中，Verifier 获得的所有信息包括：SetupV；Verifier 自己的随机数 r；Prover 发送给 Verifier 的所有信息 (记为 p)。我们把这些信息称为 Verifier 的「视野」，记为 ViewV = (SetupV,r,p)。这些信息是 Verifier 计算过程中的所有不确定性的来源。确定了这些信息后，其他的一切都可以确定性地计算出来。

注意到，ViewV 是一个随机变量。当 Verifier 与 Prover 执行了证明系统之后，Verifier 会获得这个随机变量的一个样本。如果 Verifier 能在没有 Prover 参与的情况下独自采样 ViewV，那么这个系统就是零知识的。

我们把采样 这个随机变量的算法叫做模拟器 (Simulator)。根据模拟器工作方式的不同，有如下不同的定义方式：

1. 非黑盒模拟器，相对应的零知识性叫做非黑盒零知识。这个零知识的定义允许每个 Verifier 都存在一个「独家定制」的模拟器，这种定义允许模拟器针对不同的 Verifier 的实现细节来定制不同的采样过程。

2. 黑盒模拟器，对应的就是黑盒零知识。这个零知识的定义要求存在唯一的模拟器，使得对所有的 Verifier，它都能够采样出 SetupV 。这个唯一的模拟器不可能知道所有 Verifier 的具体实现细节，所以它只能通过黑盒调用的方式来访问 Verifier。不过，模拟器对 Verifier 具有完全的控制权。模拟器可以决定 Verifier 的随机数 r，并给 Verifier 输入任何的 Prover 消息或 SetupV 。所以，在模拟器的眼里，Verifier 是一个黑盒的确定性算法。

3. 如果模拟器只针对诚实 Verifier，对应的是诚实 Verifier 零知识 (Honest Verifier ZK)。因为诚实 Verifier 的行为是完全在预期中的，模拟器自然可以利用这些信息，因此这个模拟器对 Verifier 的访问是非黑盒的。

非黑盒模拟器访问到的信息更多，所以非黑盒零知识性比黑盒零知识性更容易成立。而诚实 Verifier 零知识是最容易实现的。

关于诚实 Verifier 零知识，这里的诚实 Verifier 更准确地说是半诚实 (Semi-Honest) 的，或者说「诚实但好奇的」。这样的 Verifier 表面上会遵守协议，但有可能私下里试图从消息中提取知识。

相比之下，恶意 Verifier 的行为是完全不受限制的。Verifier 可能宕机、发送不符合格式的消息、不按协议规定的分布采样，等等。要证明一个系统对恶意的 Verifier 满足零知识性，就要把所有这些情况都覆盖到。

模拟器是一个随机算法，它的输出值也是一个随机变量，记为 SimV。零知识性要求 ViewV 和 SimV 这两个随机变量难以区分。不过，「难以区分」这个词也有很多种版本，由此可以推出零知识证明的多种定义：

1. 如果两个随机变量的分布是统计不可区分的，也就是它们的统计距离 (Statistical Distance) 可忽略，就称这个证明系统是统计零知识 (Statistically Zero-Knowledge)的；如果统计距离就是 0，又叫做完美零知识 (Perfect Zero-Knowledge)的；

2. 如果两个随机变量的分布是计算不可区分的，也就是任何多项式时间的随机敌手都无法区分这两个分布，就称这个证明系统是计算零知识 (Computationally Zero-Knowledge)的。

注意到，零知识的定义中，只要求对于正确的陈述 x， ViewV 和 SimV 的分布难以区分。对于错误的陈述，我们并不关心 Verifier 能够获取什么知识，因为这种情况下 Prover 本身就是不诚实的，没有必要去保护它，或者说，Prover 既然不遵守协议，那我们的协议设计得再好也保护不到它。

不过，虽然 是错误的情况下，零知识性对 SimV 的分布不做任何假定，但如果输入错误的 x 采样得到的 SimV 被 Verifier 验证通过的概率和 x 正确的情况下有显著差别的话，我们就可以借此判断 x 的正确性。这就意味着 x 只能来自一个平凡的 NP 语言。所以，对于困难的 NP 问题，把错误的 x 输入给模拟器，得到的 SimV 也能够以一样的概率被验证通过。

这么一来，零知识性和可靠性岂不是矛盾的？换句话说，对于错误的 x，Prover 为什么不能调用模拟器来欺骗 Verifier？实际上，Prover 不能控制 Verifier，它也就不能为模拟器提供采样 SimV 所需要的资源。的确，一个恶意的 Prover 可以去调用模拟器，但是这对它来说没用，因为模拟器输出的 SimV中的 r 并不是正在与 Prover 交互的 Verifier 的随机数。此外，模拟器输出的 SetupV也可能和 Verifier 收到的 SetupV 不同而导致验证不通过。不过，Prover 调起的模拟器无法获取 Verifier 的随机数，这已经足够保证安全性了，所以交互式证明中 SetupV 即使是固定常量也没问题。

知识证明

如果要求 Prover 必须「知道」一些信息才能让 Verifier 验证通过，这个系统就被称为知识证明 (Proof of Knowledge)。知识证明可以看做可靠性的加强版。知识证明也有计算意义下的版本，叫做知识论证 (Argument of Knowledge)。

知识证明系统通常是用来证明 NP 语言的。一个 NP 语言是指一个集合 L，使得元素 x 属于 L 可以由一个证据 w 来证明，即存在一个多项式时间的算法能够判定 w 是否是 x 属于 L 的合法证据。

简洁性

综上，对于一般的 NP 语言，(对数级别的) 简洁证明系统只能是论证系统。

非交互性

非交互性 (Non-Interactivity)是指证明系统的全部交互只有 Prover 向 Verifier 发送的一条消息，这个消息叫做一个证明，记为π 。非交互性可以带来许多的便利，为证明系统带来更多的应用场景。例如，在区块链系统中，非交互性的零知识证明可以附在交易中，供任何人随时查验，而不需要交易的作者随时在线与验证者交互。

任何 NP 语言都天然具有一个非交互证明协议，也就是 Prover 直接将证据发送给 Verifier，而且这个证明是知识证明。所以，构造一个单纯具有非交互性的证明系统意义不大。非交互性只有和前面讨论的两个性质，即零知识性或简洁性组合起来才有意思。

非交互性 + 零知识

将零知识性和非交互性结合起来，就有了非交互零知识 (Non-Interactive Zero-Knowledge, NIZK)。

我们之前在讨论零知识性时讲到，零知识性之所以和可靠性不矛盾，是因为调用模拟器采样的 SimV 中的 r 大概率和与 Prover 交互的 Verifier 的随机数不同。但是，对于非交互零知识，我们要重新审视一下这个推理过程。

在交互证明中，一个随机数为 r1 的 Verifier 能够验证通过的 Prover 消息 p，直接搬到随机数为 r2 的 Verifier 那里就很可能验证不通过了。所以，在交互式证明中，p 的正确性不是全局的，而是依赖 r 的。

而在非交互证明中，Prover 没有收到 Verifier 的任何消息，所以 Prover 的计算过程没有用到 Verifier 的随机数 r。所以，为了达到证明系统的完整性，诚实的 Prover 输出的 p，对于大部分 Verifier 随机数 都是能验证通过的。所以，非交互证明中的 p 的正确性是全局的，不依赖任何 r。

非交互性 + 简洁性

上文提到，简洁性的证明系统必然是论证系统。结合非交互性，就有了简洁非交互式论证 (Succinct Non-interactive ARGument, SNARG)。实际上，满足 SNARG 定义的系统早在 2000 年就由 Micali 构造出来了，而这个名字是后来才出现的。

如果一个 SNARG 同时是一个知识论证，它就被称为简洁非交互式知识性论证 (Succinct Non-interactive ARgument of Knowledge, SNARK)。SNARK 这个名称由论文 BCCT12 首创，现在已经成为零知识证明领域最热门的概念之一。其实 SNARK 只具有简洁性和非交互性，并不一定具有零知识性。如果有零知识性，应该叫 zkSNARK。

STARK 和 SNARK 辨析

另一个经常和 SNARK 一起提到的概念是 STARK。它和 SNARK 只有一字之差，但有很多不同。下面我们比较一下这两个概念。

可以看出，SNARK 比 STARK 唯一多出的限制就是非交互性。尽管如此，通过后续文章将要介绍的 Fiat-Shamir 变换，STARK 一般都可以转化为非交互证明，转化的结果必然是一个 SNARK。在这种意义上，可以把 STARK 看做 SNARK 的子集。

上述 SNARK 和 STARK 的定义是这两个名词的广义涵义。狭义上，它们分别指代两个具体的构造方案。其中 SNARK 指的是以 Groth16 方案为代表的一系列基于 QAP 和双线性对的 zkSNARK 构造方案。而 STARK 在狭义上就专门指代 Ben-Sasson 等人在 2018 年提出的基于 AIR 和 FRI 的那一个方案。

小结

本文介绍了证明系统的定义，并讨论了证明系统的各类性质，重点讨论了「零知识性」、「知识证明」、「简洁性」和「非交互性」，解释了如何用模拟器来定义零知识性，以及用提取器来定义知识性证明。最后，文章讨论并比较了 SNARK 和 STARK。

参考资料

1. Goldreich.Foundations of Cryptography, Volume 1. Basic Tools. 2001.

2. ZKProof Community.ZKProof Community Reference. 2019.https://docs.zkproof.org/reference.pdf

3. Yehuda Lindell.How To Simulate It – A Tutorial on the Simulation Proof Technique. 2018.

4. Eli Ben-Sasson.A Cambrian Explosion of Crypto Proofs.https://nakamoto.com/cambrian-explosion-of-crypto-proofs/

作者：Cyte

来源： Nervos 中文社区

==

和11万人同时接收最新行情资讯

搜“鸵鸟区块链”下载

和2万人一起加入鸵鸟社群

添加微信ID：tuoniao02

本文经「原本」原创认证，作者 鸵鸟区块链 ，访问yuanben.io查询【 44JSSS29 】获取授权信息。