深入理解比特币系列(18): Merkle树

Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构。在比特币网络中,Merkle树被用来归纳一个区块中的所有交易,同时生成整个交易集合的数字指纹,且提供了一种校验区块是否存在某交易的高效途径。生成一棵完整的Merkle树需要递归地对哈希节点对进行哈希,并将新生成的哈希节点插入到Merkle树中,直到只剩一个哈希节点,该节点就是Merkle树的根。

比特币的Merkle树使用两次SHA256算法,因此其加密哈希算法也被称为double-SHA256。

Merkle树的生成

Merkle树是自底向上构建的。所有的叶子节点都是单个交易哈希。如叶子A节点的交易哈希计算方法如下,返回的A节点哈希是一个32字节串。

HA = SHA256(SHA256(Transaction A))

接着,相邻节点计算拼接后(64字节)的哈希:

HAB = SHA256(SHA256(HA + HB))

以此类推,直到最后只有一个节点为止,此节点即是Merkle树根节点,其包含了所有的交易信息。以4个交易节点计算的Merkle树如下图所示:

merkle_tree

由于Merkle树是二叉树,当遇到奇数个节点时,可以采用复制节点来解决,如3个节点的情况,可以采用复制C节点的方式:

merkle_tree_odd

利用Merkle树验证区块中存在某笔特定交易

为了证明区块中存在某个特定的交易,一个节点只需要计算log2(N)个32字节的哈希,形成一条从特定交易到Merkle树根的认证路径或者Merkle路径即可。随着交易数量的急剧增加,这样的计算量就显得异常重要,因为相对于交易数量的增长,对数的增长会缓慢许多。这使得比特币节点能够高效地产生一条10或者12个哈希值(320-384字节)的路径,来证明在一个巨量字节大小的区块中上千交易中的某笔交易的存在。以下图为例,一个Merkle路径只需提供HL, HIJ, HMNOP, and HABCDEFGH.即可证明交易K是否存在与该区块中:

merkle_tree_path

Merkle树与简单支付验证(SPV)

Merkle树被SPV节点广泛使用。SPV节点不保存所有交易也不会下载整个区块,仅仅保存区块头。它们使用认证路径或者Merkle路径来验证交易存在于区块中,而不必下载区块中所有交易。

例如,一个SPV节点只关心支付到其钱包中某个比特币地址的交易,该节点可以通过建立过滤器限制只接受含有目标比特币地址的交易。当节点探测到某交易符合过滤器的设定时,它将以Merkleblock消息的形式发送该区块。Merkleblock消息包含区块头和一条连接目标交易与Merkle根的Merkle路径。SPV节点能够使用该路径找到与该交易相关的区块,进而验证对应区块中该交易的有无。SPV节点所收到的Merkleblock数据量通常少于1KB,只有接收一个完整的区块(目前大约有1MB)的千分之一不到。