零知識證明：拋磚引玉

當今密碼學世界中最酷炫的一件事，莫過於那些優美又神秘的專有名詞。我們可以自由的以這些術語給朋克樂隊或 Tumbirs 博客起名字，像是「硬核謂詞(hard-core predicate)」、「陷門函數(trapdoor function)」，或「不可差分密碼分析(impossible differential cryptanalysis)」等熱詞都受到追捧。 當然，我今天要提到的這個術語熱度絕不亞於前面三者，它就是「零知識(zero knowledge)」。

事實上太過受歡迎也不一定是件好事，因為」零知識「概念如此吸引眼球，也導致許多理解錯誤和誤用。許多人將零知識和「非常非常安全」划上等號，並將它與加密系統或匿名網路掛鉤——但這是不正確的，這與真正的零知識協議毫無關係。

這一切都說明 「零知識證明」 是密碼學家所設計出來最強大的工具之一，同時理解的人也相對較少。接下來，我將試著（儘可能）以 非數學 領域的表述方式，介紹什麼是「零知識證明」，並解釋到底是什麼使得它如此特別。同時在此篇和下篇文章中，我們會談及一些常用的零知識證明協議。

零知識起源

「零知識」的概念最早在80年代由麻省理工學院的研究人員 Shafi Goldwasser，Silvio Micali 和 Charles Rackoff 所提出。當時這些人正在研究與交互證明系統相關的問題——即一種理論系統，使得甲方（證明者）可以和乙方（驗證者）交換信息，並藉此說服乙方接受（通過驗證）某個數學論述為真 [作者注1]。

在Goldwasser等人之前，這個領域的研究工作主要聚焦在加強證明系統的可靠性（Soundness）。也就是說原先大家都假設，會有惡意的證明者試圖耍手段，誤導驗證者接受錯誤的論述。但 Goldwasser 等人卻從另一個角度思考了這個問題：如果我們壓根就不相信 驗證者，該怎麼辦？

更具體的來說，他們更關心信息泄露的問題。他們拋出了這樣的思考：「在驗證者的驗證過程中，究竟會獲取多少單純驗證論述真假無需知道的額外信息。」

這裡要強調一下，這個問題不是單純的理論思考，而是在真實、具體的應用中，會面到臨的問題。

我們舉個例子，假設今天在真實世界有個客戶端想要使用密碼登錄web伺服器，在「真實世界」的標準操作流程中，包含將密碼以哈希形式儲存在客戶端。我們可以將」登錄「這個動作視作某種證明——也就是我們要能夠提供一串輸入，這串輸入經過哈希運算後的值與密碼的哈希相同（因為哈希運算的單向性，這串輸入只能是我們的密碼）。但這有個問題是：客戶端實際上 知道 我們的密碼。

大多數系統以這種絕對最糟糕的方式進行「證明」——客戶端直接將原始密碼發送給伺服器，伺服器重新計算密碼哈希並將其與存儲值進行比較。這裡的問題很明顯：在協議結束時，伺服器已經取得我們的明文密碼。 因此，保障現代密碼安全很大程度上要祈禱伺服器不會遭受攻擊。

Goldwasser，Micali 和 Rackoff 等人提出了一種全新的方法來完成「證明」。如果零知識證明真的可行，它將允許我們在證明某些數學陳述為真的同時，保證 不會有任何不相關的信息 被透露出去。

一個「真實世界中」的案例

目前為止，我們的討論還比較抽象。為了讓大家能有更具體的概念，現在我們舉個「真正的」（腦洞微開的）零知識證明例子。

請大家配合我想像一下，現在我是個電信業巨頭，並且打算部署一個新的蜂窩電信網路。這個網路架構圖如下（圖一）。圖中的每個頂點代表一個無線電塔，每一條連線（邊）代表無線電塔信號 兩兩重疊 的區域，這意味著連線上的信號會互相干擾。

這種重疊的情況是有問題的，這表示來自相鄰電塔的信號會互相混淆。幸好在設計之初我預見這個問題，現在通信網路允許傳遞三種波段的信號，這樣就避免了臨近電塔信號干涉的問題。

不過現在我們有了新的挑戰！這個挑戰來自我該如何部署不同的波段，使得相鄰的每兩個電塔不具有相同波段。我們現在用不同顏色來表示不同波段，可以很快找到一種解決方案如下圖二所示：

當然，很多人可能已經發現我剛才是在講述著名的演算法問題——三色問題(graph three-coloring)。大家也就知道，這個問題有趣的地方在：某些非常龐大的網路中，我們很難找到解，甚至連證明問題 有解 都辦不到。事實上三色問題——特別是指這種給定圖形是否有解的決策問題，已經被歸類為NP完全問題。

如果只是上面給的這種示例圖，我們用手就能輕鬆找出解。但如果今天我的無線通信網路規模特別複雜而龐大，我以我所能調配的計算資源都無法找到解答的情況下，我該怎麼辦？我還可以把這個問題 外包 給擁有更龐大算力的人呀！比如我會去找我在谷歌的朋友幫忙。

但這又會導致另一個問題。

假設谷歌動用了大量的算力來幫我找尋有效的著色方法。當然，在我確實得到有效著色方法之前，我是不打算付錢給谷歌的。同樣對谷歌來說，在我付款之前，谷歌也不願意給我著色方法的副本。因此我倆就會陷入僵局。

在現實生活中，可能有點常識都能解決這個困境，但這涉及律師和賬戶託管。不過今天這篇博客不是表述現實生活，而是關於密碼學的。如果你曾經看過任何加密相關文章，你可能知道，解決這種困境的正確方法，就是 想出一個絕對瘋狂的技術手段 ！

一種瘋狂的技術手段（用帽子！）

谷歌的工程師向Micali 等人在麻省理工進行了諮詢。他們想出了一種非常聰明而優雅，甚至不需要任何計算機的方法來打破上述的僵局。我們只需要一個大倉庫、大量的蠟筆和紙張。噢，對了，我們還需要一堆的帽子！[作者注2]

下面是運作原理。

首先，我先進入倉庫，在地板上鋪滿紙張，並在空白的紙上畫出電塔圖。接下來我離開倉庫，換谷歌工程師進入倉庫。谷歌工程師先從一大堆的蠟筆中，隨機選定三個顏色（與上面的例子一樣，我們假設隨機選中紅色/藍色/紫色），並在紙上照著他們的解決方案上色。請注意，用哪種顏色上色並不重要，只要上色的方案是有效的就行！

谷歌工程師們上色結束後，在離開倉庫前，他們會先用帽子把每個紙上的電塔蓋住。所以當我回到倉庫的時候，我會看到如下圖三：

顯然的，這種方法保障了谷歌著色方法的秘密性。但這樣對我一點幫助都沒有！我不知道他們是不是進行了有效著色，或是他們根本沒有著色？

為了消除我的疑慮，谷歌工程師們決定給我機會「挑戰」他們的著色方案。我被允許——隨機選擇圖上的一條邊（兩個相鄰帽子中間的一條線），然後要求谷歌工程師揭開兩邊覆蓋著的帽子，讓我看到他們著色方案中的一小部分，如圖四：

產生兩種結果：

如果兩個點顏色相同（或是根本沒有被著色！），我就可以確信谷歌工程師們對我撒謊。因此我也很清楚我不需要付錢。

如果兩個點顏色不同，那麼谷歌工程師 可能沒有 撒謊。

第一種情況很單純（我不付錢！），第二種情況下我要進行更多考慮。即使我剛才進行了一輪觀察，畢竟我只揭開兩頂帽子，只看到兩個點，仍然不能保證谷歌工程師給我的方法是有效的。假如圖上有 E 條不同邊，在目前條件下谷歌仍有很大的可能是給了我一個無效的著色方案。實際上，在經過一次揭帽觀察後，我仍有高達 (E-1)/E 的概率會被騙（假如有1000條邊，有99.9%的概率這個方案無效。）

好在谷歌決定讓我們再一次、重新進行觀察！

我再次走出倉庫，他們重新鋪上新的紙張，並把空白的電塔圖畫上。谷歌工程師再次從大量蠟筆中隨機選出三種顏色進行著色。他們再次完成有效著色方案，但使用新的三種隨機顏色。

接著帽子又被蓋上啦。我走進倉庫再一次進行「挑戰」，選擇一條新的、隨機的邊。上述邏輯再一次適用。不過這次情況稍好，我會對谷歌工程師們多了那麼一點點信心，相信他們沒有對我撒謊。因為如果他們要欺騙我，他們必須連續兩次都這麼幸運。這當然有可能發生——但發生的可能性相對較低。現在谷歌連續兩次都騙到我的概率為 (E-1)/E(E-1)/E（在1000條邊的情況下，大約有99.8%的可能性，還是很高）。

不過不用擔心，我們不只可以進行兩次挑戰。事實上，我們可以不斷的重複上述的挑戰，直到我們相信谷歌給出了有效的著色方案。

切記不要盲目信我的話。感謝 Javascript，你可以通過簡單的代碼自己驗證上面的邏輯。提醒下，我永遠無法完全相信谷歌工程師是誠實的——我被騙的概率總會存在，即使概率很小。但經過大量的迭代後（E^2），我最終可以將信心提升到一個程度，那時候谷歌只剩下微不足道的概率可能騙到我——這概率低到我可以安全地把錢交給谷歌。

而且你需要知道的是，在這個過程中谷歌同樣受到保護。即使我試圖在挑戰的過程中推敲出他們正確的著色方案，那也不要緊。因為谷歌在每一次迭代前隨機更換三種新的顏色，這讓我的小手段失效了。我獲得的訊息對我毫無幫助，每次挑戰的結果也無法被串聯起來。

是什麼讓它「零知識」?

我對你聲稱，這種挑戰不會泄露任何關於谷歌著色方案的信息，但請你們不要這麼輕易放過我！現代密碼學第一條守則就是：永遠不要在未經證明的情況下相信一個人的宣稱。

Goldwasser, Micali 和 Rackoff提出三個零知識證明的特性，任何零知識都必須滿足。簡單來說：

完整性(Completeness)。如果谷歌說的真話，那麼他們最終能說服我（至少讓我相信可能性非常高）。

安全性(Soundness)。只有當他們說的是真話時，谷歌才有可能說服我。

零知識性(Zero-knowledgeness)（沒錯，就這麼叫）。我無法從中習得任何關於谷歌解決方案的信息。

我們已經討論了完整性的論點。只要重複足夠多次挑戰，這個協議最終能夠說服我（伴隨極低的失誤可能）；安全性也很容易說明，因為如果谷歌試圖欺騙我，會有很大的概率會被我發現。

最難說明的就是「零知識性」。為此，我們必須進行一項非常奇怪的思想試驗。

思想試驗（時光機？）

我們要從一個瘋狂的假設開始。假如谷歌工程師並沒有大家想像中厲害，他們花了數周時間，仍然沒有想出著色問題的解決辦法。而現在只剩下12小時他們就得展示了！他們已經感受到了絕望。絕望使人瘋狂，他們決定 誘導 我相信他們已經完成有效的著色，實際上他們並沒有完成。

他們的想法是潛入 GoogleX 研究室，並「借用」谷歌的時光機的原型機。最初他們想將時間倒退幾年，主要可以獲得更多時間來解決著色問題。不幸的是，與大多數谷歌原型機一樣，這個時光機也有限制——它只能倒退 四分半鐘 的時間。

雖然使用時光機獲得更多工作時間的想法已經不可行，但這有限的功能已經足夠欺騙我。

我不知道這裡到底發生了什麼，但看起來好厲害的樣子

這個計劃要命的簡單！因為谷歌工程師們 實際上不知道 正確的著色方案，他們只能直接從大量蠟筆中隨機選出顏色來塗，然後蓋上帽子。如果他們足夠幸運，我在挑戰時選中不同顏色點，他們就可以鬆口氣，然後繼續進行挑戰，以此類推。

然而不可避免的，我總會在某次挑戰時揭開兩頂帽子，然後發現兩個相同 顏色的點！如果按照正常挑戰規則，谷歌工程師們就原地崩潰了，而這也是時光機派上用場的時候。任何時候谷歌工程師們發現自己身處尷尬的情況（被我找到同色點），他們可以輕鬆挽回頹勢。只要其中一個工程師按下時光機按鈕，讓時間倒退大約四分鐘，然後他們再以新的完全隨機方式著色。接著時間正常前進，挑戰將繼續進行。

實際上，時光機讓谷歌工程師可以挽回在欺騙過程中的任何失誤，同時讓我誤以為這個挑戰過程完全符合規則。從谷歌工程師的角度來看，造假被挑戰出來的情況只有1/3，所以整個挑戰時間只會比誠實情況下（他們有有效解答）的挑戰時間稍微長一點；從我的角度來看，我只會認為這是完全公平的挑戰，因為我不知道時光機的存在。

最後一點，也是最重要的一點。在我的眼中，因為我壓根不知道有時光機存在，所以我看到的每一次挑戰結果，我都會認定這就是真實的！而統計結果也完全一致。值得再呼籲一次，在時光機作弊的情境下，谷歌工程師們絕對不知道正確著色方案。

我到底想說什麼？

請注意，我們剛才舉得是一個計算機模擬 的例子。在現實世界中，時間當然不能倒退，也沒有人能用時光機器騙我，所以基於帽子的挑戰協議是合理且可靠的。這表示在 E^2 輪挑戰後，我應該相信蓋著的圖是被正確著色的，同時谷歌工程師們也遵守協議規則。

方才我們展示的是，如果時間不只能夠前進——特別的是谷歌能「倒退」我的時間，那即使他們沒有正確的著色方案，他們仍然能使挑戰正常進行。

從我的角度出發，這兩種情況有什麼區別？當我們考慮從這兩種情況下的統計分布，會發現根本沒有區別，兩者都表達了相同量級的有效信息。

信不信，這恰好證明了一件非常重要的事情！

具體來講，假設我（驗證者）在正常挑戰協議過程中，有辦法「提取」關於谷歌正確著色方案相關信息。那麼當我被時光機糊弄的時候，我的「提取」策略應該仍然有效。但從我的角度來看，協議運行結果在統計學上毫無二致，我根本無法區別。

因此如果我在「公平的挑戰」和「時光機實驗」下，所能得到的信息量相同；且谷歌在「時光機實驗」中投入的信息量為零，則證明即使在公平的挑戰下，也不會透露任何相關信息給驗證者知道。

又或是這恰好說明計算機科學家有時光機？？是的，我們有。（請務必保密......）

拋開帽子（也拋開時光機）

當然在現實世界我們不會想用帽子來進行協議，谷歌（可能）也沒有真正意義上的時光機。

為了將整件事情串起來，我們先把這個協議放到數字世界。這需要我們構建一個相當於「帽子」功能的等價物——它既能隱藏數字價值，又能同時「綁定」（或「承諾」）創建者，這使得事實被公布後他也不能不認賬。

幸運的是，我們恰好有這種完美的工具。這就是所謂數字承諾方案。這個方案允許一方在保密的情況下「承諾」給出的信息，然後再「公開」承諾的信息。這種承諾可以有很多結構組成，包含（強）加密哈希函數。[作者注3]

我們現在有了承諾方案，也就有一切電子化運行零知識證明的要素。首先證明者(Prover)可以將每個點以數字信息形式」著色「（例如以數字0,1,2），然後為每個數字信息生成數字承諾。這些數字承諾會發送給驗證者(Verifier)，當驗證者進行挑戰的時候，證明者只需要展示對應的兩個點的承諾值就行。

所以我們已經設法消除帽子了。但如何證明這個過程是零知識的？

我們現在身處數字世界，不再需要一台時光機證明與此相關的事。其中的關鍵在於數字世界中，零知識證明協議不是在兩個人 之間運行的，而是在兩方不同的計算機程序 上運行的（或是更規範地說，是概率圖靈機）。

我們現在可以證明下面的定理：如果你能做出一套程序，使得驗證者（計算機）能夠在挑戰過程中」提取「額外的有用信息，則我們就有辦法在程序中加入「時光機」的功能，使得它能夠在證明者沒有投入任何信息的情況下（譯者註：即谷歌工程師沒有正確解），從「假」的挑戰過程獲得等量的額外信息。

因為我們現在討論的是計算機程序，回退、回滾等倒退時間的操作根本不是難事。實際上，我們在日常使用上就不斷在回滾程序。比如帶有快照功能的虛擬機軟體。

通過虛擬機快照進行回滾的例子示意圖。一台初始虛擬機繼續執行，回滾到一個初始的快照中，然後分叉到另一條新路徑中執行

即使你沒有複雜的虛擬機軟體，任何計算機程序也都可以回滾到先前狀態。我們只需要重新啟動程序，並提供完全相同的輸入即可。只要輸入的所有參數（包含隨機數）都是相同的，程序將永遠按照相同的執行路徑操作。這意味著我們可以從頭開始運行程序，並在需要的時間點進行「分叉(forking)」。

最終我們得到以下定理。如果存在任何的驗證者計算機(Verifier)程序，它可以通過與證明者的協議交互過程中提取信息，那麼證明者計算機(Prover)同樣可以通過程序回滾來」欺騙「驗證者——即證明者無法通過挑戰，卻以回滾的方式作弊。我們已經在上面給出了相同的邏輯：如果驗證者程序能從真實的協議中提取信息，那麼它也應該能從模擬的、會回滾的協議中獲取等量的信息。又因為模擬的協議根本沒有放入有效信息，因此沒有可提取的信息。所以驗證者計算機能提取的信息一定始終為零。

這，到底在說什麼？

讓我們回顧一下。根據我們上面的分析，可以知道這個協議是完整且可靠的。該可靠性的論點在我們知道沒有人玩弄時間的前提下都是站得住腳的。也就是說，只要驗證者計算機正常運行，並且保證沒有人在進行回滾作弊的話，協議是完整且可靠的。

同時我們也證明這種協議是零知識的。我們已經證明了任何能成功提取信息的驗證者程序，也一定能從回滾的協議運行中提取信息，而後者是沒有信息放入的。這明顯自相矛盾，間接論證該協議在任何情況下都不會泄露信息。

這一切有個重要的好處。比如在谷歌工程師向我證明他們有正確的著色方案後，我也無法將這個證明過程轉傳給其他人用以證明同樣的事（如，法官），這使得偽造協議證明變成了不可能的事。因為法官也不能保證我們的視頻是真是假，不能保證我們沒有使用時光機不斷回滾修改 證明。所以零知識證明只有在我們自己參與的情況下才有意義，同時我們可以確定這是實時發生的。

證明所有的NP問題！

如果你能堅持看到這兒，我敢打包票你已經準備好迎接一個大新聞！就是我們講了半天的三色電信網路網路，其實並不有趣——至少，本身不咋地。

真正有意思的地方在於，三色問題屬於NP完全問題。簡單來說，這件事的奇妙之處在於任何其他的NP問題都可以轉化為這個問題的實例。在一次不經意的嘗試下，Goldreich, Micali 和 Wigderson 發現「有效的」零知識證明大量存在於這類問題的表述中。其中許多問題比分配蜂窩網格問題有趣得多。你只需要在NP問題中找到想要證明的論述，比如上面的哈希函數示例，然後轉化為三色問題。然後再進行數字版的帽子協議就行啦！

總 結

當然，單純為了興趣來運行這項協議，對任何人來說都是瘋狂而近乎愚蠢的——因為這樣做的成本包含原始狀態和證人的規模大小、轉化為圖形的花費，以及理論上我們必須運行E^2 次才能說服某人這是有效的。

理論上說這個協議是「高效率的」，因為證明的總成本會是輸入狀態的多項式，但其實不然。

所以我們迄今展示的，是要表達這種證明是「可能的」。接下來我們仍然需要找到更多的實例來支撐零知識證明的可用性。

在下一章節，我們會特別談及一些被實際用於各種有效論述證明的方法。我們也會舉出一些真實場景中的例子。另外，因應讀者要求，我也會聊聊為什麼我不是很喜歡SRP（安全遠程密碼協議）。

注 解

作者注1：形式上，交互證明系統的目標是要說服驗證者，使得驗證者相信某特定字元串屬於某種語言。在該系統中，通常證明者的權利非常大（無限的），而驗證者的計算能力是有限的。

作者注2：本文中舉的例子基於Goldwasser, Micali和Rackoff的原始解決方案，而帽子方法則是基於Silvio Micali的解釋。我個人只供獻了一些愚蠢的失誤。

作者注3：我們可以通過哈希函數來構造一個數字承諾的例子。為了承諾一個值「x」，我們需要生成一段（長度適合）的隨機字元串，這段隨機字元又叫做「鹽」。然後輸出數字承諾C = Hash(salt || x)。必須公開「x」和「鹽」，才能通過承諾驗證。任何人都可以通過重新計算哈希來檢查承諾是否有效。這對於函數本身的某些（適當強度）假設是安全的。

作者:Matthew Green

翻譯&校對:IAN LIU & Elisa

本文由作者授權 EthFans 翻譯及再出版。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！