Towards Integrity-Assured Search in Scalable Blockchain Systems

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 performance and scalability. To scale blockchain systems, recent research has suggested a hybrid storage architecture, where only small meta-data are stored on-chain while raw data are outsourced to off-chain storage (e.g., Amazon S3 or Google Cloud Storage). To ensure data integrity, the on-chain meta-data are used to authenticate the data retrieved from the off-chain storage. However, existing studies have only considered data retrieval by specific keys. How to support more general types of search, such as range search and keyword search, remains unexplored in the literature.

This project aims to investigate efficient techniques and algorithms to enable integrity- assured search in scalable hybrid-storage blockchain systems. Our basic idea is 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. The amount of gas to pay for different operations differs. Notably, the gas charged for a blockchain write operation is several orders of magnitude higher than that for a blockchain read operation (e.g., 20,000 vs. 200 per word in Ethereum).1 Traditional ADS techniques, such as the Merkle B-tree and the Log-Structured Merge-Tree, are not gas-efficient because they either are not aware of write-read asymmetry or incur a prohibitively high merge cost.

To address these limitations, in this project we will propose novel gas-efficient techniques for integrity-assured search. More specifically, we plan to design 1) gas-efficient ADSs for supporting authenticated search in hybrid-storage blockchain systems; 2) verifiable search algorithms to allow users to check the correctness of search results; and 3) optimization techniques for striking a balance between the gas cost and search performance. Besides theoretical research, to understand the performance and assess the practicality of the proposed solutions in real systems, we will evaluate them in the Ethereum network. We will also collaborate with our industry partner Huawei Inc. for prototyping and testing in their blockchain service platform. We believe the proposed research will bridge the gap between blockchain data storage and retrieval, and further contribute to the broader goal of building scalable and searchable blockchain systems.