梅克尔树

梅克尔树

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

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

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

• 快速比较大量数据：当两个默克尔树根相同时，则意味着所代表的数据必然相同。
• 快速定位修改：例如上例中，如果 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 树