GEM 2-tree: A gas-efficient structure for authenticated range queries in blockchain

Ce Zhang, Cheng Xu, Jianliang Xu, Yuzhe Tang, Byron Choi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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 on-chain and the raw data are outsourced to off-chain storage. To protect data integrity, 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PublisherIEEE Computer Society
Pages842-853
Number of pages12
ISBN (Electronic)9781538674741
DOIs
StatePublished - Apr 1 2019
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: Apr 8 2019Apr 11 2019

Publication series

NameProceedings - International Conference on Data Engineering
Volume2019-April
ISSN (Print)1084-4627

Conference

Conference35th IEEE International Conference on Data Engineering, ICDE 2019
CountryChina
CityMacau
Period4/8/194/11/19

Fingerprint

Air cushion vehicles
Data structures
Gases
Metadata
Costs

Keywords

  • Authenticated query
  • Blockchain
  • Range query
  • Smart contract

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Cite this

Zhang, C., Xu, C., Xu, J., Tang, Y., & Choi, B. (2019). GEM 2-tree: A gas-efficient structure for authenticated range queries in blockchain. In Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019 (pp. 842-853). [8731412] (Proceedings - International Conference on Data Engineering; Vol. 2019-April). IEEE Computer Society. https://doi.org/10.1109/ICDE.2019.00080

GEM 2-tree : A gas-efficient structure for authenticated range queries in blockchain. / Zhang, Ce; Xu, Cheng; Xu, Jianliang; Tang, Yuzhe; Choi, Byron.

Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019. IEEE Computer Society, 2019. p. 842-853 8731412 (Proceedings - International Conference on Data Engineering; Vol. 2019-April).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zhang, C, Xu, C, Xu, J, Tang, Y & Choi, B 2019, GEM 2-tree: A gas-efficient structure for authenticated range queries in blockchain. in Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019., 8731412, Proceedings - International Conference on Data Engineering, vol. 2019-April, IEEE Computer Society, pp. 842-853, 35th IEEE International Conference on Data Engineering, ICDE 2019, Macau, China, 4/8/19. https://doi.org/10.1109/ICDE.2019.00080
Zhang C, Xu C, Xu J, Tang Y, Choi B. GEM 2-tree: A gas-efficient structure for authenticated range queries in blockchain. In Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019. IEEE Computer Society. 2019. p. 842-853. 8731412. (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2019.00080
Zhang, Ce ; Xu, Cheng ; Xu, Jianliang ; Tang, Yuzhe ; Choi, Byron. / GEM 2-tree : A gas-efficient structure for authenticated range queries in blockchain. Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019. IEEE Computer Society, 2019. pp. 842-853 (Proceedings - International Conference on Data Engineering).
@inproceedings{5d5104242a7444e7b9acd5bcc883fb1c,
title = "GEM 2-tree: A gas-efficient structure for authenticated range queries in blockchain",
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 on-chain and the raw data are outsourced to off-chain storage. To protect data integrity, 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.",
keywords = "Authenticated query, Blockchain, Range query, Smart contract",
author = "Ce Zhang and Cheng Xu and Jianliang Xu and Yuzhe Tang and Byron Choi",
year = "2019",
month = "4",
day = "1",
doi = "10.1109/ICDE.2019.00080",
language = "English (US)",
series = "Proceedings - International Conference on Data Engineering",
publisher = "IEEE Computer Society",
pages = "842--853",
booktitle = "Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019",
address = "United States",

}

TY - GEN

T1 - GEM 2-tree

T2 - A gas-efficient structure for authenticated range queries in blockchain

AU - Zhang, Ce

AU - Xu, Cheng

AU - Xu, Jianliang

AU - Tang, Yuzhe

AU - Choi, Byron

PY - 2019/4/1

Y1 - 2019/4/1

N2 - 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 on-chain and the raw data are outsourced to off-chain storage. To protect data integrity, 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.

AB - 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 on-chain and the raw data are outsourced to off-chain storage. To protect data integrity, 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.

KW - Authenticated query

KW - Blockchain

KW - Range query

KW - Smart contract

UR - http://www.scopus.com/inward/record.url?scp=85067969489&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067969489&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2019.00080

DO - 10.1109/ICDE.2019.00080

M3 - Conference contribution

AN - SCOPUS:85067969489

T3 - Proceedings - International Conference on Data Engineering

SP - 842

EP - 853

BT - Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019

PB - IEEE Computer Society

ER -