Merkle 树系列：从基础到高级的完整指南

3166 字

16 分钟

Merkle 树系列：从基础到高级的完整指南

2025-01-27

Web3

Merkle树

/

区块链

/

数据结构

/

密码学

/

分布式系统

在区块链和分布式系统中，Merkle树系列数据结构扮演着至关重要的角色。本文深入解析三种重要的Merkle树变体，帮助开发者理解其设计原理、应用场景和实现细节。

📚 概述#

Merkle树系列是密码学和分布式系统中的核心数据结构，通过树状结构和哈希验证机制，为数据完整性验证、状态管理和高效查询提供了强大的工具。

三种主要类型#

普通Merkle树 - 基础的数据完整性验证
稀疏Merkle树 - 处理稀疏数据集的高效方案
Merkle Patricia树 - 结合路径压缩的状态管理

🌳 普通 Merkle 树#

核心设计#

普通Merkle树是一种二叉树结构，用于验证大量数据的完整性：

1
        Root Hash
2
       /         \
3
   Hash(AB)    Hash(CD)
4
   /     \     /     \
5
 Hash(A) Hash(B) Hash(C) Hash(D)
6
   |       |       |       |
7
  DataA   DataB   DataC   DataD

JavaScript 实现#

1
import crypto from 'crypto';
2

3
class MerkleTree {
4
  constructor(leaves, hashFunction = 'sha256') {
5
    this.leaves = leaves.map(leaf => this.hash(leaf, hashFunction));
6
    this.hashFunction = hashFunction;
7
    this.tree = this.buildTree();
8
  }
9

10
  hash(data, algorithm = this.hashFunction) {
11
    return crypto.createHash(algorithm).update(data).digest('hex');
12
  }
13

14
  buildTree() {
15
    if (this.leaves.length === 0) return [];
16
    if (this.leaves.length === 1) return this.leaves;
17

18
    let currentLevel = [...this.leaves];
19
    const tree = [currentLevel];
20

21
    while (currentLevel.length > 1) {
22
      const nextLevel = [];
23

24
      for (let i = 0; i < currentLevel.length; i += 2) {
25
        const left = currentLevel[i];
26
        const right = currentLevel[i + 1] || left;
27
        const combined = left + right;
28
        nextLevel.push(this.hash(combined));
29
      }
30

31
      tree.push(nextLevel);
32
      currentLevel = nextLevel;
33
    }
34

35
    return tree;
36
  }
37

38
  getRoot() {
39
    return this.tree[this.tree.length - 1][0];
40
  }
41

42
  getProof(index) {
43
    if (index < 0 || index >= this.leaves.length) {
44
      throw new Error('Invalid leaf index');
45
    }
46

47
    const proof = [];
48
    let currentIndex = index;
49

50
    for (let level = 0; level < this.tree.length - 1; level++) {
51
      const levelNodes = this.tree[level];
52
      const isLeft = currentIndex % 2 === 0;
53
      const siblingIndex = isLeft ? currentIndex + 1 : currentIndex - 1;
54

55
      if (siblingIndex < levelNodes.length) {
56
        proof.push({
57
          data: levelNodes[siblingIndex],
58
          position: isLeft ? 'right' : 'left'
59
        });
60
      }
61

62
      currentIndex = Math.floor(currentIndex / 2);
63
    }
64

65
    return proof;
66
  }
67

68
  verify(leaf, proof, root) {
69
    let hash = this.hash(leaf);
70

71
    for (const proofNode of proof) {
72
      const left = proofNode.position === 'left' ? proofNode.data : hash;
73
      const right = proofNode.position === 'right' ? proofNode.data : hash;
74
      hash = this.hash(left + right);
75
    }
76

77
    return hash === root;
78
  }
79
}
80

81
// 使用示例
82
const data = ['Alice', 'Bob', 'Charlie', 'David'];
83
const merkleTree = new MerkleTree(data);
84
console.log('Merkle根:', merkleTree.getRoot());
85

86
const proof = merkleTree.getProof(1);
87
const isValid = merkleTree.verify('Bob', proof, merkleTree.getRoot());
88
console.log('验证结果:', isValid);

技术特点#

特性	描述
完整性验证	通过根哈希验证整个数据集
增量验证	只需验证从叶子到根的路径
并行计算	可以并行计算不同分支的哈希值
空间效率	存储空间与数据量成对数关系

应用场景#

区块链: 比特币交易验证、以太坊状态根
分布式系统: 文件系统完整性、数据同步
网络安全: 数字签名验证、证书链验证
数据库: 数据完整性检查、增量备份

复杂度分析#

操作	时间复杂度	空间复杂度
构建树	O(n log n)	O(n)
获取根	O(1)	O(1)
生成证明	O(log n)	O(log n)
验证数据	O(log n)	O(1)

🌿 稀疏 Merkle 树#

核心设计#

稀疏Merkle树具有固定深度，只存储非零叶子节点：

1
                    Root (256层)
2
                   /             \
3
              Hash(0,1)        Hash(2,3)
4
             /         \       /         \
5
        Hash(0)    Hash(1)  Hash(2)    Hash(3)
6
           |          |        |          |
7
         Data1      null    Data2      null

JavaScript 实现#

1
import crypto from 'crypto';
2

3
class SparseMerkleTree {
4
  constructor(depth = 256, hashFunction = 'sha256') {
5
    this.depth = depth;
6
    this.hashFunction = hashFunction;
7
    this.zeroHashes = this.computeZeroHashes();
8
    this.root = this.zeroHashes[this.depth];
9
    this.leaves = new Map();
10
  }
11

12
  hash(data, algorithm = this.hashFunction) {
13
    return crypto.createHash(algorithm).update(data).digest('hex');
14
  }
15

16
  computeZeroHashes() {
17
    const zeroHashes = new Array(this.depth + 1);
18
    zeroHashes[0] = this.hash('0');
19

20
    for (let i = 1; i <= this.depth; i++) {
21
      const prevZero = zeroHashes[i - 1];
22
      zeroHashes[i] = this.hash(prevZero + prevZero);
23
    }
24

25
    return zeroHashes;
26
  }
27

28
  keyToPath(key) {
29
    const hash = this.hash(key);
30
    const path = [];
31

32
    for (let i = 0; i < this.depth; i++) {
33
      const bit = parseInt(hash[i % hash.length], 16) % 2;
34
      path.push(bit);
35
    }
36

37
    return path;
38
  }
39

40
  update(key, value) {
41
    const path = this.keyToPath(key);
42
    const leafHash = this.hash(value);
43

44
    this.leaves.set(key, { value, hash: leafHash, path });
45
    this.root = this.updatePath(path, leafHash);
46
  }
47

48
  updatePath(path, leafHash) {
49
    let currentHash = leafHash;
50

51
    for (let level = 0; level < this.depth; level++) {
52
      const bit = path[this.depth - 1 - level];
53
      const siblingHash = this.getSiblingHash(path, level);
54

55
      if (bit === 0) {
56
        currentHash = this.hash(currentHash + siblingHash);
57
      } else {
58
        currentHash = this.hash(siblingHash + currentHash);
59
      }
60
    }
61

62
    return currentHash;
63
  }
64

65
  getSiblingHash(path, level) {
66
    const levelPath = path.slice(0, this.depth - level);
67
    const siblingPath = [...levelPath];
68
    siblingPath[siblingPath.length - 1] = 1 - siblingPath[siblingPath.length - 1];
69

70
    for (const [key, leaf] of this.leaves) {
71
      if (this.pathsMatch(leaf.path, siblingPath, level)) {
72
        return leaf.hash;
73
      }
74
    }
75

76
    return this.zeroHashes[level];
77
  }
78

79
  pathsMatch(path1, path2, level) {
80
    const start = this.depth - level;
81
    for (let i = 0; i < level; i++) {
82
      if (path1[start + i] !== path2[start + i]) {
83
        return false;
84
      }
85
    }
86
    return true;
87
  }
88

89
  getProof(key) {
90
    const path = this.keyToPath(key);
91
    const proof = [];
92

93
    for (let level = 0; level < this.depth; level++) {
94
      const siblingHash = this.getSiblingHash(path, level);
95
      proof.push(siblingHash);
96
    }
97

98
    return proof;
99
  }
100

101
  verify(key, value, proof, root) {
102
    const path = this.keyToPath(key);
103
    const leafHash = this.hash(value);
104
    let currentHash = leafHash;
105

106
    for (let level = 0; level < this.depth; level++) {
107
      const bit = path[this.depth - 1 - level];
108
      const siblingHash = proof[level];
109

110
      if (bit === 0) {
111
        currentHash = this.hash(currentHash + siblingHash);
112
      } else {
113
        currentHash = this.hash(siblingHash + currentHash);
114
      }
115
    }
116

117
    return currentHash === root;
118
  }
119

120
  getRoot() {
121
    return this.root;
122
  }
123
}
124

125
// 使用示例
126
const smt = new SparseMerkleTree(8);
127
smt.update('user1', 'Alice');
128
smt.update('user2', 'Bob');
129
console.log('稀疏Merkle根:', smt.getRoot());
130

131
const proof = smt.getProof('user1');
132
const isValid = smt.verify('user1', 'Alice', proof, smt.getRoot());
133
console.log('验证结果:', isValid);

技术特点#

特性	描述
稀疏存储	只存储实际存在的数据
固定深度	通常为256层，支持2^256个叶子
高效更新	支持单个节点的快速更新
存在性证明	可以证明某个键存在或不存在

应用场景#

区块链状态管理: 以太坊2.0信标链、Polkadot平行链
分布式数据库: 状态同步、增量备份
密码学应用: 零知识证明、隐私保护
文件系统: 版本控制、增量同步

复杂度分析#

操作	时间复杂度	空间复杂度
更新	O(log n)	O(1)
证明	O(log n)	O(log n)
验证	O(log n)	O(1)
存储	O(k)	O(k)

注：k为实际存储的键数

🌲 Merkle Patricia 树#

核心设计#

Merkle Patricia树结合了Merkle树和Patricia树，通过路径压缩优化存储：

1
                    Root Hash
2
                   /         \
3
            Extension Node    Branch Node
4
           (path: "abc")     [0,1,2,...,F]
5
                |                |
6
            Branch Node      Leaf Node
7
           [0,1,2,...,F]    (value: "data")
8
                |
9
            Leaf Node
10
        (value: "data1")

JavaScript 实现#

1
import crypto from 'crypto';
2

3
class MerklePatriciaTree {
4
  constructor() {
5
    this.root = null;
6
    this.db = new Map();
7
    this.hashFunction = 'sha256';
8
  }
9

10
  hash(data) {
11
    return crypto.createHash(this.hashFunction).update(data).digest('hex');
12
  }
13

14
  stringToHexPath(str) {
15
    return Buffer.from(str, 'utf8').toString('hex');
16
  }
17

18
  hexPathToString(hex) {
19
    return Buffer.from(hex, 'hex').toString('utf8');
20
  }
21

22
  createLeafNode(path, value) {
23
    return {
24
      type: 'leaf',
25
      path: path,
26
      value: value,
27
      hash: this.hash(JSON.stringify({ type: 'leaf', path, value }))
28
    };
29
  }
30

31
  createExtensionNode(path, childHash) {
32
    return {
33
      type: 'extension',
34
      path: path,
35
      childHash: childHash,
36
      hash: this.hash(JSON.stringify({ type: 'extension', path, childHash }))
37
    };
38
  }
39

40
  createBranchNode(children, value = null) {
41
    const childrenArray = new Array(16).fill(null);
42
    children.forEach((child, index) => {
43
      childrenArray[index] = child;
44
    });
45

46
    return {
47
      type: 'branch',
48
      children: childrenArray,
49
      value: value,
50
      hash: this.hash(JSON.stringify({ type: 'branch', children: childrenArray, value }))
51
    };
52
  }
53

54
  storeNode(node) {
55
    const hash = node.hash;
56
    this.db.set(hash, node);
57
    return hash;
58
  }
59

60
  getNode(hash) {
61
    return this.db.get(hash);
62
  }
63

64
  getCommonPrefix(path1, path2) {
65
    let i = 0;
66
    while (i < path1.length && i < path2.length && path1[i] === path2[i]) {
67
      i++;
68
    }
69
    return path1.substring(0, i);
70
  }
71

72
  put(key, value) {
73
    const path = this.stringToHexPath(key);
74
    this.root = this.insertNode(this.root, path, value);
75
  }
76

77
  insertNode(node, path, value) {
78
    if (!node) {
79
      return this.createLeafNode(path, value);
80
    }
81

82
    if (node.type === 'leaf') {
83
      return this.handleLeafNode(node, path, value);
84
    } else if (node.type === 'extension') {
85
      return this.handleExtensionNode(node, path, value);
86
    } else if (node.type === 'branch') {
87
      return this.handleBranchNode(node, path, value);
88
    }
89

90
    throw new Error('Unknown node type');
91
  }
92

93
  handleLeafNode(leafNode, path, value) {
94
    const commonPrefix = this.getCommonPrefix(leafNode.path, path);
95

96
    if (commonPrefix === leafNode.path) {
97
      return this.createLeafNode(path, value);
98
    } else if (commonPrefix.length > 0) {
99
      const remainingPath = path.substring(commonPrefix.length);
100
      const remainingLeafPath = leafNode.path.substring(commonPrefix.length);
101

102
      if (remainingLeafPath.length === 0) {
103
        const newLeaf = this.createLeafNode(remainingPath, value);
104
        const extension = this.createExtensionNode(commonPrefix, this.storeNode(newLeaf));
105
        return this.storeNode(extension);
106
      } else {
107
        const branch = this.createBranchNode([], null);
108
        const leaf1 = this.createLeafNode(remainingLeafPath, leafNode.value);
109
        const leaf2 = this.createLeafNode(remainingPath, value);
110

111
        const index1 = parseInt(remainingLeafPath[0], 16);
112
        const index2 = parseInt(remainingPath[0], 16);
113

114
        branch.children[index1] = this.storeNode(leaf1);
115
        branch.children[index2] = this.storeNode(leaf2);
116

117
        const extension = this.createExtensionNode(commonPrefix, this.storeNode(branch));
118
        return this.storeNode(extension);
119
      }
120
    } else {
121
      const branch = this.createBranchNode([], null);
122
      const leaf1 = this.createLeafNode(leafNode.path, leafNode.value);
123
      const leaf2 = this.createLeafNode(path, value);
124

125
      const index1 = parseInt(leafNode.path[0], 16);
126
      const index2 = parseInt(path[0], 16);
127

128
      branch.children[index1] = this.storeNode(leaf1);
129
      branch.children[index2] = this.storeNode(leaf2);
130

131
      return this.storeNode(branch);
132
    }
133
  }
134

135
  handleExtensionNode(extensionNode, path, value) {
136
    const commonPrefix = this.getCommonPrefix(extensionNode.path, path);
137

138
    if (commonPrefix === extensionNode.path) {
139
      const remainingPath = path.substring(commonPrefix.length);
140
      const childNode = this.getNode(extensionNode.childHash);
141
      const newChild = this.insertNode(childNode, remainingPath, value);
142

143
      const newExtension = this.createExtensionNode(commonPrefix, this.storeNode(newChild));
144
      return this.storeNode(newExtension);
145
    } else if (commonPrefix.length > 0) {
146
      const remainingPath = path.substring(commonPrefix.length);
147
      const remainingExtensionPath = extensionNode.path.substring(commonPrefix.length);
148

149
      const branch = this.createBranchNode([], null);
150
      const childNode = this.getNode(extensionNode.childHash);
151
      const newLeaf = this.createLeafNode(remainingPath, value);
152

153
      const index1 = parseInt(remainingExtensionPath[0], 16);
154
      const index2 = parseInt(remainingPath[0], 16);
155

156
      if (remainingExtensionPath.length === 1) {
157
        branch.children[index1] = this.storeNode(childNode);
158
      } else {
159
        const newExtension = this.createExtensionNode(remainingExtensionPath.substring(1), this.storeNode(childNode));
160
        branch.children[index1] = this.storeNode(newExtension);
161
      }
162

163
      branch.children[index2] = this.storeNode(newLeaf);
164

165
      const extension = this.createExtensionNode(commonPrefix, this.storeNode(branch));
166
      return this.storeNode(extension);
167
    } else {
168
      const branch = this.createBranchNode([], null);
169
      const childNode = this.getNode(extensionNode.childHash);
170
      const newLeaf = this.createLeafNode(path, value);
171

172
      const index1 = parseInt(extensionNode.path[0], 16);
173
      const index2 = parseInt(path[0], 16);
174

175
      if (extensionNode.path.length === 1) {
176
        branch.children[index1] = this.storeNode(childNode);
177
      } else {
178
        const newExtension = this.createExtensionNode(extensionNode.path.substring(1), this.storeNode(childNode));
179
        branch.children[index1] = this.storeNode(newExtension);
180
      }
181

182
      branch.children[index2] = this.storeNode(newLeaf);
183

184
      return this.storeNode(branch);
185
    }
186
  }
187

188
  handleBranchNode(branchNode, path, value) {
189
    if (path.length === 0) {
190
      return this.createBranchNode(branchNode.children, value);
191
    }
192

193
    const index = parseInt(path[0], 16);
194
    const remainingPath = path.substring(1);
195
    const childNode = branchNode.children[index];
196
    const newChild = this.insertNode(childNode, remainingPath, value);
197

198
    const newChildren = [...branchNode.children];
199
    newChildren[index] = this.storeNode(newChild);
200

201
    return this.createBranchNode(newChildren, branchNode.value);
202
  }
203

204
  get(key) {
205
    const path = this.stringToHexPath(key);
206
    return this.getNodeValue(this.root, path);
207
  }
208

209
  getNodeValue(node, path) {
210
    if (!node) {
211
      return null;
212
    }
213

214
    if (node.type === 'leaf') {
215
      if (node.path === path) {
216
        return node.value;
217
      }
218
      return null;
219
    } else if (node.type === 'extension') {
220
      if (path.startsWith(node.path)) {
221
        const remainingPath = path.substring(node.path.length);
222
        const childNode = this.getNode(node.childHash);
223
        return this.getNodeValue(childNode, remainingPath);
224
      }
225
      return null;
226
    } else if (node.type === 'branch') {
227
      if (path.length === 0) {
228
        return node.value;
229
      }
230

231
      const index = parseInt(path[0], 16);
232
      const childNode = node.children[index];
233
      if (childNode) {
234
        const remainingPath = path.substring(1);
235
        return this.getNodeValue(this.getNode(childNode), remainingPath);
236
      }
237
      return null;
238
    }
239

240
    return null;
241
  }
242

243
  getRootHash() {
244
    return this.root ? this.root.hash : null;
245
  }
246
}
247

248
// 使用示例
249
const mpt = new MerklePatriciaTree();
250
mpt.put('apple', 'red');
251
mpt.put('banana', 'yellow');
252
mpt.put('cherry', 'red');
253

254
console.log('MPT根哈希:', mpt.getRootHash());
255
console.log('查询apple:', mpt.get('apple'));
256
console.log('查询banana:', mpt.get('banana'));

节点类型#

叶子节点: 存储实际的键值对
扩展节点: 压缩公共前缀路径
分支节点: 处理路径分叉，最多16个子节点

技术特点#

特性	描述
路径压缩	通过扩展节点压缩公共前缀
查询效率	基于路径的快速查找
完整性验证	通过根哈希验证整个状态
增量更新	只更新必要的节点

应用场景#

以太坊: 状态树、存储树、交易树
分布式数据库: 状态同步、一致性验证
文件系统: 版本控制、增量同步
分布式系统: 配置管理、服务发现

复杂度分析#

操作	时间复杂度	空间复杂度
插入	O(k)	O(k)
查询	O(k)	O(1)
删除	O(k)	O(k)
更新	O(k)	O(k)

注：k为键的长度

🔄 三种树的对比#

功能对比#

特性	普通Merkle树	稀疏Merkle树	Merkle Patricia树
路径压缩	❌	❌	✅
稀疏存储	❌	✅	❌
固定深度	❌	✅	❌
哈希验证	✅	✅	✅
增量更新	❌	✅	✅
存在性证明	❌	✅	❌

性能对比#

操作	普通Merkle树	稀疏Merkle树	Merkle Patricia树
构建	O(n log n)	O(k log n)	O(k)
查询	O(log n)	O(log n)	O(k)
更新	O(n)	O(log n)	O(k)
存储	O(n)	O(k)	O(k)

应用场景对比#

场景	推荐方案	理由
批量数据验证	普通Merkle树	简单高效，适合一次性验证
稀疏状态管理	稀疏Merkle树	固定深度，支持存在性证明
频繁状态更新	Merkle Patricia树	路径压缩，高效更新
区块链状态	Merkle Patricia树	以太坊等主流方案
零知识证明	稀疏Merkle树	支持隐私保护

🛠️ 实际应用案例#

1. 比特币 - 普通Merkle树#

应用: 交易集合验证实现: 每个区块包含交易Merkle根优势: 快速验证交易完整性

1
// 比特币交易验证示例
2
function verifyTransaction(transaction, merkleProof, merkleRoot) {
3
  let hash = hashTransaction(transaction);
4

5
  for (const proofNode of merkleProof) {
6
    hash = hash(hash + proofNode);
7
  }
8

9
  return hash === merkleRoot;
10
}

2. 以太坊 - Merkle Patricia树#

应用: 状态树管理实现: 账户状态存储和验证优势: 高效的状态查询和更新

1
// 以太坊状态树示例
2
function updateAccountState(stateTree, address, newState) {
3
  const path = addressToPath(address);
4
  return stateTree.update(path, newState);
5
}

3. 以太坊2.0 - 稀疏Merkle树#

应用: 信标链状态管理实现: 验证者状态和余额管理优势: 支持存在性证明和隐私保护

1
// 以太坊2.0状态验证示例
2
function verifyValidatorState(validatorId, state, proof, root) {
3
  return sparseMerkleTree.verify(validatorId, state, proof, root);
4
}

🚀 实现建议#

1. 选择合适的数据结构#

数据密度: 稀疏数据选择SMT，密集数据选择MPT
更新频率: 频繁更新选择MPT或SMT
查询模式: 路径查询选择MPT，存在性查询选择SMT

2. 性能优化策略#

并行计算: 利用多核CPU并行计算哈希
缓存机制: 缓存常用节点和计算结果
存储优化: 使用数据库存储节点，实施压缩

3. 安全考虑#

哈希函数: 使用加密安全的哈希函数
路径安全: 确保路径计算的随机性
状态一致性: 实施事务性更新和锁定机制

📖 学习资源#

开源实现#

比特币 Core: https://github.com/bitcoin/bitcoin
以太坊 Go: https://github.com/ethereum/go-ethereum
以太坊2.0 Prysm: https://github.com/prysmaticlabs/prysm

技术文档#

比特币白皮书: 原始Merkle树应用
以太坊黄皮书: MPT详细规范
以太坊2.0规范: SMT在信标链中的应用

在线工具#

Merkle树可视化: 帮助理解树结构
哈希计算器: 验证哈希计算
性能测试工具: 评估不同实现的性能

🎯 总结#

Merkle树系列是区块链和分布式系统中的核心技术，每种变体都有其独特的优势和应用场景：

普通Merkle树: 适合批量数据验证，简单高效
稀疏Merkle树: 适合稀疏数据管理，支持存在性证明
Merkle Patricia树: 适合频繁状态更新，空间效率高

选择合适的Merkle树变体，结合适当的优化策略，可以构建高效、安全的分布式系统。随着区块链技术的发展，这些数据结构将继续发挥重要作用，为下一代分布式应用提供坚实的基础。

本文涵盖了Merkle树系列的核心概念、技术细节和实际应用，为开发者提供了全面的技术参考。建议结合实际项目深入学习，掌握这些重要的数据结构。

Merkle 树系列：从基础到高级的完整指南

https://website-truelovings-projects.vercel.app/posts/web3/merkle-trees-comprehensive-guide/

作者

欢迎来到StarSky的网站！

发布于

2025-01-27

许可协议

CC BY-NC-SA 4.0

组合总和

前端渐进式渲染