# Space and Time Blog | 理解何謂 Merkle Tree 默克爾樹

By [0xKC](https://paragraph.com/@1886) · 2023-04-21

---

在本文中，我將探討 Merkle Tree（默克爾樹）這種數據結構。

![Merkle Tree Meme](https://storage.googleapis.com/papyrus_images/13eba70c13d402e0d8bffddcda96e8a8df290143a9fbf67fcb6e848df974c3f7.jpg)

Merkle Tree Meme

### 簡介

**默克爾樹**在比特幣區塊鏈中得到了最為普及的應用。它們是樹狀的數據結構，其中每個節點都是其子節點的加密哈希值。位於樹的頂部的 Merkle Root（Merkle 根）代表整個數據集。

默克爾樹是一個碰撞抗性哈希函數，表示為 𝖬𝖧𝖳，它接受 n 個輸入（x1、x2、...、xn），並輸出一個 Merkle Root 哈希值 h=𝖬𝖧𝖳(x1、x2、...、xn)。

默克爾樹用於存儲和驗證交易。交易首先個別哈希，然後分組成對，再將其哈希成新的節點。這個過程重複進行，直到只剩下一個節點，即 Merkle Root。

驗證者擁有根節點哈希 H，可以給它一個與 xi 相關的 Merkle 證明，證明 xi 是用於計算 h 的第 i 個輸入。

### 創建默克爾樹

我們可以通過一個例子來開始創建 Merkle Tree。例如，有一個輸入數組 A = (x1, x2, x3, x4, x5, x6, x7, x8)，其中有 8 個元素。要從這個數組中創建 Merkle Tree，可以按照以下步驟進行：

1.  把輸入數組兩兩配對
    
2.  對每一對數據作一次密碼學哈希，得到一個新的哈希值，這個哈希值將作為子節點的哈希值
    
3.  如果有奇數個數據，則把最後一個數據視為一個數據對，其哈希值與自己相同
    
4.  重複步驟 1 和步驟 2，直到僅剩一個根節點，這個根節點的哈希值就是 Merkle Tree 的根哈希值
    

當然，密碼學哈希函數 H 必須是碰撞抗性的，即對於任意兩個不同的輸入 x 和 x'，計算 H(x) 和 H(x') 所需要的時間應該相當長，並且不可能在這個生命中找到兩個不同的輸入 x 和 x'，使得它們的哈希值相同（即 H(x)=H(x')）。

![](https://storage.googleapis.com/papyrus_images/9732d7dc1e41d7a923d84ef5bf7f3cb73834a44b4efc1b417d1a7c70c0a2c904.png)

### 默克爾樹驗證

從數學上來看，Merkle Hash Tree 可以表示如下：

    Merkle root = MHT(x1, x2, … , x8)
    = h(
    h(
    h( h(x1), h(x2) ), h( h(x3), h(x4) ) ),
    h(
    h( h(x5), h(x6) ), h( h(x7), h(x8) )
    )
    )
    

這再次向我們展示了 Merkle 樹的遞歸性。

現在，假設我們得到了一個輸入 x\*，並且被問及它是否屬於用於創建 Merkle 樹的數組。

我們可以使用 Merkle 哈希樹的部分並填寫下面的空白以獲得 Merkle 根節點。現在，如果 Merkle 根節點與原始的 Merkle 根節點匹配，那麼我們可以絕對肯定地說 x\* 屬於第五個位置的數組中。

![](https://storage.googleapis.com/papyrus_images/d211bd66b684944e68ec5d3a5c1febd7706cfd72b20b45c71946f2e48ce09ccf.png)

### Merkle Trees 的優點

使用 Merkle Trees 在區塊鏈中有幾個優勢。首先，它允許有效的交易驗證。節點不需要驗證每個交易，只需驗證代表整個數據集的 Merkle root 即可。

其次，它允許交易以緊湊的方式存儲。Merkle tree 允許僅存儲 Merkle root，而不是將所有交易存儲在一個區塊中，這使得存儲更小。

最後，Merkle tree 允許快速同步節點。當新節點加入網絡時，它只需要請求 Merkle root，而不是整個數據集，這使得同步更快，更高效。

### Merkle Trees 的缺點

雖然 Merkle Trees 為區塊鏈技術提供了多種好處，但還有一些潛在問題需要考慮。

一個問題是碰撞攻擊的可能性，即兩個不同的數據集產生相同的 Merkle root。這可能會讓惡意用戶在不被檢測到的情況下篡改數據。

另一個問題是可能的 51％ 攻擊，即單個實體或群體控制網絡的大部分計算能力。在這種情況下，攻擊者可能會修改 Merkle tree 中的交易及其相應的哈希，而網絡將其視為有效。

需要注意的是，儘管存在這些問題，但它們不一定會使 Merkle Trees 失效。正確的實施和安全措施可以幫助減輕這些風險，確保區塊鏈的完整性。

### 結論

除了區塊鏈之外，Merkle 樹還可以用於檢測從惡意渠道下載的任何文件的惡意或意外修改。

雖然 Merkle 樹是在區塊鏈技術中存儲和驗證數據的廣泛使用和有效方法，但也有一些替代方法。

其中一種方法是使用稀疏 Merkle 樹，它們類似於常規 Merkle 樹，但僅存儲樹的非空葉子。這可以減少存儲要求並在某些情況下提高效率。

有 n 個葉子的 Merkle 樹具有 O(log2 n) 大小的證明。在大型樹中，傳送證明可能會佔用帶寬消耗。向量承諾（VC）是 Merkle 樹的一個潛在替代方法，具有恆定大小的證明。

Space and Time 是一個去中心化的數據倉庫，也受到了 Merkle 樹等各種方法的啟發。然而，Proof of SQL 具有自己的實現，用於解決分散化的問題。我們的證明團隊一直在努力創建一種可持續的方法，改進 Merkle 樹並使用 zk-SNARKs 的各種方法。我們很快會在這方面寫更多的內容。

最終，選擇區塊鏈系統的數據結構將取決於網絡的具體需求和要求。Merkle 樹仍然是許多區塊鏈應用的流行和有效選擇，但在某些情況下，其他選擇可能更適合。

---

*Originally published on [0xKC](https://paragraph.com/@1886/space-and-time-blog-merkle-tree)*