Searchable Blockchain with Integrity Assurance (Jianliang Xu et al.)


Blockchain has recently emerged as a promising solution for providing trustworthy storage and computation for decentralized applications. While blockchain technology has many advantages such as immutability and traceability, its resource-consuming consensus mechanism limits the performance and scalability. To scale blockchain system, one can leverage third-party services to outsource computation and storage tasks. For example, to query the blockchain databases, instead of maintaining a full replica locally, users can ask the query questions to other full nodes in the network. Similarly, to reduce the cost on blockchain data storage, users can apply a hybrid storage architecture, where only small meta-data are stored on-chain while raw data are outsourced to off-chain storage. However, since the third parties cannot be fully trusted, these outsourcing models have risks on losing data integrity. To tackle these issues, the project aims at investigating techniques and algorithms to enable efficient integrity-assured query and storage services over the blockchain databases.

Findings So Far

To ensure query integrity over blockchain databases, we propose a novel framework, called vChain [1], that alleviates the storage and computing costs of the user and employs verifiable queries to guarantee the results’ integrity. To support verifiable boolean range queries, we propose an accumulator-based authenticated data structure that enables dynamic aggregation over arbitrary query attributes. Two new indexes are further developed to aggregate intra-block and inter-block data records for efficient query verification. We also propose an inverted prefix tree structure to accelerate the processing of a large number of subscription queries simultaneously. Security analysis and empirical study validate the robustness and practicality of the proposed techniques.

To protect data integrity over hybrid-storage blcokchain and offering authenticated range queries services, we propose to leverage the blockchain’s smart contract to construct and maintain an authenticated data structure (ADS) on top of the meta-data stored on-chain, which can be used to prove the correctness of the search results returned from the off-chain storage. Yet, a key challenge lies in how to design the ADS so that it can be efficiently maintained by the smart contract, which employs a unique gas model as a cost measure. By analyzing the performance of the existing techniques, we propose a novel ADS, called GEM^2-tree [2], which is not only gas-efficient but also effective in supporting authenticated queries. To further reduce the ADS maintenance cost without sacrificing much the query performance, we also propose an optimized structure, GEM^2*-tree, by designing a two-level index structure. Theoretical analysis and empirical evaluation validate the performance of the proposed ADSs.

Selected Publications
  1. C. Xu, C. Zhang, and J. Xu, “vChain: Enabling Verifiable Boolean Range Queries over Blockchain Databases,” in Proceedings of the 2019 ACM SIGMOD International Conference on Management of Data (SIGMOD ’19), Amsterdam, Netherlands, 2019.
  2. C. Zhang, C. Xu, J. Xu, Y. Tang, and B. Choi, “GEM^2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain,” in Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE ’19), Macau SAR, China, 2019.
Grant Support

This project is supported by the Research Grants Council (RGC), Hong Kong SAR, China


For further information on this research topic, please contact Prof. Jianliang Xu.