Published in the journal Data Science and Engineering, the study addresses the significant computational costs associated with locating specific transactions across historical blocks. The team, led by Yushi Liu and Aoying Zhou, proposes a hybrid tree-based architecture that balances query performance against storage overhead, a critical trade-off in blockchain analytics where data grows continuously and immutably.
Keyword search is a fundamental query type in blockchain supervision, allowing analysts to identify transactions associated with specific terms, such as sender addresses or contract identifiers. Existing methods, including on-chain indexing and off-chain database synchronization, often suffer from high space requirements or difficulties in maintaining data freshness. BlockSketch resolves these issues by adopting a differentiated encoding strategy that categorizes keywords as “hot” or “cold” based on their frequency within the blockchain, encoding them into the most suitable component of its hierarchical filtering architecture.
The core of the BlockSketch design is a binary search tree framework that integrates Bloom filters and Count-Min Sketches. In this structure, leaf nodes represent individual blocks, while index nodes cover larger ranges of blocks. Each index node contains a Bloom filter, which encodes “hot” keywords that appear frequently, and a Sketch, which handles membership queries for “cold” keywords with lower multiplicity. This hybrid approach limits the number of keywords encoded by each node, resulting in smaller data structures and improved query efficiency compared to methods that encode all keywords at every level of the tree.
To further optimize the search process, BlockSketch employs two distinct query rules: “level-down” and “jump.” When a keyword is identified as hot at a node, the query proceeds one level down to explore both child nodes. Conversely, if the keyword is cold, the system uses the Sketch to identify a “jump node,” allowing the search to bypass intermediate nodes and directly access the relevant subtree. This jump-like traversal significantly reduces the number of nodes inspected, thereby lowering query latency while maintaining high accuracy by minimizing the multiplicity of elements processed at each step.
The study also introduces a dynamic structure maintenance mechanism to handle the append-only nature of blockchains. Unlike traditional probabilistic data structures that require preallocated fixed space, BlockSketch constructs its index incrementally as new blocks arrive. This bottom-up construction allows the system to adjust the size of Bloom filters and Sketches dynamically based on the actual number of keywords, ensuring efficient space utilization without the need for costly reconstructions or significant space wastage when capacity limits are reached.
Experimental results demonstrate that BlockSketch offers substantial improvements over state-of-the-art methods. In tests using a real-world dataset of Ethereum blocks ranging from height 18,000,000 to 19,000,000, the structure delivered up to 73% faster query processing compared to baseline methods. The team also observed significant gains in storage efficiency, with BlockSketch saving 79% in storage compared to existing approaches. These results highlight the structure’s ability to handle the exponential growth in transaction volumes that pose regulatory and analytical challenges in modern blockchain networks.
Accuracy is a critical metric for blockchain keyword search, as false positives force the system to perform costly operations, such as retrieving and deserializing full blocks from disk. BlockSketch achieves a low average false positive rate, reaching 44.56% of the baselines’ rate at low multiplicity and as low as 1.52% at high multiplicity. The hierarchical structure helps prune false positives from intermediate query results, ensuring that only relevant blocks are added to the final result set. This precision is particularly important for applications like tracking phishing accounts, where identifying anomalous keywords requires high reliability.
The researchers also evaluated the effectiveness of two optimization strategies: flat nodes and a tree-based pruning strategy. Flat nodes merge lower-level subtrees into compact structures, reducing the time spent checking multiple small nodes during high-multiplicity queries. The pruning strategy identifies and eliminates branches in the search path that are unlikely to contain true-positive results. Together, these optimizations reduce query latency by up to 10% compared to the base BlockSketch implementation, while maintaining the space efficiency of the original design.
Comparisons with other probabilistic data structures, such as BloomTree, RAMBO, and CSC, reveal that BlockSketch is particularly well-suited for datasets with uneven keyword distributions. While methods like RAMBO and CSC struggle with high-multiplicity keywords, leading to increased false positives and storage overhead, BlockSketch’s differentiated encoding strategy allows it to maintain stable performance. The study notes that as multiplicity increases, the storage requirements for competing methods rise sharply, whereas BlockSketch’s storage consumption remains relatively stable or even decreases due to its efficient handling of hot keywords.
The implementation of BlockSketch was conducted in Golang, with approximately 4,000 lines of core code. The team used a physical machine equipped with an Intel Xeon Gold 6330 CPU and 125 GB of DRAM to run the experiments. By utilizing a full Ethereum node in a local environment, the researchers were able to validate the accuracy and efficiency of the structure using real test data. The results suggest that BlockSketch provides a robust solution for blockchain analytics, enabling faster and more cost-effective monitoring of on-chain activities without the need for extensive off-chain storage infrastructure.
Despite its advantages, the study acknowledges that the current implementation is vulnerable to false negatives in rare cases, where valid results may be omitted due to the probabilistic nature of the filters. To mitigate this, the team introduced a re-entry mechanism that allows the search to backtrack and verify the Sketch of parent nodes when potential false positives are encountered. This enhancement ensures query completeness, although the probability of such errors remains extremely low under normal operating conditions. The research provides a comprehensive framework for developing efficient indexing structures for decentralized ledgers, with potential applications in financial auditing, regulatory compliance, and security monitoring.
To accommodate continuous blockchain growth without exhausting host memory, BlockSketch organizes blocks into consecutive windows of 2,048 blocks each. Each window possesses a dedicated BlockSketch persisted directly to storage disk rather than resident memory. When a window reaches its capacity, its index becomes immutable, and the system initiates a fresh index for subsequent incoming blocks. When processing queries spanning temporal intervals across multiple windows, the architecture identifies all intersecting windows, executes sub-queries concurrently in parallel, and merges the resulting candidate blocks. Because windows maintain non-overlapping block data, parallel execution minimizes disk operations and bypasses operating system memory swapping during analytical range queries.
The mathematical analysis of the architecture reveals a distinct advantage in asymptotic storage complexity over traditional hierarchical filters. For a unique keyword appearing with a multiplicity of one, the space cost is confined entirely to a single entry in the root node Sketch. When a keyword appears across multiple blocks, each transition from locally cold to locally hot status consumes storage for one Bloom filter entry and two Sketch records. Consequently, the total storage cost scales strictly in proportion to keyword multiplicity as O(v), remaining independent of the tree height. In contrast, standard BloomTree designs redundantly replicate keyword signatures across every internal layer, resulting in an O(v·log M) space complexity that scales poorly in deep trees.
Direct empirical comparisons against BloomTree confirmed this theoretical divergence under controlled false positive rates of 1%. Across varying keyword multiplicities, BlockSketch achieved space savings between 57.51% and 66.83% while reducing query latency by up to 61.77%. When evaluating scalability across window sizes, BloomTree required 2.61 times more storage space than BlockSketch at a window size of 256 blocks, expanding to 3.18 times greater storage demand at 4,096 blocks. Furthermore, index construction stability favored BlockSketch under heavy workloads; while competing sketch structures such as RAMBO and CSC experienced construction times climbing to 2.99 and 1.93 times that of BlockSketch at multiplicities exceeding 80, BlockSketch construction latency remained steady, moving marginally from 1,973 milliseconds to 1,948 milliseconds as multiplicity expanded from 20 to 320.
The investigators also measured the efficiency gains provided by temporal pruning during intra-window search execution. By immediately terminating search paths when a sub-tree interval does not overlap with the requested query interval, the system eliminates unnecessary node inspections across irrelevant blocks. In experimental evaluations, time pruning produced a 1.12-fold speed improvement over unpruned traversal at a window size of 256 blocks, which increased to a 2.58-fold speedup when the window expanded to 2,048 blocks. When isolating the latency specifically spent inspecting probabilistic filter structures, the acceleration reached 3.09 times faster than full traversal, ensuring that overall query response times remain stable regardless of window capacity.
Structural parameter analysis identified precise operational limits when configuring the merging threshold tau for flat nodes. Merging consecutive leaf nodes initially produced substantial storage savings by consolidating underutilized low-level sketch components without expanding overall capacity. However, when tau increased beyond eight, the candidate sets generated by individual filter groups grew excessively large, degrading the effectiveness of set intersection and increasing false positive rates. The researchers concluded that selecting tau values of 4 or 8 establishes the optimal trade-off between space usage, query latency, and accuracy. Software implementation details confirmed that the system relied on the bitset library for Bloom filters and the xxhash library with varied seed values for hashing, while temporary in-memory map buffers tracking jump nodes were systematically deleted following sibling buffer merges to prevent memory bloat.
Subject of Research: Development of a hybrid probabilistic data structure for efficient keyword search in blockchain systems
Article Title: BlockSketch: A Hybrid Tree-Based Sketch for Keyword Search in Blockchain Systems
Article References: Liu, Y., Qi, X., Zhang, Z., Yang, Y., Jin, C., & Zhou, A. (2026). BlockSketch: A Hybrid Tree-Based Sketch for Keyword Search in Blockchain Systems. Data Science and Engineering, 11(1), 177-198. https://doi.org/10.1007/s41019-025-00326-6
Image Credits: AI Generated
DOI: 10.1007/s41019-025-00326-6
Keywords: blockchain, keyword search, probabilistic data structures, Bloom filter, Count-Min Sketch, data indexing, query optimization, Ethereum, storage efficiency, data science, BlockSketch, Hybrid
News Source: Denise Maddox. (November 10, 2026). New Blockchain Index Cuts Search Time and Storage. Scienmag.
