2.2 默克尔树

默克尔树是由Ralph Merkle于1979年提出的，它有如下两个特征。

（1）默克尔树的叶子节点值是数据的哈希值，比特币使用了SHA-256。

（2）非叶子节点的值是对所有叶子节点进行加密哈希运算得出的。

默克尔树可以是多叉树也可以是二叉树，如图2.1所示。

创建默克尔树的流程如下。

（1）根据d₁～d₄生成第一级叶子节点V₁～V₄。

（2）根据V₁和V₂生成节点V₅，根据V₃和V₄生成节点V₆。

（3）最后根据V₅和V₆生成根节点V₇。

从创建流程可以看出，默克尔树的树高度是log ₂n+1，其中 n 是数据数量。图2.1所示的默克尔树层数是log₂ 4+1=3。

使用默克尔树的好处是什么呢？

首先，验证简单。如果我们需要验证d₂，那么我们需要用到V₁和V₆，即通过d₂运算出叶子节点V₂，用V₁和V₂运算出节点V₅，再用节点V₅和V₆运算出根节点V₇，如图2.2所示。这样不需要传输所有的数据就可以完成验证，大大减少了验证的时间并简化了数据传输流程，特别是对于区块链数据集而言，数据集越大，使用默克尔树带来的验证效率的提升越明显。

其次，默克尔树还有一个重要特性，就是能够快速定位到差异数据节点。举个例子，给定默克尔树另外一个值V₈，如果V₈和V₇的两棵树因d₃的不同而产生了差异，那么默克尔树如何通过对比两棵树来找到不一样的数据d₃呢？默克尔树查找差异节点的过程如图2.3所示。

（1）根据V₇，比较节点V₅和V₆，发现V₅相同，V₆不同。

（2）根据V₆，比较叶子节点V₃和V₄，发现V₄相同，V₃不同，因此判断d₃异常。

默克尔树通过比较查询得到的最差时间复杂度是O（log₂n），即树高度减1。我们知道时间复杂度有O（1）＜O（log₂n）＜O（n）＜O（n² ），对数时间复杂度O（log₂n）比线性的O（n）更优，特别是在数据规模较大的时候。我们以比特币为例进行说明：如果每个交易为300Byte，使用的算法是SHA-256，哈希值为32Byte，那么随着区块链交易的增多，区块大小为线性增长，但是哈希比较次数和默克尔树路径占用的存储空间都增长得非常缓慢，如表2.1所示。

拥有这些特性的默克尔树还可以应用于大数据的快速比对，无论数据量多大，我们可以通过对比默克尔树的根哈希值来快速判断数据是否一致。例如，在下载电影种子哈希比对场景中，一般我们先下载后缀为.torrent 的电影种子，再通过各种下载工具进行下载。.torrent文件是BitTorrent常见的后缀文件，BitTorrent是点对点文件传输协议（Peer to Peer File Sharing，P2P），作用于互联网的文件传输和数据分发。BitTorrent中的节点会将文件划分为多个数据块，每个数据块的大小一般是2的幂，数据大小范围是32KB～16MB，目前我们使用SHA-1（未来迁移到SHA-256）来为每个数据块生成哈希值，然后记录到.torrent文件中的info数据结构的pieces字段中，一般格式如下所示：

普通的.torrent文件通过使用哈希列表（Hash List）来存储pieces，但是在大文件中 SHA-1 的大小是160bit，即1个哈希值占用20Byte 的存储空间，当数据块过大时，哈希列表虽然小，却会影响P2P的数据交换效率。反之，若数据块过小，则哈希列表会过大，这会导致.torrent 种子的体积过大。为了平衡数据块的体积问题，人们引入了新的默克尔树可选扩展字段，在原格式的基础上增加了root hash字段，该字段存储的是默克尔树的根哈希值，而不是完整的默克尔树。

当发起网络下载的时候，我们可从网络上下载默克尔树，并与root hash进行比较，以确保下载的正确性。同时，因为默克尔树只需要下载分支就可以校验数据，所以不需要完整地下载默克尔树，只需要下载一部分就可以校验数据的正确性。与哈希列表相比，这种方法的优势还是很明显的。