1.3.2 Merkle树

传统的数据中心只有一个节点，想提高数据处理能力很简单，增加磁盘阵列就可以了。区块链是“发动群众来记账”的，有了众多矿工的参与，整个系统就有了很多节点，例如，比特币社区就有几十万个节点。如果采用传统的数据模式，用不了多久，矿工们的硬盘就会被撑爆，这个游戏就没法继续了。

2014年4月，比特币网络中的一个节点要想存储所有区块数据，大概需要15GB的空间；2018年，超过了200GB。未来，随着比特币交易量的增加，该空间还将扩大，越来越难以接受。为了解决这个问题，中本聪提出了一个解决方案——简化支付验证（SPV）。

从理论上来说，数字钱包需要遍历所有区块并找到与该交易相关的所有交易，然后逐个验证谁才是可靠的，但有了SPV就不用这么麻烦了，用户只需要保存所有的区块头，区块头仅占用80B，而块身一般要占用400B。

SPV强调的是验证支付，而不是验证交易，因此只需要判断用于支付的那笔交易是否被验证过，以及得到多少次确认。为了实现SPV，需要用一种方法来检查一个区块是否包含了某笔交易，而不用下载整个区块，这就需要用到Merkle树技术。

Merkle树是一种Hash二叉树，是数据结构的一种，主要用于快速归纳和校验大规模数据的完整性。在比特币网络中，Merkle树被用来归纳一个区块中的所有交易，其树根（根节点）是整个交易集合的哈希值，最底层的叶节点是数据块的哈希值，非叶节点是其对应子节点串联字符串的哈希值。

有了Merkle树后，不需要对整个树进行验证，只需要记住根节点哈希值，因为只要树中的任意节点被篡改，根节点哈希值就会不匹配。从而实现了快速校验。

Merkle树是自下而上构建的。例如，同一时间发生A、B、C、D共4笔交易，刚开始所有交易都存储于基础节点，分别进行哈希计算，对于交易A，用Hash函数处理后，得到HA=SHA256（SHA256（交易A）），采用同样的方法可以得到交易B、交易C、交易D的哈希值，分别是HB、HC、HD。

第一层完成后，可以创建第二层节点，得到HAB=SHA256（SHA256（HA+HB）），用同样的方法可以得到HCD。然后创建第三层节点，也就是顶层的唯一节点HABCD，这样就完成了整个Merkle树的构建，包含4笔交易的Merkle树如图1-13所示。

上面的例子是只有4笔交易的3层Merkle树。包含多笔交易的Merkle树如图1-14所示，共有16笔交易，是5层Merkle树。从4笔交易增加到16笔交易，交易数量增加了3倍，但Merkle树的层数只从3层增加到5层，数据存储效率得到极大提高。

在比特币系统中，单个区块中有成百上千个交易是非常普遍的，无论有多少个节点，都可以通过Merkle树归纳为32B的Merkle根。在数据量小的时候，这种方式还看不出价值，随着交易数量的增加，计算量的变化就异常重要了。

Merkle树的效率如表1-1所示。当交易数从16笔增加到65535笔时，增加了400多倍，但是路径字节数只增加了3倍。可以看出，Merkle树在支持大规模交易方面，具有明显优势。有了Merkle树，比特币节点仅保存区块头就可以了，大大减少了对存储空间的需求。