06.20 区块链中的Merkle Tree

一家运输公司接到一批货物有运输单，货物量很多，由于不能一次运输完，于是运输公司把货物拆分为小量，采用多次运输。每一次运输都会给到对方一个货物清单，等货物全部送到的时候，对方拿着送货清单，清点货物，检查货物是否完成，有没有存在缺漏遗失的现象。

在网络传输中，需要传输大文件的时候，也采用货物运输的方式，把文件拆分很多的数据块各自进行传输。那么传送数据的“送货清单”是什么，这个是哈希值，因为哈希函数可以验证信息的完整性。

我给你传输数据之前，先把数据的哈希结果告诉你，等你收到文件再计算一次哈希然后和收到的哈希比较就知道文件有无损坏。

在传输大数据文件的时候需要一份哈希列表，列表中每一项都对应一个数据块的哈希值，如果只要一部分数据就OK了。可是要去历遍所有数据块的哈希，这个成本比较高。那有没有可能只获取部分数据的哈希，也能验证文件的完整性？

这个当然是有的，它就是Merkle tree。

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树，Merkle树的叶子是数据块的hash值，非叶节点是其对应子节点串联字符串的hash。在区块链中，每一个区块中都有一个Merkle Tree，用来储存交易信息，并对交易信息进行完整性验证。

在点对点网络中作数据传输的时候，会同时从多个机器上下载数据，而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，把分割成2K为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一快数据就行了，不用重新下载整个文件。

怎么确定小的数据块没有损坏呢？

很简单，只需要为每个数据块做Hash。BT下载的时候，在下载到真正数据之前，我们会先下载一个Hash列表。那么问题又来了，怎么确定这个Hash列表本事是正确的哪？答案是把每个小块数据的Hash值拼到一起，然后对这个长字符串在作一次Hash运算，这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后通过校验后的Hash列表校验数据块。

但有了Merkle Tree就好办多了，Merkle Tree可以看做Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree）。在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。

如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，

在p2p网络下载网络之前，先从可信的源获得文件的Merkle Tree树根，一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的Merkle Tree，如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的Merkle Tree。

Merkle Tree和Hash List的主要区别是:可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而Hash list只有下载整个hash list才能验证。

那Merkle Tree如何创建呢？

假设一个区块中，加入最低层有4个数据块，每个交易数据两两配对进行Hash运算，构成Merkle Tree节点，以此推进，进而生成整个Merkle Tree，如下图：

第1步:（红色线）对数据块做Hash运算；

第2步: （黄色线）相邻两个Hash值配对，做Hash运算；

第3步：（蓝色线）重复第2步，生成Merkle Tree Root。

Merkle Tree的应用

1. 数字签名

最初Merkle Tree目的是高效的处理Lamport one-time signatures,每一个Lamport key只能被用来签名一个消息，但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架，即Merkle Signature Scheme。

2. P2P网络

在P2P网络中，Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输，一来可以加快数据下载速度，二来减轻下载服务器的负担。BT即BitTorrent，是一种中心索引式的P2P文件分分析通信协议。

​