Merkle tree

Merkle Tree概念

定义

默克尔树，是一种哈希树，用来存储Hash值。它的组成成分分为两类，一类是叶子节点，叶子节点是数据块；另一类是非叶子节点，它们是用来验证的hash，如下图：

重点：一个大文件切分成n分，然后并自身生成一个hash，之后才是用hash来进行运算生成hash树。

特点

1. Merkle Tree是树结构，常见是二叉树，但也可以是多叉树，它具有树结构的全部特点。
2. Merkle Tree的基础数据不固定，因为Merkle Tree只需要数据经过运算后的hash值
3. Merkle Tree是从上往下逐层计算的，因此每个中间节点，都是根据相邻两个叶子节点的组合计算出的，而根节点是根据两个中间节点组合计算出的，所以叶子节点是基础。

通常，加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。

Hash List

在P2P网络中，在现在真正数据之前，要先下载一个hash列表。该列表专门存储了文件的hash值，当要验证文件完整性或者下载完整文件时，只需要对该列表进行
校验即可。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后通过校验后的Hash列表校验数据块。

算法实现

Merkle Tree的应用

数字签名

P2P网络

可信计算

IPFS

Bitcoin和Ethereum