比特币的数据结构
比特币系统中主要使用了两种核心数据结构：Hash Pointers（哈希指针） 和 Merkle Tree（默克尔树）。
Hash Pointers（哈希指针）
普通的指针通常只存储结构体在内存中的地址，而 哈希指针（Hash Pointer） 在此基础上，还额外存储了该结构体的 哈希值。
这种设计的优势在于：我们不仅能找到数据在哪里（寻找位置），还能确认该数据是否被修改过（验证防篡改）。
区块链（The Blockchain）
区块链本质上就是一个由哈希指针串联起来的链表（Linked List）。它与普通链表的关键区别在于：它使用哈希指针代替了普通指针。
如上图所示，这是一个简化的区块链结构：
- Genesis Block（创世块）：链条最前端的第一个区块。
- Most Recent Block：当前最新产生的区块。
每个区块都包含了一个指向前一区块的哈希指针。如果我们系统中保存了指向最后一个区块的哈希指针，就能牵一发而动全身地锁定整条链的内容。
防篡改原理：
如果有人恶意篡改了链中间的某个区块，那么该区块的哈希值必然发生变化；这将导致后一个区块中存储的“前驱哈希指针”失效。为了掩盖修改，攻击者必须接着修改后一个区块的内容……如此一直向后，直到修改到最后一个区块。
但也因为我们手里掌握着最后一个区块的哈希指针（锚点），攻击者的修改最终会被我们发现。因此，只需要保存最后一个区块的哈希值，就可以验证整条链的数据完整性。
同理，验证过程也是从后向前，利用后一个区块保存的哈希值，逐个校验前一个区块是否合规。
Merkle Tree（默克尔树）
Merkle Tree 可以看作是哈希指针的一种高级应用（将线性的链表扩展为树状结构）。
- Data Blocks（数据块）：树的最底层（叶子节点），在比特币中对应着具体的一笔笔交易。
- 结构特点：每上一层的节点，都包含了下层两个子节点的哈希值。
- Root Hash（根哈希）：通过层层向上计算，最终树的顶部会得到一个唯一的根哈希值。
作用：
类似于区块链，我们只需要保存树根的 Root Hash，就能验证整棵树中（也就是所有交易中）的任意一笔数据是否被篡改。
Merkle Proof（默克尔证明）
在区块链网络中，节点的存储方式主要分为两种：
- 全节点（Full Node）：保存了整条区块链的所有数据，包括 Merkle Tree 的所有节点信息。
- 轻节点（Light Node / SPV Node）：只保存区块头信息（Block Header），其中包含了 Merkle Root，但不保存具体的交易列表。
场景应用：
如果一个轻节点用户（例如手机钱包用户）想要确认“我收到的这笔交易（黄色 tx）”是否真的被打包进了某个区块中，但他手中没有完整的交易数据，该怎么办？这就需要用到 Merkle Proof。
验证流程（如上图所示）：
- 发起请求：轻节点向全节点发起查询请求。
- 获取证明：全节点不需要发送整棵树的数据，只需要发送从这笔交易通往树根路径上缺失的兄弟节点哈希值（图中红色部分）。这一组哈希值序列就是 Merkle Proof。
- 本地计算：轻节点收到证明后，会在本地进行计算。它首先计算目标交易的哈希，然后将其与红色的兄弟哈希结合，计算出上一层的父节点哈希（图中绿色部分），如此层层向上计算。
- 最终比对：最终算出的根哈希值，与轻节点手中区块头里存储的 Merkle Root（橙色块）进行比对。
- 结论：如果两者一致，即可数学证明该笔交易确实存在于该区块的 Merkle Tree 中。
Proof of Membership 与 Non-Membership
上述的 Merkle Proof 实际上是在证明“某笔交易存在于 Merkle Tree 中”，因此这种证明也被称为 Proof of Membership（或 Proof of Inclusion）。
对于一个轻节点来说，假设区块中有
思考：如何证明 Merkle Tree 里面【不包含】某笔交易（Proof of Non-Membership）？
普通 Merkle Tree：如果叶子节点的排列没有顺序，要证明某笔交易不存在，最笨的方法是把整棵树传给轻节点供其遍历验证，复杂度为
，这显然不可接受。 Sorted Merkle Tree（排序默克尔树）：
如果我们在构建 Merkle Tree 时，对叶子节点按照哈希值进行排序，情况就不同了。
要证明某笔交易不存在，只需要计算该交易的哈希值，并在排序好的叶子节点中找到它“理论上应该出现的位置”。
例如：交易哈希值为，我们找到相邻的两个叶子节点 和 ，使得 。只要我们能提供 和 的 Merkle Proof，证明它们确实是相邻的叶子节点，且原树中确实存在这两个值，就能间接证明 并不存在于这棵树中。 这种情况下，验证”不存在”的复杂度也降低 到了
。
代价：构建树时需要排序。
现状：比特币系统中目前并没有使用 Sorted Merkle Tree，因为比特币主要只需要验证交易的“存在性”。
思考：如果查找位置刚好处于两个“非同父”的叶子节点之间，该如何验证？
比如目标交易夹在叶子节点
和 之间（ ），但 和 分属不同的分支（即它们不是同一个父节点下的兄弟）。
此时需要同时提供 节点和 节点 的完整 Merkle Proof。验证端通过校验这两条路径，确认 和 均有效且位置索引紧邻（例如索引 和 ）。虽然需要两条路径（数据量为 ），但整体复杂度依然保持在对数级别 。
特别致谢：
在此想要特别称赞一下 肖臻老师。作为一门公开课，老师还能这么尽职尽责地专门绘制了这样一张清晰的哈希验证示意图，让抽象的 Merkle Proof 验证逻辑变得一目了然，非常令人敬佩。