區塊鏈入門 | 探索零知識證明系列（一）：初識「零知識」與「證明」_BOB

引言

我認為區塊鏈很難稱為一個“技術”。它更像是一個領域，包羅萬象。或者形而上地說，區塊鏈更像一個有機體，融合了各種不同的理論技術。

零知識證明是構建信任的重要技術，也是區塊鏈這個有機體中不可缺少的一環。

零知識證明是打通鏈上數據與鏈下計算的關鍵技術，也是實現鏈上數據隱私保護的重要途徑

要解釋「零知識證明」，我們需要先解釋「證明」，然后解釋什么是「知識」，最后再解釋什么是「零知識」。

“證明”的前世今生

什么是證明？很多人可能和我一樣，看到這兩個字，會不禁想起中學考卷中各種三角相似的幾何圖形，當老師在神奇地畫出一條輔助線后，證明過程突然顯而易見，然后會懊悔自己為何沒想到。

古希臘：「證明」==「洞見」

數學證明最早源于古希臘。他們發明了公理與邏輯，他們用證明來說服對方，而不是靠權威。這是徹頭徹尾的「去中心化」。自古希臘以降，這種方法論影響了整個人類文明的進程。

上圖是「勾股定理」的巧妙證明。歷史上曾出現過許許多多精巧的證明，神奇的思路，天才的靈感。一旦一個命題被證明，上帝都無能為力。嗯，對了，還有那個「上帝不是萬能的」證明：上帝不能造出一塊他舉不起來的石頭。

一個數學證明往往暗藏無比深刻的「洞見」，相信很多人都看過「費馬大定理」的故事，這個定理證明橫跨四百年，從費馬寫下「這里空間太小，我寫不下」，到懷爾斯最終登頂，耗費了許多代人的聰明才智。最近如「彭加萊猜想」，稍微帶點年代感的如「哥德巴赫猜想」，還有我非常敬佩的華裔科學家張益唐十年磨一劍，在仔細研究了「Goldston-Pintz-Y?ld?r?m」和「Bombieri-Friedlander-Iwaniec.」的證明「洞見」之后，證明了「質數間的有界間隔」。

自十七世紀，萊布尼茨起，人們就夢想找到一種機械的手段，可以來自動完成證明，而不再依賴天才的靈光一現。

二十世紀初：「證明」==「符號推理」

時間到了十九世紀末，康托、布爾、弗雷格、希爾伯特、羅素、布勞威、哥德爾等人定義了形式化邏輯的符號系統。而「證明」則是在利用形式化邏輯的符號語言編寫的推理過程。邏輯本身靠譜么？邏輯本身「自恰」嗎？邏輯推理本身對不對，能夠證明嗎？這讓數學家/邏輯學家/計算機科學家發明了符號系統，語法vs.語義，可靠vs.完備，遞歸vs.無窮。。

1910年，羅素發表了洪(zhuan)荒(tou)巨著『數學原理』。在書中，羅素與懷特海試圖將數學完整地「形式化」下來。如果能達到這樣的目標，所有的數學成果都將以證明的方式建立在堅實的基礎上。下圖就是『數學原理』中的一頁：

其中110.643這是一個命題：「1+1=2」，然后接下來就是這個定理的證明。大家可能奇怪，難道1+1還需要證明嗎？是的，在數學原理一書中，數字0，1，2，……都有嚴格定義，「加法」、「乘法」、「等于」都要嚴格定義，然后每一步的推理都需要指出依據。證明意味著什么？證明是可能繁瑣無比的、但是每一步推理都嚴格無誤。書中大量的證明都機械式的，按照公理和推理規則進行一種證明的構造，尋找證明就好像可以交給一個人，然后他無腦在公理與推理規則的集合中進行機械查找。

火幣公益負責人Ciara Sun：區塊鏈技術可以提升公益領域的工作效率:8月13日下午，火幣商務副總裁&火幣公益負責人Ciara Sun參加了由財視傳媒主辦，傳播達人匯、未來企業家俱樂部及尚品新消費聯合主辦的“抗疫 ? 自救 ? 崛起——暨’不經歷風雨，怎么見彩虹’2020抗疫特別發布”活動，并進行了《豈曰無衣，與子同裳》的主題演講。

Ciara Sun表示，2020年初疫情爆發后，火幣公益通過全球各地的同事以及合作伙伴，尋找醫療物資。同時，設立醫療物資供給專項基金，捐贈1000萬人民幣用于全球采購醫療物資，贈予有需要的醫療機構和組織。

在這個過程中，由于信息公開透明性低，很多時候無法溯源，例如商品是否過期、物資運送到了哪里等信息很難進行核實。如果將區塊鏈和公益相結合，可以有效的解決這個問題。因為區塊鏈具有公開透明、可溯源的天然優勢，能夠幫助提升公益工作的效率。火幣公益希望利用以區塊鏈技術為導向的公益平臺，為公益注入新的理念并添磚加瓦。[2020/8/13]

似乎人們距離「定理的自動證明」并不遙遠了。

不幸的是，哥德爾在1931年證明了「哥德爾不完備性定理」，圖靈在1936年證明了圖靈機停機問題的不可判定性。這些成果徹底終結了這個幾百年的幻想。無論公理系統如何精巧設計，都無法抓住所有的真理。

證明不僅僅是一個嚴格推理，而且凝結了似乎很難機械化的創造性思維。證明中蘊含了大量的「知識」，每一次的突破，都將我們的認知提升到一個新的高度。不管是「洞見」，還是推理過程中所構造的「算法」，一個定理的證明的內涵往往遠超出定理本身的結論。

六十年代：「證明」==「程序」

又過了半個世紀，到了六十年代，邏輯學家HaskellCurry和WilliamHoward相繼發現了在「邏輯系統」和「計算系統—Lambda演算」中出現了很多「神奇的對應」，這就是后來被命名的「Curry-HowardCorrespondence」。這個發現使得大家恍然大悟，「編寫程序」和「編寫證明」實際在概念上是完全統一的。而在這之后的50年，相關理論與技術發展使得證明不再停留在草稿紙上，而是可以用程序來表達。這個同構映射非常有趣：程序的類型對應于證明的定理；循環對應于歸納；……）。在直覺主義框架中，證明就意味著構造算法，構造算法實際上就是在寫代碼。(反過來也成立，嗯，碼農碼的不是代碼，是數學證明，:P)

目前在計算機科學領域，許多理論的證明已經從紙上的草圖變成了代碼的形式，比較流行的「證明編程語言」有Coq，Isabelle，Agda等等。采用編程的方式來構造證明，證明的正確性檢查可以機械地由程序完成，并且許多啰嗦重復性的勞動可以由程序來輔助完成。數學理論證明的大廈正在像計算機軟件一樣，逐步地構建過程中。1996年12月W.McCune利用自動定理證明工具EQP證明了一個長達63年歷史的數學猜想「Ronbins猜想」，『紐約時報』隨后發表了一篇題為「ComputerMathProofShowsReasoningPower」的文章，再一次探討機器能否代替人類創造性思維的可能性。

利用機器的輔助確實能夠有效幫助數學家的思維達到更多的未知空間，但是「尋找證明」仍然是最有挑戰性的工作。「驗證證明」，則必須是一個簡單、機械、并且有限的工作。這是種天然的「不對稱性」。

八十年代：「證明」==「交互」

時間撥到1985年，喬布斯剛剛離開蘋果，而S.Goldwasser博士畢業后來到了MIT，與S.Micali，Rackoff合寫了一篇能載入計算機科學史冊的經典：『交互式證明系統中的知識復雜性』。

聲音 | 工信部黨組書記苗圩：大數據、區塊鏈等創新應用日趨豐富:12月23日，全國工業和信息化工作會議在京召開。工業和信息化部黨組書記、部長苗圩作了題為“堅定不移貫徹新發展理念 以更大力度推進制造強國和網絡強國建設”的講話。會議指出，加快智能制造標準體系建設。推廣服務型制造、共享制造等新業態新模式，探索人工智能“揭榜掛帥”機制，啟動建設長三角工業互聯網一體化發展示范區、人工智能和車聯網先導區，大數據、區塊鏈等創新應用日趨豐富。（C114通信網）[2019/12/23]

他們對「證明」一詞進行了重新的詮釋，并提出了交互式證明系統的概念：通過構造兩個圖靈機進行「交互」而不是「推理」，來證明一個命題在概率上是否成立。「證明」這個概念再一次被拓展。

交互證明的表現形式是兩個的「對話腳本」，或者稱為Transcript。而這個對話過程，其中有一個顯式的「證明者」角色，還有一個顯式的「驗證者」。其中證明者向驗證者證明一個命題成立，同時還「不泄露其他任何知識」。這種就被稱為「零知識證明」。

再強調一遍，證明凝結了「知識」，但是證明過程確可以不泄露「知識」，同時這個證明驗證過程仍然保持了簡單、機械，并且有限性。這聽上去是不是有點「反直覺」？

交互式證明

Alice:我想向你證明我有一個方程的解，w^3-Bob:好啊，我聽著呢Alice:但是我不會告訴你x具體是多少，除非你愿意掏錢，我才告訴你。Bob:可以啊，但是你要先證明你有方程的解，我再給錢你。Alice:@#$%^&Bob:??????Alice:&*#$@!Bob:??????......Alice:好了，完了Bob:好吧，你確實有方程的解，不過是不是我掏了錢，你就會把答案告訴我？Alice:別廢話，掏錢！

上面例子就是一個「交互式證明」。假設Alice知道方程的解，f(w)=0，那么Alice如何讓Bob確信她知道w呢？Alice在「黑科技階段」告訴了Bob一大堆的信息。好了，關鍵問題是，Bob能不能從Alice所說的一大堆信息中猜出w到底是幾，或者能分析出關于w的蛛絲馬跡呢？如果Bob有這個能力，Bob也許就沒必要掏錢了，因為他已經獲得了這個值錢的信息。

請注意，如果Alice與Bob的對話是「零知識」的，那么Bob除了知道w是f(w)=0的解之外，不能獲取其它任何關于w的信息。這一點非常重要，這是保護Alice的利益。

現在回顧一下「零知識證明」這個詞，英文叫「Zero-KnowledgeProof」。這個詞包含三個關鍵部分：

零

知識

證明

各位可能已經有點感覺了，我們來嘗試著解讀一下：

零：Alice泄露了關于w的「零」知識，也就是沒有泄露知識。

知識：這里就是指的就是?w。

證明：就是Alice與Bob對話中的「黑科技部分」。

零知識證明有什么用處？

一提零知識證明技術，很多人就想到了匿名Coin，比如Monero,比如ZCash。確實，這幾個Coin很好地普及了零知識證明，我本人也是通過ZCash才第一次聽說了零知識證明這個詞。但是在更深入地了解這個技術之后，深深感覺這個技術的威力遠不止這一點。

行情 | 美股區塊鏈概念股普遍收跌:今日美股收盤，美股區塊鏈概念股普遍收跌。柯達收跌0.78%，埃森哲收漲0.37%，Overstock.com收跌7.14%，Riot Blockchain收漲2.17%，Marathon Patent收跌9.37%，Square收跌1.18%。[2019/4/16]

零知識證明技術可以解決數據的信任問題，計算的信任問題！

張三說他有100塊錢，李四說他北大畢業，王五說要和八菲特共進午餐。空口無憑，Showmetheproof。

那么「零知識證明」能解決數據的信任如何理解呢？在上一篇文章『zkPoD:區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易』里面，我提到了一個概念「模擬」：

零知識證明技術可以「模擬」出一個第三方，來保證某一個論斷是可信的

換句話說，當我們收到一個加了密的數據，然后還有一個零知識證明。這個零知識證明是說「關于數據的X斷言成立」，那么這等價于有一個天使在我們耳邊悄聲說，「關于數據的X斷言成立」！

對于這個X斷言，可以非常靈活，它可以是一個NP復雜度的算法。大白話講只要我們能寫一段程序來判斷一個數據是否滿足X斷言，那么這個斷言就可以用零知識證明的方式來表達。通俗點講，只要數據判定是客觀的，那么就零知識證明就適用。

零知識證明的一些用處：

數據的隱私保護：在一個數據表格中，多多少少都有一些信息不想被暴露，比如當年我的成績單，我只想向人證明，我的成績及格了，但是我不想讓別人知道我到底考了61分還是62分，這會很尷尬。我沒有心臟病，但是保險公司需要了解這一點，但是我不想讓保險公司知道我的隱私信息。那我可以證明給保險公司看，我沒有心臟病，但是病歷的全部并不需要暴露。我是一家企業，我想向銀行貸款，我只想向銀行證明我具備健康的業務與還款能力，但是我不想讓銀行知道我們的一些商業秘密。

計算壓縮與區塊鏈擴容：在眾多的區塊鏈擴容技術中，Vitalik采用zkSNARK技術能夠給現有的以太坊框架帶來幾十倍的性能提升。因為有了計算的證明，同樣一個計算就沒必要重復多次了，在傳統的區塊鏈架構中，同樣的計算被重復多次，比如簽名的校驗，交易合法性校驗，智能合約的執行等等。這些計算過程都可以被零知識證明技術進行壓縮。

端到端的通訊加密：用戶之間可以互相發消息，但是不用擔心服務器拿到所有的消息記錄，同時消息也可以按照服務器的要求，出示相應的零知識證明，比如消息的來源、與發送的目的地。

身份認證：用戶可以向網站證明，他擁有私鑰，或者知道某個只要用戶自己才知道的秘密答案，而網站并不需要知道，但是網站可以通過驗證這個零知識證明，從而確認用戶的身份

去中心化存儲：服務器可以向用戶證明他們的數據被妥善保存，并且不泄露數據的任何內容。

信用記錄：信用記錄是另一個可以充分發揮零知識證明優勢的領域，用戶可以有選擇性的向另一方出示自己的信用記錄，一方面可以有選擇的出示滿足對方要求的記錄分數，同時證明信用記錄的真實性。

構造完全公平的線上數字化商品的交易協議。

動態 | 海南自貿區（港）區塊鏈試驗區今日宣布成立:據火星財經消息，今日海南自貿區（港）區塊鏈試驗區宣布成立。該試驗區是海南正式授牌的首個區塊鏈產業試驗區，由海南省工信廳于9月30日正式批復設立，并于10月8日由海南省工信廳廳長王靜向海南生態軟件園總經理楊淳至授牌。王靜表示，鼓勵“試驗區”認真貫徹中央及海南重要發展精神，大膽試、大膽闖、自主改，積極推進制度創新和產業創新，搶占區塊鏈產業制高點，推動區塊鏈技術應用，培育發展千億新產業”。[2018/10/8]

更多的例子，可以是任何形式的數據共享，數據處理與數據傳輸。

舉例：地圖三染色問題

下面講一個經典的問題，地圖的三染色問題。如何用三種顏色染色一個地圖，保證任意兩個相鄰的地區都是不同的顏色。我們把這個「地圖三染色問題」轉變成一個「連通圖的頂點三染色問題」。假設每個地區都有一個首府，然后把相鄰的節點連接起來，這樣地圖染色問題可以變成一個連通圖的頂點染色問題。

下面我們設計一個交互協議:

「證明者」Alice

「驗證者」Bob

Alice手里有一個地圖三染色的答案，請見下圖。這個圖總共有6個頂點，9條邊。

現在Alice想證明給Bob她有答案，但是又不想讓Bob知道這個答案。Alice要怎么做呢？

Alice先要對染過色的圖進行一些「變換」，把顏色做一次大挪移，例如把所有的綠色變成橙色，把所有的藍色變成綠色，把所有的綠色變成橙色。然后Alice得到了一個新的染色答案，這時候她把新的圖的每一個頂點都用紙片蓋上，然后出示給Bob看。

看下圖，這時候Bob要出手了，他要隨機挑選一條「邊」，注意是隨機，不讓Alice提前預測到的隨機數。

假設Bob挑選的是最下面的一條邊，然后告訴Alice。

這時候Alice揭開這條邊兩端的紙片，讓Bob檢查，Bob發現這兩個頂點的顏色是不同的，那么Bob認為這次檢驗同構。這時候，Bob只看到了圖的局部，能被說服剩下的圖頂點的染色都沒問題嗎？你肯定覺得這遠遠不夠，也許恰好Alice蒙對了呢？其它沒暴露的頂點可能是胡亂染色的。

沒關系，Bob可以要求Alice再來一遍，看下圖

Alice再次把顏色做一次變換，把藍色改成紫色，改綠色改成棕色，把橙色改成灰色，然后把所有的頂點蓋上紙片。然后Bob再挑選一條邊，比如像上圖一樣，選擇的是一條豎著的邊，然后讓Alice揭開紙片看看，如果這時候Bob再次發現這條邊兩端的頂點顏色不同，那么Bob這時候已經有點動搖了，可能Alice真的有這個染色答案。可是，兩次仍然不夠，Bob還想再多來幾遍。

那么經過反復多次重復這三個步驟，可以讓Alice作弊并能成功騙過Bob的概率會以指數級的方式減小。假設經過n輪之后，Alice作弊的概率為

金色財經現場報道 中國政法大學商學院院長劉紀鵬：從區塊鏈入手擁抱新經濟:金色財經6月14日現場報道，在青藤鏈盟-中國政法大學節點啟動儀式暨青藤鏈盟研究院-區塊鏈金融法治研究中心成立儀式上，中國政法大學商學院院長劉紀鵬指出，區塊鏈這個話題已經成為全國乃至世界范圍內研究新經濟時代的最熱門的話題，當然也是爭議比較多的話題，因為還有很多人將其與ICO聯系在一起。而如何在新經濟時代加以應用顯得尤為重要，目前商學院資本金融系已經將其作為重要課題進行研究和操作。我們希望從區塊鏈入手，做第一批擁抱新經濟的人，以進一步接近新經濟時代的制高點。[2018/6/14]

這里|E|是圖中所有邊的個數，如果n足夠大，這個概率Pr會變得非常非常小，變得「微不足道」。

可是，Bob每次看到的局部染況都是Alice變換過后的結果，無論Bob看多少次，都不能拼出一個完整的三染色答案出來。實際上，Bob在這個過程中，雖然獲得了很多「信息」，但是卻沒有獲得真正的「知識」。

信息vs.知識

信息「Information」

知識「Knowledge」

在地圖三染色問題的交互證明中，當重復交互很多次之后，Bob得到了大量的信息，但是這好比Alice發給Bob一堆隨機數一樣，Bob并沒有「知道」更多的東西。打個比方，如果Alice告訴Bob「1+1=2」，Bob得到了這個信息，可是Bob并沒有額外獲取更多的「知識」，因為這個事實人人皆知。

假如Alice告訴Bob2^2^41-1這個數是一個質數，很顯然這個是「知識」，因為要算出來這個數是不是一個質數，這需要耗費大量的算力。

假如Alice告訴Bob，總共有兩個頂點用了綠顏色，那么Bob就獲得了寶貴的「知識」，因為基于他剛剛獲取的這個信息，Bob可以用更短的時間用一臺圖靈機去求解三染色問題。假如Alice又透露給Bob，最左邊的頂點顏色是用橙色，那么很顯然，這個「信息」對于Bob求解問題并沒有實質上的幫助。

我們可以嘗試定義一下，如果Bob在交互過程中獲得的「信息」，可以幫助提升Bob直接破解Alice秘密的能力，那么我們說Bob「獲得了知識」。由此可見，知識這個詞的定義與Bob的計算能力相關，如果信息并不能增加Bob的計算能力，那么信息不能被稱為「知識」。比如在Alice與Bob交互過程中，Alice每次都擲一個硬幣，然后告訴Bob結果，從信息角度看，Bob得到的信息只是一個「事件」，然而Bob并沒有得到任何「知識」，因為Bob完全可以自己來擲硬幣。

下面引用『FoundationsofCryptography——BasicTools』一書中的總結

「知識」是與「計算難度」相關，而「信息」則不是

「知識」是與公共所知的東西有關，而「信息」主要與部分公開的東西有關

注：曾有人問我，這里的信息與知識的定義是否與Kolmogorov復雜性有關。根據算法信息論，一段字符串的信息量可以用產生字符串的最小程序的長度來測量。這個問題我不是很懂，希望路過的專業人士留言。

可驗證計算與電路可滿足性問題

看了上面的地圖三染色問題，大家是不是沒有感覺，好像這只是一個學術問題，如何跟現實問題關聯起來？地圖三染色問題是一個NP-Complete問題，這是「計算理論」中的一個名詞。另外有一個叫做「電路可滿足問題」也是同樣是NP-Complete問題。NP-Complete是一類問題，他的求解過程是多項式時間內難以完成的，即「求解困難」，但是驗證解的過程是多項式時間可以完成的，即「驗證簡單」。

那什么是電路呢？下面是三個不同的「算術電路」：

可以看到一個電路由很多個門組成，其中有加法門，還有乘法門。每一個門有幾個輸入引腳，有幾個輸出引腳。每一個門做一次加法運算，或乘法運算。別看這么簡單，我們平時跑的代碼，都可以用算術電路來表示。

這意味著什么呢？我們下面結合「零知識證明」與「電路可滿足性問題」來試著解決數據的隱私保護問題。

下面請思考一個場景：Bob交給Alice一段代碼P，和一個輸入x，讓Alice來運行一遍，然后把運行結果告訴Bob。可能這個計算需要消耗資源，而Bob把計算過程外包給了Alice。然后Alice運行了一遍，得到了結果y。然后把y告訴Bob。下面問題來了：

如何讓Bob在不運行代碼的前提下，相信代碼P運行的結果一定是y呢？

這里是思考時間，大家可以想個五分鐘……

Alice的一種做法是可以把整個計算過程用手機拍下來，這個視頻里面包含了計算機CPU，還有內存，在整個運行過程中的每一晶體管的狀態。很顯然這么做是不現實的。那么有沒有更可行的方案呢？

答案是Bob把程序P轉換成一個完全等價的算術電路，然后把電路交給Alice。Alice只要計算這個電路就可以了，然后這個過程是可以用手機拍下來的，或者用紙記下來，如果電路規模沒有那么大的話。Alice只要把參數6輸入到電路，然后記錄下電路在運算過程中，所有與門相連的引腳線上的值。并且最后的電路輸出引腳的值等于y，那么Bob就能確信Alice確實進行了計算。Alice需要把電路的所有門的輸入與輸出寫到一張紙上，交給Bob，這張紙就是一個計算證明。

這樣Bob完全可以在不重復計算電路的情況下來驗證這張紙上的證明對不對，驗證過程很簡單：

Bob依次檢查每一個門的輸入輸出能不能滿足一個加法等式或者一個乘法等式。

比如1號門是一個加法門，它的兩個輸入是3，4，輸出是7，那么很容易就知道這個門的計算是正確的。當Bob檢查完所有的門之后，就能確信：Alice確確實實進行了計算，沒有作弊。

這張紙上的內容就是「滿足」算術電路P的一個解「Solution」。

所謂的電路可滿足性就是指，存在滿足電路的一個解。如果這個解的輸出值等于一個確定值，那么這個解就能「表示」電路的計算過程。

對于Alice而言，Bob如果用這種方式驗證，她完全沒有作弊的空間。但是這種方法很顯然有個弊端：

弊端一：如果電路比較大，那么證明就很大，Bob檢查證明的工作量也很大。

弊端二：Bob在驗證過程中，知道了所有的電路運算細節，包括輸入。

黑科技

我們再對剛才的Alice與Bob的場景做些修改。假如，Alice自己還有一個秘密，比如說網銀密碼。而Bob想知道Alice的網銀密碼的長度是不是20位長。而Alice想了下，告訴他密碼長度應該問題不大。這時候Bob把一個計算字符串長度的代碼轉換成了電路Q，并且發給Alice。Alice用電路Q算了一下自己的密碼，然后把電路所有門的引腳發給了Bob，并帶上運算結果20。

Wai……t，這是有問題的，Bob拿到電路運算過程中的所有內部細節之后，不就知道密碼了嗎？是的，Alice顯然不能這么做。那么Alice應該怎么做？

答案是有很多種辦法，熱愛區塊鏈技術的讀者最耳熟的就是zkSNARK，還有zkSTARK，子彈證明BulletProof，以及一些比較小眾的技術，都可以幫Alice做到：

Alice以一種零知識的方式，向Bob證明她計算過了電路，并且使用了她的秘密輸入。

換句話說，這些「零知識的電路可滿足性證明協議」為Alice提供了強大的武器來向Bob證明她的網銀密碼長度為20，并且除此之外，Bob再也得不到任何其它有用的信息。除了網銀密碼，Alice理論上可以向Bob證明任何她的隱私數據的某些特性，但是并不暴露任何別的信息。

「零知識的電路可滿足性證明協議」提供了一種最直接的保護隱私/敏感數據的技術

最近幾年來，零知識證明構造技術發展日新月異，并且在區塊鏈技術領域得到了越來越多的應用。最新的零知識證明技術，有的技術可以讓Bob高速驗證證明；有的技術可以讓所有吃瓜群眾幫忙驗證；有的技術支持非常小的證明大小。后續文章我們會逐步展開介紹。

寫在最后

無論是精妙的數論定理，地圖三染色問題，還是電路可滿足性問題。證明存在的意義是什么？所有的證明都體現了「證明」與「驗證」的「不對稱性」。證明可能是一個非常耗費算力，或者腦力的活動，無論是耗時幾百年的「費馬大定理」，還是比特幣中的POW證明，這些證明都凝結了在尋找證明過程中所消耗的能量，證明過程可能是超乎尋常的復雜，偶爾需要天才橫空出世。而驗證過程一定是一個非常簡單的，機械的，在有效時間內且能終止的活動。某種意義上，這個不對稱性真正體現了證明的意義，展示了零知識證明的價值。

粗略看，「證明」是「邏輯」的產物，但「邏輯」與「計算」卻又有著密不可分的聯系，大家可能模模糊糊感覺到一些關于「證明」與「計算」之間的關聯，它們貫穿始終：如機械推理、證明表達、交互計算。這是一個有趣但更宏大的哲學問題。

文章內容難免有不準確或不嚴謹的描述，還請各位專業人士撥冗指正。

參考文獻

西蒙,辛格,薛密.費馬大定理:一個困惑了世間智者358年的謎.上海譯文出版社,1998.

AlecWilkinson.ThePursuitofBeauty:YitangZhangsolvesapure-mathmystery.TheNewYorker.Feb.2015.

馬丁,戴維斯,張卜天.邏輯的引擎.湖南科學技術出版社,2012.

RaymondSmullyan.G?del'sIncompletenessTheorems,OxfordUniv.Press.1991.

Turing,Alan."Oncomputablenumbers,withanapplicationtotheEntscheidungsproblem."?ProceedingsoftheLondonmathematicalsociety?2.1(1937):230-265.

Pierce,BenjaminC.,etal."Softwarefoundations."中文譯文:https://github.com/Coq-zh/SF-zh

Kolata,Gina."Computermathproofshowsreasoningpower."?MathHorizons?4.3(1997):22-25.

Goldwasser,Shafi,SilvioMicali,andCharlesRackoff."Theknowledgecomplexityofinteractiveproofsystems."?SIAMJournaloncomputing?18.1(1989):186-208.

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

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

Gennaro,Rosario,etal."QuadraticspanprogramsandsuccinctNIZKswithoutPCPs."AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.SpringerBerlin,Heidelberg,2013.

Ben-Sasson,Eli,etal."Scalable,transparent,andpost-quantumsecurecomputationalintegrity."?IACRCryptologyePrintArchive?2018(2018):46.

Bünz,Benedikt,etal."Bulletproofs:Shortproofsforconfidentialtransactionsandmore."2018IEEESymposiumonSecurityandPrivacy(SP).IEEE,2018.

作者：郭宇

本文已更新至Github:https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md

來源：安比實驗室

Tags：BOBALILICICEOBOB幣ALIPEslice幣價格ice幣總量

以太坊