Numen｜零知识证明引论Part1

导语 

零知识证明（Zero-Knowledge Proof, ZKP）是由S.Goldwasser、 S.Micali 及 C.Rackoff 在1985年首次提出。在2022年凭借ZK-Rollups迅速崛起，成为以太坊扩容的重要工具。 ZKP在其数学本质上是为了解决在隐藏命题知识的情况下讨论命题正确性的问题。可以应用在各类需要隐私安全的场景，在不泄露隐私信息的情况下，进行自我身份、权益的认证。其本身属于隐私安全范畴，在与区块链的结合中，也主要用于隐私交易（zcash、tornado.cash）等，但是当Web3这一概念提出后，ZKP对于分散数据的验证、多链互操作交易及layer2交易的验证方面，有着显著的压缩和验证效率，其应用场景已经不再局限于隐私安全领域，而是成为Web3的技术基石之一。 

Numen将推出零知识证明引论系列文章，共6个部分，深入浅出的介绍零知识证明产生的背景，常见算法模型，协议以及应用等，帮助大家更好的了解零知识证明。本文是零知识证明引论系列的第一部分，主要介绍零知识证明的产生背景，定义以及相关概念。

0、前言 

2021年，阿贝尔奖由两位数学和计算机领域大佬共享：一位是匈牙利数学家拉兹洛·洛瓦兹（László Lovász）,一位是以色列计算机科学家阿维·威格森（Avi Wigderson）。

拉兹洛·洛瓦兹主要贡献：LLL算法（与Lenstra兄弟）；图论（填色问题） 

阿维·威格森主要贡献： 

1）证明“如果使用了随机性的算法看起来很高效，那么必定存在另一种同样高效的非随机算法”； 

2）证明本质上所有NP问题都可以改写成一个允许被 “零知识证明” 化的版本[1]。 

威格森的研究为“零知识证明”的通用性奠定了理论基础。 

零知识证明最早由S.Goldwasser、 S.Micali及C.Rackoff在1985年首次提出[2]。然而在91年奠定理论基础后，直到2010年才开始走上快速发展的道路，这是为什么呢？ 

零知识证明最早只是一些数学玩具，没有应用场景，也没有形成方法论。直到区块链的出现为其提供了应用场景，以及牛人Groth出现提供了一套方法论。 

1、通俗的理解零知识证明 

官方定义：零知识证明的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifier）相信某个论断是正确的。 

例子1：盲人验球 

Alice是色盲，Bob不是色盲，Alice有两个大小，形状完全一样的球，但这两个球的颜色不一样，Bob需要向Alice证明这两个球是不一样的。在这里，Alice被称为验证者（verifier），他需要验证Bob的陈述正确与否，Bob被称为证明者（prover），他需要证明自己的陈述（存在两个颜色不一样的球）。 

图片来源：https://medium.com/m/global-identity-2?redirectUrl=https%3A%2F%2Fblog.goodaudience.com%2Funderstanding-zero-knowledge-proofs-through-simple-examples-df673f796d99

例子2：数独游戏 

所谓数独是这样一种游戏，玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3×3）的数字均含 1 到 9，且不重复。 

有一天 Alice 设计了一道巨难的数独题目来考 Bob ，Bob 苦思冥想了几天也做不出，便向 Alice 抱怨这肯定是道无解的题目。Alice 需要证明这道题有解，但又不能告知其正确答案。 

Alice 拿出81张卡片，按照题目的答案排列好。将答案卡片的数字面朝下、题目卡片的数字面朝上，都放在桌上，并组成了 9×9 的卡片矩阵。

由 Bob 随机选择行、列或是粗线宫中的一种进行验证，假如选择行，则将这 81 张卡片按 9 行分别放到 9 个麻布袋中，摇匀并确保卡片次序打乱。 

验证： 

现在考虑这样一种情况：这道数独题是一个公开征集的有奖数独题，如何向公众证明这道题有解呢？Alice无法和每个公众都交互，而如果只和Bob交互，别人会觉得Alice和Bob是串通好的。 

这种情况，我们需要制造一台具有可信设置的自动验证机。Alice 只需要提交一次卡片，这台机器就可以按照初始设置好的验证序列，自动化的对这些卡片进行重复验证。验证从交互式的，变成了非交互式的。此时，随机点不由验证者给出，而是由一个可信的第三方在初始化阶段就给出，这样一来，证明者就可以直接给出证明，验证者只需要验证证明即可，验证者和证明者之间不再需要交互。 

例子3：三色图 

四色定理：任何的平面图，都可以使用四种颜色染色，使得相邻的区域颜色不同 

如果我们使用三种颜色，那就不是每个图都好使了。 

当Alice应Bob的委托好容易找出一个三色图问题的答案时，如何向Bob证明她知道答案而不透露着色方案呢？步骤如下： 

1. Alice把问题图中已经正确上色的节点都遮起来； 

2. Bob从中任意选相邻的两个节点，Alice便向其展示这两个节点的颜色。如果这两个节点的颜色不同，那么Bob便有50%的把握相信Anna确实知道答案； 

3. 接着，Alice随机选择一种颜色映射方案将目前图中的颜色变换成另一种颜色，例如“紫色->白色，橙色->黄色，绿色->黑色”，这样便生成了一张新的上色图。虽然颜色不同，但仍是原问题的有效解。接着重复第1-3步N次，如果每次展示的两个节点颜色都不相同，那么Alice知道答案的可靠性便是1-(0.5)^N。 

一个演示：http://web.mit.edu/~ezyang/Public/graph/svg.html 

2、零知识证明的几个概念 

证明：一个证明系统 (Proof System) 是一个交互式协议，包含两个参与方 Prover 和 Verifier，以及一个算法 Setup。证明系统的作用是让 Prover 说服 Verifier 相信一件事，我们把这件事叫做一个陈述 (Statement)。
协议开始前，需要先进行 Setup 。Setup 接受一些公共参数作为输入，并输出 Prover 和 Verifier 所需的 Setup 信息，其中 Verifier 获知的信息记为 Setup_V，Prover 获知的信息记为Setup_P。Setup_V和Setup_P的公共部分称为公共参考字符串 (Common Reference String, CRS)，也就是俗称的Trusted Setup。

Setup 信息获取的时间取决于证明系统的设计。例如，有可能是 Prover 和 Verifier 早就下载好存在各自硬盘里可以反复使用的，也可能是协议开始前当场输入的。

以多项式方程 x²+2x+1=9 为例，Alice(Prover)知道解2，如果Bob是Verifier，那么该证明系统中Prover的Statement是 x=2  , CRS是 x²+2x+1=9，Setup_V是乘法和加法运算，Setup_P是二元一次方程求解算法。

证明系统的性质：一个证明系统需要满足以下两条性质

•完备性 (Completeness)：诚实的Prover最后会让Verifier相信这个Statement。（真的假不了）

•可靠性 (Soundness)：只有Statement是真的时候，才能让Verifier相信。（假的真不了）

零知识：在Statement是正确的情况下，如果除了 Statement 的正确性，Verifier 无法从交互中获取任何其他“知识”，就称这个系统是零知识的。

在上例中， x=2 就是一个知识，如果Alice能够在不传递 x=2且不让Bob可以推出 x=2的情况下，让Bob可以验证“Alice知道这个方程的解”这一Statement，那么这个证明系统就是零知识的。

关于零知识，在数学上有严格的定义，大概是下面这样的：

一个交互式证明是零知识的，那么存在一个simulator（具备rewind能力），使得V与真正的P交互产生的证明副本的整体分布（ensemble distribution）和与一个simulator交互产生的证明副本的整体分布等价。 

模拟器没有知识，但是它可以通过时光倒流，提前得知V的挑战题目，然后构造出挑战题目的答案，而这个答案不需要原问题的知识，却与P给出的答案概率分布一致，则证明交互过程零知识。 

关于模拟器更通俗的详细解释: https://secbit.io/blog/2019/08/06/understand-zero-knowledge-proof-by-simulator/

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

交互： 

非交互： 

好处是1）减少交互 2）公开验证 

简洁性：零知识协议的交互数据量<原证明系统数据交互量 。

本篇文章介绍了对零知识证明的通俗理解和基本概念，希望读者能够对零知识证明有个大概的理解。下篇文章，我们将对零知识证明中的基本数据工具做一个介绍，为读者深入理解零知识证明打个基础 。

参考文献 

[1] Oded Goldreich , Silvio Micali ,Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM. 1991, 38 (3): 690–728. 

[2] Shafi Goldwasser, Silvio Micali,  CharlesRackoff. The Knowledge Complexity of Interactive Proof System. Siam Journal on Computing, 1989, 18(1):186-208. 

原文始发于微信公众号（Numen Cyber Labs）：Numen｜零知识证明引论Part1