Hash pointers(哈希指针)
普通的指针存储的是某个结构体在内存中的地址。
比如：
如下图所示的结构体，P是指向它的一个指针，那么P里面存放的是这个结构体在内存中的起始位置，哈希指针除了要存地址之外，还要保存这个结构体的哈希值， 该值与节点中内容有关。当节点（区块）中内容发生改变，该哈希值也会发生改变，从而保证了区块内容不会被篡改。
如下图是一个小型的区块链：
最前面的区块是系统中产生的第一个区块，叫做创世纪块(genesis block)；
最后的区块是最近产生的区块(most recent block)；
每个区块都包含指向前一个区块的哈希指针 ，最后一个区块有一个hash point保存在系统里。
这种数据结构的好处：
可以实现tamper-evident log(篡改证明记录)
比如：
如果我们想要破坏区块链完整性。篡改B的内容，但是C中保存有B的哈希值，所以C也得进行修改。而同样C后面的区块也得修改。而用户只需要记住最后一个区块链的哈希地址，就可以检测区块链上的内容是否被篡改
有了这个性质，比特币中有一些节点就不一定要保存整条区块链上的内容，可以只保存最近的几千个区块，如果需要以前的区块，再向系统中的其他节点要。
Merkle Tree(默克尔树)
如下图：
最下面的一层是data block(数据块)
上面的内部节点都是hash point(哈希指针)
该数据结构的优点：
只需要记住root hash（根哈希值），便可以检测出对树中任何部位的修改。
例如:
Merkle Tree中最下面的节点发生了改变，则对应上一层的节点中的哈希值便也会发生改变，进而根节点中的哈希值也会发生改变，从而导致根哈希值也发生了改变。
比特币当中各个区块之间用哈希指针连接在一起，每个区块所包含的交易是组织成一个Merkle Tree的形状。
图中每一个数据块实际上是一个交易，每个区块分为两部分：块头(block header) 和 块身(block body)。
块头(block header)里面有根哈希值(root hash)，就是说在这个区块里面所包含的所有交易组成的Merkle Tree的根哈希值是存在这个区块的块头里的，但是k块头里没有交易的具体内容，只有一个根哈希值。
块身(block body)里面是有交易的列表的。
Maerkle Tree有什么用呢？
Merkle Tree可以提供Merkle Proof。
比特币中的节点分为轻节点和全节点。
全节点保存整个区块的所有内容(block header 、block body都有)，有交易的具体信息；
轻节点（比如像手机里比特币钱包应用），仅仅保存区块的块头信息。
为什么要分轻节点和全节点？
因为硬件的局限。一个区块大小为1MB，对于移动便携设备来说，如果存储区块的所有内容，则所需空间过大，而这是不现实的。所以轻节点只需要存储区块块头信息，全节点存储区块所有内容即可。
这带来一个问题：如果需要向一个轻节点证明某个交易是写入到区块链，该怎么证明？(比如你找我买东西，给我转一笔钱，你告诉我转的钱已经写入到区块链网络里了，但我是个轻节点，我只能在手机里查一查，我怎么知道这个交易是不是已经写到区块链里面了呢？)
这就需要用到Merkle proof，找到这个交易所在的位置，然后从这个交易往上，一直到根节点这条路径就是Merkle proof，如下图所有黄色节点路径。
如下图完整Merkle proof 示意图
最上面这一行是一个小型的区块链，我们把其中一个区块的Merkle Tree展现出来了，最下面这一行包含的是交易。
假设某个轻节点想要知道黄色这个交易是不是被包含在了这棵Merkle Tree里面，这个轻节点向某个全节点发出请求，请求一个可以证明黄色这个交易被包含在这棵Merkle Tree里的Merkle Proof，全节点收到这个请求后，只要把图中标为红色的哈希值发给轻节点就可以了。有了这些哈希值后，轻节点在本地计算出根哈希值，并且和自己保存的对比，从而验证该交易是否被写入区块链。只要沿着该路径，所有哈希值都正确，说明内容没有被修改过。
问题：会不会存在不安全的情况？如下图我们要验证B，但是H(1)和H(4)都是全节点提供的。全节点可否修改B，通过H(1)调整，使得修改过后的H(1)和轻节点计算出的H(2)一起取得哈希仍然为H(3)？
实际上，这种情况为人为制造哈希碰撞。由于哈希函数的collision resistance性质，这种情况是不会发生的，保证了系统的不可篡改性。同时，这样一个Markle Proof的事件复杂度为O(log n),非常高效。
如果要证明交易不存在，如果不对叶节点进行排序，没有一个效率较高的方法证明不存在。
在比特币系统中，没有相应的需求，所以在比特币系统中并没有对Markle Tree进行排序。
