GEM2 -Tree: A Gas-Efficient Structure for Authenticated Range Queri

GEM2 -Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain

为什么要使用混合存储区块链

Owing to its immutability property and consensus protocol, blockchain offers a new solution for trusted storage and computation services.

如今数据通常都是非常大的，直接将原始数据上链是不可伸缩的。为了解决这个问题，通常的方法就是采用一个混合存储架构。

在之前的混合存储架构中，链上只存储少量的数据，大量的原始数据在链下存储，当需要验证数据的完整性时，可以在线构建一个加密证明，用于查询存储在系统中的数据。但是，只支持最简单的键值查询。

本文研究的重点是 在混合存储区块链 中研究 身份验证的范围查询。难点在于如何设计出一个认证数据结构（ADS）, 它可以高效的被区块链维护并且只消耗少量的 gas。

通过分析现有的技术，文章提出了一种新的 ADS，称为 GEM2-Tree，不仅节省 gas，而且还支持高效的身份认证查询。为了在不牺牲查询性能的前提下，进一步的节省 ADS 维护成本，文章设计出了一个两层索引结构的优化架构，称为 GEM2*-Tree。

GEM2-Tree

在区块链中 写操作 比 读操作 消耗的资源更大，为了节省 gas 的消耗，设计的主要思想就是用读操作和计算代替写操作。

在设计过程中，区块链上并不是维护一个单一的全树结构，而是维护多个 部分树（partial tree），同时可以通过插入更多数据对象合并它们。尽管查询身份验证将招致更多读取，但这有助于降低 update 成本。

在实际使用过程中，区块链只是起到一个验证结果的作用，因此，在区块链中，GEM2-Tree 中的中间节点被删除了。当需要维护根 Hash 来验证结果时，可以动态的计算出来。

系统模型

当前系统中有四个部分组成：数据拥有者（DO）、区块链、云服务提供者（SP）以及查询客户端

过程

DO 会持续不断的向区块链和 SP 发送数据，原始的数据存放在链下的 SP 中，同时将每个数据对象的 hash 存放到区块链上作为原始数据的公证。

区块链 和 SP 都会根据插入的数据生成相应的 MB-Tree，生成的算法都是相同的，因此，SP 和 链上的智能合约拥有两个相同的 MB-Tree 。

查询客户端需要数据查询时，首先向 SP 进行查询，SP 会返回 查询结果 以及 相应的证明。查询客户端就可以使用查询结果和相应的证明通过区块链验证数据真伪。

插入/添加 算法

下方的图表示区块链和 SP 中的结构。 pi 代表着每个 partical。实线框表示要存储下来的数据，虚线框表示中间的计算结果，不会存储。

1606460303(1)暂时无法显示

接下来，说一下p1,...pi 的生成过程。区块链中维护了多个 partical ，一个 partical 中包含一个或两个 SMB-Tree。下图中是模仿了文章中的树的生成过程做的一张图，下图中 绿色框 代表着一个 partical ，下图中的每个树都代表着 SMB-Tree 。

绿色的圆圈 代表着原始数据的 Hash，蓝色圆圈代表着包含根hash的中间节点。在区块链中，只保存和维护 原始数据 Hash 和根 Hash。

GEM2-Tree_插入暂时无法显示

跟新算法

由于是维护的多个 partical ，所以当要跟新一个数据时，通过绝对位置，来定位到存储的位置，跟新了相应的数据时，只需要跟新相应的 partical 中的 SMB-Tree。其他数据保持不变即可。

删除

The deletion operation can be seen as updating the data object with a dummy one.

认证查询算法

在范围查询中，查询客户端提交一个查询范围Q = [lb, ub]。然后，SP遍历所有树，并在它们上单独处理范围查询。然后，SP将这些树的结果对象和VO结合起来，生成最终的查询结果和VOsp。 最后 SP 返回范围[lb, ub]中的所有对象，以及证明VOsp。 SP的查询算法是 MBTreeRangeQuery

接下来，查询客户端就通过区块链进行数据的验证了

客户端会从区块链中检索GEM2-Tree中所有树的Merkle根。VOchain可以由客户端使用区块链一致协议对最新的块进行验证。有了经过验证的VOchain，客户机就可以对GEM2树中的每棵树执行MBTreeVerify，以建立查询结果的真实性和完整性。

GEM2*-Tree

为了进一步降低广告维护成本，文章提出了一种优化的ADS，称为GEM2∗-tree。这扩展了GEM2*-Tree，使用一个上层索引将搜索键域分割为几个不重叠的子空间。

在上层索引中，将搜索关键域划分为几个区域 I1, I2, I3，··。为了获得最大的性能，分割是基于底层数据分布的，使得落在每个区域 Ii 中的键是相同的。

使用 优化后的 GEM2*-Tree 将会节省更多的 gas, 查询速度也会更快。

查询速度块：首先，由于上层的索引分割，在查询处理期间并不需要访问所有低层索引树。此外，每个region Ii只包含整个数据集的一部分，这将缩小检索范围，从而有助于加快查询处理。

认证查询算法

GEM2树的查询处理和结果验证算法与GEM2树的相似。首先，使用二分搜索法用于定位最左边和最右边的上层区域重叠的查询范围。然后 SP 对相应区域下的每个低层 GEM2*-Tree 调用相应的算法，最后搜索全结构的 mb-Tree。它包含一个上层区域的二值搜索，验证每个GEM∗-树的结果，并验证完全结构化mb -树的结果。

补充

MB-Tree 是 B-Tree 和 merkle hash Tree 的结合。说白了就是先将叶子节点从大到小排序，然后两两一组生成 MHT

• Soundness ：All of the answers in the result satisfy the query criteria and are originated from the DO;

• Completeness ： No valid answer is missing from the query result.

每个partical 中只包含两个 SMB 以及 小的SMB 合并成为大的 SMB 优点：

First, as new object insertions can be directed to the smallest partition, less data need to be read and computed during the root hash update.

Second, there is no need to physically re-arrange the objects after they are written into the storage, which is critical to save the gas cost.

Third, this also significantly saves the maintenance cost on the SP side as it does not need to rebuild the tree structure over the entire dataset for each object insertion.

Forth, this ensures that the total number of partitions is O(log N), which will benefit the query processing.

探索如何为其他经过身份验证的查询(如关键字和聚合查询)设计高效的数据结构将是很有趣的。