三个故事为你科普零知识证明

密码学是区块链技术的基石，也随着区块链的发展逐渐成为“显学“。对历史稍做了解的同学，应该知道密码学研究成果在相当长的时间内是被定义为军工产品，列入“出口禁令“名单里面。密码学从私密领域走向公共领域，得从1976年一篇标题大胆的论文发表说起。Diffie和Hellman的《密码学的新方向》横空出世，宣告密码学新范式的出现，掀起一场公钥革命。

2008年Nakamoto Satoshi在密码学邮件组发表了名为《Bitcoin: A Peer-to-Peer Electronic Cash System》的论文，将加密朋克运动带到了一个新的高度，接下来的10年时间，“not your keys, not your coins"变得深入人心。从保护信息安全，到财产安全，晦涩艰深的密码学不仅在信息技术革命的进程中大放异彩，更是越来越和每个人息息相关。以至于Vitalik有次在推特上开玩笑，应该利用基因编辑技术把哈希和椭圆曲线运算预编译进人类的后代的大脑中。

现代密码学如同炼金术，以数学难题和图灵机模型为基础原料，熔铸成为不可思议之物。在上世纪七八十年代的很多学术界，很多密码学论文的题目中都带有impossible(不可能的)、 paradoxical(自相矛盾的)之类的字眼，或许可以一窥那个时代的科学家在发现这门炼金术时的激动的心情。

在这个密码学家的百宝箱中，有一件法器似乎最近风头十足，它就是本文的主角——零知识证明。如何向别人证明一个命题为真，同时又不泄漏任何其他信息呢？这听上去就很“自相矛盾”。

回顾经典证明

从欧几里得时代开始，延续了上千年，证明的基本形态就是以若干定理为基础，加上一定的规则，推导出某些命题的过程。

（*欧式几何的公理基础(+第五公设)*）

一旦一个命题被证明了，它就能够确定且可靠的作为其他理论的基石，而不用担心未来构建的大厦存在致命的缺陷。寻找证明的过程是一场人类智力的奥德赛，比如著名的费马大定理，历经三百余年，才在1995年由英国数学家Andrew Wiles完成第一个证明。

（*证明费马大定理的英国数学家Andrew Wiles*）

比起构造出证明的人来说，验证它似乎要简单很多，前者要付诸更多的心力才能曲径通幽，摘取桂冠。后面我们会发现，这种证明-验证的不对称性有着更普遍的内涵。

既然我们有个这个延续千年的经典证明概念，那是什么促使人们重新思考这个概念本身？

密码学的“功臣”：敌手

密码学是在攻防中成长起来的学科。如果没有敌手(adversary)，没有人窃听、篡改传输的信息，没有人盗窃电子商务的账号，没有人窥探个人隐私——如果这是个理想友善不作恶的世界，我们就不需要密码学家。但很抱歉，我们生活在一个信息传输、存储和使用的各个环节，都可能遭受到攻击的世界上。所有密码学的伟大发明和发现，都来自于那个可敬的敌手。

回到证明本身，传统的证明会给出一个命题(statement)为真所需要的理论推导过程。考虑在有一个敌手的情况下，你给出证明、说服对方命题为真的同时，对方也就获得了证明所需要的知识。

密码学家天生是一个“被害妄想症“患者，证明者提出了一个问题：证明的目的是说服验证者我的断言（claim）是正确的，我能不能不泄漏任何除此之外的信息，也就是所谓的除了合法性外不泄漏任何信息（nothing but validity）呢？验证者刚好也是密码学家，他们能理解同行的想法，但提出另一个问题：你不展示证明本身，我怎么能够确信你没有耍赖作弊呢？

（*claim is cheap, show me your proof!*）

密码学家是非常聪明的人，他们对经典的prove-verify模型进行了升级，增加了随机性和交互两种新的元素，得到了一个能够达到上面目的的一种新的证明系统。下面通过几个直观的例子，获得一些直觉上的启发。

红绿色盲游戏：交互和随机性

这个游戏是这样的，Bob是个红绿色盲，有天Alice拿着一张纸片告诉Bob，上面有红色绿色两种颜色。可能Alice说的是真的，也可能她只是拿着一张全是黄色的纸(假设红绿色盲看到的红绿色也都是黄色)，Bob怎么判断Alice的真假呢？

*红绿色盲游戏展示图*

Bob非常聪明，他想了个办法：

1.他先让Alice把这张纸片放在桌子上，红色在上方，绿色在下方；

2.叫Alice转过面，他抛一个硬币，如果正面朝上，他保持纸片不动，如果反面朝上，他把纸片旋转180度，即变成绿色在上方，红色在下方；

3.叫Alice转过身来，问她现在纸片的颜色，并检查与自己的操作是否一致；

4.重复2到3步n次；

*红绿色盲游戏交互协议*

经过这个协议，如果连续n次Alice都通过了检查，则有1-(1/2)^n的概率可以认为Alice说的是真的，这张纸的确是有红绿两种颜色。这个朴素的协议包含了两个重要的概念：

1.交互(interactive)：不像经典的prove-verify模型，这个证明是prover和verifier之间多次交互完成的；

2.随机(randomness)：Bob通过抛硬币的方式可以得到真的随机数；

另外这个交互协议中，还蕴含这三个性质：

1.如果纸片的确是红绿色，那么Alice一定能够说服Bob这一点，这叫完备性(completeness)；

2.如果纸片是黄色，Alice不管采用什么策略，由于无法提取预测到Bob抛硬币的结果，也会以极大的概率被Bob拒绝，这叫可靠性(soundness)，即Alice没法作弊。这是交互证明系统和经典证明的一个巨大的差异，经典证明是确定性的，交互证明是概率的。奇妙的地方在于，交互证明同样达到了说服验证者的目的，这实际上扩展了证明这个古老概念的内涵。

3.Bob也没有获得任何关于纸片有红绿两种颜色这个论断为真外的其他任何知识(这里比较巧妙的在于Bob本身就是色盲，它无法获得实际关于颜色的信息)，这叫做零知识(zero-knowledge）;

其中完备性和可靠性比较容易证明，但零知识是一个直觉上的感受，想要证明它需要借用模拟器(Simulator)。下面通过另外一个例子介绍下模拟的概念。

阿里巴巴的洞穴：模拟范式

“阿里巴巴和四十大盗”在中国是家喻户晓的故事，中国的互联网巨头阿里巴巴就能看到很多这个古老寓言的痕迹，除了公司名字外，还有芝麻信用(来源于“芝麻开门”的咒语)评分体系。

密码学家Quisquater等在1989年改编了这个故事，名叫《如何向你的孩子解释零知识证明》，用来解释刚在学术界兴起的零知识证明的概念，这个新编故事是这样的：

阿里巴巴是个集市做生意的商人，他的货物经常被小偷顺走，在追小偷的过程，他发现了一个如下图显示的洞穴。洞穴入口有两个分叉，无论从哪个分叉进去，都走到死路(死胡同)。在近四十次的追小偷过程，他都见到小偷进去这个洞穴但不知道是哪个岔口，他每次随机选一个岔口，从来没有抓到过小偷。他想小偷绝对不会每次都那么幸运，选择和自己不同的洞口。果然，最后他发现所谓的终点其实是一扇门，小偷用“芝麻开门”打开它。阿里巴巴抓到了小偷，并且知道这扇门的秘密。

几个世纪后，人们发现阿里巴巴留下的手稿，记录着这个洞穴的故事和关于咒语的线索。人们根据上面的信息，在巴格达找到了这个洞穴，发现居然不是一个传说！有个叫做Mick Ali的学者声称他知道咒语，电视台找到了他拿下了独家报导。但Mick不想透露关于咒语的信息，所以他采用了上面的零知识证明的方式来证明：

电视台的摄像师站在洞口，Mick通过抛硬币随机选择A或者B岔口进去，然后摄像师也抛硬币随机的在洞口喊“从A出来“，”从B出来“。这个实验重复了40 次，Mick每次都能按照要求出来。和红绿色盲游戏一样，他以极大的概率说服了摄影师。这些都被记录下来了，作为节目播放。

*阿里巴巴洞穴展示图：by ReturnValues.Academy*

另一家电视台的记者同样也想报道这个神秘的洞穴，他找到Mick，但Mick已经和前一家电视台签了独家。这个嫉妒的记者非常懊恼，Mick却暗示记者，你不需要咒语也可以拍摄这个节目。记者很聪明一听就明白了，他找了一个和Mick很像的替身，拍了这样的视频：

电视台的摄像师同样站在洞口，替身通过抛硬币随机A或者B岔口进去，摄像师也抛硬币随机的在洞口喊“从A出来“，”从B出来“。但是当替身和摄像师的抛硬币结果不一样时，替身没有咒语不能打开里面的门，也就无法按照要求出来。记者把这些失败的片段剪掉了，完美的留下了完整的40次成功的实验，作为节目的素材。

两家电视台同时播放的这个节目，引起了诉讼，前一家电视台把后一家告到了法院。两段视频作为证据呈交法院，但法官和专家都无法区分二者的区分(不考虑其他的证据、证词)。最终官司不了了之。

Mick Ali达到了他的真实目的，摄影师的确知道他有咒语，但即使有视频，也无法说服其他实验时不在场的人“Mick知道咒语“这件事，因为任何人都可以伪造这个视频。

上面这个例子，就是用来证明一个协议有“零知识”这个性质的基本思路，通过构造一个模拟程序，生成一段记录，与真正的零知识证明协议执行过程验证者看到的记录对比。如果对计算机而言，无法区分二者的差别，则证明了验证者无法从对话过程中，获得任何他自己在家无法获取的信息，除了命题为真外。

旅行中的数学家：非交互和公开验证

第三个小故事，主角是Arthur和Merlin，他们都是数学家，有天Arthur开始出门旅行，并且在旅行路程中思考数学问题。每当他发现一个新的命题，他都会写张明信片给Merlin，同样他不想透露除了命题为真外的其他任何信息。而Merlin能仅仅通过明信片来验证命题真假。

这个小例子，其实反应了前述的零知识证明虽然在理论上很酷，但在实际工程中存在的缺陷：

1. 证明者和验证者之间需要多次的交互，无疑需要很多的通信成本；

2. 每个验证者都需要独立和证明者完成交互协议，才能确认命题的真假，做不到公开可验证。

基本的想法是，寻找可以替代交互证明协议中Merlin随机性的方法，并且防止Arthur能够利用这个随机性作弊。密码学家利用Fiat-Shamir假设，借用单向哈希函数，成功的设计出了非交互零知识证明(Non Interactive Zero Knowledge, NIZK)协议。非交互和公开可验证是ZKP系统能得到广泛应用的重要基础。

上面通过三个小故事，展示了零知识证明的基本思想和重要概念，感兴趣的读者还可以去阅读专业的资料，进一步学习相关理论和技术。

超越理论

ZKP从1985年被提出到今天，已经发展了35年。它第一次从认知上，把证明的正确性和证明的知识解耦开来，这种思想范式的转变蕴含了巨大的创新势能，直到今天仍旧是一个热门的研究领域，新的成果日新月异。下图是一张ZKP家族树，底下是它基于的密码学假设，有些可以追溯到40多年前，但这棵树上大部分的果实都是在最近10年的时间内“长”出来，从实验室走进了工业界。

*zkp family trees: by StarkWare*

它们为当下世界遇到的许多难题提供了美妙的解决方案：

1.核弹头检测：Princeton和MIT的学者使用零知识证明协议设计核弹头验证系统，用于核控制、防核扩散以及核裁军。由于核设施的敏感性，国际检查人员需要高度确认提交的物品的真实性，同时不被许可获取任何信息，使用零知识证明协议恰好能够做到这点。

2.加密货币隐私保护：Zcash使用零知识证明协议zk-SNARKs，为加密货币交易提供隐私保护，能够在区块链上隐藏交易的发送人、接受人、数额的情况下，保证交易的合法性。

3.安全的机器学习：大数据和机器学习推动了新一轮的人工智能浪潮，使用零知识证明及其他密码学工具保证计算的隐私和正确性。

正如这个列表会变得越来越长，零知识证明对人类社会的影响也将会越来越大。理解零知识证明不仅仅是为了更好地理解这项技术，也是更好地理解人类通过自身努力能够拓展的智力边界，而这，也许就是人类能给自己存在的一个proof吧。

作者简介：

胡鹏，区块链行业从业者，隐私计算实验室研究员。毕业于北航计算机专业，过去两年参与设计研发了托管数十亿加密资产的管理平台。信仰技术与理性，坚信区块链会重塑互联网和社会的形态。

参考文章

1.Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291-304

2.Oded Goldreich, Silvio Micali, Avi Wigderson: Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract). FOCS 1986: 174-187

3.Jean-Jacques Quisquater, Myriam Quisquater, Muriel Quisquater, Michaël Quisquater, Louis C. Guillou, Marie Annick Guillou, Gaïd Guillou, Anna Guillou, Gwenolé Guillou, Soazig Guillou, Thomas A. Berson: How to Explain Zero-Knowledge Protocols to Your Children. CRYPTO 1989: 628-631

4.Manuel Blum, Paul Feldman, Silvio Micali: Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). STOC 1988: 103-112

5.Mihir Bellare, Shafi Goldwasser: New Paradigms for Digital Signatures and Message Authentication Based on Non-Interative Zero Knowledge Proofs. CRYPTO 1989: 194-211

6.Yan, Jie, and Alexander Glaser. "Nuclear warhead verification: A review of attribute and template systems." Science & Global Security 23.3 (2015): 157-170.