Merkle 树¶
默克尔树(又叫哈希树)是一种二叉树,由一个根节点、一组中间节点和一组叶节点组成。最下面的叶节点包含存储数据或其哈希值,每个中间节点是它的两个孩子节点内容的哈希值,根节点也是由它的两个子节点内容的哈希值组成。
Merkle树:
基于哈希值的二叉树或多叉树。
「叶子」节点的值是「数据块的哈希值」
「非叶子」节点的值是「此节点下所有叶子节点的组合结果的哈希值」
在计算机领域,Merkle大多用来进行完整性验证处理。
若C、D、E和F存储了一组数据块的哈希值,当把这些数据从Alice传输到Bob后,为验证传输到Bob的数据完整性,只需要验证Alice和Bob上所构造
的Merkle树的根节点值是否一致即可。如果一致,表示数据在传输过程中没有发生改变。假如在传输过程
中,E对应的数据被人篡改,通过Merkle树很容易定位找到(因为此时,根节点、B、E所对应的哈希值
都发生了变化),定位的时间复杂度为O(log(n))。比特币的轻量级节点所采用的SPV验证就是利用Merkle树这一优点。
比特币:简化交易验证
以太坊包含3个Merkle树:交易、收据,状态