Visible to the public GEMˆ2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain

TitleGEMˆ2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain
Publication TypeConference Paper
Year of Publication2019
AuthorsZhang, C., Xu, C., Xu, J., Tang, Y., Choi, B.
Conference Name2019 IEEE 35th International Conference on Data Engineering (ICDE)
Date Publishedapr
KeywordsADS maintenance cost, authenticated data structure, Authenticated query, authenticated range queries, blockchain, blockchain technology, composability, consensus protocol, cryptography, data integrity, Data models, data structures, Distributed databases, gas-efficient structure, GEM2-tree, hybrid storage architecture, hybrid-storage blockchain, immutability property, Indexes, meta-data, Metrics, Outsourced Database Integrity, outsourcing, pubcrawl, query processing, range query, Resiliency, smart contract, smart contracts, storage management, trusted storage, unique gas cost model
AbstractBlockchain technology has attracted much attention due to the great success of the cryptocurrencies. Owing to its immutability property and consensus protocol, blockchain offers a new solution for trusted storage and computation services. To scale up the services, prior research has suggested a hybrid storage architecture, where only small meta-data are stored onchain and the raw data are outsourced to off-chain storage. To protect data integrity, a cryptographic proof can be constructed online for queries over the data stored in the system. However, the previous schemes only support simple key-value queries. In this paper, we take the first step toward studying authenticated range queries in the hybrid-storage blockchain. The key challenge lies in how to design an authenticated data structure (ADS) that can be efficiently maintained by the blockchain, in which a unique gas cost model is employed. By analyzing the performance of the existing techniques, we propose a novel ADS, called GEM2-tree, 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, GEM2*-tree, by designing a two-level index structure. Theoretical analysis and empirical evaluation validate the performance of the proposed ADSs.
Citation Keyzhang_gem2-tree_2019