比特币中的数据结构
1.区块链
这里要用到一个重要的概念叫做哈希指针。
hash pointers，哈希指针，除了要保存这个结构体的地址之外，还要保存这个结构的的哈希值（不仅可以知道这个结构体在内存中的位置，还可以知道这个结构体的内容有没有被篡改）
区块链相比较于普通的链表有何区别？
①用哈希指针替代了普通的指针
区块链示例
这样做的好处是
tamper-evident log：篡改-证明 日志，当有人篡改了区块链中某一个区块的某个内容，则它的下一个区块的哈希值就对不上了，以此类推，直到最后一个保存在系统中的哈希值也对不上了，这样我们只需要记住保存在系统中的那最后一个哈希值，就可以检测出对任意区块的修改。这也是区块链和普通链表的一个区别。（多米诺骨牌效应）
有了这个性质，系统中就不需要保存整条区块链的内容，比如它可以只保存最近的几千个区块，如果要用到以前的区块怎么办？
可以问系统中的其他节点，去要这个区块，有些节点可能是有恶意的（去中心化系统），那么如何知道别人给你的区块是不是正确的呢？就用到哈希指针的这个性质！别人给你的最后的那个区块，算一下哈希值，如果和系统中保存的与之对应的后一个区块的哈希值对比之后相同，则正确
2.Merkle tree(默克尔树)
和binary tree（二叉树）的区别是，用哈希指针代替了普通的指针
和链式结构一样，“牵一发而动全身”。
各个区块由哈希指针连接在一起的，每个区块所包含的交易，是组织成一个Merkle tree的形式，最底层的数据块实际上是某个交易。
每个区块都是由block header和block body组成，block header 保存这个Merkle tree 的根哈希值，不保存这个区块的交易信息，而block body保存交易信息
Merkle tree的作用？
①提供Merkle proof
比特币中的结点分为两类，一类时全节点，还有一类是轻结点
全节点：保存整个区块的内容，block header和block body都有
轻结点：比如手机上的比特币钱包的应用就属于轻结点，只有一个block header
这样就带来一个问题，如果你想向一个轻结点证明某个交易是写入到了区块链中的 ，该怎么证明？
比如我想买你的东西，我就需要向你转钱，我对你说，我对你转钱的交易，已经写到了区块链中了，支付已经完成了，
那么你怎么知道，这个交易已经被写入区块链里了呢？这里就需要用到Merkle proof
一个轻结点，向某个全节点发出请求，请求一个能够证明黄色结点这个交易，被包含在这棵Merkle tree里面的Merkle proof
最后算出的根哈希值，和block header中存储的root hash比较，就可以证明出tx是否在区块链中
这种证明也叫做：
proof of membership
或
proof of inclusion
如果最底下有n个交易：时间复杂度为O(log(n))
那么可不可以证明，区块链中没有某个交易？也就是proof of non-membership
有一种比较笨的方法，就是把这一整颗Merkle tree都传给轻结点，如果hash值都正确，如果某个交易不在叶结点中，则证明了proof of non-membership，时间复杂度为O(n)，有没有比较高效的方法证明不存在？
如果我们对叶结点的排列顺序不了解，那么是没有办法证明交易不在里面的
如果我们对叶结点的排列顺序做一些要求：对每个交易取哈希值，按照这个哈希值从小到大排序，这个时候是有一个好的证明方法的：但是代价是需要排序
sorted Merkle tree：排好序的Merkle tree
比特币中没有这种排好序的Merkle tree，因为比特币中根本不需要作这种不存在证明，没有硬性需求，所以比特币中的Merkle tree 不要求排序
3.总结
比特币中的两种数据结构：区块链和Merkle tree
除了这两种数据结构，哈希指针还用在什么地方？
只要这个数据结构是无环的，都可以用哈希指针来代替普通指针，有环会带来一定的问题
会出现循环依赖的问题，定不下来任何一个区块，找不到创世纪块