北京大学肖臻老师《区块链技术与应用》公开课：03-BTC-数据结构

---

1.区块链（block chain）

比特币中最基本的数据结构是区块链，区块链是一个个区块组成的链表。区块链和普通链表的区别是用hash指针代替了普通指针。
普通指针：存储的是某个结构体在内存中的起始地址。
hash指针：存储某个结构体的内存地址和这个结构体的hash值。
hash指针的好处：除了可以根据地址找到结构体，还可以根据哈希值检查结构体内容是否被篡改。

创世区块的prev_hash被硬编码为全0（000…000），表示无前驱区块。
最后区块的哈希值保存在系统中，这个数据结构的好处只要记住最后区块的哈希值就可以检测出对区块链任意部位的修改。
每个区块分为块头（block header）和块体（block body）。

1.1.区块头（block header）

区块头通常包含版本号（比特币中哪个版本的协议）、前一个区块的哈希（区块头哈希）、Merkle tree根哈希、时间戳、难度目标和Nonce，这些都是用于维护区块链的连续性和安全性的关键信息。区块头是区块的元数据（Metadata），存储了与区块验证和链式结构相关的关键信息，体积小但安全性要求极高。

字段	内容及作用
版本号	标识区块遵循的协议版本（如比特币的 version 字段），用于网络升级兼容性。
前一个区块的哈希值	前一区块头的哈希值（prev_hash），用于链接到前一个区块，形成不可逆的链式结构。
Merkle根	当前区块所有交易生成的Merkle树的根哈希（merkle_root），用于快速验证交易完整性。
时间戳	区块生成的时间（Unix时间戳），防止区块被篡改或重复使用。
难度目标	当前区块的挖矿难度值（bits），用于调整PoW工作量证明的计算复杂度。
Nonce	随机数（nonce），矿工通过调整它来寻找满足难度目标的哈希值（完成挖矿）。

区块头的作用：

• 链式结构基础：通过prev_hash链接到前一区块，形成不可篡改的链。
• 快速验证：轻节点只需同步区块头即可验证交易存在性（依赖Merkle根）。
• 共识机制：Nonce和难度目标是工作量证明（PoW）的核心参数。

为什么指针是哈希值而非直接地址？
答：1.防篡改：哈希值（如SHA-256）具有抗碰撞性，无法伪造前一个区块的内容。修改前一个区块的数据会导致其哈希值变化，破坏链式连续性。
2.去中心化：节点只需验证哈希值是否匹配，无需信任第三方提供的“地址”。
3.空间效率：固定长度的哈希值（32字节）比存储区块地址更紧凑。
为什么指针不指向区块体？
答：区块头是轻量级元数据，全节点和轻节点均可快速验证。若指向区块体，验证效率会降低（需解析完整区块）。
如何找到前一个区块？
答：前一个区块哈希字段指向父区块的区块头哈希，形成逻辑上的“指针”。节点通过遍历prev_hash字段，按哈希值在本地数据库或网络中查询对应的区块头。
创世区块的prev_hash是什么？
答：比特币创世区块（Block 0）的prev_hash被硬编码为全0（000…000），表示无前驱区块。

比特币区块的生成流程

• 交易收集：矿工从内存池（Mempool）中选择交易，组成候选交易列表。
• Merkle树构建：计算交易列表的Merkle根，写入区块头。
• 挖矿竞争：调整Nonce，计算区块头哈希，直到满足难度目标。
• 区块广播：新区块被验证后加入链中，交易列表永久记录在区块体中。

1.2. 区块体（block body）

区块体则主要存储交易列表，也就是该区块打包的所有交易数据。体积较大但安全性依赖区块头。主要包含：

内容	描述
交易列表	该区块打包的所有交易（如比特币的transactions字段），包括普通交易和Coinbase交易（矿工奖励）。
其他辅助数据	某些区块链可能包含智能合约代码、状态变更记录等（如以太坊的区块体更复杂）。

区块体的作用：

• 数据存储：保存用户转账、智能合约执行等实际链上操作记录。
• 数据验证：通过Merkle树生成Merkle根，写入区块头，与区块头绑定确保交易数据无法篡改。

1.2.1.交易

交易列表在数据块中的角色
(1) 数据存储
交易列表是区块体的核心内容：每个区块体包含一个或多个交易（如比特币区块平均约2000笔交易），记录用户的链上操作（如转账、合约调用）。
(2)交易格式：
交易通常包含输入（资金来源）、输出（资金去向）、版本号、时间戳等信息。

• 输入（Inputs）：

字段名	描述
前一笔交易哈希(txid)	引用的前一笔交易的哈希（资金来源的交易id）。
输出索引（vout）	前一笔交易中的输出索引（指明具体使用哪个UTXO）。
解锁脚本（scriptSig）	提供签名和公钥，证明对资金来源的控制权（满足前一笔交易的 scriptPubKey。

• 输出（Outputs）：

字段名	描述
金额（value）	转账金额（以聪为单位，1 BTC = 10⁸聪）。
锁定脚本（scriptPubKey）	定义花费该输出的条件（如接收方地址的哈希或智能合约逻辑）。

• 其他字段：

字段名	描述
version	交易版本号（如隔离见证为版本2）。
locktime	交易生效时间（区块高度或时间戳）。

示例（简化）：

{"txid": "abc123...","inputs": [{"txid": "prevTxHash...","vout": 0,"scriptSig": "<signature> <pubKey>"}],"outputs": [{"value": 500000000, // 5 BTC"scriptPubKey": "OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG"}]
}

Coinbase交易：输入（TxIn）中txid为全0(000…000），因为无前一笔交易。scriptSig可包含矿工自定义数据（如“中本聪”的创世区块留言）。输出（TxOut）：矿工奖励（新生成的比特币） + 交易手续费。
为什么要把块头和块体分开？
这涉及到轻节点的运作方式，因为轻节点只需要下载块头来验证交易，而不需要存储整个块体，节省了存储空间和带宽。

2. 比特币中的节点

比特币中的节点分为两类：全节点（Full Node）和轻节点（Light Node）。全节点保存整个区块的内容，轻节点只保存区块头（block header）。

2.1.全节点（Full Node）

定义： 全节点是完全独立验证所有交易和区块的比特币客户端，存储完整的区块链数据，并严格执行比特币的共识规则。

核心功能：

• 完整区块链存储：下载并存储所有区块（截至2023年约500GB+数据）。
• 交易验证：检查每笔交易的签名、输入输出合法性，防止双花。
• 区块验证：验证区块头的PoW难度、时间戳、Merkle根等，确保符合共识规则。
• 广播与中继：将合法的交易和区块转发给其他节点，维护网络去中心化。

硬件要求：

• 存储：需要数百GB的硬盘空间（随时间增长）。
• 带宽：持续上传/下载数据（初始同步需数天）。
• CPU/内存：中等配置即可满足验证需求。

典型用户： 矿工、交易所、开发者、隐私重视者（如运行Bitcoin Core客户端）。

2.2.轻节点（Light Node）

定义： 轻节点（Simplified Payment Verification, SPV）是仅验证与自己相关交易的客户端，依赖全节点提供部分数据，不存储完整区块链。

核心功能：

• 区块头同步：仅下载区块头（每个区块头约80字节，总大小约50MB）。
• Merkle证明验证：通过全节点提供的Merkle路径验证交易是否在区块中。
• 隐私与效率：不暴露全部交易历史，适合移动端或低资源设备。

硬件要求：

• 存储：仅需几十MB存储区块头。
• 带宽：低消耗（仅同步区块头和请求特定交易数据）。
• 依赖全节点：需连接可信的全节点获取Merkle Proof。

典型用户： 手机钱包（如Electrum、BRD）、物联网设备、普通用户。

2.3. 其他比特币节点类型

(1) 矿工节点（Mining Node）
全节点的扩展，额外包含挖矿功能（计算Nonce竞争区块奖励）。
需要高性能硬件（ASIC矿机）和额外能源消耗。
(2) 归档节点（Archival Node）
全节点的变种，存储所有历史UTXO状态（未花费交易输出），用于区块浏览器或链分析。
(3) 种子节点（Seed Node）
提供初始连接引导，帮助新节点发现网络中的其他对等节点。

UTXO集（未花费交易输出）
作用：跟踪所有可用的比特币余额，避免全链扫描。
存储内容：

• txid + vout：唯一标识一个UTXO。
• value + scriptPubKey：面值和花费条件。
  更新规则：交易花费UTXO后，从集合中删除；新生成的输出加入集合。

3. Merkle tree

比特币中另一个数据结构是Merkle tree。区块链中的每个区块都有一个Merkle tree，Merkle tree是在生成区块时临时构建的，用于生成Merkle根，这个根哈希会被写入区块头。Merkle tee的结构不需要显式存储，而是通过交易列表动态生成。每个交易的哈希作为Merkle tree的叶子节点，根哈希是把所有交易的哈希两两哈希，然后层层向上计算，直到得到根哈希。如果有奇数个交易，会复制最后一个交易凑成偶数。

Binary tree和Merkle tree的区别就是把普通指针换成hash指针。

这个数据结构的好处：只要记住根哈希值，就能检测出对树中任何部位的修改。
Merkle树的作用，比如高效验证交易的存在性和完整性。优势有高效验证、节省存储空间和带宽。Merkle树的结构允许通过哈希值快速验证数据完整性，而无需暴露全部交易内容。
全节点如何高效地重建Merkle树并快速找到特定交易的路径？
如果交易数量很大，每次请求都重新构建整个Merkle树会效率很低，比如，比特币的一个区块可能包含上千笔交易，每次处理请求时都重新计算所有节点的哈希值可能不太实际。
解决方案是：全节点在存储交易列表时，已经预先计算并缓存了Merkle树的某些部分，或者优化了哈希计算的方式，以便快速生成所需的路径。例如，全节点可以根据目标交易在交易列表中的索引位置按需计算每一层的哈希，而不需要一次性构建整个树。当需要某个特定路径时，全节点只需从交易列表开始，按需生成该路径上的所有哈希值。全节点可缓存常用区块的中间哈希，加速重复请求。

4. Merkle proof

Merkle tree的一个作用是提供Merkle proof。
Merkle proof是如何工作的？当需要验证某个交易时，提供从该交易到根哈希的路径上的所有兄弟节点的哈希，这样通过计算路径上的哈希组合，就能验证是否得到正确的根哈希，从而确认交易的有效性。

4.1. 证明Merkle tree中包含某个交易

1.如何向轻节点证明某个交易是写到区块链的？
找到这个交易所在的位置，从这个交易向上一直到根节点，这条路径就是Merkle proof。

轻节点向某个全节点发出请求，请求一个能够被证明的交易被包含在merkle tree中的merkle proof。全节点收到请求后，根据请求中的交易信息，找到其在区块中的位置，重新生成Merkle树，并收集路径上的哈希值，把图中红色的哈希值按顺序发送给轻节点。有了这些哈希值后，轻节点在本地可以计算图中标为绿色部分的哈希值，最后算出根哈希值。轻节点把算出来的哈希值和块头（block header）中的根哈希值对比一下是否相等。相等证明交易在merkle tree中。也即交易包含在区块链中。这个时间复杂度为O(logn)。

4.2.证明Merkle tree中不包含某个交易

1.如何证明merkle tree中不包含某个交易？
全节点把整棵merkle tree传给轻节点，轻节点收到后验证树的构造是对的，每一层用到的哈希值是对的，这样说明merkle tree中只有这些叶节点，看找的交易是否在里面，这个时间复杂度是O(n)。线性的。如果不对叶节点的排序做任何假设的话没有更高效的方法证明不包含性。
如果对叶节点的顺序做一些要求，比如按照交易的哈希值从小到大排序，看该交易的哈希值如果在里面应该在哪个位置，比如在A,B两个交易之间，提供A,B两个交易都往根节点的路径，如果算出来的根哈希值和轻节点block header中的根哈希值相等证明A,B交易是相邻交易。所以该交易不存在merkle tree中。这个时间复杂度为O(logn)。
这种排好序的叫Sorted Merkle Tree，比特币中没有用到这种排好序的Sorted Merkle Tree。因为比特币并不需要做这种不存在证明。没有这种硬性需求。区块链和merkle tree 都是用hash指针来构造。
只要数据结构是无环的都可以用hash指针来代替普通指针。