三個經典範例解釋什麼是「零知識證明」
原文：Zero-knowledge proofs explained in 3 examples
作者：Tian Daphne
翻譯 & 整理：開放隱私計算 & PrimiHub
零知識證明(Zero-knowledge proof)是一種在不洩露陳述內容的情況下證明陳述有效性的方法。它是一個證明系統使使用者能夠公開分享知識或所有權的證明，而不揭示其細節。
在密碼學中，零知識證明允許使用者在不透露祕密內容的情況下，說服其他使用者知道某事或已經做過某事，它是迄今為止最強大的密碼學工具之一。
下面，我們將深入探討了零知識證明的概念，並通過幾個通俗易懂的範例幫助讀者理解它們的工作原理。
一、零知識證明簡史
密碼學中的零知識首次出現在 1985 年 The knowledge complexity of interactive proof systems [GMR85] 論文中，由先驅者 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 提出。他們提供了今天廣泛使用的零知識證明定義：
「零知識協定是一種方法，通過該方法，一方(證明者)可以向另一方(驗證者)證明某個陳述為真，而不揭示任何資訊，除了這個特定陳述為真。」
零知識證明必須滿足三個性質：
- 完備性：如果陳述為真，誠實的驗證者將被誠實的證明者說服。
- 嚴密性：如果陳述為假，沒有不誠實的證明者能夠說服誠實的驗證者。證明系統是誠實的，不允許作弊。
- 零知識性：如果陳述為真，沒有驗證者會獲得除了這個陳述為真之外的任何資訊。
互動式零知識證明要求證明者和驗證者進行來回對話，以完成證明。非互動式零知識證明是指證明者向驗證者傳送單個訊息，驗證者能夠在不需要證明者進一步通訊的情況下檢查證明的有效性。下圖是零知識證明的發展史：
zk-SNARK(Succinct Non-Interactive Arguments of Knowledge) 可能是最流行的零知識證明形式，最早出現在 2011 年的 Bit+11 論文中。到 2013 年，多虧了 Pinocchio PHGR13 論文，零知識證明可以在現實應用中使用，該論文使 zk-SNARKS 適用於一般計算，儘管速度較慢。2016 年提出的 Groth16 演演算法大大降低了計算複雜性，使 zk-SNARKS 非常高效，至今仍然是標準。
然而，可信設定對於這些零知識協定的安全性至關重要。必須使用初始過程生成加密引數，以便能夠執行零知識協定。由第三方執行此操作，以確保加密引數是隨機、不可預測和安全的。
隨後在 2017 年引入了 Bulletproofs(BBBPWM17)，在 2018 年引入了 zk-STARKs(BBHR18)。與前任不同，它們是不需要初始可信設定的範圍證明型別。2019 年的 PlonK 論文實現了通用零知識證明演演算法，這意味著只需要啟動一次可信設定，而與之相比，Groth16 需要每個電路都有一個單獨的可信設定。
由於領域的發展，零知識證明已經從純理論過渡到應用，在區塊鏈、安全通訊、電子投票、存取控制和遊戲中均有實際應用。隨著這些技術繼續投入商業應用，相信未來將會有更多令人興奮的發展來推進這項技術。
以下是一些概念性範例，幫助你在不涉及複雜理論和高階數學的情況下，直觀地理解不同級別的零知識證明（ZKP）。
二、向孩子們解釋零知識證明（Lv.1）
瓦利在哪裡？
在不洩露祕密資訊的情況下證明自己知道某事，可以通過常用的「瓦利在哪裡？」範例來說明。
問題：你和朋友想要找到瓦利。
條件：你知道瓦利在影象中的位置，但你的朋友不相信。你如何向朋友證明你知道瓦利在哪裡，同時又不洩露他具體的位置？
解決辦法：你可以拿出一張大紙，蓋住整個影象，通過一個切口向朋友展示瓦利的影象。這樣做就可以可以證明你真的知道瓦利的位置，但你的朋友不會獲得瓦利的位置，因為相對於影象的確切座標對他來說仍然是未知的。
這是一個非互動式零知識證明的簡單類比。透過孔隙看到瓦利的任何人都能夠證明瓦利的存在，以及證明者知道他在哪裡，同時又不洩露任何其他資訊。
三、向朋友解釋零知識證明（Lv.2）
成員證明範例
問題：當你遇到一個不認識的人，但她聲稱自己也是你所在團隊的成員。你如何知道她說的是真的？
解決辦法：幸運的是，你的團隊有一個帶鎖的保險箱，只有你的團隊成員知道密碼，可以開啟保險箱。因此，寫一條祕密資訊並放入鎖定的保險箱中。具體步驟如下：
- 驗證者寫一條祕密資訊並放入鎖定的保險箱中。
- 符合要求的證明者具有密碼，開啟鎖定的保險箱。
- 證明者將祕密資訊交還給驗證者。
- 驗證者確信證明者真的知道保險箱密碼，因此可以信任。
如果這個陌生人是如她所說是團隊成員，那她就會知道密碼。因此，她將能夠開啟鎖定的保險箱，找到你的祕密資訊，從而向你證明她確實是你團隊的成員。
這是互動式零知識證明的類比。只有真正是該團隊的成員才會知道祕密組合程式碼（密碼），能夠存取鎖定的保險箱，從而在不洩露任何其他資訊的情況下證明他的成員資格。
四、向團隊解釋零知識證明（Lv.3）
不透明定價範例
在這個範例中，你和競爭對手正在從同一供應商購買相同的材料，你想知道每千克是否支付相同的價格。但是，你們之間缺乏足夠的信任來透露各自的價格，你還受到不得分享此資訊的合同約束。
假設材料的市場價格只能為 100、200、300 或 400 每千克，這種情況下我們可以通過零知識證明來解決上述問題。按照以下步驟操作：
- 你和競爭對手想要知道是否支付相同的價格，同時不洩露各自支付的金額。
- 假設有 4 個帶鎖的鎖盒（沒有鑰匙無法開啟），每個盒子上標有 100、200、300 和 400 的數位，以及一個只能放一張紙的小插槽，放置於一個安全的私人房間中。
- 你首先獨自進入房間。由於你每千克支付 200，你拿走了標有 200 的鎖盒的鑰匙，並摧毀了其他盒子的鑰匙，然後你離開房間。
- 你的競爭對手獨自進入房間，帶有 4 張紙，其中 1 張為支票（無具體數額），另外 3 張上面都是叉號。由於你的競爭對手每千克支付 300，他將帶有支票的紙張放入標有 300 的鎖盒中，並將帶有叉號的紙張放入其他鎖盒中，最後離開房間。
- 在他們離開後，你可以帶著只能開啟標有 200 盒子的鑰匙返回。你會發現一張上面有叉號的紙，現在你知道你的競爭對手沒有與你支付相同的金額。
- 你的競爭對手回來後，看到你手上有一張上面有叉號的紙，所以現在他們也知道你沒有與他們支付相同的金額。
如果你得到一張上面有支票的紙，你倆都會知道你支付相同的金額。由於你得到的紙上有叉號，你倆都知道你沒有支付相同的金額，但也不知道對方支付了多少。
你倆離開時只知道你沒有支付相同的金額，但你倆都沒有獲得對方支付了多少的知識。
這是使用原始半範圍證明的互動式零知識證明的另一個類比。重要的是要注意，所有這些範例都有限制，並且必須採用某些假設，但它們足夠形象地說明了它們的工作方式。
五、最後
這篇文章通過 3 個範例層層遞進、簡單易懂的解釋了零知識證明的概念和原理。
通過了解零知識證明的工作原理，會發現零知識證明並不是魔法。目前它在區塊鏈以及需要敏感資訊的各種應用中具有巨大的潛力，例如提供密碼證明、身份證明和成員證明。比如：國外某些銀行中就有用到零知識證明技術，讓他們的客戶能夠在抵押貸款申請中，證明銀行賬戶中的金額而不洩露具體金額等資訊。
PrimiHub 一款由密碼學專家團隊打造的開源隱私計算平臺，專注於分享資料安全、密碼學、聯邦學習、同態加密等隱私計算領域的技術和內容。