区块链中Merkle树性能研究①

黄 根,邹一波,徐 云

1(中国科学技术大学 计算机科学与技术学院,合肥 230026)

2(上海海洋大学 信息学院,上海 201306)

3(安徽省高性能计算重点实验室,合肥 230026)

自从2009年比特币[1]问世,区块链技术逐渐进入人们的视野.区块链本质就是一个新型的分布式存储系统[2],是将传统计算机技术中的分布式存储、分布式共识、密码学、点对点传输的各种技术进行创新性结合的新技术,它也被视为继大型机、个人电脑、互联网和移动/社交网络之后的第五种颠覆性创新技术[3],目前已经用于物联网[4]、智能制造[5]、供应链管理[6]、数据资产交易[7]等多个领域.对于区块链,主要实现了分布式存储中的去中心化、去信任化、数据的时间序列化、集体维护等特征,同时也保障了可编程性、安全性和可靠性[8].

在区块链中的每个区块中,主要分为区块头和区块体[9].Merkle 树是区块体的主要构成部分,构建Merkle 树也是构建区块体的主要工作.因此Merkle 树的构建时间和存储大小都将影响区块链的性能.

在区块链的技术发展过程中,Merkle 树的结构也在不断的发生改变.目前,主流的区块链框架主要指比特币、以太坊[10]和超级账本[11].在比特币中,其采用传统的Merkle 树结构;以太坊在比特币的基础上进行了改造,汲取了Patricia 树检索高效的优点,融合Merkle树和Patricia 树而产生的Merkle Patricia 树[12];超级账本为了减少添加数据的代价,采用了融合Merkle 树和Hash 桶的Bucket 树[11]结构.

在本文中,我们首先对区块链中Merkle 树的结构和关键操作进行分析,从理论上对Merkle 树的作用和复杂度进行解析;然后根据分析结果提出相应的性能评测指标,最后通过实验进行验证和分析.

1 区块链中的Merkle 树结构分析

1.1 传统Merkle 树结构

在计算机科学与密码学中,Merkle 树是一种树形数据结构.每个叶子节点均以数据块的哈希值作为标签,而除了叶子节点之外的节点则以其子节点标签的加密哈希值作为标签.Merkle 树可以实现快捷的数据验证,因此能够高效地验证大型数据结构的内容[13].

如图1所示,该图表明了Merkle 树的结构.Merkle树可以被看成是Hash 表的推广,即Hash 表其实是树高为2 的Merkle 树.其形成的过程主要为:

图1 Merkle 树结构

(1)在Merkle 树的最底层,将数据分成一个个小的数据块,且各数据块拥有对应的Hash 值,作为叶子节点;

(2)叶子节点到上层树结构时,将相邻的两个Hash值合并成一个字符串,计算该字符串的Hash 值;

(3)每一层都重复过程(2),相邻两个Hash 值便可以一个子Hash 值.若最底层的Hash 总数为单数,则直接对其做Hash 运算.

从叶子节点向上依此类推,最终形成Merkle 树.到了根节点就只剩下一个根Hash 值了,我们将其称为Merkle Root.

1.2 区块链中的Merkle 树结构

在以比特币、以太坊和超级账本为代表的主流区块链系统中,在Merkle 上分别有着不同的设计与实现.下面,我们将依次介绍这三种不同区块链系统中Merkle 树的结构.

(1) 比特币的Merkle 树

在比特币系统中,区块分为区块头和区块体,其中区块体则是由Merkle 树构成.其中,整个区块的大小为2 M,区块头的大小固定为80 个字节,因此,区块体的大小占了整个区块的96%.

比特币的Merkle 结构和传统的Merkle 树完全相同.如图1所示,在比特币中,Merkle 树的叶子结点为系统中每一笔交易的Hash 值.不同交易利用Merkle树的结构进行组合,最终生成比特币的Merkle 树,同时产生由所有交易产生的Merkle 根.

(2) 以太坊的Merkle 树

在比特币模型中,采用UTXO 模型表示数据,因此采用传统的Merkle 树简单快捷[14];但是以以太坊为代表的第二代区块链中,大多采用账户模型[15],此时传统的Merkle 树会带来极大的存储空间消耗,并且不易查询.因此,在以太坊中,对Merkle 树进行改进,设计出一种新的数据结构-Merkle Patricia 树进行数据存储.

Merkle Patricia 树简称MPT,其本质上是先将前缀树进行改进,然后再和Merkle 树进行结合.

在原始的前缀树中,存在空间浪费、节点不易控制、深度长等缺陷.MPT 在前缀树的基础上进行了改进,主要做了以下几个方面.

① 为了防止key 的长度不同造成浪费,首先将所有的key 值进行Hash,将所有的key 转换成相同的长度;

② 为了方便对节点的控制,将所有的节点分为空节点、分支节点、叶子节点和扩展节点4 种不同的节点,分别存储不同的内容;

③ 为了更好的进行比较,将key 中的每个参数进行hex 编码.同时使用hex 编码后,每个值大小为[0-15],可以使每个分支节点的容量都减小;

④ 为了缩短树的深度,将连续两个级以上的扩展节点进行合并.

通过如上4 步改进,传统的前缀树结构如图2所示.最后,将改进后的前缀树和Merkle 树进行结合,将存储的value 值转换成所有子节点的Hash 值,即可组成Merkle Patricia 树.

图2 改进的前缀树

(3) 超级账本的Merkle 树

超级账本采用账户模型来进行数据存储[16],但是以太坊的MPT 树结构复杂、性能低,超级账本则提出了Bucket 树[17]进行数据存储.

Bucket 树其实是揉合了Merkle 树与Hash 桶两种数据结构组合而成的,即Bucket 树本质上是一棵建立在Hash 表上的Merkle 树.

如图3所示,B1-B6 为数据的Hash 桶,每个桶中储存若干被散列到该桶中的数据项,所有数据项都按序排列.每一个桶有可以用一个Hash 值表示其状态,该Hash 值是桶内所有数据项的内容进行Hash 计算所得.除底层的Hash 表之外,上层是一系列Merkle 树节点.一个Merkle 树节点对应下一层的n个Hash 桶或Merkle 节点.Merkle 节点的Hash 值是根据这n个孩子节点的Hash 值计算所得.通过这种方式不断计算,与Merkle 树类似,最顶端的值即为整棵树的Hash 值,即Merkle 根.由此可以生成完整的Bucket 树.

图3 Bucket 树

2 区块链中Merkle 关键操作分析

区块链本质上是一个去中心化的数据库,Merkle树是区块链中核心存储的数据.和传统的数据库相比,区块链只能进行增加和查询的操作,而不能进行删除和修改.因此,Merkle 树中核心的操作就是数据插入.同时,Merkle 树的一个重要作用是SPV 验证(实现简单支付验证),即Merkle 树可以直接下载一个分支并立即验证.因此,在本文中,我们主要分析Merkle 树中两个核心的操作:插入数据和SPV 验证.

2.1 数据插入

数据插入是Merkle 树中最为核心的操作,是实现区块链系统中数据插入功能的底层.因此,理解不同区块链系统中Merkle 树的数据插入的原理,是理解不同区块链系统性能瓶颈的重要途径.

对于比特币中的Merkle 树,当需要插入一个新的数据时,通常在之前的Merkle 树基础上进行插入.如图4所示,如果插入数据L4,通常情况下只需要在之前的Mekle 的基础上重新插入一条新的路径,然后通过和之前的Merkle 树中的节点进行Hash 计算,即可产生新的Merkle 树.

图4 Merkle 树的插入

对于以太坊中的MPT,其插入数据的过程相对比较复杂,其核心的思想为:按照key 的内容,从根节点依次从上往下寻找相同长度的路径,同时随时根据MPT 的性质改变节点的性质,插入新的key 的值,直到key 遍历结束.如图5所示,该虚线路径展现了键值对为＜‘1,2,2,4,5’,‘gen’＞的数据插入.

图5 MPT 的插入

对于超级账本中的Bucket 树,当插入新的数据时,需要对进行计算和合并两个过程.

如图6所示,在Bucket 树中新插入两条数据项Entry1,通常通过以下两个步骤:

图6 Bucket 树插入数据

计算:经过散列值计算,Entry1 应该放到B2 中.

合并:在B2 中需要将新插入的数据与历史数据进行合并,且按固定的排序算法进行重排序,最终得到一个新Hash 桶,即改变B2 的值;

当Hash 桶计算完成之后,便可进行Merkle 节点的Hash 计算.该过程仅对需要改变的节点进行Hash重计算.对没有变化的孩子节点可直接使用历史的Hash值.即需要重新计算Hash0-1,Hash0,Root 节点.

2.2 SPV 验证

在比特币中,Merkle 的主要作用是实现SPV 验证.SPV 验证全称叫做简单支付验证,即区块链中的SPV节点(轻型节点)验证某个交易是否已经在交易中,是区块链系统可以在手机等移动端运行的关键.

在SPV 验证中,Merkle 主要完整交易的存在性检查.其过程主要是

(1) SPV 节点从身边的全节点向获取待交易的Merkle分支;

(2) 利用Merkle 分支与本地的交易生成Merkle根,与本地的Merkle 根进行比较,验证交易的存在性.

如图7所示,SPV 节点验证交易L3 的存在性,只需要通过全节点获取L3 的Merkle 分支,即＜Hash1-1,Hash0＞节点,然后通过L3 与Merkle 分支的计算即可获得Root,最后通过比较Root 和本地存储的Merkle根是否相同判断L3 是否已经在区块中[16].

图7 SPV 验证过程

如上分析,使用Merkle 分支进行存在性检查,对于n 个交易来说,传输的区块数为log(n),可以大大较少数据传输的数量,降低网络传输的负担.

对于以太坊来说,因为其在前缀树的基础上集成了Merkle 树,因此在其SPV 验证和比特币系统相同:在SPV 节点中,也是主要存储了Merkle 根,之后从邻居的全节点获取Merkle 分支,通过哈希计算查询获取Root,最后和本地存在的Merkle 根进行比较以判断交易的存在性.

对于超级账本的Bucket 树来说,由于其叶子结点为有序的哈希桶,哈希桶中存在大量的数据.如果需要实现SPV 验证,其不仅仅需要传输Merkle 分支,同时需要传输Hash 桶中的其他元素,会大大增加传输数据的数量,增加网络负担.因此,在超级账本中很少有提及SPV 相关的操作.

2.3 性能总结

从上述的所有内容中,我们分析了比特币中的Merkle 树、以太坊中的Merkle Patricia 树以及超级账本中的Bucke 树的结构和主要操作.假设对于n个＜key,value＞键值对的数据,MPT 树中每个key 值Hash后的长度为m,Bucket 树中每个节点有a个子节点,叶子节点个数为C,那么从理论上进行分析,Merkle 树,MPT和Bucket 树的插入时间复杂度,空间复杂度和SPV 传输节点数的理论复杂度如表1所示.

表1 不同种类树理论性能分析

3 实验性能分析指标设计

在之前的工作中,我们分析了Merkle 树的结构和两大核心操作.因此,在实验中,我们主要从插入数据性能,数据存储和SPV 验证性能3 个方面进行相关的实验,以验证之前的理论分析.为了更好的定量表现出相关性能,我们设计了相关的指标,分别体现出插入数据,数据存储和SPV 验证的相关性能.

3.1 构建时间

首先考虑插入数据的时间开销.对于一个相关的数据来说,插入数据的时间极短,其插入数据的时间开销可能比程序代码在其他地方运行的时间更短,因此较难使用程序来统计一个数据的插入时间.但是,在区块链系统中,构建区块的过程中存在非常重要的一步就是将交易池中的众多交易进行打包构建成Merkle树,其本质上就是将交易池的数据一个个插入到Merkle树中以构成最终的Merkle 树并存入区块中.因此,在本实验中,我们采用统计不同规模数据集下Merkle 树的构建时间来进一步的表现出不同Merkle 树的插入性能.

3.2 节点数及树的深度

其次,我们考虑不同Merkle 树带来的数据存储.目前区块过大已经是区块链系统中十分关键的问题,而Merkle 树作为区块中主要存储的数据,对比不同Merkle 树的存储性能对我们之后选择不同的区块链结构是十分有必要的.

对于Merkle 树来说,节点数目的大小会直接影响Merkle 树的存储大小:更多节点的Merkle 树节点存储规模显然会更大.对于不同的Merkle 树结构来说,相同的数据在不同的Merkle 树结构上的节点数目和树的深度是不同的.因此可以统计不同规模的数据在Merkle 树上的节点数和深度来定量的表示在不同Merkle树的存储性能.

3.3 SPV 验证中Merkle 分支节点数

如第2 节所述,区块链中的SPV 验证是Merkle 树中的重要功能之一,因此检测SPV 验证的相关性能也是对Merkle 树性能分析的重要组成部分.

在进行SPV 验证时,主要关心两个性能指标.首先是Merkle 分支的节点数,该指标会影响在网络传输中的性能,太大的Merkle 分支会造成较大网络传输的负担,严重影响网络传输的性能.其次,Merkle 分支树也会影响SPV 验证的时间性能,因为更多的Merkle 分支节点就需要更多的重组Hash 运算,影响做SPV 验证的时间效率.因此,在本实验分析中,我们只需要利用Merkle 分支的节点数目来分析对SPV 验证的网络传输和时间的性能.

4 比较实验结果与分析

在本实验中,我们通过实验设计,利用Merkle 树的构建时间、Merkle 树的节点数、树的深度和SPV验证的Merkle 分支节点数来进一步分析和验证不同区块链系统中Merkle 树的相关性能.

4.1 实验设计

本文中,我们主要进行分析和比较比特币中的Merkle 树,以太坊中Merkle Patricia 树和超级账本中的Bucket 树.为了消除其他因素的影响而直接分析不同Merkle 的性能,我们利用统一的语言(Java)对3 种树的结构进行实现.

在数据方面,为了更好的适配MPT 结构,我们统一使用账户模型.如图8所示,在本实验中,我们通过随机产生的方式,生成了数量为1000、10 000、50 000和100 000 的键值对.这些键值对的key 值不固定大小,其长度从4 到20 不等;value 的值也不固定大小,长度从6 到30 不等.

针对3 种Merkle 树结构,具体的实验过程为:

在Merkle 树的实验中,将key 和value 的值利用“--”字符串进行合并,组成一个新的字符串.之后将新的字符串的Hash 值,作为Merkle 树的叶子节点.

在Merkle Patricia 树的实验中,首先要对key 值进行Hash 运算,将key 编成16 字节的固定长度.然后利用Hex 编码进行编码,之后采用MPT 树的相关算法实现完整的MPT 树结构.

图8 数据集格式

在Bucket 树的实验中,确定100 个Hash 桶,每个节点最多有3 个子节点.然后将所有的键值随机分配到Hash 桶中,保证每个Hash 桶的键值对应数目基本均匀,最后构建Bucket 树.

4.2 实验结果

在本实验中,我们首先对3 种不同Merkle 树架构的存储进行分析.如3.2 节所述,在Merkle 树存储分析时,我们利用树的规模作为反映存储空间的指标.即利用树的节点数和树的深度来进行表示.通过实验,表2和表3表示在不同数据规模下3 种不同Merkle 树结构的节点数和深度.

表2 不同规模树节点数比较(个)

表3 不同规模树深度比较

从表2中可以看出,在1000、10 000、50 000、100 000组数据的情况下,Merkle 树的节点数均为最多,分别为2001、20 004、99 938 和199 750 个;MPT 的节点数居中,Bucket 树的节点数最小,均为154 个.

再看树的深度,从表3可知,在1000、10 000、50 000、100 000 组数据的情况下,Merkle Patricia 树的树深均为32,Merkle 树的深度分别为11,15,17 和18,Bucket 树的深度均为6.因此,在树的深度方面,Merkle Patricia 树的树深远远大于Merkle 树和Bucket 树两种算法.同时Merkle Patricia 树和Bucket 树的树深比较稳定,不会随着节点数的增加而增加.

其次,如3.1 节所述,我们进一步对3 种不同Merkle树的构建时间进行分析.如表4所示,表明了3 种不同的Merkle 树分别创建1000、10 000、50 000 和100 000组数据的数据结构所需的时间.

表4 不同规模树创建时间比较(ms)

由表4可以看出,在相同规模的数据下,Merkle Patricia 树的创建时间最多,远大于其他两种Merkle 结构;Merkle 树的创建时间居中,Bucket 树的创建时间最短.

最后,我们需要评测3 种Merkle 树在做SPV 验证.在实验中,我们分别取了3 种Merkle 树的Merkle路径,如表5所示.

表5 不同规模树Merkle 分支(个)

从表5可以看到,可以看到比特币,以太坊和超级账本在不同规模数据下的Merkle 路径的长度,相比之下3 种系统的规模有着明显的差异.Merkle 树的Merkle路径所需要的节点最少,其次是MPT 树.Bucket 树我们采用和Merkle 树相同SPV 验证的方法进行统计Merkle路径,所需要的Merkle 路径总体来说最长.

4.3 实验总结与分析

如4.2 节所示,在存储方面,如果从节点数目来看,Merkle 所拥有的节点较多,即所占存储较大,其次是MPT 树,Bucket 树所占空间最小.从之前的理论上分析来看,由于Merkle Patricia 树和Bucket 树均采取措施压缩数据,其中MPT 树使用前缀树算法,Bucket 树使用Hash 桶,故其节点数均小于Merkle 树.值得注意的是,MPT 树的节点数其实与Merkle 树较为接近.

从树的深度来看,MPT 树最大,Merkle 其次,Bucket中树的深度最小.从理论上分析,由于在生成MPT 树的过程中,首先要将key 值Hash 运算为16 的长度,同时采用Hex 编码,会扩大树的深度,因此MPT 应该是一个非常狭长的树状结构;但是由于key 的长度一定,因此其深度永远不会进行增长;而Merkle 树的深度是数据个数的log(n),会随着数据的增多而增加;Bucket树中底层的Hash 桶数量不会发生改变,因此其树的深度很小,同时其不会因为数据规模的增加而改变.

从构建时间来看,同样是MPT 的构造时间最长,Bucket 树的构造时间最短.出现这种情况是由其算法的特殊性导致的:首先,为了提高节点的查找效率和减少存储空间浪费,MPT 树对单独存在的key 进行了合并,这需要占用一定时间;其次,为避免树中出现很长的路径并提高MPT 树的安全性,需要对每个key 求Hash 值,这一过程需要花费大量时间.而Bucket 只需要进行Hash 桶的排序和求Hash,上层的Merkle 树的规模较小;而Merkle 树只需要进行结构的构建.因此,MPT 树创建时间远大于其他两种算法.

从SPV 来看,在3 种Merkle 树中,比特币中Merkle路径最短,超级账本最多,以太坊居中.其原因是因为比特币和超级账本中只需要获取相应的路径上的节点即可,因此其Merkle 路径的长度应该和对应Merkle 树的深度成正比;而Bucket 树底层是对有序的Hash 桶求Hash,所以如果进行SPV 验证即不仅仅需要传递路径上的数据,同时也需要Hash 桶中其他的数据.因此,在三种区块链结构中,比特币应该最适合于在手机移动端使用,超级账本不适合在移动端实现.

5 结论与展望

在本文中,我们首先分析了比特币,以太坊和超级账本这3 种主流区块链中Merkle 树的相关结构和核心操作,同时根据Merkle 树的作用和特性,提出了相应的性能指标.然后利用统一的语言进行了实现,并进行了相关性能指标的检测.实验结果表明,比特币的Merkle 树结构会造成更多的存储消耗,以太坊的MPT结构会造成更多的时间消耗,超级账本的Bucket 树SPV 验证最难.本文的操作分析和实验环境为我们接下来的工作也奠定了基础,接下来我们将针对Merkle树的特性和不足,希望提出新的Merkle 树结构,在插入时间、存储或者SPV 的验证上取得更好的发展.