Merkle树

Merkle哈希数是一类基于哈希值的二叉树或多叉树,其叶子节点上的值通常为交易数据块的哈希值,而非叶子节点上的值,则是将该节点的所有子节点的进行HASH后的结果

如果要判断一笔交易是否存在于一个区块中,则需要这笔交易的父HASH,及与它的父HASH平级的所有HASH进行构造Merkle树，这样构造出的MerkleRoot与区块头的MerkleRoot相同，则可确认该交易位于此区块，只需要较小的节点数而不用去析整个区块

1.Merkle Tree
1.1 区块结构中包含两个默克树根,一个是事务transactions的默克尔树根;另一个是操作action的默克树根.

1.2 默克尔树的演化路线是 Hash->Hash Tree->Merkle Tree,它们都是为解决数据一致性而存在的

Hash下载
1 下载一个文件,通常会在下载页面看到这个文件的Hash值及Hash算法.下载完毕之后,用户可在本地对整个文件使用同样的Hash算法计算得到Hash值,然后与下载页面的文件Hash值进行对比.

2 服务端
a.将大文件数据侵害为很多小块文件,Hash每一个小块文件得到对应的Hash值
b.拼接所有的小块Hash值作为源文件,Hash该源文件得到Root Hash
c.Root Hash与所有的小块Hash值组成Hash List,放置在下载网页上

3 客户端
a.先下载Hash List,打开得到源Root Hash,以及所有的小块Hash值
b.本地Hash所有的小块Hash值得到本地Root Hash,与源Root Hash对比.
c.Root Hash对比结果相关,Hash List验证通过
d.逐一下载小块文件,每次下载成功,立即本地验证小块的Hash值是否匹配
e.若不匹配,则重新下载当前小块文件,不必清空全部,重新下载整个大文件
f.重复以上两步,直到所有小块文件下载并验证完毕,本地会自动组成源大文件

Merkle Tree下载
1.Merkle Tree是Hash List的优化,它极大地提高了性能.树高为2的Hash List只有一个Root Hash,下载Hash List需要一次性验证所有小块Hash,当小块Hash数量很多时,计算量是提高性能的瓶颈

2.Merkle Tree提高性能的关键是其树高大于或等于2,树高越高,性能提高程度越大.Merkle Tree的每个节点最多只有两个子节点,只有叶节点是小块文件的Hash,Hash每两个相邻子节点的值得到父节点的值.如果叶节点的总数是单数,则会剩余一个,逐级往上,最终生成一个根节点,这个根节点就是Merkle Root.
a.下载Merkle Tree,得到Merkle Root,各级父节点Root及叶节点的小块Hash
b.从最左下叶节点和其相邻叶节点开始,逐级往上直到Merkle Root,校验完成.
c.校验过程中,如果最左下相邻的两个叶节点的Hash值与它们父节点的Hash值一致,则立即开始下载这两个叶节点对应的小文件块
d.并行地重复上一步,再校验其他叶节点,下载其他小文件块,直到全部下载

3.Merkle Tree的算法实现了不必校验通过完整的Merkle Tree之后再下载文件,而是分部分的,并行的,边校验边下载的方式,对比Hash List,大大提高了处理性能