GEM^2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 842-853
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 GEM 2 -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, GEM 2 *-tree, by designing a two-level index structure. Theoretical analysis and empirical evaluation validate the performance of the proposed ADSs.Keywords
This publication has 27 references indexed in Scilit:
- BLOCKBENCH2017
- Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts2016
- Authenticated Online Data Integration Services2015
- Zerocash: Decentralized Anonymous Payments from Bitcoin2014
- Authenticated indexing for outsourced spatial databasesThe VLDB Journal, 2008
- Authenticating the query results of text search enginesProceedings of the VLDB Endowment, 2008
- Dynamic authenticated index structures for outsourced databases2006
- Authenticating query results in edge computing2004
- A Certified Digital Signature2001
- The log-structured merge-tree (LSM-tree)Acta Informatica, 1996