比特币那些事(3)——区块链

概述

通过 《比特币那些事(1)——入门》《比特币那些事(2)——交易》 两文,我们基本认识了比特币。本文我们来探索一下比特币工作的核心——区块链。 # 区块链 区块链,顾名思义,就是由一个个被称为区块的数据结构组成的一个链表。每个区块中都记录了大量的交易信息。比特币系统中的所有节点都维护着一个全局区块链,其中 全节点(完整节点)则拥有一份完整的拷贝。

既然区块链是由区块串联而成,那么区块之间是否有什么关系呢?事实上,每个区块都包含了前一个区块的信息。新的区块在创建时会对前一个区块的区块头进行 SHA256 加密,进而生成一个哈希值。然后在新区块的区块头中的 父区块哈希值 字段中引用该哈希值,从而实现每个区块头都包含它的父区块哈希值。最终形成一条可追溯到第一个区块(创世区块)的区块链。

区块链可以被存储为 平面文件(Flat File),或者被存储在数据库中。比特币核心客户端就是使用 Google 的 LevelDB 数据库存储区块链的元数据。

区块

区块本质上是一个服务于交易信息的容器数据结构。我们通过一个 Swift 开源库 BitcoinKit 来看看它是如何描述比特币的区块结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public struct BlockMessage {
/* 区块头 */
/// Block version information (note, this is signed)
public let version: Int32
/// The hash value of the previous block this particular block references
public let prevBlock: Data
/// The reference to a Merkle tree collection which is a hash of all transactions related to this block
public let merkleRoot: Data
/// A Unix timestamp recording when this block was created (Currently limited to dates before the year 2106!)
public let timestamp: UInt32
/// The calculated difficulty target being used for this block
public let bits: UInt32
/// The nonce used to generate this block… to allow variations of the header and compute different hashes
public let nonce: UInt32

/* 交易数 */
/// Number of transaction entries
public let transactionCount: VarInt

/* 交易列表 */
/// Block transactions, in format of "tx" command
public let transactions: [Transaction]
}

根据上述代码,其实我们可以把区块结构分为三部分:

  • Block Header:由多个字段构成的区块头
  • Transaction Count:记录本区块所记录的交易数量
  • Transactions:本区块所记录的区块列表

下面我们依次来看一下各个部分。

区块头

从上述示例代码可看出,区块头包含 6 个字段:

  • Version:本区块的版本号
  • Previous Block Hash:父区块的区块头哈希值
  • Merkle Root:由本区块交易构成的默克尔树(Merkle Tree)的树根值
  • Timestamp:本区块的创建时间戳
  • Difficulty Target:工作量证明的目标值,也称难度目标
  • Nonce:本区块计算出的工作量证明值

其中,Nonce、Difficulty Target、Timestamp 会用于挖矿过程。

Merkle Tree

上文我们提到每个区块中都包含一个 Merkle Root 的字段,用于记录默克尔树的树根。那么默克尔树是什么呢?为什么要建立这棵树?

默克尔树是一种 哈希二叉树,主要用于快速归纳和校验大规模数据完整性的数据结构。

在比特币系统中,默克尔树则被用来归纳一个区块中的所有交易,同时生成区块交易集合的数字指纹,并且提供了一种 校验区块中是否存在某交易 的高效途径。

默克尔树是自底向上构建的。构建默克尔树时会递归地对一对节点进行哈希,并将新生成的哈希节点插入到默克尔树中,直到只剩下一个哈希节点,即默克尔树的根。

下图所示,为我们对 A、B、C、D 4 个交易构建默克尔树的示例。

构建过程

首先,对每个交易进行加密哈希运算(Double-SHA256)得到叶子节点。

接着,将叶子节点两两串联后进行加密哈希运算得到父节点。

继续类似的操作,直到只剩下一个顶部的节点,即默克尔根(Merkle Root)。

由于默克尔树时二叉树,因此它需要偶数个叶子节点。如果仅有奇数个交易需要归纳,最后一个交易会被复制以构成偶数个叶子节点。如下图所示,C 节点会被复制。

由于加密哈希运算的结果长度始终都是都 32 位,所以无论使用多少交易来构建默克尔树,默克尔树的根的大小始终都是 32 位。

交易验证

为了证明区块中存在某交易,一个节点只需要计算 log2(N) 个哈希值,形成一条从该交易到树根的认证路径(也称默克尔路径)即可。这种验证方式可以将验证的时间复杂度从 O(N) 降到 log2(N)。随着交易数量的增加,这种验证方式的效率优势越明显。

以如下图所示的默克尔树为例,验证区块中是否存在交易 K。为了验证交易 K 是否存在,我们需要提供认证路径上的节点的子节点,即蓝色标注的节点,包括:

然后,使用交易 K 结合这些节点,以构建默克尔树的方式,依次进行加密哈希运算,得到:

计算得到的最后一个节点即 Merkle Root,如果它与区块中记录的 Merkle Root 的值一致,则表示本区块中存在交易 K。

这时候可能会产生一些问题:

  • 比特币系统中的节点不是都有一份全局区块链的副本吗?直接遍历区块链不就可以验证交易是否存在了吗?
  • 通过默克尔树验证交易时,辅助验证的那些节点从哪里来的?

事实上,比特币系统中并不是所有节点都保存了一份完整的全局区块链的副本。因为现阶段的比特币全局区块链数据量已经非常大了,对于普通的客户端,尤其是移动客户端,保存一份完整的区块链副本是不现实的。

因此,根据是否保存了一份完整的全局区块链副本,可以将比特币系统中的节点分成两种类型:

  • 全节点(Full Node):保存了一份完整的区块链副本,可以独立自主验证所有交易。
  • 轻节点(也称 SPV 节点):只保留了一部分区块链,依赖全节点提供验证数据,通过 简易支付验证 的方式验证交易。

事实上,基于默克尔树验证交易的方式就是所谓的 简易支付验证,主要用于轻节点。

简易支付验证

轻节点不会保存完整的区块链副本,仅仅保存区块头。它们使用认证路径来验证交易是否存在于区块中,而不必下载区块中的所有交易。

试想这样一个场景:一个 SPV 节点想知道它的钱包中的与某个地址相关的某个交易是否完成。

为了完成这个验证过程,SPV 节点首先会在节点间的通信链接上建立 布隆过滤器(Bloom Filter),限制只接受含有目标地址的交易。当对接的全节点探测到某个交易符合布隆过滤器,它将以 默克尔消息(Merkle Message)的形式发送该区块。

默克尔消息包含区块头和一条连接目标交易与默克尔根的认证路径。

SPV 节点使用默克尔消息中的认证路径以及目标交易得到默克尔根的值。然后与默克尔消息中的区块头的默克尔根值进行验证,从而判断对应区块中是否存在该交易。这种就可以证明交易是否存在于区块链中,即交易是否完成。

交易数

交易数记录了本区块包含多少条交易数据。

交易列表

交易列表中记录了一系列的交易。我们来看看开源库中是如何描述交易的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public struct Transaction {
/// Transaction data format version (note, this is signed)
public let version: UInt32

/// A list of 1 or more transaction inputs or sources for coins
public let inputs: [TransactionInput]

/// A list of 1 or more transaction outputs or destinations for coins
public let outputs: [TransactionOutput]

/// A list of witnesses, one for each input; omitted if flag is omitted above
// public let witnesses: [TransactionWitness] // A list of witnesses, one for each input; omitted if flag is omitted above
/// The block number or timestamp at which this transaction is unlocked:
public let lockTime: UInt32
}
对比 Transaction 类型的成员与《比特币(2)——交易》 所描述的交易的结构,两者基本一致。因此,本文也不再做赘述。

参考

  1. 《精通比特币》
  2. 《区块链开发指南》
  3. BlockChain 与 Ethereum 介绍
  4. BitcoinKit