比特币的数据结构

比特币有两种数据结构，一个是区块链，一个是Merkle Tree

传统意义上的指针，保存了所指向结构体在内存中的起始位置，而hash指针除了存地址之外，还要保存这个结构体的hash值，一般用H表示这hash指针，好处是不光知道这个结构体的地址，还可以知道这个结构体有没有发生改变。
比特币中最基本的数据结构就是区块链。区块链是什么，就是一个一个区块组成的链表，区块链和普通的链表有什么区别？一个区别就是hash指针代替了普通的指针。

每个区块包含一个前一个区块的hash指针，这个指针是对前一个区块整个信息进行hash出来的，包括前一个区块的hash指针，通过这种数据结构可以实现tamper-evident log（防篡改）。因为，一旦改了某个区块的信息，那么它后面的区块的hash指针就要变化，后面的区块的hash指针一变，后面的后面的hash指针也要跟着变，所以这个数据结构的好处是，只要我们保存最后一个hash指针，那么区块链上任意一个区块发生改变，我们都可以知道

比特币的另外一个结构是Merkle Tree，和二叉树类似，不过父节点保存的是左右孩子节点的hash指针

比特币当中是用hash指针将各个区块连接在一起，每个区块的交易是组织成一个Merkle tree 的形式，上图底下的数据块其实就是一个个交易。每个区块分为两部分，块头和块身。block header包含root hash，但是没有交易的具体内容，block body 有交易内容。

merkle tree 的作用

一个是merkle proof
比特币中的节点分为两类，一类是全节点，一类是轻节点，全节点保存整个区块的内容（即有block header和block body），轻节点只保存block header。轻节点不包含block body，但是交易信息是在block body里面的，那全节点如何向轻节点证明交易确实发生了呢？

假设某个轻节点想要知道黄色这个交易是不是包含在了这个merkle tree里面了，轻节点没有这颗merkle tree，只有一个根hash值，轻节点向某个全节点发出请求，请求一个能够证明黄色交易被包含在这个merkle tree里面的merkle proof ，全节点收到请求之后，只要把途中标为红色的这三个hash值发给这个轻节点就行，有了这三个hash值，轻节点可以在本地计算出图中标为绿色的hash值，首先算出黄色交易的hash值，即图中最下面的绿色的hash值，然后和右边的红色hash值组合计算出上一个绿色的hash值，同理可以算出整个树的根hash值，轻节点把这个hash值和block header里面的比较，就可以知道这个交易是不是在这个merkle tree里面。

这个是用merkle proof证明某个交易在merkle tree里面，那么如何证明某个交易不在merkle tree里面呢？

一种方法是把整个merkle tree发给别人，别人验证正确后，发现没有要找的交易，即交易不在merkle tree里面。
另外一种方法是对交易根据hash排个序，然后把要找的交易也hash一下，然后二分查找，如果找到了，merkle proof证明它确实在里面，不存在证明失败；如果没找到，对相邻的两个交易进行merkle proof，如果证明成功，说明它俩是紧邻的，也即我们要找的交易不在里面，因为如果在里面，它俩就不是紧邻的了，不存在证明成功。

数据 比特 数据结构 比特币