3 ms·

The benefits this data structure can give you sound kinda cool, even if I've got pretty much no idea how this data structure works based on the blog post. I've

by narush 5y ago

The benefits this data structure can give you sound kinda cool, even if I've got pretty much no idea how this data structure works based on the blog post. I've seen issues with fast set membership checks before that result from "Bloom filters having not the most pleasant API" - they can get annoying in practice. As something related HN might find interesting: Ethereum uses Bloom filters internally within each block to allow users to easily watch for specific "events" that are fired off by transactions. So, for example, you can just look at the Bloom filter in a block and check if your address is in it, and this will tell you if certain types of tokens might have been transferred to your address within this block. As a user, this might allow you to not look at all the transactions in a block if you're just trying to watch for transactions relevant to you. But the system is a bit broken. Because Bloom filters only do probabilistic checks of set membership (so it might say inclusion when there's nothing included), and because Bloom filters use hashing internally, you can pretty easily fill up the entire Bloom filter and potentially minorly DOS a few clients. A friend and I have a write-up about our attack (here.)[1] We ended up deciding it wasn't high severity, but it was still pretty fun. [1] https://medium.com/@naterush1997/eth-goes-bloom-filling-up-ethereums-bloom-filters-68d4ce237009 https://medium.com/@naterush1997/eth-goes-bloom-filling-up-e...)

np_tedious 5y ago
There's a linked paper at the bottom which presumably would help you learn how it works if you are interested That being said, I haven't read it. Even parts of the blog post's implementation summary were over my head. That paper would be surely more of a "study" than a "read" for me
hinkley 5y ago
The fact that Bloom filters are so far from the information theoretical limit for the problem they address offers some hope. I think it’s reasonable to expect that there are many structures out there that can achieve the same API in less space (time?) and that at least a few of those can achieve a better API in the same space, even if it means giving up some gains to store extra metadata. Example: linked list hashmaps, which store two extra pointers to remember insertion order.
tpetry 5y ago
This behaviour for the bloom filters is intended and not a DOS attack for some client. Imagine they did not use bloom filters, you had to analyze every transaction to see if you are interested in it. The bloom filters just allows in most cases to be absolutely you are _not_ interested in it. You only need to further analyze if the bloom filter says you may be interested in it.

by narush 5y ago

np_tedious 5y ago

There's a linked paper at the bottom which presumably would help you learn how it works if you are interested That being said, I haven't read it. Even parts of the blog post's implementation summary were over my head. That paper would be surely more of a "study" than a "read" for me

hinkley 5y ago

The fact that Bloom filters are so far from the information theoretical limit for the problem they address offers some hope. I think it’s reasonable to expect that there are many structures out there that can achieve the same API in less space (time?) and that at least a few of those can achieve a better API in the same space, even if it means giving up some gains to store extra metadata. Example: linked list hashmaps, which store two extra pointers to remember insertion order.

tpetry 5y ago

This behaviour for the bloom filters is intended and not a DOS attack for some client. Imagine they did not use bloom filters, you had to analyze every transaction to see if you are interested in it. The bloom filters just allows in most cases to be absolutely you are _not_ interested in it. You only need to further analyze if the bloom filter says you may be interested in it.