理解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];

}