#104 資料完整性的守護者 - 淺談 Merkle Tree ~ 大毛電腦科學筆記

當你在使用 Git 版本控制時，當你在下載 BitTorrent 檔案時，當你在使用區塊鏈應用時，有一個默默運作的資料結構正在背後確保你拿到的資料是正確的、完整的、沒有被竄改的。這個資料結構就是 Merkle Tree，它的發明者是密碼學家 Ralph Merkle，因此也有人稱它為 Hash Tree。

Merkle Tree 要解決什麼問題？

想像你正在從網路上下載一個 10GB 的電影檔案。下載完成後，你怎麼知道這個檔案是完整的？沒有在傳輸過程中損壞？更重要的是，沒有被惡意竄改？

最直覺的做法是什麼？對，就是計算整個檔案的 hash 值，例如 SHA-256，然後跟官方公布的 hash 值比對。如果一致，就代表檔案是完整且正確的。這方法聽起來不錯，但有個致命的缺點：如果下載到一半發現檔案損壞了，你得重新下載整個 10GB 的檔案。

再進一步想，如果你是從 P2P 網路下載檔案，檔案被切成了數千個小區塊 (chunk)，分別從不同的節點下載。你要怎麼確保每一個區塊都是正確的？難道要為每一個區塊都儲存一個 hash 值嗎？如果有 10,000 個區塊，你就得儲存 10,000 個 hash 值，這也是個很大的負擔。

Merkle Tree 就是為了解決這個問題而生的。它讓你能夠：

快速驗證某一小塊資料是否正確，而不需要下載或檢查整個檔案
用相對少量的 hash 值就能驗證大量的資料區塊
當資料有問題時，能快速定位出是哪一塊出了問題

Merkle Tree 的結構

Merkle Tree 本質上就是一種二元樹 (Binary Tree)，但它有一個很特別的性質：每一個節點都儲存了一個 hash 值。

讓我們從最簡單的例子開始。假設你有四筆資料：A, B, C, D。

第一步：計算葉節點 (Leaf Nodes) 的 hash

Hash(A) = h_A
Hash(B) = h_B
Hash(C) = h_C
Hash(D) = h_D

第二步：兩兩配對，計算父節點的 hash

Hash(h_A + h_B) = h_AB
Hash(h_C + h_D) = h_CD

第三步：繼續往上，計算根節點 (Root) 的 hash

Hash(h_AB + h_CD) = h_ABCD

最終的結構會長這樣：

           h_ABCD (Root Hash)
          /                \
       h_AB                h_CD
      /    \              /    \
    h_A    h_B          h_C    h_D
     |      |            |      |
     A      B            C      D

這個最頂端的 h_ABCD 就是 Merkle Root，它代表了整棵樹的 hash 值。只要底下任何一筆資料改變了，Merkle Root 也會跟著改變。

如何建立 Merkle Tree

建立 Merkle Tree 的演算法其實很簡單，步驟如下：

準備資料區塊：將原始資料切成固定大小的區塊。如果資料總數不是 2 的次方，可以用空白資料或重複最後一個區塊來補齊。
計算葉節點 hash：對每一個資料區塊計算 hash 值，這些 hash 值就是葉節點。
向上建構：將相鄰的兩個節點配對，將它們的 hash 值串接後再做一次 hash，得到父節點的 hash 值。
重複第三步：繼續往上層建構，直到只剩下一個節點，這就是 Merkle Root。

讓我們看一個簡單的 Python 實作概念：

import hashlib

def hash_data(data):
    """計算資料的 SHA-256 hash"""
    return hashlib.sha256(data.encode()).hexdigest()

def build_merkle_tree(data_blocks):
    """建立 Merkle Tree"""
    # 第一層：葉節點
    current_level = [hash_data(block) for block in data_blocks]
    
    # 向上建構，直到剩下一個根節點
    while len(current_level) > 1:
        next_level = []
        # 兩兩配對
        for i in range(0, len(current_level), 2):
            left = current_level[i]
            # 如果是奇數個節點，最後一個自己跟自己配對
            right = current_level[i + 1] if i + 1 < len(current_level) else left
            # 計算父節點的 hash
            parent_hash = hash_data(left + right)
            next_level.append(parent_hash)
        current_level = next_level
    
    # 回傳 Merkle Root
    return current_level[0]

# 使用範例
data = ["區塊 A", "區塊 B", "區塊 C", "區塊 D"]
merkle_root = build_merkle_tree(data)
print(f"Merkle Root: {merkle_root}")

建立一棵 n 個葉節點的 Merkle Tree，時間複雜度是 O(n)，因為每一個節點只需要計算一次 hash。空間複雜度也是 O(n)，因為總共會有大約 2n 個節點（葉節點 n 個，內部節點約 n 個）。

Merkle Tree 的應用場景

Merkle Tree 在許多分散式系統和需要資料完整性驗證的場景中都有重要的應用。

1. P2P 檔案分享系統

在 BitTorrent 這類的 P2P 檔案分享系統中，Merkle Tree 扮演了關鍵角色。檔案被切成數千個小區塊，分散在網路上不同的節點。當你下載這些區塊時，系統會用 Merkle Tree 來驗證每一個區塊的正確性。

傳統方法需要為每個區塊儲存一個 hash 值。如果有 10,000 個區塊，你就需要儲存 10,000 個 hash（假設每個 hash 是 32 bytes，就是 320KB）。但使用 Merkle Tree，你只需要儲存一個 Merkle Root（32 bytes）以及驗證時需要的路徑 hash 值即可。

2. 分散式資料庫

在分散式資料庫系統中，不同節點上的資料需要保持一致性。Merkle Tree 可以快速比較兩個節點的資料是否相同。如果兩個節點的 Merkle Root 相同，代表它們的資料完全一致；如果不同，可以從樹的上層往下層比較，快速找出哪些資料區塊不一致，只需同步這些不一致的部分即可。

Apache Cassandra 和 DynamoDB 等 NoSQL 資料庫就使用 Merkle Tree 來進行副本之間的資料同步。

3. 區塊鏈技術

在區塊鏈中，每一個區塊都包含了許多筆交易記錄。這些交易記錄會被組織成一棵 Merkle Tree，區塊的標頭 (Header) 只需要儲存 Merkle Root 即可。這帶來兩個好處：

輕量級節點 (Light Client) 只需下載區塊標頭，就能驗證某筆交易是否存在於區塊中
任何一筆交易被竄改，都會導致 Merkle Root 改變，立即被發現

4. Git 版本控制系統

Git 內部使用了類似 Merkle Tree 的結構（雖然不完全相同）來追蹤檔案的變更。每一個 commit 物件都包含了一個指向檔案樹的 hash，確保了程式碼的完整性和不可竄改性。

以 P2P 檔案傳輸為例說明 Merkle Tree 運作

讓我們用一個具體的例子來看 Merkle Tree 如何在 P2P 檔案傳輸中運作。

假設 Alice 想要從 P2P 網路下載一個檔案，這個檔案被切成 8 個區塊：D0, D1, D2, D3, D4, D5, D6, D7。

步驟一：建立 Merkle Tree

                      Root
                    /      \
                H01          H23
               /  \          /  \
           H01a  H01b    H23a  H23b
           /  \   /  \    /  \   /  \
          L0  L1 L2 L3  L4  L5 L6  L7
          |   |  |  |   |   |  |   |
          D0  D1 D2 D3  D4  D5 D6  D7

檔案的提供者（種子節點）會先建立這個檔案的 Merkle Tree：

其中：

L0 = Hash(D0), L1 = Hash(D1), ..., L7 = Hash(D7) ← 葉節點（Leaf）
H01a = Hash(L0 + L1), H01b = Hash(L2 + L3), H23a = Hash(L4 + L5), H23b = Hash(L6 + L7) ← 第二層
H01 = Hash(H01a + H01b), H23 = Hash(H23a + H23b) ← 第三層
Root = Hash(H01 + H23) ← 根節點

種子節點只需要公布 Merkle Root 給所有想下載檔案的節點。

步驟二：下載資料區塊

Alice 開始從不同的節點下載檔案區塊。假設她從節點 Bob 那裡下載了區塊 D2。

步驟三：驗證資料完整性

為了驗證 D2 是否正確，Alice 需要什麼？她不需要下載所有的資料區塊，她只需要：

D2 本身
D2 的 "姐妹節點" L3（D3 的 hash）
D2 父節點的姐妹節點 H01a
第三層的姐妹節點 H23
Merkle Root（這個她早就知道了）

驗證過程如下：(驗證 D2)

                      Root (已知)
                    /      \
                H01          H23 (需要)
               /  \          
           H01a    H01b (計算)
                    /  \
                   L2   L3 (需要)
                  (計算)  
                   |   
                   D2 (下載的資料)

Alice 計算 L2 = Hash(D2)
Bob 同時提供 L3（D3 的 hash）給 Alice
Alice 計算 H01b = Hash(L2 + L3)
Bob 提供 H01a 給 Alice
Alice 計算 H01 = Hash(H01a + H01b)
Bob 提供 H23 給 Alice
Alice 計算 Root' = Hash(H01 + H23)
比較 Root' 是否等於 Root

如果 Root' == Root，代表 D2 是正確的！整個驗證過程，Alice 只需要額外接收三個 hash 值（L3、H01a 和 H23），而不需要下載其他 7 個資料區塊。

步驟四：持續下載與驗證

Alice 繼續從不同節點下載其他區塊，每次都用類似的方法驗證。如果某個區塊驗證失敗，她知道這個區塊有問題（可能損壞或被竄改），可以向其他節點重新請求這個特定的區塊，而不用重新下載整個檔案。

為什麼這個方法有效？

關鍵在於 hash 函數的特性：

確定性：相同的輸入永遠產生相同的輸出
不可逆：無法從 hash 值反推原始資料

輸入的微小改變會導致 hash 值完全不同。所以，如果 D2 被竄改了哪怕一個位元，計算出來的 L2 就會完全不同，最終計算出來的 Root' 也會不同，驗證就會失敗。

Merkle Proof：驗證的效率

在上面的例子中，為了驗證 D2，Alice 需要接收 log₂(n) 個額外的 hash 值（其中 n 是資料區塊總數）。在我們的例子中，n = 8，所以需要 log₂(8) = 3 個額外的 hash（L3, H01a, H23，加上 Root 本身已知）。

這組用來驗證某個資料區塊的 hash 值集合，稱為 Merkle Proof 或 Merkle Path。

假設每個 hash 是 32 bytes（SHA-256），那麼：

傳統方法：需要儲存 8 個 hash = 256 bytes
Merkle Tree：只需要 3 個 hash = 96 bytes

當資料區塊數量增加時，這個優勢更加明顯：

1,024 個區塊：傳統方法 32KB vs Merkle Tree 320 bytes（log₂(1024) = 10）
1,048,576 個區塊：傳統方法 32MB vs Merkle Tree 640 bytes（log₂(1048576) = 20）

這就是為什麼 Merkle Tree 在大規模分散式系統中如此重要且有效率。了解 Merkle Tree 不僅能幫助你更深入了解這些系統的運作原理，也能在設計需要資料驗證的系統時，提供一個優雅且高效的解決方案。

大毛電腦科學筆記