Bloom Filter

Bloom filters were invented by Burton Howard Bloom in 1970. They are a space-efficient probabilistic data structure that answers "is this element in the set?" with either "definitely not" or "possibly yes."

**How Bloom filters work:** - A fixed-size bit array (e.g., 2048 bits) - Multiple hash functions map an element to bit positions in the array - To add element: set the bits at those positions to 1 - To query element: check if all bit positions are 1; if any is 0, element is definitely NOT in set; if all are 1, element might be in set (false positive possible)

**False positives, never false negatives:** Bloom filters can incorrectly report an element as present (false positive) but never miss an element that's actually present (no false negatives). The false positive rate is tunable by adjusting the bit array size and number of hash functions.

**In Ethereum:** Each Ethereum block header contains a 2048-bit Bloom filter encoding all addresses and topic hashes from events emitted in that block. This allows: - Light clients to scan block headers for transactions relevant to their addresses without downloading full blocks - `eth_getLogs` RPC calls to pre-filter blocks before full inspection - Indexers to efficiently build event logs without processing every transaction

**Limitations in Ethereum:** The 2048-bit Bloom filter on Ethereum has a relatively high false positive rate for blocks with many events. This is why `eth_getLogs` still requires full block inspection after Bloom filtering — the filter eliminates clearly irrelevant blocks but doesn't guarantee event presence.