Vitalik Buterin：如何使用 zk-SNARKs 技術保護隱私？

作者：Vitalik Buterin

原文標題：《Some ways to use ZK-SNARKs for privacy》

編譯：去中心化金融社區

ZK-SNARK 是一種強大的加密工具，它在區塊鏈和區塊鏈以外構建的應用程序中變成日益重要的一部分。但它們是複雜的，無論是從它們的工作原理，還是從我們如何使用它的角度來看，都是複雜的。

這篇文章將關注 ZK-SNARK 如何適應現有的應用程序，有哪些例子說明它們能做什麼，不能做什麼，以及有哪些通用的指導方針來判斷 ZK-SNARK 是否適合某些特定的應用程序。

這篇文章特別關注 ZK-SNARK 在保護隱私中的應用。

ZK-SNARK 是做什麼的？

假設有一個公共輸入 x，一個私有輸入 w，和一個 (公共) 函數 f (x,w)→{True,False}，其會對輸入執行某種驗證。使用 ZK-SNARK，就可以證明你知道一個 w，對於某些給定的 f 和 x，f (x,w)=True，在此過程中不用透露 w 到底是什麼。另外，驗證者可以更快地驗證證明，這比他們自己計算 f (x,w) 要快得多，就算他們知道 w。

這賦予了 ZK-SNARK 兩個屬性：隱私性和可擴展性。如上所述，在這篇文章中，我們的例子將聚焦於隱私。

成員資格的證明

假設你有一個以太坊錢包，你想要證明這個錢包是人性證明（proof-of-humanity）註冊，同時不透露註冊的到底是誰。我們可以用數學方法描述這個函數：

• 私有輸入 (w)：你的地址 A，你的地址私鑰 k
• 公共輸入 (x)：所有經過驗證的人性證明配置文件 {H1…Hn} 的地址集合
• 驗證函數 f (x,w)
• 將 w 解釋為一對 (A，σ)， x 為有效配置文件列表 {H1…Hn}
• 驗證 A 是 {H1…Hn} 中的一個地址
• 驗證 privtoaddr (k) = A
• 如果兩個驗證都通過，則返回 True，如果任何一個驗證失敗則返回 False

證明者生成他們的地址 A 和相關的密鑰 k，並提供 w=(A,k) 作為 f 的私有輸入。他們從鏈中獲取公共輸入，就是當前已驗證的人性證明配置文件集 {H1…Hn}。他們運行 ZK-SNARK 證明算法，此算法 (假設輸入是正確的) 生成證明。證明者將證明發送給驗證者，並且提供他們獲得驗證配置文件列表的區塊高度。

驗證者還會讀取鏈，獲取證明者指定高度的列表 {H1…Hn}，並檢查證明。如果檢查通過，驗證者就相信證明者有一些已驗證的人性證明文件。

在我們繼續討論更複雜的例子之前，我強烈建議先看看上面的示例，直到完全理解其中的所有內容。

使成員證明更有效

上述證明系統的一個缺點是驗證者需要知道整個配置文件集 {H1…Hn}，他們需要花費 O (n) 時間將這組配置文件「輸入」到 ZK-SNARK 機制中。

我們可以通過將包含所有配置文件的鏈上 Merkle 根作為公共輸入 (這可能只是狀態根) 來解決這個問題。我們添加另一個私有輸入，一個 Merkle 證明 M，證明證明者的帳戶 A 在樹的相關部分。

用於 ZK 證明成員資格的 Merkle 證明的一個非常新且更有效的替代方案是 Caulk。將來，其中一些用例可能會遷移到類似於 Caulk 的方案中。

ZK-SNARK 和幣

Zcash 和 Tornado.cash 等項目允許我們擁有保護隱私的貨幣。現在，你可能認為你可以使用上面的「ZK 人性證明」，但它不是證明對人性證明配置文件的訪問，而是用它來證明對幣的訪問。現在我們有一個問題：我們必須同時解決隱私和雙花問題。也就是說，我們不應該花兩次幣。

我們是這樣解決的。任何擁有幣的人都有一個私有秘密「s」。他們在本地計算「leaf」 L=hash (s,1)，它被發布在鏈上，並成為狀態的一部分，N=hash (s,2)，我們稱之為 nullifier。狀態存儲在默克爾樹中。

要花一枚幣，發送者必須做一個 ZK-SNARK，其中：

• 公共輸入包含一個 nullifier N，當前或最近的 Merkle 根 R，和一個新的葉子 L '(目的是接收方有一個秘密 s '，並傳遞給發送方 L ' =hash (s '，1))
• 私有輸入包含一個秘密 s，一個葉子 L 和一個默克爾分支 M
• 驗證功能會檢查：
• M 是一個有效的 Merkle 分支，證明 L 是根為 R 的樹的葉子，其中 R 是當前狀態的 Merkle 根
• hash (s,1)=L
• hash (s,2)=N

交易包含了 nullifier N 和新的葉子 L'。我們實際上並不證明關於 L ' 的任何東西，但我們將其「混合」到證明中，以防止交易在進行時被第三方修改。

為了驗證交易，鏈檢查 ZK-SNARK，另外檢查 N 是否在之前的支出交易中被使用。如果交易成功，則將 N 添加到已花費的 nullifier 集，這樣它就不能再被用。L ' 被添加到 Merkle 樹中。

這我們使用 zk-SNARK 將兩個值聯繫起來，L (當幣被創造出來時出現在鏈上) 和 N (當幣被消費時出現在鏈上)，而不是揭示哪個 L 與哪個 N 相連。只有當你知道產生這兩個值的秘密 s 時，才能發現 L 與 N 之間的聯繫。每個創造出來的幣只能使用一次 (因為對於每個 L 來說，對應的有效的 N 只有一個)，但在特定時間內使用的幣是被隱藏的。

這也是一個需要理解的重要原語。我們下面描述的許多機制都是基於此，儘管目的不同。

任意餘額的幣

上述情況可以很容易地擴展到任意餘額的幣。我們保留了「幣」的概念，但每個幣都附有一個 (私有) 餘額。做到這一點的一個簡單方法是讓每個幣都有鏈存儲，不只是有葉子 L，還有一個加密的餘額。

每次交易將消耗兩個幣並創建兩個新幣，它將向狀態添加兩對 (葉子，加密的餘額)。ZK-SNARK 還會檢查輸入的餘額之和等於輸出的餘額之和，並且兩個輸出的餘額都是非負的。

ZK 反拒絕服務

一個有趣的反拒絕服務小工具。假設你有一些鏈上身份，這是不容易創建的；它可以是一個人性證明配置文件，也可以是 32 個 ETH 驗證者，或者它可以只是有非零 ETH 餘額的帳戶。我們可以通過只接受帶有消息發送者有一個配置文件的證明的消息的方法，創建一個更能抵抗 DoS 的點對點網絡。每個配置文件將被允許每小時發送多達 1000 條的消息，如果發件人作弊，發件人的配置文件將從列表中刪除。但是我們如何保護隱私呢？

首先，設置。設 k 為用戶的私鑰；A=privtoaddr (k) 是對應的地址。有效的地址列表是公開的 (例如。它是鏈上註冊表)。到目前為止，這類似於人性證明的例子：你必須證明你擁有一個地址的私鑰，但不能透露是哪個地址。但在這裡，我們不只是想證明你在列表上。我們想要一個協議，它可以讓你證明你在列表中，但防止你做太多的證明。

我們將把時間分成幾個時期：每個時期持續 3.6 秒（所以，每小時有 1000 個時期）。我們的目標是允許每個用戶在每個時期只發送一條消息；如果用戶在同一時期發送兩條消息，他們就會被捕獲。為了允許用戶偶爾發送突發消息，他們可以使用最近的時期，所以如果某個用戶有 500 個未使用的時期，他們可以使用這些時期一次性發送 500 條消息。

協議

我們將從一個簡單的版本開始：使用 nullifier。用戶生成一個具有 N=hash (k,e) 的 nullifier，其中 k 是他們的密鑰，e 是時期號，並將其與消息 m 一起發布。ZK-SNARK 再次混合 hash (m)，在此過程中沒有驗證關於 m 的任何東西，因此證明綁定到單個消息。如果用戶使用相同的 nullifier 將兩個證明綁定到兩個不同的消息，他們可能會被捕獲。

現在，我們將轉向更複雜的版本。在這種情況下，下個協議將暴露他們的私鑰，而不是簡單地證明某人是否使用了相同的時期兩次。我們的核心技術將依賴於「兩點構成一條線」的技巧：如果你在一條線上顯示一個點，你就顯示的很少，但是如果你在一條線上顯示兩個點，你就顯示了整條線。

對於每個時期 e，我們取直線 Le (x)=hash (k,e)∗x+k 。直線的斜率為 hash (k,e)，y 截距為 k；兩者都不為公眾所知。要為消息 m 製作一個證書，發送者提供 y=Le (hash (m))= hash (k,e)∗hash (m)+k，以及一個 ZK-SNARK 證明 y 的計算是正確的。

綜上所述，ZK-SNARK 如下:

公共輸入:

• {A1…An}，有效帳戶列表
• M，表示證書正在驗證的消息
• E，用於證書的時期號
• Y，是線函數的求值

私有輸入:

• K，你的私鑰

驗證功能:

• 檢查 privtoaddr (k) 是否在 {A1…An} 中
• 檢查 y=hash (k,e)∗hash (m)+k

但是如果有人將一個時期使用兩次呢？這意味著他們公布了兩個值 m1 和 m2 以及相應的證書值 y1=hash (k,e)∗hash (m1)+k 和 y2=hash (k,e)∗hash (m2)+k。我們可以使用這兩個點來恢復直線，因此 y 軸截距 (這是私鑰)：

因此，如果有人重用一個時期，他們就會洩露他們的私鑰，讓所有人看到。根據不同的情況，這可能意味著資金被盜，或者只是將私鑰廣播並包含到了智能合約中，此時相應的地址將從集合中刪除。

一個可行的鏈下匿名反拒絕服務系統，適用於區塊鏈點對點網絡、聊天應用程序等系統，不需要任何工作證明。RLN 項目目前基本上就是在構建這個想法，儘管進行了少量修改 (也就是說，他們同時使用了 nullifier 和兩點在線技術，使用 nullifier 更容易捕獲雙重使用一個時期的問題）。

ZK 的負面聲譽

假設我們想要建立 0chan，一個像 4chan 一樣提供完全匿名的網絡論壇 (你甚至沒有永久的名字)，但是有一個聲譽系統來鼓勵更多高質量的內容。這可能是一個系統，一些審核 DAO 可以標記違反系統規則的帖子，並建立一個三振出局的機制。

聲譽系統可以支持正面或負面聲譽；然而，支持負面聲譽需要額外的基礎設施，要求用戶在證明中考慮所有的聲譽信息，就算它是負面的。我們將重點關注這個更難的用例，它類似於 Unirep Social 正在實現的用例。

鏈接帖子：基礎知識

任何人都可以通過在鏈上發布包含該帖子的消息和 ZK-SNARK 來發布帖子，以證明 (i) 你擁有一些稀缺的外部身份，授權你創建一個帳戶，或 (ii) 你發布過一些特定的帖子。具體來說，ZK-SNARK 如下:

• 公共投入
• nullifier N
• 最近的區塊鏈狀態根 R
• 帖子內容 (「混合」到證明，將其綁定到帖子中，但我們不做任何計算)

私有輸入:

• 你的私鑰 k
• 一個外部身份 (地址 A)，或者前一篇文章使用的 nullifier Nprev
• 一個 Merkle 證明 M 證明鏈上包含 A 或 Nprev
• 你之前使用此帳戶發布的第 i 個帖子

驗證功能:

• 檢查 M 是一個有效的 Merkle 分支，證明（A 或 Nprev，以提供者為準）是根為 R 的樹的葉子
• 檢查 N=enc (i,k)，其中 enc 是一個加密函數 (例如.AES)
• 如果 i=0，檢查 A=privtoaddr (k)，否則檢查 Nprev=enc (i−1,k)

除了驗證證明之外，該鏈還檢查兩個方面 (i) R 實際上是一個最近的狀態根，(ii) nullifier N 還沒有被使用。到目前為止，這就像前面介紹的保護隱私的幣一樣，但我們添加了一個「鑄造」新帳戶的過程，並且我們刪除了將你的帳戶「發送」到不同密鑰的能力 ------ 相反，所有 nullifier 都是使用原來的密鑰來生成。

我們在這裡使用 enc 來使 nullifier 可逆，而不是 hash：如果你有 k，你可以解密鏈上任何特定的 nullifier，如果結果是一個有效的索引而不是隨機的垃圾（例如，我們可以只檢查 dec (N)<264），你就會知道 nullifier 是使用 k 生成的。

添加聲譽

在這個方案中，聲譽是鏈上的，並且是明確的：一些智能合約有一個方法 addReputation，它以 (i) 隨帖子發布的 nullifier 和 (ii) 要加減的聲譽單位數量作為輸入。

我們擴展了每個帖子存儲的鏈上數據：我們存儲 {N,h¯,u¯}，而不是僅存儲 nullifier N，其中：

• h¯=hash (h,r) 其中 h 是證明中引用的狀態根的區塊高度
• u¯=hash (u,r) 其中 u 是帳戶的聲譽分數（新帳戶為 0）

這裡的 R 只是一個隨機值，添加它是為了防止 h 和 u 被強制搜索發現 (在密碼學術語中，添加 R 使哈希成為一個隱藏承諾)。

假設帖子使用根 R 並存儲 {N,h¯，u¯}。在證明中，它鏈接到以前的帖子，存儲數據 {Nprev,h¯prev,u¯prev}。帖子的證明也需要遍歷在 hprev 和 h 之間發布的所有聲譽條目。對於每個 nullifier N，驗證函數將使用用戶的密鑰 k 解密 N，如果解密輸出一個有效的索引，它會將應用聲譽更新。如果所有聲譽更新的總和為 δ，那麼最終證明為 u=uprev+δ。

如果我們想要一個「三振出局」規則，ZK-SNARK 也會檢查 u>−3。如果我們想要一個規則，即如果帖子的 rep≥100，那麼該帖子可以獲得一個特殊的「高聲譽帖子」標識。

為了提高方案的可擴展性，我們可以將其分為兩類消息：帖子和 RCA。一个帖子将是链下的，尽管它需要指向过去一周制作的 RCA。RCA 将是链上的， RCA 将遍历自该发布者之前的 RCA 以来的所有声誉更新。通过这种方式，链上负载减少到每周每个帖子的一笔交易加上每条声誉消息的一笔交易。

對中心化的各方負責

有時，你需要構建一個具有某種中心化「運營者」的方案。其背後原因可能有很多：有時是為了可擴展性，有時是為了隱私（具體來說，是為了運營者所持有的數據的隱私）。

例如，MACI 強制抵抗投票系統要求投票者在鏈上提交他們的投票，並加密到中心化運營者持有的密鑰中。運營者將解密鏈上所有的投票，將其計數，並展示最終結果，同時使用 ZK-SNARK 來證明他們所做的一切都是正確的。這種額外的複雜性對於確保強大的隱私性 (稱為強制抵抗) 來說是非常必要的：用戶不能向其他人證明他們是如何投票的，即使他們想這樣做。

多虧了區塊鏈和 ZK-SNARK，確保了我們對運營者的信任度可以保持在非常低的水平。惡意的運營者仍然可以打破強制抵抗，但是因為投票是在區塊鏈上發布的，所以運營者不能通過審查投票來作弊，而且因為運營者必須提供 ZK-SNARK，所以他們不能通過錯誤計算結果來作弊。

結合 ZK-SNARK 與 MPC

ZK-SNARK 的一個更高級的使用涉及到的是在計算中進行證明，其中輸入在兩方或多方之間分配，我們不希望任何一方學習其他方的輸入。在兩方的情況下，你可以通過雜湊電路滿足隱私要求，在 N 方情況下使用更複雜的多方計算協議來滿足隱私要求。ZK-SNARK 可以與這些協議結合起來進行可驗證的多方計算。

這可以啟用更高級的聲譽系統，多個參與者可以在他們的私有輸入上執行聯合計算。現在有效地實現這一目標的數學計算仍處於相對初級階段。

我們不能將什麼設為私有？

ZK-SNARK 對創建用戶擁有私有狀態的系統非常有效。但是 ZK-SNARK 不能保持沒有人知道的私有狀態。要對一段信息進行證明，則證明者必須以明文的形式知道這段信息。

Uniswap 就是一個不容易私有化的例子。在 Uniswap 中，有一個邏輯中心的「東西」，就是做市商帳戶，它不屬於任何人，Uniswap 上的每筆交易都是與做市商帳戶進行交易的。你不能隱藏做市商帳戶的狀態，因為那樣的話，就必須有人以明文的形式持有這個狀態以進行證明，並且每筆交易都需要他們的積極參與。

你可以用 ZK-SNARK 的雜湊電路做一個中心化操作的、安全的、私有的 Uniswap，但誰也不清楚這樣做的好處能否抵消執行它所需要的代價。這甚至可能不會帶來任何真正的好處：合約需要能夠告訴用戶資產的價格是什麼，而逐塊的價格變化可以告訴用戶交易活動是什麼。

區塊鏈可以讓狀態信息全球化，ZK-SNARK 可以讓狀態信息私有化，但我們真的沒有任何好的方法可以讓狀態信息全球化同時實現私有化。

將原語放在一起

在上面的子節中，我們看到了一些本身就是強大且有用的工具的示例，但它們也可以作為其他應用程序的構建塊。例如，nullifier 對於貨幣來說很重要，現在它們在其他用例中也在重複出現。

在負面聲譽部分使用的「強制鏈接」技術適用範圍非常廣。它對於許多應用程序非常有效，其中用戶的「配置文件」會隨著時間的推移以複雜的方式發生變化，你希望強制用戶遵守系統的規則，同時保護隱私。用戶甚至可以被要求用完整的私有 Merkle 樹來表示他們的內部「狀態」。這篇文章中提出的「承諾池」小工具可以用 ZK-SNARK 來構建。如果某些應用程序不能完全在鏈上並且必須有一個中心化的運營者，那麼完全相同的技術也可以用來保持運營者的誠實。

ZK-SNARK 是一個非常強大的工具，它將責任和隱私的好處結合在了一起。同時它們也確實有其局限性，但在某些情況下，聰明的應用程序設計可以繞過這些限制。我希望看到更多的應用程序使用 ZK-SNARK，並最終在未來幾年內構建出將 ZK-SNARK 與其他形式的加密相結合的應用程序。