哈希指针(Hash Pointer)

• 哈希指针不仅存储了数据的内存地址，还额外存储了那块数据内容的加密哈希值。
• 组成：一个哈希指针包含两个部分：
  • 指针 (Pointer)：指向数据的存储位置。
  • 哈希 (Hash)：指向的数据内容的哈希值。

区块链是一连串的哈希指针配合组成的：

• 我们有一个数据块 Block 1。
• 我们创建一个指向 Block 1 的哈希指针 HP_1。这个指针里包含了 Block 1 的地址和 Hash(Block 1)。
• 现在，我们创建第二个数据块 Block 2。我们将哈希指针 HP_1 存放在 Block 2 的内部。
• 接着，我们再创建一个指向 Block 2 的哈希指针 HP_2，它包含 Block 2 的地址和 Hash(Block 2)。
• 然后我们将 HP_2 存入 Block 3 中……如此往复。

这条由哈希指针连接起来的链条，具有极强的防篡改能力，或称为防篡改日志，而且这种能力是向后传递的。 假设一个攻击者想要篡改 Block 1 里的内容。

1. 篡改数据：攻击者修改了 Block 1 的数据。
2. 哈希值改变：由于哈希函数的雪崩效应，Block 1 的哈希值 Hash(Block 1) 会立刻发生巨大变化。
3. 链接断裂：存放在 Block 2 里的那个哈希指针 HP_1，它里面记录的还是原始的 Hash(Block 1)。现在这个记录与 Block 1 新的哈希值对不上了！任何人只要一检查，就会立刻发现这个矛盾，从而知道 Block 1 被篡改了。
4. 连锁反应：为了掩盖罪行，攻击者必须更新 Block 2 里的哈希指针。但如果他修改了 Block 2 的内容（哪怕只是更新了里面的一个哈希值），Block 2 自身的哈希值 Hash(Block 2) 也会跟着改变。
5. 无法逃脱：这个改变又会与存放在 Block 3 里的哈希指针 HP_2 产生矛盾。攻击者因此必须一路修改下去，直到链条的最后一个区块。

区块链 (Blockchain) 本质上就是一个由哈希指针连接起来的、反向链接的区块列表。而只要保存最后一个哈希指针，就能知道整条链数据是否正确，同时，在去中心化系统中也可以不用保存完整的链，需要的时候再向别的节点请求，并可以通过这个哈希指针知道别的节点给你的区块对不对。

需要注意的是，在实际系统中，哈希指针只有哈希，没有指针，所谓的指针，是逻辑上的哈希指针。比特币中的“哈希指针”与我们通常在编程语言（如C++）中谈论的“内存地址指针”是完全不同的两个概念。“哈希指针”并不是一个指向内存地址的指针，而是一个包含了两重信息的强大数据结构：

• 一个“指针” (Pointer)：它指向前一个区块。这个“指向”的动作，是通过存储前一个区块的唯一标识符来实现的。
• 一个“哈希” (Hash)：这个唯一标识符，恰恰就是前一个区块所有内容的加密哈希值（在比特币中是SHA-256哈希值）。

所以，BTC中对于哈希指针更准确的描述是：哈希指针是一个包含了前一个区块哈希值的变量，通过这个哈希值，我们可以唯一地找到并验证前一个区块，从而在逻辑上“指向”它。

默克尔树（Merkle Tree）

1. 叶子节点 (Leaf Nodes)：
   • 拿出你所有需要处理的数据块（比如，比特币中的每一笔交易）。
   • 对每一块数据单独进行一次哈希计算，得到各自的哈希值。这些哈希值就构成了Merkle树的最底层——叶子节点。
2. 中间节点 (Non-leaf Nodes)：
   • 将底层的叶子节点两两配对。
   • 将每一对哈希值拼接在一起，然后对这个拼接后的新字符串再进行一次哈希计算。
   • 这样生成的新的哈希值就构成了上一层的父节点。
3. 循环向上构建：
   • 重复第二步的过程，将新生成的一层节点继续两两配对、拼接、哈希，再生成更上一层的父节点。
   • 这个过程不断重复，每一层的节点数量大约是下一层的一半。
4. 默克尔根 (Merkle Root)：
   • 最终，这个过程会收敛到只剩下一个节点，这个唯一的、位于树顶端的哈希值，就是默克尔根。

Hash(AB) 是由 Hash(A) 和 Hash(B) 拼接后哈希得到的。Root 就是由 Hash(AB) 和 Hash(CD) 拼接后哈希得到的。

优点：

• 总数据完整性验证：
  • 无论你有10条数据还是100万条数据，最终你都可以用一个简短的、固定长度的默克尔根来代表整个数据集合的“指纹”。
  • 这个根对所有原始数据都极其敏感。只要原始数据中任何一个字节发生改变，都会通过“雪崩效应”层层向上传递，最终导致默克尔根发生巨大变化。
• 高效的局部完整性验证（默克尔证明 Merkle Proof）：
  • 这是Merkle树最强大的功能。假设你有一个庞大的数据集（比如一个1GB的文件或一个包含4000笔交易的比特币区块），而我只想验证其中一小块数据（比如文件中的某几KB或者区块中的某一笔交易）是否真的属于这个集合，且没有被篡改。
  • 传统方法：我需要下载整个1GB的文件，计算它的总哈希值，然后和你给我的总哈希值进行比对。这非常浪费带宽和计算资源。
  • Merkle树方法：你不需要给我整个1GB的文件。你只需要给我那一小块数据，以及从它所在的叶子节点到默克尔根路径上的**“兄弟节点”（这被称为默克尔证明或默克尔路径**）。我只需要进行几次哈希计算（计算次数与树的深度成正比，而不是与数据总量成正比），就能重新计算出默克尔根，并与你公布的官方默克尔根进行比对。
  • 优势：验证一个拥有上百万条记录的数据集合中的某一条记录，可能只需要几十次哈希计算和几KB的验证数据。

在一个比特币区块中，成百上千笔交易被构建成一棵Merkle树。最终，只有默克尔根被记录在区块头 (Block Header) 中。这可以使得轻节点（或SPV节点）在不下载整个区块数据的情况下，高效地验证某笔特定交易是否存在于这个区块中。这实际上是成员资格证明 (Proof of Membership)，即能够证明某个特定数据确实属于一个更大集合的方法，而无需暴露这个集合中的所有其他成员。

![[Pasted image 20250614134645.png]]

默克尔证明本身是强大的“证有”工具，却是无力的“证无”工具。它无法防范恶意全节点的“谎报军情”（Lie by Omission）。因此，轻节点的安全性并不单纯依赖于默克尔证明，而是建立在一套更广泛的信任和冗余机制之上，其中连接多个节点是最核心的安全保障。

为了解决这个问题，可以引入“顺序”的概念。只要数据是有序的，我们就可以证明某个元素“不在它该在的位置上”。

以下是几种主流的解决方案：

1. 有序默克尔树 (Sorted Merkle Tree)

这是最直观的改进方法。它要求在生成默克尔树之前，先将所有的叶子节点（例如，交易ID）按照字母或数字顺序进行排序。

• 如何工作：所有叶子节点 L1, L2, L3, ..., Ln 是有序的。
• 如何证明缺席：如果您想证明某个交易 T_x 不存在于树中，您不需要检查整棵树。您只需要找到在排序列表中与 T_x 相邻的两个叶子节点 L_i 和 L_{i+1}，并提供它们俩的默克尔证明。
  • 这个证明相当于证明：“L_i 和 L_{i+1} 在树中是紧挨着的，而 T_x 按顺序应该在它们俩中间。既然它们之间没有空隙，那么 T_x 就不可能存在。”

2. 稀疏默克尔树 (Sparse Merkle Tree - SMT)

这是一种非常强大和优雅的解决方案，被许多现代区块链项目采用。

• 如何工作：SMT是一棵拥有巨大且固定深度的树（例如256层），这意味着它有 2^{256} 个可能的叶子节点位置，足以覆盖所有可能的哈希值。树中绝大多数叶子节点都是“空的”，并用一个公开已知的、统一的“零值占位符”（null value）来表示。
• 如何证明缺席：证明一个元素不存在，就等同于证明它所对应的叶子节点的位置上，其值是那个“零值占位符”。这本质上是一个标准的默克尔“包含”证明——你只是在证明这个位置“包含”了一个“空”值。
• 类比：想象一个有无数格子的巨型货架，每个格子都有唯一的编号。当一个包裹（数据）存入时，它会被放在对应编号的格子里。要证明编号为 #123 的格子是空的，你只需要走过去，拍一张照片（默克尔证明），显示那个格子里确实空无一物。

3. 默克尔帕特里夏树 (Merkle Patricia Trie - MPT)

这是以太坊（Ethereum）采用的核心数据结构。它是一种结合了默克尔树和前缀树（Trie）的复杂结构。由于其基于键值（Key-Value）的特性，它天然就是有序的，并且能非常高效地生成关于某个键（Key）是否存在或缺席的证明。