---

hash pointers

比特币中的数据结构里用到的重要概念是哈希指针hash pointers

普通的指针指存储的是某个结构体在内存中的位置。

p是指向某结构体的指针，那么p里面存放的就是该结构体在内存中的起始位置。
哈希指针除了要存地址之外，还要保存这个结构体的哈希值 H() 。

这样做的好处是，这个指针不但能够有这个结构体的位置信息，还能够验证这个结构体里面的内容有没有被篡改，因为我们保存了它的哈希值。

比特币中一个最基本的数据结构就是区块链，区块链是什么呢，就是一个一个区块组成的链表。

Block chain is a linked list using hash pointers

区块链和普通链表的区别是什么呢？

一个区别就是用哈希指针代替了普通指针。

最前面的区块是第一个区块，创世纪区块genesis block，最近一个区块是最近产生的区块 most recent block。每一个区块前面都有一个hash pointer。

这种数据结构的好处是什么？

是整个区块一起取哈希。我们通过这样的数据结构可以实现tamper-evident log 防篡改日志。

比如说有一个人篡改了区块链中的某一个内容，会有怎样的结果？

篡改内容的后面一个哈希指针就对不上，后面一个哈希指针改了，在后面的也要改。所以我只要保存最后一个哈希值，我就能保证前面的所有数据都没有被篡改。

普通链表我们可以改变其中一个元素而不会对其他区块有影响。区块链是牵一发动全身，我只要保存最后一个哈希值，就能保证整条区块链是完整的。我们只需要保存最近的几千个区块数据就行了，不需要保存整条区块，用到的时候问别人要就行了。

有些节点可能是恶意的，所以我们要验证，我们算一下别人给我们的区块的哈希值跟我们保存的哈希值是否相等就可以了。

---

Merkle tree

比特币中的另外一个数据结构是Merkle tree。大家可能没有听说过Merkle tree ，但是听说过binary tree。这两者有什么区别呢？

• List item

一个区别就是用哈希指针代替了普通指针。

这就是一棵merkle tree
最下面的一层是data blocks
上面的都是哈希指针

两两结合取哈希，一层层推上去，最后根节点也取哈希叫做根哈希值root hash

只要记住对根节点取哈希的哈希值，整个结构的数值都能保护。

比特币中各个区块之间用哈希指针连接在一起，每个区块所包含的交易组织成Merkle tree的形式。底层的这个data blocks的每个块其实是个交易tx （transaction）。

每个区块可以分为两部分，块头和块身。

block header

• root hash 是存在这个块头里面的

block body

• 交易列表

Merkle tree 有什么用呢？
提供Merkle proof

比特币中的节点有两种，一个是全节点，一个是轻节点。
比如说手机上的比特币钱包就是轻节点，它只保存block header。那么轻节点怎么知道交易是否被存到区块链中了呢？这时候就要用到Merkle proof。
从交易节点追溯到根节点，这条就叫做Merkle proof。

假设轻节点想知道黄色这个交易tx是否被包含在merkle tree中，怎么做呢？
首先绿的哈希值跟红色哈希值拼接，算出上一层绿色的哈希值，再跟红色哈希值拼接，以此类推，算出根哈希值，全节点把这个哈希值跟根节点的哈希值进行比较就可以证明。

轻节点只要从下往上验证，只要沿途的哈希值都是正确的就行了。轻节点只有block header，查的时候只能差交易这一条链上的哈希值，只需要验证有数据的部分的哈希值即可。

这个证明过程是否有一点不太安全？

因为我们验证的过程只能验交易所在的链条，这其实给修改提供了一定的*度。

这里面就用到了collision resistance性质。修改交易内容其实就是在人为做哈希碰撞。

这种证明也叫做 proof of membership,或者叫 proof of inclusion

对于轻节点来说，你发给我一个merkle proof，我要验证他，时间复杂度是多少？

那么proof of non-memberships 的时间复杂度是多少？

是线性的时间复杂度。

我们想找的这个交易可能出现在叶节点的任何位置。但是如果我们对这个叶节点的内容取哈希值，按照哈希值的大小从小到大排序，这时候就有一个好的排序方法，我要查的交易先算出哈希值，然后就找这个哈希值在叶节点中的位置，把相邻的两个叶节点都算进去，这样向上所有的哈希值都是正确的就一定能保证交易在原来的merkle tree 中。

这种排好序的叫做sorted Merkle tree。比特币中并没有用到这种排序的merkle tree，因为比特币中不需要进行不存在证明，没有这种硬性需求。

---

除了这两种结构之外，哈希指针还能用在什么地方呢？

• 只要是无环的结构，都可以用哈希指针来代替普通指针。

那么有环的结构会有什么问题呢？

• 形成循环依赖了。
• 
  所以有环的不行，没环的都能够使用哈希指针。