Merkle 树
#########


默克尔树（又叫哈希树）是一种二叉树，由一个根节点、一组中间节点和一组叶节点组成。最下面的叶节点包含存储数据或其哈希值，每个中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。


Merkle树::

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

.. image:: https://img.zhaoweiguo.com/knowledge/images/theorys/trees/merkle-tree1.png