BTC 中对交易数据的存储主要涉及到了两种数据结构,一种是区块链,一种是 Merkle Tree。这两种数据结构组成了 BTC 中完整的区块链结构(如下图所示),共同完成对数据的存储和验证,确保交易的有效性。

一、区块链

所谓的区块链是由一个个区块构成的链,其中,每一个区块包括两个部分,分别是块头(block header)和块身(block body),块头中包含了指向前一个区块的哈希值指向块身中 Merkle Tree 的 merkle root hash时间戳等信息,块身中包含了交易数据列表。

区块链与普通链表相似,但是存在一定的区别:

(1)区块链用哈希指针代替了普通指针

(2)区块链具有防篡改、易验证的性质

区块链这种数据结构具有防篡改(tamper-evident log)的性质,这与普通链表是不同的。当对普通链表中的任意元素进行修改时,对其他元素是没有影响的,而区块链是牵一发而动全身的,由于每个区块都保留了由前一区块计算得到的哈希指针,因此,改变前面的任意一个区块,都会导致后面区块的哈希指针完全对不上,从而引发多米诺骨牌效应,实现对数据篡改的定位。

二、Merkle Tree

所谓的 Merkle Tree 是一种与 Binary Tree 类似的数据结构,用于组织和存储区块链中的交易信息,且主要存放在每个区块的块身中。在 Merkle Tree 中的每个叶节点对应一个交易数据块,其他节点用于存储左右子节点的块哈希值。

Merkle Tree 与 Binary Tree 相似,但是存在一定的区别:

(1)Merkle Tree 用哈希指针代替了普通指针

(2)Merkle Tree 可以高效验证某笔交易写入了区块链

在区块链的系统中,可以将网络中的节点分为全节点和轻节点,全节点存放了区块链的完整数据信息(既保留了区块的块头又保留了完整的块身),轻节点如 BTC 钱包等应用只存放了区块的部分数据信息(仅保留了区块的块头)。如果与某一轻节点之间进行交易,且需要向该轻节点证明某个交易是写入区块链了,则这时可以使用上 Merkle Tree 这一数据结构的 merkle proof。

merkle proof 的验证过程是这样的,假设待验证交易是颜色为黄色的 tx 块(如上图),则轻节点可以在本地计算出指向该 tx 的 H()(图中最下层的绿色 H()),并向网络中其他全节点请求验证需要的其他 H()(图中所有的红色 H()),之后,利用请求得到的红色 H() 和指向 tx 的 H(),从叶子节点一路向根节点方向计算块哈希(除指向 tx 的 H() 外的其他绿色 H()),当达到最顶层时,利用最顶层的两个 H()(图中最顶层中一红一绿的 H())计算出 root hash,最后将计算得到的 root hash 与区块头中存储的 merkle root hash 比较,如果相同,则证明该交易已经写入区块链。

当然利用 Merkle Tree 结构也可以证明交易数据中没有包含某一交易块,这时需要全节点将完整的树结构发给轻节点,轻节点通过依次比对交易块哈希值进行验证,时间复杂度为 Θ ( n ) \Theta(n) Θ(n) 。另一种比较高效的方法是使用 Sorted Merkle Tree,即是交易的哈希值按大小排序的 Merkle Tree(需要排序),此时验证的时间复杂度是 Θ ( l o g ( n ) ) \Theta(log(n)) Θ(log(n))。然而,由于 BTC 中没有涉及这一验证需求,因此,BTC 中使用的是未经过排序的 Merkle Tree 数据结构。