MASTERING-BITCOIN · Unit 11 · Video 5

Maybe Yes, Definitely No: Bitcoin's Bloom Filter — Interactive Practice

IKey Formulas and Facts

Concept	Formula / Rule	Meaning
False positive rate	$P_{FP} \approx \left(1 - e^{-kn/m}\right)^k$	Probability filter says "maybe yes" when answer should be "no"
Optimal hash count	$k^* = \frac{m}{n}\ln 2$	Hash functions minimizing $P_{FP}$ for given $m$ , $n$
Bloom filter rule	Definitely No, Maybe Yes	False negatives are impossible; false positives are inherent
Bits flipped	One per (hash, item) pair, with collisions	Patterns cannot be removed — collisions are permanent

where $m$ is filter size in bits, $n$ is the number of inserted items, and $k$ is the number of hash functions.

IIVisualization 1: Building a Bloom Filter

Conceptual question: As we add more addresses to a bloom filter, how does the bit array fill up, and where do collisions occur?

Use the slider to choose how many addresses to insert into a 32-bit filter with $k = 3$ hash functions. Watch which bits flip on and where the same bit gets hit by multiple addresses (collisions) — those collisions are exactly what creates ambiguity.

⚙ interactive visualization — coming to this page format soon

Notice: When two addresses land on the same bit (red cells in the top row), the filter loses information about which address put the bit there. With only 2 addresses you may see few or no collisions; by the time you reach 8 addresses, collisions are routine. That ambiguity is the source of bloom-filter privacy — and, as we'll see, also the reason a malicious full node can still recover your wallet.

IIIVisualization 2: The Privacy / Bandwidth Dial

Conceptual question: BIP37 let wallets choose their own filter size. What's the actual trade-off between filter size and false-positive rate (the cover that hides real transactions)?

The false-positive probability after inserting $n$ items into a filter of $m$ bits with $k$ hash functions is

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

Use the controls below to see how this curve shifts. Higher $P_{FP}$ means more noise the wallet receives — more cover, more privacy, more bandwidth. Lower $P_{FP}$ means precision — and exposure.

⚙ interactive visualization — coming to this page format soon

Reflect: Try pushing $m$ down to 64 with $k=3$ — the curve climbs toward 1.0 fast, meaning almost everything looks like a "maybe yes". Now push $m$ up to 2048 — $P_{FP}$ stays low, so the peer barely sees any false matches. That's the dial the tourist was turning when they decided between asking about "streets ending in URCH" (precise) and "streets ending in H" (noisy). BIP37 handed this dial to the wallet.

IVQuiz Questions

Question 1

You query a bloom filter for a pattern. One of the three bits at the hashed indices is 0. What can you conclude?

✅ Correct! A single zero bit guarantees absence — that's the 'Definitely No' half of the bloom filter mantra.

❌ Not quite. Remember the mantra: Definitely No, Maybe Yes. A zero bit is the strongest signal a bloom filter can give.

Show solution

Solution:

The defining asymmetry of a bloom filter is: Definitely No, Maybe Yes.

If any of the $k$ queried bits is 0, the item was never inserted — because inserting it would have flipped that bit to 1, and bits are never cleared. So:

One zero bit → definitely not present. (No false negatives.)
All ones → maybe present. (False positives are possible due to collisions.)

Three bits queried; one is 0; we stop immediately. Definitely not present.

Question 2

True or False: To remove an address from a BIP37 bloom filter, the wallet sends a filterremove message that clears the bits corresponding to that address's hashes.

✅ Correct! Collisions make removal impossible — clearing one bit would corrupt every other pattern that touched it. BIP37 has filteradd and filterclear, but no filterremove.

❌ Not quite. Think about why: if two addresses both hashed to bit 7, clearing bit 7 to remove one would also break lookups for the other. There is no safe way to delete from a bloom filter.

Show solution

Solution:

This is False. Patterns cannot be removed from a bloom filter, and there is no filterremove message.

Why? Because of collisions. A single bit may have been set by hashes from many different inserted items. Clearing that bit to remove one address would also "remove" parts of every other address that touched it — creating false negatives, which would break the filter's only hard guarantee.

The actual BIP37 messages are:

filterload — install a new filter (rebuild from scratch).
filteradd — insert additional patterns (only ever flips more bits to 1).
filterclear — wipe everything and start over.

To "refine" a filter you must rebuild it.

Question 3

A wallet inserts $n = 200$ patterns into a bloom filter of size $m = 1000$ bits using $k = 5$ hash functions. Using the formula

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

which value is closest to the false-positive probability? (Hint: $kn/m = 1$ , so $e^{-1} \approx 0.368$ .)

✅ Correct! $(1 - e^{-1})^5 = (0.632)^5 \approx 0.09$ . About 9% noise — substantial cover, but as the next question explores, not enough.

❌ Not quite. Compute $kn/m = 1$ , so the base of the power is $1 - e^{-1} \approx 0.632$ . Then raise to the $k = 5$ power.

Show solution

Solution:

Plug in $k = 5$ , $n = 200$ , $m = 1000$ :

$\frac{kn}{m} = \frac{5 \cdot 200}{1000} = 1.$

$P_{FP} \approx \left(1 - e^{-1}\right)^{5} = (1 - 0.368)^5 = (0.632)^5.$

Computing $(0.632)^5$ :

$(0.632)^2 \approx 0.399, \quad (0.632)^4 \approx 0.159, \quad (0.632)^5 \approx 0.159 \times 0.632 \approx 0.10.$

So $P_{FP} \approx 0.09$ , or about 9%. Roughly one in eleven queried items the peer sees will look like a match purely by accident — that's the "noise" hiding real wallet traffic.

Question 4

Researchers showed in 2014 that a malicious full node could deanonymize most addresses in a real BIP37 filter. What was the key insight that broke the privacy promise?

✅ Correct! Graph analysis separates signal (the connected wallet cluster) from noise (isolated false-positive nodes). Probabilistic obfuscation can't hide structural connectivity.

❌ Not quite. The attack didn't break any cryptographic primitive — it exploited the public structure of the blockchain itself. Think about how real transactions are linked versus how false-positive matches relate to each other.

Show solution

Solution:

The right answer is: real wallet transactions form a connected graph, while false positives are isolated.

A bloom filter doesn't encrypt anything — it obfuscates through collision. But a full node has the entire blockchain, so it can:

Test every address ever used against the wallet's filter.
Collect the set of "maybe yes" matches.
Draw the transaction graph: outputs of one tx become inputs of another (parent → child).

Real wallet transactions cluster along this graph. False positives, generated by random hash collisions on unrelated addresses, do not connect to anything. They float as isolated nodes.

Run a connected-components analysis on the matches, throw away the orphans, and what remains is the wallet. The noise drops away.

The other options are wrong:

❌ SHA-256 is not reversed — the attack doesn't need to invert hashes.
❌ Private keys aren't recovered — only the set of addresses used by the wallet.
❌ The filter is not encrypted; that was the whole problem.

This is why BIP37 was replaced by BIP157/158 compact block filters, which invert the model: the node publishes a filter per block to everyone, and the wallet checks locally. The node learns nothing.

Solved: 0 / 4