4 ms·
A bloom filter would also have a non-zero probability to produce false positives, which I don’t think is acceptable at all.
by pdpi 6y ago
A bloom filter would also have a non-zero probability to produce false positives, which I don’t think is acceptable at all.
- nrmitchi 6y agoPositives could still be confirmed remotely.
- thekyle 6y agoI believe the Safe browsing list in Google Chrome (list of malicious URLs) uses a bloom filter locally.
- lmilcin 6y agoThe probability can be dialed depending on your needs and you can make it as low as you want. For a Bloom filter storing 50k hashes with one in quadrillion (10^-15) probability of false positive you need 438kB bitmap. I would worry more about ability to create software with hashes that exploit false positives in the filter. I guess there is multiple ways to remediate this: the filter could be used only as fallback if the primary service doesn't work. And it could also be rotated regularly. It could be salted (ie. thousands of versions of the filter available) making it difficult to predict which one is going to be used. These are just couple silly ideas off the top of my head.
- 0xCMP 6y agoThe ideal design would be using the bloom filter to reduce remote checks and check any positives for confirmation if the remote service is available.