Knowledge and Information Systems Взаимодействие человека и компьютера

Evq: efficient and verifiable k most influential transaction retrieval in blockchain systems

Yin, Bo, Ji, Youlin
Springer Nature · 2026-11-12 · DOI 10.1007/s10115-026-02938-4

Аннотация

Blockchains facilitate trustworthy transaction management in a distrust environment without relying on a centralized authority. The rapid growth in the number of transactions recorded on blockchains necessitates efficient and verifiable data query processing. Queries typically seek data that includes both numerical and set-valued attributes. Additionally, many real-world data exploration and decision-making applications require obtaining a small selection of representatives from a large collection of transactions based on specific metrics, such as their influence on set-valued attributes. However, existing studies primarily focus on verifying query results and do not adequately support complex queries, such as counting on set-valued attributes. Moreover, most of these studies overlook query efficiency. In this paper, we introduce the novel EVQ framework for the k most influential transaction ( k MIT) retrieval to promote the query and verification efficiency. The main challenge arises from the set-valued attribute, which can significantly increase query time and the size of the verification object (VO). To address this issue, we propose a new authenticated data structure called the MB $$^\textrm{fm}$$ fm -tree, which incorporates FM sketches into a Merkle B-tree. The FM sketches are used to approximate the count of elements. We further extend the MB $$^\textrm{fm}$$ fm -tree to create the MR $$^\textrm{fm}$$ fm -tree by transforming the set-valued attribute into a numeric attribute, enabling batch pruning on both attributes. Extensive experimental results demonstrate that the MR $$^\textrm{fm}$$ fm -tree delivers query times one to three orders of magnitude faster than the Merkle tree-based approach, and exceeds the performance of the state-of-the-art approach by over an order of magnitude.

Читать у издателя →