Empowering Authenticated and Efficient Queries for STK Transaction-Based Blockchains

Hao Xu, Bin Xiao, Xiulong Liu, Li Wang, Shan Jiang, Weilian Xue, Jianrong Wang, Keqiu Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)


Owing to the attractive properties of decentralization, unforgeability, transparency, and traceability, blockchain is increasingly being used in various scenarios such as supply chain and public services, where massive Spatial-Temporal-Keywords (STK) transactions need to be packaged. However, due to the multi-dimensionality and randomness of STK transactions, existing solutions fail to enable queries in a verifiable and efficient way for blockchains storing multidimensional transactions. To this end, this article takes the first step to propose an authenticated and efficient query approach in hybrid blockchain systems consisting of on-chain and off-chain parts. We first design a data structure named MRK-Tree in the block body, which organizes STK transactions for efficient nodes pruning of both kNN and range queries. Then we propose an improved block header, which improves the efficient pruning of blocks on the basis of ensuring the authentication of query results. Also, we design a cross-block searching algorithm named Efficient Block Pruning (EBP) and intra-block searching algorithms named Authenticated kNN/Range Query (AKQ/ARQ) to accelerate authenticated queries for multiple MRK-Trees in the hybrid blockchain systems. Authentication mechanisms are proposed to ensure the soundness and completeness of query results. Rigorous security analysis validates the practicability of the proposed approach. We build a blockchain prototype to comprehensively evaluate the performance of proposed query schemes. Extensive evaluation results with real datasets reveal that our approach can ensure authenticated queries, meanwhile improving the time efficiency by up to 36.45x and space efficiency by up to 4 orders of magnitude compared with the well-known benchmark query schemes.

Original languageEnglish
Pages (from-to)2209-2223
Number of pages15
JournalIEEE Transactions on Computers
Issue number8
Publication statusPublished - 1 Aug 2023


  • Authenticated query
  • blockchain system
  • kNN query
  • range query
  • STK transactions

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Empowering Authenticated and Efficient Queries for STK Transaction-Based Blockchains'. Together they form a unique fingerprint.

Cite this