解讀零知識證明

本文包括以下內容：1. 什麼是零知識證明？ 2. 為什麼需要零知識證明？ 3. 零知識證明的應用場景。 4. 零知識證明的工作原理。 5. 零知識證明的分類和應用案例。 6. 零知識證明的缺陷。

PART.01

什麼是零知識證明

零知識證明(Zero-Knowledge Proof)，是由S.Goldwasser、S.Micali 及C.Rackoff 在20世紀80 年代初提出的。它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。

舉一個簡單的例子，泡芙說自己是個大廚，中餐，韓餐、意大利菜都會做。我媽表示不信，因為我在家沒做過一頓飯。那麼這個時候我要怎麼證明我會做菜呢？

我可以讓老媽在廚房看著我做完一頓飯，這樣就證明我確實會做。但是我不想讓老媽看到我做飯的時候把廚房弄的一團亂，不然又要被嘮叨，那該怎麼辦呢？我一個人進廚房，爸媽都在外面等著，等我做完飯收拾好了，把菜端出來。這依然可以證明我會做飯。至於我用了什麼食材，放了什麼調料，過程中把廚房弄得亂不亂，這都不需要，老媽只要知道我能做一頓飯，就證明我沒說謊。

簡單說：零知識證明在試圖以最小的信息交換量在雙方之間建立信任。在不透露更多信息的前提下，一方（證明者， the prover）可以向另一方（驗證者，the verifier）證明一件事是對的。

PART.02

為什麼需要零知識證明

保護隱私數據

流氓廠商們都想盡可能多地收集用戶數據，其中一些和他們業務無關的收據也給用戶要權限（真的是非常討厭它們）。他們又把我們收集到的用戶個人身份信息（PII）放在中心化的數據庫中，這些數據庫非常容易被攻擊，一旦受到攻擊，個人身份信息洩露，進而導致各種詐騙問題。

身份認證

在使用網站時，用戶可以向網站證明他擁有私鑰，或者知道某個只有自己才知道的答案，網站不用知道密鑰，但可以通過零知識證明確認用戶身份，通過去中心化存儲，服務器可以向用戶證明數據被妥善保存下來且不被洩露。

計算壓縮與區塊鏈擴容

在傳統的區塊架構中，同樣的計算被重複多次，比如簽名校驗，交易的合法性校驗，智能合約執行等一些其他的地方，因為有了計算的證明，同一個計算就不需要多次重複了，計算過程可以被零知識技術證明壓縮。

零知識證明真正解決了數據的信任，實現了隱私數據的保護，也讓區塊鏈真正實現了信任機器這一構想。

PART.03

零知識證明的應用場景

零知識證明的主要應用場景有：匿名支付、身份證明、可驗證計算、匿名投票。

匿名支付

加密貨幣交易在公鏈上都是公開可見的。用戶通過匿名進行交易，但是也鏈接到真實世界的身份（例如，通過在Twitter 或GitHub 個人資料中包含ETH 地址），要么就可以通過鏈上和鏈外數據分析獲得用戶真實世界的身份。

有專為完全匿名交易而設計的特定“隱私幣”。例如Zcash 和Monero ，他們會屏蔽交易細節，包括發送方/接收方地址、資產類型、數量和交易時間表。通過將零知識技術融入協議，以隱私為中心的區塊鍊網絡允許節點在無需訪問交易數據的情況下驗證交易。

零知識證明也被應用於公共區塊鏈上的匿名交易。例如Tornado Cash，一種去中心化的非託管服務，允許用戶在以太坊上進行私人交易。 Tornado Cash 使用零知識證明來混淆交易細節並保證財務隱私。

身份證明

在不暴露具體身份信息的前提下，，出具具體的身份特徵證明。例如使用在線服務需要證明用戶的身份和訪問這些平台的權利。這通常需要提供個人信息，例如姓名、電子郵件地址、出生日期等。

零知識證明可以簡化平台和用戶的身份驗證。使用公共輸入（例如，證明用戶是平台成員的數據）和私人輸入（例如，用戶的詳細信息）生成了ZK 證明，用戶可以在需要訪問時簡單地出示它以驗證其身份服務。例如證明用戶是否成年，不用出具身份證信息，或者俱體的出生年份，只出具是否滿十八歲的結論。

可驗證計算

當用戶的設備無法支持需要的計算，或者在本地進行計算成本太高的時候，就會考慮第三方服務。這些第三方服務可以快速且廉價地向用戶返回輸出的結果（例如Chainlink 的oracle 服務）。這種場景下零知識證明允許第三方算力提供商輸出計算完整性證明，確保用戶收到的輸出結果是正確的。

匿名投票

在不暴露具體身份的前提下，證明用戶的身份並獲得投票權限，完成投票。

PART.04

零知識證明的工作原理

零知識證明最早由MIT 的Shafi Goldwasser 和Silvio Micali 在1985 年一篇名為《互動式證明系統的知識複雜性》的論文中提出。作者在論文中提到，證明者（prover）有可能在不透露具體數據的情況下讓驗證者（verifier）相信數據的真實性。零知識證明可以是交互式的，即證明者面對每個驗證者都要證明一次數據的真實性；也可以是非交互式的，即證明者創建一份證明，任何使用這份證明的人都可以進行驗證。零知識證明目前有多種實現方式，如zk-SNARKS、zk-STARKS、PLONK 以及Bulletproofs。每種方式在證明大小、證明者時間以及驗證時間上都有自己的優缺點。

零知識證明有三個基本特徵，即：

• 完整性：如果statement 為true，則誠實的驗證者可以相信誠實的證明者確實擁有正確的信息。

• 可靠性：如果statement 為false，則任何不誠實的證明者都無法說服誠實的驗證者相信他擁有正確的信息。

• 零知識性：如果statement 為true，則驗證者除了從證明者那裡得知statement 為true 以外，什麼都不知道。

總而言之，要創建零知識證明，驗證者需要讓證明者執行一系列操作，而證明者只有在得知底層信息的情況下才能正確執行。如果證明者亂蒙一個結果，那麼驗證者極有可能在驗證中發現並證明他的錯誤。

PART.05

零知識證明的分類

零知識證明可以根據交互方式分為『交互式零知識證明』和『非交互式零知識證明』。

交互式零知識證明

證明者和驗證者需要進行多次互動，驗證者會不斷提出問題來挑戰證明者，證明者則要不斷回應這些挑戰，直到驗證者被說服。

交互式零知識證明——色盲遊戲

Alice 是色盲，Bob 不是色盲，在Bob 手上有兩個大小，形狀完全一樣的球，但這兩個球的顏色不一樣，一個球是藍色的，另一個球是紅色的，由於Alice 是色盲，所以Alice 無法分辨這兩個球是否是一樣的，Bob 需要向Alice 證明這兩個球是不一樣的。在這裡，Alice 被稱為驗證者，他需要驗證Bob 的陳述正確與否，Bob 被稱為證明者，他需要證明自己的陳述（存在兩個顏色不一樣的球），Bob 需要在Alice 不能獲得兩個球的顏色的情況下，向Alice 證明這兩個球的顏色是不一樣的這個事實，這與零知識證明的定義是相符合的。

Alice 當Bob 的面拿起兩個球，左手拿藍球，右手拿紅球，然後將雙手放到背後，這樣Bob 就看不到Alice 手上的球了，Alice 在背後隨機交換左右手上的球，交換完成後Alice 將手伸出，並詢問Bob 兩個球是否交換過位置，如果Bob 能看到球上的顏色，那麼每次Alice換過球的位置後，Bob 都能正確回答出Alice 的問題。

第一次，Alice 偷偷交換了手中球的位置，然後Alice 問Bob 是否交換了球的位置，如果Bob 回答Yes，那麼Alice 有50% 的概率相信Bob 是可以區分這兩個球的顏色，因為Bob 有1/2 的概率蒙對，所以Alice 可以再進行一次測試。如果Bob 回答No，那麼Alice 可以肯定Bob 不能區分兩個球的顏色。

第二次，Alice 沒有交換手中球的位置，然後Alice 問Bob 是否交換了球的位置。如果Bob 回答No，那麼Alice 有75% 的概率相信Bob 是可以區分兩個球的顏色。

第一次迭代後，Alice 可以說Bob 陳述的斷言為真的概率為50％。如果Bob 第二次回答正確，那麼Alice 可以說Bob 陳述為真的概率達75％。在第三次迭代後，它將是87.5％。如果連續n次Bob都通過了檢查，則Alice 有1-(1/2)^n 的概率可以認為 Bob 說的是真的，這兩個球的確是有紅藍兩種顏色。

交互式零知識證明是一種基於概率的驗證方式，驗證者（verifier）基於一定的隨機性向證明者（prover)提出問題，如果證明者都能給出正確回答，則說明證明者大概率擁有他所聲稱的“知識”。零知識證明並不是數學意義上的證明，因為它存在小概率的誤差，欺騙的證明者有可能通過虛假的陳述騙過驗證者。換句話說，零知識證明是概率證明而不是確定性證明，但是也存在技術能將誤差降低到可以忽略的值。

這種交互式方法有一些局限：

• 每次驗證都需要進行整個冗長的過程。

• 證明方與驗證方都需要同時在場，不管是在線還是面對面。

• 只能夠取信於一個驗證者，如果要取信於多個驗證者，則對每個驗證者都需要進行一遍證明過程。

非交互式零知識證明

交互式零知識證明需要兩方隨時可用並反復交互。即使驗證者確信證明者是誠實的，該證明也無法用於獨立驗證（計算新證明需要證明者和驗證者之間的一組新消息）。

為了解決交互式零知識證明面臨的問題，非交互式零知識證明應運而生。 Manuel Blum、Paul Feldman 和Silvio Micali 提出了第一個交互式零知識證明——其中證明者和驗證者有一個共享密鑰。這使證明者可以在不提供信息本身的情況下證明他們對某些信息的了解。

非交互式零知識證明—數獨遊戲

數獨是源自18 世紀瑞士的一種數學遊戲，是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9 盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重複。

Alice 為了向Bob 證明她已經解決了一個數獨難題，為此Alice 創建了一個防篡改的機器。 Alice 將生成好的數獨答案放入機器中，機器可以向Bob 發送證明。 Alice 的機器遵循以下公開可驗證的協議：首先，Alice 在機器中放入尚未被解決的原始數獨題目，數獨中的謎題卡片三張正面朝上。接下來，Alice 上機器將他的答案正面朝下放置在相應的單元格上，同樣也是每個單元格放三張。最後Bob 向機器獲取證明，機器返回給Bob27 個袋子：

機器將數獨中每一行9 張卡片取出，並分別混淆後放入一個袋子中，一共有9行，用掉9 個袋子；機器將數獨中每一列9 張卡片取出，並分別混淆後放入一個袋子中，一共有9 列，用掉9 個袋子；機器將數獨中每個粗線宮（3*3）內卡片取出，並分別混淆後放入一個袋子中，一共有9 個，用掉9 個袋子；

Bob 分別對這27 個袋子進行檢查，如果每個袋子中的卡片都包含數字1 到9，而且沒有任何數字丟失或重複，那麼Bob 可以確認Alice 的確解開了數獨，並且Bob 並沒有從機器返回的證明中獲取任何關於數獨解的知識，因為機器返回給Bob 袋子中的數據是被隨機打亂的。

非交互式零知識證明克服了交互式零知識證明的一些缺點，不需要冗長的在線交互，可以取信於很多人（甚至所有人），證明始終有效，但是可能需要額外的機器和程序來確定實驗的順序。例如，在數獨這個例子中，由程序決定要驗證的列或行。驗證序列必須保密，否則驗證者可能會在不知道真正“知識”的情況下通過驗證。

交互式零知識證明VS 非交互式零知識證明

交互式證明的每次驗證都需要進行新一輪通信，非交互式證明只需要參與者（證明者和驗證者）之間進行一輪通信。證明者將秘密信息傳遞給特殊算法以計算零知識證明。該證明被發送給驗證者，驗證者使用另一種算法檢查證明者是否知道秘密信息。

非交互式證明減少了證明者和驗證者之間的通信，使ZK 證明更加高效。此外，一旦生成了證明，其他任何人（可以訪問共享密鑰和驗證算法）都可以進行驗證。

PART.06

零知識證明的技術方案和應用

零知識技術可以讓開發者既能利用以太坊等底層區塊鏈的安全性，又能為dApp 提高交易吞吐量和速度，並同時將用戶個人信息放在鏈下，以保護用戶隱私。交易將打包上傳至鏈上，以降低終端用戶的使用成本。最終，項目可以利用這些功能打造出高級的dApp，不僅在性能上可以與Web2 系統媲美，而且還能保持Web3 去中心化的優勢。

（圖片來源：Chainlink）

在Layer2 中zk-rollup 會將多筆交易打包在一起，並發佈到Layer1 區塊鏈上，同時還會發布一個驗證計算有效性的零知識證明。發佈到鏈上的證明也被稱作“有效性證明”。有效性證明技術分為SNARKs 和STARKs 兩類。

zk-SNARs

SNARK 的全稱是“zero-knowledge succinct non-interactive argument on knowledge”（簡潔的非交互式零知識證明）。這是一種加密證明，文件很小而且很容易驗證。它利用橢圓曲線生成一個加密證明，該橢圓曲線假設無法從一個公開的基點找到隨機橢圓曲線元素的離散對數。橢圓曲線的計算成本低於STARK 的哈希函數，因此SNARK 協議的gas 成本更低。

案例：Zcash, Loopring, zkSync1.0,zkSync 2.0,Zigzag, Mina

zk-STARK

STARK 全稱是“zero-knowledge scalable transparent argument of knowledge”（零知識的可擴展、透明知識證明）。這種加密證明幾乎不需要證明者和驗證者之間產生任何交互。 STARKs 相比SNARKs 的最大優勢在於證明時間更短，而且更容易擴展。另外，由於STARKs 採用哈希函數，因此也可以抗量子攻擊。

值得一提的是，STARKs 的發明者是Eli Ben-Sasson，此人是StarkWare 的聯合創始人，這個團隊也開發了StarkEx 和StarkNet。

案例：StarkEx, StarkNet, Immutable X, Starkware

PART.07

零知識證明的缺點

高昂的硬件成本

根據證明系統的不同，零知識證明生成過程有所不同。但最終都會面臨難題：大數字向量（字段或組）的乘法，特別是可變基數和固定基數的多標量乘法（MSM），或者快速傅立葉變換（FFT）和逆FFT。

MSM 和FFT 的運算速度都很慢。在同時存在FFT 和MSM 的系統中，大約70% 的證明生成時間花在MSM 上，30%的時間花在FFT 上。需要硬件加速才能在復雜的計算中實現。通常認為對ZK 硬件加速最重要的技術是FPGA 而不是GPU（由於成本和能源效率）或ASIC（由於它們的不靈活性和長迭代周期）。頂級FPGA比頂級GPU 便宜約3 倍。而且FPGA 的能效比GPU 高出10 倍以上，主要原因是GPU 需要連接到主機設備，這會消耗大量電能。

驗證成本

驗證證明需要大量複雜的計算，這也增加了運算成本。例如，ZK-rolluos 需要支付約500，000gas 來驗證以太坊上的單個AK-SNARK 證明，ZK-STARKs 需要的費用就更高了。

信任假設

零知識證明的前提是，雙方都是誠實的，都很希望知道真實答案，不會進行數據造假。在ZK-SNARK 中，生成一次公共參數可以讓參與零知識協議的各方重複使用，這就默認參與者是提供的數據是正確的。

但事實上，用戶沒有辦法評估參與者的誠實度，即使參與者輸入了假的數據，用戶也必須相信。在ZK-STARK 中沒有信任假設，現在，研究人員正在為ZK-SNARKs 進行非可信設置，來提高證明機制的安全性。

量子計算威脅

ZK-SNARK 使用了橢圓曲線數字簽名算法（ECDSA）進行加密，目前看來ECDSA 算法是安全的，但是未來量子計算機的發展很可能破解這種算法。

通常認為ZK-STARK 不會受到量子計算的威脅，因為它使用抗碰撞哈希進行加密，與ECDSA 的公私密鑰對不同，抗碰撞哈希更難被量子計算破解。