理解Merkle-Tree（默克尔树）

默克尔树，也称哈希树。

定义：若一种树，满足每个叶节点等于数据块的哈希值，每个非叶节点都等于其子节点的哈希值。

Merkle tree - Wikipedia

例如，假设我们要验证以下数据：

1
Hello, world!

我们可以将其分成两个小块：

1
2
Hello, 
world!

然后计算每个小块的哈希值：

1
2
SHA256(Hello, ) = 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad
SHA256(world!) = 098f6bcd4624e37a20471f1875a427d7d1172a5b28685e5b637d5cc72f707d64

接下来，将这两个哈希值配对并计算它们的哈希值：

1
SHA256(1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad, 098f6bcd4624e37a20471f1875a427d7d1172a5b28685e5b637d5cc72f707d64) = 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b

现在只剩下一个哈希值，这就是默克尔树的根哈希值：

1
3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b

作用：

默克尔树主要防止传输的数据不被篡改。一个默克尔树，若某个数据块的内容发生修改，则对应的叶节点的哈希值就会改变，根哈希值就也会发生改变。所以，我们要验证数据是否发生篡改，只需要比较哈希值即可。

在区块链中，例如比特币，假如比特币不用默克尔树，那么每个节点都必须保留每笔比特币交易的完整内容，这将是极其庞大的数据。而利用默克尔树，只储存并比较根哈希值。

参考资料：https://www.simplilearn.com/tutorials/blockchain-tutorial/merkle-tree-in-blockchain

附比特币计算默克尔树-根哈希值的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {

  bool mutation = false;

  while (hashes.size() > 1) {

​    if (mutated) {

​      for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {

​        if (hashes[pos] == hashes[pos + 1]) mutation = true;

​      }

​    }

​    if (hashes.size() & 1) {

​      hashes.push_back(hashes.back());

​    }

​    SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);

​    hashes.resize(hashes.size() / 2);

  }

  if (mutated) *mutated = mutation;

  if (hashes.size() == 0) return uint256();

  return hashes[0];

}