RFC: Block-Range Filters (a.k.a. Hierarchical filters)

The premise involves creating filters for specific ranges of blocks (e.g., every 256 blocks) and downloading these first. Should there be a match indicated by the block-range filter, individual block filters would then be obtained only for those specific blocks. This method proposes that the total size of the block-range filters is smaller than the sum of all individual block filters, thereby potentially reducing total download sizes significantly. Preliminary results suggest that with this approach, the download size can be reduced to under 25% of what it would be otherwise.

Further details from simulations show varying impacts depending on the transaction count in the scripts used. For instance, for scripts with an average of about six transactions, the download size was reduced to 18.2% for 256-block ranges, while for scripts averaging around 27 transactions, it was slightly higher at 28.1%. Additionally, it's noted that the efficiency of the block-range filters decreases as the range size increases beyond an optimal point, which seems to be around 256 blocks. Larger range sizes result in diminishing returns due to increased complexity and potential practical concerns.

To enhance this approach, further exploration into different parameters for block-range filters and the optimization of block filters themselves is suggested. This includes possibly utilizing script indexes within the block-range filters instead of the original script hashes, which could reduce size further.

In relation to the broader context of using filters and trees for data querying and management, the paper "Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying" (link) highlights advancements in designing efficient structures for set membership queries. It underscores a partitioning scheme that helps in ensuring disjointness of entries, which is crucial for reducing collision and improving query accuracy.

Moreover, the email explores the idea of employing a hierarchical structure for managing block filters via a trusted server or a peer-to-peer network. This structure could start with a simple download of a root node encoding a coarse-grained approximate set membership query structure, followed by more detailed downloads as needed based on query responses. The challenges discussed include potential attacks through malicious transaction ID collisions and the computational overhead required to manage such a system.

Overall, the concepts discussed aim at refining blockchain data management and retrieval processes, enhancing efficiency while considering both security implications and practical deployment challenges.