比特币数据结构

比特币作为一种基于区块链技术的加密货币,使用了多种数据结构来支持其运作。其中最主要的数据结构包括交易(Transaction)、哈希指针(hash pointers),区块(Block)和 Merkle 树(Merkle Tree)。

欧易
欧易(OKX)

全球三大交易所之一,注册领50U数币盲盒,币圈常用的交易平台!

币安
币安(Binance)

币安交易所是世界领先的数字货币交易平台,注册领100U。



哈希指针

哈希指针(hash pointers):普通的指针是存储内存中的一个结构体起始位置,哈希指针除了要指向这个地址外,还要保存这个结构体的哈希值。这样除了可以通过该指针得到这个结构体的位置,同时还可以用哈希值检测这个结构体的内容是否被篡改。

区块链

比特币数据结构

区块链(block chain)就是一个一个区块组成的链表。

区块链和普通链表的区别:用哈希指针代替了普通指针。

最前面的区块叫做“创世纪块”(genesis block),最近的区块叫做most recent block。每个区块都包含指向前一个区块的哈希指针,最后一个区块的哈希指针保存在系统里。后一个区块的哈希指针的值是前一个区块的整个内容(包括前一个区块中保存的前前一个区块的哈希指针)取哈希。通过这样来实现tamper-evident log。这样做的好处就是,只要记住保存在系统里的最后一个区块的哈希,就可以检测出整个区块链中任何一个区块的修改。

普通链表中间的节点内容可以进行修改,但是区块链如果修改了其中某个节点,就会导致后一个区块的哈希指针对应不上,就需要继续修改后面所有的区块内容。只要在系统中保存最后一个区块的哈希,就可以知道区块链内容是否被修改。

因为有了区块链,比特币不需要每个电脑节点都保存完整的区块链内容,只需要保存最近的一一些区块即可,需要用到前面的区块时,可以找其他节点要这些区块。因为自己保存的最近的区块中带有前一个区块的哈希指针,就可以避免从一些恶意节点中要到被篡改的区块。

Merkle tree

merkle tree(默克尔树)和binary tree(二叉树)的区别:用哈希指针代替了普通指针。

比特币数据结构

其中:最下面一层为数据节点Data Node,除去最下面一层数据节点外,其他都是哈希指针节点。每个哈希指针节点会存放下面两个子节点的哈希值。最上层的节点称为根节点,对根节点也可以取一个哈希,称为根哈希值root hash。只要记下来根哈希值,就能检测出树中任何节点的修改。

比特币中,每个区块以区块链的结构组织在一起。每个区块中的交易,是Merkle tree的形式,即Merkle tree最底层的每个Data Node都是记录了一个交易transaction。

每个区块分为两部分:块头(block header)和块身(block body)。在block header中,保存有该区块所有交易组成的merkle tree的根哈希值,而交易的具体内容保存在block body中。

Merkle tree可以提供Merkle proof。

比特币的区块保存分为全节点和轻节点,全节点保存有完整的block header和block body。而像手机比特币钱包之类的是以轻节点形式保存,只保存有block header。

假如A向B进行了一次转账交易,而只有手机比特币钱包里的轻节点,便可以通过Merkle proof查看该交易是否被记录到区块链中,A经过如下图所示的流程得到一个Merkle proof,向B提供证明:

比特币数据结构

具体流程:

●图中蓝色块表示用户手机区块链钱包中存储的轻节点区块链,橙色为记录本次交易的区块的根哈希值,淡蓝色为本节点记录的交易的merkle tree(轻节点没有block body,也就没有该merkle tree,需要通过请求全节点来获取相关数据)

●轻节点信息的block header中存储的有根哈希值。但是轻节点中没有block body,无法通过block body存储的完整交易列表来验证该笔交易是否保存进块中

●轻节点向区块链全节点发送请求,请求获取途中红色的哈希值

●用户有本次交易的信息,以及全节点返回的红色的哈希值之后,可以通过本地计算出图中绿色的哈希值

●轻节点可以通过merkle tree来验证本笔交易是否写入了区块链中:用户本地计算出本次交易tx的哈希值,然后请求全节点获取该交易旁边的交易的哈希值,然后将这两个哈希值合并再算一次哈希,再向全节点请求旁边节点的哈希….最终算出根节点哈希,和轻节点存储的根哈希做对比

这种证明方式称为:proof of membership,也称proof of inclusion,证明该树中包含该交易。复杂度是该merkle tree叶子节点个数的对数log(n)。

如果需要证明一个交易不在该merkle tree中(即证明proof of non-membership),就需要得到整个树,然后进行计算验证,这个复杂度就是线性的,即复杂度为n。但是如果我们对这些叶子节点的顺序做了排列,例如对该树的所有交易按哈希值从小到大排序,这样证明时,只需对需要验证的交易做哈希,然后获取该交易应该出现的位置的前后两个交易,验证这前后两个交易的merkle proof是正确的,那么说明这前后两个交易确实是相邻节点,确实不存在中间的交易。这种排好序的树称为Sorted Merkle Tree,验证不存在比较容易,但是代价是需要进行排序。比特币中并没有使用排序,因为比特币中不需要做这种不存在交易的证明。

哈希指针的其他用途

哈希指针在数据结构中扮演着非常重要的角色。对于无环的数据结构来说,哈希指针是一个非常有效的方法,因为每个区块都可以轻松地指向前一个区块的哈希值,保证数据的一致性和完整性。然而,一旦数据结构中存在环,问题就会变得复杂起来。

当数据结构存在环时,每个区块需要保存前一个区块的哈希值,但由于循环依赖的存在,会导致无法确定哪个区块是第一个区块,从而破坏了数据的准确性。这种情况下,使用哈希指针可能会导致数据结构的混乱和不一致性。举个例子来说明这个问题:假设有一个循环链表,每个节点都包含一个指向前一个节点的哈希指针。当我们试图遍历这个链表时,由于循环的存在,可能会陷入无限循环,或者无法准确确定起点和终点,从而导致程序无法正常运行。

为了解决这个问题,我们可以考虑使用其他数据结构来处理有环的情况,比如使用额外的标记或者指针来标记已经访问过的节点,避免重复访问,或者采用其他算法来处理循环依赖的情况。另外,也可以考虑对数据结构进行一定的改动,使其变为无环结构,从而避免出现循环依赖的情况。

© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...