什么是数据结构里的 Merkle 树

Merkle 树，也被称为 "hash tree"，是一种二叉树的数据结构。这种树的每个节点都是基于其子节点的一种特殊形式的 hash。具体来说，叶节点的 hash 是由存储在那里的数据块（例如文件或文件的部分）生成的，而非叶节点的 hash 是由其子节点的 hash 生成的。如果 Merkle 树只有一个节点（也就是根节点），那么该节点的 hash 就是所有数据的 hash。

Merkle 树的主要优点是它可以用来有效地和安全地验证大型数据结构的内容。因为每个节点的 hash 都依赖于其子节点，所以如果数据的任何部分发生更改，这将导致 hash 的变化，从而可以轻松地在树中的高层级检测到。这使得 Merkle 树在分布式系统和区块链技术中特别有用，因为它们需要在无法信任所有参与者的情况下验证数据的一致性。

让我们通过一个例子来详细说明这个过程。假设我们有四个数据块，我们将它们称为 D1、D2、D3 和 D4。首先，我们为每个数据块创建一个叶节点，并计算每个数据块的 hash，我们将这些 hash 命名为 H1、H2、H3 和 H4。然后，我们为这些叶节点创建父节点。每个父节点的 hash 是其子节点 hash 的 hash。例如，左边的父节点的 hash（我们将其称为 H12）是 H1 和 H2 的连接的 hash。同样，右边的父节点的 hash（我们将其称为 H34）是 H3 和 H4 的连接的 hash。

在这个例子中，我们的 Merkle 树看起来像这样：

         H12-34
         /    \
     H12      H34
    /  \      /  \
  H1   H2   H3   H4
 /     /     /    \
D1   D2   D3   D4

H12-34 是根节点，它是整个数据结构的 hash。如果任何 Dx 发生更改，那么相应的 Hx 也会更改，这将导致父节点和根节点的 hash 更改。

现在，假设我们想要验证 D4 的完整性，但我们没有整个 Merkle 树，只有 H12-34。在这种情况下，我们需要 D4、H3、和 H12。我们可以用 D4 计算 H4，然后用 H3 和 H4 计算 H34，最后用 H12 和 H34 计算 H12-34。