雷锋网 (大众号：雷锋网) AI金融评论按：本文作者知乎ID“Xiaoyao Qian”，团体简介为UIUC计算机迷信系硕士，NAD Grid（https://nadgrid.com）技术合伙人。雷锋网AI金融评论受权转载自知乎网友“Xiaoyao Qian”文章《 一个数独引发的惨案：零知识证明（Zero-Knowledge Proof） 》。

这篇文章大局部译自：https://medium.com/qed-it/the-incredible-machine-4d1270d7363a 原文的作者是著名的Ghost和Spectre 这两个协议的开创团队的领队Aviv Zohar。原文作者说他的这篇原文又是援用了以下这两篇学术论文：

How to Explain Zero Knowledge Protocols to Your Children (Quisquater et. al.)

Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles (Gradwohl et. al.).

老钱觉得原文是零知识证明方面写的最好最接地气的科普类的文章。所以想要翻译一下，特地在原文根底上加上一些本人的解读。想要理解零知识证明，或许匿名性极强的区块链加密货币ZCash的冤家无妨读一读。

小明，小红，小刚三个好冤家很喜欢玩数独。素日里他们三个也会相互出题给对方做。有时分他们会出一些十分变态的数独题相互应战。他们会挑一团体在纸上画出一个NxN的格子，填上谜面（Constraint），然后交给另外两人去解。

证明

有一天，小明出了一道十分难的数独题，小红花了很长工夫尝试去解开这个数独，但是怎样都解不出后果。小红觉得小明在耍她，“这题压根就无解！小明你耍我！”，她跑到小明那埋怨。

“呵呵，我能证明给你看这题是有解的，而且我晓得这个解“，小明淡定的答复道。

“好啊“，小红暗自想着，“哼哼，等你证明给我看之后，我就把解记上去然后去戏耍一下小刚，给他也做一下这题。”

小明接着说：“我会用零知识证明的办法给你证明我会这题的解。也就是说我不会把解给你看，却能让你服气我的确有这题的解。”

小红并不置信他能这样做到，还在想象小刚被耍的样子。

承诺

小明拿出81（9x9）张空白的卡片放在桌上，在每张纸上写上1-9中的一个数字，他让小红转过身闭上眼，然后把这81张卡片小心翼翼地依照解的陈列放在桌上，代表谜底的卡片，数字面朝下放在桌上；代表谜面的卡片，则数字面朝上放在桌上。

随机实验

小明放好卡片后，让小红睁开眼转过身。小红很冲动，她觉得谜底就要揭晓了，很是开心。她可花了好几地利间都没能解出这题。

小明对小红说：“小红，你不能偷看这些面朝下的卡片。“，分明能看出小红很绝望，她以为能看到完好的一个解。“但是我能让你检验这些解：你可以随意选择依照行(row)，或许依照列(column)，或许依照3x3的九宫格(box) 来检验我的解。你挑一种吧～”

小红很困惑，嘴上念叨着什么鬼心里想着mmp，然后通知小明她决议选择依照行的办法来验证，小明接着把每一行的9张卡片收起来独自放到一个麻布袋里。一切卡片都被收完放在了9个麻布袋里。小明接着摇了摇每个麻布袋，把外面的卡片顺序都打散。最初把这9个麻布袋交给小红。

验证

“好了，你可以翻开这些布袋了。“小明对小红说，“每个布袋里应该都有正好9张，没有反复数字的，辨别是数字1-9的卡片。” 小红翻开每个布袋一看，还果真是这样。

“可这啥都证明不了啊！我也可以这样做给你看。我只需保证每一行都是1-9这9张卡片，不去管纵列和九宫格里的数字是不是也都是没有反复的不就行了。“小红气急败坏的说道。

小明解释说：“可是我事前也不晓得你会选依照行来搜集卡片，还是依照列，还是依照九宫格啊。我又不是你肚子里的蛔虫。。。我是依照题解来放置卡片的，你选啥我都没在怕的”

小红想了想，的确，一个数独只要真正正确的解才干保证每一行每一列每一个九宫格里的数字都是没有反复的1-9。小明假如真的在骗她，小明不会那么理屈词穷，小红也至多有1/3的概率可以抓到他在骗人。

反复

小红还是不信服。觉得小明依然有能够在骗她，所以要求小明再把卡片恢复，依照原来的办法，重新选。这样接连试了几次，小红每次都选一个不一样的实验办法。试了好屡次都是一样的后果。小红这下不得不供认，小明要么运气十分十分好，每次都能押中小红会选择哪种实验方式，要么就是他的确晓得题解，（或许小明会读心术能事后晓得小红会选什么实验方式）。小红很绝望，这么屡次实验上去，她还是不晓得真正的题解，她只晓得每次小明放置卡片的陈列里很大几率每行每列每个九宫格的确都是没有反复的1-9，这就阐明很大几率这题是有解的，而且小明很大几率的确晓得这题的解。

小明把这种零知识证明的办法也给小刚展现了一遍。从此之后三个好友养成了经过零知识证明去证明给对方看本人晓得某题解的习气。毕竟每团体在解题的时分都花了很大功夫，不想随便地把题解直接通知对方。虽然每次零知识证明的进程很花工夫，但是他们都乐在其中。

席卷全球的数独风暴

逐步的，小明和小红发现全世界有很少数独喜好者，他俩决议在斗鱼上开一个直播间，直播解数独。为了展示本人的聪明才智，每周开播前，小明在粉丝团里随机抽取一个粉丝递交的数独，直播时，小明会把题解通知小红，然后由小红用零知识证明的办法向观看直播的老铁们证明这题有解，并且本人晓得题解，老铁们纷繁表示666并送上飞机火箭。就这样小明和小红的直播间人气暴跌，两人成为了斗鱼的签约艺人。

开挂

一天，小明离开小红家预备直播一个十分难的数独，可是他发现他把解出的题解落在本人家了。工夫紧迫，要重新算一遍指定赶不上开播工夫会被斗鱼老板骂。但是他和小红还是决议开播。开播前小明和小红说：“咱俩伪装弄一弄零知识证明，我通知你一会儿我会怎样选实验方式。你只需确保每次我选的那种实验方式（每行，或每列，或每个九宫格）里的数字不要反复就行了。” 小红赞同了。

小刚，在本人家看完了直播，预先小明和小红把他俩这次作假的办法通知小刚，小刚义愤填膺的呵斥他们俩，“你们这样做和卢本伟开挂有什么区别！对得起支持你们的粉丝吗？我再也不置信你们俩的零知识证明了！”

神奇的机器和非交互式证明 (Non-interactive Proofs)

小刚很不爽。一来他很享用之前和小明和小红一同玩数独，但是如今他觉得挂逼不值得信任。小刚想找另一种办法来保证直播中他俩不能再这样作假。几个不眠的夜晚过来之后，小刚通知小明小红，他想到了一个好办法。小刚把本人关在屋里忙活了一整天，第二天早上他把小明小红叫来，给他们展现本人的新创造：零知识数独非交互式证明机（“The Zero-Knowledge Sudoku Non-Interactive Proof Machine” or zk-SNIPM）。

这台机器根本上就是把小明和小红之前当面做的那套证明自动化，不再需求人为交互。小明只需把卡片放在传送带上，机器会自动选择按行，或列，或九宫格来收取卡片，放到袋子里打乱顺序，然后把袋子经过传送带再送出来。然后小明就可以当着镜头的面拆开袋子展现外面的卡片。

这台机器有一个控制面板，翻开外面是一串旋钮，这些旋钮用来指示每次实验的选择（行，列， 九宫格）。

小刚曾经设置好了实验的序列，然后把控制面板焊死，以保证小明和小红不会晓得他究竟选择了怎样样一个实验序列。

这下小刚很担心，他可以完全信任本人这台机器，担心的把机器交给小明和小红，让他俩下次直播就直接用这台机器来证明。小刚置信有了这台机器他俩就没法再开挂了。

典礼

小明和小红很妒忌小刚的这台机器，并且想也能用这台机器来验证小刚本人出的数独题。但是成绩是，小刚是晓得本人选了什么样的实验序列的，假如用同一台机器去验证小刚本人的数独题解，小刚就可以开挂。小明把大伙聚集起来提议让小刚把控制面板重新翻开，然后大家一同来设置控制面板上的实验序列。小明把这个进程称为“可信任的初始设置典礼（trusted setup ceremony）”。

小明提议把这台机器放在一个乌黑的屋子里，把旋钮上的指示贴纸都撕去。他们三人辨别进入这个屋子，小红还提议大家进房间时蒙上眼来保证随机性，并且带一顶锡纸做的金属帽子（小红还是疑心小明多少会一点读心术，想经过锡纸帽子来屏蔽脑电波信号避免读心术（side-channel attack））。这样，最初这些旋钮所代表的实验序列他们三团体都没有方法晓得。就算他们3人中有2人事前磋商好本人会怎样选，他们也无法得知第三团体会怎样选，从而没有方法作假。这个典礼完毕之后，他们一同把控制面板焊死。

破解这台机器？

一天下午，小红和小刚出去玩儿了。小明一团体在家守着这台机器。他开端揣摩它是不是像小刚说的那样平安牢靠。过了一会，他开端给机器成心传送一些假的题解（只保证每行或每列或每九宫格的数字不反复），试图经过这种试错来找出机器里设置的实验序列。渐渐的，小明把机器里的实验序列都推断出来了。他既兴奋又懊丧，你能帮小明设计一个更好的证明机吗？

透过故事看实质

故事讲完了，置信大家对零知识证明有了一个大约的印象。零知识证明的实质就是在不揭晓我所晓得或拥有的某样东西的前提下，向他人证明我有很大几率（这点很重要，零知识证明说究竟是一个概率上的证明）的确晓得或拥有这个东西。

故事里要证明的东西就是一个数独题的解，小明让小红每次随机抽取行，列，九宫格的卡片，并搜集在一同随机打乱，小红经过拆开袋子并不能晓得题解，但是却能置信小明很大几率的确晓得题解。

这个故事里的zk-SNIPM也是半开玩笑地暗指了零知识证明如今最普遍的zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）算法。故事中的zk-SNIPM虽然存在破绽，但是他还有改良的余地，比方用一台扫描仪把第一次卡片的组合就全扫描上去，然后一次性同时验证一切的实验序列。这样就很难经过试错的方式来破解机器。

小明和小红之间最开端那种互动式的证明办法暗指的是交互式零知识证明（interactive zero-knowledge proof）。交互式零知识证明需求验证方（小红）在证明方（小明）放好答案（commitment）后，不时的发送随机实验。假如验证和证明单方事前串通好，那么他们就可以在不晓得真实答案的状况下开挂（simulate/forge a proof）。

非交互式的证明则不需求这种互动。但是会额定需求一些机器或许顺序，并且需求一串实验序列，这个实验序列不能被任何人晓得。有了这么一个顺序和实验序列，证明机就能自动算出一个证明，并且能避免任何一方作假。

主打匿名性的区块链加密货币ZCash里用到了零知识证明来保证买卖单方和买卖金额的匿名性。ZCash团队举行过2次故事中的那种典礼，第一次典礼他们甚至拍摄了一个纪录片，第二次典礼中一组人甚至不惜代价去切尔诺贝利核事故发作地取来了带有核辐射的废料，然后在地面中用应用核辐射来生成随机数。 有兴味的各位可以去看看ZCash典礼的相关材料，十分风趣。

雷锋网版权文章，未经受权制止转载。概况见。