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

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.