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