引言

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

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

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

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

“證明” 的前世今生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交互式證明

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

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

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

· 零

· 知識(shí)

· 證明

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

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

· 知識(shí)：這里就是指的就是 w。

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

好了，證明也就是黑科技部分還沒講。看官們不要急，且聽我慢慢道來。

零知識(shí)證明有什么用處？

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

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

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

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

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

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

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

零知識(shí)證明的一些用處：

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

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

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

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

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

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

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

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

舉例：地圖三染色問題

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

下面我們?cè)O(shè)計(jì)一個(gè)交互協(xié)議：

「證明者」Alice

「驗(yàn)證者」 Bob

Alice 手里有一個(gè)地圖三染色的答案，請(qǐng)見下圖。這個(gè)圖總共有 6 個(gè)頂點(diǎn)，9 條邊。

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

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

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

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

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

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

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

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

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

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

信息 vs. 知識(shí)

· 信息 「InformaTIon」

· 知識(shí) 「Knowledge」

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

假如 Alice 告訴 Bob 2^2^41-1這個(gè)數(shù)是一個(gè)質(zhì)數(shù)，很顯然這個(gè)是「知識(shí)」，因?yàn)橐愠鰜磉@個(gè)數(shù)是不是一個(gè)質(zhì)數(shù)，這需要耗費(fèi)大量的算力。

假如 Alice 告訴 Bob，總共有兩個(gè)頂點(diǎn)用了綠顏色，那么 Bob 就獲得了寶貴的「知識(shí)」，因?yàn)榛谒麆倓偒@取的這個(gè)信息，Bob 可以用更短的時(shí)間用一臺(tái)圖靈機(jī)去求解三染色問題。假如 Alice 又透露給 Bob，最左邊的頂點(diǎn)顏色是用橙色，那么很顯然，這個(gè)「信息」對(duì)于 Bob 求解問題并沒有實(shí)質(zhì)上的幫助。

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

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

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

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

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

可驗(yàn)證計(jì)算與電路可滿足性問題

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

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

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

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

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

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

這里是思考時(shí)間，大家可以想個(gè)五分鐘 ……

（五分鐘后……）

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

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

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

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

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

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

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

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

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

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

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

黑科技

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

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

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

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

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

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

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

寫在最后

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

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