理解Merkle-Tree(默克尔树)
默克尔树,也称哈希树。
定义:若一种树,满足每个叶节点等于数据块的哈希值,每个非叶节点都等于其子节点的哈希值。
例如,假设我们要验证以下数据:
1 | Hello, world! |
我们可以将其分成两个小块:
1 | Hello, |
然后计算每个小块的哈希值:
1 | SHA256(Hello, ) = 1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad |
接下来,将这两个哈希值配对并计算它们的哈希值:
1 | SHA256(1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad, 098f6bcd4624e37a20471f1875a427d7d1172a5b28685e5b637d5cc72f707d64) = 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b |
现在只剩下一个哈希值,这就是默克尔树的根哈希值:
1 | 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b |
作用:
默克尔树主要防止传输的数据不被篡改。一个默克尔树,若某个数据块的内容发生修改,则对应的叶节点的哈希值就会改变,根哈希值就也会发生改变。所以,我们要验证数据是否发生篡改,只需要比较哈希值即可。
在区块链中,例如比特币,假如比特币不用默克尔树,那么每个节点都必须保留每笔比特币交易的完整内容,这将是极其庞大的数据。而利用默克尔树,只储存并比较根哈希值。
参考资料:https://www.simplilearn.com/tutorials/blockchain-tutorial/merkle-tree-in-blockchain
附比特币计算默克尔树-根哈希值的源码:
1 | uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) { |