探索零知识证明系列（二）【转】

作者：郭宇    安比实验室

本文已更新至Github

https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/2/zkp-simu.md

I know that I know nothing  —— 苏格拉底

相信很多人都听说过零知识证明，但是只有极少数人听说过模拟，然而模拟是理解零知识的关键。

我们在第一篇文章『初识「零知识」与「证明」』[1]中介绍了一个简单的零知识交互系统：地图三染色问题。那么这个系统真的是零知识的吗？我们为什么要相信这个结论呢？有证明吗？在  Alice 与 Bob 的对话过程中，如果不零知识，Alice就被坑了。交互式系统的设计者「我」需要让 Alice 确信，这个对话确实是零知识的。

如果从直觉主义角度解释，要证明一个交互系统中存在信息泄露，那么你只需要指证：第几个 bit 导致信息泄露即可；但如果要证明不存在信息泄露，那么你要对着所有信息流中的所有 bit 说，这从1，2，3，4，5，……  编号的 bit 都没泄露任何信息。看官们，这是不是很难？

本文约八千字，略微烧脑。

安全的定义与不可区分性

首先，一个交互式系统，也就是一个对话，它的「零知识」需要证明。毕竟，现代密码学是建立在严格的形式化系统之上。在证明之前，还需要明确「安全假设」到底有哪些。所谓安全假设，比如我们说一个系统的权限隔离做得无比精确，每一个用户只能看到被授权的信息，但是这基于一个安全假设：管理员账号没有被破解。又比如在手机银行软件里，只能通过短信认证码，才能完成转账功能，这也基于一个安全假设：你的手机 SIM 卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统，都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗？比特币账户的安全假设也不少：首先你的助记词不能让别人知道，手机钱包里私钥保存加密算法足够强，密钥派生算法正规，你不能忘记助记词，等等等。

脱离安全假设来谈安全都是在耍流氓。一切安全都有前提的。只有经过数学证明之后，大家才能够确信这个 算法/方案 的安全性基于一些非常明确的「安全假设」。

在证明之前，还缺少一个东西，那就是「安全定义」。在多数人的认知系统中，安全就是一个框，什么都可以往里装。大家应该好好提醒下自己，当谈论安全二字的时候，有没有想过到底什么是安全？怎么算安全？

「安全」需要有一个数学意义上的严格定义

伟大的科学家香农（Claude Shannon）从信息论的角度给出了一个非常靠谱的安全性定义[2]：

完美安全：假设你是一个攻击者，你通过密文获取不到任何有价值的信息，破解的唯一手段就是靠瞎蒙。

大家想一想，这个定义很有趣，通过密文获取不到信息，这就意味着你没有获得任何额外的计算能力，能够帮助让你以更短的时间来计算出明文。

但是这个定义太完美，以至于使用的加密算法都很难满足这个安全性定义。后来 Goldwasser 与 Micali 等人写了另一篇载入史册的经典『概率加密』[2]。

在这篇论文中定义了这样一个概念：语义安全。所谓语义安全在完美安全的定义上放松了些要求。

语义安全：假设你是一个攻击者，你通过密文在多项式时间内计算不出来任何有价值的信息。

好了，这个看起来靠谱多了。接下来一个问题就是，怎么理解「计算不出来信息」这个概念？这看来要对信息进行度量，信息的定义又是什么呢？

我们又引入一个概念——「不可区分性」，来重新表述加密算法的安全性：假设你是一个攻击者，而我有一个加密算法：

1.你随机产生两段等长的明文，m1=「白日依山尽，黄河入海流」，m2=「烫烫烫烫烫，烫烫烫烫烫」

2.你把这两段明文，m1 与 m2 交给我

3.我随机挑选一个明文，不告诉你是哪一个，然后进行加密，产生一个密文 c

4.我把密文 c 出示给你看，让你猜这个c 究竟是由唐诗加密产生，还是乱码加密产生

5.如果你用一台计算机来破解c，在多项式时间内破解不出来，也就是说你没办法区分c的来源，那么就说明加密算法是语义安全的

OK，理解完「不可区分性」，我们再回到「零知识」，如何证明一个交互式系统是「零知识」呢？首先我们要定义下零知识这个概念。

注：不可区分性是概率意义上的不可区分；在学术上，它可以分为「完全不可区分」，「统计不可区分」，还有「计算不可区分」。在本文中，我们暂时不需要理解这些概念的差别。

遇见模拟器

先开个脑洞，设想在平行宇宙中，有两个平行的世界，一个叫做「理想世界」（Ideal World），另一个叫做「现实世界」（Real World）。我们每一个个体可以在两个平行世界中愉快地玩耍，但是两个世界的普通人无法互相感知，也无法互相沟通。

假设「你」是一个很厉害的密码破解者，而且「你」不是普通人，具备在平行宇宙之间穿梭的能力。而 Alice 有一个地图三染色的答案，你的目的是通过和 Alice 对话来获取地图三染色的答案，会话的过程参考上一篇文章的「地图三染色问题」协议。

继续脑洞，Alice 只存在「现实世界」中；在「理想世界」，Alice 被「替换」成了一个长相与声音一模一样的个体，我们称替身为 Zlice。下一步，把「你」同时放入两个世界中，但不让你知道是你当前位于哪一个世界。你的两个分身所面对的都是一个 “Alice”模样的人。

再重复一遍，在「现实世界」中， 与你对话的是一个真实的，并且诚实的 Alice；而在「理想世界」中，与你对话的是  Zlice （假 Alice），Zlice 虽然相貌语言与 Alice 并无二致，但差异是，Zlice 并不知道「知识」，即不知道一个三染色问题的答案。

接下来在这两个世界中，你的两个分身将同时与真假 Alice 进行对话。神奇的事情发生了，最终在两个世界中，你的两个分身都被说服了，都经过n轮挑战，没有发现对方作弊，即「你」的两个分身都认为对方确实知道「答案」。换句话说，「你」没有能力「区分」出来自己到底在 「现实世界」 还是 「理想世界」，当然也没能力「区分」和自己对话的究竟是 Alice 还是 Zlice。不仅如此，对于吃瓜群众我而言，如果把「我」作为观察者放入任何一个世界中，我会和你一样「无法区分」出来眼前的 这个长相为 “Alice” 的人到底是真还是假。

下面是烧脑结论：

这个交互系统为何是「零知识」？因为 Zlice 是没有任何知识，而且她和 Alice 不可区分。

我再换个方式解释：因为你和我都没办法区分我们究竟是在哪个世界中，两个世界发生的交互过程几乎不可区分，而且其中一个世界中根本就不存在知识，因此，我们说这个交互协议——「地图三染色问题」是「零知识的」。

这里还有个前提，理想世界必须是算法可构造的。然后，有一个「神」，他通过算法「模拟」了一个「理想世界」，其中构造了一个算法叫做 Zlice，她没有「知识」作为输入，也即「零知识」；除此之外，「理想世界」与「现实世界」一模一样。

设想你在对话过程中，如果真 Alice 泄露了信息，那么你就能立即区分出面前这个人是 真 Alice 还是 Zlice，Zlice 是不可能伪装泄露信息的。因此可以得出结论：

真Alice 没有泄露任何信息。

这个神，被称为「模拟器」（Simulator），而在理想世界中，和你对话的这个 Zlice 幻象其实也是「模拟器」，你在理想世界中，所有能感知到的东西都是模拟器「模拟」出来的。

好了，到这里，我们用「模拟器」这个概念对「零知识」进行了定义。

接下来，我们开始进入证明零知识的环节。

区分两个世界

（Save World State as Snapshot X）

证明的零知识过程，等价于构造（寻找）一个「模拟」算法，这个算法能够让模拟器来模拟出一个「没有知识」的理想世界。如果这个算法存在，而且两个世界不可区分，那么就证明完毕。

等等，可能「你」会觉得哪里不对劲。

假如说真的存在这种算法，而且它能够在没有知识的情况下骗过我，那么在「现实世界」中，不排除真  Alice 也使用了这样的算法来欺骗我。这样一来，我岂不是在两个世界中都被欺骗了。那么这个交互协议就失去意义了。

其实，这里有个关键点，借用电影『盗梦空间』中的剧照，在「理想世界」中有点东西是和「现实世界」本质不同的。这个东西是区分两个世界的关键，而它要让我们「无法感知」。这个东西不是梦境中的陀螺，它是一种「超能力」，模拟器 Simulator 所具备的超能力。

比如这样一种超能力：「时光倒流」。

（上图是电影『土拨鼠之日』的剧照，剧中主人公每次睡醒都会回到2月2日的早上，这样他永远活在同一天里）

等等，各位看官，不是刚才我们一直在讨论不可区分性吗？怎么两个世界又需要区分啦？“我糊涂了”。不要慌，所谓的不可区分性针对的是理想世界中的个体认知而言。而「可区分性」是对位于世界外部的神而言。

设想下在我们周围，如果有一个人有时空穿越能力，或者他能让时间回退到一年前，那么我们这些凡夫俗子完全是一脸茫（meng）然（bi）的，无从感知。那么，如果「模拟器」可以在他构造出的「理想世界」中实现「时间倒流」，那么他就可以达成一些神奇的事情，从而骗过作为验证者身份的「你」，也能骗过观察者「我」。对于「你」而言，你明白，在「理想世界」中，时间是可以回退的，但是在「现实世界」中，显然真 Alice 不可能拥有超能力。虽然你和我不能区分在哪个世界里，但是至少我们知道在两个世界中的其中「现实世界」里，对面那个Alice是没办法欺骗我们的，当然我们却不能说出我们到底在哪个世界中。

到此，交互协议的「零知识」已经证明完了。各位是否已经明白了？我再给大家再梳理下证明思路：

首先「零知识」是为了保护 Alice 的利益，因为 Alice 不想在交互过程中透露更多的信息给 Bob，不想让 Bob 知道她所拥有的秘密 w，甚至不想让 Bob 从交互的过程中分析出哪怕一丁点的信息。那么怎么保证这一点呢？「模拟器」这时候登场了，它能模拟出一个和现实世界外表一模一样的「理想世界」，然后「模拟器」在这个世界中可以轻松地骗过任何一个对手，让对方无法分辨自己是在现实世界中，还是理想世界中。因为「模拟器」手里没有那个秘密 w，「理想世界」是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice 的交互协议是「零知识」的。

我们来看一个具体的例子，上一篇文章[1]中提到的地图3染色问题。

地图三染色问题的零知识证明

回忆一下「地图三染色问题交互系统」：

第一步：Alice 把地图染色答案做一次完全置换，然后将所有顶点盖上纸片，交给 Bob

第二步：Bob 随机挑选一条边

第三步： Alice 打开指定边的两端顶点的纸片，Bob检验两个顶点的颜色是否相同，如果不同则通过，如果相同则失败

回到第一步，重复 n 遍

我们接下来就来证明上述这个交互是零知识的，这里先假设验证者 Bob 是诚实的，这有助于大家理解这个证明过程。然后我们再讨论，如果 Bob 不诚实的证明方法。

在「理想世界」中，跟 Bob 对话的是一个「模拟器」，它模拟出了整个世界的样子。Bob 按照三染色问题的交互协议进行交互。模拟器并没有一个三染色答案，它索性把所有的顶点都染成了灰色。

首先，模拟器模仿 Alice ，把每个顶点用纸片盖起来。然后发给 Bob。

Bob 随机挑选了一条边，挑战证明者。

模拟器这时候不能打开纸片，因为这条边两端的颜色都是灰色啊。

这时候，模拟器要发挥「超能力」了，他运用时间倒流的技能，回到对话第一步之前。

模拟器现在处于第一步，他把最下面那条边的两端染上任意不同的颜色，然后重新盖上纸片，并发给 Bob。

Bob 这时候无法感知到时间已经倒退回第一步了，对他来说，一切都是新鲜的，他「诚实」地再次选择了最下面的边。

这时候模拟器就可以放心地打开纸片，让 Bob 检查。Bob 很显然会被骗过。然后 Bob 一轮轮地重复这个过程，每一次模拟器都能用时间倒流的方式骗过 Bob。

于是在理想世界中，模拟器并没有任何三染色答案的「知识」，却同样能骗过Bob，并且从概率上来看，与「现实世界」中被观察到的交互过程高度地一致（完全一致的概率分布）。于是上面的过程展示了模拟器的算法的存在性，也就相当于证明了交互系统的「零知识性质」。

不诚实的 Bob

在上面的证明过程中，有一个相当强的假设，就是每次时间倒流之后，Bob都会选择同一条边。如果 Bob 每次都会换一条不同的边呢？没关系，如果在模拟器第一次实施时间倒流之后，Bob又选择了不同的边，那么模拟器可以把颜色打乱之后，再次运行时间倒流，在多次时间倒流之后，Bob 极大的概率总会一次选择模拟器进行染色的那条边，然后这时候模拟器才走到第三步，打开纸片。

阿里巴巴、洞穴与芝麻开门

在网上众多的讲解「零知识证明」的中文科普文章中，有一个例子流传非常广，这就是阿里巴巴与强盗的故事。可惜地是，这些不同版本的故事都只讲了一半。那么我接下来讲一个不一样的「阿里巴巴」与「四十大盗」的故事：

在很久很久以前，在一个叫做巴格达的城市里，住着一个人叫阿里巴巴。每天阿里巴巴会到集市上买东西。

有一天，阿里巴巴被一个盗贼抢了钱包，于是他一路追着盗贼到了一个山洞口，然后盗贼就消失了。阿里巴巴发现洞口里面有两条岔路，如下图所示。

阿里巴巴不知道盗贼往哪边跑了，于是他决定去「左边」岔道看看，很快阿里巴巴就发现这是个死胡同，也不见盗贼踪影。然后他又去「右边」岔道检查，也是个死胡同，不见盗贼踪影。阿里巴巴自言自语道：「该死的盗贼跑哪去了呢？」

第二天，阿里巴巴又去集市买东西，这次另一个盗贼抢了他的篮子，然后阿里巴巴追着这个盗贼到了昨天同样的山洞口，然后盗贼又不见了，这一次阿里巴巴决定先去「右边」岔道看看，没有发现盗贼，然后再去左边看看，也同样不见盗贼。这好奇怪。

第三天，第四天，……，第四十天，同样的故事上演，阿里巴巴追着第四十个大盗到了神秘的洞口，盗贼就消失了。阿里巴巴想，这个山洞里面一定有机关，于是他躲在「右边」岔道的尽头，耐心地等了很长时间，这时一个盗贼跑了进来，走道岔道尽头之后，念了一个咒语「芝麻开门」。这时候墙壁居然打开了，盗贼跑进去之后，然后墙壁又合上了，这时候另一个受害者追了进来，找了半天，一无所获。

阿里巴巴随后等他们走了之后，试验了一下这个咒语，果然非常有效，而且阿里巴巴发现这个墙壁通向「左边」岔道。后来，阿里巴巴找到了更换咒语的办法，并且把一个新咒语和洞穴的地理位置写在了一张羊皮纸上。

注：到这里，故事并没有结束.... （上字幕）很久很久以后

在很多年后，到了80年代，阿里巴巴的羊皮纸流落到了几个密码学家手里，他们跑到巴格达，找到了洞穴的位置，尽管过了几个世纪，咒语居然仍然有效，这几个密码学家兴奋地打开墙壁，在两个岔道之间跑来跑去。

一家电视台很快知道了这个奇异事件，一个密码学家 Mick Ali（与密码学家 Micali 发音相似）决定向电视观众展示他知道这个咒语，首先，电视节目主持人把摄像机架在洞口，然后让所有人都在山洞口等待，这时候 Mick Ali一个人进入到山洞中，然后主持人抛一个硬币，来决定让 Mick Ali 从哪个岔道跑出来。为了纪念阿里巴巴与四十大盗，Mick Ali 重复了四十遍每次都成功。

节目非常成功。但很快，另外一个电视台眼红，也想拍一个类似的节目，但是Mick Ali 因为签了独家协议，没办法参与这个新节目。怎么办呢？第二个电视台的主持人心生一计，他找了一个和 Mick Ali 很像的演员，穿着打扮、姿态和说话口音都模仿 Mick Ali。然后他们开拍了，每次主持人掷硬币后，都让这个演员跑出来，但是很显然，演员并不知道咒语，没办法打开那个墙壁。于是有时候演员碰巧会成功，有时候则会失败，于是演员很辛苦，重复了将近一百次，才成功了四十次。最后这个狡猾的新节目主持人，把录制视频进行了剪辑，只保留了成功的片段，错误的片段都删除了。然后这个新节目和 Mick Ali 的节目在同一时间，不同频道播出。然后观众们完全无法区分哪个视频是真的，哪个视频是假的。第一个电视台的主持人完全明白 Mick Ali 是真正知道墙壁的咒语的人，但是他却不能把这个事实传递给无辜的观众们。

看到这里，大家是不是对「模拟」慢慢有了感觉？这里第二个电视台的主持人通过剪辑视频的方式，而不是「时间倒流」。他对「理想世界」，也就是电视中播出的内容所在的世界，进行了外部干预，达到了同样的效果。对理想世界而言，这种剪辑本质上就是一种超能力。

这个故事其实来源于一篇论文『如何向你的孩子解释零知识证明』（How to Explain Zero-Knowledge Protocols to Your Children）[3]，发表在1989年的美密会议上。

模拟与图灵机

一谈到超能力，大家有没有觉得这玩意不科学。是的，如果我们无脑地用「超能力」来解释任何事情，那么我们逻辑就无法自恰（Consistent）。在理想世界中，模拟器是不能随便开挂的，比如模拟器肯定不能直接修改 Bob 的内部状态，比如 Bob 在验证步骤明明验证失败，但是模拟器强硬去把验证结果改为「接受」，这会导致我们可以证明：「任何的交互系统都是零知识的」，这个错误结论。

模拟器不是理想世界中全能的上帝

那么模拟器到底可以是什么呢？模拟器其实只是一个图灵机。所谓的「时间倒流」，「剪辑录像」这类的所谓超能力并不是玄乎的超自然能力，而是图灵机可以实现的功能。计算机专业的朋友们肯定都用过 VMWare，虚拟机之类的软件，本文讲的「模拟器」完全可以想象成一个「虚拟机」软件，它能虚拟出一个计算机环境，这个虚拟环境就是我们上文说的「理想世界」。「时间倒流」如何解释呢？不知道大家有没有用过虚拟机软件的「快照」功能（Snapshot），使用快照的时候，虚拟机软件可以把整个虚拟计算机的所有状态保存下来，然后在任意时刻，虚拟机软件都可以重新回到保存快照的位置继续运行。

注：其实所谓时间倒流是计算机中的一个基本操作，在程序语言理论中有一个概念叫做 Continuation。抽象地讲，Continuation 表示从现在开始到未来的计算。Continuation这是控制流的一个显式抽象，而 goto，call-with-current-continuation，甚至 thread scheduling  都可以看做是操作 Continuation 的操作符。比如采用call/cc，也就是call-with-current-continuation 就可以轻松地实现「回溯」功能。保存快照可以理解为保存当前的 Continuation，而回到过去的某一刻，就是应用这个Continuation。

不管 Zlice 还是 Bob，还有我们的每一个观察者，都是一个个可执行程序。这些程序被拷贝到了虚拟机里。Zlice 与 Bob 的会话实际上就是这两个程序之间的通讯。观察者是 Hook 在 Zlice 与 Bob 进程 IO 上的程序。在上文的地图三染色「理想世界」的诚实 Bob，实际上是 Bob 进程调用了虚拟机的「随机数发生器」，而这个随机数发生器是能被 Zlice 操纵的。「现实世界」是外部运行虚拟机软件的计算机环境。

大家是不是又有所悟，我再强调一下：

证明零知识的过程，就是要寻找一个算法，或者更通俗点说，写出一段代码，它运行在外部计算机系统中，但是实现了虚拟机的功能。而且在虚拟机中，需要有一个不带有「知识」作为输入的 Zlice，可以骗过放入虚拟机运行的 Bob。

如果还没理解上面我这句话，请时光回退到『区分两个世界』这一小节，重新思考模拟。:P （Load World State from Snapshot X）

柏拉图的洞穴寓言

模拟无处不在，哥德尔不完备性定理就使用了模拟的概念，用哥德尔数（Godel Numbers）模拟了形式算术。图灵提出了「Universal Turing Machine」（通用图灵机）的概念，这种图灵机可以模拟自身。

但最早的「模拟」概念，出自『理想国』一书的第七卷[4]中，古希腊哲学家柏拉图讲了这么一则寓言——Allegory of Cave：

设想在一个暗无天日的山洞中，有一排被锁链锁住的囚徒，他们从小就只能看到前方的墙壁。这些囚徒们身后是一堵墙，再后面有一堆放着火，在火与墙壁之间，有一些人举着道具和木偶来回走，这样道具木偶就会在火光映射下在墙壁上投下影子。而这些囚徒们整天就只能看着这些影子。因为这些囚徒们从打出生起，所闻所见就只是前方洞壁上的各种影子，他们会以为所看到的这些影子就是真实的世界。

然而有一天，一个囚徒偶然挣脱锁链，他回头看到了火。但是他从小到大仅能看到暗淡的影子，他第一次看到了明亮的火光。看到了道具和木偶，假如有人告诉他，这些道具和木偶才是实物，他一定会嗤之以鼻，会坚持认为影子才是真实的。

柏拉图假设说，如果把这个囚徒强制拖出洞穴，到外面去看到真实的世界， 一开始囚徒会不适应真实世界的光亮而感到刺目眩晕，他会因此而愤怒。 但是当他慢慢适应了这个世界，看到太阳，树木，河流，看到星空，他逐渐明白，这个世界比洞穴中那个世界更为优越高级。他再也不想回到黑暗的洞穴生活中了。

过了一段时间，他对洞穴中的囚徒心生怜悯，于是想去把他们都带出来。但是当他再次返回洞穴中，他因为已经适应了外面明亮的世界，回到洞穴中反而看不清楚。被锁的囚徒们反而认为他的视力受损，胡言乱语，是个疯子，最后当他想尽办法把这群囚徒带出洞穴时，被囚徒们联手杀死。

这是则人类命运的寓言，就和那一排被锁链锁着的囚徒类似， 我们以为眼睛看到的就是世界的真相,但实际上，那也许是幻象，就像洞穴墙壁上投下的影子一样。

未完待续

本文章介绍了理解零知识所需的关键概念——模拟。任何一个零知识的协议，都可以通过构造一个「理想世界」来理解。第一次接触这个概念的读者需要反复琢磨。

计算机科学中有两个方法论至关重要，第一个是「抽象」，第二个是「模拟」

回顾一下在地图三染色问题中，Bob 在「理想世界」与「现实世界」中的对话。虽然 Bob 无法区分两个世界，但是有一点，他可以确信：现实世界中，Alice 没有超能力。

问题来了，Alice 没有超能力，并不能直接证明 Alice 真的有答案。万一这个交互协议并不能保证 Alice 一定有知识呢？「零知识」保护了 Alice 的利益，谁来保证 Bob 的利益呢？这个问题留给下一篇。

参考文献

[1] 初识「零知识」与「证明」. 安比实验室. 2019.

[2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.

[3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.

[4] 柏拉图 and 吴献书, 1986. 理想国 (Vol. 1, No. 986, p. 1). 商务印书馆.

[5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.

[6] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

[7] Rackoff, Charles, and Daniel R. Simon. "Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.

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

[9] zkPoD: 区块链，零知识证明与形式化验证，实现无中介、零信任的公平交易. 安比实验室. 2019