services/bloom_filter library
Airpass Protocol — Bloom Filter
A compact, serializable probabilistic set membership test used for pre-sync message deduplication.
How It's Used
Before exchanging the full sync payload, each peer sends a Bloom filter containing the IDs of all messages it already has. The other peer uses this filter to exclude messages the receiver already has, dramatically reducing bandwidth in dense meshes.
False Positive Tradeoff
A Bloom filter can produce false positives ("probably in set") but never false negatives ("definitely not in set"):
- False positive (1% default): We skip sending a message the peer doesn't actually have. That message will arrive via another path or on the next encounter. Acceptable in epidemic routing.
- False negative (impossible): We would never send a message the peer already has. This is guaranteed by the data structure.
Wire Format
[0xBF, 0x00] [bitCount: 4 bytes LE] [hashCount: 1 byte] [bit array...]
The magic prefix 0xBF 0x00 distinguishes Bloom filter payloads from
gzip sync payloads (which start with 0x1F 0x8B).
Classes
- BloomFilter
- A space-efficient probabilistic set membership test.
Constants
-
kBloomFilterMagic
→ const List<
int> -
Magic bytes prefixed to serialized Bloom filters.
Distinguishes them from gzip sync payloads (
0x1F 0x8B).