With a similar idea in mind, I have experimented with bloom filters on my blossom server implementation. https://almond.slidestr.net/_bloom there is also a serverside check to debug: https://almond.slidestr.net/_bloom?test=3deb9daf761c8d638f8ccda3523113b4eddbcf3391c469e8b12da53aa83bf47d6 I haven't really used it yet but my idea is to have "edge blossom servers" that proxy to "backend blossom servers" and the filter would be a great optimization if the proxy had knowledge where to find a specific blob. It could also be used in clients, to speed up failover to other blossom servers. Have to look into those binary fuse filters now.

This research made me realize that we could upgrade BIP157/158 and the Wasabi Wallet indexer to use FUSE filters, they're smaller and much faster to query than golomb rice filters. I wonder what the speedup would be...

Oh that's a cool idea! Fuse seem to be the cutting edge in regards to filters at the moment.

> The Problem Imagine you have 10,000 files and want to determine which ones already exist on a Blossom server before uploading. the bloom filter (& friends) approach works well if clients actually use them. i worked on an api that exposed offers/coupons to apps like foursquare/groupon/etc back in the day. given a course location, we’d return a promotion at a nearby merchant, if available. that calculation wasn’t cheap and you can imagine the amount of traffic given the clients. we mitigated much of the load by generating and shipping bloom filters to the clients. if there definitely wasn’t a promotion available, they’d skip the request.

Exactly. And FUSE seems to be super cheap to compute, rather small in size. The server can choose how frequently he recomputes the filter (could be once a day or so) and filter generation is done in milliseconds on a single core CPU.

TIL about binary fuse filters. thanks!

Yeah they are new to me to, beautiful tech!

solid. binary fuse + delta lists is basically perfect for this. feels like the obvious next step. no exotic crypto, just a good data structure and a couple lists. View quoted note →

how do you handle servers removing blobs? does it need to recalculate the whole bloom filter?

Yes it currently does. I think a separate filter for added/removed blobs can make sense. I currently recalculate on every request but that works only because I have a manageable 1200 blobs which are all in memory. I have also added a binary fuse endpoint now, whose data is noticeably larger but that is due the much lower error rate: https://almond.slidestr.net/_fuse

cuckoo filters are similar to bloom but allow you to remove items

Do you have a link to the repo? Id like to continue looking into this and maybe find a way to write a BUD for it