引谈 | 零知识证明的简单解释

零知识证明背后的核心原理其实是我们每天都在使用的假设推理逻辑。
用汉密尔顿循环,简单解释零知识证明→

引谈 | 零知识证明的简单解释 Filecoin 第1张
本文由IPFS原力区收集译制,版权所属原作者
引谈 | 零知识证明的简单解释 Filecoin 第2张
 
零知识证明很容易理解,它基于的推理逻辑和我们日常对身边事物进行假设时使用的推理逻辑一致。
 
当你处于一个没有窗户的房间内,听着屋顶淅淅沥沥的雨声,即使你没有看到下雨,你也会认为屋外正在下雨。当你结束工作回到家中,看到室友的汽车停在路边,你也会认为你的室友已经到家,即使你没有实际看到他。
 
这种思考方式是我们每天必不可少的,这也是零知识证明背后的核心原理。证明人试图说服验证人某个事实,但是由于事实本身的敏感性,并不能直白地表达出来。为了避开这一点,证明人可以构建一条间接性证明。如果间接性证明没有泄漏前面提及的消息敏感性,那么它就是零知识证明。
 
假设你的室友,我们叫他王一,性格内向,总是不愿和你闲聊。但是王一并不喜欢你独自一人时播放吵闹的音乐,所以,他把车停在路边,外套放在长凳上,你会认为他在家中,即使你没有亲眼看见。王一正是给了你一个他在场的零知识证明。
 
接下来介绍1986年Manuel Blum的论文《How to Prove a Theorem So No one Else Can Claim it》中的简单零知识证明协议。
 
写这个协议的理由
 
这个协议和目前区块链应用的zk-SNARKs协议有很大不同。zk-SNARKs是简明的、非交互式的、通常使用运算电路来证明解决方案。它的简明性来自于椭圆曲线原理,非交互性源自随机的外部数据源(oracle)或通用参考字符串。
 
这里讨论的协议比这些都要简单。它并不关心简明性而且也明确有交互性。因此,它避免了zk-SNARKs算法中的复杂性。它通过图形来表示,相对于运算电路来说更加直观。
 
我希望通过本文的阅读,你可以对零知识证明这项工具的使用场景有更加深刻的理解。如果你淹没在椭圆曲线配对的海洋中,你会回想到这个80年代的简单协议并找到一些理论支撑。
 
一个简单的构建
 
首先,让我们浏览一些图相关的描述。
  • 图是由顶点和边构成的。
  • 路径是由边组成的序列。
  • 循环是自我闭合的路径。
  • 汉密尔顿循环是经过图中每个顶点仅一次的循环。在有n个顶点的图中,汉密尔顿循环是有n个顶点的循环。下面是一些具有汉密尔顿循环的图,汉密尔顿循环用红色表示。
 
引谈 | 零知识证明的简单解释 Filecoin 第3张
 
正如你所见,图中每条路径都闭合,且仅经过所有顶点一次,即汉密尔顿循环。
 
在这个协议中,证明人试图说服验证人,他知道图中的汉密尔顿循环。
 
假设,你以投递报纸为生,你有一个所有需要投递地址的列表。如果将地图想象为图,地址为图中的顶点,地址之间的路径就是边。你试图说服你的老板这样一个事实,你只经过每个地址一次,但你并不希望你的老板知道你如何拜访这些地址,以防有一天你的工作被别人替代。
 
假设王一是投递报纸的证明人,张三是验证人即王一的老板。王一并不希望告诉张三他的投递路线,但是他希望证明所有人都收到了报纸。为了实现这一点,王一需要向张三证明两件事:首先,他知道这条投递路线;其次,他表述过程中并没有说谎。
 
如果诚实的王一能够利用协议证明他知道秘密的汉密尔顿循环,那么协议就是正确的。如果王一可以证明他的行为是诚实的,那么协议就是健全的。如果王一可以完成上面两件事情,同时没有泄漏任何路线的信息,那么协议就是零知识的。
 
正确性——假设王一(证明人)是诚实的
 
为了简单,我们先不考虑健全性。我们假设王一是诚实的。
 
协议过程如下,王一创建了新的图。新图和旧图中每条路径和循环的长度和基数都相同。
 
比如,如果旧图中有两个长度为3的循环,新图中也有两个长度为3的循环。如果旧图中有1个长度为4的路径,那么新图中也同样存在。同理,旧图中有汉密尔顿循环,则新图中也存在汉密尔顿循环。因此,新图中存在汉密尔顿循环就是旧图中存在汉密尔顿循环的间接证明。
 
王一首先将旧图进行复制,然后按照随机方式交换顶点,确保记录下原来的顶点位置。最终,他将得到新的图,同时得到旧图和新图的顶点映射关系。他确保这两项内容保密。
 
引谈 | 零知识证明的简单解释 Filecoin 第4张
左边是旧图
中间是顶点标签变换后的新图
右边是旧图和新图顶点的映射关系
红线表示证明人的汉密尔顿循环
 
不难发现,在新图中,所有的路径和循环都得到了保留。另外,旧图中的汉密尔顿循环在新图中以不同顶点的方式展示出来。
 
因为顶点的标签进行了随机互换,新的汉密尔顿循环并没有泄漏原始的汉密尔顿循环(除了循环由N个顶点构成以外,这在定义中也是隐式的)。因此,这个间接的证明就是零知识的。
 
健全性——检查证明人是否诚实
 
如果我们生活在一个所有人都诚实的世界中,我们可以在这里停止了。当王一提交新的汉密尔顿循环,张三验证新汉密尔顿循环(具有n个顶点的循环)的正确性,一切就此结束。
 
但是,现实中,王一可以创建一个新的汉密尔顿循环,它和原有的事实之间并无联系。
 
基于这种场景,张三就需要检查王一创建的新图是正确的(也就是说新图和旧图之间的差别仅仅在于顶点进行了交换)。
 
让我们先回忆一下:张三已经得到了一个新的汉密尔顿循环(n个顶点的循环),如果张三信任王一,那么他就不需要再做什么了:接受这个证明,并支付投递报纸的费用。
 
但是,如果他不信任王一,他还需要做一项额外的工作,以确认新图的产生过程是正确的。
 
为了证明,张三可以直接将新图还原为旧图进行验证。
引谈 | 零知识证明的简单解释 Filecoin 第5张 
验证人可以通过新旧图顶点映射关系图表,还原出旧图
 
不幸的是,如果张三可以访问顶点关系图表、新图和新的汉密尔顿循环,那么他也就能够计算出需要保密的汉密尔顿循环。这与协议的初始目的相背。
引谈 | 零知识证明的简单解释 Filecoin 第6张
 
为了解决问题,王一需要生成多个新图。对于每个新图,张三通过抛硬币的方式,选择下面问题之一进行提问:
1.(正面):新图中的汉密尔顿循环(假设王一是诚实的,可以证明原始信息)
2.(反面):新图和对应的顶点关系图表(直接证明新图的生成是正确的)
 
因为王一无法提前知道会被问及哪个问题,他需要猜测硬币的正反面,以确保造假过程顺利进行。
 
假设王一作弊。他期望张三抛出硬币正面,即选择问题1,王一会选择虚假的包含随机汉密尔顿循环的新图,和旧图并无任何关联。但是如果张三再抛出硬币的反面,王一的作弊行为将被揭穿。
 
另外,如果王一期望张三抛出硬币反面,即选择问题2,他将创建一个没有汉密尔顿循环的新图。如果张三实际抛出硬币的正面,则王一将无法提供新图中的汉密尔顿循环。
 
王一如果能够蒙混过关,他需要能猜测出张三抛硬币的结果。在一次迭代中,王一有50%的成功概率。两次迭代中,则只有50%✖️50%=25%的机会。通过多次迭代,王一几乎没有可能提供一个虚假证明。
 
如果张三对多次测试的结果满意,那么他就可以确信王一知道秘密的汉密尔顿循环,也就是我们需要实现的目标。
 
—END—
本文由IPFS原力区编译,原文链接:
https://medium.com/@tobilon/零知识证明的简单解释-de5b42b49f8a
引谈 | 零知识证明的简单解释 Filecoin 第7张

IPFS原力区】

价值观:价值 共建 共享 荣耀

总部位于上海,聚集基于分布式网络&存储的众多技术大咖和爱好者,深耕基于 IPFS 的商业生态建设和社区发展。

每周二举办“分布式存储网络”主题沙龙,聚集了众多技术大咖和 IPFS 爱好者,通过持续输出全面、精细、优质的IPFS咨询和技术支持,将生态中的爱好者转化为IPFS支持者和参与者,共建IPFS生态的健康发展。

引谈 | 零知识证明的简单解释 Filecoin 第8张

本文来自https://mp.weixin.qq.com/s/_cij9lRIFA1vmTNoiqmlew,经授权后发布,本文观点不代表IPFSER立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

在线咨询:点击这里给我发消息

邮件:ipfsforce@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code