Bloom filter
Also called: BIP 37, BIP37, connection Bloom filtering, filterload, SPV Bloom filter.
A Bloom filter is a compact probabilistic set; BIP 37 used one so light wallets could ask full nodes for only the transactions matching their addresses.
A Bloom filter is a compact data structure for testing whether an item is in a set. It can give false positives but never false negatives. In Bitcoin the term usually means connection Bloom filtering from BIP 37, by Mike Hearn and Matt Corallo, which let lightweight (SPV) wallets sync without downloading every transaction.
How BIP 37 Bloom filtering works
- The wallet builds a Bloom filter containing its public keys, addresses and outpoints, tuned to include some false positives as cover.
- It sends the filter to a full node with filterload (at most 36,000 bytes and 50 hash functions); filteradd and filterclear update or remove it.
- The node relays only matching transactions and answers block requests with merkleblock messages: the block header plus a partial Merkle tree proving the matching transactions are in the block.
Why Bloom filters fell out of favor
- Privacy. In practice the filters revealed far more about the wallet than intended, since a node can test any address against them and compare filters over time.
- Load on nodes. Each client makes the node scan data with its own filter, which can be abused for denial of service.
BIP 111 added the NODE_BLOOM service bit so nodes can say whether they offer the service, and Bitcoin Core turned it off by default in version 0.19. The modern alternative is compact block filters (BIP 157, BIP 158), which reverse the model: the node publishes one filter per block and the wallet does the matching itself.