介绍
Merkle 树是区块链技术的基本组成部分。它是一种数学数据结构，由不同数据块的哈希值组成，作为区块中所有交易的汇总。它还可以对大量数据的内容进行有效和安全的验证。比特币和以太坊都使用默克尔树结构。默克尔树也被描述为哈希树。
Merkle Tree 概念以 Ralph Merkle 的名字命名，他在 1979 年为这一想法申请了专利。它是一种树形数据结构，其中每个叶节点都用数据块哈希标记，非叶节点用密码哈希标记标记它的子节点。叶节点是树中的最后一个结束节点。
来源：dev.to/
默克尔树的工作
Merkle 树通过创建整个交易集的数字指纹将所有交易存储在一个块中。它允许用户确认交易是否可以包含在一个块中。
计算节点的哈希对会产生 Merkle 树，直到只剩下一个哈希。这个散列被描述为 Root Hash 或 Merkle Root。Merkle 树是使用自下而上的方法构建的。
资料来源：researchgate.net
每个叶子节点是交易数据的哈希，非叶子节点是其先前哈希的哈希。Merkle 树是二叉树的一部分；因此，它需要偶数个叶节点。如果 Transactions 为奇数，则最后一个 hash 将重复一次以生成偶数个叶子节点。
资料来源：developer.bitcoin.org
上面的例子是最常见和最简单的 Merkle 树形式，即二叉 Merkle 树。区块中的交易数量分别为 TX1、TX2、TX3 和 TX4。这里可以看到有一个top hash，就是整棵树的hash，称为Root Hash或者Merkle Root。这些中的每一个被重复哈希并存储在每个叶子节点中，产生哈希 0、1、2 和 3。然后通过哈希 Hash0 和 Hash1 在父节点中汇总连续的叶子节点对，产生 Hash01，并分别哈希哈希2和哈希3；结果是 Hash23。然后再次对两个散列（Hash01 和 Hash23）进行散列以创建 Root Hash 或 Merkle Root。
Merkle Root 存放在区块头中。区块头是比特币区块的一部分，在挖掘过程中被散列。它包含最后一个区块的哈希值、Nonce 和 Merkle 树中当前区块中所有交易的根哈希值。区块头中的 Merkle 根目录使交易防篡改。因为这个根哈希包含了区块内所有交易的哈希，这些交易可以节省磁盘空间。
资料来源：selfkey.org
Merkle Tree 维护数据完整性。如果交易的任何个别细节或交易顺序发生变化，这些变化将反映在该交易的哈希中。这种变化会将 Merkle 树级联到 Merkle 根，改变 Merkle 根的值，从而使区块无效。因此，每个人都可以看到 Merkle 树允许快速轻松地测试特定交易是否包含在集合中。
为什么区块链需要 Merkle 树？
要了解 Merkle 树对区块链技术的重要性，想象一下没有它们的区块链。我们将主要介绍比特币，因为使用默克尔树是加密货币的基础并且易于理解。例如，如果比特币没有默克尔树，网络中的每个节点都必须维护比特币上发生的每笔交易的完整副本。任何关于比特币的身份验证请求都需要大量 数据包通过网络发送，因此您必须自己拥有它来验证数据。用于验证的计算机必须使用大量处理能力来比较分类账，以确保没有进行任何更改。Merkle Trees 可以有效地解决这个问题。它们在分类账中对记录进行哈希处理，从而有效地将数据证据与数据本身分开。证明交易的有效性只涉及向网络提供少量信息。此外，它还允许您证明账本的两种变体在名义上的计算能力和网络带宽方面是相同的。
重要性
Merkle Trees 至关重要，因为它们允许 Merkle 证明。这些使我们能够快速验证输入是否包含在特定数据集中以及以什么顺序包含。Merkle 树也很有效，因为它们允许我们通过删除所有不必要的分支来压缩大型数据集，同时保留我们需要证明的唯一分支。在区块链世界中，这意味着默克尔树提供以下关键特性：
- 验证交易是否包含在区块中的能力
- 明亮的客户
- 完全的效率和可扩展性
- 简化付款验证
默克尔树的优点
- 高效验证：Merkle 树提供高效的数据完整性和有效性验证，并显着减少验证所需的内存量。验证证明不需要通过区块链网络传输大量数据。通过快速验证交易，在点对点分布式系统中启用受信任的加密货币传输。
- 无延迟：通过网络传输数据时没有延迟。Merkle 树广泛用于保持加密货币工作的计算。
- 更少的磁盘空间：与其他数据结构相比，Merkle 树占用的磁盘空间更少。
- 不变的数据传输：默克尔根有助于确保通过网络发送的块是完整的和不变的。
- 篡改检测： Merkle 树为矿工检查是否有任何交易被篡改提供了惊人的优势。
- 由于交易存储在 Merkle 树中，该树将每个节点的哈希存储在顶级父节点中，因此对交易细节的任何更改，例如要借记的金额或必须进行付款的地址，都将传播到在上层散列，最后到 Merkle 根。
- 矿工可以将标头中的 Merkle 根与存储在块的数据部分中的 Merkle 根进行比较，并轻松检测到这种操作。
- 时间复杂度：如果比较在像 Merkle 树这样的块中搜索交易的时间复杂度和在链表中分类交易的另一个块的时间复杂度，则 Merkle 树是最佳解决方案，然后 -
- Merkle-Tree 搜索： O(logn)，其中 n = 块中的事务数。
- 链表搜索： O(n)，其中 n = 块中的事务数。
结论
一旦你了解了默克尔树的基础知识，你就可以开始欣赏区块链数据结构的保护和效率。如果默克尔树从未被发现，加密货币和区块链技术就不会存在。如果没有合适的替代方案，计算能力和存储量将过于昂贵而无法运行。默克尔树对区块链至关重要，并允许它们在保持交易完整性的同时发挥作用。
关键要点：
- Merkle Tree 提供了一种维护数据完整性和有效性的方法。
- Merkle 树有助于节省内存或磁盘空间作为证明，计算简单且快速。
- Merkle Tree 证据和管理需要通过网络传输的少量信息。
Merkle 根是一种简单的数学方法来验证 Merkle 树上的数据。
- Merkle 根用于加密货币，以确保在点对点网络之间传递的数据块是完整的、未损坏的和未更改的。
- 默克尔根对于维持比特币和以太币等加密货币所需的计算至关重要。
原文标题：A Quick Guide to Blockchain: Merkle Tree
原文作者：ANURAG SINGH CHOUDHARY
原文链接：https://www.analyticsvidhya.com/blog/2022/10/a-quick-guide-to-blockchain-merkle-tree/
