Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bloom Filters by Example

llimllib.github.io

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Bloom Filters by Example

#21

Post by CJefferson »

peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

SHA1 lives in an inbetween world, it's not cryptographically secure, but it is slow when you don't actually care about cryptographic security. It has increasingly few modern uses.

Your second point I agree with, sounds like someone is using a very bad hash function there.

Re: Bloom Filters by Example

#22

Post by HelloNurse »

peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

The article is too informal and it might suggest that hash functions are iterated (taking the hash of the hash of the hash...), like in applications that need very expensive hash functions.

A Bloom filter needs multiple cheap and decently independent hashes of the input, which at least in principle could be computed in parallel. For example a FNV-family hash function, which has no arbitrary parameters nor a key input, could be applied to the concatenation of k different fixed integers with the input data to get k different, and approximately independent, hash values. The hash function would also have to be adjusted to obtain a uniform distribution over m distinct values rather than the usual much larger range.

Re: Bloom Filters by Example

#23

Post by user5994461 »

peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

Bloom filters are data structure, in the same category as hashtable and trees.

They need a "hash" function to select an index for an item. A hash function in that context does not need to be cryptographic, it only needs to be quick and gives a good distribution of data.

SHA1 is slow, compared to a general purpose hash functions (typically murmurhash for bloom filters).

Re: Bloom Filters by Example

#24

Post by nandemo »

meenzu wrote: post #18
nandemo wrote: post #16

Earlier quoted context omitted.

If I was going to explain a bloom filter like you're 5... a bloom filter is like a savant who never forgets a face -- maybe he's got a job in passport control in Arstotzka -- if you show him someone's face or picture once, he'll never forget it: if any time later you show him the same picture and ask him "have you seen this face before?" he'll say "yes" without fail. If he replies "no way", you can be 100% sure he's…

Thanks for this explanation it was really helpful!

Glad to help. But I noticed the analogy is a bit flawed; testing for membership does not add anything to the set, but the analogy might imply asking yaSeenThisFaceBefore(x) will make the savant remember x. I should change the story and the 2 functions to "remember this terrorist" and "is this a terrorist?" or something like that.

Re: Bloom Filters by Example

#25

Post by masklinn »

peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

SHA1 is fast compared to key-derivation functions so you do not want to use it to hash passwords.

However SHA1 is slow compared to most hash functions (especially but not solely non-cryptographic hashes) so you don't want to use it for hash-based collections like hash tables or bloom filters.

edit: here's a bit I saved from tptacek (sadly I didn't keep the link, only the content):

* If you need random fixed-sized URLs, generate UUIDs; don't tie them to content, which can (a) change and (b) be predicted.

* For error detection, CRC schemes aren't weak. Against adversaries, MD5 is weak. For offline file integrity checking, or user-timescale online checking, use SHA256; at the very minimum, use an algorithm that hasn't been broken.

* Do not ever use the MD5(password) password scheme. MD5 is much faster than Unix crypt; even conventional Unix crypt is at least salt'ed to defend against rainbow table attacks, and modern adaptive hashing can be tuned to make dictionary attacks infeasable.

* MD5 is too slow for in-memory hash tables; I cringe when I see people use it. You're probably just hashing a string: use Torek's 31/37 hash. Otherwise, use Jenkins.

* PRNG design is hard. Just running MD5 over trivially small internal state doesn't yield a secure PRNG. Again, a problem other people solved that you have no business hacking on yourself, at least if your code matters.

* If you are concerned about collision attacks on your cryptosystem, which you should be if you're this guy and you're using MD5, use an algorithm that hasn't been broken; don't just jumble up one that already has. Kerckhoff's principal: look it up.

The bits you want are 3 and 4, but everything is good. Just sed s/MD5/SHA1/

Re: Bloom Filters by Example

#26

Post by j_s »

masklinn wrote: post #25
peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

SHA1 is fast compared to key-derivation functions so you do not want to use it to hash passwords . However SHA1 is slow compared to most hash functions (especially but not solely non-cryptographic hashes) so you don't want to use it for hash-based collections like hash tables or bloom filters. edit: here's a bit I saved from tptacek (sadly I didn't keep the link, only the content): * If you need random fixed-sized UR…

https://www.reddit.com/r/programming/comments/2fu8q/we_worsh...

Re: Bloom Filters by Example

#27

Post by plopilop »

tzs wrote: post #20

For implementations that use cryptographic hash functions, do you actually need more than one hash function invocation per item? For instance, suppose you were implementing a Bloom filter with 2^20 bits, and you want to use 10 bits per item. Instead of hashing the item 10 times, could you hash once with a 256 bit cryptographic hash, and then take the lower 200 bits, divide that into 10 bit strings of 20 bits each, an…

I remember I played with this specific scheme a while ago, and from what I remember it was doing the work well (I did not run a comparison though).

Re: Bloom Filters by Example

#28

Post by llimllib »

HelloNurse wrote: post #22
peteretep wrote: post #19

I am confused by: > cryptographic hashes such as sha1, > though widely used therefore are not > very good choices I thought SHA1 was fast, and that was a reason to not use it in applications where brute-forcing might be an issue. > [the more times you hash it the fewer > false positives] That doesn't match my understanding of how any even slightly reasonable hash function should work, doubly so if it's uniformly dist…

The article is too informal and it might suggest that hash functions are iterated (taking the hash of the hash of the hash...), like in applications that need very expensive hash functions. A Bloom filter needs multiple cheap and decently independent hashes of the input, which at least in principle could be computed in parallel. For example a FNV-family hash function, which has no arbitrary parameters nor a key input…

I had added a paragraph with this idea but have since lost it accidentally :(

Re: Bloom Filters by Example

#29

Post by skate22 »

asdfaoeu wrote: post #17
natch wrote: post #5

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long…

The only problem is this assumes that the hash unpredictably changes on input modification. Which is true for cryptographic hashes but not others.

basically, ideally you would want all of your hash functions to belong to the same universal hash family[1].

[1]: https://en.wikipedia.org/wiki/Universal_hashing

Re: Bloom Filters by Example

#30

Post by felipeerias »

tzs wrote: post #20

For implementations that use cryptographic hash functions, do you actually need more than one hash function invocation per item? For instance, suppose you were implementing a Bloom filter with 2^20 bits, and you want to use 10 bits per item. Instead of hashing the item 10 times, could you hash once with a 256 bit cryptographic hash, and then take the lower 200 bits, divide that into 10 bit strings of 20 bits each, an…

Yes, you can do that. Let me describe something similar that I implemented recently.

To use your example, let's say that the Bloom filter has a size of 2²⁰ bits (128 KB) and that we are using 10 bits per item. In other words, for each new item we need to calculate ten positions in the range [0,2²⁰).

We start by using a cryptographic hash function on the item just once. For example, SHA-256, which will give us a 256-bit value.

Now we need to extract ten blocks from these 256 bits. We can do as you suggest and make each block 20 bits long, but I don't know of a reason why we should not make them a bit longer. A length of 32 bits would be nice, so each block could be neatly mapped to a long.

To get ten blocks of 32 bits out of a 256-bit value, we just calculate a step such that block i starts at the position i * step. In our example, this means that the first block is in positions [0,31], the second is in [22,54]… and the tenth one is in [220,252].

At this point, we have ten blocks of 32 bits and we need ten values in the range [0,2²⁰). So we just turn each block into a long and calculate modulo 2²⁰ for each of them.

And that's pretty much it.

To enter the item in the filter, we set to true the positions corresponding to each of those 10 values.

To check whether an item may be in the filter, we do the same procedure and check that all of the ten positions have been set to true. If any of them is false, the item is not in the filter.

Post reply on HN