引言

我認(rèn)為區(qū)塊鏈很難稱為一個“技術(shù)”。它更像是一個領(lǐng)域，包羅萬象?；蛘咝味系卣f，區(qū)塊鏈更像一個有機(jī)體，融合了各種不同的理論技術(shù)。

零知識證明是構(gòu)建信任的重要技術(shù)，也是區(qū)塊鏈這個有機(jī)體中不可缺少的一環(huán)。

零知識證明是打通鏈上數(shù)據(jù)與鏈下計算的關(guān)鍵技術(shù)，也是實現(xiàn)鏈上數(shù)據(jù)隱私保護(hù)的重要途徑

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

“證明” 的前世今生

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

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

數(shù)學(xué)證明最早源于古希臘。他們發(fā)明（發(fā)現(xiàn)）了公理與邏輯，他們用證明來說服對方，而不是靠權(quán)威。這是徹頭徹尾的「去中心化」。自古希臘以降，這種方法論影響了整個人類文明的進(jìn)程。

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

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

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

二十世紀(jì)初：「證明」 == 「符號推理」

時間到了十九世紀(jì)末，康托、布爾、弗雷格、希爾伯特、羅素、布勞威、哥德爾等人定義了形式化邏輯的符號系統(tǒng)。而「證明」則是在利用形式化邏輯的符號語言編寫的推理過程。邏輯本身靠譜么？邏輯本身「自恰」嗎？邏輯推理本身對不對，能夠證明嗎？這讓 數(shù)學(xué)家/邏輯學(xué)家/計算機(jī)科學(xué)家 發(fā)明（發(fā)現(xiàn)） 了符號系統(tǒng)，語法 vs. 語義，可靠 vs. 完備，遞歸 vs. 無窮。（這部分精彩故事請參看『邏輯的引擎』一書［3］）。

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

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

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

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

證明不僅僅是一個嚴(yán)格推理，而且凝結(jié)了似乎很難機(jī)械化的創(chuàng)造性思維。證明中蘊含了大量的「知識」，每一次的突破，都將我們的認(rèn)知提升到一個新的高度。不管是「洞見」，還是推理過程中所構(gòu)造的「算法」，一個定理的證明的內(nèi)涵往往遠(yuǎn)超出定理本身的結(jié)論。

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

又過了半個世紀(jì)，到了六十年代，邏輯學(xué)家 Haskell Curry 和 William Howard 相繼發(fā)現(xiàn)了在「邏輯系統(tǒng)」和「計算系統(tǒng)— Lambda 演算」中出現(xiàn)了很多「神奇的對應(yīng)」，這就是后來被命名的「Curry-Howard Correspondence」。這個發(fā)現(xiàn)使得大家恍然大悟，「編寫程序」和「編寫證明」實際在概念上是完全統(tǒng)一的。而在這之后的 50 年，相關(guān)理論與技術(shù)發(fā)展使得證明不再停留在草稿紙上，而是可以用程序來表達(dá)。這個同構(gòu)映射非常有趣：程序的類型對應(yīng)于證明的定理；循環(huán)對應(yīng)于歸納；……（這里推薦一本書：『軟件基礎(chǔ)』（Software Foundations 中譯本）［6］）。在直覺主義框架中，證明就意味著構(gòu)造算法，構(gòu)造算法實際上就是在寫代碼。（反過來也成立，嗯，碼農(nóng)碼的不是代碼，是數(shù)學(xué)證明，：P）

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

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

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

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

他們對「證明」一詞進(jìn)行了重新的詮釋，并提出了交互式證明系統(tǒng)的概念：通過構(gòu)造兩個圖靈機(jī)進(jìn)行「交互」而不是「推理」，來證明一個命題在概率上是否成立?！缸C明」這個概念再一次被拓展。

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

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

交互式證明

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

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

現(xiàn)在回顧一下「零知識證明」這個詞，英文叫 「Zero-Knowledge Proof」 。這個詞包含三個關(guān)鍵部分：

· 零

· 知識

· 證明

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

· 零：Alice 泄露了關(guān)于 w 的「零」知識，也就是沒有泄露知識。

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

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

好了，證明也就是黑科技部分還沒講?？垂賯儾灰?，且聽我慢慢道來。

零知識證明有什么用處？

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

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

張三說他有100塊錢，李四說他北大畢業(yè)，王五說要和八菲特共進(jìn)午餐。空口無憑，Show me the proof。

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

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

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

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

零知識證明的一些用處：

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

· 計算壓縮與區(qū)塊鏈擴(kuò)容：在眾多的區(qū)塊鏈擴(kuò)容技術(shù)中，Vitalik 采用 zkSNARK 技術(shù)能夠給現(xiàn)有的以太坊框架帶來幾十倍的性能提升。因為有了計算的證明，同樣一個計算就沒必要重復(fù)多次了，在傳統(tǒng)的區(qū)塊鏈架構(gòu)中，同樣的計算被重復(fù)多次，比如簽名的校驗，交易合法性校驗，智能合約的執(zhí)行等等。這些計算過程都可以被零知識證明技術(shù)進(jìn)行壓縮。

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

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

· 去中心化存儲：服務(wù)器可以向用戶證明他們的數(shù)據(jù)被妥善保存，并且不泄露數(shù)據(jù)的任何內(nèi)容。

· 信用記錄：信用記錄是另一個可以充分發(fā)揮零知識證明優(yōu)勢的領(lǐng)域，用戶可以有選擇性的向另一方出示自己的信用記錄，一方面可以有選擇的出示滿足對方要求的記錄分?jǐn)?shù)，同時證明信用記錄的真實性。

· 構(gòu)造完全公平的線上數(shù)字化商品的交易協(xié)議［9］。

· 更多的例子，可以是任何形式的數(shù)據(jù)共享，數(shù)據(jù)處理與數(shù)據(jù)傳輸。

舉例：地圖三染色問題

下面講一個經(jīng)典的問題，地圖的三染色問題。如何用三種顏色染色一個地圖，保證任意兩個相鄰的地區(qū)都是不同的顏色。我們把這個「地圖三染色問題」轉(zhuǎn)變成一個「連通圖的頂點三染色問題」。假設(shè)每個地區(qū)都有一個首府（節(jié)點），然后把相鄰的節(jié)點連接起來，這樣地圖染色問題可以變成一個連通圖的頂點染色問題。

下面我們設(shè)計一個交互協(xié)議：

「證明者」Alice

「驗證者」 Bob

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

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

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

看下圖，這時候 Bob 要出手了（請見下圖），他要隨機(jī)挑選一條「邊」，注意是隨機(jī)，不讓 Alice 提前預(yù)測到的隨機(jī)數(shù)。

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

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

沒關(guān)系，Bob 可以要求 Alice 再來一遍，看下圖

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

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

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

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

信息 vs. 知識

· 信息 「InformaTIon」

· 知識 「Knowledge」

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

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

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

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

下面引用『FoundaTIons of Cryptography—— Basic Tools』一書［10］中的總結(jié)

「知識」是與「計算難度」相關(guān)，而「信息」則不是

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

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

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

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

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

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

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

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

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

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

（五分鐘后……）

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

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

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

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

比如 1 號門是一個加法門，它的兩個輸入是 3，4，輸出是7，那么很容易就知道這個門的計算是正確的。當(dāng) Bob 檢查完所有的門之后，就能確信：

Alice 確確實實進(jìn)行了計算，沒有作弊。

這張紙上的內(nèi)容就是「滿足」算術(shù)電路 P 的一個解「SoluTIon」。

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

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

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

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

黑科技

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

Wai……t，這是有問題的，Bob 拿到電路運算過程中的所有內(nèi)部細(xì)節(jié)之后，不就知道密碼了嗎？是的，Alice 顯然不能這么做。那么 Alice 應(yīng)該怎么做？

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

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

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

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

最近幾年來，零知識證明構(gòu)造技術(shù)發(fā)展日新月異，并且在區(qū)塊鏈技術(shù)領(lǐng)域得到了越來越多的應(yīng)用。最新的零知識證明技術(shù)，有的技術(shù)可以讓 Bob 高速驗證證明（在移動設(shè)備上幾毫秒驗證完成）；有的技術(shù)可以讓所有吃瓜群眾幫忙驗證（非交互式零知識證明）；有的技術(shù)支持非常小的證明大?。ㄐ〉綆资畟€字節(jié)）。后續(xù)文章我們會逐步展開介紹。

寫在最后

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

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