1.2 哈希指针及数据结构

哈希指针是一个指向数据存储位置及其位置数据的哈希值的指针。

（图 哈希指针）

_{注：哈希指针是一个不但可以指向数据存储的位置，还可以明晰某个时间戳下该数据的哈希值的指针。}

区块链

（图 数据结构）

防篡改日志

如果修改了区块链中的任意部位的数据，那么将会导致下一个数据块的哈希指针不正确。

如果对手想要篡改区块链中任意地方的数据，为了保证整个内容一致，他需要篡改所有的哈希指针直至最开始的地方。他最终将碰到障碍，因为他不能篡改链表头部的指针。仅通过记住一个哈希指针，我们就基本记住了整个链表的防篡改哈希值

链表头部的哈希指针被称作创世区块（genesis block）。

 

梅克尔树

使用哈希指针的二叉树也叫作梅克尔树 (Merkle trees)。

（图 merkel tree）

_{在梅克尔树的数据结构中，所有的数据区块都被两两分组，指向这些数据区块的指针被存储在上一层的父节点（parent node）中，而这些父节点再次被两两分组，并且指向父节点的指针被存储在上一层的父节点中，一直持续这个过程，直到最后我们到达树的根节点。}

我们要记住树最前面的哈希指针。我们现在可以通过哈希指针回溯到列表中的任何位置，这让我们能保证数据确实未经篡改。如果对手篡改了树底部的一些数据区块，会导致上一层的哈希指针不匹配，即使他继续篡改这个区块，改动数据行为将最终传递到树的顶端。因此，通过记住顶部的哈希指针，任何企图篡改任何数据的行为都会被检测到。

 

隶属证明

梅克尔树可以实现简洁的隶属证明。

（图 隶属证明）

为了证明某个数据区块来自一个梅克尔树，我们只需要找到该数据区块到树根节点的路径。

如果整棵树上有n个节点，只需要展示约log(n)个项目，因为每个步骤仅需要计算子区块的哈希值，验证过程需要时间约为log(n)。验证的时间与空间花费鱼log(n)同级。

 

排序梅克尔树

一个排序梅克尔树是把底层的数据通过某些排序得到的梅克尔树，这里排序规则可以是字母表排序、词典排序、数字化排序，或者其他约定的排序方式。

 

非隶属证明

通过排序梅克尔树，我们可以在一个对数复杂度log(n)的条件下验证某一个数据区块并非来自某梅克尔树。

展示被验证区块之前的区块路径，和被验证区块之后的区块路径，如果之前、之后两个区块在树上是连续的，那么这说明了被验证区块与该梅克尔树之间是非隶属关系。

 

除了链表和二叉树，我们可以在任何以指针为基础的数据结构中使用哈希指针，条件是数据结构不存在循环。因为在一个有循环结构的网络中，并没有一个根节点，可以让我们去追溯。