BTC 数据结构
# 一、哈希指针
普通指针存储的是某个结构体在内存中的地址。假如 P 是指向一结构体的指针，那么 P 里面存放的就是该结构体在内存中的起始位置。而哈希指针除了要存地址之外，还要保存该结构体的哈希值 H()。
使用哈希指针的好处是不仅可以找到该结构体的位置，同时还能够基于它的哈希值检测出该结构体的内容有没有被篡改。
# 二、区块链
比特币中最基本的结构就是区块链，区块链就是一个一个区块组成的链表。区块链和普通的链表相比有以下区别：
- 哈希指针代替普通指针。
- 牵一发而动全身。
下面来进行详细说明。
# 2.1 哈希指针代替普通指针
区块链使用哈希指针代替了普通指针（B block chain is a linked list using hash pointers）。
区块链第一个区块叫作创世纪块（genesis block），最后一个区块是最近产生的区块（most recent block），每一个区块都包含指向前一个区块的哈希指针，整体结构如下图所示。
一个区块哈希指针的计算，是把前面整个区块的内容，包括里面的哈希指针，合在一起取哈希值。
# 2.2 牵一发而动全身
普通链表可以改变任意一个元素，对链表中其他元素是没有影响的。而区块链是牵一发而动全身，因为只需要保存最后一个哈希值，就可以判断区块链有没有改变，在哪里改变了。
基于区块链的这种结构，可以实现 防篡改日志（tamper-evident log）。如果有人改变了一个区块的内容，后面一个区块的哈希指针就对不上，因为后一个区块哈希指针是根据前一个区块的内容算出来的，所以后一个哈希指针也得改，以此类推，我们系统中保留的是最后一个哈希值也会发生变化。所以 只需要保留最后一个区块的哈希指针，就可以检测整个区块链是否被篡改。
因此，某些节点没必要保存所有区块的内容，可以只保留最近的几千个区块。如果要用到以前的区块，可以向系统中其他节点要这个区块。但如果有些节点是有恶意的，要怎么判断？
这里要用到哈希指针的性质，只需要算出收到区块的哈希值，与保留的区块的哈希值对比即可。
# 三、Merkle Tree
# 3.1 Merkle Tree 的结构
Merkle Tree 的结构如下图所示。
其中最下面一层是数据块（data blocks），上面三层内部节点都是哈希指针（hash pointers），第一层是根节点，根节点的区块也可以取个哈希，叫根哈希（root hash）。
这种结构的好处：只要记住根哈希值，就能检测出对树中任何部位的修改。相比于区块链的检测效率更高。
比特币当中各区块之间用哈希指针连接在一起，每个区块所包含的交易组织成一个 Merkle Tree 的形式，最下面一行 data blocks 每个区块实际上是一个交易，每个区块分为两部分，分别是块头和块身（block header, block body)。
块头里面有根哈希值，每个区块所包含的所有交易组成的 Merkle Tree 的根哈希值存在于区块的块头里面，但是，块头里没有交易的具体内容，只有一个根哈希值，块身里面有交易的列表。
# 3.2 Merkle Tree 的作用
比特币中的节点分为两类：全节点（保存整个区块的内容，即块头块身都有，有交易的具体信息）和轻节点（只有块头，例如手机上的比特币钱包）。
这时存在一个问题：如何向一个轻节点证明某个交易是写入区块链的？
这时需要用到 merkle proof：找到交易所在的位置（最底行的其中一个区块），这时该区块一直往上到根节点的路径就叫 merkle proof。
如上图所示，最上面一行是小型的区块链，该图展现的是一个区块的 merkle tree，最下面一行是包含的交易。
假设某个轻节点想知道图中黄色的交易，是否包含在了 merkle tree 里面。该轻节点没有包含交易列表，没有这棵 merkle tree 的具体内容，只有一个根哈希值。
- 这时轻节点向一个全节点发出请求，请求证明黄色的交易被包含在这棵 merkle tree 里面的 merkle proof。
- 全节点收到这个请求之后，只需要将图中标为红色的这三个哈希值发给轻节点即可。
- 有了这些哈希值之后，轻节点可以在本地计算出图中标为绿色三个哈希值。
- 首先算出黄色交易的哈希值，即它正上方的那个绿的哈希值；
- 然后跟旁边红色的哈希值拼接起来，可以算出上层节点绿色的哈希值；
- 然后再拼接，再算出上层绿色哈希值；
- 再拼接，就可以算出整棵树的根哈希值。
- 轻节点把这个根哈希值和 block header 里的根哈希值比较一下，就能知道黄色的交易是否在这棵 merkle tree 里。
总结一下，全节点在 merkle proof 里提供的这几个哈希值，就是从黄色的交易所在的节点的位置到树根的路径上用到的这些哈希值。轻节点收到这样一个 merkle proof 之后，只要从下往上验证，沿途的哈希值都是正确的即可（验证时只能验证该路径的哈希值，其他路径是验证不了的，即该图中红色的哈希值是验证不了的）。
这样是否不安全呢？假如黄色交易被篡改，它的哈希值发生了变化，那能不能调整旁边红色的哈希值，使得它们拼接起来的哈希值是不变的呢？
这种操作相当于人为制造哈希碰撞，根据 抗碰撞性（collision resistance），在实际中这是不可行的。
merkle proof 可以证明 merkle tree 里面包含了某个交易，所以这种证明又叫 proof of membership 或 proof of inclusion。
对于一个轻节点来说，验证一个 merkle proof 复杂度是多少？
假设最底层有 n 个交易，则 merkle proof 复杂程度是 。
如何证明 merkle tree 里面没有包含某个交易，即 proof of non-membership？
可以把整棵树传给轻节点，轻节点收到后验证树的构造都是对的，每一层用到的哈希值都是正确的，说明树里只有这些叶节点，要找的交易不在里面，就证明了 proof of non-membership。问题在于，它的复杂度是 ，是比较笨的方法。
如果对叶节点的排列顺序做一些要求，比如按照交易的哈希值排序。
- 每一个叶节点都是一次交易，对交易的内容取一次哈希，按照哈希值从小到大排列。
- 要查的交易先算出一个哈希值，看看如果它在里面该是哪个位置。
- 比如说在第三个第四个之间，这时提供的 proof 是第三个第四个叶节点都要往上到根节点。
- 如果其中哈希值都是正确的，最后根节点算出的哈希值也是没有被改过的，说明第三、四个节点在原来的 merkle tree 里面，确实是相邻的点。要找的交易如果存在的话，应该在这两个节点中间。但是它没有出现，所以就不存在。其复杂度也是 ，代价是要排序。
排好序的 merkle tree 叫做 sorted merkle tree。比特币中没有用到这种排好序的 merkle tree，因为比特币中不需要做不存在证明。