BTC 中对交易数据的存储主要涉及到了两种数据结构,一种是区块链,一种是 Merkle Tree。这两种数据结构组成了 BTC 中完整的区块链结构(如下图所示),共同完成对数据的存储和验证,确保交易的有效性。
一、区块链
所谓的区块链是由一个个区块构成的链,其中,每一个区块包括两个部分,分别是块头(block header)和块身(block body),块头中包含了指向前一个区块的哈希值、指向块身中 Merkle Tree 的 merkle root hash,时间戳等信息,块身中包含了交易数据列表。
区块链与普通链表相似,但是存在一定的区别:
(1)区块链用哈希指针代替了普通指针
(2)区块链具有防篡改、易验证的性质
区块链这种数据结构具有防篡改(tamper-evident log)的性质,这与普通链表是不同的。当对普通链表中的任意元素进行修改时,对其他元素是没有影响的,而区块链是牵一发而动全身的,由于每个区块都保留了由前一区块计算得到的哈希指针,因此,改变前面的任意一个区块,都会导致后面区块的哈希指针完全对不上,从而引发多米诺骨牌效应,实现对数据篡改的定位。
二、Merkle Tree
所谓的 Merkle Tree 是一种与 Binary Tree 类似的数据结构,用于组织和存储区块链中的交易信息,且主要存放在每个区块的块身中。在 Merkle Tree 中的每个叶节点对应一个交易数据块,其他节点用于存储左右子节点的块哈希值。
Merkle Tree 与 Binary Tree 相似,但是存在一定的区别:
(1)Merkle Tree 用哈希指针代替了普通指针
(2)Merkle Tree 可以高效验证某笔交易写入了区块链
在区块链的系统中,可以将网络中的节点分为全节点和轻节点,全节点存放了区块链的完整数据信息(既保留了区块的块头又保留了完整的块身),轻节点如 BTC 钱包等应用只存放了区块的部分数据信息(仅保留了区块的块头)。如果与某一轻节点之间进行交易,且需要向该轻节点证明某个交易是写入区块链了,则这时可以使用上 Merkle Tree 这一数据结构的 merkle proof。
merkle proof 的验证过程是这样的,假设待验证交易是颜色为黄色的 tx 块(如上图),则轻节点可以在本地计算出指向该 tx 的 H()
(图中最下层的绿色 H()
),并向网络中其他全节点请求验证需要的其他 H()
(图中所有的红色 H()
),之后,利用请求得到的红色 H()
和指向 tx 的 H()
,从叶子节点一路向根节点方向计算块哈希(除指向 tx 的 H()
外的其他绿色 H()
),当达到最顶层时,利用最顶层的两个 H()
(图中最顶层中一红一绿的 H()
)计算出 root hash,最后将计算得到的 root hash 与区块头中存储的 merkle root hash 比较,如果相同,则证明该交易已经写入区块链。文章来源:https://www.toymoban.com/news/detail-791595.html
当然利用 Merkle Tree 结构也可以证明交易数据中没有包含某一交易块,这时需要全节点将完整的树结构发给轻节点,轻节点通过依次比对交易块哈希值进行验证,时间复杂度为 Θ ( n ) \Theta(n) Θ(n) 。另一种比较高效的方法是使用 Sorted Merkle Tree,即是交易的哈希值按大小排序的 Merkle Tree(需要排序),此时验证的时间复杂度是 Θ ( l o g ( n ) ) \Theta(log(n)) Θ(log(n))。然而,由于 BTC 中没有涉及这一验证需求,因此,BTC 中使用的是未经过排序的 Merkle Tree 数据结构。文章来源地址https://www.toymoban.com/news/detail-791595.html
到了这里,关于【BTC】数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!