黄 根,邹一波,徐 云

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 树的作用和复杂度……