零知識證明：zk-STARK 是什麼？它如何運作？

1. 什麼是 zk-STARK？

zk-STARK 儲備金證明系統運用了一種稱為 STARK 理論的復雜數學模型。zk-STARK是「Zero-Knowledge Scalable Transparent Arguments of Knowledge」(零知識可擴展透明知識論證) 的縮寫，這是一種加密證明技術，由以太坊發明人維塔利克-布特林 (Vitalik Buterin，即「V神」) 的理論發展而來，旨在透過區塊鏈確保計算的完整性和隱私性。本文將介紹 zk-STARK 的原理并解釋一般的數學概念。如果您想深入瞭解相關資訊，可以參考以下資料： https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71 https://vitalik.eth.limo/general/2017/11/09/starks_part_1.html

zk-STARK 如何運作？

圖 1：zk-STARK 儲備金證明執行記錄表和默克爾樹

**第一步：**設定約束條件

為了證明平臺持有的用戶資產，我們先提出三項陳述：

**陳述 1：**平臺每名用戶資產價值的總和是正確的，包括每種數字貨幣的價值和全部用戶的凈資產價值。

**陳述 2：**平臺沒有透過偽造凈資產為負的虛擬用戶，來減少平臺持有用戶資產價值的賬面數字 (僅當單一用戶的凈資產大于 0 時，才允許存在負余額)。

**陳述 3：**平臺持有的用戶資產總和等于每一名用戶的資產之和，因此每位用戶都可以驗證其凈資產是否包含在平臺持有的總資產中。

為了驗證上述三項陳述，我們需要先構建約束條件，例如：

**陳述 1：**余額總和約束 (驗證余額總和計算結果是否正確)

uts：用戶記錄體量 (user trace size)，即每名用戶的數據記錄表的行數

sum：總用戶余額

N：用戶數量

**陳述 2：非負約束 (驗證總資產是否為正)

**陳述 3：包含性約束 (驗證是否所有用戶的資產都已包括在結果之內)

根據上述約束條件，我們創建一個記錄表，透過抽樣檢查來提交和驗證余額總和及非負性。以下是構建記錄表的方法 (舉一個簡單的例子，假設有 3 個用戶，總資產價值小于 4^6 = 4096 USD)：

1. 首先創建一個 32 × 5 的表格，并將用戶的資產價值和 ID 填入第

行，其中 k % 8 = 6，且

。每 8 行是一個區域，用戶資產信息現在在每個區域的倒數第

個位置。假設第一個用戶的余額為 0，因此我們可以將其公佈，證明資產價值總和的計算不是從負值開始的。

2. 將用戶的資產價值逐個累加，將結果填入第

行，此處 k % 8 = 7，且

，即每個區域的最後一行。

3. 從每個區域的倒數第

個位置開始，逐行將每個用戶的總價值除以 4 并向下取整，進而透過檢查每個區域的前幾行是否為零來確保每個用戶的凈資產價值非負。如果某個用戶的凈資產價值為負，該用戶相應區域的第一行將不為零，因為在有限域

中，負數 (-x) 會變成 (p - x)，這是一個非常大的正數。

4. 為每個用戶配對一個隨機數，并在表格中的空白部分填入 0。

第二步：低次多項式擴展

利用上述多項式約束，我們可以得到一個長度為 uts * N 的計算記錄多項式。出于安全考慮，我們在一個更大的評估域上進行多項式承諾，擴展因子為 extension_factor。

在上述情況下，我們可以從 I(x) 計算出一個多項式 p(x)。當我們使用擴展因子 8 時，我們將在 p(x) 上計算另外 32 * (8-1) 個點。

由于兩個不同的 D 次多項式最多共享 D 個點，因此具有有效多項式 (滿足上述約束條件) 和 D 次假多項式 (不滿足上述約束條件) 的多項式對最多共享 D 個點。這意味著假多項式有

次機會通過隨機抽樣檢查。如果我們進行 n 次抽樣檢查，機會會降低到

。

我們默認將 extension_factor 設置為 16，將抽樣檢查默認次數設置為 16，因此安全級別將為 80 位。

第三步：多項式承諾

我們使用計算記錄和相應的用戶余額、用戶 ID 以及每行對應約束多項式的值來計算哈希值，并生成默克爾樹 (Mekel tree)。默克爾樹根是多項式的承諾 (commitment) 值。

第四步：生成抽樣證明

使用默克爾樹根作為隨機源對數據進行抽樣。為避免洩露計算記錄數據，在抽樣過程中將會避免使用序號為 *k ** extension_factor 的數據，并生成相應的默克爾證明路徑。

然後進行抽樣檢查，檢查承諾的多項式是否是滿足第一步中列出的約束條件的有效多項式。如第二步所述，抽樣檢查的次數將影響結果遭到篡改的可能性。

第五步：生成低次證明

我們可以透過抽樣檢查來控制結果遭到篡改的概率。但如第二步所述，我們需要確保驗證的多項式次數不超過有效多項式的次數。為了提高證明效率，我們將所有約束多項式線性組合成一個多項式，并為其生成低次證明。組合係數也是使用默克爾樹根作為隨機源生成的。

例如，如果我們想證明 p0(x)、p1(x) 和 p2(x) 不超過 D 次，我們可以從第三步生成的默克爾樹根中生成 2 個隨機係數，并計算線性多項式 l(x)：

k0 = hash(root + "0") k1 = hash(root + "1") l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

如果可以證明 l(x) 不超過 D 次，則 p0(x)、p1(x) 和 p2(x) 中任何一個的次數超過 D 的機會將接近于 0。

**第六步：**總余額驗證

首先驗證第五步生成的低次證明，然後在第四步生成的抽樣數據上進行進一步的開放驗證。首先驗證數據是否與多項式承諾一致，其次驗證數據是否滿足第一步中構建的約束條件。最後，驗證低次測試多項式的組合係數。

第七步：生成包含性證明

為了證明每名用戶的資產均包含在交易持有資產總額中，我們提供用戶的計算記錄、用戶余額、用戶 ID 以及與用戶序號相對應的隨機數，以及相應的默克爾路徑。

第八步：用戶驗證包含性證明

用戶可以檢查他們的余額、ID，計算與他們序號對應數據的哈希值，并使用默克爾路徑驗證葉子節點上的哈希值。

2. 如何 自行驗證 儲備金證明？

2.1 驗證 zk-STARK 包含性約束

驗證理論

按照 STARK 程序，我們將計算所有用戶資產的執行記錄表，并將每個用戶的信息加密生成哈希值記錄表，作為默克爾樹的葉子節點，然後將葉子節點提交到將在每輪儲備金證明中公佈的默克爾樹根中。

為了驗證您的資產是否包含在樹根中，我們將為您提供默克爾路徑進行驗證。您可以透過將您的資產信息加密生成哈希值來計算您的葉子節點，然後驗證您的葉子節點是否是 OKX 公佈的默克爾樹根的有效葉子節點。

例如，在圖 1 中，ID 為 id_k 的用戶將計算 hashk = hash("20" + "15" + "5" + "id_k" + "99821")，紅色方框中的其他數據將是默克爾路徑驗證，用戶可以透過 OKX 提供的開源工具進行此驗證。

由于默克爾數據樹的葉子節點是經過加密生成的哈希值，您的任何私人信息都不會洩露給他人。

如何驗證：

1. 要驗證您的賬戶資產余額是否以 zk-STARK 默克爾樹葉子節點的形式包含在樹根中，請登錄您 OKX 賬戶，前往【審計】頁面查看近期審計文件，點擊【詳情】查看審計數據。

2. 點擊【複製數據】獲取手動驗證所需的數據。

3. 點擊【複製數據】後，打開記事本或其他文本編輯器，粘貼剛剛複製的 JSON 文本并保存為文件。文件名後綴必須含有「_inclusion_proof.json.」。JSON 文本包含您的賬戶余額和默克爾路徑快照，粘貼完成後請將文件保存在一個新建文件夾中。

JSON 文本如下所示：

{ "batch_inclusion_proof": { "batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed", "total_value": 138312291, "BTC": 2152907, "ETH": 909757, "USDT": 2319557, "random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac", "merkle_path": [ "5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9", "9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da", "973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2", "0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a", "2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a", "4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609", "4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374", "cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab", "ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62", "1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8", "5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933", "e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167" ] }, "trunk_inclusion_proof": { "trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290", "batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "total_value": 2007657936, "BTC": 18915744, "ETH": 21522734, "USDT": 21268768, "random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164", "merkle_path": [ "1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376", "a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b", "413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b", "d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b", "85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6", "d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec", "147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e", "0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4", "b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a", "ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2", "7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf", "239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d", "bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43" ] } }

1. 下載 OKX 的開源驗證工具 zk-STARKValidator

2. 將驗證工具 zk-STARKValidator 和 JSON 文件保存在第三步創建的新文件夾內。在下方示意圖中，我們將驗證工具和數據保存在「下載」文件夾中，命名為「proof-of-reserves」：

1. 打開 zk-STARKValidator 并自動運行保存在文件夾中的 JSON 文本文件。

2. 查看結果

• 如果驗證通過，將顯示如下「Inclusion constraint validation passed」執行結果：

• 如果驗證失敗，將顯示如下「Inclusion constraint validation failed」執行結果：

  

2.2 驗證 zk-STARK 總余額約束和非負約束

如何驗證：

如需驗證 OKX 持有的資產是否真實，以及是否無用戶持有負資產，請前往【審計文件】的【賬戶余額文件】部分下載 zk-STARK 文件，并保存至新建文件夾。

將下載的文件解壓縮，您將獲得一個名為「sum proof data」的文件夾，包括一個聚合證明文件夾和數千個分支證明文件夾，每個文件夾均包含「sum_proof.json」和「sum_value.json」兩個文件。

下載 OKX 的開源驗證工具 zk-STARKValidator

將 zk-STARKValidator和「sum proof data」文件夾保存在第一步新建的文件夾中。在下方示意圖中，我們將驗證工具和數據保存在「下載」文件夾中，命名為「proof-of-reserves」：

打開 zk-STARKValidator 并自動運行保存在文件夾中的「sum proof data」文件。

查看結果

如果驗證通過，將顯示如下「Total sum and non-negative constraint validation passed」執行結果：

如果驗證失敗，將顯示如下「Total sum and non-negative constraint validation failed」執行結果：