转载探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 六 ) _宇宙知识

看到这里，大家是不是对「模拟」慢慢有了感觉？这里第二个电视台的主持人通过剪辑视频的方式，而不是「时间倒流」。他对「理想世界」，也就是电视中播出的内容所在的世界，进行了外部干预，达到了同样的效果。对理想世界而言，这种剪辑本质上就是一种超能力。
这个故事其实来源于一篇论文『如何向你的孩子解释零知识证明』（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 。

转载 探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 六 )

猜你喜欢

转载探索零知识证明系列 | 从「模拟」理解零知识证明：平行宇宙与时光倒流( 六 )