随着比特币、以太币等一系列加密货币的兴起,其底层的区块链技术受到越来越广泛的关注.区块链有防篡改、去中心化的特性.以太坊利用区块链技术来构建新一代去中心化的应用平台.BigchainDB将区块链技术与传统的分布式数据库相结合,利用基于联盟投票的共识机制改进传统Pow机制中的节点全复制问题,提高了系统的扩展性与吞吐率.但是现有的区块链系统存储的信息大都是固定格式的交易信息,虽然在每个交易里有数据字段,但是现有的区块链系统并不能经由链上对交易内的数据字段的具体细节进行直接查询.如果想要查询数据字段的具体细节,只能先根据交易的哈希值进行查询,得到该交易的完整信息,然后再检索该交易内的数据信息.数据可操作性低,不具备传统数据库的查询功能.首先提出一种区块链数据库系统框架,将区块链技术应用于分布式数据管理;其次提出一种基于哈希指针的不可篡改索引,根据该索引快速检索区块内数据,以此实现区块链的查询;最后,通过实验测试数据库的读写性能,实验结果表明,所提出的不可篡改索引在保证不可篡改的同时具有较好的读写性能.
With the rise of a series of crypto-currencies, such as Bitcoin and Ether, the underlying blockchain technology has received more and more attention. The blockchain is known as the characteristics of decentralization and immutability. Ethereum utilizes the blockchain technology to build the next generation decentralized application platform. BigchainDB combines blockchain technology with traditional distributed databases, and uses the federal based voting to improve the traditional PoW mechanism and finally improves the system's scalability and throughput. However, the existing blockchain system mostly stores transaction information with a fixed-form. Although there are data fields in each transaction, the existing blockchain system cannot directly query the specific details within the data fields of the transaction data from the blockchain data. To query the specific details of the data field, it must query the transaction first with the hash value of the transaction to get the complete information of the transaction, and then retrieve the details in the transaction data. This mechanism has a low operability of data and a lack of query functions of the traditional database. This study first proposes a framework of blockchain database system, which applies blockchain technology to distributed data management. Then, an immutable index is proposed based on hash functions. According to the index, the data in the block can be quickly retrieved to implement the query processing in the blockchain. Finally, experiments are designed to test the database's read/write performance. The experimental results show that the immutable index has good read/write performance while ensuring immutability.
随着比特币、以太币等一系列加密货币的兴起, 其底层的区块链技术也受到了越来越广泛的关注[
而区块链技术具有去中心化、防篡改以及可回溯的特性, 为解决上述这些问题提供了可能.为此, 我们提出了区块链数据库的概念, 核心思想是:通过限制中心机构对数据记录的操作, 来达到防篡改和去中心化的目的.该数据库中有多条区块链, 每一条区块链相当于传统数据库中的一张表, 所有的中心机构充当数据的存储节点, 所有的存储节点根据共识算法生成区块链, 所有节点(包括用户)存储区块头信息, 可以由区块头信息检索到记录并验证记录的正确性.我们希望有高效的共识算法来提高系统的吞吐率, 并有高效的查询算法实现在区块链上检索数据.当前, 在共识算法上已经有很多研究, 例如POW[
本文首先提出了区块链数据库系统框架, 将区块链技术应用于数据管理; 其次, 提出了一种基于哈希指针的不可篡改索引, 根据该索引快速检索区块内数据, 以此实现区块链的查询; 最后, 通过实验测试数据库的读写性能, 实验结果表明, 本文提出的不可篡改索引在保证不可篡改的同时具有较好的读写性能.
文献[
文献[
比特币、以太坊和超级账本三大应用平台的主要功能是针对数字货币与智能合约, 但是数据管理性能较弱, 一些机构发现了区块链不可篡改、去中心化与数据可回溯特性, 力图将区块链技术与传统的数据库技术相结合, 提升数据管理的性能, 同时兼顾区块链去中心化、数据可回溯、防篡改的特性.
文献[
通过结合区块链和数据库技术, 提出一种去中心化、防篡改同时支持查询的区块链数据库框架.如
● 存储层:在最底部, 为
● 网络层:是该框架的核心, 负责节点间的数据传输以及根据共识协议确定区块的先后顺序.其中, 节点由存储节点以及用户组成, 每一机构为一个存储节点, 用于存储本机构的数据信息, 可以是一个数据库, 也可以是多个数据库.当添加或者修改用户相关的数据时, 需要由用户和机构共同签名认可; 签名后的数据由机构封装到区块中, 当区块大小达到某一阈值时, 将其打包发送给其他机构进行验证.机构间根据共识算法验证区块的正确性, 并决定区块的先后顺序.将验证正确的区块发送给存储节点存储, 将区块头广播给所有节点, 包括用户.在进行查询操作时, 用户向存储节点发送查询请求, 存储节点会返回查询到的记录项以及查询路径, 用户根据查询路径以及区块头信息, 可以验证查询结果的正确性;
● 区块链层:显示的是区块链的“世界状态”, 上层应用可以据此对区块链数据进行查询操作;
● 应用层:是最上层, 可以对查询到的数据进行进一步的分析处理.
针对这一框架, 本文重新定义了数据库中的数据结构以及数据操作, 并提出了Merkle RBTree索引, 基于哈希指针构建不可篡改的索引, 在保证不可篡改的前提下实现高效查询.系统中数据的操作定义如下.
● 增加记录:数据在初次添加时, 数据拥有者指定可以进行数据写操作的公钥, 生成权限锁定脚本, 然后用自己的私钥对该数据进行签名;
● 修改记录:操作者用自己的私钥对其父记录进行签名, 然后验证该签名是否能够解锁父记录的锁定脚本, 当且只当在解锁锁定脚本的情况下, 才可以添加一条相同
● 查找记录:所有的参与者都可以进行查找操作, 查找操作返回最新值为有效值, 但是可以通过溯源操作查看该记录的完整修改历史;
● 删除记录:数据一旦添加便不可删除, 当数据已经被修改多次, 处于非常古老的版本时, 为了节约磁盘空间, 可以删除该数据的具体信息, 但是该数据的哈希值则需要永久保存.
区块链数据库系统框架
Blockchain database system framework
(1) 数据结构
为了能够较好地理解区块链的结构, 我们给出了哈希指针的定义.一个数据项的哈希指针是指将该数据项的内容做哈希操作后得到固定长度的哈希值, 同时以该哈希值为
区块链就是一个个的区块根据哈希指针首尾相连, 每一个区块一旦形成便不可改变.如
如
(2) 数据读写流程
对于数据的存储管理, 在写入数据时, 每个区块的数据操作流程如下.
1) 收集交易.将未写入到区块内的交易数据进行正确性检查(包括格式检查以及双花检查), 并将有效的交易数据收集在集合(MapTransaction)中, 其中, MapTransaction只存放在内存中, 其内存放了从交易哈希到交易的map映射;
2) 创建区块.将MapTransaction中的数据添加到区块体中; 之后运行PoW机制, 搜索合适的随机数值, 使得区块头的哈希值小于目标哈希, 从而证明该区块有效, 即挖矿成功并获得奖励;
3) 存储区块.在网络上将该区块广播, 在本地将该区块顺序存储在本地磁盘文件(blk000x.bat)中;
4) 更新区块索引(CblockIndex).在
5) 更新交易索引(TxIndex).TxIndex存储在
6) 将写入到磁盘的交易数据从MapTransaction中移除.
区块结构示意图
Block structure diagram
交易结构示意图
Transaction structure diagram
在读取数据的时候, 必须要提供要读取数据的
(3) 已有模型存在的不足
已有的模型利用数字签名技术以及MerkleRoot来保证数据不可篡改和数据安全, 但是其交易数据结构固定, 只能处理固定结构的交易数据, 不能处理一般数据, 不适合传统数据库中的数据处理, 缺少一般性; 在进行数据读写操作时, 只能够根据数据的
针对已有模型中的不足, 本文提出一种面向数据库的区块链系统模型, 将交易结构扩展到任意记录格式, 为每一个区块创建一个不可篡改的索引, 在保证不可篡改的同时实现高效查询, 为数据的所有者赋予新的语义, 并重新定义数据操作.
(1) 数据结构
为了能够操作更一般的数据, 本文将交易结构进行了扩展, 如
面向数据库的交易结构示意图
Database-oriented transaction structure
区块结构与已有的大体类似, 特别之处是在区块的MerkleTree中添加了关于交易
(2) 数据读写流程
为了实现针对于
区块链数据库要求其数据满足不可篡改性, 则对于数据的索引自然也应该是不可篡改的.我们定义区块一旦形成便不可修改, 因此, 我们对于每一个区块构造一个二叉查找树, 然后将数据与二叉查找树一起做哈希运算, 从而实现数据与索引的不可篡改.
我们选择红黑树和Merkle树结合, 选择红黑树有以下几个原因.
1) 红黑树是二叉查找树, 同时也是平衡二叉树, 虽然不是完美平衡, 但是能够保证查询复杂度为
2) 和Merkle树一样, 红黑树是由下往上生长的, 从而能够保证父节点是由子节点哈希得到的, 在插入新节点时, 父节点信息可以得到相应更新.
然而, 传统索引中的记录值并不是全部存储在叶子节点, 其内部节点也都存储着记录值.然而这会在两个方面影响Merkle树的性能.
1) 不利于轻量级存在性证明.
如
MerkleRBTree逻辑结构图
MerkleRBTree logical structure
2) 不利于分支删减, 不能节省磁盘空间.
考虑到这样一种情景:
因此, 我们将索引内部节点的记录值往左下方移动, 直到叶子节点为止, 从而使得记录值只存放在叶子节点.在实现上, 就是将小于等于节点关键字的记录存储在左子树, 大于关键字的记录存放在右子树, 中间节点只存放关键字和子节点
如
(1) 数据插入算法
根据数据结构定义, 节点结构如下.
struct Node{
Key
Node
Node
Uint256
Uint256
Val
Bool
}
叶子节点包含交易信息, 中间分支节点存储索引信息.如果节点是分支节点, 其
我们从根节点开始插入数据, 如果关键值小于等于根节点, 则插入到其左子树; 如果大于, 则插入到右子树, 直到最后一层分支节点
● 情况1:如果该分支节点为空(只在MerkleRoot为空时出现), 先新建一个叶子节点存放(
● 情况2:如果待插入数据
● 情况3:如果待插入数据
● 情况4:如果待插入数据
最后一层分支节点插入示例
Example of last layer branch node insertion
输入:根节点
输出:根节点.
1. Node
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
● 算法1的第2行、第3行是区块为空时的初始插入操作;
● 第4行~第6行是当插入
● 第7行~第10行是当插入
● 第11行~第13行添加红黑树旋转规则, 保证该树黑色平衡;
● 第14行、第15行更新节点哈希值.
数据插入之后, 我们得到从根节点开始的二叉搜索树, 而每个节点的哈希值即
为了便于理解, 可以认为MerkleRBIndex对应一个map集合
(2) 数据查找算法
根据之前创建的索引, 我们可以提供一种针对关键字
当输入关键值
输入:关键值
输出:节点哈希值以及验证路径
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
● 算法2的第2行初始化当前查找
● 第3行~第9行向下检索直到叶子节点, 其中:第4行~第6行是如果目标
● 第10行~第14行是检验叶子节点是否包含目标
在
本文提出的索引结构能够让索引自我检测索引的正确性和完整性.在区块内检索数据的过程, 就是对
(3) 数据验证算法
不仅存储节点可以在查询的时候检测到索引的正确性和完整性, 而且用户节点可以在接收到查询结果之后对查询进行验证.如第2节所述:用户节点存有区块头信息, 而区块头当中有MerkleRoot值, 用户根据查询结果和验证路径, 对路径上的值两两哈希生成查询结果对应的MerkleRoot值, 用户通过比较该值是否与自己保存的区块头中的MerkleRoot值相同, 从而验证查询的正确性.而且查询路径的长度对应交易在二叉查找树中的深度, 对于含有
输入:交易信息
输出:true or false.
1. boolean
2.
3.
4.
5.
6.
7.
8.
算法3的第2行计算交易哈希值; 第3行~第5行根据验证路径, 从该交易开始向上重新生成父节点, 最后生成根节点; 第6行~第8行比对根据验证路径生成的根节点值与本地保存的根节点值, 如果相同, 则查询有效.
实验的硬件环境是Intel(R)Core(TM) i5-6500 CPU(3.2GHz), RAM为8Gb的PC机, 操作系统为Windows10.借助Bitcoin的开源代码v0.1.0版本构建了一个区块链数据库, 实验中主要修改了Bitcoin的底层数据结构, 包括交易格式以及在区块中交易的组织形式, 其中:交易格式扩展为支持更一般的数据格式, 交易的组织形式由Merkle树改为MerkleRBTree; 保留了非对称加密技术以及UTXO的思想, 类比Bitcoin中的公钥与私钥脚本结合形成价值传递轨迹, 本实验中利用公钥私钥脚本结合形成数据的修改轨迹, 并且利用该轨迹进行数据溯源.需要说明的是, 本文的主要研究点是对于区块链数据的索引方法, 不涉及网络以及共识协议, 故在实验时利用单机进行测试, 并将共识替换为检查交易的合法性, 将有效交易存入到区块中, 当区块大小达到阈值, 则将整个区块存入磁盘.在本节中, 我们设计多组实验来测试本文所提出的不可篡改索引的性能, 实验中的主要指标为算法的运行时间, 并将算法独立运行30次的平均值定义为算法的运行时间.
● 实验1:MerkleRBTree的性能测试
在比特币中生成区块时, 需要对交易两两哈希得到MerkleRoot.本文的模型中将MerkleTree替换成MerkleRBTree, 在得到MerkleRoot的同时生成对应的索引.我们设计实验测试了在区块交易数为26, 27, …, 216时对应的索引构建的时间代价.如
● 实验2:区块大小对于交易平均写入时间以及内存消耗的影响
交易到内存之后, 需要等到形成一个完整区块才能存入到磁盘, 这就使得第1个进入到区块的交易和最后一个进入区块的交易有时间差, 故在此取多个交易的平均时间.在这里, 用交易数来度量区块大小, 分别设置区块中最大交易数量为64, 128, 256, 512, 1024, 2048, 4096, 8192, 设置交易的字段数为3.如
MerkleRBTree和MerkleTree构建代价对比
MerkleRBTree and MerkleTree build cost comparison
区块大小对内存和写入时间的影响
Impact of block size on memory and write time
● 实验3:
现有的区块链系统只能根据交易哈希值进行查询, 哈希值形如“1ef4c1a9c62aa236766d2864c4c0f2d609aa83 d4f256dc35962a603a6832a476”抽象且与数据没有直接关联.本文实现了针对数据关键字
Comparison of
● 实验4:区块深度对于查询时间的影响
数据在存储时是按照写入顺序依次添加到区块中, 区块顺序写入磁盘.我们设计的实验测试了数据写入先后顺序对于查询的影响.实验中顺序写入50万条
区块深度对于查询时间的影响
Block depth influence on query time
● 实验5:数据溯源性能测试
区块链的特性之一就是数据可回溯, 即返回任意数据的完整修改历史.我们设计实验测试了数据版本数对于溯源时间的影响, 分别设置7条区块链, 每条链的区块个数依次为10, 20, 30, 40, 50, 60, 70, 区块中交易个数固定为1 024, 交易的字段数固定为3, 字段值为
版本数对于查询时间的影响
Impact of version number on query time
本文首先提出了一种区块链数据库模型, 将区块链技术应用于数据管理; 其次提出了一种基于哈希指针的树型索引结构, 用于管理区块内的记录项, 并由此实现查询; 最后, 通过实验测试数据库的读写性能.实验结果表明:本文提出的不可篡改索引在保证不可篡改的同时, 具有较好的读写性能.同时, 本文提出的针对
当下人们对于数据安全的要求越来越高, 区块链凭借着安全不可篡改的特性, 必然会有出色的表现.然而要构建一个成熟的区块链数据库还需要一些后续工作.
(1) 利用高效的共识算法提升系统的吞吐率;
(2) 利用智能合约管理每一个数据项的读写权限, 保证只有拥有者授权的公钥可以访问和修改数据.
Yuan Y, Wang FY. Blockchain:The state of the art and future trends. Acta Automatica Sinica, 2016, 42(4):481-494(in Chinese with English abstract).[doi:10.16383/j.aas.2016.c160158]
袁勇, 王飞跃.区块链技术发展现状与展望.自动化学报, 2016, 42(4):481-494.[doi:10.16383/j.aas.2016.c160158]
He P, Yu G, Zhang YF, Bao YB. Survey on blockchain technology and its application prospect. Computer Science, 2017, 44(4):1-7, 15(in Chinese with English abstract).[doi:10.11896/j.issn.1002-137X.2017.04.001]
何蒲, 于戈, 张岩峰, 鲍玉斌.区块链技术与应用前瞻综述.计算机科学, 2017, 44(4):1-7, 15.[doi:10.11896/j.issn.1002-137X.2017. 04.001]
https://bitcoin.org/bitcoin.pdf]]>
Sleiman MD, Lauf AP, Yampolskiy R. Bitcoin message:Data insertion on a proof-of-work cryptocurrency system. In:Proc. of the Int'l Conf. on Cyberworlds. Visby:IEEE Computer Society, 2015. 332-336.[doi:10.1109/CW.2015.56]
Bentov I, Lee C, Mizrahi A, Rosenfeld M. Proof of activity:Extending bitcoin's proof of work via proof of stake. ACM Sigmetrics Performance Evaluation Review, 2014, 42(3):34-37.[doi:10.1145/2695533.2695545]
Kiayias A, Russell A, David B, Oliynykov R. Ouroboros:A provably secure proof-of-stake blockchain protocol. In:Proc. of the Int'l Cryptology Conf. Santa Barbara:Springer-Verlag, 2017. 357-388.[doi:10.1007/978-3-319-63688-7_12]
Castro M, Liskov B. Practical Byzantine fault tolerance and proactive recovery. ACM Trans. on Computer Systems, 2002, 20(4):398-461.[doi:10.1145/571637.571640]
https://github.com/ethereum/wiki/wiki/White-Paper]]>
Androulaki E, Barger A, Bortnikov V, et al. Hyperledger Fabric:A distributed operating system for permissioned blockchains. In:Proc. of the EuroSys Conf. Porto:ACM Press, 2018. 30:1-30:15.[doi:https://doi.org/10.1145/3190508.3190538]
https://arxiv.org/pdf/1702.02799.pdf]]>
https://www.bigchaindb.com/whitepaper]]>
https://storj.io/white-paper]]>
http://dx.doi.org/10.1145/3035918.3064033]]]>
http://www.jos.org.cn/1000-9825/5232.htm[doi:10.13328/j.cnki.jos.005232]]]>
http://www.jos.org.cn/1000-9825/5232.htm [doi:10.13328/j.cnki.jos.005232]]]>
Li Y, Zheng K, Yan Y, Liu Q, Zhou XF. EtherQL:A query layer for blockchain system. In:Proc. of the Int'l Conf. on Database Systems for Advanced Applications. Suzhou:Springer-Verlag, 2017. 556-567.[doi:10.1007/978-3-319-55699-4_34]
http://blockchain.peersafe.com/PDF/ChainSQL-whitepaper.pdf]]>
Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm (ECDSA). Int'l Journal of Information Security, 2001, 1(1):36-63.[doi:10.1007/s102070100002]