Where Bloom Filters Live in Real Systems

Bloom filters are not a classroom curiosity. Most of the systems below rely on one to avoid work that would otherwise be repeated millions of times. After a short tour, you will build one of them byte for byte: the filter a Bitcoin light wallet sends to a full node, checked against the published test vectors from Bitcoin Core.

Databases

LevelDB, RocksDB, Cassandra, HBase and Bigtable store data in immutable files (SSTables). A point lookup might have to search many of them, and each search is a disk read. So every file carries a small Bloom filter of its keys, usually about 10 bits per key (a 1% false-positive rate). A NO skips the file without touching the disk; a false positive costs one wasted read. Because the files are immutable, the filter is built once when the file is written and thrown away with it, so these systems never need to delete from a Bloom filter.

Caches, networks and browsers

• CDN invalidation. When content changes at the origin, edges receive a filter of invalidated URLs. MAYBE means "recheck with the origin", NO means "serve from cache". A false positive costs one extra recheck. A false negative would serve stale content, which is exactly the error a Bloom filter cannot make.
• Cache digests and URL blocklists (Squid; an early Chrome Safe Browsing): a filter of what a peer holds, or of known-bad URLs, so only a MAYBE costs a request or a server lookup.

Bitcoin: BIP 37

A light wallet wants only the transactions that involve its own addresses, but it does not want to download every block. BIP 37 lets it send a Bloom filter of its addresses to a full node; the node forwards only the transactions that match. False positives return a few unrelated transactions, which was meant to blur which addresses are the wallet's. (That privacy turned out to be weak, and BIP 157/158 replaced it with a different scheme.) The filter is a precise byte format, which makes it an excellent test of everything in this course.

Sizing

For n elements and false-positive rate p, with LN2 = 0.6931471805599453 and LN2SQ = 0.4804530139182014:

bits   = min( trunc(-1 / LN2SQ * n * ln(p)), 36000 * 8 )
bytes  = bits / 8                        (integer division)
hashes = min( trunc( (bytes * 8 / n) * LN2 ), 50 )    where bytes * 8 / n is an INTEGER division

Where the bits go

Hash function number i (0, 1, 2, ...) is MurmurHash3 of the element's bytes with the seed

seed_i = (i * 0xFBA4C795 + tweak) mod 2^32

and the bit index is murmur3(data, seed_i) mod (bytes * 8). Bit x is bit x mod 8 (from the least significant) of byte x / 8. The tweak is a random number the wallet picks so that two wallets' filters differ.

The filterload payload

+------------+-----------------+--------------+-----------+---------+
| compact N  | N filter bytes  | hashes (u32) | tweak     | flags   |
| 1 or 3 B   |                 | little-end.  | (u32) LE  | (u8)    |
+------------+-----------------+--------------+-----------+---------+

compact N is the byte count N: if N < 253 it is one byte, otherwise the byte 0xfd followed by N as 2 bytes, little-endian.

Worked example

Size a filter for n = 8, p = 0.05, tweak = 7: 6 bytes (48 bits) and 4 hash functions. Two elements, given as hex, hash like this:

ab    seeds 0x00000007, 0xfba4c79c, 0xf7498f31, 0xf2ee56c6
      bit indexes 31, 5, 13, 34
cafe  seeds 0x00000007, 0xfba4c79c, 0xf7498f31, 0xf2ee56c6
      bit indexes 20, 38, 46, 26

The bytes after inserting both are 202010844440. With flags = 0 the whole filterload payload is

06202010844440040000000700000000

which you can split into the length byte 06, the 6 filter bytes 202010844440, then 04000000 (hashes = 4), 07000000 (tweak = 7) and 00 (flags).

Common mistakes

• Dividing in floating point. bytes * 8 / n is an integer division in the reference code. For 9 elements at 1% that gives 5 hashes, not 6, and a different filter.
• Computing the seed in 64 bits and not wrapping it to 32. The seed for i = 2 and above overflows 32 bits.
• Hashing the hex text instead of the decoded bytes.
• Using the byte count where the bit count belongs: positions are mod (bytes * 8).
• Writing the length, hashes or tweak big-endian.

Your exercise

The starter provides MurmurHash3, the hex decoding, and INSERT, CONTAINS and INDEXES. You write the sizing in INIT, the per-hash bit index, and the FILTERLOAD serialisation.