默克尔树是一种二叉树,由一组叶节点、一组中间节点和一个根节点构成,看下图:
consensus-png
来简单讲一下这幅图,我们从最底部开始看,D0、D1、D2和D3是叶子节点包含的数据,也就是叶子节点的value,继续往上看,N0、N1、N2和N3是就是叶子节点,它是将数据(也就是D0、D1、D2和D3)进行hash运算后得到的hash值;继续往上看,N4和N5是中间节点,它们各是N0和N1经过hash运算得到的哈希值以及N2和N3经过hash运算得到的哈希值,注意,它们是把相邻的两个叶子结点合并成一个字符串,然后运算这个字符串的哈希;接着往上,Root节点是N4和N5经过hash运算后得到的哈希值,这就是这颗默克尔树的根哈希。
在默克尔树中最下面的大量的叶节点包含基础数据;每个中间节点是它的两个叶子节点的哈希,根节点也是由它的两个子节点的哈希,代表了默克尔树的顶部。
还有从默克尔树的结构可以看出,任意一个叶子节点的交易被修改,叶子节点hash值就会变更,最终根节点的hash值就会改变。所以确定的根节点的hash值可以准确的作为一组交易的唯一摘要。
可以总结出默克尔树的特点:
1.首先是它的树的结构,默克尔树常见的结构是二叉树,但它也可以是多叉树,它具有树结构的全部特点。
2.默克尔树的基础数据不是固定的,想存什么数据由你说了算,因为它只要数据经过哈希运算得到的hash值。
3.默克尔树是从下往上逐层计算的,就是说每个中间节点是根据相邻的两个叶子节点组合计算得出的,而根节点是根据两个中间节点组合计算得出的,所以叶子节点是基础。
实际上是一种数据结构。这种树状数据结构在快速归纳和检验大规模数据完整性方面效率很高。在比特币网络中,默克尔树被用来归纳一个区块中的所有交易,其树根就是整个交易集合的哈希值,最底层的叶子节点是数据块的哈希值,非叶节点是其对应子节点串联字符串的哈希。我们只需要记住根节点哈希,只要树中的任何一个节点被篡改,根节点哈希就不会匹配,从而可以达到校验目的。
(以上内容摘自公众号及相关网络文章)