LIC:探索零知識證明系列 | 從「模擬」理解零知識證明：平行宇宙與時光倒流_SpongeBob

IknowthatIknownothing——蘇格拉底

相信很多人都聽說過零知識證明，但是只有極少數人聽說過模擬，然而模擬是理解零知識的關鍵。

我們在第一篇文章『初識「零知識」與「證明」』中介紹了一個簡單的零知識交互系統：地圖三染色問題。那么這個系統真的是零知識的嗎？我們為什么要相信這個結論呢？有證明嗎？在Alice與Bob的對話過程中，如果不零知識，Alice就被坑了。交互式系統的設計者「我」需要讓Alice確信，這個對話確實是零知識的。

如果從直覺主義角度解釋，要證明一個交互系統中存在信息泄露，那么你只需要指證：第幾個bit導致信息泄露即可；但如果要證明不存在信息泄露，那么你要對著所有信息流中的所有bit說，這從1，2，3，4，5，……編號的bit都沒泄露任何信息。看官們，這是不是很難？

本文約八千字，略微燒腦。

安全的定義與不可區分性

首先，一個交互式系統，也就是一個對話，它的「零知識」需要證明。畢竟，現代密碼學是建立在嚴格的形式化系統之上。在證明之前，還需要明確「安全假設」到底有哪些。所謂安全假設，比如我們說一個系統的權限隔離做得無比精確，每一個用戶只能看到被授權的信息，但是這基于一個安全假設：管理員賬號沒有被破解。又比如在手機銀行軟件里，只能通過短信認證碼，才能完成轉賬功能，這也基于一個安全假設：你的手機SIM卡沒有被克隆。如果我們深入地分析每一個我們感覺安全的系統，都存在大量的似乎不那么穩固的安全假設。比特幣私鑰安全嗎？比特幣賬戶的安全假設也不少：首先你的助記詞不能讓別人知道，手機錢包里私鑰保存加密算法足夠強，密鑰派生算法正規，你不能忘記助記詞，等等等。

脫離安全假設來談安全都是在耍流氓。一切安全都有前提的。只有經過數學證明之后，大家才能夠確信這個算法/方案的安全性基于一些非常明確的「安全假設」。

在證明之前，還缺少一個東西，那就是「安全定義」。在多數人的認知系統中，安全就是一個框，什么都可以往里裝。大家應該好好提醒下自己，當談論安全二字的時候，有沒有想過到底什么是安全？怎么算安全？

「安全」需要有一個數學意義上的嚴格定義

偉大的科學家香農從信息論的角度給出了一個非常靠譜的安全性定義：

完美安全：假設你是一個攻擊者，你通過密文獲取不到任何有價值的信息，破解的唯一手段就是靠瞎蒙。

大家想一想，這個定義很有趣，通過密文獲取不到信息，這就意味著你沒有獲得任何額外的計算能力，能夠幫助讓你以更短的時間來計算出明文。

但是這個定義太完美，以至于使用的加密算法都很難滿足這個安全性定義。后來Goldwasser與Micali等人寫了另一篇載入史冊的經典『概率加密』。

在這篇論文中定義了這樣一個概念：語義安全。所謂語義安全在完美安全的定義上放松了些要求。

語義安全：假設你是一個攻擊者，你通過密文在多項式時間內計算不出來任何有價值的信息。

好了，這個看起來靠譜多了。接下來一個問題就是，怎么理解「計算不出來信息」這個概念？這看來要對信息進行度量，信息的定義又是什么呢？

我們又引入一個概念——「不可區分性」，來重新表述加密算法的安全性：假設你是一個攻擊者，而我有一個加密算法：

英國上議院兩位議員對英國央行正在探索實施的數字英鎊感到一些擔憂:金色財經報道，英國央行正在探索實施數字英鎊的技術，而議會一直保持沉默，英國上議院兩位議員表達了一些擔憂，包括隱私和犯罪活動。[2023/6/2 11:53:10]

你隨機產生兩段等長的明文，m1=「白日依山盡，黃河入海流」，m2=「燙燙燙燙燙，燙燙燙燙燙」

你把這兩段明文，m1與m2交給我

我隨機挑選一個明文，不告訴你是哪一個，然后進行加密，產生一個密文c

我把密文c出示給你看，讓你猜這個c究竟是由唐詩加密產生，還是亂碼加密產生

如果你用一臺計算機來破解c，在多項式時間內破解不出來，也就是說你沒辦法區分c的來源，那么就說明加密算法是語義安全的

OK，理解完「不可區分性」，我們再回到「零知識」，如何證明一個交互式系統是「零知識」呢？首先我們要定義下零知識這個概念。

注：不可區分性是概率意義上的不可區分；在學術上，它可以分為「完全不可區分」，「統計不可區分」，還有「計算不可區分」。在本文中，我們暫時不需要理解這些概念的差別。

遇見模擬器

先開個腦洞，設想在平行宇宙中，有兩個平行的世界，一個叫做「理想世界」，另一個叫做「現實世界」。我們每一個個體可以在兩個平行世界中愉快地玩耍，但是兩個世界的普通人無法互相感知，也無法互相溝通。

假設「你」是一個很厲害的密碼破解者，而且「你」不是普通人，具備在平行宇宙之間穿梭的能力。而Alice有一個地圖三染色的答案，你的目的是通過和Alice對話來獲取地圖三染色的答案，會話的過程參考上一篇文章的「地圖三染色問題」協議。

繼續腦洞，Alice只存在「現實世界」中；在「理想世界」，Alice被「替換」成了一個長相與聲音一模一樣的個體，我們稱替身為Zlice。下一步，把「你」同時放入兩個世界中，但不讓你知道是你當前位于哪一個世界。你的兩個分身所面對的都是一個“Alice”模樣的人。

再重復一遍，在「現實世界」中，與你對話的是一個真實的，并且誠實的Alice；而在「理想世界」中，與你對話的是Zlice，Zlice雖然相貌語言與Alice并無二致，但差異是，Zlice并不知道「知識」，即不知道一個三染色問題的答案。

接下來在這兩個世界中，你的兩個分身將同時與真假Alice進行對話。神奇的事情發生了，最終在兩個世界中，你的兩個分身都被說服了，都經過n輪挑戰，沒有發現對方作弊，即「你」的兩個分身都認為對方確實知道「答案」。換句話說，「你」沒有能力「區分」出來自己到底在「現實世界」還是「理想世界」，當然也沒能力「區分」和自己對話的究竟是Alice還是Zlice。不僅如此，對于吃瓜群眾我而言，如果把「我」作為觀察者放入任何一個世界中，我會和你一樣「無法區分」出來眼前的這個長相為“Alice”的人到底是真還是假。

下面是燒腦結論：

這個交互系統為何是「零知識」？因為Zlice是沒有任何知識，而且她和Alice不可區分。

我再換個方式解釋：因為你和我都沒辦法區分我們究竟是在哪個世界中，兩個世界發生的交互過程幾乎不可區分，而且其中一個世界中根本就不存在知識，因此，我們說這個交互協議——「地圖三染色問題」是「零知識的」。

上海將建數字貿易國際樞紐港，探索推進數字貿易規則制度建設:上海市副市長宗明表示，上海在培育外貿綜合競爭新優勢、構筑全球貿易樞紐方面包括4個重點，其中包括，建設數字貿易國際樞紐港，探索推進數字貿易規則制度建設，加快建設高質量基礎設施，健全公共服務功能，集聚培育國際化的數字貿易品牌，推動建設一批重要承載區，打造長三角全球數字貿易高地。（澎湃）[2021/4/8 19:58:15]

這里還有個前提，理想世界必須是算法可構造的。然后，有一個「神」，他通過算法「模擬」了一個「理想世界」，其中構造了一個算法叫做Zlice，她沒有「知識」作為輸入，也即「零知識」；除此之外，「理想世界」與「現實世界」一模一樣。

設想你在對話過程中，如果真Alice泄露了信息，那么你就能立即區分出面前這個人是真Alice還是Zlice，Zlice是不可能偽裝泄露信息的。因此可以得出結論：

真Alice沒有泄露任何信息。

這個神，被稱為「模擬器」，而在理想世界中，和你對話的這個Zlice幻象其實也是「模擬器」，你在理想世界中，所有能感知到的東西都是模擬器「模擬」出來的。

好了，到這里，我們用「模擬器」這個概念對「零知識」進行了定義。

接下來，我們開始進入證明零知識的環節。

區分兩個世界

證明的零知識過程，等價于構造一個「模擬」算法，這個算法能夠讓模擬器來模擬出一個「沒有知識」的理想世界。如果這個算法存在，而且兩個世界不可區分，那么就證明完畢。

等等，可能「你」會覺得哪里不對勁。

假如說真的存在這種算法，而且它能夠在沒有知識的情況下騙過我，那么在「現實世界」中，不排除真Alice也使用了這樣的算法來欺騙我。這樣一來，我豈不是在兩個世界中都被欺騙了。那么這個交互協議就失去意義了。

其實，這里有個關鍵點，借用電影『盜夢空間』中的劇照，在「理想世界」中有點東西是和「現實世界」本質不同的。這個東西是區分兩個世界的關鍵，而它要讓我們「無法感知」。這個東西不是夢境中的陀螺，它是一種「超能力」，模擬器Simulator所具備的超能力。

比如這樣一種超能力：「時光倒流」。

等等，各位看官，不是剛才我們一直在討論不可區分性嗎？怎么兩個世界又需要區分啦？“我糊涂了”。不要慌，所謂的不可區分性針對的是理想世界中的個體認知而言。而「可區分性」是對位于世界外部的神而言。

設想下在我們周圍，如果有一個人有時空穿越能力，或者他能讓時間回退到一年前，那么我們這些凡夫俗子完全是一臉茫然的，無從感知。那么，如果「模擬器」可以在他構造出的「理想世界」中實現「時間倒流」，那么他就可以達成一些神奇的事情，從而騙過作為驗證者身份的「你」，也能騙過觀察者「我」。對于「你」而言，你明白，在「理想世界」中，時間是可以回退的，但是在「現實世界」中，顯然真Alice不可能擁有超能力。雖然你和我不能區分在哪個世界里，但是至少我們知道在兩個世界中的其中「現實世界」里，對面那個Alice是沒辦法欺騙我們的，當然我們卻不能說出我們到底在哪個世界中。

海南金融局與金融壹賬通簽訂合作 推動法定數字貨幣應用探索:海南省地方金融監督管理局（以下簡稱“海南省金融局”）與平安集團聯營公司深圳壹賬通智能科技有限公司（以下簡稱“金融壹賬通”）簽訂戰略合作框架協議，未來雙方將就建設海南智慧金融及監管服務體系展開深度合作，共同促進海南自由貿易港金融領域的進一步發展。

根據協議，海南金融局與金融壹賬通將發揮各自優勢通力合作、資源共享，落實智慧金融綜合服務體系、地方金融監管數字化體系建設、深化金融科技領域研究多層次合作以及積極推動海南法定數字貨幣應用探索等規劃，共同促進海南自貿港金融領域的繁榮發展。（中國銀行保險報網）[2020/6/16]

到此，交互協議的「零知識」已經證明完了。各位是否已經明白了？我再給大家再梳理下證明思路：

首先「零知識」是為了保護Alice的利益，因為Alice不想在交互過程中透露更多的信息給Bob，不想讓Bob知道她所擁有的秘密w，甚至不想讓Bob從交互的過程中分析出哪怕一丁點的信息。那么怎么保證這一點呢？「模擬器」這時候登場了，它能模擬出一個和現實世界外表一模一樣的「理想世界」，然后「模擬器」在這個世界中可以輕松地騙過任何一個對手，讓對方無法分辨自己是在現實世界中，還是理想世界中。因為「模擬器」手里沒有那個秘密w，「理想世界」是零知識的。又因為兩個世界的不可區分性，所以我們可以得出結論：Alice的交互協議是「零知識」的。

我們來看一個具體的例子，上一篇文章中提到的地圖3染色問題。

地圖三染色問題的零知識證明

回憶一下「地圖三染色問題交互系統」：

第一步：Alice把地圖染色答案做一次完全置換，然后將所有頂點蓋上紙片，交給Bob

第二步：Bob隨機挑選一條邊

第三步：Alice打開指定邊的兩端頂點的紙片，Bob檢驗兩個頂點的顏色是否相同，如果不同則通過，如果相同則失敗

回到第一步，重復n遍

我們接下來就來證明上述這個交互是零知識的，這里先假設驗證者Bob是誠實的，這有助于大家理解這個證明過程。然后我們再討論，如果Bob不誠實的證明方法。

在「理想世界」中，跟Bob對話的是一個「模擬器」，它模擬出了整個世界的樣子。Bob按照三染色問題的交互協議進行交互。模擬器并沒有一個三染色答案，它索性把所有的頂點都染成了灰色。

首先，模擬器模仿Alice，把每個頂點用紙片蓋起來。然后發給Bob。

Bob隨機挑選了一條邊，挑戰證明者。

動態 | 廣州高新區將探索在“區塊鏈+AI”商事服務平臺上增加商事登記“跨境通”服務功能:據科技日報報道，今日，廣州高新區正式啟動商事登記“跨境通”服務。下一步，廣州市黃埔區、廣州開發區、廣州高新區將探索在“區塊鏈+AI”商事服務平臺上增加商事登記“跨境通”服務功能，實現港澳投資者通過微信小程序全流程掌上辦照，并逐步將“跨境通”向其他地區和國家擴展。[2019/10/22]

模擬器這時候不能打開紙片，因為這條邊兩端的顏色都是灰色啊。

這時候，模擬器要發揮「超能力」了，他運用時間倒流的技能，回到對話第一步之前。

模擬器現在處于第一步，他把最下面那條邊的兩端染上任意不同的顏色，然后重新蓋上紙片，并發給Bob。

Bob這時候無法感知到時間已經倒退回第一步了，對他來說，一切都是新鮮的，他「誠實」地再次選擇了最下面的邊。

這時候模擬器就可以放心地打開紙片，讓Bob檢查。Bob很顯然會被騙過。然后Bob一輪輪地重復這個過程，每一次模擬器都能用時間倒流的方式騙過Bob。

于是在理想世界中，模擬器并沒有任何三染色答案的「知識」，卻同樣能騙過Bob，并且從概率上來看，與「現實世界」中被觀察到的交互過程高度地一致。于是上面的過程展示了模擬器的算法的存在性，也就相當于證明了交互系統的「零知識性質」。

不誠實的Bob

在上面的證明過程中，有一個相當強的假設，就是每次時間倒流之后，Bob都會選擇同一條邊。如果Bob每次都會換一條不同的邊呢？沒關系，如果在模擬器第一次實施時間倒流之后，Bob又選擇了不同的邊，那么模擬器可以把顏色打亂之后，再次運行時間倒流，在多次時間倒流之后，Bob極大的概率總會一次選擇模擬器進行染色的那條邊，然后這時候模擬器才走到第三步，打開紙片。

阿里巴巴、洞穴與芝麻開門

在網上眾多的講解「零知識證明」的中文科普文章中，有一個例子流傳非常廣，這就是阿里巴巴與強盜的故事。可惜地是，這些不同版本的故事都只講了一半。那么我接下來講一個不一樣的「阿里巴巴」與「四十大盜」的故事：

在很久很久以前，在一個叫做巴格達的城市里，住著一個人叫阿里巴巴。每天阿里巴巴會到集市上買東西。

有一天，阿里巴巴被一個盜賊搶了錢包，于是他一路追著盜賊到了一個山洞口，然后盜賊就消失了。阿里巴巴發現洞口里面有兩條岔路，如下圖所示。

阿里巴巴不知道盜賊往哪邊跑了，于是他決定去「左邊」岔道看看，很快阿里巴巴就發現這是個死胡同，也不見盜賊蹤影。然后他又去「右邊」岔道檢查，也是個死胡同，不見盜賊蹤影。阿里巴巴自言自語道：「該死的盜賊跑哪去了呢？」

中國比特幣礦工在遭受打擊的壓力之下正在探索海外契機:據外媒報道，目前越來越多的中國比特幣礦工正在探索海外其他司法管轄區域的挖礦業務，盡管中國政府并沒有表示要加大對加密貨幣的鎮壓力度，或是給予礦工更多的壓力，但是中國比特幣礦業未來的不確定性讓許多人正在計劃在海外開展比特幣相關業務。[2017/11/20]

第二天，阿里巴巴又去集市買東西，這次另一個盜賊搶了他的籃子，然后阿里巴巴追著這個盜賊到了昨天同樣的山洞口，然后盜賊又不見了，這一次阿里巴巴決定先去「右邊」岔道看看，沒有發現盜賊，然后再去左邊看看，也同樣不見盜賊。這好奇怪。

第三天，第四天，……，第四十天，同樣的故事上演，阿里巴巴追著第四十個大盜到了神秘的洞口，盜賊就消失了。阿里巴巴想，這個山洞里面一定有機關，于是他躲在「右邊」岔道的盡頭，耐心地等了很長時間，這時一個盜賊跑了進來，走道岔道盡頭之后，念了一個咒語「芝麻開門」。這時候墻壁居然打開了，盜賊跑進去之后，然后墻壁又合上了，這時候另一個受害者追了進來，找了半天，一無所獲。

阿里巴巴隨后等他們走了之后，試驗了一下這個咒語，果然非常有效，而且阿里巴巴發現這個墻壁通向「左邊」岔道。后來，阿里巴巴找到了更換咒語的辦法，并且把一個新咒語和洞穴的地理位置寫在了一張羊皮紙上。

注：到這里，故事并沒有結束....很久很久以后

在很多年后，到了80年代，阿里巴巴的羊皮紙流落到了幾個密碼學家手里，他們跑到巴格達，找到了洞穴的位置，盡管過了幾個世紀，咒語居然仍然有效，這幾個密碼學家興奮地打開墻壁，在兩個岔道之間跑來跑去。

一家電視臺很快知道了這個奇異事件，一個密碼學家MickAli決定向電視觀眾展示他知道這個咒語，首先，電視節目主持人把攝像機架在洞口，然后讓所有人都在山洞口等待，這時候MickAli一個人進入到山洞中，然后主持人拋一個硬幣，來決定讓MickAli從哪個岔道跑出來。為了紀念阿里巴巴與四十大盜，MickAli重復了四十遍每次都成功。

節目非常成功。但很快，另外一個電視臺眼紅，也想拍一個類似的節目，但是MickAli因為簽了獨家協議，沒辦法參與這個新節目。怎么辦呢？第二個電視臺的主持人心生一計，他找了一個和MickAli很像的演員，穿著打扮、姿態和說話口音都模仿MickAli。然后他們開拍了，每次主持人擲硬幣后，都讓這個演員跑出來，但是很顯然，演員并不知道咒語，沒辦法打開那個墻壁。于是有時候演員碰巧會成功，有時候則會失敗，于是演員很辛苦，重復了將近一百次，才成功了四十次。最后這個狡猾的新節目主持人，把錄制視頻進行了剪輯，只保留了成功的片段，錯誤的片段都刪除了。然后這個新節目和MickAli的節目在同一時間，不同頻道播出。然后觀眾們完全無法區分哪個視頻是真的，哪個視頻是假的。第一個電視臺的主持人完全明白MickAli是真正知道墻壁的咒語的人，但是他卻不能把這個事實傳遞給無辜的觀眾們。

看到這里，大家是不是對「模擬」慢慢有了感覺？這里第二個電視臺的主持人通過剪輯視頻的方式，而不是「時間倒流」。他對「理想世界」，也就是電視中播出的內容所在的世界，進行了外部干預，達到了同樣的效果。對理想世界而言，這種剪輯本質上就是一種超能力。

這個故事其實來源于一篇論文『如何向你的孩子解釋零知識證明』，發表在1989年的美密會議上。

模擬與圖靈機

一談到超能力，大家有沒有覺得這玩意不科學。是的，如果我們無腦地用「超能力」來解釋任何事情，那么我們邏輯就無法自恰。在理想世界中，模擬器是不能隨便開掛的，比如模擬器肯定不能直接修改Bob的內部狀態，比如Bob在驗證步驟明明驗證失敗，但是模擬器強硬去把驗證結果改為「接受」，這會導致我們可以證明：「任何的交互系統都是零知識的」，這個錯誤結論。

模擬器不是理想世界中全能的上帝

那么模擬器到底可以是什么呢？模擬器其實只是一個圖靈機。所謂的「時間倒流」，「剪輯錄像」這類的所謂超能力并不是玄乎的超自然能力，而是圖靈機可以實現的功能。計算機專業的朋友們肯定都用過VMWare，虛擬機之類的軟件，本文講的「模擬器」完全可以想象成一個「虛擬機」軟件，它能虛擬出一個計算機環境，這個虛擬環境就是我們上文說的「理想世界」。「時間倒流」如何解釋呢？不知道大家有沒有用過虛擬機軟件的「快照」功能，使用快照的時候，虛擬機軟件可以把整個虛擬計算機的所有狀態保存下來，然后在任意時刻，虛擬機軟件都可以重新回到保存快照的位置繼續運行。

注：其實所謂時間倒流是計算機中的一個基本操作，在程序語言理論中有一個概念叫做Continuation。抽象地講，Continuation表示從現在開始到未來的計算。Continuation這是控制流的一個顯式抽象，而goto，call-with-current-continuation，甚至threadscheduling都可以看做是操作Continuation的操作符。比如采用call/cc，也就是call-with-current-continuation就可以輕松地實現「回溯」功能。保存快照可以理解為保存當前的Continuation，而回到過去的某一刻，就是應用這個Continuation。

不管Zlice還是Bob，還有我們的每一個觀察者，都是一個個可執行程序。這些程序被拷貝到了虛擬機里。Zlice與Bob的會話實際上就是這兩個程序之間的通訊。觀察者是Hook在Zlice與Bob進程IO上的程序。在上文的地圖三染色「理想世界」的誠實Bob，實際上是Bob進程調用了虛擬機的「隨機數發生器」，而這個隨機數發生器是能被Zlice操縱的。「現實世界」是外部運行虛擬機軟件的計算機環境。

大家是不是又有所悟，我再強調一下：

證明零知識的過程，就是要尋找一個算法，或者更通俗點說，寫出一段代碼，它運行在外部計算機系統中，但是實現了虛擬機的功能。而且在虛擬機中，需要有一個不帶有「知識」作為輸入的Zlice，可以騙過放入虛擬機運行的Bob。

如果還沒理解上面我這句話，請時光回退到『區分兩個世界』這一小節，重新思考模擬。:P

柏拉圖的洞穴寓言

模擬無處不在，哥德爾不完備性定理就使用了模擬的概念，用哥德爾數模擬了形式算術。圖靈提出了「UniversalTuringMachine」的概念，這種圖靈機可以模擬自身。

但最早的「模擬」概念，出自『理想國』一書的第七卷中，古希臘哲學家柏拉圖講了這么一則寓言——AllegoryofCave：

設想在一個暗無天日的山洞中，有一排被鎖鏈鎖住的囚徒，他們從小就只能看到前方的墻壁。這些囚徒們身后是一堵墻，再后面有一堆放著火，在火與墻壁之間，有一些人舉著道具和木偶來回走，這樣道具木偶就會在火光映射下在墻壁上投下影子。而這些囚徒們整天就只能看著這些影子。因為這些囚徒們從打出生起，所聞所見就只是前方洞壁上的各種影子，他們會以為所看到的這些影子就是真實的世界。

然而有一天，一個囚徒偶然掙脫鎖鏈，他回頭看到了火。但是他從小到大僅能看到暗淡的影子，他第一次看到了明亮的火光。看到了道具和木偶，假如有人告訴他，這些道具和木偶才是實物，他一定會嗤之以鼻，會堅持認為影子才是真實的。

柏拉圖假設說，如果把這個囚徒強制拖出洞穴，到外面去看到真實的世界，一開始囚徒會不適應真實世界的光亮而感到刺目眩暈，他會因此而憤怒。但是當他慢慢適應了這個世界，看到太陽，樹木，河流，看到星空，他逐漸明白，這個世界比洞穴中那個世界更為優越高級。他再也不想回到黑暗的洞穴生活中了。

過了一段時間，他對洞穴中的囚徒心生憐憫，于是想去把他們都帶出來。但是當他再次返回洞穴中，他因為已經適應了外面明亮的世界，回到洞穴中反而看不清楚。被鎖的囚徒們反而認為他的視力受損，胡言亂語，是個瘋子，最后當他想盡辦法把這群囚徒帶出洞穴時，被囚徒們聯手殺死。

這是則人類命運的寓言，就和那一排被鎖鏈鎖著的囚徒類似，我們以為眼睛看到的就是世界的真相,但實際上，那也許是幻象，就像洞穴墻壁上投下的影子一樣。

未完待續

本文章介紹了理解零知識所需的關鍵概念——模擬。任何一個零知識的協議，都可以通過構造一個「理想世界」來理解。第一次接觸這個概念的讀者需要反復琢磨。

計算機科學中有兩個方法論至關重要，第一個是「抽象」，第二個是「模擬」

回顧一下在地圖三染色問題中，Bob在「理想世界」與「現實世界」中的對話。雖然Bob無法區分兩個世界，但是有一點，他可以確信：現實世界中，Alice沒有超能力。

問題來了，Alice沒有超能力，并不能直接證明Alice真的有答案。萬一這個交互協議并不能保證Alice一定有知識呢？「零知識」保護了Alice的利益，誰來保證Bob的利益呢？這個問題留給下一篇。

參考文獻

初識「零知識」與「證明」.安比實驗室.2019.

ShafiGoldwasserandSilvioMicali,ProbabilisticEncryption,SpecialissueofJournalofComputerandSystemsSciences,Vol.28,No.2,pages270-299,April1984.

Quisquater,J.J.,Quisquater,M.,Quisquater,M.,Quisquater,M.,Guillou,L.,Guillou,M.A.,Guillou,G.,Guillou,A.,Guillou,G.andGuillou,S.,1989,August.Howtoexplainzero-knowledgeprotocolstoyourchildren.InConferenceontheTheoryandApplicationofCryptology(pp.628-631).Springer,NewYork,NY.

柏拉圖and吳獻書,1986.理想國(Vol.1,No.986,p.1).商務印書館.

Goldwasser,Shafi,SilvioMicali,andCharlesRackoff."Theknowledgecomplexityofinteractiveproofsystems."SIAMJournaloncomputing18.1(1989):186-208.

Oded,Goldreich."Foundationsofcryptographybasictools."(2001).

Rackoff,Charles,andDanielR.Simon."Non-interactivezero-knowledgeproofofknowledgeandchosenciphertextattack."AnnualInternationalCryptologyConference.Springer,Berlin,Heidelberg,1991.

Goldreich,Oded,SilvioMicali,andAviWigderson."ProofsthatyieldnothingbuttheirvalidityoralllanguagesinNPhavezero-knowledgeproofsystems."JournaloftheACM(JACM)38.3(1991):690-728.

zkPoD:區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易.安比實驗室.2019.

作者：郭宇

來源：安比實驗室

Tags：LICICEALIBOBSLICE幣justice幣最新消息ALIA幣SpongeBob

MANA