哈希指针

普通指针存储的是某个结构体在内存中的地址。假如P是指向一结构体的指针，那么P里面存放的就是该结构体在内存中的起始位置。

哈希指针除了要存地址之外，还要保存该结构体的哈希值H()。好处是：哈希指针不仅可以找到该结构体的位置，同时还能够检测出该结构体的内容有没有被篡改。如果结构体的内容被篡改过，根据collision resistance性质，哈希值就会改变；只需要与我们保存的哈希值比对即可。

除了环状结构，任何出现普通指针的地方，我们都可以用哈希指针代替。

区块链

比特币中最基本的结构就是区块链，区块链就是一个一个区块组成的链表。区块链和普通的链表相比有什么区别：

  • 用哈希指针代替了普通指针 (block chain is a linked list using hash pointers)

区块链第一个区块叫作创世纪块(genesis block)；最后一个区块是最近产生的区块(most recent block)。每一个区块都包含指向前一个区块的哈希指针。

一个区块的哈希指针怎么算？它是把前面整个区块的内容，包括里面的hash pointer ，合在一起取哈希值。通过这种结构，可以实现tamper-evident log。如果有人改变了一个区块的内容，后面一个区块的哈希指针就对不上，因为后一个区块哈希指针是根据前一个区块的内容算出来的，所以后一个哈希指针也得改，以此类推，我们保留的是最后一个哈希值也会变化。

  • 普通链表可以改变任意一个元素，对链表中其他元素是没有影响的。区块链是牵一发而动全身。只需要保存最后一个哈希值，就可以判断区块链有没有改变。

因此比特币没有要保存所有区块的内容，可以只保留最近的几千个区块。如果要用到以前的区块，可以向系统中其他节点要这个区块。我们也很容易判断这个区块是不是被篡改过。

Merkle tree

比特币中的另外一个结构是：Merkle tree。(其中最下面一层是数据块(data blocks)，上面三层内部节点都是哈希指针(hash pointers)，第一层是根节点，根节点的区块也取哈希，叫根哈希(root hash)。Merkle tree的结构类似于binary tree，只不过它用哈希指针代替了普通指针。和区块链类似，只要记住根哈希值，就能检测出对 Merkle tree中任何部位的修改。

比特币当中各区块之间用哈希指针连接在一起，每个区块所包含的交易组织成一个Merkle tree的形式，最下面一行data blocks对应的是交易。

每个区块分为两部分，分别是块头和块身(block header, block body)。块头里面有根哈希值，但它没有交易的具体内容，只有一个根哈希值。包含完整交易内容的Merkle tree储存在块身。

Merkle proof : proof of membership

比特币中的节点分为两类：全节点(保存整个区块的内容，即块头块身都有，有交易的具体信息)和轻节点(它只有块头，例如手机上的比特币钱包)。这时存在一个问题：如何向一个轻节点证明某个交易是写入区块链的？

这时需要用到Merkle proof：找到交易所在的位置(最底行的其中一个区块)，这时该区块一直往上到根节点的路径就叫Merkle proof。

最上面一行是一系列区块链，该图展现的是一个区块的Merkle tree，最下面一行是该区块包含的交易。假设某个轻节点想知道图中黄色的交易是否包含在Merkle tree里面。该轻节点没有包含交易列表，没有这棵Merkle tree的具体内容，只有一个根哈希值。这时轻节点向一个全节点（通常是付款给我们的人）发出请求，请求证明黄色的交易被包含在这棵Merkle tree里面，这个证明叫做Merkle proof。全节点收到这个请求之后，只需要将图中标为红色的这三个哈希值发给轻节点即可。有了这些哈希值之后，轻节点可以在本地计算出图中标为绿色三个哈希值。首先算出黄色的交易的哈希值，即它正上方的那个绿的哈希值，然后跟旁边红色的哈希值拼接起来，可以算出上层节点绿色的哈希值。然后再拼接，再算出上层绿色哈希值；再拼接，就可以算出整棵树的根哈希值。轻节点把这个根哈希值和block header里自己储存的根哈希值比较一下，就能知道黄色的交易是否在这棵Merkle tree里。

全节点在Merkle proof里提供的这几个哈希值，就是从黄色的交易所在的节点的位置到树根的路径上用到的这些哈希值。轻节点收到这样一个Merkle proof之后，只要从下往上验证，沿途的哈希值都是正确的即可。(验证时只能验证该路径的哈希值，其他路径是验证不了的，即该图中红色的哈希值是验证不了的)

Merkle proof 的有效性：假如黄色交易被篡改，它的哈希值发生了变化，那能不能调整旁边红色的哈希值，使得它们拼接起来的哈希值是不变的呢?不行，根据collision resistance的性质，这是不可行的。

Merkle proof 可以证明Merkle tree里面包含了某个交易，所以这种证明又叫proof of membership或 proof of inclusion。对于一个轻节点来说，验证一个Merkle proof 复杂度是多少?假设区块中有n个交易，则验证Merkle proof 复杂程度是O(log(n))。

proof of non-membership

那么如何证明Merkle tree里面没有包含某个交易?即proof of non-membership。可以把整棵树传给轻节点，轻节点用O(n)的复杂度验证，是比较笨的方法。

如果对叶节点的排列顺序做一些要求，比如按照交易的哈希值排序，根据要查的交易内容先算出一个哈希值，看看如果它在里面，应该在哪个位置。比如说在第三个第四个之间。这时，需要提供第三、第四个叶节点在Merkle tree中的proof of membership。如果得证，说明第三、四个节点在原来的Merkle tree里面，确实是相邻的点。要找的交易如果存在的话，应该在这两个节点中间。但是它没有出现，所以就不存在。

这样，proof of non-membership的复杂度也是log(n)形式，代价是要排序。排好序的叫作Sorted Merkle tree。比特币中没有用到这种排好序的Merkle tree，因为比特币中不需要做proof of non-membership。