精通比特币(65):区块中的Merkle树

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

 

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

 

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

 

Merkle树是自底向上构建的。

构建Merkle树的过程如下:
从A、B、C、D四个构成Merkle树树叶的交易开始

精通比特币(65):区块中的Merkle树

所有的交易都并不存储在Merkle树中,而是将数据哈希化,然后将哈希值存储至相应的叶子节点。这些叶子节点分别是H{A}、H{B}、H{C}和H{D}:
HA = SHA256(SHA256(Transaction A))
将相邻两个叶子节点的哈希值串联在一起进行哈希,这对叶子节点随后被归纳为父节点。 例如,为了创建父节点H{AB},子节点 A和子节点B的两个32字节的哈希值将被串联成64字节的字符串。随后将字符串进行两次哈希来产生父节点的哈希值:
HAB = SHA256(SHA256(H{A} + H{B}))
继续类似的操作直到只剩下顶部的一个节点,即Merkle根。产生的32字节哈希值存储在区块头,同时归纳了四个交易的所有数据。

 

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

 

在比特币中,在单个区块中有成百上千的交易是非常普遍的,这些交易都会采用同样的方法归纳起来,产生一个仅仅32字节的数据作为Merkle根。

 

为了证明区块中存在某个特定的交易,一个节点只需要计算log{2}(N)个32字节的哈希值,形成一条从特定交易到树根的认证路径或者Merkle路径即可。

 

证明包含数据元素的merkle路径

一个节点能够通过生成一条仅有4个32字节哈希值长度(总128字节)的Merkle路径,来证明区块中存在一 笔交易K。该路径有4个哈希值(由蓝色标注)H{L}、H{IJ}、H{MNOP}和H{ABCDEFGH}。由这4个哈希值产生的认证路径,再通过计算另外四对哈希值H{KL}、H{IJKL}、H{IJKLMNOP}和Merkle树根(在图中由虚线标注),任何节点都能证明H{K}(在图中由绿色标注)包含在Merkle根中。

 

精通比特币(65):区块中的Merkle树

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

精通比特币(65):区块中的Merkle树

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

发表评论

您必须才能发表评论!