引言

我認(rèn)為區(qū)塊鏈很難稱為一個(gè)“技術(shù)”。它更像是一個(gè)領(lǐng)域，包羅萬(wàn)象?；蛘咝味系卣f(shuō)，區(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à)出一條輔助線后，證明過(guò)程突然顯而易見(jiàn)，然后會(huì)懊悔自己為何沒(méi)想到。

古希臘：「證明」 == 「洞見(jiàn)」

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

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

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

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

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

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

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

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

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

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

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

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

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

目前在計(jì)算機(jī)科學(xué)領(lǐng)域，許多理論的證明已經(jīng)從紙上的草圖變成了代碼的形式，比較流行的「證明編程語(yǔ)言」有 Coq，Isabelle，Agda 等等。采用編程的方式來(lái)構(gòu)造證明，證明的正確性檢查可以機(jī)械地由程序完成，并且許多啰嗦重復(fù)性的勞動(dòng)可以由程序來(lái)輔助完成。數(shù)學(xué)理論證明的大廈正在像計(jì)算機(jī)軟件一樣，逐步地構(gòu)建過(guò)程中。1996 年 12 月 W. McCune 利用自動(dòng)定理證明工具 EQP 證明了一個(gè) 長(zhǎng)達(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年，喬布斯剛剛離開(kāi)蘋(píng)果，而 S. Goldwasser 博士畢業(yè)后來(lái)到了 MIT，與 S. Micali，Rackoff 合寫(xiě)了一篇能載入計(jì)算機(jī)科學(xué)史冊(cè)的經(jīng)典：『交互式證明系統(tǒng)中的知識(shí)復(fù)雜性』［8］。

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

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

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

交互式證明

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

請(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)感覺(jué)了，我們來(lái)嘗試著解讀一下：

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

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

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

好了，證明也就是黑科技部分還沒(méi)講。看官們不要急，且聽(tīng)我慢慢道來(lái)。

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

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

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

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

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

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

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

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

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

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

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

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

· 身份認(rèn)證：用戶可以向網(wǎng)站證明，他擁有私鑰，或者知道某個(gè)只要用戶自己才知道的秘密答案，而網(wǎng)站并不需要知道，但是網(wǎng)站可以通過(guò)驗(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ù)傳輸。

舉例：地圖三染色問(wèn)題

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

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

「證明者」Alice

「驗(yàn)證者」 Bob

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

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

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

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

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

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

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

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

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

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

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

信息 vs. 知識(shí)

· 信息 「InformaTIon」

· 知識(shí) 「Knowledge」

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（五分鐘后……）

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

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

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

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

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

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

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

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

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

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

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

黑科技

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

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

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

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

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

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

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

寫(xiě)在最后

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

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