区块链技术| Merkle Tree

简介

默克尔树是一种二叉树（类似于松树的树冠形状）。

merkle模型.png

结构

• D0 ~ D3存储数据的数据块，N0 ~ N3是D0 ~ D3对应的哈希值，统称为叶节点。
• N4、N5称为中间节点。是两个相邻叶节点的HASH值之和再取哈希。N4 = Hash(N0 + N1) , N5 = (Hash(N2 + N3))
• ROOT节点也被称作根节点。

原理

假如D0的值被恶意修改，那么会牵扯到N0、N4、ROOT等节点。

如果叶节点(D0~D3)是单数，不是双数怎么办？

merkle.png

如图所示D0 ~ D4存储数据，H1-0 ～H1-4是D0 ~ D4对应的Hash值。
H2-1 = Hash(H1-0 + H1-1)，H2-2 = Hash(H1-2 + H1-3)。这时我们发现出现了单数的H1-4，遇到这种情况默认会选择进行本身复制（H1-4-1），然后再进行Hash操作，即H2-3 = Hash(H1-4 + H1-4)，上面以此类推，直到产生ROOT节点。

典型应用场景

• 快速比较大量数据：如果两个根节点相同，则表示所有数据都相同。
• 快速定位修改：例如上例中，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。因此，沿着 Root --> N4 --> N1，可以快速定位到发生改变的 D1，不需要将所有数据Hash进行遍历。