P3.3.2 — Gossip Bloom Filter Dedup — Verification
Step 5 of the 5-step chain. Test evidence for the Bloom filter dedup module.
§1. Gate results
| Gate | Command | Result |
|---|---|---|
| Build | npm run build |
PASS — tsc clean, postbuild migration copy clean |
| Lint | npm run lint |
PASS — eslint src clean, no errors, no warnings |
| Test | npm test |
PASS — 2987/2987 (65 suites) |
§2. Test count delta
| Metric | Baseline (origin/main 9c7165d5) |
After P3.3.2 (f9e8f782) |
Δ |
|---|---|---|---|
| Test Suites | 64 (1 skipped) | 65 (0 skipped) | +1 suite |
| Tests | 2970 (2969 passed + 1 skipped) | 2987 (2987 passed) | +17 |
The +17 delta matches the 17 it-blocks across 10 describe-groups in bloom-dedup.test.ts.
(The previously-skipped baseline test ran cleanly in this run — appears to be a pre-existing variable-skip test unrelated to bloom-dedup.)
§3. Test inventory
| Group | Count | Coverage |
|---|---|---|
Group 1 — sizeFilter math |
3 | Default config (m=9586, k=7), n=100 (m=959, k=7), n=10000 p=0.001 sanity (positive integers) |
| Group 2 — Constructor allocation | 2 | stats().m === 9586, stats().k === 7; fresh set_bits === 0, occupancy === 0 |
| Group 3 — No false negatives | 1 | Insert 1000 distinct event_ids; assert every one returns true from mightContain |
| Group 4 — Empirical FPR primary seed | 1 | Insert counters 0–999, query counters 1000–10999; FPR < 1.5% |
| Group 5 — Empirical FPR secondary seed | 1 | Insert counters 100000–100999, query 101000–110999; FPR < 1.5% (cross-check) |
Group 6 — reset() clears |
2 | Post-insert set_bits > 0, post-reset set_bits = 0 + all original IDs return false; reset preserves m/k |
| Group 7 — Hash determinism | 2 | Two filters with same insert sequence have identical set_bits; insertion-order invariance (forward vs reverse) |
Group 8 — Math.* confined to sizeFilter |
1 | Static scanner against bloom-dedup.ts source confirms no Math.* outside the sizeFilter body |
| Group 9 — Banned-token scan | 1 | Mirror of messages.test.ts Group 9 — checks Date.*, new Date, setTimeout/setInterval/setImmediate, fetch, XMLHttpRequest, process.hrtime/process.nextTick, async function, await, Math.random, [native code] |
Group 10 — stats().occupancy |
3 | Fresh = 0; after 100 inserts in [0.05, 0.1]; after 1000 inserts < 1.0 |
§4. Coverage
src/domains/consensus/bloom-dedup.ts: 100/100/100/100 (line/branch/func/stmt)
Full coverage on the new module. Verified in the jest –coverage output of npm test.
§5. Empirical FPR data
Out-of-test measurement across 5 disjoint seeds, run via dist/-loaded module:
| Seed offset | False positives / 10000 | Observed FPR | Set bits / 9586 | Occupancy |
|---|---|---|---|---|
| 0 | 83 | 0.0083 | 4928 | 0.5141 |
| 100000 | 101 | 0.0101 | 4993 | 0.5209 |
| 200000 | 91 | 0.0091 | 4926 | 0.5139 |
| 300000 | 96 | 0.0096 | 4987 | 0.5202 |
| 400000 | 108 | 0.0108 | 4979 | 0.5194 |
All five observed FPRs are under the 1.5% acceptance threshold and hover around the 1.0% theoretical bound. Occupancy ~52% matches the textbook optimum for k = 7 hashes at full load (theoretical optimum: 1 - (1 - 1/m)^(k·n) ≈ 0.50 at k = (m/n) ln 2).
The 1.5% threshold sits ~5σ above the theoretical mean (σ ≈ 0.10% for 10000 trials at p=0.01), so the Group 4–5 tests are not flake-prone.
§6. Math.* / banned-token discipline
Static scanner in Group 8 confirms Math.log, Math.ceil, Math.round appear ONLY inside the sizeFilter function body (bloom-dedup.ts lines 84–88). The class body uses:
(this.m + 7) >>> 3for ceiling-divide-by-8 (constructor byte allocation)bit >>> 3for byte index ininsert/mightContainbit & 7+1 << (bit & 7)for bit mask- Brian Kernighan
b &= b - 1popcount instats() set_bits / this.msimple float division foroccupancy(diagnostic return value only; no Math.* invoked)
No Math.random, Date.*, setTimeout/setInterval/setImmediate, fetch, XMLHttpRequest, process.hrtime, process.nextTick, async function, await, or [native code] appear in the source body (post-comment-strip).
§7. Integration verification
P3.3.1’s gossip-wire.ts defines BuildIWANTOptions.seen?: (event_id: Buffer) => boolean as the dedup predicate seam. The bloom-dedup module is consumed at receiver call sites as:
const filter = new BloomFilter({ n: 1000, p: 0.01 });
for (const id of recentlySeenInThisRound) filter.insert(id);
const iwant = buildIWANT(ihave, locally_have, {
seen: (id) => filter.mightContain(id),
sender_id, timestamp_logical,
});
// at end of round:
filter.reset(); // or discard
The slice does NOT modify gossip-wire.ts. The seam was already cut at P3.3.1 in anticipation of this slice (see gossip-wire.ts line 401: “P3.3.2’s Bloom impl swaps a real predicate here”).
§8. Files added (5)
| File | Status |
|---|---|
docs/audits/p3-3-2-bloom-dedup-audit.md |
new (Step 1, c322c5e0) |
docs/contracts/p3-3-2-bloom-dedup-contract.md |
new (Step 2, d7d059ab) |
docs/packets/p3-3-2-bloom-dedup-packet.md |
new (Step 3, d9394629) |
src/domains/consensus/bloom-dedup.ts + tests |
new (Step 4, f9e8f782) |
docs/verification/p3-3-2-bloom-dedup-verification.md |
new (Step 5, this commit) |
No existing source touched. No new npm deps.
§9. Acceptance gate
- s08 sizing formula implemented (
m = ceil(-n·ln(p)/(ln 2)²),k = round((m/n)·ln 2)) - Default config m≈9585 (precise: 9586), k=7
insert(event_id: Buffer): voidmightContain(event_id: Buffer): boolean, FPR ≤ preset()zeroes the bit array- In-memory only — no persistence
- Empirical FPR < 1.5% (observed range 0.83–1.08% across 5 seeds)
- Number-vs-bigint exception documented + isolated to
sizeFilter - K independent SHA-256 truncations seeded by
i npm run build && npm run lint && npm testall pass
Step 5 complete. Slice ready for PR.