5 ms·

Smaller than Bloom filters

119 points by fogus 16y ago

gorset 16y ago
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.
- davidst 16y ago
  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.
- gjm11 16y ago
  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.
- agl 16y ago
  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...
  - gorset 16y ago
    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.
    - agl 16y ago
      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.
    - MichaelGG 16y ago
      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?)
deleted 16y ago
[deleted]
leif 16y ago
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).
jadc 16y ago
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.
tantalor 16y ago
tl;dr? Abstract?
- pjscott 16y ago
  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.
weinzierl 16y ago
I don't see how we can accept false positives. Doesn't that mean that the client will reject some perfectly valid certificates?
- CJefferson 16y ago
  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.
- orijing 16y ago
  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.
MichaelGG 16y ago
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?
- agl 16y ago
  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.

119 points by fogus 16y ago

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.

davidst 16y ago
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.
gjm11 16y ago
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.
agl 16y ago
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...
- gorset 16y ago
  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.
  - agl 16y ago
    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.
  - MichaelGG 16y ago
    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?)

deleted 16y ago

[deleted]

leif 16y ago

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).

jadc 16y ago

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.

tantalor 16y ago

tl;dr? Abstract?

pjscott 16y ago
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.

weinzierl 16y ago

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

CJefferson 16y ago
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.
orijing 16y ago
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.

MichaelGG 16y ago

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?

agl 16y ago
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.