The data structure that answers "probably not"

Here is a structure whose pitch sounds like a swindle: it answers membership questions about a set without storing the set, in about nine bits per item regardless of how large the items are, and it is never wrong when it says no.

The catch is in the other answer. It cannot say yes. It says maybe, and you get to choose in advance how often "maybe" is a lie — 1%, 0.1%, whatever you're willing to pay bits for. That asymmetry sounds like a defect and is the entire product, because an enormous number of real systems are built around a question where a cheap "definitely not" is worth almost as much as a certain "yes."

I have used this twice in this blog without explaining it. It's the logsBloom field in every Ethereum block header, and it's BIP37, the light-client mechanism Bitcoin Core switched off by default after it turned out to leak everything. Both times I described the local behaviour and moved on. This is the structure itself, the arithmetic that sizes it, and an honest look at the three deployments — because the same filter is close to the best trade in database engineering in one of them and nearly worthless in another, and the difference is arithmetic you can watch happen.

Nothing here is a mockup. Every filter below is real, backed by SHA-256, and every false-positive rate is either computed from the standard formula or measured by probing a real filter with thousands of items it never saw. The two agree to a fraction of a percent, which is the only honest reason to believe an approximation.

01 · Bits, not items

Start with the mechanism, which is smaller than you expect. A Bloom filter is an array of m bits, all zero, and k hash functions. That's the whole structure — there is no second field, no list, no items anywhere.

To add something: hash it k ways, get k positions, set those bits to 1.

To ask about something: hash it the same k ways and look. If any probed bit is 0, the item was definitely never added — setting bits is the only thing add does, and it never unsets. If all k bits are 1, then either the item was added, or other items happened to set all k of its bits between them. The filter genuinely cannot tell those apart, so it says maybe.

Add things, then interrogate it:

Things worth watching for:

• "No" is proof; "maybe" is a rumour. A single clear bit ends the question with certainty. That asymmetry is structural rather than statistical — there is no tuning that produces a false negative, and no tuning that eliminates false positives.
• Nothing went in. Look at the array: it is bits. You cannot enumerate what was added, you cannot read anything back, and two different sets can produce identical filters. That's the space win, and it's also why people reach for these when they shouldn't — see BIP37 in section 05.
• Press "find a false positive." With a small m and a few dozen items, the filter will happily swear it might have seen something nobody ever added. Add twenty more and watch the array fill up and the lying get worse.
• k cuts both ways. More hashes mean a more distinctive fingerprint per item, and also more bits set per insert. Drag it and watch the fill rate climb. That tension has an exact optimum, which is the next figure.

02 · The arithmetic, and then the measurement

Three numbers decide a Bloom filter's behaviour: m bits, n items, k hashes. Everything else follows, and the derivation is short enough to do here.

A given bit survives one hash unset with probability 1 − 1/m. After n items with k hashes each, that's kn chances to be hit, so the bit is still clear with probability (1 − 1/m)^(kn), which for a large m is about e^(−kn/m). A false positive is all k probed bits happening to be set at once:

$p \approx \left(1 - e^{-kn/m}\right)^{k}$

Differentiate that with respect to k and the minimum sits at k = (m/n)·ln 2 — the point where exactly half the array is set. Substitute back and invert, and you get the number to actually remember:

$m = -\frac{n \ln p}{(\ln 2)^2}$

Drag all three and watch the formula and a real filter agree:

Things worth watching for:

• The measured column is a real filter. It builds one with your m and k, inserts n items, then probes four thousand items it never saw and counts the hits. It tracks the formula to a fraction of a percent — and the formula is a slight underestimate, because it assumes the k probed bits are independent and they aren't quite.
• The curve has a real minimum, and both sides of it are bad. Too few hashes and each item barely marks the array, so a single unlucky bit decides everything. Too many and every insert floods more bits until the array saturates and every probe finds them all set. Click along the curve and watch it turn around.
• Nine and a half bits per element, per 1%. That number falls out of −ln(p)/(ln2)² and it is the one worth memorising. 1% costs 9.6 bits per item; 0.1% costs 14.4; 0.01% costs 19.2. Each factor-of-ten improvement costs about 4.8 more bits — and none of it depends on how large the items are. A filter over million-character URLs costs the same per item as one over integers.

That last point is the whole reason the structure exists. Store the items and you pay for the items; store a Bloom filter and you pay for the count.

03 · Why you cannot remove anything

Here is where the compression stops being free. The obvious way to delete an item is to clear its k bits. Try it:

Things worth watching for:

• Removing one item silently removes others. Bits are shared. Clearing bruno's bits also clears bits that carla and diego were relying on, and now the filter answers "no" for items that really are in the set. That's a false negative — the one error a Bloom filter exists to never make. It isn't a bug in the deletion code; there is no correct deletion code.
• Counting filters fix it by storing more. Replace each bit with a small counter, increment on add, decrement on remove, and a slot shared with another item stays above zero. The price is the point: four bits per slot instead of one, so the same false-positive rate costs four times the memory.
• And counters introduce a new failure. A counter that saturates has lost track of how many items share it, and decrementing it would under-count. A correct implementation has to refuse — so a counting filter that gets hot in one spot degrades in a way the plain one can't.

Two honest notes on what people reach for in 2026. If you need deletion, a cuckoo filter usually beats a counting Bloom filter: it stores short fingerprints in a hash table, supports deletion properly, and uses less space than Bloom below roughly 3% false positives. And very often nobody needs deletion at all — the set is an immutable on-disk table that will never change — which is exactly why the plain filter still dominates in databases.

04 · Where it earns its keep

The single largest deployment of Bloom filters is not a blockchain, and it's worth naming because it's the case where the trade is close to perfect: log-structured merge trees. RocksDB, LevelDB, Cassandra, HBase, and by extension a very large fraction of the data you interact with daily.

An LSM-tree stores data in many immutable on-disk tables. A read that isn't in memory has to ask "is this key in this table?" for table after table, and every wrong guess is a disk seek — the single most expensive thing the database does. So each table carries a Bloom filter over its keys, typically at ten bits per key. Roughly 99% of the tables that don't contain your key are eliminated without touching the disk, and the 1% that slip through cost exactly one wasted seek and are then resolved correctly by the real lookup.

Read that last clause again, because it's the criterion for whether a Bloom filter is the right tool: a false positive costs work, not correctness. The filter is an optimization in front of a source of truth. Nothing it says can produce a wrong answer, only a slow one. Every good deployment has that shape, and every bad one doesn't.

Some others with the same shape: CDNs use a filter to avoid caching "one-hit wonders" — URLs requested exactly once — by only caching on the second sighting. Web browsers historically used one to check URLs against a malicious-site list locally before asking a server. Spell-checkers used them when a dictionary didn't fit in memory, which is what Burton Bloom was writing about in 1970.

05 · Three real deployments, one of which is a warning

Now the comparison, with real parameters and the rates computed rather than asserted:

Things worth watching for:

• Ethereum's filter saturates, and you can watch it happen. logsBloom is fixed by consensus at 2048 bits with 3 hashes. Each log contributes its contract address plus up to four topics, so a block with a few hundred logs puts n in the thousands — and at n = 1500 the false-positive rate is over 70%. Drag the item count up. Past a point "maybe" carries no information at all and a client reads the logs regardless. The parameters were frozen in 2015 against a workload nobody had seen yet, and they cannot be changed without a hard fork.
• The LSM row is the good one. Ten bits per key, k = 7, about 1% — and the k they chose is the optimal k. This is what it looks like when the parameters match the workload.
• BIP37's arithmetic was fine. That's what makes it the interesting failure. A Bitcoin SPV wallet built a filter over its own addresses and sent it to a stranger's full node, which replied with matching transactions. The maths worked exactly as designed — and researchers showed that the filter's own bits identify the wallet's addresses with embarrassing ease, because a filter built from your set is a fingerprint of your set. Bitcoin Core stopped serving them by default in 2019.

That third one is the lesson the formula cannot express. A Bloom filter is compact and irreversible-looking, and neither of those makes it private. It is not a hash of your data in the sense that matters; it is a lossy sketch that still narrows the search space enormously. If you are tempted to send one somewhere because "it's just bits," BIP37 already ran that experiment.

The replacement is worth a sentence because it inverts the direction rather than improving the filter. BIP157/158 has the server build one compact filter per block — a Golomb-coded set, which is a different structure that compresses sorted hashes rather than setting bits — and the client downloads filters and checks them locally. The server learns nothing, because the client never asks about anything specific. The fix wasn't a better filter; it was noticing that asking a stranger about yourself is the leak.

06 · What's next

The compressed model: m bits, k hashes, no items. Adding sets k bits; asking checks k bits; a single clear bit is a definite no and all-set is a maybe. False positives are tunable and false negatives are impossible, which is what makes the structure a legitimate optimization in front of a source of truth and a terrible one anywhere the answer is final. Size it with m = −n·ln(p)/(ln2)² and use k = (m/n)·ln2 hashes — about 9.6 bits per item per 1%, independent of item size. You cannot delete without storing more, and being compact is not the same as being private.

The honest edges. My filters derive their k indices from one SHA-256 by the Kirsch–Mitzenmacher trick — h₁ + i·h₂ — which is what real implementations do and does not change the rate, but it means "k hash functions" is a figure of speech. The rate formula is the standard approximation and slightly understates the truth. The Ethereum item count in section 05 is a plausible range for a busy block rather than a capture from a specific one; the 2048 bits and 3 hashes are exact and from the Yellow Paper. And I have described cuckoo filters without building one — that's a real structure with real trade-offs I've only summarized.

Where this shows up:

• The blockchain is a log file: BIP37's rise and fall, and the BIP157 inversion that replaced it
• Ethereum's entire state fits in 32 bytes: the M3:2048 filter in the block header, with its three bits per topic
• Merkle trees: the other structure this blog kept using without explaining — the one that answers with certainty, and what that certainty costs

Same promise as always: it's bits all the way down, and every rate on this page was either derived or counted.