BTC数据结构

hash pointer(哈希指针)

在传统链表里，通过指针将各个节点串联起来。
指针指的是一个节点对象在内存中的首地址。

顾名思义，区块链也是一种链表结构，节点为区块。不过区块链并未采用指针，而是使用了哈希指针。
如下图所示，该节点有两个指针指向这个节点（实际上为一个），其中 p 为该节点的地址，H()为该节点的哈希值，该值与节点中内容有关。当节点（区块）中内容发生变化，该哈希值也会发生改变，从而保证了区块内容不能被篡改。

在比特币系统中，其最基本的数据结构便是一个个区块形成的区块链。

如图所示，每个区块根据自己的内容生成自己的哈希值，此外，每个区块（除创世纪块）都保存有前一个区块的哈希值。这保证了区块内容不被篡改。

如果我们篡改 A 的值，而 B 中保存有 A 的哈希值，所以 B 也得进行修改，同样 B 后的区块也得修改。
这就是区块链区别与普通链表的区别：普通链接修改节点不会影响其他节点，而区块链牵一发而动全身，后面的节点都得跟着改。

所以用户只需要保存最后一个区块的哈希值，就可以检测出区块链上内容是否被篡改过。

由于这个特性，那么对于个人节点而言，就不需要完整的保存链上的所有的节点内容，只需要保存常用的父级几千个节点即可。

merkle tree(默克尔树)

merkle tree 是比特币系统中一个重要的数据结构。区别于 binary tree，merkle tree 用哈希指针代替了普通指针。
一个简单的 merkle tree：

tree 中，A B C D 表是一个个交易(tx)，A 和 B 各有一个哈希值 H(1)和 H(2)，将其合并放在一个节点中，C 和 D 同理，然后针对得到的两个节点又可以得到新的哈希值，即为图中根节点。实际中，会对图中的根节点再取一次哈希，也就是 root hash。
该数据机构的优点在于：只需要记住 root hash，便可以检测出对树中任何部位的修改。

区块：
每个区块分为两部分，包括块头(block header)和块身(block body)。
block header 中存储的是 root hash，但是 block header 没有交易的具体内容，block body 里存储的是交易列表。

merkle tree 的实际用途：可以用于提供 merkle proof。

区块链中的节点分为轻节点和全节点。全节点保存整个区块的内容（block header 和 block body），而轻节点仅保存区块的块头信息（block header）。
那么就存在一个问题，轻节点想知道某个交易是否被写入到区块链上，该怎么办？打个比方，你向我转钱，我是个轻节点，我怎么知道这个交易已经被写到区块链里呢？

轻节点没有 block body，只有 root hash，那怎么证明某笔交易包含在这个 merkle tree 里呢？这就用到了 merkle proof。

merkle proof

从交易一直到根节点的路径，就属于 merkle proof。

有了 merkle proof，轻节点就可以算出 merkle tree 里是否包含某笔交易。

通过 merkle proof，可以验证计算得到的 root hash 是否与轻节点 block hader 里的 root hash 是否一致，如果一致说明该交易包含在 merkle tree 上。