哈希指针 Hash Pointers

除了存放结构体的地址外，还存放结构体的哈希值。
Block chain is a linked list using hash pointers

使用哈希指针的好处：区块链上任何一处的改动，都会导致最后的哈希值的改动。因此，我们只需要保存最后一个哈希值，就可以确定整条链上是否有改动。

默克尔树 Merkle Tree

Merkle Tree通常是一颗二叉树，也可以是多叉树。跟普通的树相比，merkle tree使用哈希指针替代普通指针。
Merkle Tree中，叶子节点为数据块，非叶子节点为哈希指针。

只要记住根哈希值，就可以检测出树上是否有更改。

比特币中，各个区块间使用哈希指针组织在一起，而每个区块内部，则使用merkle tree来记录多笔交易【每笔交易都是merkle tree的叶子节点】。每个区块分两部分：block header 和 block body。每个区块merkle tree的根哈希是存储在block header 中的，block body里面有交易信息。

Merkle Proof
假设某个轻节点【节点只存储block header，不存储block body】需要验证某个交易【黄色部分的tx】是否包含在某个Merkle tree中，则该轻节点向某个全节点【存储了block header和block body】发出Merkle Proof 请求，全节点返回Merkle Tree对应Path上的哈希值【蓝色框框部分】。结合全节点返回的哈希值，轻节点在本地向上计算出根节点哈希值【红色框框部分】，然后与本地保存的根哈希值作比较

Merkle Proof 时间复杂度： O(log(n))。
Merkle Proof只能证明某比交易是否存在于Merkle Tree中，不能证明某比交易不存在。