This is a read note of Programming Bitcoin Ch12: Bloom Filters. Bloom filter is used by a light client to tell the full node enough information to create a superset of all transactions of interest without giving accurate addresses.

1 Bloom Filter

A Bloom filter is a filter for all possible transactions. Full nodes run transactions through a Bloom filter and send merkleblock commands for transactions that make it through.

For a 32 bit field (the bucket size), five hash functions generate 32! / (27! * 5 !) about 200,000 possible 5-bit combinations. Of 1 million possible items, 5 items may have that 5-bit combination. A Bloom filter can be optimized by changing the number of hash functions and bit field size to get a desirable false-positive rate.

2 BIP0037

BIP0037 specifies Bloom filters in network communication. In practice, we use a single hash function with a different seed. The hash function we use is called murmur3. Unlike sha256, murmur3 is not cryptographically secure, but it is much faster. The task of filtering and getting a deterministic, evenly distributed modulo does not require cryptographic security but benefits from speed, so murmur3 is the appropriate tool for the job.

Once a light client has created a Bloom filter, it needs to let the full node know the details of the filter so the full node can send proofs of inclusion. The command to set the Bloom filter is called filterload. Another command, the getdata command is what communicates blocks and transactions.