<story><title>Blooming Password – A banned password check using a bloom filter</title><url>https://www.bloomingpassword.fun/</url></story><parent_chain><item><author>bloomthrowaway</author><text>Sorry to say this, but this is actually worse than just truncating the hash.&lt;p&gt;Why? Bloom filters are designed to maintain a reasonable false positive rate while still allowing you to add items extremely quickly (high insertion rate).&lt;p&gt;Since the bad password list is presumably fixed (or almost so) you can do checks faster and with a lower FP rate by just truncating the hashes and prefix sorting the list ahead of time.</text></item></parent_chain><comment><author>teraflop</author><text>I get your point but I don&amp;#x27;t think it&amp;#x27;s accurate. If the list contains 500 million hashes (approximately 2^29), then in order to achieve a false positive rate of 0.001, you must store at least a 39-bit prefix of each hash. A Bloom filter can do better -- approximately 14 bits per entry -- because it uses multiple hash functions.</text></comment>
<story><title>Blooming Password – A banned password check using a bloom filter</title><url>https://www.bloomingpassword.fun/</url></story><parent_chain><item><author>bloomthrowaway</author><text>Sorry to say this, but this is actually worse than just truncating the hash.&lt;p&gt;Why? Bloom filters are designed to maintain a reasonable false positive rate while still allowing you to add items extremely quickly (high insertion rate).&lt;p&gt;Since the bad password list is presumably fixed (or almost so) you can do checks faster and with a lower FP rate by just truncating the hashes and prefix sorting the list ahead of time.</text></item></parent_chain><comment><author>honoredb</author><text>But that&amp;#x27;s still 12G of memory, since you can&amp;#x27;t compress it. Is there a data structure that&amp;#x27;s better optimized for space and probabilistic membership tests?</text></comment>