比特币中用到的数据结构

哈希指针

哈希指针（hash pointers）：普通的指针是存储内存中的一个结构体起始位置，哈希指针除了要指向这个地址外，还要保存这个结构体的哈希值。这样除了可以通过该指针得到这个结构体的位置，同时还可以用哈希值检测这个结构体的内容是否被篡改。

区块链

区块链（block chain）就是一个一个区块组成的链表。

区块链和普通链表的区别：用哈希指针代替了普通指针。

Block chain is a linked list using hash pointers.

最前面的区块叫做“创世纪块”（genesis block），最近的区块叫做most recent block。每个区块都包含指向前一个区块的哈希指针，最后一个区块的哈希指针保存在系统里。后一个区块的哈希指针的值是前一个区块的整个内容（包括前一个区块中保存的前前一个区块的哈希指针）取哈希。

通过这样来实现 tamper-evident log。这样做的好处就是，只要记住保存在系统里的最后一个区块的哈希，就可以检测出整个区块链中任何一个区块的修改。

普通链表中间的节点内容可以进行修改，但是区块链如果修改了其中某个节点，就会导致后一个区块的哈希指针对应不上（“牵一发而动全身”），就需要继续修改后面所有的区块内容。只要在系统中保存最后一个区块的哈希，就可以知道区块链内容是否被修改。

因为有了区块链，比特币不需要每个电脑节点都保存完整的区块链内容，只需要保存最近的几千个区块即可，需要用到前面的区块时，可以找其他节点要这些区块。因为自己保存的最近的区块中带有前一个区块的哈希指针，就可以避免从一些恶意节点中要到被篡改的区块。

Merkle tree

merkle tree（默克尔树） 和 binary tree（二叉树）的区别：用哈希指针代替了普通指针。

其中：最下面一层为数据节点 Data Node，除去最下面一层数据节点外，其他都是哈希指针节点。每个哈希指针节点会存放下面两个子节点的哈希值。最上层的节点称为根节点，对根节点也可以取一个哈希，称为根哈希值 root hash。只要记下来根哈希值，就能检测出树中任何节点的修改。

比特币中，每个区块以区块链的结构组织在一起。每个区块中的交易，是Merkle tree的形式，即Merkle tree最底层的每个Data Node都是记录了一个交易transaction。

每个区块分为两部分：块头（block header）和块身（block body）。在block header中，保存有该区块所有交易组成的merkle tree的根哈希值，而交易的具体内容保存在 block body中。

Merkle tree 可以提供 Merkle proof。

比特币的区块保存分为全节点和轻节点，全节点保存有完整的 block header 和 block body。而像手机比特币钱包之类的是以轻节点形式保存，只保存有 block header。

假如A向B进行了一次转账交易，而只有手机比特币钱包里的轻节点，便可以通过 Merkle proof查看该交易是否被记录到区块链中，A经过如下图所示的流程得到一个Merkle proof，向B提供证明：

具体流程：

● 图中蓝色块表示用户手机区块链钱包中存储的轻节点区块链，橙色为记录本次交易的区块的根哈希值，淡蓝色为本节点记录的交易的merkle tree（轻节点没有block body，也就没有该merkle tree，需要通过请求全节点来获取相关数据）

● 轻节点信息的block header中存储的有根哈希值。但是轻节点中没有block body，无法通过block body存储的完整交易列表来验证该笔交易是否保存进块中

● 轻节点向区块链全节点发送请求，请求获取途中红色的哈希值

● 用户有本次交易的信息，以及全节点返回的红色的哈希值之后，可以通过本地计算出图中绿色的哈希值

● 轻节点可以通过merkle tree来验证本笔交易是否写入了区块链中：用户本地计算出本次交易tx的哈希值，然后请求全节点获取该交易旁边的交易的哈希值，然后将这两个哈希值合并再算一次哈希，再向全节点请求旁边节点的哈希....最终算出根节点哈希，和轻节点存储的根哈希做对比

这种证明方式称为：proof of membership ，也称 proof of inclusion，证明该树中包含该交易。复杂度是该merkle tree叶子节点个数的对数 log(n)。

如果需要证明一个交易不在该merkle tree中（即证明 proof of non-membership），就需要得到整个树，然后进行计算验证，这个复杂度就是线性的，即复杂度为 n。但是如果我们对这些叶子节点的顺序做了排列，例如对该树的所有交易按哈希值从小到大排序，这样证明时，只需对需要验证的交易做哈希，然后获取该交易应该出现的位置的前后两个交易，验证这前后两个交易的merkle proof是正确的，那么说明这前后两个交易确实是相邻节点，确实不存在中间的交易。这种排好序的树称为 Sorted Merkle Tree，验证不存在比较容易，但是代价是需要进行排序。比特币中并没有使用排序，因为比特币中不需要做这种不存在交易的证明。

哈希指针的其他用途

一般情况下，只要是无环的数据结构，都可以使用哈希指针。

如果数据结构是有环的，那么就可能会有一些问题。因为每个区块要保存前一个区块的哈希值，而因为数据结构有环，就会出现循环依赖，最终哪个区块都无法确定。