Authenticated keyword search in scalable hybrid-storage blockchains

Ce Zhang, Cheng Xu, Haixin Wang, Jianliang Xu, Byron Choi

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

45 Citations (Scopus)


Blockchain has emerged as a promising solution for secure data storage and retrieval for decentralized applications. To scale blockchain systems, a prevailing approach is to employ a hybrid storage model, where only small meta-data are stored on-chain while the raw data are outsourced to an off-chain storage service provider. The key issue for query processing in such a system is the design of gas-efficient authenticated data structure (ADS) to authenticate the query results. In this paper, we study novel ADS schemes for authenticated keyword search in hybrid-storage blockchains. We first propose the Suppressed Merkle inverted (Merkleinv) index, which maintains only a partial ADS structure on-chain that can be securely updated with a logarithm-sized cryptographic proof. Moreover, we propose a Chameleon inverted (Chameleoninv) index that leverages the chameleon vector commitment to achieve a constant maintenance cost. It is further optimized with Bloom filters to enhance the query and verification performance. We prove the security of the proposed ADS schemes and evaluate their performance using real datasets on the Ethereum platform. Experimental results show that, compared to a baseline solution, the proposed Merkleinv and Chameleoninv indexes reduce the average on-chain maintenance cost from US10.39 down to US2.50 and US0.24, respectively, without sacrificing much the query performance.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021
Number of pages12
ISBN (Electronic)9781728191843
ISBN (Print)9781728191850
Publication statusPublished - Apr 2021
Event37th IEEE International Conference on Data Engineering, ICDE 2021 - Virtual, Chania, Greece
Duration: 19 Apr 202122 Apr 2021

Publication series

NameProceedings of IEEE International Conference on Data Engineering (ICDE)
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X


Conference37th IEEE International Conference on Data Engineering, ICDE 2021
CityVirtual, Chania
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Authenticated keyword search in scalable hybrid-storage blockchains'. Together they form a unique fingerprint.

Cite this