EUVIMEDEUVIMED entdecken
Crossref

BBA: A Maintenance-Efficient Authenticated Data Structure for Sliding-Window Range Queries in Blockchain Systems

Bo Yin, Yihu Liu

ACM Transactions on the Web · 06.11.2026

DOI: 10.1145/3859367 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on the Web, online erschienen am 06.11.2026. Verfasst von Bo Yin und 1 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Blockchain, a fundamental technology that enables decentralization and trustlessness, has been widely adopted across various applications. To meet the urgent need for data retrieval from blockchain databases, it is crucial to optimize the traditional authenticated data structure (ADS)–initially designed to ensure data integrity–so that it also supports efficient search. In this paper, we focus on solving the sliding-window range-and-selective (SWR) query problem, a useful tool for analyzing historical data in blockchains. The primary challenge is minimizing ADS maintenance costs, as data insertion and deletion complicate the well-known tree-based index and require expensive hash updates due to node operations such as construction, merging, and rotation. We propose a novel ADS, named BBA, that constructs a small, fixed-topology tree via bucketing and leverages bitmaps to support efficient search and hash updates. BBA is a two-layer index: the filtering layer consists of a bucket tree with bitmaps, while the strengthening layer utilizes a limited number of bitmaps for fine-grained bucketing. We introduce a recursive bucketing mechanism to develop this lightweight strengthening layer that enhances data filtering. Our evaluation shows a reduction in maintenance costs by one to two orders of magnitude for dataset sizes ranging from 10 2 to 10 4 compared to the state-of-the-art methods.

Zitieren

APA

Yin, B., & Liu, Y. (2026). BBA: A Maintenance-Efficient Authenticated Data Structure for Sliding-Window Range Queries in Blockchain Systems. ACM Transactions on the Web. https://doi.org/10.1145/3859367

Vancouver

Yin B, Liu Y. BBA: A Maintenance-Efficient Authenticated Data Structure for Sliding-Window Range Queries in Blockchain Systems. ACM Transactions on the Web. 2026. doi:10.1145/3859367

BibTeX
@article{Yin2026,
  author = {Yin, Bo and Liu, Yihu},
  title = {BBA: A Maintenance-Efficient Authenticated Data Structure for Sliding-Window Range Queries in Blockchain Systems},
  journal = {ACM Transactions on the Web},
  year = {2026},
  doi = {10.1145/3859367}
}
Kostenlos starten →