Bloom Filter

What Is a Bloom Filter?

A bloom filter is a probabilistic data structure invented by Burton H. Bloom in 1970. It answers a simple question: "Is this element in the set?" The answer is either "definitely no" or "probably yes." This one-sided certainty makes bloom filters useful wherever fast, space-efficient set membership testing matters more than absolute precision.

In Bitcoin, bloom filters were introduced through BIP 37 (2012) to help lightweight wallets sync with the network without downloading every transaction. An SPV client would construct a bloom filter containing its wallet addresses and send it to a full node, which would then relay only matching transactions. This worked but came with a critical flaw: the filter itself revealed which addresses the client cared about, undermining user privacy.

How It Works

A bloom filter consists of a bit array of m bits (all initially set to 0) and k independent hash functions. Each hash function maps an input to one of the m positions in the array.

Inserting Elements

To add an element to the filter, pass it through all k hash functions. Each function returns a position in the bit array. Set every returned position to 1.

// Simplified bloom filter insertion
function insert(filter, element, hashFunctions) {
  for (const hashFn of hashFunctions) {
    const position = hashFn(element) % filter.length;
    filter[position] = 1;
  }
}

Querying Elements

To test whether an element is in the set, hash it with the same k functions and check the corresponding bit positions:

• If any position is 0, the element was never inserted. This is a definitive negative: no false negatives are possible.
• If all positions are 1, the element is probably in the set. However, those bits may have been set by other elements, creating a false positive.

// Simplified bloom filter query
function mightContain(filter, element, hashFunctions) {
  for (const hashFn of hashFunctions) {
    const position = hashFn(element) % filter.length;
    if (filter[position] === 0) return false; // Definitely not in set
  }
  return true; // Possibly in set (may be false positive)
}

False Positive Rate

The probability of a false positive after inserting n elements into an m-bit filter with k hash functions is approximately:

P(false positive) = (1 - e^(-kn/m))^k

Optimal hash functions:  k = (m/n) * ln(2)
Required bits:           m = -n * ln(p) / (ln 2)^2

At a 1% false positive rate, a bloom filter requires only about 9.6 bits per element, regardless of element size. This extreme space efficiency is what made bloom filters attractive for bandwidth-constrained SPV clients: storing thousands of Bitcoin addresses (each 20+ bytes) requires only a few kilobytes of filter data.

Bloom Filters in Bitcoin (BIP 37)

BIP 37, authored by Mike Hearn and Matt Corallo in October 2012, added bloom filter support to the Bitcoin peer-to-peer protocol. The goal was to let SPV clients receive only wallet-relevant transactions instead of downloading every transaction in every block.

Protocol Flow

1. The SPV client constructs a bloom filter containing its addresses, public keys, and outpoints of interest
2. The client sends the filter to a full node via the filterload message
3. The full node tests each transaction in new blocks against the filter
4. Matching transactions are delivered via merkleblock messages containing the block header plus a Merkle proof that the transaction was included in the block

BIP 37 Protocol Messages

BIP 37 used MurmurHash3 (32-bit) for its hash functions, with each function seeded by the formula nHashNum * 0xFBA4C795 + nTweak, where nTweak is a random value chosen by the client.

The Privacy Problem

While BIP 37 reduced bandwidth for light clients, it introduced a severe privacy leak. A full node receiving a bloom filter can test candidate addresses against it to determine which addresses belong to the client. With the low false positive rates used by real wallets, the filter essentially broadcast the client's entire address set to any connected peer.

Research Findings

A 2014 paper by Gervais, Karame, Gruber, and Capkun ("On the Privacy Provisions of Bloom Filters in Lightweight Bitcoin Clients," ACSAC 2014) demonstrated that an SPV client using fewer than 20 Bitcoin addresses risked revealing almost all of them to any connected full node. With just 10 addresses in the filter, the probability of correctly identifying them was approximately 0.99.

In 2015, researcher Jonas Nick analyzed BitcoinJ (the most widely used SPV library, powering Android Wallet and MultiBit). He found that BitcoinJ included both public keys and public key hashes in its bloom filter, reducing the effective false positive rate to approximately 0.0000000213. A fresh wallet with 271 public keys produced roughly one false positive when scanned against the entire blockchain, meaning nearly every address could be identified. His conclusion: SPV users had "practically zero wire privacy."

Three Attack Vectors

• Direct testing: a node tests every known address against the received filter, and with a low false positive rate, matches almost certainly belong to the client
• Intersection attack: when a wallet reconnects and sends a new filter, an adversary can intersect multiple filters to eliminate false positives and reveal the true address set
• Transaction graph analysis: combining filter data with public blockchain transaction patterns allows adversaries to distinguish true positives from false positives

These weaknesses led Bitcoin Core to disable BIP 37 bloom filter serving by default in version 0.19.0 (November 2019). The cited reasons were both the privacy problems and denial-of-service risks, as processing bloom filters is CPU-intensive and could be weaponized against nodes.

The Replacement: Compact Block Filters

BIP 157/158 (authored by Olaoluwa Osuntokun, Alex Akselrod, and Jim Posen in 2017) took the opposite approach to light client filtering. Instead of clients sending filters to servers (server-side filtering), full nodes generate deterministic filters for each block and clients download and test them locally (client-side filtering).

Compact block filters use Golomb-Rice coded sets instead of bloom filters, achieving better compression. The basic filter type has a false positive rate of approximately 1 in 784,931. When a filter matches, the client downloads the full block from any peer. The total monthly bandwidth for downloading all filters is approximately 70 MB. For a deeper look at how SPV clients evolved, see the Bitcoin light clients and SPV explained research article.

Other Uses in Bitcoin

Beyond BIP 37, Bitcoin Core uses rolling bloom filters internally for transaction relay optimization:

• The recentRejects filter tracks recently rejected transaction IDs (120,000 entries, 1-in-1,000,000 false positive rate) to avoid re-validating the same invalid transaction announced by multiple peers
• Per-peer bloom filters track which transactions were recently announced to each peer, preventing redundant data transmission
• A rolling bloom filter of confirmed transaction IDs prevents nodes from re-requesting transactions that are already in recent blocks

These internal uses are separate from BIP 37 and do not expose filters to external peers, avoiding the privacy issues that plagued SPV bloom filtering.

Why It Matters

The bloom filter story in Bitcoin is a case study in the tension between efficiency and privacy. BIP 37 solved a real problem: mobile wallets needed a way to sync without downloading the entire blockchain. But the solution leaked enough information that researchers could identify wallet addresses with near-certainty.

The replacement, compact block filters, trades slightly more bandwidth for genuine privacy. This same design philosophy carries forward into modern Bitcoin layer-2 protocols: solutions like Spark prioritize both efficiency and privacy, using techniques like FROST threshold signatures to avoid exposing sensitive information while keeping operations lightweight.

Risks and Considerations

False Positives Are Unavoidable

Any bloom filter will occasionally report that an element is in the set when it is not. For applications where false positives have consequences (triggering unnecessary block downloads, for example), the filter must be sized carefully. Reducing the false positive rate requires more bits per element, increasing memory and bandwidth costs.

No Deletion Support

Standard bloom filters are append-only. Once a bit is set to 1, it cannot be cleared without rebuilding the entire filter. BIP 37 reflected this limitation: there was a filteradd command but no filterremove. Variants like counting bloom filters support deletion but require more memory.

Privacy Remains a Concern for Legacy Clients

Although Bitcoin Core disabled BIP 37 by default in 2019, some older nodes still serve bloom filter requests with the -peerbloomfilters=1 option enabled. SPV wallets that still rely on BIP 37 continue to leak address information to connected peers. Users concerned about privacy should use wallets that support compact block filters (BIP 157/158) or connect to their own full node.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.