【BTC】数据结构

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