梅克尔树

梅克尔树

梅克尔树

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

进一步的,默克尔树可以推广到多叉树的情形。
默克尔树的特点是,底层数据的任何变动,都会传递到其父亲节点,一直到树根。

默克尔树的典型应用场景包括:

  • 快速比较大量数据:当两个默克尔树根相同时,则意味着所代表的数据必然相同。
  • 快速定位修改:例如上例中,如果 D1 中数据被修改,会影响到 N1,N4 和 Root。因此,沿着 Root --> N4 --> N1,可以快速定位到发生改变的 D1;
  • 零知识证明:例如如何证明某个数据(D0……D3)中包括给定内容 D0,很简单,构造一个默克尔树,公布 N0,N1,N4,Root,D0 拥有者可以很容易检测 D0 存在,但不知道其它内容。

Neo中的梅克尔树

我们看一下Neo的代码,看看如此神奇的的数据结构,到底怎么实现的。
代码在/neo/Cryptography/MerkleTree.cs

构造函数

image.png
  1. 构造函数的参数传入了一个hash数组,这些数组,就是叶子节点。
  2. 调用的build函数,返回root,说明build函数是用来把数组变成一颗树的函数。
  3. for循环计算树的高度。

build树

树的节点

节点
  1. 每个节点都有一个hash值
  2. 有三个指针,父节点指针,左孩子指针,右孩子指针。

建立树的算法

建立树

对于图中的标记,解释一下。

  1. 参数就是叶子节点。
  2. 计算父节点的数目,创建父节点数组,父节点的数目为(leaves.Length + 1) / 2
  3. 通过一个循环,给父节点赋值。
  4. 如果叶子节点是奇数,则最后一个父节点的左右孩子是一样的。
  5. 根据左右孩子的hash值,产生父节点。
  6. 当前生成的parent,又变成leaves,递归调用build方法。

退出的时候,就是leaves.Length == 1的时候,当做root的返回。

Neo如何使用梅克尔树

计算根节点

计算根节点

根节点会被包含在block中,block就是区块链的块,后面看到这块代码再仔细分析。

从树变成数组

从树变成数组

使用的地方

MerkleBlockPayload里面,保存的是这个数组,我想可能是这样可以节省一点空间吧。后面继续研究具体存在这里干嘛。

裁剪树

裁剪树

BitArray和BloomFilter相关,这里就是根据这个array来表示存在的节点,然后把梅克尔树修剪一下,具体什么时候才会用到这个呢,后面跑起来再看看,现在还不知道。

总结

我们看到Neo实现的梅克尔树还是很简练的,而且有一些使用场景,需要进一步研究。

参考文档

merkling-in-ethereum
C#并行编程-PLINQ:声明式数据并行
Merkle 树

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,509评论 1 31
  • 默克尔树(又叫哈希树)是一种二叉树,由一个根节点、一组中间节点和一组叶节点组成。 最下面的叶节点包含存储数据或其哈...
    天狼42阅读 1,951评论 0 0
  • 哈希算法(Hash) 哈希算法也叫散列算法,一般来说满足这样的关系:Func(data)=key,输入任意长度的 ...
    叶开源阅读 1,469评论 0 15
  • 母亲生我的时候是难产。二天三夜的疼痛让母亲眼淌热泪,精疲力尽。父亲坐立不安,双唇不知不觉布满了水泡。他焦灼地守在租...
    诗意的云阅读 589评论 0 3
  • 雪花漫舞落无声,风雪神作美画成。 天冻地寒银素裹,地天一色眼朦胧。 欢心喜悦踏霜雪,胜景无垠释傲情。 无际鹅绒披遍...
    徐一村阅读 208评论 6 9