摘要：\u003C\u002Fp\u003E\u003Cp\u003E沒關係，Bob 可以要求 Alice 再來一遍，看下圖\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpFHq99L2aOw\" img_width=\"730\" img_height=\"331\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003EAlice 再次把顏色做一次變換，把藍色改成紫色，改綠色改成棕色，把橙色改成灰色，然後把所有的頂點蓋上紙片。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpEmm5zlmZxN\" img_width=\"730\" img_height=\"344\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E這時候 Alice 揭開這條邊兩端的紙片，讓 Bob 檢查，Bob 發現這兩個頂點的顏色是不同的，那麼 Bob 認爲這次檢驗同構。

"\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpDGnIqUy9fq\" img_width=\"800\" img_height=\"534\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E\u003Cem\u003E本文作者：郭宇\u003C\u002Fem\u003E\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E引言\u003C\u002Fh2\u003E\u003Cp\u003E我認爲區塊鏈很難稱爲一個“技術”。它更像是一個領域，包羅萬象。或者形而上地說，區塊鏈更像一個有機體，融合了各種不同的理論技術。\u003C\u002Fp\u003E\u003Cp\u003E零知識證明是構建信任的重要技術，也是區塊鏈這個有機體中不可缺少的一環。\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E零知識證明是打通鏈上數據與鏈下計算的關鍵技術，也是實現鏈上數據隱私保護的重要途徑\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E要解釋「零知識證明」，我們需要先解釋「證明」，然後解釋什麼是「知識」，最後再解釋什麼是「零知識」。\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E\"證明\" 的前世今生\u003C\u002Fh2\u003E\u003Cp\u003E什麼是證明？很多人可能和我一樣，看到這兩個字，會不禁想起中學考卷中各種三角相似的幾何圖形，當老師在神奇地畫出一條輔助線後，證明過程突然顯而易見，然後會懊悔自己爲何沒想到。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E古希臘：「證明」 == 「洞見」\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E數學證明最早源於古希臘。他們發明（發現）了公理與邏輯，他們用證明來說服對方，而不是靠權威。這是徹頭徹尾的「去中心化」。自古希臘以降，這種方法論影響了整個人類文明的進程。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp3.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpDHB8LBVnoI\" img_width=\"1145\" img_height=\"527\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E上圖是「勾股定理」的巧妙證明。歷史上曾出現過許許多多精巧的證明，神奇的思路，天才的靈感。一旦一個命題被證明，上帝都無能爲力。嗯，對了，還有那個「上帝不是萬能的」證明：上帝不能造出一塊他舉不起來的石頭。\u003C\u002Fp\u003E\u003Cp\u003E一個數學證明往往暗藏無比深刻的「洞見」，相信很多人都看過「費馬大定理」的故事[1]，這個定理證明橫跨四百年，從費馬寫下「這裏空間太小，我寫不下」，到懷爾斯最終登頂，耗費了許多代人的聰明才智。最近如「彭加萊猜想」，稍微帶點年代感的如「哥德巴赫猜想」，還有我非常敬佩的華裔科學家張益唐十年磨一劍，在仔細研究了「Goldston-Pintz-Yıldırım」和 「Bombieri-Friedlander-Iwaniec.」的證明「洞見」之後，證明了「質數間的有界間隔」[2]。\u003C\u002Fp\u003E\u003Cp\u003E自十七世紀，萊布尼茨起，人們就夢想找到一種機械的手段，可以來自動完成證明，而不再依賴天才的靈光一現。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E二十世紀初：「證明」 == 「符號推理」\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E時間到了十九世紀末，康託、布爾、弗雷格、希爾伯特、羅素、布勞威、哥德爾等人定義了形式化邏輯的符號系統。而「證明」則是在利用形式化邏輯的符號語言編寫的推理過程。邏輯本身靠譜麼？邏輯本身「自恰」嗎？邏輯推理本身對不對，能夠證明嗎？這讓 數學家\u002F邏輯學家\u002F計算機科學家 發明（發現） 了符號系統，語法 vs. 語義，可靠 vs. 完備，遞歸 vs. 無窮。（這部分精彩故事請參看『邏輯的引擎』一書[3]）。\u003C\u002Fp\u003E\u003Cp\u003E1910年，羅素髮表了洪(zhuan)荒(tou)鉅著『數學原理』。在書中，羅素與懷特海試圖將數學完整地「形式化」下來。如果能達到這樣的目標，所有的數學成果都將以證明的方式建立在堅實的基礎上。下圖就是『數學原理（卷二）』中的一頁：\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpDJbEN8g4yb\" img_width=\"1281\" img_height=\"1056\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E其中\u003Cem\u003E110.643\u003C\u002Fem\u003E這是一個命題：「1+1=2」，然後接下來就是這個定理的證明。大家可能奇怪，難道 1+1 還需要證明嗎？是的，在數學原理一書中，數字 0，1，2，…… 都有嚴格定義，「加法」、「乘法」、「等於」都要嚴格定義，然後每一步的推理都需要指出依據。證明意味着什麼？證明是可能繁瑣無比的、但是每一步推理都嚴格無誤。書中大量的證明都機械式的，按照公理和推理規則進行一種證明的構造，尋找證明就好像可以交給一個人，然後他無腦在公理與推理規則的集合中進行機械查找。\u003C\u002Fp\u003E\u003Cp\u003E似乎人們距離「定理的自動證明」並不遙遠了。\u003C\u002Fp\u003E\u003Cp\u003E不幸的是，哥德爾在 1931 年證明了「哥德爾不完備性定理」[4]，圖靈在 1936 年證明了圖靈機停機問題的不可判定性[5]。這些成果徹底終結了這個幾百年的幻想。無論公理系統如何精巧設計，都無法抓住所有的真理。\u003C\u002Fp\u003E\u003Cp\u003E證明不僅僅是一個嚴格推理，而且凝結了似乎很難機械化的創造性思維。證明中蘊含了大量的「知識」，每一次的突破，都將我們的認知提升到一個新的高度。不管是「洞見」，還是推理過程中所構造的「算法」，一個定理的證明的內涵往往遠超出定理本身的結論。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E六十年代：「證明」 == 「程序」\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E又過了半個世紀，到了六十年代，邏輯學家 Haskell Curry 和 William Howard 相繼發現了在「邏輯系統」和「計算系統— Lambda 演算」中出現了很多「神奇的對應」，這就是後來被命名的「Curry-Howard Correspondence」。這個發現使得大家恍然大悟，「編寫程序」和「編寫證明」實際在概念上是完全統一的。而在這之後的 50 年，相關理論與技術發展使得證明不再停留在草稿紙上，而是可以用程序來表達。這個同構映射非常有趣：程序的類型對應於證明的定理；循環對應于歸納；……（這裏推薦一本書：『軟件基礎』（Software Foundations 中譯本）[6]）。在直覺主義框架中，證明就意味着構造算法，構造算法實際上就是在寫代碼。(反過來也成立，嗯，碼農碼的不是代碼，是數學證明，:P)\u003C\u002Fp\u003E\u003Cp\u003E目前在計算機科學領域，許多理論的證明已經從紙上的草圖變成了代碼的形式，比較流行的「證明編程語言」有 Coq，Isabelle，Agda 等等。採用編程的方式來構造證明，證明的正確性檢查可以機械地由程序完成，並且許多囉嗦重複性的勞動可以由程序來輔助完成。數學理論證明的大廈正在像計算機軟件一樣，逐步地構建過程中。1996 年 12 月 W. McCune 利用自動定理證明工具 EQP 證明了一個 長達 63 年曆史的數學猜想「Ronbins 猜想」，『紐約時報』隨後發表了一篇題爲「Computer Math Proof Shows Reasoning Power」的文章[7]，再一次探討機器能否代替人類創造性思維的可能性。\u003C\u002Fp\u003E\u003Cp\u003E利用機器的輔助確實能夠有效幫助數學家的思維達到更多的未知空間，但是「尋找證明」仍然是最有挑戰性的工作。「驗證證明」，則必須是一個簡單、機械、並且有限的工作。這是種天然的「不對稱性」。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E八十年代：「證明」 == 「交互」\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E時間撥到1985年，喬布斯剛剛離開蘋果，而 S. Goldwasser 博士畢業後來到了 MIT，與 S. Micali，Rackoff 合寫了一篇能載入計算機科學史冊的經典：『交互式證明系統中的知識複雜性』[8]。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRWG6STA6ab26z5\" img_width=\"4029\" img_height=\"1297\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E他們對「證明」一詞進行了重新的詮釋，並提出了交互式證明系統的概念：通過構造兩個圖靈機進行「交互」而不是「推理」，來證明一個命題在概率上是否成立。「證明」這個概念再一次被拓展。\u003C\u002Fp\u003E\u003Cp\u003E交互證明的表現形式是兩個（或者多個圖靈機）的「對話腳本」，或者稱爲 Transcript。而這個對話過程，其中有一個顯式的「證明者」角色，還有一個顯式的「驗證者」。其中證明者向驗證者證明一個命題成立，同時還「不泄露其他任何知識」。這種就被稱爲「零知識證明」。\u003C\u002Fp\u003E\u003Cp\u003E再強調一遍，證明凝結了「知識」，但是證明過程確可以不泄露「知識」，同時這個證明驗證過程仍然保持了簡單、機械，並且有限性。這聽上去是不是有點「反直覺」？\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E交互式證明\u003C\u002Fh2\u003E\u003Cblockquote\u003E \u003Cp\u003EAlice: 我想向你證明我有一個方程的解，`w^3 - （w+1)^2 + 7 = 0` （方程的解：`w=3`）\u003C\u002Fp\u003E\u003Cp\u003EBob: 好啊，我聽着呢\u003C\u002Fp\u003E\u003Cp\u003EAlice: 但是我不會告訴你 x 具體是多少，除非你願意掏錢，我才告訴你。\u003C\u002Fp\u003E\u003Cp\u003EBob: 可以啊，但是你要先證明你有方程的解，我再給錢你。\u003C\u002Fp\u003E\u003Cp\u003EAlice: @#$%^& （黑科技）\u003C\u002Fp\u003E\u003Cp\u003EBob: ?????? （黑科技）\u003C\u002Fp\u003E\u003Cp\u003EAlice: &*#$@! （黑科技）\u003C\u002Fp\u003E\u003Cp\u003EBob: ??????（黑科技）\u003C\u002Fp\u003E\u003Cp\u003E...... （繼續黑科技）\u003C\u002Fp\u003E\u003Cp\u003EAlice: 好了，完了\u003C\u002Fp\u003E\u003Cp\u003EBob: 好吧，你確實有方程的解，不過是不是我掏了錢，你就會把答案告訴我？\u003C\u002Fp\u003E\u003Cp\u003EAlice: 別廢話，掏錢！\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E上面例子就是一個「交互式證明」。假設Alice知道方程的解，\u003Cem\u003E f(w) = 0\u003C\u002Fem\u003E，那麼 Alice 如何讓 Bob 確信她知道\u003Cem\u003Ew\u003C\u002Fem\u003E呢？Alice 在 「黑科技階段」 告訴了 Bob 一大堆的信息。好了，關鍵問題是，Bob 能不能從 Alice 所說的一大堆信息中猜出\u003Cem\u003Ew\u003C\u002Fem\u003E到底是幾，或者能分析出關於\u003Cem\u003Ew\u003C\u002Fem\u003E的蛛絲馬跡呢？如果 Bob 有這個能力，Bob也許就沒必要掏錢了，因爲他已經獲得了這個值錢的信息。\u003C\u002Fp\u003E\u003Cp\u003E請注意，如果 Alice 與 Bob 的對話是 「零知識」 的，那麼 Bob 除了知道 \u003Cem\u003Ew\u003C\u002Fem\u003E是\u003Cem\u003Ef(w)=0\u003C\u002Fem\u003E的解之外，不能獲取其它任何關於\u003Cem\u003Ew\u003C\u002Fem\u003E的信息。 這一點非常重要，這是保護 Alice 的利益。\u003C\u002Fp\u003E\u003Cp\u003E現在回顧一下「零知識證明」這個詞，英文叫 「Zero-Knowledge Proof」 。這個詞包含三個關鍵部分：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E零\u003C\u002Fli\u003E\u003Cli\u003E知識\u003C\u002Fli\u003E\u003Cli\u003E證明\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E各位可能已經有點感覺了，我們來嘗試着解讀一下：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E零： Alice 泄露了關於 \u003Cem\u003Ew\u003C\u002Fem\u003E的「零」知識，也就是沒有泄露知識。\u003C\u002Fli\u003E\u003Cli\u003E知識：這裏就是指的就是 \u003Cem\u003Ew\u003C\u002Fem\u003E。\u003C\u002Fli\u003E\u003Cli\u003E證明：就是Alice與Bob對話中的「黑科技部分」。\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E好了，證明也就是黑科技部分還沒講。看官們不要急，且聽我慢慢道來。\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E零知識證明有什麼用處？\u003C\u002Fh2\u003E\u003Cp\u003E一提零知識證明技術，很多人就想到了匿名 Coin，比如 Monero, 比如 ZCash。確實，這幾個 Coin 很好地普及了零知識證明，我本人也是通過 ZCash 才第一次聽說了零知識證明這個詞。但是在更深入地瞭解這個技術之後，深深感覺這個技術的威力遠不止這一點。\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E零知識證明技術可以解決數據的信任問題，計算的信任問題！\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E張三說他有100塊錢，李四說他北大畢業，王五說要和八菲特共進午餐。空口無憑，\u003Cem\u003EShow me the proof\u003C\u002Fem\u003E。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpDKk2htKt4h\" img_width=\"4032\" img_height=\"1719\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E那麼「零知識證明」能解決數據的信任如何理解呢？在上一篇文章『zkPoD: 區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易』[9]裏面，我提到了一個概念「模擬」：\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E零知識證明技術可以「模擬」出一個第三方，來保證某一個論斷是可信的\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E換句話說，當我們收到一個加了密的數據， 然後還有一個零知識證明。這個零知識證明是說 「關於數據的 X 斷言成立」，那麼這等價於有一個天使在我們耳邊悄聲說，「關於數據的X 斷言成立」！\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp9.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpEkW7DCJFgh\" img_width=\"1440\" img_height=\"737\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E對於這個\u003Cem\u003EX 斷言\u003C\u002Fem\u003E，可以非常靈活，它可以是一個\u003Cem\u003ENP\u003C\u002Fem\u003E複雜度的算法。大白話講只要我們能寫一段程序（一個多項式時間的算法）來判斷一個數據是否滿足\u003Cem\u003EX斷言\u003C\u002Fem\u003E，那麼這個斷言就可以用零知識證明的方式來表達。通俗點講，只要數據判定是客觀的，那麼就零知識證明就適用。\u003C\u002Fp\u003E\u003Cp\u003E零知識證明的一些用處：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E數據的隱私保護：在一個數據表格中，多多少少都有一些信息不想被暴露，比如當年我的成績單，我只想向人證明，我的成績及格了，但是我不想讓別人知道我到底考了61分還是62分，這會很尷尬。我沒有心臟病，但是保險公司需要了解這一點，但是我不想讓保險公司知道我的隱私信息。那我可以證明給保險公司看，我沒有心臟病，但是病歷的全部並不需要暴露。我是一家企業，我想向銀行貸款，我只想向銀行證明我具備健康的業務與還款能力，但是我不想讓銀行知道我們的一些商業祕密。\u003C\u002Fli\u003E\u003Cli\u003E計算壓縮與區塊鏈擴容：在衆多的區塊鏈擴容技術中，Vitalik 採用 zkSNARK 技術能夠給現有的以太坊框架帶來幾十倍的性能提升。因爲有了計算的證明，同樣一個計算就沒必要重複多次了，在傳統的區塊鏈架構中，同樣的計算被重複多次，比如簽名的校驗，交易合法性校驗，智能合約的執行等等。這些計算過程都可以被零知識證明技術進行壓縮。\u003Cbr\u003E端到端的通訊加密：用戶之間可以互相發消息，但是不用擔心服務器拿到所有的消息記錄，同時消息也可以按照服務器的要求，出示相應的零知識證明，比如消息的來源、與發送的目的地。\u003C\u002Fli\u003E\u003Cli\u003E身份認證：用戶可以向網站證明，他擁有私鑰，或者知道某個只要用戶自己才知道的祕密答案，而網站並不需要知道，但是網站可以通過驗證這個零知識證明， 從而確認用戶的身份\u003Cbr\u003E去中心化存儲：服務器可以向用戶證明他們的數據被妥善保存，並且不泄露數據的任何內容。\u003C\u002Fli\u003E\u003Cli\u003E信用記錄：信用記錄是另一個可以充分發揮零知識證明優勢的領域，用戶可以有選擇性的向另一方出示自己的信用記錄，一方面可以有選擇的出示滿足對方要求的記錄分數，同時證明信用記錄的真實性。\u003C\u002Fli\u003E\u003Cli\u003E構造完全公平的線上數字化商品的交易協議[9]。\u003C\u002Fli\u003E\u003Cli\u003E更多的例子，可以是任何形式的數據共享，數據處理與數據傳輸。\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E舉例：地圖三染色問題\u003C\u002Fh2\u003E\u003Cp\u003E下面講一個經典的問題，地圖的三染色問題。如何用三種顏色染色一個地圖，保證任意兩個相鄰的地區都是不同的顏色。我們把這個「地圖三染色問題」轉變成一個「連通圖的頂點三染色問題」。假設每個地區都有一個首府（節點），然後把相鄰的節點連接起來，這樣地圖染色問題可以變成一個連通圖的頂點染色問題。\u003C\u002Fp\u003E\u003Cp\u003E下面我們設計一個交互協議：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E「證明者」Alice\u003C\u002Fli\u003E\u003Cli\u003E「驗證者」 Bob\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003EAlice 手裏有一個地圖三染色的答案，請見下圖。這個圖總共有 6 個頂點，9 條邊。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpElZ6VJTVp2\" img_width=\"730\" img_height=\"300\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E現在 Alice 想證明給 Bob 她有答案，但是又不想讓 Bob 知道這個答案。Alice 要怎麼做呢？\u003C\u002Fp\u003E\u003Cp\u003EAlice 先要對染過色的圖進行一些「變換」，把顏色做一次大挪移，例如把所有的綠色變成橙色，把所有的藍色變成綠色，把所有的綠色變成橙色。然後 Alice 得到了一個新的染色答案，這時候她把新的圖的每一個頂點都用紙片蓋上，然後出示給 Bob 看。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp3.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpEm0Er5bIBU\" img_width=\"730\" img_height=\"341\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E看下圖，這時候 Bob 要出手了（請見下圖），他要隨機挑選一條「邊」，注意是隨機，不讓 Alice 提前預測到的隨機數。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpEmQBVkFTzx\" img_width=\"730\" img_height=\"340\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E假設 Bob 挑選的是最下面的一條邊，然後告訴 Alice。\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpEmm5zlmZxN\" img_width=\"730\" img_height=\"344\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E這時候 Alice 揭開這條邊兩端的紙片，讓 Bob 檢查，Bob 發現這兩個頂點的顏色是不同的，那麼 Bob 認爲這次檢驗同構。這時候，Bob 只看到了圖的局部，能被說服剩下的圖頂點的染色都沒問題嗎？你肯定覺得這遠遠不夠，也許恰好 Alice 蒙對了呢？其它沒暴露的頂點可能是胡亂染色的。\u003C\u002Fp\u003E\u003Cp\u003E沒關係，Bob 可以要求 Alice 再來一遍，看下圖\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpFHq99L2aOw\" img_width=\"730\" img_height=\"331\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003EAlice 再次把顏色做一次變換，把藍色改成紫色，改綠色改成棕色，把橙色改成灰色，然後把所有的頂點蓋上紙片。然後 Bob 再挑選一條邊，比如像上圖一樣，選擇的是一條豎着的邊，然後讓 Alice 揭開紙片看看，如果這時候 Bob 再次發現這條邊兩端的頂點顏色不同，那麼 Bob 這時候已經有點動搖了，可能 Alice 真的有這個染色答案。可是，兩次仍然不夠，Bob 還想再多來幾遍。\u003C\u002Fp\u003E\u003Cp\u003E那麼經過反覆多次重複這三個步驟，可以讓 Alice 作弊並能成功騙過 Bob 的概率會以指數級的方式減小。假設經過 \u003Cem\u003En\u003C\u002Fem\u003E輪之後，Alice 作弊的概率爲\u003C\u002Fp\u003E\u003Cp\u003E這裏 \u003Cem\u003E|E|\u003C\u002Fem\u003E是圖中所有邊的個數， 如果\u003Cem\u003En\u003C\u002Fem\u003E足夠大，這個概率\u003Cem\u003EPr\u003C\u002Fem\u003E會變得非常非常小，變得「微不足道」。\u003C\u002Fp\u003E\u003Cp\u003E可是，Bob 每次看到的局部染色情況都是 Alice 變換過後的結果，無論 Bob 看多少次，都不能拼出一個完整的三染色答案出來。實際上，Bob 在這個過程中，雖然獲得了很多「信息」，但是卻沒有獲得真正的「知識」。\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E信息 vs. 知識\u003C\u002Fh2\u003E\u003Cul\u003E\u003Cli\u003E信息 「Information」\u003C\u002Fli\u003E\u003Cli\u003E知識 「Knowledge」\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E在地圖三染色問題的交互證明中，當重複交互很多次之後，Bob 得到了大量的信息，但是這好比 Alice 發給 Bob 一堆隨機數一樣，Bob 並沒有「知道」更多的東西。打個比方，如果 Alice 告訴 Bob 「1+1=2」，Bob 得到了這個信息，可是 Bob 並沒有額外獲取更多的「知識」，因爲這個事實人人皆知。\u003C\u002Fp\u003E\u003Cp\u003E假如 Alice 告訴 Bob \u003Cem\u003E2^2^41-1\u003C\u002Fem\u003E這個數是一個質數，很顯然這個是「知識」，因爲要算出來這個數是不是一個質數，這需要耗費大量的算力。\u003C\u002Fp\u003E\u003Cp\u003E假如 Alice 告訴 Bob，總共有兩個頂點用了綠顏色，那麼 Bob 就獲得了寶貴的「知識」，因爲基於他剛剛獲取的這個信息，Bob 可以用更短的時間用一臺圖靈機去求解三染色問題。假如 Alice 又透露給 Bob，最左邊的頂點顏色是用橙色，那麼很顯然，這個「信息」對於 Bob 求解問題並沒有實質上的幫助。\u003C\u002Fp\u003E\u003Cp\u003E我們可以嘗試定義一下，如果 Bob 在交互過程中獲得的「信息」，可以幫助提升 Bob 直接破解 Alice 祕密的能力，那麼我們說 Bob 「獲得了知識」。由此可見，知識這個詞的定義與 Bob 的計算能力相關，如果信息並不能增加 Bob 的計算能力，那麼信息不能被稱爲「知識」。比如在 Alice 與 Bob 交互過程中，Alice 每次都擲一個硬幣，然後告訴 Bob 結果，從信息角度看，Bob 得到的信息只是一個「事件」，然而 Bob 並沒有得到任何「知識」，因爲 Bob 完全可以自己來擲硬幣。\u003C\u002Fp\u003E\u003Cp\u003E下面引用『Foundations of Cryptography—— Basic Tools』一書[10]中的總結\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E1. 「知識」是與「計算難度」相關，而「信息」則不是2. 「知識」是與公共所知的東西有關，而「信息」主要與部分公開的東西有關\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E注：曾有人問我，這裏的信息與知識的定義是否與 Kolmogorov 複雜性有關。根據算法信息論，一段字符串的信息量可以用產生字符串的最小程序的長度來測量。這個問題我不是很懂，希望路過的專業人士留言。\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E可驗證計算與電路可滿足性問題\u003C\u002Fh2\u003E\u003Cp\u003E看了上面的地圖三染色問題，大家是不是沒有感覺，好像這只是一個學術問題，如何跟現實問題關聯起來？地圖三染色問題是一個 NP-Complete 問題，這是「計算理論」中的一個名詞。另外有一個叫做「電路可滿足問題」也是同樣是 NP-Complete 問題。NP-Complete 是一類問題，他的求解過程是多項式時間內難以完成的，即「求解困難」，但是驗證解的過程是多項式時間可以完成的，即「驗證簡單」。\u003C\u002Fp\u003E\u003Cp\u003E那什麼是電路呢？下面是三個不同的「算術電路」：\u003C\u002Fp\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002FRXlpFIY4YK74yM\" img_width=\"849\" img_height=\"292\" alt=\"初識「零知識」與「證明」——探索零知識證明系列\" inline=\"0\"\u003E\u003Cp\u003E可以看到一個電路由很多個門組成，其中有加法門，還有乘法門。每一個門有幾個輸入引腳，有幾個輸出引腳。每一個門做一次加法運算，或乘法運算。別看這麼簡單，我們平時跑的（沒有死循環）代碼，都可以用算術電路來表示。\u003C\u002Fp\u003E\u003Cp\u003E這意味着什麼呢？我們下面結合「零知識證明」與「電路可滿足性問題」來試着解決數據的隱私保護問題。\u003C\u002Fp\u003E\u003Cp\u003E下面請思考一個場景：Bob 交給 Alice 一段代碼 \u003Cem\u003EP\u003C\u002Fem\u003E，和一個輸入\u003Cem\u003Ex\u003C\u002Fem\u003E，讓 Alice 來運行一遍，然後把運行結果告訴 Bob。可能這個計算需要消耗資源，而 Bob 把計算過程外包給了 Alice。然後 Alice 運行了一遍，得到了結果\u003Cem\u003Ey\u003C\u002Fem\u003E。然後把\u003Cem\u003E y\u003C\u002Fem\u003E告訴 Bob。下面問題來了：\u003C\u002Fp\u003E\u003Cp\u003E> 如何讓 Bob 在不運行代碼的前提下，相信代碼 \u003Cem\u003EP\u003C\u002Fem\u003E運行的結果一定是\u003Cem\u003Ey\u003C\u002Fem\u003E呢？\u003C\u002Fp\u003E\u003Cp\u003E這裏是思考時間，大家可以想個五分鐘 ……\u003C\u002Fp\u003E\u003Cp\u003E（五分鐘後……）\u003C\u002Fp\u003E\u003Cp\u003EAlice 的一種做法是可以把整個計算過程用手機拍下來，這個視頻裏面包含了計算機 CPU，還有內存，在整個運行過程中的每一晶體管的狀態。很顯然這麼做是不現實的。那麼有沒有更可行的方案呢？\u003C\u002Fp\u003E\u003Cp\u003E答案是 Bob 把程序\u003Cem\u003E P\u003C\u002Fem\u003E轉換成一個完全等價的算術電路，然後把電路交給 Alice。Alice 只要計算這個電路就可以了，然後這個過程是可以用手機拍下來的，或者用紙記下來，如果電路規模沒有那麼大的話。Alice 只要把參數 6 輸入到電路，然後記錄下電路在運算過程中，所有與門相連的引腳線上的值。並且最後的電路輸出引腳的值等於\u003Cem\u003Ey\u003C\u002Fem\u003E，那麼 Bob 就能確信 Alice 確實進行了計算。Alice 需要把電路的所有門的輸入與輸出寫到一張紙上，交給 Bob，這張紙就是一個計算證明。\u003C\u002Fp\u003E\u003Cp\u003E這樣 Bob 完全可以在不重複計算電路的情況下來驗證這張紙上的證明對不對，驗證過程很簡單：\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003EBob 依次檢查每一個門的輸入輸出能不能滿足一個加法等式或者一個乘法等式。\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E比如 1 號門是一個加法門，它的兩個輸入是 3，4，輸出是7，那麼很容易就知道這個門的計算是正確的。當 Bob 檢查完所有的門之後，就能確信：\u003C\u002Fp\u003E\u003Cp\u003EAlice 確確實實進行了計算，沒有作弊。\u003C\u002Fp\u003E\u003Cp\u003E這張紙上的內容就是「滿足」算術電路 `P` 的一個解「Solution」。\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E所謂的電路可滿足性就是指，存在滿足電路的一個解。如果這個解的輸出值等於一個確定值，那麼這個解就能「表示」電路的計算過程。\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E對於 Alice 而言，Bob 如果用這種方式驗證，她完全沒有作弊的空間。但是這種方法很顯然有個弊端：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E弊端一：如果電路比較大，那麼證明就很大，Bob 檢查證明的工作量也很大。\u003C\u002Fli\u003E\u003Cli\u003E弊端二：Bob 在驗證過程中，知道了所有的電路運算細節，包括輸入。\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E\u003Cstrong\u003E黑科技\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E我們再對剛纔的 Alice 與 Bob 的場景做些修改。假如，Alice 自己還有一個祕密，比如說網銀密碼。而 Bob 想知道 Alice 的網銀密碼的長度是不是 20 位長。而 Alice 想了下，告訴他密碼長度應該問題不大。這時候 Bob 把一個計算字符串長度的代碼轉換成了電路 Q，並且發給 Alice。Alice 用電路 Q 算了一下自己的密碼，然後把電路所有門的引腳發給了 Bob，並帶上運算結果 20。\u003C\u002Fp\u003E\u003Cp\u003EWai……t，這是有問題的，Bob 拿到電路運算過程中的所有內部細節之後，不就知道密碼了嗎？是的，Alice 顯然不能這麼做。那麼 Alice 應該怎麼做？\u003C\u002Fp\u003E\u003Cp\u003E答案是有很多種辦法，熱愛區塊鏈技術的讀者最耳熟的就是 zkSNARK[11]，還有zkSTARK[12]，子彈證明BulletProof[13]，以及一些比較小衆的技術，都可以幫 Alice 做到：\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003EAlice 以一種零知識的方式，向 Bob 證明她計算過了電路，並且使用了她的祕密輸入。\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E換句話說，這些「零知識的電路可滿足性證明協議」爲 Alice 提供了強大的武器來向 Bob 證明她的網銀密碼長度爲 20，並且除此之外， Bob 再也得不到任何其它有用的信息。除了網銀密碼，Alice 理論上可以向 Bob 證明任何她的隱私數據的某些特性，但是並不暴露任何別的信息。\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E「零知識的電路可滿足性證明協議」提供了一種最直接的保護隱私\u002F敏感數據的技術\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E最近幾年來，零知識證明構造技術發展日新月異，並且在區塊鏈技術領域得到了越來越多的應用。最新的零知識證明技術，有的技術可以讓 Bob 高速驗證證明（在移動設備上幾毫秒驗證完成）；有的技術可以讓所有喫瓜羣衆幫忙驗證（非交互式零知識證明）；有的技術支持非常小的證明大小（小到幾十個字節）。後續文章我們會逐步展開介紹。\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E寫在最後\u003C\u002Fh2\u003E\u003Cp\u003E無論是精妙的數論定理，地圖三染色問題，還是電路可滿足性問題。證明存在的意義是什麼？所有的證明都體現了「證明」與「驗證」的「不對稱性」。證明可能是一個非常耗費算力，或者腦力的活動，無論是耗時幾百年的「費馬大定理」，還是比特幣中的 POW 證明，這些證明都凝結了在尋找證明過程中所消耗的能量，證明過程可能是超乎尋常的複雜，偶爾需要天才橫空出世。而驗證過程一定（或者應該）是一個非常簡單的，機械的，在（多項式）有效時間內且能終止的活動。某種意義上，這個不對稱性真正體現了證明的意義，展示了零知識證明的價值。\u003C\u002Fp\u003E\u003Cblockquote\u003E \u003Cp\u003E粗略看，「證明」是「邏輯」的產物，但「邏輯」與「計算」卻又有着密不可分的聯繫，大家可能模模糊糊感覺到一些關於「證明」與「計算」之間的關聯，它們貫穿始終：如機械推理、證明表達、交互計算 。這是一個有趣但更宏大的哲學問題。\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003Cp\u003E\u003Cem\u003E提醒：文章內容難免有不準確或不嚴謹的描述，還請各位專業人士撥冗指正。\u003C\u002Fem\u003E\u003C\u002Fp\u003E\u003Cp\u003E\u003C\u002Fp\u003E\u003Ch2\u003E參考文獻\u003C\u002Fh2\u003E\u003Cp\u003E[1] 西蒙, 辛格, 薛密. 費馬大定理: 一個困惑了世間智者 358 年的謎[M]. 上海譯文出版社, 1998.\u003C\u002Fp\u003E\u003Cp\u003E[2] Alec Wilkinson. The Pursuit of Beauty: Yitang Zhang solves a pure-math mystery. The New Yorker. Feb. 2015.\u003C\u002Fp\u003E\u003Cp\u003E[3] 馬丁, 戴維斯, 張卜天. 邏輯的引擎[M]. 湖南科學技術出版社, 2012.\u003C\u002Fp\u003E\u003Cp\u003E[4] Raymond Smullyan. Gödel's Incompleteness Theorems, Oxford Univ.Press. 1991.\u003C\u002Fp\u003E\u003Cp\u003E[5] Turing, Alan. \"On computable numbers, with an application to the Entscheidungsproblem.\" \u003Cem\u003EProceedings of the London mathematical society\u003C\u002Fem\u003E2.1 (1937): 230-265.\u003C\u002Fp\u003E\u003Cp\u003E[6] Pierce, Benjamin C., et al. \"Software foundations.\" 中文譯文: <https:\u002F\u002Fgithub.com\u002FCoq-zh\u002FSF-zh\u003C\u002Fp\u003E\u003Cp\u003E[7] Kolata, Gina. \"Computer math proof shows reasoning power.\" \u003Cem\u003EMath Horizons\u003C\u002Fem\u003E4.3 (1997): 22-25.\u003C\u002Fp\u003E\u003Cp\u003E[8] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. \"The knowledge complexity of interactive proof systems.\" \u003Cem\u003ESIAM Journal on computing\u003C\u002Fem\u003E18.1 (1989): 186-208.\u003C\u002Fp\u003E\u003Cp\u003E[9] zkPoD: 區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易. 安比實驗室. 2019.\u003C\u002Fp\u003E\u003Cp\u003E[10] Oded, Goldreich. \"Foundations of cryptography basic tools.\" (2001). \u003C\u002Fp\u003E\u003Cp\u003E[11] Gennaro, Rosario, et al. \"Quadratic span programs and succinct NIZKs without PCPs.\" Annual\u003C\u002Fp\u003E\u003Cp\u003EInternational Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin, Heidelberg, 2013.\u003C\u002Fp\u003E\u003Cp\u003E[12] Ben-Sasson, Eli, et al. \"Scalable, transparent, and post-quantum secure computational integrity.\" IACR Cryptology ePrint Archive 2018 (2018): 46.\u003C\u002Fp\u003E\u003Cp\u003E[13] Bünz, Benedikt, et al. \"Bulletproofs: Short proofs for confidential transactions and more.\" 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018.\u003C\u002Fp\u003E\u003Cp\u003E\u003Cem\u003E（作者：SECBIT實驗室，內容來自鏈得得內容開放平臺“得得號”；本文僅代表作者觀點，不代表鏈得得官方立場）\u003C\u002Fem\u003E\u003C\u002Fp\u003E"'.slice(6, -6), groupId: '6719671534744519182