3.5 默克尔树

默克尔树（Merkle Tree）是比特币和大多数主流区块链系统的数据组织方式，是由拉尔夫·默克尔提出并以其名字命名的。1979年，拉尔夫·默克尔获得了默克尔树的专利权（于2002年过期），“该发明包含了一种提供信息验证的数字签名的方法，该方法利用单向的认证树对密码数字进行校验”。维基百科对默克尔树的定义为：在密码学和计算机科学中，默克尔树是一种树型数据结构，其中每个叶子节点用数据块的哈希值标记，并且每个非叶子节点用其子节点的标签的加密哈希值标记。默克尔树能快速和安全地验证大型数据结构的内容。默克尔树被递归地定义为哈希值列表的二叉树，其中父节点是其子节点的哈希值，并且叶子节点是原始数据块的哈希值。

3.5.1 原理与实现

默克尔树是哈希树的一个子类—哈希二叉树，其特点是可以针对大量的数据生成较小的校验数据，可以利用校验数据快速地从大量数据中校验单个数据存在与否。在区块链上，默克尔树典型的使用场景就是对区块交易的处理。

默克尔树的生成过程是从叶子节点开始的，两两哈希运算生成上一层节点，每一层的节点也都按照同样的方式两两哈希运算继续生成上一层节点，直到计算至一个根节点。

图3-3为默克尔树的生成示意图。首先对Tx₁、Tx₂、Tx₃、Tx₄排序，假定索引分别为0、1、2、3，转换成二进制数分别为00、01、10、11。定义哈希二叉树的左分支的值为0，右分支的值为1，按照二进制的0和1构造默克尔树，在第一层深度下，H₅左分支的值为0，H₅右分支的值为1；H₆左分支的值为0，H₆右分支的值为1。在第二层深度下，H₁路径为00（Tx₁），H₂路径为01（Tx₂），H₃路径为10（Tx₃），H₄路径为11（Tx₄）。然后，需要对这个默克尔树进行哈希运算，首先对4笔交易Tx₁、Tx₂、Tx₃、Tx₄分别进行哈希运算（具体的哈希算法可以根据具体的应用场景来设计），生成叶子节点H₁、H₂、H₃、H₄，然后对叶子节点（H₁、H₂）、（H₃、H₄）分别进行哈希运算，生成节点H₅、H₆，对（H₅、H₆）继续进行哈希运算，得到默克尔树的根哈希值，即H₇。

图3-3

接下来，介绍默克尔树的验证过程。如图3-4所示，以一棵高度为4的默克尔树来介绍验证过程，这棵树是16笔交易生成的默克尔树。例如，要证明第6笔交易存在，就需要提供一个默克尔路径，即4个节点的哈希值，如图3-5所示。

图3-4

第6笔交易的哈希值标记为灰色块。由于H₅、H₆可以计算得到H₁₉，H₁₉与H₂₀可以计算得到H₂₆，H₂₆与H₂₅可以计算得到H₂₉，H₂₉与H₃₀可以计算得到最终的默克尔根，所以第6笔交易的默克尔路径为（H₅、H₂₀、H₂₅、H₃₀），在图3-5中标记为阴影块。

图3-5

在了解了默克尔树的结构和算法特点后，我们可以知道默克尔树的算法优势很明显。只需要很短的默克尔路径，就可以从成千上万条记录中，快速地验证记录是否存在。当有N条记录的时候，默克尔路径的长度是log₂N个哈希值的大小，验证过程中需要计算log₂N次哈希值，也就是说，记录数每增加一倍，默克尔路径只增加一个哈希值的大小，验证过程也就只增加一次哈希运算，这在处理区块链上大量交易的过程中，提供了强有力的算法支持。

3.5.2 简单支付证明

现在区块链的终端设备类型非常多，这给区块链系统带来了新的挑战。通常来说，区块链系统中的每个节点都保存了整条区块链的所有区块数据，也就是所有交易记录。随着区块链系统运行，这些区块数据在不断快速增加，节点对设备存储空间的需求越来越大。为了降低对设备的存储要求，结合默克尔树算法的优势，只需要同步区块头和简单支付证明（Simplified Payment Verification，SPV）的节点就应运而生了。

区块链系统的区块头信息，包含了区块交易的默克尔根，所以，在同步了所有区块头信息之后，只需要提供默克尔路径就可以证明一笔交易是否存在。SPV节点向完整的区块链节点获取关注账户地址的相关交易，就可以证明并处理这些交易的数据。但是，由于SPV节点只能证明收到的交易是否有效，并不能保证完整地获取到关注账户地址的所有交易。所以，节点间的网络问题，或者完整节点的恶意行为，都可能导致SPV节点接收到的相关交易不完整。如果区块链是基于UTXO的账户模型的，那么在这种情况下通过SPV节点发送交易，就可能会因为“双花”（双重花费）问题而导致交易失败。

轻量级的SPV节点目前只能靠连接多个完整节点来避免相关交易被漏掉的问题，在运行的区块链系统上，这种情况不太容易遇到。要彻底解决这个问题，就只能运行完整的区块链节点，这就是给区块链节点“瘦身”的弊端。