区块brandoff

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2019,30(9):26712685[doi:10.
13328/j.
cnki.
jos.
005776]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563区块链数据库:一种可查询且防篡改的数据库焦通,申德荣,聂铁铮,寇月,李晓华,于戈(东北大学计算机科学与工程学院,辽宁沈阳110169)通讯作者:申德荣,E-mail:shendr@mail.
neu.
edu.
cn摘要:随着比特币、以太币等一系列加密货币的兴起,其底层的区块链技术受到越来越广泛的关注.
区块链有防篡改、去中心化的特性.
以太坊利用区块链技术来构建新一代去中心化的应用平台.
BigchainDB将区块链技术与传统的分布式数据库相结合,利用基于联盟投票的共识机制改进传统Pow机制中的节点全复制问题,提高了系统的扩展性与吞吐率.
但是现有的区块链系统存储的信息大都是固定格式的交易信息,虽然在每个交易里有数据字段,但是现有的区块链系统并不能经由链上对交易内的数据字段的具体细节进行直接查询.
如果想要查询数据字段的具体细节,只能先根据交易的哈希值进行查询,得到该交易的完整信息,然后再检索该交易内的数据信息.
数据可操作性低,不具备传统数据库的查询功能.
首先提出一种区块链数据库系统框架,将区块链技术应用于分布式数据管理;其次提出一种基于哈希指针的不可篡改索引,根据该索引快速检索区块内数据,以此实现区块链的查询;最后,通过实验测试数据库的读写性能,实验结果表明,所提出的不可篡改索引在保证不可篡改的同时具有较好的读写性能.
关键词:区块链;数据库;可查询;哈希指针;不可篡改索引;可回溯中图法分类号:TP311中文引用格式:焦通,申德荣,聂铁铮,寇月,李晓华,于戈.
区块链数据库:一种可查询且防篡改的数据库.
软件学报,2019,30(9):26712685.
http://www.
jos.
org.
cn/1000-9825/5776.
htm英文引用格式:JiaoT,ShenDR,NieTZ,KouY,LiXH,YuG.
BlockchainDB:Querableandimmutabledatabase.
RuanJianXueBao/JournalofSoftware,2019,30(9):26712685(inChinese).
http://www.
jos.
org.
cn/1000-9825/5776.
htmBlockchainDB:QuerableandImmutableDatabaseJIAOTong,SHENDe-Rong,NIETie-Zheng,KOUYue,LIXiao-Hua,YUGe(SchoolofComputerScienceandEngineering,NortheasternUniversity,Shenyang110169,China)Abstract:Withtheriseofaseriesofcrypto-currencies,suchasBitcoinandEther,theunderlyingblockchaintechnologyhasreceivedmoreandmoreattention.
Theblockchainisknownasthecharacteristicsofdecentralizationandimmutability.
Ethereumutilizestheblockchaintechnologytobuildthenextgenerationdecentralizedapplicationplatform.
BigchainDBcombinesblockchaintechnologywithtraditionaldistributeddatabases,andusesthefederalbasedvotingtoimprovethetraditionalPoWmechanismandfinallyimprovesthesystem'sscalabilityandthroughput.
However,theexistingblockchainsystemmostlystorestransactioninformationwithafixed-form.
Althoughtherearedatafieldsineachtransaction,theexistingblockchainsystemcannotdirectlyquerythespecificdetailswithinthedatafieldsofthetransactiondatafromtheblockchaindata.
Toquerythespecificdetailsofthedatafield,itmustquerythetransactionfirstwiththehashvalueofthetransactiontogetthecompleteinformationofthetransaction,andthenretrievethedetailsinthetransactiondata.
Thismechanismhasalowoperabilityofdataandalackofqueryfunctionsofthetraditionaldatabase.
Thisstudyfirstproposesaframeworkofblockchaindatabasesystem,whichappliesblockchaintechnologytodistributeddatamanagement.
Then,animmutable基金项目:国家重点研发计划(2018YFB1003404);国家自然科学基金(61472070,61672142,U1435216)Foundationitem:NationalKeyR&DProgramofChina(2018YFB1003404);NationalNaturalScienceFoundationofChina(61472070,61672142,U1435216)本文由"区块链数据管理"专题特约编辑于戈教授、牛保宁教授、金澈清教授推荐.
收稿时间:2018-06-10;修改时间:2018-08-28;采用时间:2018-12-14;jos在线出版时间:2019-04-10CNKI网络优先出版:2019-04-0917:32:25,http://kns.
cnki.
net/kcms/detail/11.
2560.
TP.
20190409.
1732.
005.
html2672JournalofSoftware软件学报Vol.
30,No.
9,September2019indexisproposedbasedonhashfunctions.
Accordingtotheindex,thedataintheblockcanbequicklyretrievedtoimplementthequeryprocessingintheblockchain.
Finally,experimentsaredesignedtotestthedatabase'sread/writeperformance.
Theexperimentalresultsshowthattheimmutableindexhasgoodread/writeperformancewhileensuringimmutability.
Keywords:blockchain;database;blockchainquery;hashpointer;immutableindex;retrospective随着比特币、以太币等一系列加密货币的兴起,其底层的区块链技术也受到了越来越广泛的关注[1,2].
比特币最核心的意图是为了实现去中心化,即:在没有第三方信任机构参与的情况下,实现两个对等实体的数字货币交易.
然而,现实世界中不可避免地存在很多自然中心,比如提供贷款的银行、提供电信服务的电信运营商等.
虽然我们可以把这些中心机构当作对等实体,将其与用户的交易记录到区块链上,比如用比特币去交话费,但是这种做法是不切实际的,因为这不利于机构管理用户数据(包括用户的信用等级等).
实际上,现有的中心机构都是由自己管理其存储用户相关信息的数据库,但是这种模式存在很多缺陷:(1)不同的数据库可能存储着相同的用户基本身份信息,导致数据冗余度高;(2)不同的中心机构各自管理自己的数据,不利于机构之间的数据共享;(3)每个数据库大都由单一机构中心化管理,使得用户必须无条件信任该机构,存在中心化问题;(4)用户不能够独立验证数据的正确性,如果数据被恶意篡改,用户与机构都无法察觉.
不仅如此,在供应链以及商品溯源等领域,也对数据可信性以及数据可回溯提出了新的要求.
而区块链技术具有去中心化、防篡改以及可回溯的特性,为解决上述这些问题提供了可能.
为此,我们提出了区块链数据库的概念,核心思想是:通过限制中心机构对数据记录的操作,来达到防篡改和去中心化的目的.
该数据库中有多条区块链,每一条区块链相当于传统数据库中的一张表,所有的中心机构充当数据的存储节点,所有的存储节点根据共识算法生成区块链,所有节点(包括用户)存储区块头信息,可以由区块头信息检索到记录并验证记录的正确性.
我们希望有高效的共识算法来提高系统的吞吐率,并有高效的查询算法实现在区块链上检索数据.
当前,在共识算法上已经有很多研究,例如POW[3,4],POS[5,6],PBFT[7].
然而针对区块链查询的研究相对较少,而且现有的区块链系统并不能兼顾数据回溯与数据查询.
在比特币中可以根据每一笔交易回溯前一笔交易,但是存在的问题是交易本身不易检索.
在以太坊中是状态树+交易树,状态树存储的是用户账号信息,状态树支持检索,可以根据状态树查询用户当前余额,但是状态树本身不记录历史信息,不能对状态进行数据回溯,而且状态树不直接关联交易,同样无法有效对交易进行回溯.
虽然已有一些研究利用同步技术将交易数据同步到传统数据库,根据各数据项建立索引,从而实现快速查询,但是这种做法并不能保证索引的不可篡改,所以损失了区块链不可篡改的特性.
基于此,本文提出一种不可篡改的索引结构,兼顾数据查询以及数据回溯.
本文首先提出了区块链数据库系统框架,将区块链技术应用于数据管理;其次,提出了一种基于哈希指针的不可篡改索引,根据该索引快速检索区块内数据,以此实现区块链的查询;最后,通过实验测试数据库的读写性能,实验结果表明,本文提出的不可篡改索引在保证不可篡改的同时具有较好的读写性能.
1相关工作文献[3]中,中本聪将数字签名技术、P2P技术、时间戳技术、Merkle树技术和工作量证明机制巧妙地结合起来,解决了双花与女巫攻击问题,实现了拥有去中心化、防篡改和数据可回溯等特性的数字货币系统——比特币系统.
文献[8]中,Buterin等人对比特币系统进行扩展,构建了新一代智能合约和去中心化应用平台——以太坊.
除了比特币的功能之外,以太坊还有图灵完备的合约语言,内置的持久化状态存储,具有可编程性,使开发者可以很快地在以太坊平台上创建自己的区块链应用.
这两个应用都是自下而上设计区块链,有内置代币,比特币主要应用于货币,而以太坊的主要功能则是智能合约.
文献[9]中,超级账本则采用自上而下的设计方式,去除了内置代币,提出了商用区块链框架.
它采用了松耦合的设计,将共识机制、身份验证等组件模块化,使之在应用过程中可以方便地根据应用场景来选择相应的模块,除此之外还采用了容器技术,将智能合约放在docker中运行,从而使得智能合约可以用几乎任意的高级语言来编写.
比特币、以太坊和超级账本三大应用平台的主要功能是针对数字货币与智能合约,但是数据管理性能较焦通等:区块链数据库:一种可查询且防篡改的数据库2673弱,一些机构发现了区块链不可篡改、去中心化与数据可回溯特性,力图将区块链技术与传统的数据库技术相结合,提升数据管理的性能,同时兼顾区块链去中心化、数据可回溯、防篡改的特性.
文献[10]中,Dinh等人受区块链链式结构以及Git版本控制的启发,为每个key创建设计了一个有向无环图,图中每一个节点对应key的某一历史版本,节点的前驱后继分别对应其版本的前驱后继,在保证高扩展性和高吞吐率的同时,实现了数据可共享与不可篡改的特性.
文献[11]中,BigchainDB将区块链技术与RethinkDB相结合,在企业级分布式数据库的基础上添加区块链不可篡改和去中心化等特性,提出了一种基于管程的一致性策略,提高了数据的安全性,同时解决了区块链的数据存储容量问题.
文献[12]提供了基于区块链的加密存储网络,通过将原始数据加密并签名后,保存到P2P文件系统中,用户可以对数据的完整性进行验证.
文献[13]中,Tuan等人提出了一种区块链测试框架,包括针对区块链应用的一致性算法、数据模型、执行引擎和链上应用的测试方法,并且分析了以太坊、超级账本、Parity以及UStore的读写以及查询能力,对于区块链的设计以及瓶颈发现和解决带来了极大的帮助.
文献[14]中,Tsai等人总结了基于区块链的应用开发方法,给出了开发区块链应用时需要注意的关键问题,设计并实现了"北航链".
文献[15]中,Li等人提出了一种高效的检索区块链的方法,包括范围查询和Top-k查询,有较好的灵活性.
但是其解决方法是通过把区块链数据以及k-v数据库里面的数据同步到MongoDB数据库中,利用MongoDB进行查询操作,没有从根本上解决区块链的查询问题.
为了将区块链技术应用于数据存储,ChainSQL[16]将数据库操作日志存储于区块链中,将数据存储于附属关系型数据库中,在底层支持SQLite3,MySQL,PostgreSQL等关系数据库,可以根据区块链里的日志记录将数据库表恢复到任意时刻点,但是其恢复粒度是以表为单位,不利于以交易为单位的数据溯源.
2区块链数据库系统框架通过结合区块链和数据库技术,提出一种去中心化、防篡改同时支持查询的区块链数据库框架.
如图1所示,分4层,具体如下.
存储层:在最底部,为k-v数据库,负责分布式存储数据,为每一个区块链备份多个副本;网络层:是该框架的核心,负责节点间的数据传输以及根据共识协议确定区块的先后顺序.
其中,节点由存储节点以及用户组成,每一机构为一个存储节点,用于存储本机构的数据信息,可以是一个数据库,也可以是多个数据库.
当添加或者修改用户相关的数据时,需要由用户和机构共同签名认可;签名后的数据由机构封装到区块中,当区块大小达到某一阈值时,将其打包发送给其他机构进行验证.
机构间根据共识算法验证区块的正确性,并决定区块的先后顺序.
将验证正确的区块发送给存储节点存储,将区块头广播给所有节点,包括用户.
在进行查询操作时,用户向存储节点发送查询请求,存储节点会返回查询到的记录项以及查询路径,用户根据查询路径以及区块头信息,可以验证查询结果的正确性;区块链层:显示的是区块链的"世界状态",上层应用可以据此对区块链数据进行查询操作;应用层:是最上层,可以对查询到的数据进行进一步的分析处理.
针对这一框架,本文重新定义了数据库中的数据结构以及数据操作,并提出了MerkleRBTree索引,基于哈希指针构建不可篡改的索引,在保证不可篡改的前提下实现高效查询.
系统中数据的操作定义如下.
增加记录:数据在初次添加时,数据拥有者指定可以进行数据写操作的公钥,生成权限锁定脚本,然后用自己的私钥对该数据进行签名;修改记录:操作者用自己的私钥对其父记录进行签名,然后验证该签名是否能够解锁父记录的锁定脚本,当且只当在解锁锁定脚本的情况下,才可以添加一条相同key值的记录,以此实现对父记录的修改.
其中,权限锁定脚本只有数据拥有者可以修改.
需要说明的是,数据修改与数据防篡改并不冲突,本文中的防篡改指的是对应版本的数据不可改且数据的更改历史不可改,但是支持数据从较老版本更新到新的版本;查找记录:所有的参与者都可以进行查找操作,查找操作返回最新值为有效值,但是可以通过溯源操作查看该记录的完整修改历史;2674JournalofSoftware软件学报Vol.
30,No.
9,September2019删除记录:数据一旦添加便不可删除,当数据已经被修改多次,处于非常古老的版本时,为了节约磁盘空间,可以删除该数据的具体信息,但是该数据的哈希值则需要永久保存.
Fig.
1Blockchaindatabasesystemframework图1区块链数据库系统框架3区块链式数据模型3.
1已有的区块链系统模型(1)数据结构为了能够较好地理解区块链的结构,我们给出了哈希指针的定义.
一个数据项的哈希指针是指将该数据项的内容做哈希操作后得到固定长度的哈希值,同时以该哈希值为key,该数据项的内容为value,将此k-v对存储于k-v数据库,则该key即为该数据项的哈希指针.
区块链就是一个个的区块根据哈希指针首尾相连,每一个区块一旦形成便不可改变.
如图2所示,区块分为区块头和区块体两部分:区块头包括版本号、前一区块哈希指针(由前一区块头数据哈希得到)、区块形成时的时间戳、区块体中交易自下而上哈希得到的Merkle根以及用于工作量证明的随机数和目标哈希;区块体中保存着区块中的所有交易记录.
如图3所示,交易(transaction)包含版本号(nVersion)、交易输入(TxIn)、交易输出(Txout)以及交易时间(nLockTime).
其中:交易输入包含其要花费的交易输出(preout)以及锁定脚本(ScriptSig),并且当且仅当SicriptSig是上一个输出中ScriptPubk对应的私钥签名时才被认为是有效的;交易输出指定该笔交易的输出金额(nValue),以及收款人的公钥(ScripPubk).
数字签名技术[17]保证每笔交易被支付到一个公钥里,然后只有拥有私钥的人才能花费掉这笔交易.
(2)数据读写流程对于数据的存储管理,在写入数据时,每个区块的数据操作流程如下.
1)收集交易.
将未写入到区块内的交易数据进行正确性检查(包括格式检查以及双花检查),并将有效的交易数据收集在集合(MapTransaction)中,其中,MapTransaction只存放在内存中,其内存放了从交易哈焦通等:区块链数据库:一种可查询且防篡改的数据库2675希到交易的map映射;2)创建区块.
将MapTransaction中的数据添加到区块体中;之后运行PoW机制,搜索合适的随机数值,使得区块头的哈希值小于目标哈希,从而证明该区块有效,即挖矿成功并获得奖励;3)存储区块.
在网络上将该区块广播,在本地将该区块顺序存储在本地磁盘文件(blk000x.
bat)中;4)更新区块索引(CblockIndex).
在k-v数据库中更新CblockIndex,CblockIndex记录着区块的磁盘存储位置以及该区块的前驱和后继区块,根据区块索引,能够得到区块链的世界状态;5)更新交易索引(TxIndex).
TxIndex存储在k-v数据库中,包含每一笔交易的磁盘存储位置以及交易的后继交易(以该交易作为输入的交易).
后继交易初始为空,标识该交易是未花费的,当该交易被花费后更新其后继交易,也是根据该标识位判断交易是否被双花;6)将写入到磁盘的交易数据从MapTransaction中移除.
Hash0~7Data0共识参数版本号前一区块时间戳Merkle根区块头区块体后一区块前一区块Hash0~3Hash4~7Hash0,1Hash2,3Hash4,5Hash6,7Hash0Hash1Hash2Hash3Hash5Hash4Hash7Hash6Data1Data2Data3Data4Data5Data6Data7Fig.
2Blockstructurediagram图2区块结构示意图TransactionnVersionTxInTxOutnLockTimepreoutScriptSignValueScripPubkTransactionnVersionTxInTxOutnLockTimepreoutScriptSignValueScripPubkFig.
3Transactionstructurediagram图3交易结构示意图在读取数据的时候,必须要提供要读取数据的hash值,根据hash值,先在内存中的MapTransaction中查找;如果没有查找到,则根据hash值到k-v数据库中查找对应索引信息TxIndex;最后,根据TxIndex在磁盘文件blk000x.
bat中读取到数据.
2676JournalofSoftware软件学报Vol.
30,No.
9,September2019(3)已有模型存在的不足已有的模型利用数字签名技术以及MerkleRoot来保证数据不可篡改和数据安全,但是其交易数据结构固定,只能处理固定结构的交易数据,不能处理一般数据,不适合传统数据库中的数据处理,缺少一般性;在进行数据读写操作时,只能够根据数据的hash值进行处理,在不知道数据hash值的情况下,无法进行数据查询操作.
3.
2面向数据库的区块链系统模型针对已有模型中的不足,本文提出一种面向数据库的区块链系统模型,将交易结构扩展到任意记录格式,为每一个区块创建一个不可篡改的索引,在保证不可篡改的同时实现高效查询,为数据的所有者赋予新的语义,并重新定义数据操作.
(1)数据结构为了能够操作更一般的数据,本文将交易结构进行了扩展,如图4所示,交易分为交易头(transaction)和数据(data)两部分:交易头包含版本号(version)、父交易哈希(PreHash)、交易时间(nTime)、交易下一拥有者公钥(ScriptPubk)、证明本交易有效的签名(ScriptSig);数据部分类似于传统数据库中的表结构,包含关键字key以及各个字段(field).
根据交易头部分实现数据的权限管理以及不可篡改和可回溯,根据数据部分记录各种类型的数据.
其中,PreHash指向相同Key的前一交易.
在进行写入数据的时候,首先查询是否存在关键字为key的交易:如果存在,则检验当前交易的SicriptSig是否与前一交易的ScriptPubk相匹配,只有在匹配的情况下,才认为交易有效;如果该key是第1次出现,则将PreHash置为0.
在进行数据读取的时候,根据key进行检索,返回最近的查询结果,但是可以根据交易中的PreHash进行溯源.
数据的修改通过写入新交易实现,所有的记录都不可删除.
TransactionDataScriptSigScripPubknTimeVersionPreHashKeyField1Field2Field3.
.
.
TransactionScriptSigScripPubknTimeVersionPreHashDataKeyField1Field2Field3.
.
.
Fig.
4Database-orientedtransactionstructure图4面向数据库的交易结构示意图区块结构与已有的大体类似,特别之处是在区块的MerkleTree中添加了关于交易key值的索引信息,使得可以从MerkleRoot根据key值直接检索到对应交易,实现了交易的可查询性;同时,索引是经由Hash运算保存在Merkle树中,保证了索引的不可篡改.
(2)数据读写流程为了实现针对于key的查询,写入数据时,在每一个区块中创建一个关于key的不可篡改索引,并将该索引记录保存在k-v数据库中;在读取数据时,根据key从区块头的MerkleRoot开始索引,在O(logN)时间内索引到交易的hash值,然后根据该hash值到k-v数据库中查询到对应的TxIndex,最后,在磁盘文件blk000x.
dat中读取交易信息.
焦通等:区块链数据库:一种可查询且防篡改的数据库26774数据操作算法4.
1MerkleRBTree索引构建区块链数据库要求其数据满足不可篡改性,则对于数据的索引自然也应该是不可篡改的.
我们定义区块一旦形成便不可修改,因此,我们对于每一个区块构造一个二叉查找树,然后将数据与二叉查找树一起做哈希运算,从而实现数据与索引的不可篡改.
我们选择红黑树和Merkle树结合,选择红黑树有以下几个原因.
1)红黑树是二叉查找树,同时也是平衡二叉树,虽然不是完美平衡,但是能够保证查询复杂度为O(logN);2)和Merkle树一样,红黑树是由下往上生长的,从而能够保证父节点是由子节点哈希得到的,在插入新节点时,父节点信息可以得到相应更新.
然而,传统索引中的记录值并不是全部存储在叶子节点,其内部节点也都存储着记录值.
然而这会在两个方面影响Merkle树的性能.
1)不利于轻量级存在性证明.
如图5所示:如果轻量级节点持有MerkleRoot即H11以及记录信息Data4,我们想证明Data4是否存在于这棵树中.
我们直接将序列{H3,H7,H9}发送给该节点,该节点计算Hash(Hash(H7,Hash(H3,Hash(Data4))),H9),如果得到的值等于H11,则证明Data4存在于这棵树中;否则不存在.
其实,存在性证明就是通过将孩子节点两两哈希得到父亲节点,通过判断父亲节点是否相同来验证孩子节点的正确性.
这就要求我们可以由孩子节点哈希得到父亲节点,但是如果父亲节点存放了与孩子节点无关的记录,我们便无法根据孩子节点哈希得到父亲节点,也便无法进行存在性证明;812515105810121516H1=H(Data1)H2=H(Data2)H4=H(Data4)H3=H(Data3)H5=H(Data5)H6=H(Data6)H7H7=H(H1,H2,5)H8=H(H3,H4,10)H9=H(H5,H6,15)H10=H(H7,H8,8)H11=H(H10,H9,12)H11H10H8H9H1H2H3H4H5H6Data1Data2Data3Data4Data5Data6Fig.
5MerkleRBTreelogicalstructure图5MerkleRBTree逻辑结构图2)不利于分支删减,不能节省磁盘空间.
考虑到这样一种情景:Data1,Data2,Data3,Data4已经被修改过多次,而Data5,Data6则很少被修改,根据第2节对于修改记录的描述可知:前面4个数据项已经有了很多后继,相当于非常久远的版本;而后两个数据项还是属于较新的版本.
我们希望可以删除Data1~Data4但是不影响后续对于Data5,Data6的查询验证等操作.
如果数2678JournalofSoftware软件学报Vol.
30,No.
9,September2019据项都存在叶子节点,我们可以通过删除Data1~Data4只保留H10来节省磁盘空间而不影响树的功能;但是如果有数据记录存放在分支节点,我们便无法删除分支节点来节省磁盘空间,因为那样会影响树的功能(无法对剩余分支进行存在性证明).
因此,我们将索引内部节点的记录值往左下方移动,直到叶子节点为止,从而使得记录值只存放在叶子节点.
在实现上,就是将小于等于节点关键字的记录存储在左子树,大于关键字的记录存放在右子树,中间节点只存放关键字和子节点hash值.
如图5所示,共有6条记录项:Data1,Data2,…,Data6,每个记录项都有一个关键值分别为5,8,10,12,15,16.
按照关键值顺序将记录项存储到叶子节点中.
分支节点中存放着左右子树的哈希值以及关键字,同时保证该节点的左子树中的关键值都小于等于该节点的关键值,右子树中的关键值都大于该节点关键值.
4.
2基于索引的数据操作算法(1)数据插入算法根据数据结构定义,节点结构如下.
structNode{Keykey;//节点关键字Nodeleft;//左右孩子节点Noderight;Uint256lefthash;//左右孩子节点哈希值Uint256righthash;Valvalue;Boolcolor;//标记节点颜色(红黑)}叶子节点包含交易信息,中间分支节点存储索引信息.
如果节点是分支节点,其lefthash和righthash分别为左右孩子节点哈希,key值等于左子树最大关键值.
如果节点是叶子节点,其左右子树为空,为了区别于分支节点,其lefthash为0,righthash等于交易哈希值,value为交易记录.
节点的哈希值定义为Hash(Node)=Hash(lefthash,righthash,key).
我们从根节点开始插入数据,如果关键值小于等于根节点,则插入到其左子树;如果大于,则插入到右子树,直到最后一层分支节点h,根据如下所述4种情况分别在该节点处插入新值.
情况1:如果该分支节点为空(只在MerkleRoot为空时出现),先新建一个叶子节点存放(key,value)数据,然后新建一个分支节点,并定义其左孩子为叶子节点,关键值为key,左哈希为叶子节点哈希值.
插入结果如图6(a)所示.
这也说明了一棵树只要不为空,则其分支节点一定不为空,而且最后一层分支节点的key值一定与其左孩子key值相同;情况2:如果待插入数据key值小于该节点key值,我们应该将该数据插入到该节点左侧,但是由情况1可知:该节点左孩子一定不为空,而且是叶子节点.
为此,我们新建一个叶子节点存放待插入的(key,value)数据,然后新建一个分支节点,其关键字为待插入节点key,左孩子为新建的叶子节点,右孩子为原来分支节点的左孩子,父节点为原分支节点,插入结果如图6(b)所示,其中,连接和分支节点用虚线表示;情况3:如果待插入数据key值大于该节点,而且该节点右孩子为空,则直接新建叶子节点存储数据,并将其定义为分支节点右孩子,插入结果如图6(c)所示;情况4:如果待插入数据key值大于该节点,而且该节点右孩子不为空,我们先新建叶子节点存储数据,然后新建分支节点,分支节点关键值为待插入数据key值与原分支节点右孩子key值中的较小者,左孩子为待插入数据与原分支节点右孩子中key值较小者,右孩子为较大者,父节点为原分支节点,插入后结果如图6(d)所示.
焦通等:区块链数据库:一种可查询且防篡改的数据库2679H,_,55Val1457454567(a)空节点插入结果(b)左侧插入结果(c)右孩子为空右侧插入结果(d)右孩子不为空右侧插入结果添加红黑树旋转规则4567H,_,5H,H,5H,H,4H,H,4Val2Val1Val3Val1Val2H,H,5H,H,6H,H,4Val2Val1Val4Val3H,H,5H,H,4H,H,6Val2Val1Val4Val3Fig.
6Exampleoflastlayerbranchnodeinsertion图6最后一层分支节点插入示例算法1.
数据插入算法.
输入:根节点h,插入记录关键值key,插入数据值value;输出:根节点.
1.
Nodeput(Nodeh,Keykey,Valueval)2.
if(h==null)//空节点3.
insert_1(key,val);//按照情况1添加节点4.
if(keyh.
key){8.
if(h.
right==null),insert_3(key,val);9.
if(h.
right!
=null&&h.
right.
left==null),insert_4(key,val);10.
elseh.
right=put(h.
right,key,val);}//右下方移动11.
if(isRed(h.
right)&&!
isRed(h.
left)),h=rotateLeft(h);//添加红黑树旋转规则12.
if(isRed(h.
left)&&isRed(h.
left.
left)),h=rotateRight(h);13.
if(isRed(h.
left)&&isRed(h.
right)),flipColors(h);14.
h.
lefthash=Hash(h.
left);15.
h.
righthash=Hash(h.
right);16.
returnh;算法1的第2行、第3行是区块为空时的初始插入操作;第4行~第6行是当插入key值小于节点key值时,如果该节点左孩子是最后一层分支节点,则按照之前所述情况2插入数据;否则,以左孩子节点为当前节点递归插入数据;第7行~第10行是当插入key值大于节点key值时:如果右孩子为空,则该节点是最后一层分支节点,按照情况3插入数据;如果右孩子不为空,且是最后一层分支节点,则按照情况4插入数据;否则,以右孩子为当前节点,递归插入数据;第11行~第13行添加红黑树旋转规则,保证该树黑色平衡;2680JournalofSoftware软件学报Vol.
30,No.
9,September2019第14行、第15行更新节点哈希值.
数据插入之后,我们得到从根节点开始的二叉搜索树,而每个节点的哈希值即Hash(lefthash,righthash,key)又完全映射成一个基于哈希的不可篡改索引.
数据是先写入到内存区块当中,当内存区块大小到达一定的阈值,则将该区块顺序写入到磁盘中,将其对应的MerkleRBIndex存储到k-v数据库中.
数据库中存储格式:k=Hash(lefthash,righthash,key),v=(lefthash,righthash,key).
为了便于理解,可以认为MerkleRBIndex对应一个map集合mapMerkleIndex.
(2)数据查找算法根据之前创建的索引,我们可以提供一种针对关键字key的查询方法,并且根据Merkle树的特性,提供对应该查询结果的验证路径,使得轻量级客户端可以根据极少量信息去自我验证查询结果的正确性.
当输入关键值key时,首先在内存区块中检索,如果检索不到,就加载k-v数据库中上一区块的MerkleRBIndex索引,直到检索到该数据项或者不存在该记录.
当在特定区块中检索的时候,首先从MerkleRoot节点开始检索,如果目标关键字小于等于根节点关键字,则在mapMerkleIndex中查找k为root.
lefthash的目录,其对应的v则为下次要比对的对象;否则,查找root.
righthash.
最后,查询锁定在叶子节点,如果叶子节点的关键值等于目标关键值则查询成功;否则,记录不存在该区块中.
算法2.
数据查找算法.
输入:关键值key,索引mapHash(lefthash,righthash,key),lefthash,righthash,keymmap;输出:节点哈希值以及验证路径Vectorhash,keypath.
1.
Vectorhash,keyquery(key,merkleroot,txhash=0)2.
hash=merkleroot;3.
while(mmap[hash].
lefthash!
=0){//向下检索直到叶子节点4.
if(keyBrandoffJ,PrestwichJ,HallG,GerbesP,HutchinsP,PollardC.
Storj:Apeer-to-peercloudstoragenetwork.
2016.
https://storj.
io/white-paper[13]TuanT,DinhA,WangJ,ChenG,LiuR,OoiBC,TanKL.
Blockbench:Aframeworkforanalyzingprivateblockchains.
In:Proc.
oftheSIGMODConf.
Chicago:ACMPress,2017.
10851100.
[doi:http://dx.
doi.
org/10.
1145/3035918.
3064033][14]TsaiWT,YuL,WangR,LiuN,DengEY.
Blockchainapplicationdevelopmenttechniques.
RuanJianXueBao/JournalofSoftware,2017,28(6):14741487(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/5232.
htm[doi:10.
13328/j.
cnki.
jos.
005232][15]LiY,ZhengK,YanY,LiuQ,ZhouXF.
EtherQL:Aquerylayerforblockchainsystem.
In:Proc.
oftheInt'lConf.
onDatabaseSystemsforAdvancedApplications.
Suzhou:Springer-Verlag,2017.
556567.
[doi:10.
1007/978-3-319-55699-4_34][16]BeijingPeerSafeTechnologyCo.
,Ltd.
Whitepaperforblockchaindatabaseapplicationplatform.
2017.
http://blockchain.
peersafe.
com/PDF/ChainSQL-whitepaper.
pdf[17]JohnsonD,MenezesA,VanstoneS.
Theellipticcurvedigitalsignaturealgorithm(ECDSA).
Int'lJournalofInformationSecurity,2001,1(1):3663.
[doi:10.
1007/s102070100002]附中文参考文献:[1]袁勇,王飞跃.
区块链技术发展现状与展望.
自动化学报,2016,42(4):481494.
[doi:10.
16383/j.
aas.
2016.
c160158]焦通等:区块链数据库:一种可查询且防篡改的数据库2685[2]何蒲,于戈,张岩峰,鲍玉斌.
区块链技术与应用前瞻综述.
计算机科学,2017,44(4):17,15.
[doi:10.
11896/j.
issn.
1002-137X.
2017.
04.
001][14]蔡维德,郁莲,王荣,刘娜,邓恩艳.
基于区块链的应用系统开发方法研究.
软件学报,2017,28(6):14741487.
http://www.
jos.
org.
cn/1000-9825/5232.
htm[doi:10.
13328/j.
cnki.
jos.
005232]焦通(1994-),男,山东临沂人,硕士,主要研究领域为分布式数据管理,区块链.
寇月(1980-),女,博士,副教授,CCF专业会员,主要研究领域为实体搜索,数据挖掘.
申德荣(1964-),女,博士,教授,博士生导师,CCF高级会员,主要研究领域为分布式数据管理,数据集成.
李晓华(1969-),女,博士,讲师,CCF专业会员,主要研究领域为大图数据查询,区块链.
聂铁铮(1980-),男,博士,副教授,CCF专业会员,主要研究领域为数据质量,数据集成,区块链.
于戈(1962-),男,博士,教授,博士生导师,CCF会士,主要研究领域为数据库,大数据管理.