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

到此，交互协议的「零知识」已经证明完了。各位是否已经明白了？我再给大家再梳理下证明思路：
首先「零知识」是为了保护 Alice 的利益，因为 Alice 不想在交互过程中透露更多的信息给 Bob ，不想让 Bob 知道她所拥有的秘密 w ，甚至不想让 Bob 从交互的过程中分析出哪怕一丁点的信息。那么怎么保证这一点呢？「模拟器」这时候登场了，它能模拟出一个和现实世界外表一模一样的「理想世界」，然后「模拟器」在这个世界中可以轻松地骗过任何一个对手，让对方无法分辨自己是在现实世界中，还是理想世界中。因为「模拟器」手里没有那个秘密 w ，「理想世界」是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice 的交互协议是「零知识」的。
我们来看一个具体的例子，上一篇文章[1]中提到的地图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 极大的概率总会一次选择模拟器进行染色的那条边，然后这时候模拟器才走到第三步，打开纸片。

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

猜你喜欢

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