区块的连接与Merkle树

区块的连接

比特币的完整节点保存了区块链从创世区块起的一个本地副本。随着新的区块的产生,该区块链的本地副本会不断地更新用于扩展这个链条。当一个节点从网络接收传入的区块时,它会验证这些区块,然后链接到现有的区块链上。为建立一个连接,一个节点将检查传入的区块头并寻找该区块的“父区块哈希值”。

让我们假设,例如,一个节点在区块链的本地副本中有277,314个区块。该节点知道最后一个区块为第277,314个区块,这个区块的区块头哈希值为:00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249。

然后该比特币节点从网络上接收到一个新的区块,该区块描述如下:

区块的连接

对于这一新的区块,节点会在“父区块哈希值”字段里找出包含它的父区块的哈希值。这是节点已知的哈希值,也就是第277314块区块的哈希值。故这个区块是这个链条里的最后一个区块的子区块,因此现有的区块链得以扩展。节点将新的区块添加至链条的尾端,使区块链变长到一个新的高度277,315。图7-1显示了通过“父区块哈希值”字段进行连接三个区块的链。

区块通过引用父区块的区块头哈希值的方式,以链条的形式进行相连

图7-1区块通过引用父区块的区块头哈希值的方式,以链条的形式进行相连

Merkle树

区块链中的每个区块都包含了产生于该区块的所有交易,且以Merkle树表示。

Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构。这种二叉树包含加密哈希值。术语“树”在计算机学科中常被用来描述一种具有分支的数据结构,但是树常常被倒置显示,“根”在图的上部同时“叶子”在图的下部,你会在后续章节中看到相应的例子。

比特币网络中,Merkle树被用来归纳一个区块中的所有交易,同时生成整个交易集合的数字指纹,且提供了一种校验区块是否存在某交易的高效途径。生成一棵完整的Merkle树需要递归地对哈希节点对进行哈希,并将新生成的哈希节点插入到Merkle树中,直到只剩一个哈希节点,该节点就是Merkle树的根。在比特币的Merkle树中两次使用到了SHA256算法,因此其加密哈希算法也被称为double-SHA256。

当N个数据元素经过加密后插入Merkle树时,你至多计算2*log2(N)次就能检查出任意某数据元素是否在该树中,这使得该数据结构非常高效。

Merkle树是自底向上构建的。在如下的例子中,我们从A、B、C、D四个构成Merkle树树叶的交易开始,如图7-2。起始时所有的交易都还未存储在Merkle树中,而是先将数据哈希化,然后将哈希值存储至相应的叶子节点。这些叶子节点分别是HA、HB、HC和HD:

H~A~=SHA256(SHA256(交易A))

通过串联相邻叶子节点的哈希值然后哈希之,这对叶子节点随后被归纳为父节点。例如,为了创建父节点HAB,子节点A和子节点B的两个32字节的哈希值将被串联成64字节的字符串。随后将字符串进行两次哈希来产生父节点的哈希值:

H~AB~=SHA256(SHA256(H~A~+H~B~))

继续类似的操作直到只剩下顶部的一个节点,即Merkle根。产生的32字节哈希值存储在区块头,同时归纳了四个交易的所有数据。

Merkle树中计算节点

图7-2在Merkle树中计算节点


因为Merkle树是二叉树,所以它需要偶数个叶子节点。如果仅有奇数个交易需要归纳,那最后的交易就会被复制一份以构成偶数个叶子节点,这种偶数个叶子节点的树也被称为平衡树。如图7-3所示,C节点被复制了一份。

Merkle树是二叉树

由四个交易构造Merkle树的方法同样适用于从任意交易数量构造Merkle树。在比特币中,在单个区块中有成百上千的交易是非常普遍的,这些交易都会采用同样的方法归纳起来,产生一个仅仅32字节的数据作为Merkle根。在图7-4中,你会看见一个从16个交易形成的树。需要注意的是,尽管图中的根看起来比所有叶子节点都大,但实际上它们都是32字节的相同大小。无论区块中有一个交易或者有十万个交易,Merkle根总会把所有交易归纳为32字节。

Merkle树是二叉树

为了证明区块中存在某个特定的交易,一个节点只需要计算log2(N)个32字节的哈希值,形成一条从特定交易到树根的认证路径或者Merkle路径即可。随着交易数量的急剧增加,这样的计算量就显得异常重要,因为相对于交易数量的增长,以基底为2的交易数量的对数的增长会缓慢许多。这使得比特币节点能够高效地产生一条10或者12个哈希值(320-384字节)的路径,来证明了在一个巨量字节大小的区块中上千交易中的某笔交易的存在。

在图7-5中,一个节点能够通过生成一条仅有4个32字节哈希值长度(总128字节)的Merkle路径,来证明区块中存在一笔交易K。该路径有4个哈希值(在图7-5中由蓝色标注)HL、HIJ、HMNOP和HABCDEFGH。由这4个哈希值产生的认证路径,再通过计算另外四对哈希值HKL、HIJKL、HIJKLMNOP和Merkle树根(在图中由虚线标注),任何节点都能证明HK(在图中由绿色标注)包含在Merkle根中。

图7-5—条为了证明树中包含某个数据元素而使用的Merkle路径

—条为了证明树中包含某个数据元素而使用的Merkle路径

例7-1中的代码借用libbitcoin库中的一些辅助程序,演示了从叶子节点哈希至根创建整个Merkle树的过程。

—条为了证明树中包含某个数据元素而使用的Merkle路径

—条为了证明树中包含某个数据元素而使用的Merkle路径

—条为了证明树中包含某个数据元素而使用的Merkle路径

例7-2展示了编译以及运行上述代码后的结果。例7-2编译以及运行构造Merkle树代码

—条为了证明树中包含某个数据元素而使用的Merkle路径

Merkle树的高效随着交易规模的增加而变得异常明显。表7-3展示了为了证明区块中存在某交易而所需转化为Merkle路径的数据量。

表7-3Merkle树的效率

—条为了证明树中包含某个数据元素而使用的Merkle路径

依表可得,当区块大小由16笔交易(4KB)急剧增加至65,535笔交易(16MB)日寸,为证明交易存在的Merkle路径长度增长极其缓慢,仅仅从128字节到512字节。有了Merkle树,一个节点能够仅下载区块头(80字节/区块),然后通过从一个满节点回溯一条小的Merkle路径就能认证一笔交易的存在,而不需要存储或者传输大量区块链中大多数内容,这些内容可能有几个G的大小。这种不需要维护一条完整的区块链的节点,又被称作简单支付验证(SPV)节点,它不需要下载整个区块而通过Merkle路径去验证交易的存在。

Merkle树和简单支付验证(SPV)

Merkle树被SPV节点广泛使用。SPV节点不保存所有交易也不会下载整个区块,仅仅保存区块头。它们使用认证路径或者Merkle路径来验证交易存在于区块中,而不必下载区块中所有交易。

例如,一个SPV节点欲知它钱包中某个比特币地址即将到达的支付,该节点会在节点间的通信链接上建立起bloom过滤器,限制只接受含有目标比特币地址的交易。当节点探测到某交易符合bloom过滤器,它将以Merkleblock消息的形式发送该区块。Merkleblock消息包含区块头和一条连接目标交易与Merkle根的Merkle路径。SPV节点能够使用该路径找到与该交易相关的区块,进而验证对应区块中该交易的有无。SPV节点同时也使用区块头去关联区块和区块链中的区域区块。这两种关联,交易与区块、区块和区块链,证明交易存在于区块链。简而言之,SPV节点会收到少于1KB的有关区块头和Merkle路径的数据,其数据量比一个完整的区块(目前大约有1MB)少了一千倍有余。

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。