NIC:从「模拟」理解零知识证明：平行宇宙与时光倒流_KAL

编者按：本文来自安比实验室，作者：郭宇，Odaily星球日报经授权转载。IknowthatIknownothing——苏格拉底相信很多人都听说过零知识证明，但是只有极少数人听说过模拟，然而模拟是理解零知识的关键。我们在第一篇文章『初识「零知识」与「证明」』中介绍了一个简单的零知识交互系统：地图三染色问题。那么这个系统真的是零知识的吗？我们为什么要相信这个结论呢？有证明吗？在Alice与Bob的对话过程中，如果不零知识，Alice就被坑了。交互式系统的设计者「我」需要让Alice确信，这个对话确实是零知识的。如果从直觉主义角度解释，要证明一个交互系统中存在信息泄露，那么你只需要指证：第几个bit导致信息泄露即可；但如果要证明不存在信息泄露，那么你要对着所有信息流中的所有bit说，这从1，2，3，4，5，……编号的bit都没泄露任何信息。看官们，这是不是很难？本文约八千字，略微烧脑。安全的定义与不可区分性

首先，一个交互式系统，也就是一个对话，它的「零知识」需要证明。毕竟，现代密码学是建立在严格的形式化系统之上。在证明之前，还需要明确「安全假设」到底有哪些。所谓安全假设，比如我们说一个系统的权限隔离做得无比精确，每一个用户只能看到被授权的信息，但是这基于一个安全假设：管理员账号没有被破解。又比如在手机银行软件里，只能通过短信认证码，才能完成转账功能，这也基于一个安全假设：你的手机SIM卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统，都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗？比特币账户的安全假设也不少：首先你的助记词不能让别人知道，手机钱包里私钥保存加密算法足够强，密钥派生算法正规，你不能忘记助记词，等等等。脱离安全假设来谈安全都是在耍流氓。一切安全都有前提的。只有经过数学证明之后，大家才能够确信这个算法/方案的安全性基于一些非常明确的「安全假设」。在证明之前，还缺少一个东西，那就是「安全定义」。在多数人的认知系统中，安全就是一个框，什么都可以往里装。大家应该好好提醒下自己，当谈论安全二字的时候，有没有想过到底什么是安全？怎么算安全？「安全」需要有一个数学意义上的严格定义伟大的科学家香农从信息论的角度给出了一个非常靠谱的安全性定义：完美安全：假设你是一个攻击者，你通过密文获取不到任何有价值的信息，破解的唯一手段就是靠瞎蒙。大家想一想，这个定义很有趣，通过密文获取不到信息，这就意味着你没有获得任何额外的计算能力，能够帮助让你以更短的时间来计算出明文。但是这个定义太完美，以至于使用的加密算法都很难满足这个安全性定义。后来Goldwasser与Micali等人写了另一篇载入史册的经典『概率加密』。在这篇论文中定义了这样一个概念：语义安全。所谓语义安全在完美安全的定义上放松了些要求。语义安全：假设你是一个攻击者，你通过密文在多项式时间内计算不出来任何有价值的信息。好了，这个看起来靠谱多了。接下来一个问题就是，怎么理解「计算不出来信息」这个概念？这看来要对信息进行度量，信息的定义又是什么呢？我们又引入一个概念——「不可区分性」，来重新表述加密算法的安全性：假设你是一个攻击者，而我有一个加密算法：OK，理解完「不可区分性」，我们再回到「零知识」，如何证明一个交互式系统是「零知识」呢？首先我们要定义下零知识这个概念注：不可区分性是概率意义上的不可区分；在学术上，它可以分为「完全不可区分」，「统计不可区分」，还有「计算不可区分」。在本文中，我们暂时不需要理解这些概念的差别。遇见模拟器

先开个脑洞，设想在平行宇宙中，有两个平行的世界，一个叫做「理想世界」，另一个叫做「现实世界」。我们每一个个体可以在两个平行世界中愉快地玩耍，但是两个世界的普通人无法互相感知，也无法互相沟通。假设「你」是一个很厉害的密码破解者，而且「你」不是普通人，具备在平行宇宙之间穿梭的能力。而Alice有一个地图三染色的答案，你的目的是通过和Alice对话来获取地图三染色的答案，会话的过程参考上一篇文章的「地图三染色问题」协议。继续脑洞，Alice只存在「现实世界」中；在「理想世界」，Alice被「替换」成了一个长相与声音一模一样的个体，我们称替身为Zlice。下一步，把「你」同时放入两个世界中，但不让你知道是你当前位于哪一个世界。你的两个分身所面对的都是一个“Alice”模样的人。再重复一遍，在「现实世界」中，与你对话的是一个真实的，并且诚实的Alice；而在「理想世界」中，与你对话的是Zlice，Zlice虽然相貌语言与Alice并无二致，但差异是，Zlice并不知道「知识」，即不知道一个三染色问题的答案。接下来在这两个世界中，你的两个分身将同时与真假Alice进行对话。神奇的事情发生了，最终在两个世界中，你的两个分身都被说服了，都经过n轮挑战，没有发现对方作弊，即「你」的两个分身都认为对方确实知道「答案」。换句话说，「你」没有能力「区分」出来自己到底在「现实世界」还是「理想世界」，当然也没能力「区分」和自己对话的究竟是Alice还是Zlice。不仅如此，对于吃瓜群众我而言，如果把「我」作为观察者放入任何一个世界中，我会和你一样「无法区分」出来眼前的这个长相为“Alice”的人到底是真还是假。下面是烧脑结论：这个交互系统为何是「零知识」？因为Zlice是没有任何知识，而且她和Alice不可区分。我再换个方式解释：因为你和我都没办法区分我们究竟是在哪个世界中，两个世界发生的交互过程几乎不可区分，而且其中一个世界中根本就不存在知识，因此，我们说这个交互协议——「地图三染色问题」是「零知识的」。这里还有个前提，理想世界必须是算法可构造的。然后，有一个「神」，他通过算法「模拟」了一个「理想世界」，其中构造了一个算法叫做Zlice，她没有「知识」作为输入，也即「零知识」；除此之外，「理想世界」与「现实世界」一模一样。设想你在对话过程中，如果真Alice泄露了信息，那么你就能立即区分出面前这个人是真Alice还是Zlice，Zlice是不可能伪装泄露信息的。因此可以得出结论：真Alice没有泄露任何信息。这个神，被称为「模拟器」，而在理想世界中，和你对话的这个Zlice幻象其实也是「模拟器」，你在理想世界中，所有能感知到的东西都是模拟器「模拟」出来的。好了，到这里，我们用「模拟器」这个概念对「零知识」进行了定义。接下来，我们开始进入证明零知识的环节。区分两个世界

SaveWorldStateasSnapshotX证明的零知识过程，等价于构造一个「模拟」算法，这个算法能够让模拟器来模拟出一个「没有知识」的理想世界。如果这个算法存在，而且两个世界不可区分，那么就证明完毕。等等，可能「你」会觉得哪里不对劲。假如说真的存在这种算法，而且它能够在没有知识的情况下过我，那么在「现实世界」中，不排除真Alice也使用了这样的算法来我。这样一来，我岂不是在两个世界中都被了。那么这个交互协议就失去意义了。其实，这里有个关键点，借用电影『盗梦空间』中的剧照，在「理想世界」中有点东西是和「现实世界」本质不同的。这个东西是区分两个世界的关键，而它要让我们「无法感知」。这个东西不是梦境中的陀螺，它是一种「超能力」，模拟器Simulator所具备的超能力。比如这样一种超能力：「时光倒流」。等等，各位看官，不是刚才我们一直在讨论不可区分性吗？怎么两个世界又需要区分啦？“我糊涂了”。不要慌，所谓的不可区分性针对的是理想世界中的个体认知而言。而「可区分性」是对位于世界外部的神而言。设想下在我们周围，如果有一个人有时空穿越能力，或者他能让时间回退到一年前，那么我们这些凡夫俗子完全是一脸茫然的，无从感知。那么，如果「模拟器」可以在他构造出的「理想世界」中实现「时间倒流」，那么他就可以达成一些神奇的事情，从而过作为验证者身份的「你」，也能过观察者「我」。对于「你」而言，你明白，在「理想世界」中，时间是可以回退的，但是在「现实世界」中，显然真Alice不可能拥有超能力。虽然你和我不能区分在哪个世界里，但是至少我们知道在两个世界中的其中「现实世界」里，对面那个Alice是没办法我们的，当然我们却不能说出我们到底在哪个世界中。到此，交互协议的「零知识」已经证明完了。各位是否已经明白了？我再给大家再梳理下证明思路：首先「零知识」是为了保护Alice的利益，因为Alice不想在交互过程中透露更多的信息给Bob，不想让Bob知道她所拥有的秘密w，甚至不想让Bob从交互的过程中分析出哪怕一丁点的信息。那么怎么保证这一点呢？「模拟器」这时候登场了，它能模拟出一个和现实世界外表一模一样的「理想世界」，然后「模拟器」在这个世界中可以轻松地过任何一个对手，让对方无法分辨自己是在现实世界中，还是理想世界中。因为「模拟器」手里没有那个秘密w，「理想世界」是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice的交互协议是「零知识」的。我们来看一个具体的例子，上一篇文章中提到的地图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年代，阿里巴巴的羊皮纸流落到了几个密码学家手里，他们跑到巴格达，找到了洞穴的位置，尽管过了几个世纪，咒语居然仍然有效，这几个密码学家兴奋地打开墙壁，在两个岔道之间跑来跑去。一家电视台很快知道了这个奇异事件，一个密码学家MickAli决定向电视观众展示他知道这个咒语，首先，电视节目主持人把摄像机架在洞口，然后让所有人都在山洞口等待，这时候MickAli一个人进入到山洞中，然后主持人抛一个硬币，来决定让MickAli从哪个岔道跑出来。为了纪念阿里巴巴与四十大盗，MickAli重复了四十遍每次都成功。节目非常成功。但很快，另外一个电视台眼红，也想拍一个类似的节目，但是MickAli因为签了独家协议，没办法参与这个新节目。怎么办呢？第二个电视台的主持人心生一计，他找了一个和MickAli很像的演员，穿着打扮、姿态和说话口音都模仿MickAli。然后他们开拍了，每次主持人掷硬币后，都让这个演员跑出来，但是很显然，演员并不知道咒语，没办法打开那个墙壁。于是有时候演员碰巧会成功，有时候则会失败，于是演员很辛苦，重复了将近一百次，才成功了四十次。最后这个狡猾的新节目主持人，把录制视频进行了剪辑，只保留了成功的片段，错误的片段都删除了。然后这个新节目和MickAli的节目在同一时间，不同频道播出。然后观众们完全无法区分哪个视频是真的，哪个视频是假的。第一个电视台的主持人完全明白MickAli是真正知道墙壁的咒语的人，但是他却不能把这个事实传递给无辜的观众们。看到这里，大家是不是对「模拟」慢慢有了感觉？这里第二个电视台的主持人通过剪辑视频的方式，而不是「时间倒流」。他对「理想世界」，也就是电视中播出的内容所在的世界，进行了外部干预，达到了同样的效果。对理想世界而言，这种剪辑本质上就是一种超能力这个故事其实来源于一篇论文『如何向你的孩子解释零知识证明』，发表在1989年的美密会议上。模拟与图灵机

一谈到超能力，大家有没有觉得这玩意不科学。是的，如果我们无脑地用「超能力」来解释任何事情，那么我们逻辑就无法自恰。在理想世界中，模拟器是不能随便开挂的，比如模拟器肯定不能直接修改Bob的内部状态，比如Bob在验证步骤明明验证失败，但是模拟器强硬去把验证结果改为「接受」，这会导致我们可以证明：「任何的交互系统都是零知识的」，这个错误结论。模拟器不是理想世界中全能的上帝。那么模拟器到底可以是什么呢？模拟器其实只是一个图灵机。所谓的「时间倒流」，「剪辑录像」这类的所谓超能力并不是玄乎的超自然能力，而是图灵机可以实现的功能。计算机专业的朋友们肯定都用过VMWare，虚拟机之类的软件，本文讲的「模拟器」完全可以想象成一个「虚拟机」软件，它能虚拟出一个计算机环境，这个虚拟环境就是我们上文说的「理想世界」。「时间倒流」如何解释呢？不知道大家有没有用过虚拟机软件的「快照」功能，使用快照的时候，虚拟机软件可以把整个虚拟计算机的所有状态保存下来，然后在任意时刻，虚拟机软件都可以重新回到保存快照的位置继续运行。注：其实所谓时间倒流是计算机中的一个基本操作，在程序语言理论中有一个概念叫做Continuation。抽象地讲，Continuation表示从现在开始到未来的计算。Continuation这是控制流的一个显式抽象，而goto，call-with-current-continuation，甚至threadscheduling都可以看做是操作Continuation的操作符。比如采用call/cc，也就是call-with-current-continuation就可以轻松地实现「回溯」功能。保存快照可以理解为保存当前的Continuation，而回到过去的某一刻，就是应用这个Continuation。不管Zlice还是Bob，还有我们的每一个观察者，都是一个个可执行程序。这些程序被拷贝到了虚拟机里。Zlice与Bob的会话实际上就是这两个程序之间的通讯。观察者是Hook在Zlice与Bob进程IO上的程序。在上文的地图三染色「理想世界」的诚实Bob，实际上是Bob进程调用了虚拟机的「随机数发生器」，而这个随机数发生器是能被Zlice操纵的。「现实世界」是外部运行虚拟机软件的计算机环境。大家是不是又有所悟，我再强调一下：证明零知识的过程，就是要寻找一个算法，或者更通俗点说，写出一段代码，它运行在外部计算机系统中，但是实现了虚拟机的功能。而且在虚拟机中，需要有一个不带有「知识」作为输入的Zlice，可以过放入虚拟机运行的Bob。如果还没理解上面我这句话，请时光回退到『区分两个世界』这一小节，重新思考模拟。:P柏拉图的洞穴寓言

模拟无处不在，哥德尔不完备性定理就使用了模拟的概念，用哥德尔数模拟了形式算术。图灵提出了「UniversalTuringMachine」的概念，这种图灵机可以模拟自身。但最早的「模拟」概念，出自『理想国』一书的第七卷中，古希腊哲学家柏拉图讲了这么一则寓言——AllegoryofCave：设想在一个暗无天日的山洞中，有一排被锁链锁住的囚徒，他们从小就只能看到前方的墙壁。这些囚徒们身后是一堵墙，再后面有一堆放着火，在火与墙壁之间，有一些人举着道具和木偶来回走，这样道具木偶就会在火光映射下在墙壁上投下影子。而这些囚徒们整天就只能看着这些影子。因为这些囚徒们从打出生起，所闻所见就只是前方洞壁上的各种影子，他们会以为所看到的这些影子就是真实的世界。然而有一天，一个囚徒偶然挣脱锁链，他回头看到了火。但是他从小到大仅能看到暗淡的影子，他第一次看到了明亮的火光。看到了道具和木偶，假如有人告诉他，这些道具和木偶才是实物，他一定会嗤之以鼻，会坚持认为影子才是真实的。柏拉图假设说，如果把这个囚徒强制拖出洞穴，到外面去看到真实的世界，一开始囚徒会不适应真实世界的光亮而感到刺目眩晕，他会因此而愤怒。但是当他慢慢适应了这个世界，看到太阳，树木，河流，看到星空，他逐渐明白，这个世界比洞穴中那个世界更为优越高级。他再也不想回到黑暗的洞穴生活中了。过了一段时间，他对洞穴中的囚徒心生怜悯，于是想去把他们都带出来。但是当他再次返回洞穴中，他因为已经适应了外面明亮的世界，回到洞穴中反而看不清楚。被锁的囚徒们反而认为他的视力受损，胡言乱语，是个疯子，最后当他想尽办法把这群囚徒带出洞穴时，被囚徒们联手杀死。这是则人类命运的寓言，就和那一排被锁链锁着的囚徒类似，我们以为眼睛看到的就是世界的真相,但实际上，那也许是幻象，就像洞穴墙壁上投下的影子一样。未完待续本文章介绍了理解零知识所需的关键概念——模拟。任何一个零知识的协议，都可以通过构造一个「理想世界」来理解。第一次接触这个概念的读者需要反复琢磨。计算机科学中有两个方法论至关重要，第一个是「抽象」，第二个是「模拟」。回顾一下在地图三染色问题中，Bob在「理想世界」与「现实世界」中的对话。虽然Bob无法区分两个世界，但是有一点，他可以确信：现实世界中，Alice没有超能力。问题来了，Alice没有超能力，并不能直接证明Alice真的有答案。万一这个交互协议并不能保证Alice一定有知识呢？「零知识」保护了Alice的利益，谁来保证Bob的利益呢？这个问题留给下一篇。参考文献初识「零知识」与「证明」.安比实验室.2019.ShafiGoldwasserandSilvioMicali,ProbabilisticEncryption,SpecialissueofJournalofComputerandSystemsSciences,Vol.28,No.2,pages270-299,April1984.Quisquater,J.J.,Quisquater,M.,Quisquater,M.,Quisquater,M.,Guillou,L.,Guillou,M.A.,Guillou,G.,Guillou,A.,Guillou,G.andGuillou,S.,1989,August.Howtoexplainzero-knowledgeprotocolstoyourchildren.InConferenceontheTheoryandApplicationofCryptology(pp.628-631).Springer,NewYork,NY.柏拉图and吴献书,1986.理想国(Vol.1,No.986,p.1).商务印书馆.Goldwasser,Shafi,SilvioMicali,andCharlesRackoff."Theknowledgecomplexityofinteractiveproofsystems."SIAMJournaloncomputing18.1(1989):186-208.Oded,Goldreich."Foundationsofcryptographybasictools."(2001).Rackoff,Charles,andDanielR.Simon."Non-interactivezero-knowledgeproofofknowledgeandchosenciphertextattack."AnnualInternationalCryptologyConference.Springer,Berlin,Heidelberg,1991.Goldreich,Oded,SilvioMicali,andAviWigderson."ProofsthatyieldnothingbuttheirvalidityoralllanguagesinNPhavezero-knowledgeproofsystems."JournaloftheACM(JACM)38.3(1991):690-728.zkPoD:区块链，零知识证明与形式化验证，实现无中介、零信任的公平交易.安比实验室.2019.

标签：LICNICANDKALSLICEconic币在哪儿买OLAND价格Kalkulus

币安币热门资讯