自从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树的最底层, 将数据分成一个个小的数据块, 且各数据块拥有对应的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树.

(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树.

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

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

2.1 数据插入

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

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

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

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

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

计算: 经过散列值计算, 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].

如上分析, 使用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所示.

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树结构.

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

4.2 实验结果

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

从表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可以看出, 在相同规模的数据下, Merkle Patricia树的创建时间最多, 远大于其他两种Merkle结构; Merkle树的创建时间居中, Bucket树的创建时间最短.

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

从表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的验证上取得更好的发展.