第 3 讲：BTC 数据结构

1. 本节主线

1. 本节课讲 Bitcoin 中最基础的两类数据结构：blockchain 和 Merkle tree。
2. 两者的共同核心都是 hash pointer：既能定位数据，又能验证数据是否被篡改。
3. blockchain 用 hash pointer 把一个个 block 连成链，从而形成 tamper-evident log。
4. Merkle tree 用 hash pointer 组织一个 block 内部的 transactions，使轻节点可以高效验证某笔交易是否被包含在区块中。
5. 本节重点不是复杂的共识机制，而是理解 Bitcoin 为什么能用数据结构本身提供“可验证性”。

2. 核心概念速览

3. 知识结构图

  flowchart TD
    A[Bitcoin 数据结构] --> B[hash pointer]
    B --> C[blockchain]
    B --> D[Merkle tree]

    C --> C1[block 之间相连]
    C --> C2[tamper-evident log]
    C --> C3[只保存最新 hash 也可检测历史修改]

    D --> D1[组织 block 内 transactions]
    D --> D2[root hash 存入 block header]
    D --> D3[Merkle proof]

    D3 --> E1[proof of membership]
    D3 --> E2[light node 验证交易]
    D --> F[proof of non-membership]
    F --> F1[普通 Merkle tree 低效]
    F --> F2[sorted Merkle tree 可高效证明不存在]
  

这张图的主线是：hash pointer 是底层工具，blockchain 和 Merkle tree 是两个具体应用场景。blockchain 解决的是“历史记录是否被篡改”的问题；Merkle tree 解决的是“某笔交易是否包含在某个 block 中”的高效证明问题。

4. 课程内容详解

4.1 hash pointer：比普通 pointer 多了完整性验证

普通 pointer 只保存某个数据结构在内存中的地址。
例如，一个 pointer p 指向某个结构体，它的作用只是“找到这个结构体在哪里”。

hash pointer 则多保存一份被指向数据的 hash 值：

1

hash pointer = 数据位置引用 + 数据内容的 hash 值

这样它就有两个功能：

1. 定位数据：知道数据在哪里。
2. 验证数据：重新计算数据的 hash，和 pointer 中保存的 hash 对比。

如果数据内容被改了，那么重新计算出来的 hash 会发生变化，于是 hash pointer 中保存的 hash 就对不上了。

关键理解：
hash pointer 不只是“指向数据”，还把“数据应该长什么样”压缩成 hash 值保存下来。

4.2 blockchain：用 hash pointer 连接 block 的链表

Bitcoin 中的 blockchain 可以理解为一个由 block 组成的链表。
但它和普通链表不同：普通链表用 pointer 连接节点，blockchain 用 hash pointer 连接 block。

每个 block 中都保存指向前一个 block 的 hash pointer：

1
2
3

Block n 中保存 Block n-1 的 hash
Block n-1 中保存 Block n-2 的 hash
……

最早的 block 叫做 Genesis Block。

这种结构带来的结果是：
如果有人修改了历史上的某个 block，那么这个 block 的 hash 会变化。于是下一个 block 中保存的 hash pointer 就对不上。为了继续伪装，他还必须修改后一个 block，再修改再后一个 block，直到最新 block。

这就是课程中说的“牵一发而动全身”。

4.3 tamper-evident log：不是不能改，而是改了会被发现

blockchain 的性质可以称为 tamper-evident log。

这里要注意一个易错点：

blockchain 并不是说数据在物理上“绝对不能被修改”。
它的意思是：只要修改了历史数据，就会破坏后续 hash 关系，从而留下可验证的痕迹。

假设系统只保存最新 block 的 hash。
如果历史中任意一个 block 被修改，那么这个修改会沿着 hash pointer 一路传导，最终导致最新 block 的 hash 也变化。

因此，只要最新 hash 是可信的，就可以检测出整条链中是否发生过篡改。

4.4 为什么部分节点可以不保存完整 blockchain？

课程中提到，有些节点不一定保存整条 blockchain，只保存最近的一部分 block。

如果它需要更早的 block，可以向其他节点请求。
问题是：Bitcoin 是去中心化系统，别人发来的 block 不一定可信。

这时 hash pointer 的作用就体现出来了：

1. 节点向别人请求某个旧 block。
2. 收到后，自己计算这个 block 的 hash。
3. 将计算结果和自己保存的后续 block 中的 hash pointer 对比。
4. 如果一致，说明这个 block 与后续链条匹配。
5. 如果不一致，说明数据可能被篡改或不是正确 block。

也就是说，即使数据来自不可信节点，也可以通过 hash pointer 自行验证。

4.5 Merkle tree：用 hash pointer 组织 block 内部交易

Bitcoin 中，每个 block 内部包含很多 transactions。
这些 transactions 不是随便堆在一起，而是组织成一棵 Merkle tree。

Merkle tree 的基本结构是：

1. 最底层叶节点是 transactions。
2. 每个 transaction 先计算 hash。
3. 相邻两个 hash 拼接后再 hash，得到父节点 hash。
4. 一层层向上计算，最后得到 root hash。
5. root hash 存入 block header。

简化表示：

1
2
3
4
5

H(tx1)      H(tx2)      H(tx3)      H(tx4)
   \        /             \        /
   H(H1||H2)              H(H3||H4)
          \              /
             root hash

其中 || 表示拼接。

Merkle tree 的关键性质是：

只要记住 root hash，就可以检测整棵树中任意 transaction 是否被修改。

因为任何一个叶节点 transaction 改变，都会导致它的 hash 改变，再导致父节点 hash 改变，最后传导到 root hash。

4.6 block header 与 block body

课程中区分了一个 block 的两个部分：

重要的是：

block header 中没有完整 transaction list，只有这些 transactions 组成的 Merkle tree 的 root hash。

这使得轻节点可以只保存 block header，而不用保存所有交易细节。

4.7 full node 与 light node

Bitcoin 中节点大致可以分为：

例如手机上的 Bitcoin 钱包通常更接近 light node。
它不可能保存完整 blockchain 的全部交易数据，但它仍然希望能验证：

某笔付款交易是否真的已经被写入 blockchain？

这个问题就需要 Merkle proof。

4.8 Merkle proof：证明某笔交易被包含在区块中

Merkle proof 也叫：

• proof of membership
• proof of inclusion

它要证明的是：

某个 transaction 是否属于某个 block 的 Merkle tree。

假设 light node 想验证交易 tx 是否在某个 block 中。
它自己只有 block header，也就是只有 root hash，没有完整 Merkle tree。

于是它向 full node 请求证明。
full node 不需要把整棵树都发过来，只需要发送从该 transaction 到 root 路径上计算所需的“兄弟节点 hash”。

light node 收到后：

1. 先计算 tx 的 hash。
2. 和 full node 提供的兄弟 hash 拼接。
3. 继续向上计算父节点 hash。
4. 重复这个过程，直到算出 root hash。
5. 将算出的 root hash 与 block header 中的 root hash 对比。
6. 如果一致，就说明该 transaction 被包含在这个 block 中。

Merkle proof 的优势是复杂度低：

1
2

如果 block 中有 n 笔交易，
Merkle proof 只需要 O(log n) 个 hash。

这比发送完整 transaction list 高效得多。

4.9 为什么只验证路径就够了？

一个初学者容易产生疑问：

light node 只能验证 transaction 所在路径上的 hash，旁边那些分支它没有完整数据，为什么还可以相信？

核心原因是 collision resistance。

假设攻击者修改了某个 transaction，但还想让最终 root hash 不变。
他就必须构造出不同的数据，使得 hash 结果和原来一样。

这相当于人为制造 hash collision。
在安全 hash function 的 collision resistance 假设下，这是计算上不可行的。

因此，只要最终算出的 root hash 和 block header 中的 root hash 一致，light node 就可以认为这条 proof 是有效的。

4.10 proof of non-membership：证明“不存在”更难

Merkle proof 很适合证明某个 transaction 存在。
但如果要证明某个 transaction 不存在，普通 Merkle tree 就麻烦得多。

最直接的方法是：

1. full node 把整棵 Merkle tree 或完整 transaction list 发给 light node。
2. light node 验证整棵树构造正确。
3. light node 检查目标 transaction 不在所有叶节点中。

这样当然可以证明不存在，但复杂度是：

1

O(n)

不再是 O(log n)。

原因是：
如果叶节点没有排序，那么目标 transaction 理论上可能出现在任意位置。
你不看完整交易列表，就无法确认它真的不在里面。

4.11 sorted Merkle tree：高效证明不存在

如果要求 Merkle tree 的叶节点按照某个规则排序，比如按照 transaction hash 从小到大排序，那么就可以更高效地做 proof of non-membership。

思路是：

1. 先计算目标 transaction 的 hash。
2. 根据排序规则，判断它如果存在，应该位于哪两个叶节点之间。
3. full node 提供这两个相邻叶节点的 Merkle proof。
4. light node 验证这两个叶节点确实都在树中，并且它们相邻。
5. 如果目标 hash 应该在二者之间，但实际没有出现，就证明目标 transaction 不存在。

这种结构叫做 sorted Merkle tree。

不过课程中特别指出：

Bitcoin 中没有使用 sorted Merkle tree。
因为 Bitcoin 没有强需求去高效证明某笔交易“不存在”。

Bitcoin 更常见的需求是证明某笔交易“已经被包含进某个 block”。

4.12 hash pointer 适合无环数据结构

课程最后提到：
只要数据结构是 acyclic，也就是无环的，就可以用 hash pointer 替代普通 pointer。

例如：

• linked list
• tree
• directed acyclic graph, DAG

但如果数据结构中有环，就会出现问题。

比如循环链表：

1

A -> B -> C -> A

如果这些都是普通 pointer，完全没问题。
但如果换成 hash pointer，就会产生循环依赖：

1. A 的 hash pointer 依赖 B 的内容。
2. B 的 hash pointer 依赖 C 的内容。
3. C 的 hash pointer 又依赖 A 的内容。
4. A 的内容又还没有最终确定。

这样就变成“谁都要等别人先确定”，最终无法完成 hash 计算。

所以 hash pointer 天然适合无环结构，不适合直接用于有环结构。

5. 关键机制图解

5.1 blockchain 中的 hash pointer 结构

  flowchart LR
    G[Genesis Block] -->|hash pointer| B1[Block 1]
    B1 -->|hash pointer| B2[Block 2]
    B2 -->|hash pointer| B3[Latest Block]
    B3 --> H[系统保存 latest hash]

    X[修改 Genesis Block] -.导致.-> G
    G -.hash 改变.-> B1
    B1 -.hash 改变.-> B2
    B2 -.hash 改变.-> B3
    B3 -.latest hash 不匹配.-> H
  

这张图表示：历史 block 的任何修改都会改变自身 hash，然后影响后续 block 中保存的 hash pointer，最终影响 latest hash。因此，只要 latest hash 是可信的，就可以检测历史数据是否被篡改。

5.2 Merkle tree 的交易组织方式

  flowchart TD
    R[root hash]

    A[H12]
    B[H34]
    R --> A
    R --> B

    A --> H1[H tx1]
    A --> H2[H tx2]
    B --> H3[H tx3]
    B --> H4[H tx4]

    H1 --> T1[tx1]
    H2 --> T2[tx2]
    H3 --> T3[tx3]
    H4 --> T4[tx4]
  

这张图展示了 Merkle tree 的基本结构。最底层是 transactions，向上逐层计算 hash，最终得到 root hash。root hash 相当于整个交易集合的“摘要”。

5.3 light node 使用 Merkle proof 验证交易

  flowchart TD
    L[light node 只有 block header] --> R[root hash]
    L --> Q[请求 tx 是否在 block 中]

    F[full node] --> P[返回 Merkle proof]
    P --> S1[tx 本身]
    P --> S2[兄弟节点 hash]
    P --> S3[路径上所需 hash]

    L --> C[本地自底向上计算 root hash]
    C --> M{是否等于 block header 中的 root hash?}

    M -->|是| Y[tx 被证明包含在 block 中]
    M -->|否| N[proof 无效]
  

这个机制的关键是：light node 不需要完整 block body，也不需要完整 Merkle tree，只需要少量路径信息，就可以验证某笔交易是否属于某个 block。

6. 易混点与常见误解

7. 课堂外补充理解

7.1 tamper-evident 与 tamper-proof 的区别

本节课强调的是 blockchain 的 tamper-evident 性质，而不是绝对 tamper-proof。

• tamper-proof：让篡改完全无法发生。
• tamper-evident：篡改可以尝试发生，但会留下证据。

Bitcoin 的数据结构本身主要提供的是 tamper-evident。
至于为什么攻击者即使修改并重算后续 block 也很难成功，还需要后续课程中的 proof of work 和共识机制来解释。

本节只需要先理解：
hash pointer 让篡改变得“可检测”。

7.2 root hash 为什么可以代表整棵树？

root hash 不是简单地 hash 某一笔交易，而是由所有叶节点 transaction 的 hash 层层计算得到。

因此，root hash 依赖于：

1. 每一笔 transaction 的内容；
2. transaction 在 Merkle tree 中的位置；
3. 每一层 hash 的组合结果。

只要其中任何一项变了，最终 root hash 通常都会变。

所以 root hash 可以被看作整棵 Merkle tree 的简短摘要。

7.3 Merkle proof 为什么是 O(log n)？

如果 Merkle tree 是平衡二叉树，底层有 n 个 transactions，那么树高大约是：

1

log2(n)

验证某个 transaction 时，只需要沿着从叶节点到 root 的路径向上计算。
每一层只需要一个兄弟节点 hash。

所以 proof 的大小和验证步骤数量都是：

1

O(log n)

这就是 Merkle tree 对 light node 特别重要的原因。

8. 本节小结

1. Bitcoin 的两个基本数据结构是 blockchain 和 Merkle tree。
2. 它们都建立在 hash pointer 之上，用 hash 提供完整性验证。
3. blockchain 用 hash pointer 连接 block，使历史修改会影响后续所有 block。
4. Merkle tree 用 hash 组织一个 block 内部的 transactions，root hash 存在 block header 中。
5. light node 不保存完整交易列表，但可以通过 Merkle proof 验证某笔交易是否被包含在 block 中。
6. 普通 Merkle tree 擅长证明 membership，但不擅长高效证明 non-membership。
7. sorted Merkle tree 可以更高效证明元素不存在，但 Bitcoin 中没有采用这种结构。
8. hash pointer 适合无环数据结构，不适合直接用于循环结构。

9. 自测问题

1. 什么是 hash pointer？它比普通 pointer 多了什么功能？

参考答案：
hash pointer 可以理解为“数据引用 + 数据 hash”。普通 pointer 只能定位数据，hash pointer 还能通过重新计算 hash 来验证数据是否被篡改。

2. 为什么 blockchain 可以检测历史 block 的修改？

参考答案：
因为每个 block 都保存前一个 block 的 hash。如果历史 block 被修改，它的 hash 会变化，导致后一个 block 中保存的 hash pointer 不匹配，并继续影响后续 block，最终影响 latest hash。

3. blockchain 是不是说明数据绝对不能被篡改？

参考答案：
不是。数据在物理上可以被改，但改了以后 hash 关系会被破坏，容易被检测出来。更准确地说，blockchain 提供 tamper-evident 的性质。

4. Merkle tree 在 Bitcoin 中用来解决什么问题？

参考答案：
Merkle tree 用来组织一个 block 中的 transactions，并通过 root hash 摘要式代表整个交易集合。它允许 light node 用 Merkle proof 高效验证某笔交易是否被包含在 block 中。

5. block header 和 block body 分别保存什么？

参考答案：
block header 保存 Merkle root 等摘要和元数据；block body 保存具体的 transaction list。light node 通常只保存 block header，full node 保存完整 block。

6. light node 如何验证某笔交易已经写入区块？

参考答案：
light node 向 full node 请求 Merkle proof。full node 返回该 transaction 到 root 路径上需要的兄弟节点 hash。light node 自底向上计算 root hash，并与 block header 中保存的 root hash 对比。一致则证明交易被包含。

7. 为什么普通 Merkle tree 难以高效证明某笔交易不存在？

参考答案：
因为叶节点没有排序时，目标交易可能出现在任意位置。除非检查完整交易列表，否则无法确认它不存在。因此普通 Merkle tree 的 non-membership proof 通常需要 O(n)。

8. 为什么 hash pointer 不适合直接用于循环链表？

参考答案：
因为会产生循环依赖。每个节点的 hash pointer 都依赖下一个节点的内容，而下一个节点又间接依赖自己，导致所有节点内容都无法先确定下来。