带你一文了解零知识证明

原标题：干货 | 零知识证明引论（一）

作者：Cyte

继上一次 Shor 发出了对之后，又有一位热爱研究的 Nervos 小伙伴 Cyte 对零知识证明做了详细的研究。

在这篇文章中，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 获知的信息记为 。 和  的公共部分称为公共参考字符串 (Common Reference String, CRS)。具体由谁、在什么时候调用 Setup 算法，取决于证明系统的设计。协议一开始，Prover 和 Verifier 同时得到输入陈述 。Prover 相对于 Verifier 必然要有一些额外的优势，例如更强大的计算能力，或者得到了一些额外的输入 。除此之外，Prover 和 Verifier 还分别获知了  和 。Setup 信息获取的时间取决于证明系统的设计。例如，有可能是 Prover 和 Verifier 早就下载好存在各自硬盘里可以反复使用的，也可能是协议开始前当场输入的。然后 Prover 和 Verifier 开始执行证明系统规定的协议。如果 Prover 和 Verifier 都是诚实的，那么它们都严格遵守协议执行。不过，也有可能某一方是恶意的，没有按照协议规定来执行，此时会发生什么事情，取决于证明系统的安全性。如果两方都是恶意的，它们都不遵守协议，那就和这个证明系统没关系了。最后，Verifier 输出 accept 或 reject，表示是否相信陈述 。一个证明系统需要满足两个性质：

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

这两个要求是使得一个证明系统成立的最基本的要求。少了哪个要求，我们都可以得到符合条件但完全没用的证明系统。例如，如果我们只要求完整性，那就无论 Prover 做什么，Verifier 永远只输出 accept 就好了；如果只要求可靠性，那就让 Verifier 永远只输出 reject。此外，一般希望  和  都不超过 ，并且加起来小于 ，否则这个证明系统误差太大，也近乎无用。如果将一个证明系统的可靠性只对任何计算能力受限的 Prover 成立，也就是说，计算能力无限的敌手是有可能欺骗 Verifier 的，此时这个证明系统只有计算可靠性 (Computational Soundness)，这样的系统又称为 论证系统 (Argument System)。相比之下，对任何 Prover 都安全的可靠性被称为统计可靠性 (Statistical Soundness)。

证明系统的其他性质

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

• CRS 模型 (CRS model)：如果 Setup 信息是对所有人公开可见的，即 Setup=Setup=Setup，称这个证明系统是在 CRS 模型下的
• 交互 (Interactive) / 非交互 (Non-interactive)：如果整个交互过程只有 Prover 向 Verifier 发送一条信息，就称这个系统是非交互证明系统；否则这个系统就是交互式证明系统
• 可迁移 (Transferable) / 可抵赖 (Deniable)：如果陈述  是正确的，并且把交互过程发送给其他 Verifier，也能够让其他 Verifier 相信陈述  的正确性，这个证明系统就是可迁移的；否则这个证明系统就是可抵赖的
• 公开可验证 (Public Verifiable) / 特定验证者 (Designated Verifier)：如果 Setup 是对所有人公开可见的，即任何人都可以成为 Verifier，这个零知识证明系统就是公开可验证的。否则这个系统就是针对特定验证者的
• 公开随机 (Public coin)：如果 Verifier 的所有消息的选取都均匀随机且独立于 Prover 的消息，就称这个系统是公开随机的
• 零知识 (Zero-Knowledge)：在陈述  是正确的情况下，如果除了  的正确性，Verifier 无法从交互中获取任何其他“知识”，就称这个系统是零知识的
• 简洁性 (Succinctness)：如果这个证明系统是用来证明 NP 语言的，并且证明系统的通信量比证据  还要小，那么这个证明系统就具有简洁性

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

Setup 信息：有两个球

陈述 ：这两个球颜色不同Verifier 计算能力受限 (蒙上双眼)，Prover 具有正常的视力

1. Verifier 左右手各持一个球，展示给 Prover 看。
2. Verifier 把双手放到背后，接着 (在心里) 随机抛硬币，如果是正面朝上，就交换左右手里的球，否则不交换。
3. Verifier 把球拿出来给 Prover 看。
4. Prover 告诉 Verifier 两个球有没有交换。

结果：如果 Prover 猜对了，Verifier 输出 accept，否则 Verifier 输出 reject。性质讨论完整性如果两球颜色不同，显然 Prover 一定能以百分之百的概率猜中 Verifier 有没有交换球可靠性如果两球颜色相同，那么 Prover 只能盲目猜测，只有 1/2 的概率猜中。这个系统的可靠性误差为 1/2CRS这个证明系统是在 CRS 模型下的，因为 Setup 信息是公开的交互性这是个交互系统，因为 Prover 和 Verifier 互相发送的信息超过一条可迁移性这个系统是不可迁移的，即可抵赖的。即使 Verifier 把交互过程记录下来展示给其他蒙住眼的人，他们也不能确信两个球颜色不同公开可验证性这个系统是公开可验证的，任何 Verifier 都可以和 Prover 进行这个协议公开随机性这个系统不是公开随机的，因为 Verifier 发送给 Prover 的信息不是均匀随机的零知识性这个系统是零知识的，因为在两个球颜色确实不同的情况下，Prover 的猜测是 Verifier 意料之中的，除了表示陈述 x 的正确性外，没有任何额外知识

重要性

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

零知识性

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

上文中已经提到了证明系统的零知识性，将其简单描述为 Verifier 无法从交互中获取任何“知识”。这个描述是不确切的，因为它并没有给出一个严格的判断标准。零知识性的定义本身是违直觉的：Prover 明明发送了一些比特数据给 Verifier，为什么这个系统会是“零知识”的呢？实际上，“信息”并不等同于“知识”。如果 Verifier 获取了信息，但获得这些信息并不能让 Verifier 计算出更多结果，或者说这些信息是 Verifier 自己就能够计算出来的，那么 Verifier 就没有获取任何“知识”。在一个证明系统的执行过程中，Verifier 获得的所有信息包括：；Verifier 自己的随机数；Prover 发送给 Verifier 的所有信息 (记为 )。我们把这些信息称为 Verifier 的“视野”，记为 。这些信息是 Verifier 计算过程中的所有不确定性的来源。确定了这些信息后，其他的一切都可以确定性地计算出来。注意到， 是一个随机变量。当 Verifier 与 Prover 执行了证明系统之后，Verifier 会获得这个随机变量的一个样本。如果 Verifier 能在没有 Prover 参与的情况下独自采样 ，那么这个系统就是零知识的。我们把采样  这个随机变量的算法叫做模拟器 (Simulator)。根据模拟器工作方式的不同，有如下不同的定义方式：

1. 非黑盒模拟器，相对应的零知识性叫做非黑盒零知识。这个零知识的定义允许每个 Verifier 都存在一个“独家定制”的模拟器，这种定义允许模拟器针对不同的 Verifier 的实现细节来定制不同的采样过程。
2. 黑盒模拟器，对应的就是黑盒零知识。这个零知识的定义要求存在唯一的模拟器，使得对所有的 Verifier，它都能够采样出 。这个唯一的模拟器不可能知道所有 Verifier 的具体实现细节，所以它只能通过黑盒调用的方式来访问 Verifier。不过，模拟器对 Verifier 具有完全的控制权。模拟器可以决定 Verifier 的随机数 ，并给 Verifier 输入任何的 Prover 消息或 。所以，在模拟器的眼里，Verifier 是一个黑盒的确定性算法。
3. 如果模拟器只针对诚实 Verifier，对应的是诚实 Verifier 零知识 (Honest Verifier ZK)。因为诚实 Verifier 的行为是完全在预期中的，模拟器自然可以利用这些信息，因此这个模拟器对 Verifier 的访问是非黑盒的。

非黑盒模拟器访问到的信息更多，所以非黑盒零知识性比黑盒零知识性更容易成立。而诚实 Verifier 零知识是最容易实现的。关于诚实 Verifier 零知识，这里的诚实 Verifier 更准确地说是半诚实 (Semi-Honest) 的，或者说“诚实但好奇的”。这样的 Verifier 表面上会遵守协议，但有可能私下里试图从消息中提取知识。相比之下，恶意 Verifier 的行为是完全不受限制的。Verifier 可能宕机、发送不符合格式的消息、不按协议规定的分布采样，等等。要证明一个系统对恶意的 Verifier 满足零知识性，就要把所有这些情况都覆盖到。模拟器是一个随机算法，它的输出值也是一个随机变量，记为 。零知识性要求  和  这两个随机变量难以区分。不过，“难以区分”这个词也有很多种版本，由此可以推出零知识证明的多种定义：

• 如果两个随机变量的分布是统计不可区分的，也就是它们的统计距离 (Statistical Distance) 可忽略，就称这个证明系统是统计零知识 (Statistically Zero-Knowledge) 的；如果统计距离就是 0，又叫做完美零知识 (Perfect Zero-Knowledge) 的；
• 如果两个随机变量的分布是计算不可区分的，也就是任何多项式时间的随机敌手都无法区分这两个分布，就称这个证明系统是计算零知识 (Computationally Zero-Knowledge)的。

注意到，零知识的定义中，只要求对于正确的陈述 ， 和  的分布难以区分。对于错误的陈述，我们并不关心 Verifier 能够获取什么知识，因为这种情况下 Prover 本身就是不诚实的，没有必要去保护它，或者说，Prover 既然不遵守协议，那我们的协议设计得再好也保护不到它。不过，虽然  是错误的情况下，零知识性对  的分布不做任何假定，但如果输入错误的 采样得到的  被 Verifier 验证通过的概率和  正确的情况下有显著差别的话，我们就可以借此判断  的正确性。这就意味着  只能来自一个平凡的 NP 语言。所以，对于困难的 NP 问题，把错误的  输入给模拟器，得到的  也能够以一样的概率被验证通过。这么一来，零知识性和可靠性岂不是矛盾的？换句话说，对于错误的 ，Prover 为什么不能调用模拟器来欺骗 Verifier？实际上，Prover 不能控制 Verifier，它也就不能为模拟器提供采样  所需要的资源。的确，一个恶意的 Prover 可以去调用模拟器，但是这对它来说没用，因为模拟器输出的  中的  并不是正在与 Prover 交互的 Verifier 的随机数。此外，模拟器输出的  也可能和 Verifier 收到的  不同而导致验证不通过。不过，Prover 调起的模拟器无法获取 Verifier 的随机数，这已经足够保证安全性了，所以交互式证明中  即使是固定常量也没问题。

知识证明

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

知识证明系统通常是用来证明 NP 语言的。一个 NP 语言是指一个集合 ，使得元素  属于 可以由一个证据  来证明，即存在一个多项式时间的算法能够判定  是否是  属于  的合法证据。普通的证明系统使得 Prover 可以向 Verifier 证明 。而知识证明系统使得 Prover 可以向 Verifier 证明的不仅是 ，还可以证明 Prover “知道” 。也就是说，即使 ，如果 Prover 不知道对应的 ，也难以验证通过。和上一节讨论的零知识性类似，“知识性”也需要严格的定义。一个程序 P “知道”数据 ，到底该怎样定义呢？想象一下把这个程序运行在一个虚拟机里，它的随机数是可以由我们随意指定的。它的整个运行过程中，CPU 状态的完整历史记录，以及所有的内存读写操作，都可以由虚拟机记录下来。如果这个程序“知道” ，我们总该从这些记录中提取出  的信息吧。实际上，这就是提取器 (Extractor) 的一种直观的理解方式。提取器就是一个算法，它能够和被提取的程序同时运行，并能够访问到被提取的程序的内部状态。最后，它可以输出提取的结果。上面描述的提取器是非黑盒提取器，因为它可以访问被提取程序的内部状态。非黑盒提取器的算法必然要随着被提取程序的不同而变化。所以，一个证明系统是一个知识证明，是这样定义的：“对于任意 Prover ，存在一个提取器 ，它和  同时执行，并能够访问到  的内部状态。如果  和  交互后  输出 accept，那么  就会输出满足条件的 。”类似于零知识定义中的模拟器，提取器也可以用黑盒的方式定义。提取器无法访问程序的内部状态，但可以调用这个程序，控制这个程序的随机数，并读取这个程序的输出。我们引入这样一个记号 ，表示提取器通过黑盒的方式访问一对 Prover 和 Verifier 的交互过程。黑盒提取器对所有的 Prover 只需要有一个就够了，所以知识性证明就可以如下定义：“存在一个提取器 ，对于任意 Prover ，如果  和  交互后  输出 accept，那么  就会输出满足条件的 。”

简洁性

用  表示一个 NP 语言的实例， 表示  存在语言中的证据。简洁性 (Succinctness) 是指一个证明系统所需的通信量低于  的线性函数。换句话说，Prover 和 Verifier 执行这个证明系统，比 Prover 直接把  发送给 Verifier，还要节省通信带宽。有时候，简洁性还可能要求 Verifier 在证明系统中的计算量要低于验证 。总之，简洁性要求证明系统在效率方面有优势。

我们可能会希望一个简洁证明系统的通信量达到对数级别或更低，即 。然而这样的简洁性要求会带来安全性的损失。因为如果通信量低达对数级别，那么 Prover 的消息组合  所在的整个空间是可以在  时间内穷举的。然而，系统的可靠性要求，对于错误的陈述 ， Prover 不能找到让 Verifier 验证通过的 。假如能够验证通过的  压根不存在，这样确实能够保证可靠性。但这样就可以通过穷举  来判断 的合法性，那么  就不是一个困难问题，这就排除了一般的 NP 语言。如果我们想要一般的 NP 语言的证明系统，我们必须允许即使对于错误的 ，也存在少量的能够验证通过的 。这种情况下，我们只能额外引入一个安全参数 ，将通信量的大小放宽为 ，使得穷举  的复杂度达到 ，这样至少实现了计算意义下的可靠性。同时，通信量相对于  仍然是对数级别的，所以满足了简洁性。综上，对于一般的 NP 语言，(对数级别的) 简洁证明系统只能是论证系统。

非交互性

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

任何 NP 语言都天然具有一个非交互证明协议，也就是 Prover 直接将证据发送给 Verifier，而且这个证明是知识证明。所以，构造一个单纯具有非交互性的证明系统意义不大。非交互性只有和前面讨论的两个性质，即零知识性或简洁性组合起来才有意思。非交互性 + 零知识将零知识性和非交互性结合起来，就有了非交互零知识 (Non-Interactive Zero-Knowledge, NIZK)。我们之前在讨论零知识性时讲到，零知识性之所以和可靠性不矛盾，是因为调用模拟器采样的  中的  大概率和与 Prover 交互的 Verifier 的随机数不同。但是，对于非交互零知识，我们要重新审视一下这个推理过程。在交互证明中，一个随机数为  的 Verifier 能够验证通过的 Prover 消息 ，直接搬到随机数为  的 Verifier 那里就很可能验证不通过了。所以，在交互式证明中， 的正确性不是全局的，而是依赖  的。而在非交互证明中，Prover 没有收到 Verifier 的任何消息，所以 Prover 的计算过程没有用到 Verifier 的随机数 。所以，为了达到证明系统的完整性，诚实的 Prover 输出的 ，对于大部分 Verifier 随机数  都是能验证通过的。所以，非交互证明中的  的正确性是全局的，不依赖任何。零知识性要求，Verifier 的视野  和模拟器的输出  不可区分。这意味着，如果单独观察这它们部分分量，它们也是不可区分的。即  和  中的  也是不可区分的。所以，一个恶意的 Prover 可以调用模拟器来输出 。这在交互式证明中不成问题，恶意的 Prover 仅仅是得到了关于某个  正确的  罢了。但在非交互证明中， 的正确性是不依赖  的，就会带来安全问题。这时候，就要轮到  发挥作用了。虽然  的正确性不再依赖于 ，但还是依赖于 的。为了可靠性，我们希望，给定  和陈述  难以计算出能够通过验证的 。虽然模拟器在给定  时可以同时输出一对 ，但是难以先计算前者再计算后者。具体是怎样做到这一点的，后续文章中介绍具体方案时会详细讲解。非交互性 + 简洁性上文提到，简洁性的证明系统必然是论证系统。结合非交互性，就有了简洁非交互式论证 (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 只有一字之差，但有很多不同。下面我们比较一下这两个概念。共同点：

• 都是知识论证 (ARK)，即只有计算意义下的可靠性，且证明是知识性的

区别：

• SNARK 的 “S” 是简洁性 (Succintness)，而 STARK 的 “S” 是可扩展性 (Scalability)，它在简洁性的基础上还要求 Prover 复杂度至多是拟线性 (Quasi-linear) 的，即 ，而 Setup 的计算复杂度最多是对数的
• 透明性 (Transparent)：STARK 不需要可信第三方 Setup；而 SNARK 没有这个限制
• 非交互性 (Non-Interactivity)：SNARK 一定是非交互的，而 STARK 没有这个限制

可以看出，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/