IPFS星想法|从「模拟」理解零知识证明:平行宇宙与时光倒流(一)

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

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

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

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

安全的定义与不可区分性

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

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

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

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

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

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

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

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

2020063003161024

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

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

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

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

IPFS星想法|从「模拟」理解零知识证明:平行宇宙与时光倒流(一)

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

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

遇见模拟器

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

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

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

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

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

2020063003164388

下面是烧脑结论:

这个交互系统为何是「零知识」?

因为 Zlice 是没有任何知识,而且她和 Alice 不可区分。

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

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

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

真 Alice 没有泄露任何信息。

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

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

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

区分两个世界

Save World State as Snapshot X

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

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

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

2020063003183283

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

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

2020063003185333

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

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

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

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

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

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

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

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

2020063003192288

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

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

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

回到第一步,重复 n 遍

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

2020063003195918

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

2020063003203013

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

2020063003205269

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

2020063003213733

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

2020063003223662

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

2020063003231782

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

2020063003234028

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

2020063003235913

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

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

不诚实的 Bob

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

本文来自投稿,不代表中文资讯网(www.ipfsnews.cn)的立场,

文章内的信息、意见等均仅供参考,并非作为或被视为实际投资建议。

如若转载,请注明出处:https://www.ipfsnews.cn/3229.html

发表评论

登录后才能评论