Bloom Filter

A Bloom filter is a probabilistic data structure that tests whether an item might belong to a set, using very little memory and allowing false positives but never false negatives. In Bitcoin, BIP 37, published in 2012, used Bloom filters to let lightweight wallets ask full nodes for relevant transactions without naming their addresses outright.

Why it matters

Bloom filters were the first serious attempt to make simplified payment verification wallets practical on phones. A wallet could sync in minutes by downloading only block headers plus the handful of transactions matching its filter, rather than the full multi hundred gigabyte chain. The privacy promise, hiding addresses inside deliberate false positives, largely failed in practice. Research showed that a node observing a wallet's filters over time could recover most of its addresses, and filter serving also exposed full nodes to denial of service load. Modern light clients have largely moved to BIP 157 and BIP 158 compact block filters, which invert the model so the node reveals a digest of each block and the wallet checks it locally, revealing nothing.

How it works

The filter is a bit array. Each inserted item is run through several hash functions, and the resulting positions are set to 1. To test membership, the same hashes are computed: if any position is 0 the item is definitely absent, and if all are 1 it is probably present. Tuning the array size and hash count sets the false positive rate, which in BIP 37 doubled as an imprecise privacy dial.