区块链:Merkle树生成算法的详细过程解析

Merkle树是Hash的二叉树。在比特币中会两次使用SHA-256算法来生成Merkle树,如果叶业节点为奇数,则要重复计算最后一个叶子的两次SHA-256值,以达到偶数叶子节点的要求。

以下是区块链中 Merkle树生成算法 的详细过程解析,配合具体示例说明。Merkle树是区块链的核心数据结构,用于高效验证交易完整性,其生成过程遵循密码学递归原则。


Merkle树生成算法步骤

  • 输入:交易列表 [Tx1, Tx2, Tx3, ..., Txn]
  • 输出:32字节的Merkle根哈希(存入区块头)

算法流程

  • 首选按照区块中交易的两次SHA-256进行散列,然后按照Hash值的大小进行排序,生成最底层。

  • 第二层的每个元素则是相邻的两个Hash值的两次SHA-256的Hash值。

  • 之后,会重复这个过程,直到某一层只有一个Hash值为止,这就是Merkle根。

1. 计算叶子节点哈希

  • 为每笔交易计算双SHA-256哈希:
    LeafHash(Tx) = SHA256(SHA256(Tx_data))
  • 若交易数为奇数,复制最后一笔交易(比特币规则)

2. 构建中间层节点

  • 将相邻两个哈希值拼接(左节点 + 右节点)
  • 计算拼接后的双SHA-256哈希:
    ParentHash = SHA256(SHA256(LeftChildHash ∥ RightChildHash))

3. 递归计算直至根节点

  • 重复步骤2,每层节点数减半,直到生成唯一根哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 伪代码实现
def build_merkle_tree(transactions):
if len(transactions) == 0:
return None
if len(transactions) == 1:
return double_sha256(transactions[0])

# 处理奇数个交易
if len(transactions) % 2 != 0:
transactions.append(transactions[-1])

new_level = []
for i in range(0, len(transactions), 2):
combined = transactions[i] + transactions[i+1]
new_level.append(double_sha256(combined))

return build_merkle_tree(new_level)

生成示例

假设4笔交易的原始哈希值(简化成4字节):

交易 原始数据 交易哈希 (SHA256)
Tx1 “Alice→Bob 1 BTC” H1 = 6b6a
Tx2 “Bob→Carol 0.5 BTC” H2 = 2d9d
Tx3 “Carol→Dave 0.3 BTC” H3 = c1d7
Tx4 “Dave→Eve 0.2 BTC” H4 = 3860

生成过程图示

1
2
3
4
5
6
7
8
Level 3 (Root): 
Hash(H12 + H34) = H1234 [最终Merkle根]
/ \
/ \
Level 2: H12 H34
/ \ / \
Level 1: H1 H2 H3 H4
[Tx1] [Tx2] [Tx3] [Tx4]

逐步计算说明

  1. 叶子层(Level 1)

    • 保持原始交易哈希:[H1, H2, H3, H4] = [6b6a, 2d9d, c1d7, 3860]
  2. 中间层(Level 2)

    • 计算 H12 = SHA256(SHA256(H1 + H2))
      → 输入:6b6a + 2d9d = "6b6a2d9d"
      → 输出:12ab(示例值)
    • 计算 H34 = SHA256(SHA256(H3 + H4))
      → 输入:c1d7 + 3860 = "c1d73860"
      → 输出:34cd(示例值)
  3. 根节点(Level 3)

    • 计算 H1234 = SHA256(SHA256(H12 + H34))
      → 输入:12ab + 34cd = "12ab34cd"
      → 输出:abcd(最终Merkle根)

奇数交易处理示例

当交易数为奇数时,复制最后一笔交易,下面以3笔交易为例。

1
2
3
4
5
6
原始交易: [Tx1, Tx2, Tx3] → 处理后: [Tx1, Tx2, Tx3, Tx3*]  (Tx3*为复制项)

Level 2:
H12 = Hash(H1+H2) H33 = Hash(H3+H3*) # 注意H3被复制
\ /
Level 3: Hash(H12 + H33) = Root

计算过程

  1. 复制Tx3:[H1, H2, H3, H3] = [6b6a, 2d9d, c1d7, c1d7]
  2. 计算 H12 = SHA256(SHA256("6b6a2d9d")) → 12ab
  3. 计算 H33 = SHA256(SHA256("c1d7c1d7")) → 77ff(相同哈希拼接结果不同)
  4. 计算根:H1233 = SHA256(SHA256("12ab77ff")) → ef01

Merkle树的关键特性

  1. 不可篡改性

    • 修改任一交易 → 导致其父节点哈希变化 → 连锁改变根哈希
    • 示例:篡改Tx3后:
      H3' ≠ H3H34' ≠ H34H1234' ≠ H1234
  2. 高效验证(Merkle证明)

    • 验证Tx2是否在区块中,只需提供:
      [H1, H34] + 根哈希 abcd
    • 计算路径:H2 → Hash(H1+H2) → Hash(H12+H34) = abcd
  3. 空间优化

    • 无论交易数量多少,Merkle根固定 32字节
    • 1万笔交易的区块,验证单笔交易只需 log₂(10000)≈14个哈希值

真实区块链的Merkle根示例

比特币创世区块(Block 0)的Merkle根:
4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b
由单笔Coinbase交易生成:H_root = SHA256(SHA256(Tx_coinbase))


总结

  • 输入:原始交易列表
  • 处理:递归哈希(叶子→父节点→根节点)
  • 输出:32字节Merkle根(写入区块头)
  • 核心价值
    • ✅ 实现轻节点快速交易验证(SPV)
    • ✅ 确保交易历史不可篡改
    • ✅ 节省区块验证所需带宽

通过这种树状结构,区块链在保持去中心化的同时,实现了对数级复杂度的数据验证效率。

区块链:Merkle树生成算法的详细过程解析

http://blog.gxitsky.com/2025/06/29/Blockchain-03-Merkle-Hash/

作者

光星

发布于

2025-06-29

更新于

2025-07-05

许可协议

评论