Skip to main content
  1. Posts/

如何向你的孩子讲述零知识证明

·1 min·
零知识证明
Tech Enthusiast running out of Coffee.

知道吧,我的孩子们,在很久很久以前的东方城市巴格达,住着一个叫阿里巴巴的老人。每天,阿里巴巴都会去市集买卖东西。这是一个关于阿里巴巴的故事,同时也是关于一个洞穴的故事,一个奇怪的洞穴,它的秘密和奇迹至今仍然存在。但我提前说得太多了…

在巴格达市集的一天,一个窃贼从阿里巴巴那里抢走了一个钱包,阿里巴巴立刻开始追赶他。窃贼逃进了一个洞穴,洞口分成两条黑暗曲折的通道:一条向左,另一条向右(洞穴的入口)。

阿里巴巴没有看清窃贼逃进哪条通道。阿里巴巴不得不选择要走哪条路,他决定选择左边的通道。左边的通道最终是个死胡同。阿里巴巴从分岔口一直搜寻到死胡同,但他没有找到窃贼。阿里巴巴对自己说,窃贼也许在另一条通道里。于是他搜寻右边的通道,但也是到了一个死胡同。然而,他再次没有找到窃贼。“这个洞穴真奇怪,“阿里巴巴自言自语道,“我的窃贼去哪里了呢?”

第二天,另一个窃贼抢走了阿里巴巴的篮子,并像第一个窃贼一样逃进了那个奇怪的洞穴。阿里巴巴追赶他,但再次没有看清窃贼逃走的方向。这次,阿里巴巴决定向右搜索。他一直走到右边通道的尽头,但没有找到窃贼。他对自己说,和第一个窃贼一样,第二个窃贼也很幸运地选择了阿里巴巴没有搜索的通道。这无疑让窃贼再次逃离并悄然融入拥挤的市集中。

日子一天天过去,每一天都有窃贼出现。阿里巴巴总是追赶着窃贼,但他从未捉住过任何一个。在第四十天,第四十个窃贼抢走了阿里巴巴的头巾,像之前的三十九个窃贼一样,逃进了那个奇怪的洞穴。阿里巴巴再次没有看清窃贼逃走的方向。这次,阿里巴巴决定搜寻左边的通道,但他再次没有在通道尽头找到窃贼。阿里巴巴感到非常困惑。

他本可以像之前那样对自己说,第四十个窃贼和其他三十九个窃贼一样幸运。但这种解释太牵强了,甚至连阿里巴巴自己都不相信。四十个窃贼的运气实在是太好了,不可能只是凭借偶然。在一百万亿次中,只有一次机会所有的四十个窃贼都能逃脱!因此,阿里巴巴对自己说,一定有另一个更有可能的解释。他开始怀疑这个奇怪的洞穴守护着一个秘密!

阿里巴巴决定去揭开这个奇怪洞穴的秘密。他决定躲在右边通道尽头的一些麻袋下。在非常不舒服的等待之后,他看到一个窃贼来了,窃贼感觉到自己被追捕,低声念出了魔法词句:“开门西米。”阿里巴巴惊讶地看到洞穴的墙壁滑动开了。窃贼穿过开口逃走了,然后墙壁又滑动闭合了。追捕者赶到,却惊讶地发现只有阿里巴巴躲在通道死胡同的麻袋下。窃贼逃脱了。但阿里巴巴很高兴,因为他正在揭开这个奇怪洞穴的秘密。

阿里巴巴开始试验这个魔法词句。令他惊讶的是,当墙壁滑动开时,右边通道与左边通道相连。现在阿里巴巴知道了所有四十个窃贼是如何从他眼前逃脱的。

阿里巴巴不断尝试着使用这个魔法词句,最终成功地将其替换为新的魔法词句,有点像你更改一些挂锁的组合密码。第二天,一个窃贼被捕了。阿里巴巴将这个故事和他的发现记录在一本精美的彩绘手稿中。他没有写下新的魔法词句,但他在手稿中留下了一些微妙的线索。

阿里巴巴的精美彩绘手稿在中世纪抵达了意大利。如今,它位于美国的波士顿附近。最近,这本手稿吸引了几位好奇的研究人员的全神贯注。通过解密这些微妙线索,这些研究人员甚至成功找回了新的魔法词句!

在旧巴格达市集的废墟中进行了几次考古发掘后,奇怪的洞穴被找到了。它并非神话!尽管经历了几个世纪,魔法词句仍然有效。好奇的研究人员激动不已,穿过了连接两个通道的尽头墙壁。

电视网络迅速得知了在巴格达发生的不寻常事件。甚至有一家美国大型电视网络独家报道了这个故事。其中一位研究人员,名叫米克·阿里(Mick Ali),可能是阿里巴巴的后代,他想证明自己知道这个秘密。但他不想揭示这个秘密。以下是他所做的事情。

首先,一支电视摄制组对洞穴进行了详细的拍摄,包括两个死胡同通道。然后,所有人都离开了洞穴。米克·阿里独自回到洞穴,并走进其中一个通道。然后,记者带着摄像机进入洞穴,只走到分岔口。在那里,他抛硬币来选择右边还是左边。如果硬币正面朝上,他会告诉米克从右边出来。如果硬币反面朝上,他会告诉米克从左边出来。这次是正面,所以记者大声喊道:“米克,从右边出来。”而米克也确实这样做了。

为了纪念那四十个窃贼,这个演示场景被重复演绎了四十次。每一次,所有人都走出洞穴,米克独自进入其中一条通道。然后记者和摄像机走到分岔口,通过抛硬币来决定给米克的指令。在所有的四十场景中,米克都成功完成了任务。

任何不知道洞穴秘密的人在第一次失败时都会被揭露。每一次新的测试都会将没有秘密的人成功的机会减半。而秘密则让米克每次都能按照要求的出口离开。

由另一家电视网络雇佣的一位嫉妒的记者也想拍摄关于这个奇怪洞穴的故事。但米克拒绝参与,因为他已经将这个故事的独家报道权给了第一个网络。

然而,米克调皮地向嫉妒的记者建议,可以在没有掌握秘密的情况下拍摄这个故事。嫉妒的记者思考了很久,最终他明白了。他自言自语道:“我甚至认识一个舞台演员,他看起来像米克·阿里,可能会被误认为是他。”

第二个故事开始拍摄了。在拍摄过程中,一半的场景被搞砸了,因为米克的替身不知道如何从一个通道走到另一个通道!嫉妒的记者编辑了录像带,只保留了成功的场景,直到拥有了其中的四十个场景。

这两个故事在同一天晚上的同一时间由两家竞争的美国电视网络播出。此事被提交法庭审理。两个录像带都被作为证据提交。但是法官和专家无法辨别这两个录像带。哪一个是伪造的?哪一个是真实的?仅凭录像带本身是不足以作出判断的。

的确,模拟录像肯定没有传达出秘密的知识。但是,无法区分模拟录像和真实录像。因此,真实录像也没有传达出秘密的知识。当时获得独家报道的记者确信米克·阿里知道这个秘密,但是记者无法将他的确信传递给法庭的法官或电视观众。

米克·阿里实现了他真正的目标。事实上,他想要展示的是,可以在不揭示秘密的情况下,通过说服他人来达到目的。

与此同时,以色列的其他研究人员观察到,通过使用多个秘密并进行并行测试,可以减少电影中的场景数量,也就是身份验证的长度。

他们设想了一栋公寓楼,每层楼都有一个洞穴,每个洞穴都有自己的魔法词句。他们只需要在每个洞穴里多雇佣一个演员。所有楼层可以同时拍摄,以确定每个演员出现在哪个楼层。

他们甚至提出了一种算术解决方案,其中使用一个单一数字的回答作为证明可以替代许多演员。

尽管如此,秘密的数量和需要拍摄的场景数量之间的折中可能并不总是最优的。拥有一个秘密和一个场景会更好。

当秘密数量增加时,通过连续尝试进行模拟变得越来越不切实际。当无法通过连续尝试进行模拟时,我们是否无法传达知识呢?

所有这些确实引起了一些欧洲研究人员的兴趣。他们做出了一个适用于串行版本和并行版本的观察。为了节省拍摄时间,嫉妒的记者和米克·阿里的替身可以聪明地事先商定一份包含四十个随机选择的列表,选择是左还是右。在拍摄过程中,嫉妒的记者可以假装在脑中随机选择问题,而事先知道自己将会被问到的问题的替身则不需要知道秘密,仍然可以依次通过所有的测试。

因此,对于只保留成功场景的连续尝试模拟技术,添加了先前约定的模拟技术,这样证明者和验证者之间就达成了一致。

作为对这一观察的回应,建立了一个新的洞穴,其中有更多的通道以分岔的方式结束(即存在多个选择)。当通道数量增加时,洞穴的物理建设确实变得困难。建造一个拥有百万亿通道的洞穴是不可能的。但无论通道数量如何,可以通过先前的协议进行模拟。一个更加算术的方案可以让验证者从百万亿个问题中选择一个问题。通过一次测试,您可以直接达到在具有两个通道的洞穴中进行四十次连续测试所获得的安全级别。

法庭完全无法区分这两个录像带:一个展示了一个演示,另一个则是通过先前的协议进行的模拟。因此,即使问题的规模很大,演示也无法显示对秘密价值的了解。

这样,孩子们,你们听到了阿里巴巴是如何学到奇怪洞穴的秘密,以及他的后代、聪明的研究者米克·阿里是如何能够说服一位电视记者,让他相信自己知道这个秘密,而不必告诉他这个秘密是什么。无数人在电视上看到了米克·阿里,他因此而成名,并在世界各地经历了许多冒险。他仍然没有揭示奇怪洞穴的秘密,但已经让很多人相信他确实知道。保守秘密让我想起了默克尔·海尔曼和他的超级递增背包的故事。但是现在时间已经很晚了。那是另一个故事,留待以后讲述。

Related

不可思议的机器
·1 min
零知识证明
论文阅读: Exploiting Commutativity ForPractical Fast Replication
·4 mins
论文 分布式系统 复制协议 CURP
论文总结: To FUSE or Not to FUSE: Performance of User-Space File Systems
·3 mins
论文 存储 FUSE
分布式系统大局观(二): 实践
·6 mins
分布式系统
分布式系统大局观(一): 理论基础
·12 mins
分布式系统
mmap-sync: cloudflare 对于低延迟 IPC 的解决方案
·8 mins