Wouldn't using a simple bloom filter make sense in their case? Just build the thing offline and your app loads it in RAM at startup.
False positives Size (MB)
0.1 285
0.01 571
0.001 857
0.0001 1120
0.00001 1390
0.000001 1670The real problem is that the current API returns a count of the number of times each particular password has appeared, and AFAIK there's no good way to do that with a bloom filter.
Also, a Bloom filter has a smaller page cache footprint and disk space usage than using a precise set.
In order to increase the count for a given key, you expand the key into your probe sequence, find the minimum counter across all of the probed locations, and then increment all of the values equal to that minimum value. One generally uses saturating addition to avoid overflow. If you want to support removing items, you actually increment the values at all of the probe locations, at a cost of increasing the expected deviation from correct counts.
To read the count for a given key, you generate your probe sequence and return the minimum of the values stored at the probed locations.
Note that a regular Bloom filter is just a counting Bloom filter using 1-bit counters.
In this case, I presume one would generate a counting bloom filter and then either store logarithm or quantile of the count, since there isn't a common use case for distinguishing between 4,096 and 4,095 occurrences of a given password.
Just send a hash from the client and have the bloom filter built offline with the sames hashes, no big deal. You'd never ask clients to download it.
But for one of the calls (checking a whole password against what's stored), which probably accounts for most of the usage of the API, a bloom filter seems like a perfect fit.