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 language | English (US) |
|---|---|
| Title of host publication | Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019 |
| Publisher | IEEE Computer Society |
| Pages | 842-853 |
| Number of pages | 12 |
| ISBN (Electronic) | 9781538674741 |
| DOIs | |
| State | Published - Apr 1 2019 |
| Event | 35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China Duration: Apr 8 2019 → Apr 11 2019 |
Publication series
| Name | Proceedings - International Conference on Data Engineering |
|---|---|
| Volume | 2019-April |
| ISSN (Print) | 1084-4627 |
Conference
| Conference | 35th IEEE International Conference on Data Engineering, ICDE 2019 |
|---|---|
| Country | China |
| City | Macau |
| Period | 4/8/19 → 4/11/19 |
Fingerprint
Keywords
- Authenticated query
- Blockchain
- Range query
- Smart contract
ASJC Scopus subject areas
- Software
- Signal Processing
- Information Systems
Cite this
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 proceeding › Conference contribution
}
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 -