BTC数据结构
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 比较,如果相同,则证明该交易已经写入区块链。
当然利用 Merkle Tree 结构也可以证明交易数据中没有包含某一交易块,这时需要全节点将完整的树结构发给轻节点,轻节点通过依次比对交易块哈希值进行验证,时间复杂度为 Θ ( n ) \Theta(n) Θ(n) 。另一种比较高效的方法是使用 Sorted Merkle Tree,即是交易的哈希值按大小排序的 Merkle Tree(需要排序),此时验证的时间复杂度是 Θ ( l o g ( n ) ) \Theta(log(n)) Θ(log(n))。然而,由于 BTC 中没有涉及这一验证需求,因此,BTC 中使用的是未经过排序的 Merkle Tree 数据结构。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgbgiic
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01