THE FOLD / BOSS / THE FIREWALL / THE XOR FILTER
THE XOR FILTER
a set in 1.23 bytes a key
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The XOR filter is a modern, leaner cousin of the Bloom filter for testing membership of a fixed set. It stores a table of small fingerprints so that for every key x, its 8-bit fingerprint equals the XOR of three table slots the key hashes to: fp(x) = t[h₀(x)] ⊕ t[h₁(x)] ⊕ t[h₂(x)]. Building it is a graph peeling: repeatedly take a slot touched by only one key, and assign that slot last so the XOR comes out right. The result uses about 1.23 bytes per key — smaller than Bloom for the same false-positive rate — with no false negatives and a rate near 2−8.
LIT verified live: across many builds, every member’s three-slot XOR equals its fingerprint (no false negatives), and the false-positive rate on non-members is about 1/256 (window.__xor_filter). FIG no framing; construction by peeling, membership, and the false-positive sweep all run in-browser.
LIT verified live: across many builds, every member’s three-slot XOR equals its fingerprint (no false negatives), and the false-positive rate on non-members is about 1/256 (window.__xor_filter). FIG no framing; construction by peeling, membership, and the false-positive sweep all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-firewall — like the Bloom firewall it never blocks a real member, but it does it in less space by solving for the fingerprints instead of just setting bits. AVAN (AI) built the instrument: the three-block hashing, the peeling construction, the XOR membership test, and a false-positive sweep.
Credit as content: Thomas Mueller Graf & Daniel Lemire (2020). The weave: David names the leaner firewall; I confirm the three-slot XOR reproduces every fingerprint and that strangers slip through only ~1/256 of the time.
Credit as content: Thomas Mueller Graf & Daniel Lemire (2020). The weave: David names the leaner firewall; I confirm the three-slot XOR reproduces every fingerprint and that strangers slip through only ~1/256 of the time.
3 ONE DIMENSION
A key hashes to three table slots; the XOR of those three slots is exactly its fingerprint — the equation the construction solves for every key at once.
4 TWO DIMENSIONS · INTERACTIVE
Build a filter over a set; query members (all pass) and strangers (a rare ~1/256 false positive). Watch the fill of the fingerprint table.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the fingerprint table that answers membership by one XOR.
AVAN’s addition (the inverse-companion): don’t just set bits — solve for them. The inverse of ‘hash and mark’ is ‘peel the hypergraph to a degree-1 order, then assign each slot last so every key’s XOR lands on its fingerprint.’ Magenta is a rare false positive; green is the solved table. Solve, don’t just mark.
LIT Genuine XOR filter (Thomas Mueller Graf & Daniel Lemire, 2020): static membership via fp(x)=⊕ of 3 slots, built by hypergraph peeling, ~1.23 bytes/key. Verified live: every member's three-slot XOR equals its fingerprint — no false negatives (window.__xor_filter.noFalseNegatives) — and the measured FPR on non-members ≈ 1/256 (.fprMatches).
FIG No framing: the peeling construction, the XOR membership test, and a false-positive sweep all run in-browser (retrying the peel with a new seed on the rare failure, as the real algorithm does). The AVAN inverse is honest — solving for the table by peeling to a degree-1 order (rather than just setting bits) is what makes the three-slot XOR reproduce every fingerprint; magenta is a rare false positive, green the solved table. Solve, don't just mark.
FIG No framing: the peeling construction, the XOR membership test, and a false-positive sweep all run in-browser (retrying the peel with a new seed on the rare failure, as the real algorithm does). The AVAN inverse is honest — solving for the table by peeling to a degree-1 order (rather than just setting bits) is what makes the three-slot XOR reproduce every fingerprint; magenta is a rare false positive, green the solved table. Solve, don't just mark.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FIREWALL · David Lee Wise (ROOT0), with AVAN