什麼是梅克爾樹（Merkle Tree）?

親愛的全球Bitgetters，

梅克爾樹是一種數據結構，又稱雜湊樹。將數據儲存在樹形結構的葉節點中，藉由雜湊值數據逐層記錄到最頂層的根節點，葉節點數據的任何變化都會傳遞給更上層的節點，最後會顯示更改後的數據在樹形的根部。

1. 梅克爾樹的作用

- 零知識證明
- 確保數據不變性
- 確保數據隱私

2. Bitget Limited 的梅克爾樹定義
2.1 節點訊息
每個樹節點中存儲的訊息包含：
1. 雜湊值（Hash value）

2. 用戶資產快照中所包含的幣數（以 BTC、ETH、USDT 為例）

2.2 雜湊規則
葉節點（填充節點除外）

- 加密 Uid：用戶的加密 UID
- nonce：分配給每位用戶唯一的值
- balances：用戶資產快照幣種數量組成 json 字串（注意：去除末尾無效 0，並保留 8 位精度）
父節點

- h1：當前節點的左子節點的 hash
- h2：當前節點的右子節點的 hash
- 階層：父節點所在的位置

樹節點的高度定義：一個完整的梅克爾樹（滿二元樹）需要2^n個葉節點數據，葉節點階層 = n + 1，父節點階層 = 子節點階層 - 1，根節點階層 = 1，葉節點階層為最高

填充節點規則
一個完整的梅克爾樹（滿二元樹）需要 2^n 個葉節點數據，但實際情況數據的數量未必滿足且還可能是奇數。在此種情況下，如果一個節點 k 沒有兄弟節點，則自動填充生成一個兄弟節點 k'，該兄弟節點 hash(k') = hash(k)，節點 k' 的幣種數量設定為零。

範例：

則填充節點 hash4 = hash3，存儲的 balances 為 {"BTC": 0, "ETH": 0,"USDT": 0}，如圖一綠色節點所示：
圖一

因此，hash6 = SHA256 (hash3 + hash3, {BTC: (2+0), ETH:(1+0), USDT:(12+0)}, level)

驗證原理
1. 驗證原理：根據 Bitget Limited 梅克爾樹定義，從用戶本身葉節點開始往上計算父節點的雜湊值，一直到根節點得出雜湊值，對比步驟 1 中獲取到的梅克爾樹路徑中根節點的雜湊值，如果二者相等則通過驗證，不相同則驗證失敗。
2. 範例：結合圖一和下面的 json 文本，依據用戶本身葉節點 h3 和提供的相鄰節點 h4 訊息可以計算出父節點 h6 的雜湊值，再和提供的相鄰節點 h5 訊息可以計算出父節點 h7 的雜湊值，然後和梅克爾樹路徑數據中提供的根節點 h7 訊息對比雜湊值是否相等即可完成驗證。
梅克爾樹路徑數據 json 文本：

驗證步驟：
1. 登入您的 Bitget 帳戶，點擊「資產總覽 - 資產證明」，進入「資產證明」可以直接查看近期審計情況。 您審核時的數據將被默認展開顯示。

2. 如果您想進一步手動驗證您的資產是否包含在梅克爾樹中，您可以按照以下驗證步驟進行操作。 點擊「下載數據」按鈕，獲取手動驗證所需的數據，下載默認名稱的文件：merkel_tree_bg.json

3. 實際操作：
在我們的範例中，文件名為 merkel_tree_bg.json。梅克爾樹路徑數據 json 的文本如下所示：

4. 下載 Bitget Limited 提供的開源驗證工具 ProofOfReserves.zip。
5. 將 ProofOfReserves.zip 文件解壓縮到當前目錄，並將步驟 3 中保存的 merkel_tree_bg.json 文件存放到同一個資料夾中。 在我們的範例中，文件儲存在下載項目中，資料夾名稱為 proof-of-reserves，截圖如下：

6. 打開終端程式（Mac系統：終端機應用程式。Windows系統：CMD應用程式）
7. 輸入指令 cd ~/Downloads/proof-of-reserves 在終端程式中，並輸入下載檔案的目錄
8. 輸入以下指令驗證您的數據

Mac/Linux

Windows
點擊 start.bat 資料夾

請注意：如果您使用的是 Mac 系統，並在此步驟中遇到安全設定問題，請至系統偏好設定 -> 安全性與隱私權 -> 一般 -> 按一下鎖頭，以進行更改 -> 允許以下來源下載的 App：App Store 和已識別的開發者 -> 給予工具權限
如果出現以下問題，zsh: permission denied: . /start.sh，請執行以下指令

9. 查看結果
(1) 如果您的數據正確且通過驗證，結果會是「梅克爾樹根雜湊值一致，驗證成功」。

(2) 如果您的數據有誤且驗證失敗，結果會是「梅克爾樹根雜湊值不一致，驗證失敗」。

10. 您也可以參考 Bitget Limited 開源驗證工具代碼和梅克爾樹定義（參考「什麼是梅克爾樹」段落）自行編寫程式驗證在步驟 2 中得到的路徑數據，確認您的資產被包含在此次審計生成的梅克爾樹中。

Bitget 團隊