Binary Fuse filters as an alternative to BIP 158 GCS

In a recent analysis of filter performance in blockchain scenarios, distinct differences were identified between Golomb-Coded Sets (GCS) and Bloom Filters (BF) with regard to false positive rates. Specifically, GCS exhibits a significantly lower false positive rate at 1/784931 compared to BF's 16-bit fingerprints at 1/65536. To achieve parity with GCS's false positive rates, a 20-bit fingerprint would be required for BF.

Further investigation into the practical application of these filters using a dataset of 50,000 blocks from the mainnet with 10 different wallet scenarios revealed some interesting findings. Despite Fuse20 having a false positive rate that aligns more closely with that of GCS, Fuse16 demonstrated better overall performance in terms of bandwidth and CPU load. This outcome highlights an important aspect of filter performance: the real-world utility of a filter is not solely determined by its ability to minimize false positives, but also by its operational efficiency across various computing environments.

The comparative benchmarks indicate that while Fuse20 might have a closer false positive rate to GCS, Fuse16 offers more practical benefits due to its smaller filter size, which results in less bandwidth consumption and block downloads triggered by false positives. The actual false positive numbers recorded during the tests align closely with theoretical expectations. For instance, in the simple_user wallet scenario involving 24 scripts, the expected number of false positives for Fuse16 was around 17.9, whereas the measured result was 19, confirming the reliability of the theoretical model used to predict these outcomes.

Moreover, the comprehensive data provided on GitHub includes detailed false positive ratios for all measured filters, lending further credibility to these findings. However, there remains some uncertainty regarding whether the sample wallets used in the study are representative enough of real-world scenarios, suggesting that further research may be needed to ensure the generalizability of these results across different blockchain applications.