哈希指针
简介
除了结构体在内存中的位置以外，还保存着结构体的哈希值 H()
能够在找到结构体位置的同时，检查结构体的内容是否被篡改
只要是无环的数据结构，都可以使用哈希指针来代替普通指针。
若有环，会造成循环依赖的问题，无法确定块中的内容（哈希值不能确定）
在区块链中的应用
区块链与普通链表的不同之处之一在于，区块链中使用的指针是哈希指针
具体结构如下图：
H() 为前一块区块的整个内容以及区块中的hash point合在一起取的哈希
实现 tamper-evident log ：如果修改了其中某一块区块中的内容，将会使得后续的所有H()值均会发生变化，因此只需要记住最后的 H()，就可以得知链表中的内容是否发生变化
在默克尔树中的应用 Merkle Tree
简介
相比二叉树的不同：指针使用了哈希指针
同理，只要知道根哈希值，就可以知道树中的内容是否被修改过
比特币中各个区块之间用哈希指针连接起来，每个区块包含的交易组成一个默克尔树。data blocks中保存的是transaction交易（一个块就是一个交易，有且仅有一个）
block header中保存的是根哈希值，header中没有交易的具体内容，交易的列表保存在block body中
作用：Merkle Proof
比特币中的节点分类：
全节点full node(fully validation node)：保存所有信息（包括header和body）
轻节点light node：只保存block header
轻节点如何确认一笔交易：（向轻节点证明有一笔交易已经写入了区块中）
- 找到交易位置（黄色标注），向上直到root hash的节点路径即为merkle proof
- 轻节点向全节点发出请求，获取到图中红色标注的哈希值
- 本地计算绿色哈希值并和红色哈希值拼接起来，最终得到计算出的root hash值
- 轻节点把刚刚计算出来的根哈希值和自己保存的根哈希值进行对比，如果相同，就可以知道这笔交易写到了区块中
这种交易证明称作：proof of membership / proof of inclusion
对于轻节点来说，要验证一个merkle proof的正确，需要的时间复杂度为 $\theta(\log(n))$
要验证一个交易的错误(proof of non-membership)，如果全节点将整个树发送给轻节点让其在data blocks中逐个验证，需要的时间复杂度是 $\theta(n)$。
此时，可以对叶节点的排列顺序进行一些要求（如按照交易的哈希值进行排序）
- 如果发现了哈希值相同的交易，那么就用之前的方法使用merkle proof进行验证
- 如果没有发现相同的，则找到哈希值左右的两个交易，提供两个交易的merkle proof
- 证明左右两个交易的正确性后，则可以说明要找的交易并不在块中
这种排好序的叫做 sorted Merkle Tree
比特币中不需要进行不存在证明，不需要排序
