默克尔树

默克尔树是一个使用哈希指针的二叉树。默克尔树是一种将大量数据通过哈希方式构建的方式，并且可以将这些数据表示为一个单一的哈希值。

默克尔树根的哈希值是整个区块中所有交易的哈希。如果任何交易被改变、移除或者改变顺序，都会改变默克尔树根的哈希值。这样可以唯一固定整个区块中的所有交易。

验证交易存在（Merkel Proof）

全节点和轻节点

• 全节点：一直在线，在本地硬盘上维护完整的区块链信息。在内存里维护UTXO集合，以便快速检验交易的合法性。监听比特币网络上的交易信息，验证每个交易的合法性。决定哪些交易会被打包到区块里，监听别的矿工挖出来的区块，验证其合法性。

  如果用于挖矿，会决定沿着哪条链挖下去，当出现等长的分叉的时候，选择哪一个分叉。

• 轻节点：不是一直在线，不用保存整个区块链，只要保存每个区块的块头；不用保存全部交易，只保存与自己有关的交易。无法检验大多数交易的合法性，只能检验与自己有关的那些交易的合法性。无法检测网上发布的区块的准确性，可以验证挖矿的难度。只能检测哪个是最长链，不知道哪个是合法最长链。

汇款人A要向收款人B证明提供Merkel Proof，证明A->B这个交易存在某个区块n中。（使用轻节点，比对区块头中Merkel root hash）。

                          Root=H(H1+H2)
                         /              \
                  H1=H(T1+T2)        H2=H(T3+T4)
                 /          \        /          \
               T1          T2     T3          T4

只需要以下几个哈希值来验证 T3：

• T3 的哈希（自己有）

• T4 的哈希（路径上的兄弟节点）

• H1 的哈希（路径上的“叔叔”节点）

然后，用这些哈希值重构一个新的默克尔根，并与原来的默克尔根进行比对。如果一致，就证明了 T3 确实存在于该区块中。

现在，我们要证明一个交易 T5（假设其哈希值为 H(T5)）不存在于这个树中（假设交易已经按照哈希值排序）。

1. 寻找相邻节点: 假设 H(T5) 的值介于 H(T2) 和 H(T3) 之间，那么这两个哈希值就是它的相邻节点。

2. 提供路径证明: 为了证明 T5 不存在，我们需要提供从 H(T2) 和 H(T3) 到 Merkle Root 的路径。这个路径包括 H(T1 + T2) 和 H(T3 + T4)。

3. 验证与相邻交易的顺序关系: 确保 H(T2) < H(T5) < H(T3)。

4. 重新计算默克尔根: 使用提供的路径和相邻交易的哈希值重新计算 Merkle Root。这个重新计算的值应该与原来的 Merkle Root 相匹配。

5. 比对默克尔根: 如果重新计算出的 Merkle Root 与区块头中的 Merkle Root 匹配，那么证明了 T5 确实不存在于这个默克尔树中。