零知識證明：什麼是 zk-STARKs 以及它們是如何工作的？（zk-STARK V2）

一、什麼是儲備證明和零知識證明？

1、什麼是儲備證明（PoR）？

儲備證明（PoR）是加密貨幣交易所展示其擁有足夠資產來覆蓋所有用戶餘額的過程。這通過證明交易所沒有隱藏任何負債，以博取信任。展示這一點的最簡單方法是發佈交易所的資產金額和用戶餘額列表，以便每個人都可以確認：

• OKX 持有的用戶資產總量等於每個用戶資產餘額的總和。

• 每個用戶的總餘額都大於零，並對其資產進行核算，覆蓋其負債並確保每個用戶擁有正的淨資產。

• 交易所公佈的總價值包含每個用戶，因此每個用戶都應該能夠驗證他們的淨值是否包含在總價值中。

然而，洩露這些餘額可能會危及用戶隱私。為了解決這個問題，我們使用了一種稱為零知識證明（ZKP）的方法來保護用戶的隱私。

2、什麼是零知識證明（ZKP）？

零知識證明（ZKP）是一種安全技術，允許加密貨幣交易所在不透露任何額外信息的情況下證明聲明的真實性。在我們的情況下，我們希望證明我們有足夠的資金，而不分享特定的用戶詳細信息。

大多數 ZKP 分為兩類：

• zk-snark

• ZK-STARK

我們使用zk-STARK是因為它更安全並且具有最低安全假設。在本文中，我們將解釋如何使用zk-STARK來保護用戶隱私，同時證明我們的償付能力。

在我們繼續之前，瞭解一些基本的ZKP術語是有幫助的，比如電路、默克爾樹和承諾。對於初學者，有許多資源可以幫助你入門。對於高級用戶，你可以參考MOOC課程和學術專著。

二、zk-STARK 是如何工作的？

我們使用每個用戶賬戶的哈希作為葉子創建一個默克爾樹。每個賬戶都顯示各種代幣（例如，BTC，ETH）的USD餘額。為了處理這些餘額，我們將其餘額分成每個代幣的非負股權和債務。這樣，我們只使用正數，更容易處理計算和避免錯誤。

例如：

• 如果用戶的BTC代幣餘額為 A，則其 BTC 權益為 A，BTC債務為 0。

• 如果一個用戶的ETH代幣餘額是 - B，它對應的權益是 0，債務是 B。

接下來，我們將這些賬戶值作為葉子構建一個 Merkle 樹。樹的根充當代表所有用戶餘額的單個值。每個用戶都可以通過使用顯示他們的賬戶如何連接到根的 Merkle 路徑來證明他們的賬戶是這棵樹的一部分。

我們還發佈所有用戶所有代幣的總資產和債務總和。然後，我們創建一個零知識證明（ZKP）來顯示兩件事情：

• 求和證明：

  默克爾樹中的資產和債務價值正確相加

• 非負證明：

  每個用戶的總資產大於他們的總債務

當我們試圖驗證大量賬戶的默克爾樹時，有限的計算資源無法一次整理一整顆樹。為了克服這一挑戰，我們將賬戶分成稱為批次的較小組。每個批次都使用批次電路單獨處理，該電路檢查默克爾樹的底部。

批處理不僅使其易於管理，而且允許我們同時運行這些檢查（並行處理）。一旦我們有了每個批次的結果，我們就使用另一層電路，稱為遞歸電路，將所有批次組合在一起並驗證，直到我們證明了整個默克爾樹。

1、什麼是批處理電路？

批處理電路接受1024個賬戶 (acc₀, acc₁,..., acc₁₀₂₃) 作為輸入，並生成3個主要輸出：一個哈希 (h_batch)，一個總資產價值 (e_batch)，和一個總債務價值 (d_batch)。它檢查：

• 每個賬戶的 USD 權益總額大於債務總額。

• e_batch 是這些賬戶中所有以 USD 計價的權益價值的總和。

• d_batch 是這些賬戶中所有以 USD 計價的債務價值的總和。

• h_batch 是使用帳戶哈希創建的 Merkle 樹的根。

• 在求和 e_batch 和 d_batch 期間沒有溢出。

2、什麼是遞歸電路？

遞歸電路從低層電路中獲取 64 種不同的證明(π₀, ..., π₆₃)、哈希 (h₀, ..., h₆₃)、股票(e₀, ..., e₆₃₎, 和債務 (d₀, ..., d₆₃)作為輸入。它組合這些輸入並產生 3 個輸出：新哈希 (h_recursive)、總資產(e_recursive),和總債務(d_recursive)。它檢查：

• 64 個證明中的每一個都是有效的。

• 每個證明 π₀, ..., π₆₃來自下層電路是有效的。

• e_recursive 是 e₀, ..., e₆₃ 的總和

• d_recursive 是 d₀, ..., d₆₃ 的總和

• h_recursive 是串聯的 h₀, ..., h₆₃, i.e.

  • h_recursive = Hash (h₀ || h₁ || ... || h₆₃）

• 在求和 e_recursive 和 d_recursive 期間沒有溢出。

3、批處理電路和遞歸電路之間的關係是什麼？

下圖說明了批處理電路和遞歸電路如何相互連接和傳遞數據。請記住，在圖中，我們出於說明目的複製了電路，但在我們的實現中，我們只為每一層使用一個電路。

我們的 Merkle 樹的結構有點不同。在底部 10 層，每個父節點有 2 個子節點，而在上層，每個父節點有 64 個子節點。這是因為批處理電路處理底部，而遞歸電路管理頂部。下圖使用帶有“Alice”的示例來顯示 Merkle 樹和她的 Merkle 證明（用綠色著色）。

有關更多技術細節，例如我們如何調整帳號以適應批量大小或選擇正確的哈希算法，請查看此頁面。

三、zk-PoR 版本 2 的進展

我們的zk-PoR版本2比以前的版本有了幾個進步。

• 更高的效率：

  它現在比以前的版本快50倍。在單個10核機器上需要3小時，而以前的版本使用9臺64核機器需要36小時。這種加速是由於使用了Plonky2框架，該框架將Rust編碼的電路編譯成高效的機器語言，而不是使用較慢的Python腳本。我們還增強了Plonky2在GPU上運行一些計算，將時間額外減少了30%。

• 更好的可審計性：

  在版本2中，我們使用了一個高級框架，為我們處理複雜的加密細節。這使我們的代碼更清晰，更易讀，更不容易出錯。

• 簡明證明：

  V2證明大小（~500KB）僅為V1（~1.2GB）的0.05%。由於遞歸方法，證明可以重複聚合並壓縮成一個證明。

四、如何執行準備金證明（PoR）的自我驗證？

這是如何檢查您的資產餘額是否包含在zk-STARK Merkle葉子中的方法：

1、登錄您的OKX帳戶，轉到資產，並選擇 PoR報告

2、選擇詳細信息 ，以查看審計數據

3、通過選擇複製數據獲取手動驗證所需的數據

4、選擇複製數據後，打開文本編輯器（例如使用筆記本），然後粘貼並將JSON字符串保存為文件。文件必須以名稱“_inclusion_proof. json”結尾。JSON字符串包含您的帳戶餘額和Merkle路徑的快照，然後將文件保存在新文件夾中。

5、打開文本編輯器（例如Notebook），然後粘貼JSON字符串並將其保存為文件。文件名必須以“_inclusion_proof. json”結尾。將文件保存在新文件夾中。

• JSON字符串包含帳戶餘額和Merkle路徑的快照。

• JSON文本如下所示：

{"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}}

6、下載OKX開源驗證工具：zk-STARKValidator

7、將OKX開源驗證工具zk-STARKValidator和JSON字符串文件一起保存在步驟5中創建的新文件夾中。在我們的例子中，我們將工具和數據文件放在名為“ por_inclusion_proof.json ”下載文件夾中，如下所示：

8、打開 zk-STARKValidator；它將自動運行您保存在文件夾中的JSON文件。

9、檢查結果：

• 如果驗證通過，將顯示包含約束驗證通過的結果：

  

• 如果驗證失敗，將顯示包含約束驗證失敗的結果：

  

五、如何驗證zk-STARK總餘額和非負約束？

以下是如何驗證我們聲稱持有的資產是否屬實以及沒有用戶持有負淨資產的方法：

1、轉到我們的儲備證明頁面並選擇責任報告

2、下載 zk-STARK 文件並將其保存在新文件夾中

3、解壓文件以提取"sum_proof_data. json"文件

4、下載OKX開源驗證工具：zk-STARKValidator

5、將OKX開源驗證工具zk-STARKValidator和"sum_proof_data. json"文件一起保存在步驟2中創建的新文件夾中。在我們的例子中，我們將工具和數據文件放在下載文件夾中，名為"儲備證明"，如下所示：

6、打開zk-STARKValidator；它將自動運行您保存在文件夾中的求和證明數據文件

7、檢查結果

如果驗證通過，將顯示結果Total sum和非負約束驗證通過

如果驗證失敗，將顯示結果Total sum和非負約束驗證失敗

為了探索更多技術細節，我們的儲備證明系統是開源的，可在github上查看和使用。