本系列文章 以非专业的视角介绍零知识相关知识。
I know that I know nothing —— 苏格拉底
相信很多人都听说过零知识证明，但是只有极少数人听说过模拟，然而模拟是理解零知识的关键。
上一篇文章 初识零知识与证明 介绍了一个简单的零知识交互系统：地图三染色问题。那么这个系统真的是零知识的吗？我们为什么要相信这个结论？有证明吗？在 Alice 与 Bob 的对话过程中，如果不零知识，Alice 就被坑了。交互式系统的设计者我需要让 Alice 确信，这个对话确实是零知识的。
如果从直觉主义角度解释，要证明一个交互系统存在信息泄露，只需要指证：第几个比特导致信息泄露即可；但如果要证明不存在信息泄露，要考虑信息流的所有比特，证明 1, 2, 3, 4, 5, ...... 编号的比特都没泄露任何信息。感觉很难= =
# 安全的定义与不可区分性
一个交互式系统就是一个对话，它的零知识需要证明。现代密码学是建立在严格的形式化系统之上。在证明之前，还需要明确安全假设到底有哪些。所谓安全假设，例如
- 一个系统的权限隔离做得无比精确，每一个用户只能看到被授权的信息，但是这基于一个安全假设：管理员账号没有被破解。
- 手机银行软件只能通过短信认证码完成转账功能，这也基于一个安全假设：手机 SIM 卡没有被克隆。
深入地分析每一个我们感觉安全的系统，会发现大量似乎不那么稳固的安全假设。比特币私钥安全吗？比特币账户的安全假设也不少：首先助记词不能让别人知道，手机钱包里保存私钥的加密算法得足够强，密钥派生算法正规，不能忘记助记词，等等等。
脱离安全假设来谈安全都是在耍流氓。一切安全都有前提。只有经过数学证明之后，大家才能够确信这个算法/方案的安全性基于一些非常明确的安全假设。
证明还需要一个东西--安全定义。在多数人的认知系统中，安全就是一个无所不容的框。大家应该好好提醒下自己：谈论安全二字的时候，有没有想过到底什么是安全？怎么算安全？
安全需要有一个数学意义上的严格定义
伟大的科学家香农（Claude Shannon）从信息论的角度给出了一个非常靠谱的安全性定义 [2]：
完美安全
攻击者通过密文获取不到任何有价值的信息，破解的唯一手段就是靠瞎蒙。
这个定义很有趣--通过密文获取不到信息，这就意味着攻击者没有获得任何额外的计算能力，能够帮助以更短的时间来计算出明文。
但是这个定义太完美，以至于使用的加密算法都很难满足这个安全性定义。后来 Goldwasser 与 Micali 等人写了另一篇载入史册的经典《概率加密》[2]。
论文定义了一个称为语义安全的概念。语义安全由完美安全放松了部分要求得到。
语义安全
攻击者通过密文在多项式时间内计算不出来任何有价值的信息。
这个看起来靠谱多了。接下来一个问题就是，怎么理解计算不出来信息这个概念？这是要对信息进行度量，信息的定义又是什么呢？
为此再引入一个概念--不可区分性，用于重新表述加密算法的安全性：假设你是一个攻击者，而我有一个加密算法：
- 你随机产生两段等长的明文，
m1=白日依山尽，黄河入海流，m2=烫烫烫烫烫，烫烫烫烫烫 - 你把这两段明文
m1与m2交给我 - 我随机挑选一个明文进行加密，不告诉你具体哪个，产生一个密文
c - 我把密文
c出示给你看，让你猜这个c究竟是由唐诗加密产生，还是乱码加密产生 - 你如果用一台计算机在多项式时间内破解不了
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。Zlice 没有知识作为输入，也即零知识。除此之外，理想世界与现实世界一模一样。
如果真 Alice 在对话过程泄露了信息，那么你就能立即区分出真假 Alice，Zlice 是不可能伪装泄露信息的。因此可以得出结论：
真 Alice 没有泄露任何信息。
这个神被称为模拟器（Simulator），而在理想世界和你对话的这个 Zlice 幻象其实也是模拟器。理想世界中所有能感知到的东西都是模拟器模拟出来的。
至此，我们用模拟器这个概念对零知识进行了定义。
接下来进入证明零知识的环节。
# 区分两个世界
证明的零知识过程等价于构造一个模拟算法--这个算法能够让模拟器模拟出一个没有知识的理想世界。如果存在使两个世界不可区分的算法，证毕。
且慢，好像哪里不对劲。
假如说真的存在这种算法，而且它能够在没有知识的情况下骗过我，那么在现实世界中，不排除真 Alice 也使用了这样的算法来欺骗我。这样一来，我岂不是在两个世界中都被欺骗了，使得这个交互协议没意义了。
其实这里有个关键点：借用电影《盗梦空间》的剧照，理想世界有点东西是和现实世界本质不同。这个东西是区分两个世界的关键，且无法感知。这个东西不是梦境中的陀螺，它是模拟器所具备的一种超能力。
比如这样一种超能力：时光倒流。
（上图是电影《土拨鼠之日》的剧照，剧中主人公每次睡醒都会回到 2 月 2 日早上，永远活在同一天里）
等等，刚才我们不是一直在讨论不可区分性吗？怎么又要区分两个世界啦？有点懵= =不要慌。所谓的不可区分性针对的是理想世界的个体认知，而可区分性是对位于世界外部的神而言。
设想下在我们周围，如果有一个人有时空穿越能力，或者他能让时间回退到一年前，那么我们这些凡夫俗子完全是一脸茫（meng）然（bi）的，无从感知。如果模拟器可以在他构造出的理想世界实现时间倒流，就可以做到一些神奇的事情，从而骗过作为验证者身份的你，也能骗过观察者我。你知道在理想世界的时间可以倒流，但是现实世界的真 Alice 不可能拥有超能力。虽然无法区分在哪个世界里，但是至少我们知道两个世界中现实世界的 Alice 是没办法欺骗我们的，我们却说不出自己身处在哪个世界。
到此，交互协议的零知识已经证明完了。各位是否已经明白了？再缕缕如下：
首先零知识是为了保护 Alice 的利益，因为 Alice 不想在交互过程透露更多的信息给 Bob，不想让 Bob 知道她所拥有的秘密 w，甚至不想让 Bob 利用交互的过程分析出哪怕一丁点的信息。那么怎么保证这一点呢？模拟器登场--它能模拟出一个和现实世界外表一模一样的理想世界，然后模拟器其中轻松地骗过任何一个对手，让对方无法分辨自己是在现实世界还是理想世界。因为模拟器手里没有那个秘密 w，理想世界是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice 的交互协议是零知识的。
下面看一个具体的例子，上一篇文章 提到的地图三染色问题。
# 地图三染色问题的零知识证明
回忆一下地图三染色问题交互系统：
- Alice 把地图染色答案做一次完全置换，然后将所有顶点盖上纸片，交给 Bob
- Bob 随机挑选一条边
- Alice 打开指定边端点的纸片，Bob 检验两个顶点的颜色是否相同，如果不同则通过，如果相同则失败
- 回到第一步，重复
n遍
接下来证明上述交互是零知识的。这里先假设验证者 Bob 是诚实的，帮助大家理解这个证明过程。然后再讨论 Bob 不诚实情况下的证明方法。
在理想世界中，跟 Bob 对话的是一个模拟器。它模拟出整个世界。Bob 按照三染色问题的交互协议进行交互。模拟器并没有任何三染色答案，所以索性把所有的顶点都染成灰色。
首先，模拟器模仿 Alice ，把每个顶点用纸片盖起来。然后发给 Bob。
Bob 随机挑选了一条边，挑战证明者。
模拟器这时候不能打开纸片，因为这条边两端的颜色都是灰色啊。
这时候，模拟器发挥超能力，运用时间倒流的技能，回到对话第一步之前。
模拟器现在处于第一步，他把最下面那条边的两端染上任意不同的颜色，然后重新盖上纸片，发给 Bob。
Bob 这时候无法感知到时间已经倒退回第一步。对他来说，一切都是新鲜的，他诚实地再次选择了最下面的边。
这时候模拟器就可以放心地打开纸片让 Bob 检查。Bob 很显然会被骗过。然后循环往复，每一次模拟器都能用时间倒流的方式骗过 Bob。
在理想世界中，模拟器没有任何三染色答案的知识，却能骗过 Bob，且从概率上来看，与现实世界中被观察到的交互过程高度地一致（完全一致的概率分布）。因此，以上过程展示了模拟器算法的存在性，也就相当于证明了交互系统的零知识性质。
# 不诚实的 Bob
上述证明过程有一个相当强的假设：每次时间倒流之后，Bob 都会选择同一条边。如果 Bob 每次都会换一条不同的边呢？没关系，如果在模拟器第一次实施时间倒流之后，Bob 又选择了不同的边，那么模拟器可以把颜色打乱之后，再次运行时间倒流。多次时间倒流之后，Bob 极大的概率总会一次选择模拟器进行染色的那条边，然后这时候模拟器才走到第 3 步，打开纸片。
# 阿里巴巴、洞穴与芝麻开门
在网上众多的讲解零知识证明的中文科普文章中，有一个例子流传非常广--阿里巴巴与强盗的故事。可惜地是，这些不同版本的故事都只讲了一半。那么我接下来讲一个不一样的阿里巴巴与四十大盗的故事：
在很久很久以前，在一个叫做巴格达的城市里，住着一个人叫阿里巴巴。每天阿里巴巴会到集市上买东西。有一天，阿里巴巴被一个盗贼抢了钱包，于是他一路追着盗贼到了一个山洞口，然后盗贼就消失了。阿里巴巴发现洞口里面有两条岔路，如下图所示。
阿里巴巴不知道盗贼往哪边跑了，于是他决定去左边岔道看看，很快阿里巴巴就发现这是个死胡同，也不见盗贼踪影。然后他又去右边岔道检查，也是个死胡同，不见盗贼踪影。阿里巴巴自言自语道：该死的盗贼跑哪去了呢？
第二天，阿里巴巴又去集市买东西，这次另一个盗贼抢了他的篮子，然后阿里巴巴追着这个盗贼到了昨天同样的山洞口，然后盗贼又不见了，这一次阿里巴巴决定先去右边岔道看看，没有发现盗贼，然后再去左边看看，也同样不见盗贼。这好奇怪。
第三天，第四天，……，第四十天，同样的故事不断上演--阿里巴巴追着第四十个大盗到了神秘的洞口，盗贼就消失了。阿里巴巴想：这个山洞里面一定有机关，于是他躲在右边岔道的尽头，耐心地等了很长时间，这时一个盗贼跑了进来，走道岔道尽头之后，念了一个咒语芝麻开门。这时候墙壁居然打开了，盗贼跑进去之后，墙壁又合上了。这时候另一个受害者追了进来，找了半天，一无所获。
阿里巴巴随后等他们走了之后，试验了一下这个咒语，果然有效，而且阿里巴巴发现这个墙壁通向左边岔道。后来，阿里巴巴找到了更换咒语的办法，并且把一个新咒语和洞穴的地理位置写在一张羊皮纸上。
注：到这里，故事并没有结束.... （上字幕）很久很久以后
在很多年后到了上世纪 80 年代，阿里巴巴的羊皮纸流落到了几个密码学家手里，他们跑到巴格达，找到了洞穴的位置。尽管过了几个世纪，咒语居然仍然有效，这几个密码学家兴奋地打开墙壁，在两个岔道之间跑来跑去。
一家电视台很快知道了这个奇异事件，一个密码学家 Mick Ali（与密码学家 Micali 发音相似）决定向电视观众展示他知道这个咒语。首先，电视节目主持人把摄像机架在洞口，然后让所有人都在山洞口等待，这时候 Mick Ali 一个人进入山洞，然后主持人抛一个硬币，来决定让 Mick Ali 从哪个岔道跑出来。为了纪念阿里巴巴与四十大盗，Mick Ali 重复了四十遍，每次都成功。
节目非常成功。但很快，另外一个电视台眼红，也想拍一个类似的节目。但是 Mick Ali 因为签了独家协议，没办法参与这个新节目。怎么办呢？第二个电视台的主持人心生一计，他找了一个和 Mick Ali 很像的演员，穿着打扮、姿态和说话口音都模仿 Mick Ali。然后开拍，每次主持人掷硬币后，都让这个演员跑出来，但是很显然，演员并不知道咒语，没办法打开那个墙壁。结果是演员时而成功时而失败--演员很辛苦，重复了将近一百次，才成功四十次。最后这个狡猾的新节目主持人，把录制视频进行了剪辑，只保留了成功的片段，删了错误的片段。然后这个新节目和 Mick Ali 的节目在同一时间，不同频道播出。然后观众们完全无法区分哪个视频是真的，哪个视频是假的。第一个电视台的主持人完全明白 Mick Ali 是真正知道墙壁的咒语的人，但是他却无法把这个事实告诉无辜的观众们。
至此，大家是不是对模拟慢慢有了感觉？这里第二个电视台的主持人通过剪辑视频的方式，而不是时间倒流。他对理想世界，也就是电视播出的内容所在世界进行外部干预，达到了同样的效果。对理想世界而言，这种剪辑本质上就是一种超能力。
这个故事其实来源于一篇论文《如何向你的孩子解释零知识证明》[3]，发表在 1989 年的美密会议上。
# 模拟与图灵机
一谈到超能力，大家有没有觉得这玩意不科学。如果我们无脑地用超能力来解释任何事情，逻辑确实无法自恰（Consistent）。在理想世界中，模拟器是不能随便开挂的。比如模拟器肯定不能直接修改 Bob 的内部状态--Bob 明明验证失败，但是模拟器强硬去把验证结果改为接受，这会导出错误的证明结论：任何的交互系统都是零知识的。
模拟器不是理想世界中全能的上帝
那么模拟器到底可以是什么呢？模拟器其实只是一个图灵机。时间倒流、剪辑录像这类的所谓超能力并不是玄乎的超自然能力，而是图灵机可以实现的功能。计算机专业的朋友们肯定都用过 VMWare 等虚拟机软件。本文讲的模拟器完全可以想象成一个虚拟机软件，它能虚拟出一个计算机环境。这个虚拟环境就是上文说的理想世界。时间倒流如何解释呢？不知道大家有没有用过虚拟机软件的快照功能--虚拟机软件可以把整个虚拟计算机的状态保存下来，在任意时刻都可以重新回到保存快照的位置继续运行。
注：其实所谓时间倒流是计算机的一个基本操作，程序语言理论有一个概念叫做 Continuation。抽象地讲，Continuation 表示从现在开始到未来的计算。Continuation 这是控制流的一个显式抽象，而 goto，call-with-current-continuation，甚至 thread scheduling 都可以看做是操作 Continuation 的操作符。比如采用 call/cc（call-with-current-continuation）就可以轻松地实现回溯功能。保存快照可以理解为保存当前的 Continuation，而回到过去的某一刻则是应用这个 Continuation。
Zlice、Bob 和每一个观察者都是一个个可执行程序。这些程序被拷贝到虚拟机里。Zlice 与 Bob 的会话实际上就是进程间通讯。观察者是挂在 Zlice 与 Bob 进程 IO 上的程序。上文的地图三染色理想世界的诚实 Bob，实际上是 Bob 进程调用了虚拟机的随机数发生器，而这个随机数发生器是能被 Zlice 操纵的。现实世界是外部运行虚拟机软件的计算机环境。
大家是不是又有所悟，我再强调一下：
证明零知识的过程，就是要寻找一个算法，或者更通俗点说，写出一段代码，它运行在外部计算机系统中，但是实现了虚拟机的功能。而且在虚拟机中，需要有一个不带有知识作为输入的 Zlice，可以骗过放入虚拟机运行的 Bob。
如果还没理解上面这句话，请时光回退到区分两个世界小节，重新思考模拟 😛
# 柏拉图的洞穴寓言
模拟无处不在--哥德尔不完备性定理就用了模拟的概念，用哥德尔数（Godel Numbers）模拟了形式算术。图灵提出了可以模拟自身的Universal Turing Machine（通用图灵机）。
但最早的模拟概念，出自《理想国》一书的第 7 卷 [4]：古希腊哲学家柏拉图讲了这么一则寓言——Allegory of Cave：
在一个暗无天日的山洞中，一排囚徒被锁链锁住，从小就只能看到前方的墙壁。这些囚徒们身后是一堵墙，再后面有一堆火，在火与墙壁之间，有一些人举着道具和木偶来回走，这样道具木偶就会在火光映射下在墙壁上投下影子。而这些囚徒们整天就只能看着这些影子。因为这些囚徒们从打出生起，所闻所见就只是前方洞壁上的各种影子，他们会以为所看到的这些影子就是真实的世界。
然而有一天，一个囚徒偶然挣脱锁链，回头看到了火。但是他从小到大仅能看到暗淡的影子，第一次看到了明火、道具和木偶。假如有人告诉他，这些道具和木偶才是实物，他一定会嗤之以鼻，坚持认为影子才是真实的。
柏拉图假设说：如果这个囚徒强制拖出洞穴，到外面去看到真实的世界。一开始囚徒会不适应真实世界的光亮而感到刺目眩晕，会因此而愤怒。但是慢慢适应了这个世界，看到太阳、树木、河流和星空，他逐渐明白这个世界比洞穴那个世界更为优越高级，再也不想回到黑暗的洞穴生活了。
过了一段时间，他对洞穴的囚徒心生怜悯，于是想去把他们都带出来。但是再次返回洞穴时，他因为已经适应了外面明亮的世界，反而看不清楚了。被锁的囚徒们认为他的视力受损，胡言乱语，是个疯子。最后当他想尽办法把这群囚徒带出洞穴时，被囚徒们联手杀死。
这是则人类命运的寓言，就和那一排被锁链禁锢的囚徒类似，我们以为眼睛看到的就是世界真相，但实际上那也许是幻象，就像洞穴墙壁上投下的影子一样。
# 未完待续
本文章介绍了理解零知识所需的关键概念——模拟。任何一个零知识的协议，都可以通过构造一个理想世界来理解。第一次接触这个概念的读者需要反复琢磨。
计算机科学有两个方法论至关重要，第一个是抽象，第二个是模拟
回顾一下在地图三染色问题：Bob 在理想世界与现实世界中的对话。虽然 Bob 无法区分两个世界，但是有一点可以确信：现实世界中 Alice 没有超能力。
问题来了：Alice 没有超能力，并不能直接证明 Alice 真的有答案。万一这个交互协议并不能保证 Alice 一定有知识呢？零知识保护了 Alice 的利益，谁来保证 Bob 的利益呢？请听下回分解。
致谢: 本文受密码学教授 Matthew Green 发表在 2014 年与 2017 年的两篇个人博客文章 [10-11] 启发。
# 参考文献
- [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.
- [10] Matthew Green. Zero Knowledge Proofs: An illustrated prime. 2014. https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
- [11] Matthew Green. Zero Knowledge Proofs: An illustrated primer, Part 2. 2017. https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/