4 ms·
You don't even need a database. A Bloom filter would be very compact, easy to check, would not divulge any extra information and could adequately store hashes f
by lmilcin 6y ago
You don't even need a database. A Bloom filter would be very compact, easy to check, would not divulge any extra information and could adequately store hashes for orders of magnitude more apps.
- pdpi 6y agoA 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.
- gwbas1c 6y agoIs a bloom filter mutable? Can I make incremental changes to sync it? Or, do I have to download a new one every time?
- senkora 6y agoKind of. Incremental adds are possible with a Bloom filter, but not incremental removes. Resizing is also not possible, so you’ll want to redownload occasionally.