Age-Partitioned Bloom Filters
arxiv.org
Age-Partitioned Bloom Filters
1–10 of 12 posts
Re: Age-Partitioned Bloom Filters
#2I've used something like this before, thank you for characterizing it. :- )
I used mine for authentication rejection.
Re: Age-Partitioned Bloom Filters
#3This is really great!
For those that don't know, bloom filters are really good at determining when something is not in a set. So if says "not in set" that's 100% accurate and super fast.
We used this to our advantage at reddit. When you load a comments page, we had to determine if you've voted on anything. So with the bloom filter in front, the query for "have they voted on anything here" was very quick if the answer was no.
But we still had to make the query. So another hack we did was to put a value on your user object to track the last time you interacted with the website. If the comments page was made after your last interaction, then we didn't even have to do the query.
With this, we wouldn't have to do the two step process -- it sounds like this would be super fast when it was time boxed. Maybe...
Re: Age-Partitioned Bloom Filters
#4Aether (https://getaether.net) also uses a roughly equivalent version of this I had thought, up to this point, that I ‘discovered’. I call it ‘Rolling Bloom’. (Not sure which implementation is first.)
Here’s the Go implementation: https://github.com/nehbit/aether/blob/master/aether-core/aet...
Re: Age-Partitioned Bloom Filters
#5I've used something like this before, thank you for characterizing it. :- ) I used mine for authentication rejection.
Do you suppose there's a timing attack where someone can figure out if any particular users (target user, or admins) are currently online and get up to nonsense if they aren't?
Not sure if your app is big enough to care, but it might be you want to normalize the response times, so server load is reduced but auth time is fixed.
Re: Age-Partitioned Bloom Filters
#6Aether ( https://getaether.net ) also uses a roughly equivalent version of this I had thought, up to this point, that I ‘discovered’. I call it ‘Rolling Bloom’. (Not sure which implementation is first.) Here’s the Go implementation: https://github.com/nehbit/aether/blob/master/aether-core/aet...
Thanks for the pointer. I took a look at the code and it’s different. Looks like Aether maintains several bloom filters, each link to a given time range. In contrast the paper builds a different kind of bloom filter where hash functions can overlap.
Re: Age-Partitioned Bloom Filters
#7Aether ( https://getaether.net ) also uses a roughly equivalent version of this I had thought, up to this point, that I ‘discovered’. I call it ‘Rolling Bloom’. (Not sure which implementation is first.) Here’s the Go implementation: https://github.com/nehbit/aether/blob/master/aether-core/aet...
Thanks for the pointer. I took a look at the code and it’s different. Looks like Aether maintains several bloom filters, each link to a given time range. In contrast the paper builds a different kind of bloom filter where hash functions can overlap.
Interesting, thanks for taking a look. That is correct. Aether also does some partial merging in the cases where the time range required does not exactly match the filter sequence.
Re: Age-Partitioned Bloom Filters
#8I've used something like this before, thank you for characterizing it. :- ) I used mine for authentication rejection.
Do you suppose there's a timing attack where someone can figure out if any particular users (target user, or admins) are currently online and get up to nonsense if they aren't? Not sure if your app is big enough to care, but it might be you want to normalize the response times, so server load is reduced but auth time is fixed.
It was a general rejection system, so all valid (and recently invalidated) tokens were in the same bloom. If we rejected your token, your connection was cut immediately without response. The normal mechanisms for limiting short-lived connections from a given address apply, so your ability to sample for that would be severely limited, and chances are you wouldn't even have a well-formed token to sample with anyway (since the tokens were authenticated).
I don't work on that anymore though. I might do something similar in the future, but being able to detect when admins are snoozing is low on my list of concerns; if it's designed properly, it'll be cheaper to hire PIs to just look and see when they're snoozing.
Re: Age-Partitioned Bloom Filters
#9Missed opportunity to title this paper "OK Bloomer".
Re: Age-Partitioned Bloom Filters
#10This is really great! For those that don't know, bloom filters are really good at determining when something is not in a set. So if says "not in set" that's 100% accurate and super fast. We used this to our advantage at reddit. When you load a comments page, we had to determine if you've voted on anything. So with the bloom filter in front, the query for "have they voted on anything here" was very quick if the answer…
> For those that don't know, bloom filters are really good at determining when something is not in a set. So if says "not in set" that's 100% accurate and super fast.
Agreed. It allows for false positives, but disallows false negatives.