一文读懂零知识证明

零知识证明

本文来聊一聊零知识证明的一点知识, 本文的例子纯属虚构，故事素材来源于网络和论文，以及我的瞎编, 如有雷同, 纯属巧合。

话说，从前有一组人打算去探险, 然后由于他们的水平有限, 因此他们到达目的地之后找了一个导游, 假设这个导游名字叫张三吧, 然后他们担心这个导游不够专业, 而且要价比较高, 然后这一组人呢就想让导游证明一下他的实力, 于是导游带他们到了4个门前, 门的入口有一个机关，只有破开这个机关，才能够进去, 故事便从这里开始。

巧分葫芦

第一扇门前面有两个葫芦, 相传在西游记当中，混沌初分，天地开辟，一位太上老祖，解化女娲之名，炼石补天，普救阎浮世界。补到乾宫触地，见一座昆仑山脚下，有一缕仙藤，上结着这个紫金红葫芦, 其中一个是雌的，一个是雄的, 这一关要求区分这两个葫芦哪一个是雌的，哪一个是雄的, 张三心理想，这我不能直接给他们说，把这个门打开，万一我分出来了，这帮人不给我钱了，这怎么办，那我不就亏了，这时候，一道灵光闪现，张三有了主意。

于是张三对这一帮人说，我能够分出来这两个葫芦，但是我不直接给你们分出来把门打开，你们看这样，现在这两个葫芦在这。

葫芦

然后你们等我转过身去，你们可以选择交换这两个葫芦的位置或者不交换这个葫芦的位置，等你们操作完成，我再转过身来，然后我说出你们是否交换了这两个葫芦的位置，如果我能说对，这证明我确实能分出来。

这一队人说，这样万一你是蒙的呢，交换和不交换就这两种可能，你随便猜一下，这都有一半的概率能猜中。

张三说，这样，我们重复进行这个操作，如果我连续10次都能说对，这样我是猜的概率就是, 这样你们总不能说我这是蒙的了吧，要是这样，那我可就有欧皇附体的体质了，哈哈。

于是这一组人合计了一下，这样可以，于是相信了向导张三，他们走向了第二扇门。

洞穴谜题

这有一个奇怪的洞穴，这洞穴有一扇门，这一扇门需要一个咒语才能够打开，如下图所示:

洞穴谜题

忽略一下我的灵魂画图，意会一下这一个洞穴蛤，这时候张三有不想直接把这个咒语告诉他们把这个门打开，然后张三灵感再次出现，想到了一个主意，他和这一对人说，你们在门口看到我进去了，然后你们到门口喊一下，我从A或者B出来。

张三选择A

假设张三选择了A, 然后他们要求张三从A口出来的话，那么正好张三可以直接从A口出来，不需要开门就可以了，但是如果他们要求从B口出来，这就需要张三默念咒语，然后把门打开，才能从B口出去。

A默念咒语，从B出去

和上面的葫芦一样，如果张三每次都能从所说的口出去，这一队人就可以相信张三是真的知道这个咒语了，紧接着，这一队人便跟着张三到了下一扇门前。

数独谜题

先来介绍一下什么是数独，「数独」 是一种数学逻辑游戏，游戏由9×9个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案(这段话来自于维基百科)，具体规则如下（图片来自于维基百科）:

数独图片

• 每一列的数字均须包含 1～9，不能缺少，也不能重复。
• 每一宫(粗黑线围起来的区域，通常是 3*3 的九宫格)的数字均须包含 1～9，不能缺少，也不能重复。

具体关于数独的介绍，我也就不啰嗦了，来看具体的故事吧，这里的张三简单化身一下数独高手，就当这一队人都不会玩数独，技术是非常的菜。那么张三有没有办法在不告诉这一队人数独答案的情况下让他们相信张三可以解开这个数独呢？

这时候张三绞尽脑汁思考了一下，这时候仿佛神仙附体，张三一下有了方案。

张三先把数独上面的答案写在小卡片上面，然后可以让他们去选择按行，按列或者按块把小卡片放到一个袋子里面，然后豁楞豁楞，豁楞均匀了，如果打开每个袋子都是1-9的话，那么表示张三确实是有能力解开这个数独的。

按行分割

卡片

同样，忽略一下我这拙劣的绘图，理解一下什么意思就好了，不接受对画图的吐槽。紧接着，他们到了最后一个门前面，这同样是一个数学问题。

地图三染色问题

先来简单解释一下什么是地图三染色，如何用三种颜色染色一个地图，并且保证任意两个相邻的地区都是不同的颜色，这显然并不是所有的地图都可以三染色的。

地图三染色

这个时候，考验张三的时候又来了，张三怎么向这一队探险者证明他真的可以给这个图用三种颜色染色，又不想告诉这一队人具体的结果呢？

这其实也不难，聪明的张三再次的想到了方法，张三吧上色的结果放到信封里面，然后让这一队人随机选择两个相邻的信封打开，这样如果发现这两种颜色不同，然后张三销毁掉之前的信封，打乱顺序，就是对这三种颜色做个轮换，再次放到信封里面，再让这一队人选两个相邻的打开，重复多次操作。

选择相邻的信封打开

经过这一系列的验证，这一队人终于相信了张三的能力，于是愉快的付钱了，故事到此结束了，后面的事情就由读者自行想象一下吧。

总结

本文简单介绍了几个零知识证明中的例子，故事纯属虚构，如有雷同纯属巧合, 实际上零知识证明的思想早在16世纪文艺复兴时期就出现了，当时的两位数学家塔尔塔利亚和奥菲都宣称掌握了一元三次方程的求根公式，于是他们两个为了向众人证明他们确实掌握了解决这个问题的方法，这他们不能直接公布这个公式，如果第一个人先公布了，第二个说我也是用的这个方法，这就不好去判断是不是这两个人都发现了这个问题的解法，于是他们采用擂台对决的方式来证明，由双方互相出30个一元三次方程的题让对方求解，最终，塔尔塔利亚解出来了奥菲提出的所有的题，但是奥菲一道也没解出来塔尔塔利亚的题，所以大家相信塔尔塔利亚是真的掌握了一元三次方程的求根公式，这便是一个比较简单的零知识证明的例子了，好了本文到这里结束了，个人能力有限，可能会有我理解的不到位的地方，请各位读者大佬指正。