Hacker News Reader

Comment by captn3m0 | Hacker News Reader

Going to generate a bloom-filter from this dataset tonight.

Troy mentions some arguments against torrents, but it is better to have a authoritative torrent than none, imo.

A signed minimal perfect hash function may be a better bet. You can get down to around 2.68 bits per key plus w sign bits where the false positive rate is 2^-w.

For false positive rate of 2^-9 (0.00195) that's 447 MB, which is slightly less than an optimal bloom filter for the same number of items, and lookups will be considerably faster.

Construction time and the fact that you can't add to it without rebuilding the whole thing are the downsides. But given the application I don't think they matter much.

http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/Minimal...

Is a bloom filter worth it in this case? With the optimal "k" hash functions of 10 and a "p" error rate of 0.001% (false positives of approximately 1 in 1000), a bloom filter for the 306,259,512 items will take 538 MB. Increasing the error rate to 0.01% (1 in 100) is still 358 MB. That's a sizeable filter to maintain in memory (then again... RAM is cheap).

I'd probably just shove the passwords into a database, limiting the index prefix to the first X characters to reduce index size.

Distributing a 538 MB file (which can be compressed further) is much easier.

What are the actual use cases where this size difference matters?

I distributing to a general audience, 0.5GB and 10GB isn't that much of a difference, and most people are more equipped for handling lists of strings than for handling bloom filters.

>which can be compressed further

Can it? I think of a bloom filter as similar to a lossy compression scheme and wouldn't expect it to be further compressible to any significant extent using a general purpose lossless scheme. Similar to how general purpose compressors generally don't do very well with mp3s or jpgs.

Reducing the size by ~95% in exchange for a 0.001% error rate seems like a pretty nice tradeoff to be able to make for some uses.

The nature of the data means it can never really be "perfect" anyway (there are certainly some password breaches that exist but aren't included in the list), so massively reducing the resources required in exchange for a bit of artificial error seems pretty reasonable to me.

If it doesn't have to be really fast, you can simply binary search fetching no more than 29 lines from the file. Or you can interpolate the expected location of the hash and read a block around that location. This could get you down to reading only one or two disk blocks if the actual position is never more than half a disk block away from the interpolated position. It could be more but given that we are dealing with cryptographic hashes I would expect the interpolated position to never be too far away from the actual position.

It's also a bummer there are only sha1's in the file. It would be good to block things within hamming distance 2 of a leaked password (so p@ssw0rd€ would also be blacklisted...)

You could go the other way, and check likely candidates from the new password - e.g. if user enters "hunter2", you check hunter and hunter0 and hunter1 and hunter3 and hunt3r2.

Or better a cookoo filter:

http://dl.acm.org/citation.cfm?doid=2674005.2674994

Reply on news.ycombinator.com