Page 294 - 《软件学报》2020年第9期

张志威 等:区块链的数据管理技术综述 2915

有者、添加可访问用户、进行溯源查询等.同时,该合约要求所有对指定文件的更改需经过投票过程.参与投票
的用户由数据拥有者确定.对数据的任意一次更改需至少半数以上的用户投票同意才可进行.在这种环境下,恶
意的用户若对数据进行恶意篡改,需控制半数以上参与投票的用户.同时,由于所有的修改均利用部署的智能合
约,因而对数据的溯源查询转化为对智能合约调用的查询.
部分工作研究区块链查询处理语,使其与数据库的 SQL 查询语句类似 [86−88] ,文献[88]提出了 SEBDB,并设
计了与数据库 SQL 语句类似的查询语句,使之可以完成在区块链中对关系型表的建表、插入、选择等操作.在
SEBDB 中,数据分别采用链上链下存储方式.链下存储的数据由一个本地关系型数据库进行管理.针对链上与
链下的数据, SEBDB 设计了包括连接操作等语句.当只需要链下数据进行连接操作时,SEBDB 可以直接利用本
地数据库的 Join 语句来进行.当需要链上链下数据同时进行连接时,SEBDB 首先扫描链上数据,并利用 hash-join
的方法将其与链下数据进行连接.为了提高查询效率,SEBDB 设计了区块层级的 B+-Tree.SEBDB 利用区块 ID、
事务 ID 以及时间戳作为每一个 B+-Tree 里面数据的排序键值.当给定区块 ID、事务 ID 或者时间戳时,可利用
区块级的 B+Tree,快速找到存储相应数据的区块.同时,SEBDB 建立表与区块的索引,即每个表的索引指向所有
包含对该表进行操作的事务的区块.利用以上索引,使得对链上数据的访问不需扫描所有区块.文献[89]在
SEBDB 基础上,通过建立数据的视图,进一步提高其查询效率.
4.2 可信查询处理
考虑到区块链应用在不可信的环境下,当用户提交查询并获得查询结果时,往往需验证其查询结果的可信
性 [90−93] .文献[94]提出了一个区块链系统 vChain,实现了高效的可验证查询处理算法.该系统假定用户节点并不
一定存储整个区块链的全部数据,而是只存储所有区块中的哈希值.由于一个区块的哈希值所占的存储空间远
远小于区块内存储事务所花费的空间,因而该假设即使在轻量级的硬件环境下也可实现.为了验证查询结果,在
每个区块中添加一个额外的命名为 AttDigest 的字段.具体而言,AttDigest 由多集合加密累加器(cryptographic
multiset accumulator)所生成.所生成的 AttDigest 具有如下性质:给定同一公钥,当需验证两个集合的交集是否为
空时,可以通过各自的 AttDigest 直接验证.利用该性质,当查询条件可以表达为集合交集的形式时,可利用返回
结果的 AttDigest 与查询条件中集合的 AttDigest 进行比较,来确定返回的结果与查询的条件是否存在交集.如果
发现二者不存在交集的关系,则验证查询结果和查询条件不匹配.
文献[94]进一步将该方法推广到范围查询.范围查询中,用户会对值域为数字的属性给定一个区间.查询结
果返回在该区间中满足条件的数据.当验证范围查询的查询结果时,无法直接将 AttDigest 应用到范围查询中.
其原因在于,AttDigest 只适用于判定集合的关系.因此,作者将范围查询转化为集合查询.具体而言,首先,vChain
将所有数字以二进制形式进行标识,并将其视作字符串.利用二进制表示,vChain 构建了前缀树来表示所有数
字.每个叶子节点是一个具体的数字,而非叶子节点对应一个数字的范围.当一个查询中包含范围条件时,该范
围对应前缀树的一部分连续的叶子节点.因此,可将其转化为基于前缀的集合表示形式.例如,当查询范围为
[0,6],且该属性数据的范围为[0,7]时,其对应的表达形式可为 0*∩10*∩110.符号*表示二进制的 0 或 1.基于此集
合表示,则可以将 AttDigest 的签名同样应用于范围查询.
同时,为了提高验证效率,vChain 提出了区块内以及区块间的索引.区块内的索引为一种类似于默克尔树的
结构.树中的每一个节点包含 3 个域,分别为左子树哈希值、右子树的哈希值和集合属性所包含的元素.利用该
树结构,查询处理可以看作对树的搜索.当搜索到树中节点时,如果该节点的集合的 AttDigest 不满足查询条件,
则不需要继续搜索该节点的子节点.同样的思想也被用来建立区块间的索引.vChain 将区块按照指数递增的方
式来分段.例如,每段区块域包含的区块的个数分别为 2,4,8 等.每一个区块域均计算相应的 AttDigest.当一个区
块域所包含的所有集合元素所产生的 Attigest 均不满足查询条件时,则整个区块域可以不被搜索.利用区块内以
及区块间的索引,vChain 提高了查询验证的效率.
同样针对范围查询,文献[95]研究在以太坊框架下,查询结果验证的开销问题.开销是指在以太坊框架下,执
行操作所产生的 gas 开销.在以太坊的框架下,当用户需要存储以及执行智能合约时,需要支付相应的 gas.gas 可
由以太币兑换.在智能合约中,不同的操作需要支付不同数量的 gas.例如,从区块中读数据需要 200gas,更新操作