5 種難度等級解析零知識證明

電腦科學家 Amit Sahai（加州大學洛杉磯分校薩繆理工程學院教授）在這部 WIRED 製作的影片中，以五種不同的複雜度等級（從兒童到專家）解釋了零知識證明。這個概念透過物理類比進行演示，並以不斷增加的技術深度進行討論，讓每個人都能理解密碼學中最重要的概念之一。

本逐字稿是 WIRED 發布的原始影片逐字稿 (opens in a new tab)的無障礙副本。為了提高可讀性，已進行了輕微的編輯。

簡介 (0:00)

Amit Sahai： 大家好，我是 Amit Sahai，加州大學洛杉磯分校薩繆理工程學院的電腦科學教授。今天，我受邀以五種不斷增加的複雜度等級來解釋零知識證明。

零知識證明是一種讓證明者說服驗證者某個陳述為真的方法，而且除了該陳述為真這個事實之外，不會透露任何額外的資訊。零知識證明正被應用於區塊鏈和加密貨幣中。密碼學家對零知識感到興奮，不僅因為它具有驚人的數學特性，還因為它在許多不同場景中具有令人難以置信的適用性。

第 1 級：兒童 (0:41)

Amit Sahai： 妳最喜歡的科目是什麼？

Chelsea： 我會說是數學。有些小問題實際上可能非常龐大且複雜。這就像謎題一樣。

Amit Sahai： 我也因為同樣的原因熱愛數學。今天，我要告訴妳一個叫做零知識證明的東西。在零知識證明中，有兩個人——一個是證明者，另一個是驗證者。我想向妳證明某件事是真的，但奇怪的是，我想在不告訴妳任何原因的情況下向妳證明它是真的。我記得我第一次聽到這個概念時，我的反應是：等等，什麼？這怎麼可能？

那麼，妳在這張照片中看到了什麼？

Chelsea： 很多企鵝。

Amit Sahai： 沒錯。在這些企鵝之中隱藏著一隻海鸚。妳想試著找找看嗎？妳看到牠在哪裡了嗎？我知道牠在哪裡，但我不想告訴妳。妳相信我嗎？

Chelsea： 相信。

Amit Sahai： 但如果我能向妳證明我知道海鸚在哪裡，卻不向妳透露牠的具體位置呢？讓我展示給妳看。我把那張照片放在這張海報後面。妳要不要透過那個洞看一看？

Chelsea： 我看到海鸚了。

Amit Sahai： 所以當妳看著這塊板子時，我們不知道照片原本在哪裡，對吧？照片的角落是在這裡，所以海鸚完全在這一側嗎？還是照片的角落是在這裡，所以海鸚在另一側？這就是一個非常簡單的零知識證明範例。我說服了妳我知道海鸚在哪裡，但妳沒有學到任何其他資訊。

Chelsea： 你為什麼要研究零知識證明？

Amit Sahai： 當我第一次了解到它們時，我只覺得它們太酷了。但事實證明它們也非常有用——不僅僅是用來找海鸚。如果妳只是輸入密碼，而駭客駭入了電腦，他們就能直接取得妳的密碼。但如果我們能以某種方式使用零知識證明來登入呢？妳將能夠證明妳是 Chelsea，而無需向他們透露任何資訊。如果妳能做到這一點，那將會非常了不起，因為即使駭客駭入了電腦，他們也學不到任何東西——因為連電腦本身也沒有學到任何東西。

所以 Chelsea，用妳自己的話來說，什麼是零知識證明？

Chelsea： 零知識證明是對某個陳述的證明。你不需要向他們展示原因或內容。你只需要向他們展示一小部分，或者只是變某種其實不是魔術的奇怪魔術，他們就會被說服。而且你沒有向他們展示原因或類似的東西。

第 2 級：青少年 (3:31)

Amit Sahai： 那麼，你以前聽過零知識證明這個詞嗎？

Teen： 沒有，我沒聽過。

Amit Sahai： 這是證明者說服驗證者某件事為真，卻不透露任何關於它為何為真的資訊的一種方法，這聽起來完全不可思議。我想做的是向你證明我知道這個密碼鎖的密碼，但不向你透露密碼是什麼。你可以做的是寫一張小紙條，寫一個我絕對不會知道的秘密。把它摺起來，塞進這裡。然後，如果我知道密碼，我就應該能打開它並告訴你寫了什麼。

好。「我的狗名叫 Doug。」

Teen： 你知道密碼是什麼了嗎？

Amit Sahai： 不知道。所以在這個互動過程中，你沒有看到任何你原本不知道的資訊。然而，我卻說服了你我知道密碼。

Teen： 那麼零知識證明的確切目的是什麼？它是不是像證明某件事，但不提供足以危及你所證明之物的充分資訊？

Amit Sahai： 人們互不信任。如果我能夠向某人證明我正確地完成了某件事，而無需透露我的秘密，那麼那個人就會更信任我。

Teen： 這與電腦技術有什麼關係？這是一種面對面的互動嗎？

Amit Sahai： 假設你想和認識的人交換訊息。你們可能會先聚在一起想出某種密碼，對吧？然後用那種密碼互相寫訊息。但如果你以前從未見過這個人呢？如果你想和我交換秘密訊息，而我們以前從未見過面呢？我們怎麼可能做到這一點？

Teen： 我不知道。

Amit Sahai： 聽起來不可能，對吧？但並非如此。你不會使用實體的鎖或實體的盒子。相反地，我們會使用數學來做這些事情。你可以拿一則訊息並使用數學對其進行加密。然後我可以向你證明我知道金鑰，打開它，並把它送回給你。這樣一來，我就能向你證明我知道這個數學密碼盒的數學金鑰。

所以根據我們今天的討論，用你自己的話來說，什麼是零知識證明？

Teen： 就像如果你有一個非常重要的秘密，你想讓某人知道，但你不想告訴他們全部。你可以使用零知識證明向他們證明那個秘密，但不會洩露全部內容。

第 3 級：大學生 (6:13)

Amit Sahai： 妳在學什麼？

College Student： 我是南加州大學維特比工程學院電腦科學系一年級的學生。我對資料、網際網路、區塊鏈和加密貨幣等所有事物都很感興趣。

Amit Sahai： 妳聽過零知識證明嗎？

College Student： 只有略有耳聞。

Amit Sahai： 實際上，區塊鏈領域是我們看到零知識證明正在被實作的領域之一——而且我認為這只是一個開始。在其核心，零知識證明是兩個人之間的互動。我應該能夠說服妳某個陳述為真，但妳完全不知道它為何為真。

我們將透過一種稱為 NP 完全（NP-completeness）的概念來探討這個問題。NP 完全問題是一個非常難以解決的問題。但如果你能解決它，你就能解決屬於 NP 類別的任何問題——這包含了數量龐大的問題。我們將使用一個 NP 完全問題，透過零知識證明來實際證明各種令人難以置信的陳述。我們將要探討的特定 NP 完全問題稱為地圖三著色問題（map three-coloring）。

這裡我們有一張包含許多國家的地圖，其排列方式使得沒有任何兩個顏色相同的國家共享邊界。這就是讓這樣一張地圖被視為有效著色的原因。事實證明，一張地圖是否能以這種方式進行三著色，就是 NP 完全問題的一個例子。

也許妳真正想做的是提供一個零知識證明，證明妳至少擁有 0.3 顆比特幣，而不透露妳的帳戶地址。事實證明，我可以將該陳述轉換為一張國家地圖。只有當妳至少擁有 0.2 顆比特幣時，該國家地圖才能進行三著色。

College Student： 我們該如何將這樣的東西變成零知識證明？

Amit Sahai： 當然，第一步是我們必須擦除所有顏色。我已經在這些信封裡各放了一種顏色。現在，妳怎麼知道這是一個有效的著色？妳不知道。妳必須挑選任何兩個相鄰的國家——妳可以隨意挑選，隨機挑選。

College Student： 我可以選這兩個嗎？

Amit Sahai： 這裡我們有綠色，而這裡我們有藍色。如妳所見，它們是兩種不同的顏色。所以妳有一點信心，相信我已經成功地正確著色了——但信心沒有那麼大，因為我只向妳展示了兩個國家。獲得更多信心的一種方法是打開更多信封，但那樣就會向妳透露資訊。我不想那樣做。

所以相反地，我要請妳轉過身去。現在，讓我們改變這些顏色。

妳能隨機挑選兩個國家嗎？我們將再次揭曉兩種顏色。

College Student： 我選這個和這個。

Amit Sahai： 妳很聰明，檢查了妳已經選過的同一個國家。但如妳所見，現在它不是綠色——它是藍色。而另一方面，這個是綠色。我上次給妳看的顏色與這些新顏色不符。但它適用於我現在展示給妳看的這種著色方式。所以我們所做的是讓妳無法將這些片段拼湊起來。如果妳這樣做一千次，而我每次都正確地向妳展示不同的顏色，妳就會非常確信。就是這樣——這就是整個零知識證明。

College Student： 所以這就像是一種機率性證明嗎？

Amit Sahai： 是的。在實際實作中，我們不會使用信封——妳會使用加密。但這就是該協定。

College Student： 那麼零知識證明更廣泛的影響是什麼？它們是為了在實作上更實用，還是為了在結構上證明某些東西？

Amit Sahai： 這不是為了讓某件事變得更有效率。這是為了做到我們以前根本不知道該怎麼做的事情。我實際上可以向妳證明，在不透露我任何秘密的情況下，我的行為是誠實的。我可以向妳證明我正確地簽署了某份加密文件，而不透露那份秘密文件是什麼。這種改變遊戲規則的能力——真正改變我們能做什麼的能力——就是零知識所帶來的優勢。

College Student： 你認為我們可以在哪裡使用零知識證明建立更多信任？

Amit Sahai： 一個很好的例子是選舉。如果妳能在零知識的情況下證明一場選舉是正確進行的——每一張投票都被計算在內，並且總和結果是某個人以特定的總票數獲勝——那麼妳就不必公開任何人的實際投票。然而，每個人都可以看到它是正確完成的。

第 4 級：研究生 (11:59)

Amit Sahai： 很高興你能來這裡和你交談，Eli。你能跟我說說你的研究嗎？

Eli： 我的研究領域是密碼學。具體來說，我正在研究一些多方計算協定。我目前正在研究的是一個用於計算聚合統計資料的系統，這樣一來，像 Google Chrome 或 Tesla 這樣的服務提供商就可以收集這些統計資料，而無需了解任何關於個別使用者資料的資訊。身為使用者，我不必讓 Firefox 知道我最喜歡的網站是 mylittlepony.com。但他們可以知道每天有多少使用者造訪 mylittlepony.com。

Amit Sahai： 太棒了。多方計算是我非常熱愛的領域。顯然，零知識證明是關於向另一個人證明事情，而不透露你所證明內容的細節。但在我心裡，零知識實際上遠不止於此。這是一個總體概念，你在多方計算中經常可以看到，你想要完成某項任務，除了完成該任務所需的最少資訊外，不透露任何其他資訊。

Eli： 沒錯，而且它允許你證明你的行為是誠實的，而不透露你用來實際表現誠實所涉及的任何秘密。我們知道針對 NP 完全語言的零知識證明在密碼學中扮演著非常重要的角色。你第一次接觸 NP 完全問題的經驗是什麼樣的？

Amit Sahai： 我第一次接觸是在我大學部第一堂演算法課上。NP 完全語言是一個驚人的問題，它不僅告訴你關於它本身的資訊，而且解決這個問題實際上可以告訴你關於一整類非常有趣的問題的資訊。

Eli： 當你第一次開始將證明視為我們互相交談的互動遊戲時，這是否讓零知識成為可能？

Amit Sahai： 絕對是。而且隨機性可能對證明某件事有用的想法——如果我們考慮證明的柏拉圖式理想，這似乎又非常違反直覺。那裡不存在隨機性，也不存在非決定論。

Eli： 這與徹底顛覆證明的整個想法有關。在古老的經典證明中，隨機性特別違背了你試圖達成的目標，因為你試圖讓一切變得明顯並揭示資訊流。但一旦你徹底顛覆了這一點，並且你不再試圖這樣做，突然之間，隨機性的所有壞屬性都變成了好屬性。

Amit Sahai： 完全正確。隨機是不可預測的，而這正是我們想要的。我們希望這種不可預測性實際上能隱藏我們想要隱藏的資訊。你在你參與的專案中是如何使用零知識的？你發現了哪些挑戰？

Eli： 通常最困難的部分是弄清楚到底哪裡是使用它的最佳位置。我寫過一些以更理論的方式使用零知識的論文，但說到應用，到目前為止我看到最令人興奮的應用是在區塊鏈領域。

Amit Sahai： 有哪些效率瓶頸？

Eli： 零知識證明最酷的事情之一就是它有很多種類——我喜歡稱它們為口味。一般來說，當你在應用程式中使用零知識證明時，主要的瓶頸往往在於證明者。

Amit Sahai： 你能把證明者的工作拆分成許多平行計算嗎？

Eli： 這是一個非常有趣的問題。我認為作為一個領域，我們仍然不知道這個問題的答案。在過去三、四年裡，我看到最酷的事情之一是從理論到應用的轉變——看到人們在過去 30 年裡想出的所有這些驚人系統，開始變得足夠有效率以至於能夠被實際製造出來。

Amit Sahai： 毫無疑問。特別是隨著雲端運算的發展——利用雲端的力量來實現零知識證明將會非常了不起。同樣在區塊鏈領域，如果你想加速證明的生成，如果能以分散式的方式完成，那就太棒了。我的一個希望是，多方計算的力量在於將互不信任的人們聚集在一起。我們能否利用密碼學中的這種力量，並用它來幫助解決目前社會中存在的巨大不信任感？

Eli： 我認為這是我如此被多方計算吸引的原因之一。世界上最重要的問題之一就是許多人互不信任。能夠使用數學來創造一種技術，讓人們在不必互相信任的情況下一起工作，這是一個非常酷且了不起的使命。

第 5 級：專家 (17:10)

Amit Sahai： Shang-Hua，很高興再次見到你。我想我們上次見面是在 2017 年左右。

Shang-Hua： 我想我們在疫情期間用 Zoom 視訊過一次，但很高興能親自見到你。實際上，在 86 年，我正在上 Leonard Adleman 教授（RSA 中的 A）的密碼學課程。他指派我閱讀 Goldwasser、Micali 和 Charlie Rackoff 關於零知識證明的論文。所以那確實是我在這個國家的第一次簡報——關於零知識。

Amit Sahai： 太棒了。這是一個幾乎令人著迷的概念。

Shang-Hua： 如何在數學上制定這些概念也很有趣。例如，我們有資料。最終從資料中，透過資料探勘，你可以獲得資訊。然後你有一個詞叫做「知識」。知識即使在哲學中也一直備受爭議。什麼是知識？但在這裡，數學家或電腦科學家想要捕捉這種知識的方式非常迷人。它沒有說「零資訊證明」。那麼你認為為什麼是「知識」而不是「資訊」，或者是「零資料證明」？顯然那裡有資料，所以它不可能是零資料。

Amit Sahai： 絕對是。我認為我們對這個問題仍然沒有一個完全令人滿意的答案。如此美妙的見解在於，零知識是你已經可以預測的東西。如果你已經可以預測答案，那麼你一定沒有透過那次互動獲得任何知識。這種見解——能夠準確預測未來，而這正是缺乏新知識的證據——是如此美妙、驚人的見解。

Shang-Hua： 嗯，這裡並非零資訊。從根本上來說，從運算和安全的角度來看，重要的是你獲得了多少知識，而不是你獲得了多少資訊以及你擁有多少資料。資料並不直接意味著知識。但人們並不總是能區分。

Amit Sahai： 沒錯。例如，在醫學研究中——如果能有一種藥物，並證明它在這個模型中有效，而無需透露化合物的結構，那該有多神奇？

Shang-Hua： 你認為這個領域的下一個方向是什麼？

Amit Sahai： 零知識程式的這個概念將允許你以零知識的方式執行完全任意的計算，而無需任何互動。我可以直接拿這個程式，將其轉換為零知識程式——或混淆程式——然後直接發送給你。你可以執行它並獲得該計算的好處，而無需再與我交談。

Shang-Hua： 沒錯。它具有非互動的性質。但其中包含可驗證性。在區塊鏈中，他們也開始在帳本中納入更通用的零知識證明。

Amit Sahai： 我們現在絕對處於零知識將被越來越多地使用的時刻。在零知識領域有許多會議和聚會，你和我都沒有受邀——因為那是為開發人員、寫程式的人準備的，而不是我們這些數學家。我認為這是一個跡象。這是一個跡象，表明我們的孩子已經長大，是時候讓它發展了。

Shang-Hua： 我認為意義深遠的是，學生們經常問我未來的方向是什麼——無論是在密碼學、零知識證明方面，還是在現實世界和數學運算方面。

Amit Sahai： 這是一個很好的問題。我希望我能看到未來。我不能，但讓我試試看。我認為在過去的幾十年裡，我們在密碼學方面做了很多，但我們了解的卻很少。最基本的方面是理解難度——我們如何獲得難題？我們如何實際建立數學上的難題，以便我們隨後可以使用它們來建立有效率的零知識程式和證明？

Shang-Hua： 我猜在量子運算中，你也需要更難的問題。

Amit Sahai： 確實如此。現在我們面臨著量子運算的威脅，我們都知道量子電腦可以破解許多密碼系統。這是一個嚴峻的挑戰。那麼我們能否找到抗量子的新難度來源——即使是量子電腦也無法破解？這是我過去幾年一直在研究的課題。

Shang-Hua： 但我確信它們會激發出美妙的數學。

Amit Sahai： 是的，沒錯。現實世界的一大優點是，現實世界中的人們有需求。而這些需求通常聽起來是不可能的。這就是我們發揮作用的地方——讓不可能成為可能就是我們的工作。