一个数独引发的惨案：零知识证明（Zero-Knowledge Proof）
這篇文章大部分譯自：https://medium.com/qed-it/the-incredible-machine-4d1270d7363a 原文的作者是著名的Ghost和Spectre 這兩個協(xié)議的創(chuàng)始團隊的領隊Aviv Zohar。原文作者說他的這篇原文又是引用了以下這兩篇學術論文：
老錢覺得原文是零知識證明方面寫的最好最接地氣的科普類的文章。所以想要翻譯一下，順便在原文基礎上加上一些自己的解讀。想要了解零知識證明，或者匿名性極強的區(qū)塊鏈加密貨幣ZCash的朋友不妨讀一讀。
小明，小紅，小剛三個好朋友很喜歡玩數(shù)獨。平日里他們?nèi)齻€也會互相出題給對方做。有時候他們會出一些非常變態(tài)的數(shù)獨題互相挑戰(zhàn)。他們會挑一個人在紙上畫出一個NxN的格子，填上謎面（Constraint），然后交給另外兩人去解。
證明
有一天，小明出了一道非常難的數(shù)獨題，小紅花了很長時間嘗試去解開這個數(shù)獨，但是怎么都解不出結果。小紅覺得小明在耍她，“這題壓根就無解！小明你耍我！”，她跑到小明那抱怨。
“呵呵，我能證明給你看這題是有解的，而且我知道這個解“，小明淡定的回答道。
“好啊“，小紅暗自想著，“哼哼，等你證明給我看之后，我就把解記下來然后去戲耍一下小剛，給他也做一下這題。”
小明接著說：“我會用零知識證明的方法給你證明我會這題的解。也就是說我不會把解給你看，卻能讓你信服我確實有這題的解。”
小紅并不相信他能這樣做到，還在想象小剛被耍的樣子。
承諾
小明拿出81（9x9）張空白的卡片放在桌上，在每張紙上寫上1-9中的一個數(shù)字，他讓小紅轉過身閉上眼，然后把這81張卡片小心翼翼地按照解的排列放在桌上，代表謎底的卡片，數(shù)字面朝下放在桌上；代表謎面的卡片，則數(shù)字面朝上放在桌上。
隨機試驗
小明放好卡片后，讓小紅睜開眼轉過身。小紅很激動，她覺得謎底就要揭曉了，很是開心。她可花了好幾天時間都沒能解出這題。
小明對小紅說：“小紅，你不能偷看這些面朝下的卡片。“，明顯能看出小紅很失望，她以為能看到完整的一個解。“但是我能讓你檢驗這些解：你可以隨意選擇按照行(row)，或者按照列(column)，或者按照3x3的九宮格(box) 來檢驗我的解。你挑一種吧～”
小紅很困惑，嘴上念叨著什么鬼心里想著mmp，然后告訴小明她決定選擇按照行的方法來驗證，小明接著把每一行的9張卡片收起來單獨放到一個麻布袋里。所有卡片都被收完放在了9個麻布袋里。小明接著搖了搖每個麻布袋，把里面的卡片順序都打散。最后把這9個麻布袋交給小紅。
驗證
“好了，你可以打開這些布袋了。“小明對小紅說，“每個布袋里應該都有正好9張，沒有重復數(shù)字的，分別是數(shù)字1-9的卡片。” 小紅打開每個布袋一看，還果真是這樣。
“可這啥都證明不了啊！我也可以這樣做給你看。我只要保證每一行都是1-9這9張卡片，不去管縱列和九宮格里的數(shù)字是不是也都是沒有重復的不就行了。“小紅氣急敗壞的說道。
小明解釋說：“可是我事先也不知道你會選按照行來收集卡片，還是按照列，還是按照九宮格啊。我又不是你肚子里的蛔蟲。。。我是按照題解來放置卡片的，你選啥我都沒在怕的”
小紅想了想，確實，一個數(shù)獨只有真正正確的解才能保證每一行每一列每一個九宮格里的數(shù)字都是沒有重復的1-9。小明如果真的在騙她，小明不會那么理直氣壯，小紅也至少有1/3的概率可以抓到他在騙人。
重復
小紅還是不服氣。覺得小明仍然有可能在騙她，所以要求小明再把卡片復原，按照原來的方法，重新選。這樣接連試了幾次，小紅每次都選一個不一樣的試驗方法。試了好多次都是一樣的結果。小紅這下不得不承認，小明要么運氣非常非常好，每次都能押中小紅會選擇哪種試驗方式，要么就是他確實知道題解，（或者小明會讀心術能預先知道小紅會選什么試驗方式）。小紅很失望，這么多次試驗下來，她還是不知道真正的題解，她只知道每次小明放置卡片的排列里很大幾率每行每列每個九宮格確實都是沒有重復的1-9，這就說明很大幾率這題是有解的，而且小明很大幾率確實知道這題的解。
小明把這種零知識證明的方法也給小剛展示了一遍。從此之后三個好友養(yǎng)成了通過零知識證明去證明給對方看自己知道某題解的習慣。畢竟每個人在解題的時候都花了很大功夫，不想輕易地把題解直接告訴對方。雖然每次零知識證明的過程很花時間，但是他們都樂在其中。
席卷全球的數(shù)獨風暴
逐漸的，小明和小紅發(fā)現(xiàn)全世界有很多數(shù)獨愛好者，他倆決定在斗魚上開一個直播間，直播解數(shù)獨。為了展現(xiàn)自己的聰明才智，每周開播前，小明在粉絲團里隨機抽取一個粉絲遞交的數(shù)獨，直播時，小明會把題解告訴小紅，然后由小紅用零知識證明的方法向觀看直播的老鐵們證明這題有解，并且自己知道題解，老鐵們紛紛表示666并送上飛機火箭。就這樣小明和小紅的直播間人氣暴漲，兩人成為了斗魚的簽約藝人。
開掛
一天，小明來到小紅家準備直播一個非常難的數(shù)獨，可是他發(fā)現(xiàn)他把解出的題解落在自己家了。時間緊迫，要重新算一遍指定趕不上開播時間會被斗魚老板罵。但是他和小紅還是決定開播。開播前小明和小紅說：“咱倆假裝弄一弄零知識證明，我告訴你一會兒我會怎么選試驗方式。你只要確保每次我選的那種試驗方式（每行，或每列，或每個九宮格）里的數(shù)字不要重復就行了。” 小紅同意了。
小剛，在自己家看完了直播，事后小明和小紅把他倆這次作假的方法告訴小剛，小剛義憤填膺的斥責他們倆，“你們這樣做和盧本偉開掛有什么區(qū)別！對得起支持你們的粉絲嗎？我再也不相信你們倆的零知識證明了！”
神奇的機器和非交互式證明 (Non-interactive Proofs)
小剛很不爽。一來他很享受之前和小明和小紅一起玩數(shù)獨，但是現(xiàn)在他覺得掛逼不值得信任。小剛想找另一種方法來保證直播中他倆不能再這樣作假。幾個不眠的夜晚過去之后，小剛告訴小明小紅，他想到了一個好方法。小剛把自己關在屋里忙活了一整天，第二天早上他把小明小紅叫來，給他們展示自己的新發(fā)明：零知識數(shù)獨非交互式證明機（“The Zero-Knowledge Sudoku Non-Interactive Proof Machine” or zk-SNIPM）。
這臺機器基本上就是把小明和小紅之前當面做的那套證明自動化，不再需要人為交互。小明只要把卡片放在傳送帶上，機器會自動選擇按行，或列，或九宮格來收取卡片，放到袋子里打亂順序，然后把袋子通過傳送帶再送出來。然后小明就可以當著鏡頭的面拆開袋子展示里面的卡片。
這臺機器有一個控制面板，打開里面是一串旋鈕，這些旋鈕用來指示每次試驗的選擇（行，列， 九宮格）。
小剛已經(jīng)設置好了試驗的序列，然后把控制面板焊死，以保證小明和小紅不會知道他到底選擇了怎么樣一個試驗序列。
這下小剛很放心，他可以完全信任自己這臺機器，放心的把機器交給小明和小紅，讓他倆下次直播就直接用這臺機器來證明。小剛相信有了這臺機器他倆就沒法再開掛了。
儀式
小明和小紅很嫉妒小剛的這臺機器，并且想也能用這臺機器來驗證小剛自己出的數(shù)獨題。但是問題是，小剛是知道自己選了什么樣的試驗序列的，如果用同一臺機器去驗證小剛自己的數(shù)獨題解，小剛就可以開掛。小明把大伙聚集起來提議讓小剛把控制面板重新打開，然后大家一起來設置控制面板上的試驗序列。小明把這個過程稱為“可信任的初始設置儀式（trusted setup ceremony）”。
小明提議把這臺機器放在一個漆黑的屋子里，把旋鈕上的指示貼紙都撕去。他們?nèi)朔謩e進入這個屋子，小紅還提議大家進房間時蒙上眼來保證隨機性，并且?guī)б豁斿a紙做的金屬帽子（小紅還是懷疑小明多少會一點讀心術，想通過錫紙帽子來屏蔽腦電波信號防止讀心術（side-channel attack））。這樣，最后這些旋鈕所代表的試驗序列他們?nèi)齻€人都沒有辦法知道。就算他們3人中有2人事先商量好自己會怎么選，他們也無法得知第三個人會怎么選，從而沒有辦法作假。這個儀式結束之后，他們一起把控制面板焊死。
破解這臺機器？
一天下午，小紅和小剛出去玩兒了。小明一個人在家守著這臺機器。他開始琢磨它是不是像小剛說的那樣安全可靠。過了一會，他開始給機器故意傳送一些假的題解（只保證每行或每列或每九宮格的數(shù)字不重復），試圖通過這種試錯來找出機器里設置的試驗序列。慢慢的，小明把機器里的試驗序列都推斷出來了。他既興奮又沮喪，你能幫小明設計一個更好的證明機嗎？
透過故事看本質(zhì)
故事講完了，相信大家對零知識證明有了一個大概的印象。零知識證明的本質(zhì)就是在不揭曉我所知道或擁有的某樣東西的前提下，向別人證明我有很大幾率（這點很重要，零知識證明說到底是一個概率上的證明）確實知道或擁有這個東西。
故事里要證明的東西就是一個數(shù)獨題的解，小明讓小紅每次隨機抽取行，列，九宮格的卡片，并收集在一起隨機打亂，小紅通過拆開袋子并不能知道題解，但是卻能相信小明很大幾率確實知道題解。
這個故事里的zk-SNIPM也是半開玩笑地暗指了零知識證明現(xiàn)在最普遍的zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）算法。故事中的zk-SNIPM雖然存在漏洞，但是他還有改進的余地，比如用一臺掃描儀把第一次卡片的組合就全掃描下來，然后一次性同時驗證所有的試驗序列。這樣就很難通過試錯的方式來破解機器。
小明和小紅之間最開始那種互動式的證明方法暗指的是交互式零知識證明（interactive zero-knowledge proof）。交互式零知識證明需要驗證方（小紅）在證明方（小明）放好答案（commitment）后，不斷的發(fā)送隨機試驗。如果驗證和證明雙方事先串通好，那么他們就可以在不知道真實答案的情況下開掛（simulate/forge a proof）。
非交互式的證明則不需要這種互動。但是會額外需要一些機器或者程序，并且需要一串試驗序列，這個試驗序列不能被任何人知道。有了這么一個程序和試驗序列，證明機就能自動算出一個證明，并且能防止任何一方作假。
主打匿名性的區(qū)塊鏈加密貨幣ZCash里用到了零知識證明來保證交易雙方和交易金額的匿名性。ZCash團隊舉行過2次故事中的那種儀式，第一次儀式他們甚至拍攝了一個紀錄片，第二次儀式中一組人甚至不惜代價去切爾諾貝利核事故發(fā)生地取來了帶有核輻射的廢料，然后在高空中用利用核輻射來生成隨機數(shù)。 有興趣的各位可以去看看ZCash儀式的相關資料，非常有趣。
老錢打算接下去再寫幾篇關于零知識證明的系列文章，繼續(xù)介紹零知識證明的正式定義，在以太坊中的應用，以及zk-SNARKs的一些細節(jié)。
https://zhuanlan.zhihu.com/p/34072069
總結
以上是生活随笔為你收集整理的一个数独引发的惨案：零知识证明（Zero-Knowledge Proof）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 分布式入门：常用的分布式基础算法
- 下一篇： 时间序列相关算法与分析步骤