| Title | GEMˆ2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Zhang, C., Xu, C., Xu, J., Tang, Y., Choi, B. |
| Conference Name | 2019 IEEE 35th International Conference on Data Engineering (ICDE) |
| Date Published | apr |
| Keywords | ADS 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 |
| Abstract | Blockchain 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. |
| DOI | 10.1109/ICDE.2019.00080 |
| Citation Key | zhang_gem2-tree_2019 |
GEMˆ2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain