梅克尔树
梅克尔树
默克尔树（又叫哈希树）是一种二叉树，由一个根节点、一组中间节点和一组叶节点组成。最下面的叶节点包含存储数据或其哈希值，每个中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。
进一步的，默克尔树可以推广到多叉树的情形。
默克尔树的特点是，底层数据的任何变动，都会传递到其父亲节点，一直到树根。
默克尔树的典型应用场景包括：
- 快速比较大量数据：当两个默克尔树根相同时，则意味着所代表的数据必然相同。
- 快速定位修改：例如上例中，如果 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
- 构造函数的参数传入了一个hash数组，这些数组，就是叶子节点。
- 调用的build函数，返回root，说明build函数是用来把数组变成一颗树的函数。
- for循环计算树的高度。
build树
树的节点
节点
- 每个节点都有一个hash值
- 有三个指针，父节点指针，左孩子指针，右孩子指针。
建立树的算法
建立树
对于图中的标记，解释一下。
- 参数就是叶子节点。
- 计算父节点的数目，创建父节点数组，父节点的数目为
(leaves.Length + 1) / 2 - 通过一个循环，给父节点赋值。
- 如果叶子节点是奇数，则最后一个父节点的左右孩子是一样的。
- 根据左右孩子的hash值，产生父节点。
- 当前生成的parent，又变成leaves，递归调用build方法。
退出的时候，就是
leaves.Length == 1的时候，当做root的返回。
Neo如何使用梅克尔树
计算根节点
计算根节点
根节点会被包含在block中，block就是区块链的块，后面看到这块代码再仔细分析。
从树变成数组
从树变成数组
使用的地方
在
MerkleBlockPayload里面，保存的是这个数组，我想可能是这样可以节省一点空间吧。后面继续研究具体存在这里干嘛。
裁剪树
裁剪树
BitArray和BloomFilter相关，这里就是根据这个array来表示存在的节点，然后把梅克尔树修剪一下，具体什么时候才会用到这个呢，后面跑起来再看看，现在还不知道。
总结
我们看到Neo实现的梅克尔树还是很简练的，而且有一些使用场景，需要进一步研究。
