Merkle Tree¶

来源：密码学引论 / electronic_payment/Merkle Tree.md

它是一种用来高效验证数据完整性的树形结构，在区块链、Git、文件校验、分布式存储里都很常见。

1. Merkle Tree 的核心思想¶

假设有 4 笔交易：

Tx1, Tx2, Tx3, Tx4

先分别对每笔交易做哈希：

H1 = Hash(Tx1)
H2 = Hash(Tx2)
H3 = Hash(Tx3)
H4 = Hash(Tx4)

然后两两合并，再哈希：

H12 = Hash(H1 || H2)
H34 = Hash(H3 || H4)

最后再把上一层的哈希合并：

Root = Hash(H12 || H34)

整体结构是：

              Root
             /    \
          H12      H34
         /  \      /  \
       H1   H2   H3   H4
       |    |    |    |
      Tx1  Tx2  Tx3  Tx4

最上面的 Root 就叫 Merkle Root，也就是默克尔根。

2. 它有什么用？¶

Merkle Tree 最重要的作用是：

用一个很短的哈希值，代表一大堆数据的整体完整性。

比如一个区块里有几千笔交易，如果你只保存 Merkle Root，那么只要任何一笔交易被改动，最终的 Root 都会变化。

例如 Tx3 被篡改：

Tx3 -> Tx3'

那么：

H3 变
H34 变
Root 变

所以只要比较 Root，就能知道整批数据有没有被改过。

3. 为什么不用直接 Hash 所有交易？¶

也可以直接：

Hash(Tx1 || Tx2 || Tx3 || Tx4)

但这样有一个问题：如果你只想证明 Tx3 在不在这一批交易里，你可能需要拿出所有交易重新算一遍。

Merkle Tree 的优势是：

只需要提供一小部分路径信息，就能证明某个数据属于这棵树。

4. Merkle Proof 是什么？¶

假设你想证明 Tx3 在这棵树里。

你不需要给出所有交易，只需要给出：

Tx3
H4
H12
Root

验证过程是：

H3 = Hash(Tx3)
H34 = Hash(H3 || H4)
Root' = Hash(H12 || H34)

如果算出来的 Root' 等于已知的 Root，就说明 Tx3 确实在这棵 Merkle Tree 里。

证明路径大概是：

              Root
             /    \
          H12      H34
                  /   \
                H3     H4
                |
               Tx3

要证明 Tx3，只需要补充它的兄弟节点 H4 和上层的兄弟节点 H12。

5. 它为什么高效？¶

假设有 n 条数据。

如果直接验证，可能要检查很多数据，复杂度接近：

O(n)

而 Merkle Tree 只需要沿着树高验证，复杂度是：

O(log n)

比如有 1024 笔交易，树高大约是 10。

你只需要大约 10 个哈希值，就能证明某笔交易在区块中，而不是拿出全部 1024 笔交易。

6. 在比特币里的作用¶

在比特币区块中，区块头里不会保存所有交易，只保存一个 Merkle Root。

区块大概可以理解成：

Block Header:
    previous block hash
    timestamp
    nonce
    Merkle Root

Block Body:
    transaction list

Merkle Root 是这个区块中所有交易的摘要。

如果区块里的任意一笔交易发生变化，Merkle Root 就会变化，从而导致区块头哈希变化，整个区块就不再合法。

7. 和最长链原则的关系¶

最长链原则决定：

哪条区块链分支是主链。

Merkle Tree 决定：

一个区块内部的交易是否被正确包含、是否被篡改。

也就是说：

最长链原则：解决区块和区块之间的共识问题
Merkle Tree：解决区块内部交易集合的完整性证明问题

一句话总结：

Merkle Tree 是一种把大量数据逐层哈希成一个根哈希的树形结构。它可以用很小的证明，验证某条数据是否属于某个数据集合，并且能快速发现数据是否被篡改。