比特币的数据结构_realpanda_的博客-爱代码爱编程
普通指针与哈希指针
普通指针存储的是某个结构体在内存中的地址。假如P是指向一结构体的指针,那么P里面存放的就是该结构体在内存中的起始位置。
哈希指针除了要存地址之外,还要保存该结构体的哈希值H()。好处是:存了哈希值和地址的哈希指针,不仅可以找到该结构体的位置,同时还能够检测出该结构体的内容有没有被篡改,因为我们保存了它的哈希值。
普通链表和区块链
比特币中最基本的数据结构就是区块链,区块链就是一个一个区块组成的链表。他和普通链表有着如下的区别:
1.用哈希指针代替了普通指针(B block chain is a linked list using hash pointers)区块链第一个区块叫作创世纪块(genesis block) 最后一个区块叫最近产生的区块(most recent block) 。每一个区块都包含指向前一个区块的哈希指针,最后一个区块也有一个哈希指针保存在系统里。
这样做的好处是通过这种结构,可以实现tamper-evident log。如果有人改变了一个区块的内容,后面一个区块的哈希指针就对不上,因为后一个区块哈希指针是根据前一个区块的内容算出来的,所以后一个哈希指针也得改,以此类推,我们保留的是最后一个哈希值也会变化。
因此我们甚至只要记住最后一个哈希值,就可以检测出对去区块链中任何一个部位的是否有修改。
2.由此引出第二个区别,普通链表可以改变任意一个元素,对链表中其他元素是没有影响的。而区块链是牵一发而动全身,因为只需要保存最后一个哈希值,就可以判断区块链有没有改变,在哪里改变了。
因此比特币没有要保存所有区块的内容,可以只保留最近的几千个区块。如果要用到以前的区块,可以向系统中其他节点要这个区块。
有些节点是有恶意的,怎么判断?这里要用到哈希值一个性质,其他节点给你一个区块,如何判断它是正确的?算出它的哈希值,与相邻保存上一个节点的区块的哈希值对比,看他们是否相同即可。
二叉树和默克尔树(哈希树)
Merkle Tree 是什么?
答:比特币中的另外一个结构是:Merkle Tree。其中最下面一层是数据块(data blocks),上面几层的内部节点都是哈希指针(hash pointers),第一层是根节点,根节点的区块也可以取个哈希,叫根哈希(root hash)
这种结构的好处:只要记住根哈希值,就能检测出对树中任何部位的修改。
比特币当中各区块之间用哈希指针连接在一起,每个区块所包含的交易组织成一个merkle tree的形式,最下面一行data blocks每个区块实际上是一个交易。
每个区块分为两部分,分别是块头和块身(block header ,block body)。
块头里面有根哈希值,每个区块所包含的所有交易组成的merkle tree的根哈希值存在于区块的块头里面,但是,块头里没有交易的具体内容,只有一个根哈希值。
块身里面是有交易的列表的。
Merkle Tree 的主要作用
提供merkle proof
比特币中的节点分为两类:
全节点:保存整个区块的内容,即block header ,block body都有。
轻节点:例如手机上的比特币钱包,只有block header。
这时存在一个问题:如何向一个轻节点证明某个交易是写入区块链的?
答:这时需要用到merkle proof :找到交易所在的位置(最底行的其中一个区块),这时该区块一直往上到根节点的路径就叫merkle proof。
假设某个轻节点想知道图中黄色的交易,是否包含在了merkle tree里面(轻节点没有包含交易列表,没有这颗merkle tree的具体内容,只有一个根哈希值)。这时轻节点向一个全节点发出请求,请求证明黄色的交易被包含在这颗merkle tree里面的merkle proof。全节点收到这个请求之后,只需要将图中标为红色的这三个哈希值发给轻节点即可。有了这些哈希值之后,轻节点可以在本地计算出图中标为绿色三个哈希值。首先算出黄色交易的哈希值,即它正上方的那个绿的哈希值,然后跟旁边红色的哈希值拼接起来,可以算出上层节点绿色的哈希值。然后再拼接,再算出上层绿色哈希值,再拼接,就可以算出整棵树的根哈希值。轻节点把这个根哈希值和block header里的根哈希值比较一下是否相等,就能知道黄色的交易是否在这颗merkle tree里。
由于merkle proof可以证明merkle tree里面包含了某个交易,所以这种证明又叫proof of membership或者 proof of inclusion。
对于一个轻节点来说,验证一个merkle proof 复杂度是多少?
答:假设最底层有n个交易,则merkle proof 复杂程度是θ(log(n))。
如何证明merkle tree里面没有包含某个交易(proof of non-membership)?
答:可以把整棵树传给轻节点,轻节点收到后验证树的构造都是对的,每一层用到的哈希值都是正确的,说明树里只有这些叶节点,要找的交易不在里面,就证明了proof of non-membership。问题在于,它的复杂度是线性的θ(n),是比较笨的方法。
查找效率高一点的办法是如果对叶节点的排列顺序做一些要求,比如按照交易的哈希值排序。每一个叶节点都是一次交易,对交易的内容取一次哈希,按照哈希值从小到大排列。要查的交易先算出一个哈希值,看看如果它在里面该是哪个位置。比如说在第三个第四个之间,这时提供的proof是第三个第四个叶节点都要往上到根节点。如果其中哈希值都是正确的,最后根节点算出的哈希值也是没有被改过的,说明第三、四个节点在原来的merkle tree里面,确实是相邻的点。要找的交易如果存在的话,应该在这两个节点中间。但是它没有出现,所以就不存在。其复杂度也是log形式,代价是要排序。排好序的叫作sorted merkle tree。比特币中没有用到这种排好序的merkle tree,因为比特币中不需要做不存在证明。
总结
这节讲了比特币中两种最基本的结构:区块链和merkle tree,都是用哈希指针来构造的。除了这两种之外,哈希指针还能用另一个方面。只要一个数据结构是无环的(非循环链表),都能用哈希指针代替普通指针。有环的话存在一个问题,他们的哈希值没法计算,没法确定一个哈希值固定的区块,会出现循环依赖。