2.1. 默克尔树¶
2.1.1. 默克尔树要解决的问题¶
许多区块链应用需要存储双方之间某种形式的交易。 例如，像比特币这样的加密货币使用区块链来存储涉及一方将比特币发送给另一方的所有交易的记录。 随着时间的推移，区块链将包含大量的交易。 通常，区块链应用不会想要每个区块存储一笔交易，而是可能存储许多交易。 例如，截至 2021 年 9 月，比特币区块链上一个区块大约有 1500 到 2500 笔交易。 在 2021 年 6 月，整个区块链存储了数百万笔交易，总共 350 GB 数据。
典型区块链应用的一个基本操作是验证特定交易确实存储在区块链的某个位置。 考虑到可能涉及的大量交易，线性搜索链中每一笔交易是不切实际的。 我们需要一种更快的方式来搜索给定的交易。
2.1.2. 默克尔树¶
默克尔树（或哈希树）是一种树结构，其中叶节点包含单个交易的密码学哈希。 所有内部节点存储其左右子节点的哈希值，以及这两个值的哈希。 这意味着树的根节点包含一个哈希，该哈希受所有被连续配对并哈希化的叶节点影响。
2.1.3. 为什么有用？¶
回忆一下（参见 区块与节点），区块链生态系统中的许多参与者是"薄节点"。 这意味着它们只保留少量关于区块链的信息： 即每个区块的哈希值和少量元数据。 当薄节点想要确认某笔特定交易确实在区块链上时，它首先会从维护更多信息的实体获取必要信息。 这可能是一个存储完整区块链的节点，也可能是对区块链交易数据库建立索引的"区块浏览器"。 返回的信息通常类似于区块号和区块内的交易索引，以及包含该交易的区块的完整内容。
然而，由于任何人都可以参与分布式账本区块链系统，给定的薄节点可能不信任提供此交易信息的实体。 薄节点希望有一种方法来验证刚刚提供给它的信息确实来自区块链。 由于区块很大，遍历整个区块内容来验证一切都与薄节点存储的区块哈希一致将是耗时的。
2.1.4. 简化支付验证¶
现在我们了解了什么是默克尔树，让我们看看它如何帮助验证第三方信息提供者声称的交易确实在区块链上。 默克尔树在常见公共区块链中的主要用例（包括比特币）是作为向客户提供 简化支付验证 （SPV）的有效手段。 SPV 是网络上的节点可以轻松验证交易发生的流程。
一个 默克尔证明 是证明交易合法性的有效手段。 如 1.3 中的图所示，交易 2 仅使用 3 个不同的值进行了验证。 此默克尔证明由 O(log(n)) 个哈希加上最终的根哈希组成。 薄节点可以使用提供的 O(log(n)) 个哈希自行计算根节点，并将其计算出的根节点与存储在区块头中的根节点进行比较。 如果计算出的根节点与实际根节点匹配，则交易得到验证。 这比要求任何薄节点存储一个或多个区块的完整交易历史要高效得多。
