The Difference Peels Out of the Table
A Bloom filter is a one-way kind of memory. It can answer:
is this key possibly present?
It cannot answer:
which keys are in you?
That second question sounds too much like asking a shadow to produce the object that cast it. Most of the time, that is exactly right. A saturated Bloom filter does not contain a recoverable list.
An invertible Bloom lookup table changes the bargain. It stores a small algebraic receipt per cell: a count, an XOR of keys, and a checksum XOR. If a cell is holding exactly one remaining key, the table can recognize that fact, recover the key, delete it from its other cells, and possibly reveal more single keys.
That makes the structure feel less like a membership filter and more like a peelable puzzle.
The useful systems move is subtraction. If Alice and Bob hold two huge, mostly equal sets, they can build compatible IBLTs, subtract the tables cell by cell, and try to list only the symmetric difference. Shared keys cancel. The residue is the part they need to exchange.
The Problem Is Not Membership
Suppose two replicas each hold file-block IDs, calendar event IDs, routing updates, or content-addressed chunks:
Alice: many keys
Bob: many keys
The expensive but simple reconciliation protocol is:
exchange sorted lists, diff them
That spends bandwidth proportional to the total set sizes. A log can do better when both sides share prior context, but logs have their own operational price: they have to be maintained, retained, compacted, and interpreted correctly.
Eppstein, Goodrich, Uyeda, and Varghese framed the no-prior-context version cleanly in their Difference Digest paper: compute the set difference in a single round with communication proportional to the size of the difference, not the size of the original sets.1
That is the shape of the problem:
large sets, small difference, no shared update log
An ordinary Bloom filter is the wrong tool for this particular job. It can help one side guess which of its keys the other might have, but it still communicates information shaped by the full set and it has false positives. Set reconciliation needs a way for common keys to disappear.
The Cell Receipt
In the key-only IBLT used by the lab, each cell stores:
count = signed number of mapped keys
keyXor = XOR of mapped keys
hashXor = XOR of checksum(key) for mapped keys
Each key maps to k cells. Insert updates every mapped cell:
count += 1
keyXor ^= key
hashXor ^= checksum(key)
Deletion uses the same XOR updates and subtracts from the count:
count -= 1
keyXor ^= key
hashXor ^= checksum(key)
Goodrich and Mitzenmacher’s IBLT paper describes the general key-value version with a count field, a key-sum field, and a value-sum field; it also notes that XOR can replace sums in many settings to avoid overflow issues.2
For reconciliation, Alice builds a table for her set. Bob builds a table with the same size, hash functions, and checksum function. Then one side subtracts:
diff.count = alice.count - bob.count
diff.keyXor = alice.keyXor ^ bob.keyXor
diff.hashXor = alice.hashXor ^ bob.hashXor
A shared key appears once in Alice’s table and once in Bob’s table. It maps to the same cells. In the subtraction, its count contribution becomes zero and its XOR contribution cancels.
Only disagreement remains.
The Peel
A cell is pure when it looks like exactly one remaining key:
abs(count) == 1
hashXor == checksum(keyXor)
If count == 1, the key belongs to Alice but not Bob. If count == -1, it
belongs to Bob but not Alice. After recording that key, the decoder removes it
from every cell it hashes to.
That deletion can expose new pure cells:
find pure cell
recover key and side
delete that key from its k cells
repeat
This is not merely a convenient implementation. Goodrich and Mitzenmacher point out that IBLT listing is the same peeling process used to find the 2-core of a random hypergraph: cells are vertices, keys are hyperedges, and decoding stops when every remaining vertex has degree at least two.3
That gives the most important failure mode a concrete shape:
no pure cells left, but nonempty cells remain
The table is not lying. It is stuck.
The Lab
The lab below builds two full synthetic sets, inserts both into compatible IBLTs, subtracts the tables, and runs the pure-cell peeling decoder. It also runs a small deterministic capacity sweep so the failure cliff is visible.
The byte accounting is intentionally simple: each cell is treated as three
32-bit words, count, keyXor, and hashXor. Real systems choose wider
checksums, salts, encodings, and failure budgets.
The default run has 2,500 shared keys and 84 differing keys. The two full
lists would cost about 20.3 KB under the lab’s 32-bit key model; the IBLT
message costs about 2.2 KB and decodes the exact difference.
The exported audit checks five deterministic scenarios and reports 25 named checks. It verifies that:
- a shared set cancels to an empty subtracted table;
- decoded Alice-only and Bob-only keys match the exact generated difference;
- every peeled cell has a valid side,
+1or-1; - successful decodes leave no residual cells; and
- the subtracted table’s nonempty cells are bounded by the number of difference keys times the hash count.
The compact reproduction check is:
node - <<'NODE'
const lab = require("./assets/js/iblt-reconciliation-lab.js");
const EXPECTED_CASES = 5;
const EXPECTED_CHECKS = 25;
const EXPECTED_CHECK_NAMES = [
"decoded-difference-exact",
"peeled-cell-sign-valid",
"shared-set-cancels-empty",
"subtracted-cells-bounded",
"successful-decode-empty-residual"
];
const EXPECTED_CASE_SHAPE = [
"alice:5:24:62:3:2.55:19:24:0:744:3296",
"balanced:5:140:308:5:2.2:73:140:0:3696:26160",
"bob:5:48:84:4:1.75:16:48:0:1008:7392",
"default-balanced:5:84:185:3:2.2:59:84:0:2220:20336",
"split:5:90:171:3:1.9:61:90:0:2052:9960"
];
const EXPECTED_CASE_ROWS = [
"alice:diff=24:cells=62:hashes=3:factor=2.55:pure=19:peeled=24:residual=0:bytes=744/3296:ratio=4.43:checks=5/5:passed=true",
"balanced:diff=140:cells=308:hashes=5:factor=2.2:pure=73:peeled=140:residual=0:bytes=3696/26160:ratio=7.08:checks=5/5:passed=true",
"bob:diff=48:cells=84:hashes=4:factor=1.75:pure=16:peeled=48:residual=0:bytes=1008/7392:ratio=7.33:checks=5/5:passed=true",
"default-balanced:diff=84:cells=185:hashes=3:factor=2.2:pure=59:peeled=84:residual=0:bytes=2220/20336:ratio=9.16:checks=5/5:passed=true",
"split:diff=90:cells=171:hashes=3:factor=1.9:pure=61:peeled=90:residual=0:bytes=2052/9960:ratio=4.85:checks=5/5:passed=true"
];
const EXPECTED_CHECK_ROWS = [
"alice:decoded-difference-exact=true|peeled-cell-sign-valid=true|shared-set-cancels-empty=true|subtracted-cells-bounded=true|successful-decode-empty-residual=true",
"balanced:decoded-difference-exact=true|peeled-cell-sign-valid=true|shared-set-cancels-empty=true|subtracted-cells-bounded=true|successful-decode-empty-residual=true",
"bob:decoded-difference-exact=true|peeled-cell-sign-valid=true|shared-set-cancels-empty=true|subtracted-cells-bounded=true|successful-decode-empty-residual=true",
"default-balanced:decoded-difference-exact=true|peeled-cell-sign-valid=true|shared-set-cancels-empty=true|subtracted-cells-bounded=true|successful-decode-empty-residual=true",
"split:decoded-difference-exact=true|peeled-cell-sign-valid=true|shared-set-cancels-empty=true|subtracted-cells-bounded=true|successful-decode-empty-residual=true"
];
const EXPECTED_RESIDUAL_SHAPE = [
"alice:0",
"balanced:0",
"bob:0",
"default-balanced:0",
"split:0"
];
const EXPECTED_TOTALS = {
rows: EXPECTED_CASES,
passed: EXPECTED_CASES,
total: EXPECTED_CASES,
passedChecks: EXPECTED_CHECKS,
totalChecks: EXPECTED_CHECKS
};
function sameJson(actual, expected) {
return JSON.stringify(actual) === JSON.stringify(expected);
}
function rowDrifts(actual, expected) {
const count = Math.max(actual.length, expected.length);
const drift = [];
for (let index = 0; index < count; index += 1) {
if (actual[index] !== expected[index]) {
drift.push({ index, actual: actual[index], expected: expected[index] });
}
}
return drift;
}
const audit = lab.auditIBLTLab();
const auditShape = {
totals: {
rows: audit.cases.length,
passed: audit.passed,
total: audit.total,
passedChecks: audit.passedChecks,
totalChecks: audit.totalChecks
},
caseChecks: audit.cases.map((row) => [
row.scenario,
row.totalChecks,
row.diffSize,
row.cells,
row.hashes,
row.factor,
row.initialPure,
row.peeled,
row.residual,
row.bytesIblt,
row.bytesLists
].join(":")).sort(),
caseRows: audit.cases.map((row) =>
`${row.scenario}:diff=${row.diffSize}:cells=${row.cells}:` +
`hashes=${row.hashes}:factor=${row.factor}:pure=${row.initialPure}:` +
`peeled=${row.peeled}:residual=${row.residual}:` +
`bytes=${row.bytesIblt}/${row.bytesLists}:` +
`ratio=${row.compressionRatio.toFixed(2)}:` +
`checks=${row.passedChecks}/${row.totalChecks}:passed=${row.passed}`
).sort(),
checkRows: audit.cases.map((row) =>
`${row.scenario}:` +
row.checks.map((check) => `${check.name}=${check.ok}`).sort().join("|")
).sort(),
checkNames: Array.from(new Set(audit.cases.flatMap(
(row) => row.checks.map((check) => check.name)
))).sort(),
residualByScenario: Object.entries(audit.byScenario)
.map(([scenario, row]) => `${scenario}:${row.residual}`)
.sort()
};
const caseRowDrifts = rowDrifts(auditShape.caseRows, EXPECTED_CASE_ROWS);
const checkRowDrifts = rowDrifts(auditShape.checkRows, EXPECTED_CHECK_ROWS);
const shapeErrors = [
sameJson(auditShape.totals, EXPECTED_TOTALS) ? null : "totals",
sameJson(auditShape.caseChecks, EXPECTED_CASE_SHAPE) ? null : "caseChecks",
caseRowDrifts.length ? "caseRows" : null,
checkRowDrifts.length ? "checkRows" : null,
sameJson(auditShape.checkNames, EXPECTED_CHECK_NAMES) ? null : "checkNames",
sameJson(auditShape.residualByScenario, EXPECTED_RESIDUAL_SHAPE)
? null
: "residualByScenario"
].filter(Boolean);
if (shapeErrors.length) {
throw new Error(
`audit shape drifted in ${shapeErrors.join(", ")}:\n` +
JSON.stringify({
auditShape,
drifts: {
caseRows: caseRowDrifts,
checkRows: checkRowDrifts
}
}, null, 2)
);
}
const summary =
`${audit.passed}/${audit.total} scenarios and ` +
`${audit.passedChecks}/${audit.totalChecks} checks passed`;
const failedCases = audit.cases.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (failedCases.length || !audit.ok ||
audit.passed !== audit.total ||
audit.passedChecks !== audit.totalChecks) {
throw new Error(JSON.stringify({
summary,
errors: audit.errors,
failedCases,
shapeErrors,
auditShape
}, null, 2));
}
console.table(audit.cases.map((row) => ({
scenario: row.scenario,
diff: row.diffSize,
cells: row.cells,
hashes: row.hashes,
factor: row.factor,
initialPure: row.initialPure,
peeled: row.peeled,
residual: row.residual,
messageKB: (row.bytesIblt / 1024).toFixed(1),
listKB: (row.bytesLists / 1024).toFixed(1),
checks: `${row.passedChecks}/${row.totalChecks}`,
passed: row.passed
})));
console.log(summary);
NODE
Sizing Is the Algorithm
The lab’s Cells per diff slider is the important one.
Push it down toward 1.05x. Many runs stop with residual cells. The decoder is
not confused; it has reached a 2-core. Every remaining key is entangled with
other remaining keys, so no cell can testify alone.
Push it up. Pure cells appear, the peeling cascade starts, and the table lists the whole difference.
Goodrich and Mitzenmacher give 2-core threshold constants for several hash
counts; for example, the table in their paper lists about 1.222 for k = 3,
1.295 for k = 4, and 1.425 for k = 5.3 Those are asymptotic
thresholds under random-hypergraph assumptions, not a promise that a tiny
browser demo with a 32-bit checksum should run exactly at the constant. In
production, the sizing question belongs to a failure budget.
This is also why the number of hash locations is not monotone magic. Difference Digest notes the tradeoff directly: too few hashes do not propagate enough peeling information, while too many hashes can make it hard to find a pure cell at the start; values like 3 or 4 work well in practice.4
What This Toy Leaves Out
The lab assumes the difference size is known well enough to size the table. Difference Digest adds a Strata Estimator for that missing first step, because an IBLT that is too small may fail and an IBLT that is too large wastes bandwidth.1
The lab also uses a short checksum. Real deployments choose checksum widths so that a false pure cell is negligible relative to the system’s risk budget. They also have to version the hash functions, salt them, serialize cell fields unambiguously, and decide what to do about duplicate keys, value changes, and malicious peers.
The conceptual invariant is still compact:
common keys cancel
single remaining keys reveal themselves
revealed keys delete themselves
An IBLT is not a smaller list. It is a table that can sometimes turn a set difference back into a list by finding enough places where only one key is left standing.
-
David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese, “What’s the Difference? Efficient Set Reconciliation without Prior Context”, SIGCOMM 2011. The paper describes a Difference Digest for one-round set reconciliation with communication proportional to the set difference, adapts whole-IBF subtraction for reconciliation, and adds a Strata Estimator for difference-size estimation. Google Research also hosts the publication summary. ↩ ↩2
-
Michael T. Goodrich and Michael Mitzenmacher, “Invertible Bloom Lookup Tables”, Allerton 2011 / arXiv version. The paper defines an IBLT as a Bloom-filter-like table for key-value pairs supporting insert, delete, lookup, and listing; the PDF describes the count, keySum, and valueSum fields and notes XOR variants for many settings. ↩
-
Goodrich and Mitzenmacher, “Invertible Bloom Lookup Tables”, Section 2.4. Their listing algorithm repeatedly removes cells of count 1, connects the process to the 2-core of a random hypergraph, and gives threshold constants for several hash counts. ↩ ↩2
-
Eppstein et al., “What’s the Difference?”, Section 3. The paper discusses
hash_count, checksum fields for purity checks, negative counts after subtraction, and reports that hash counts 3 or 4 work well in practice. ↩