第七节 Merkle树

区块链中的每个区块都包含了产生于该区块的所有交易，且以Merkle树表示。

Merkle树是一种哈希二叉树，它是一种用作快速归纳和校验大规模数据完整性的数据结构。这种二叉树包含加密哈希值。术语“树”在计算机学科中常被用来描述一种具有分支的数据结构，但是树常常被倒置显示，“根”在图的上部，同时“叶子”在图的下部，你会在后续内容中看到相应的例子。

在比特币网络中，Merkle树被用来归纳一个区块中的所有交易，同时生成整个交易集合的数字指纹，提供一种校验区块是否存在某交易的高效途径。生成一棵完整的Merkle树需要递归地对哈希节点对进行哈希，并将新生成的哈希节点插入Merkle树中，直到只剩一个哈希节点，该节点就是Merkle树的根。在比特币的Merkle树中两次使用到了SHA256算法，因此其加密哈希算法也被称为double-SHA256。

当n个数据元素经过加密后被插入Merkle树时，你最多计算 次就能检查出某任意数据元素是否在该树中，这使得该数据结构非常高效。

Merkle树是自下向上构建的。在图2.4中，我们从A、B、C、D四个构成Merkle树树叶的交易开始。起始时所有的交易都还未存储在Merkle树中，而是先将数据哈希化，然后将哈希值存储至相应的叶子节点。这些叶子节点分别是HA、HB、HC和HD：

H~A~=SHA256（SHA256（交易A））

通过串联相邻叶子节点的哈希值然后哈希之，这对叶子节点随后被归纳为父节点。例如，为了创建父节点HAB，子节点A和子节点B的两个32字节的哈希值将被串联成64字节的字符串。随后将字符串进行两次哈希来产生父节点的哈希值：

H~AB~=SHA256（SHA256（H~A~+H~B~））

继续类似的操作直到只剩下顶部的一个节点，即Merkle根。产生的32字节哈希值存储在区块头，同时归纳了四个交易的所有数据。如图2.4所示。

图2.4

因为Merkle树是二叉树，所以它需要偶数个叶子节点。如果仅有奇数个交易需要归纳，那最后的交易就会被复制一份以构成偶数个叶子节点，这种偶数个叶子节点的树也被称为平衡树。如图2.5所示，C节点被复制了一份。

图2.5

由四个交易构造Merkle树的方法同样适用于从任意交易数量构造Merkle树。在比特币中，在单个区块中有成百上千的交易是非常普遍的，这些交易都会采用同样的方法归纳起来，产生一个仅仅32字节的数据作为Merkle根。在图2.6中，你会看见一个由16个交易形成的树。需要注意的是，尽管图中的根看起来比所有叶子节点都大，但实际上它们的大小都是32字节。无论区块中只有一个交易或者有10万个交易，Merkle根总会把所有交易都归纳为32字节。

图2.6

为了证明区块中存在某个特定的交易，一个节点只需要计算log₂⁽ᴺ⁾个32字节的哈希值，形成一条从特定交易到树根的认证路径或者Merkle路径即可。随着交易数量的急剧增加，这样的计算量就显得异常重要，因为相对于交易数量的增长，以基底为2的交易数量的对数的增长会缓慢许多。这使得比特币节点能够高效地产生一条10或者12个哈希值（320～384字节）的路径，来证明在一个巨量字节大小的区块中上千笔交易中的某笔交易的存在。

在图2.7中，一个节点能够通过生成一条仅有4个32字节哈希值长度（总128字节）的Merkle路径，来证明区块中存在一笔交易K。该路径有4个哈希值（在图2.7中由深黑色标注）HL、HIJ、HMNOP和HABCDEFGH。由这4个哈希值产生的认证路径，再通过计算另外4对哈希值HKL、HIJKL、HIJKLMNOP和Merkle树根（在图

2.7中由虚线标注），任何节点都能证明HK（在图2.7中由浅黑色标注）包含在Merkle根中。

图2.7

例1中的代码借用libbitcoin库中的一些辅助程序，演示了从叶子节点哈希至根创建整个Merkle树的过程。

例1构造Merkle树。

#include

bc::hash_digest create_merkle（bc::hash_digest_list&merkle）{

//Stop if hash list is empty.

if（merkle.empty（））

return bc::null_hash;

else if（merkle.size（）==1）

return merkle[0];

//While there is more than 1 hash in the list，keep looping…

while（merkle.size（）>1）{

//If number of hashes is odd，duplicate last hash in the list.

if（merkle.size（）%