Smaller than Bloom filters | Hacker News Reader

Smaller than Bloom filters

imperialviolet.org

119 pointsfogus16 comments

The article says 400K revoked certificates leading to 51MB uncompressed bloom filter. That's like 133 bytes per certificate, which seems wrong. Am I missing something?

If 1 out of 1024 false positive is the target, then using 8 bytes per entry should be more than enough, which gives ~3MB of data without any magic.

The article is a bit untidy, so it would be nice to get a clearer picture of the sizes of the different approaches.

You're not missing anything. I don't want to knock the author because there's a lot of good stuff here that is well-worth reading but in this case I think he got a little carried away and missed the obvious, simple solution.

That's an uncompressed Bloom filter with a single hash function. To get a false-positive probability of p with a single hash function you need 1/p bits per entry.

But that's the uncompressed filter. It compresses way, way down: to about 8 bits per entry. That gives 400KB of data, still with a 1/1024 false-positive rate. Much better than 3MB.

If you consider (uncompressed) Bloom filters with arbitrarily many hashes, the best you can do for a false-positive rate of 1/1024 is about 14 bits per entry.

I lost several people at that point, so I clearly didn't communicate that point well. Sorry about that, I'll see if I can tweak it tomorrow.

But the point was that you can beat a Bloom filter on size, for the same performance, if you use only a single hash function (making the Bloom huge) and then compress the result.

Of course, you lose the random access in that case and, if you're looking at processing the whole thing for a lookup, then the volume of the uncompressed data becomes a concern. Thus the GCS...

Thanks.

Which values are you using for the matching? I was assuming a fingerprint of the cert. Have you considered compressing the domains? Compiling them to a DFA should yield a very small structure, and you then will need far fewer bits for the actual fingerprint.

We can only use the information that the CAs give us, which is the serial number of the certificate. So we match the serial number and issuer.

If you use the domains, then any domain that ever had a cert revoked would hit, and need a secondary lookup. That means some of the busiest sites on the Internet would not benefit from this check. Also, I think if you re-issue or otherwise change your cert, the old one goes into the CRL, even if it wasn't for a compromise, right? (Which would explain a high number of revocations?)

It sounds like the Matrix filter can't be delta compressed because the bits in each element get smeared across dimensions, but it also sounds like you understand that. I don't think structures which hit lower bonds can't be delta compressed (but I don't have an example handy).

Is this correct: 400K revoked certificates? Isn't that a lot of revocations?

Shouldn't the filter size be based on total elements to be checked, not elements stored? Assume there are only 1000 revoked certs. If a bloom filter were used, it'd have to still be huge to keep a low false positive rate, because there's millions(?) of valid certificates, correct?

Please, could someone fill in what I'm missing here?

Yes, 400K is a lot of revocations, but we can only download the CRLs and treat them as gospel.

Keeping a low false positive rate is important because, in the event of a hit in the filter, the resulting OCSP check has to be hard-fail and, if that starts bringing down good sites, then that's a problem.

In the end, we have to collect data and see how it does in the real world. The theory suggests that it might work but reality always has tricks.

This definitely seems like an interesting idea. It has been proposed before in the context of peer to peer networks, but I am not sure if it was taken beyond academic research.

I don't see how we can accept false positives. Doesn't that mean that the client will reject some perfectly valid certificates?

We must understand the trade offs in each decision.

False positives are MUCH better than false negatives. It's safer to reject a valid cert than to accept an invalid cert.

I had assumed the plan was, when the bloom filter does reject a certificate, go and check if it is actually valid or not.

I imagine 99.9% of the time (totally made up), certificates will be valid, and the bloom filter will agree they are valid. In the 0.1% of the time the bloom filter rejects, go and actually check.

tl;dr? Abstract?

Bloom filters are a data structure for testing set membership, which may have false positives but no false negatives. They're remarkably compact, and often useful. The blog post talks about how to do even better in terms of compactness, through the clever use of Golomb coding. (And, incidentally, reduce the expected number of cache misses for a lookup.)

Definitely worth a read, if any of that sounded interesting.

Reply on news.ycombinator.com