03.3 · Entropy Source

Parent: Document 03 (D2 Experiment Plan), Step 0.3 — “specify the entropy source precisely; write down why it is sufficient.” Status: ✅ Banked. Completes Step 0. The D2 harness implements the draw exactly as §3; deviations require a Doc 04 log entry. Origin note: requirement R3 below exists because a design review question (“how can the same key ever win if its draw never changes?”) exposed the static-pairing bug in the original sketch of Option A. §2.1 tells the full story self-contained; this document is the permanent fix.

---

1. What this document specifies

Schedules M1/M3 (Doc 03.2) end with: “test whether the low k bits of the draw are all zero.” This document defines the draw: where its bits come from, how they are mixed, and the argument that the result behaves like k fair coins on every attempt.

2. Requirements on the draw

#	Requirement	Source	If violated
R1	Fair coins: each tested bit ~ uniform, independent ⇒ P(k zeros) = 2⁻ᵏ exactly	03.2’s entire probability table assumes it	every mask probability becomes fiction
R2	Already-paid material only: no RNG call, no additional memory reads	C2; the raison d’être of Option A vs C	Option A loses its cost advantage
R3	Fresh draw every attempt: identical (challenger, victim-state) pairs must not replay identical draws	static-pairing bug (review finding)	a challenger can deterministically bounce forever — the lockout bug resurrected
R4	Reproducible: bit-for-bit replayable given the run’s seed	Doc 03 §5.2	results cannot be debugged or audited

2.1 The static-pairing bug (why R3 exists — read this first if you’re new here)

The original draft of Option A built the draw from only two ingredients: spare ⊕ victimWord — the challenger’s leftover hash bits mixed with the victim’s current slot. It looked random. It compiled. It would have passed a casual demo. It was broken, and here is the exact failure:

Both ingredients can be simultaneously frozen. A given key always hashes to the same value, so its spare bits are identical on every visit — that’s not a flaw, it’s what hashes are. And a victim that is receiving no traffic has a slot word that never changes — same tag, same timestamp, same count, bit for bit. XOR two constants and you get a third constant. So:

Challenger X arrives. Bucket full, no match. Victim: an idle slot, eff 5, k = 0…wait, eff 5 gives k = 0 under M3 — make it a quiet bucket where the weakest is eff 40, k = 4, chip odds nominally 1/16. X’s draw is computed: low 4 bits = 0110. Not all zero. BOUNCE. X arrives again. Same spare (same key). Same victimWord (idle victim). Same XOR. Same 0110. BOUNCE. X arrives 10,000 more times. Ten thousand identical draws. Ten thousand bounces.

The “1/16 probability” was a lie: probability requires fresh draws, and we had silently built a lottery that hands the same person the same ticket number forever while the winning number never changes. One frozen verdict, replayed eternally. A genuinely hot new key could be deterministically locked out of a quiet bucket for an unbounded time — which is the v1 strict-comparison lockout bug (Spec §4.1) resurrected through the entropy source, the exact disease Option A exists to cure.

Why it’s an especially nasty bug class: it is workload-masked. In a busy bucket the victim’s word churns (its own traffic, other challengers’ chips), so draws vary and everything looks statistically healthy — demos pass, light testing passes. It bites only where buckets are quiet and victims idle: intermittent, environment-dependent, invisible in averages. Option C never had this problem — rng.Float64() is fresh per call by definition; our free-entropy substitution silently discarded that guarantee, and nothing in the type system or the tests of the day would have said so.

How it was found: not by testing — by a design-review question: “if the same key keeps retrying against an unchanged victim, what makes its draw different the second time?” The honest answer was “nothing,” and R3 was born. (Provenance matters: a requirement whose origin story is recorded is a requirement future maintainers won’t delete as redundant.)

The fix is Ingredient 3 in §3: a per-attempt salt whose freshness is arithmetic — attempt n and attempt n+1 differ because n ≠ n+1, not because we hope some state churned. The lesson, generalized for the project’s toolbox: when substituting constructed entropy for real randomness, every guarantee the RNG gave you implicitly must be re-provided explicitly — and “fresh per call” is the easiest one to lose without noticing.

🧭 In plain terms: the old design was a raffle where your ticket number was printed from your name and the prize barrel’s label — so the same person walking up to the same barrel got the same ticket, every single time, forever. “Try again!” meant nothing; the outcome was decided before the first try. The fix adds the attempt number to the ticket printing: now every try is genuinely a new ticket, because 4,081 is never 4,082.

3. The draw, normatively

// One eviction attempt's lottery draw. All inputs are register-resident
// leftovers; the only new state is the attempt salt.
salt++                                        // per-attempt, monotone (R3)
draw := finalize(spare ^ victimWord ^ salt*0x9E3779B97F4A7C15)
win  := k == 0 || (draw & ((1<<k)-1)) == 0    // low-k-bits-zero test

Ingredient 1 — spare (the challenger’s contribution). The unused top 32 bits of the challenger’s 64-bit hash. Budget per Doc 03.2 §8: 16 bits spent on bucket index, 16 on fingerprint tag ⇒ 32 bits spare. Varies per key; frozen for a given key (hence insufficient alone).

Ingredient 2 — victimWord (the defender’s contribution). The victim’s full packed 64-bit slot (tag|ts|count), already in a register from the min-effective nomination scan — cost zero. Varies with victim state; frozen while the victim is idle (hence insufficient even combined with Ingredient 1 — this pairing was the bug).

Ingredient 3 — salt × ODD (time’s contribution; the R3 fix). salt increments on every eviction attempt structure-wide; multiplying by the large odd constant (2⁶⁴/φ, a Weyl-sequence generator) smears the +1 step across all 64 bits instead of wiggling only the low ones. Cannot freeze by construction: attempt n and attempt n+1 differ arithmetically, independent of key or victim behavior. Cost: one add, one multiply, miss-path only.

Concurrency note (named open item, out of D2 scope): in the single-threaded harness, salt is a plain variable. The concurrent implementation must choose between a relaxed atomic counter (simplest; miss-path-only contention) and per-thread salts (zero contention; per-thread state). Decision deferred to the implementation spec; either satisfies R3.

4. finalize — why the low bits need laundering

The problem: our win-test reads the draw’s lowest k bits — exactly where the ingredients are most patterned (the victim’s small, structured count occupies its word’s low bits; XOR combines patterns but does not destroy them). Patterned low bits = bent coins = silent R1 violation.

The device: a bit-mixing finalizer — the standard splitmix64 finalizer (xorshift-multiply ×3, ~4 ns):

func finalize(x uint64) uint64 {
    x ^= x >> 30; x *= 0xBF58476D1CE4E5B9
    x ^= x >> 27; x *= 0x94D049BB133111EB
    x ^= x >> 31
    return x
}

Its defining property is avalanche: flipping any single input bit flips each output bit with ≈50% probability. After finalize, the low k bits are fair coins regardless of input structure. This is the same mathematical device that makes quality hashes quality, applied once more to launder our mixture.

🧭 In plain terms: we’re building lottery numbers out of leftovers — the challenger’s ID digits, the victim’s current ledger line, and a ticker that counts attempts. Leftovers carry habits: ledger lines end in small numbers, tickers count in order. finalize is the tumbling cage that shakes the balls until no habit survives — and we always read the balls after the cage, never before.

5. Sufficiency argument (R-by-R)

• R1 (fair): finalizer avalanche renders low bits uniform and inter-bit-independent to the standard achievable by non-cryptographic mixing; verified empirically, not assumed — the harness includes bit-uniformity tests (per-bit bias, pairwise correlation, k-zeros frequency vs 2⁻ᵏ) over real draw streams from real workloads. A failed uniformity test fails the run.
• R2 (paid-for): ingredients 1–2 are register-resident leftovers; ingredient 3 is one add + one multiply; finalize is ~6 ALU ops. No RNG, no memory traffic.
• R3 (fresh): the salt is strictly monotone per attempt — freshness by arithmetic, not by hoping state churns. The static-pairing bug is closed by construction.
• R4 (reproducible): hash (seeded), victim state (deterministic from the stream), and salt (deterministic sequence) ⇒ every draw replays exactly from (workload, params, seed).

Honest limits (not claimed): an adversary who knows the unkeyed hash function may choose keys to bias spare’s distribution. We claim testability, not immunity: the entropy-attack workload (Doc 03 §3.4) attacks exactly this, and the keyed-hash requirement (Spec §4.3) is the designated defense for adversarial deployments. If the entropy attack defeats Option A even under a keyed hash, gate clause 4.2 sends Option C to ship.

6. Interface to the rest of the experiment

OptionA_Evict(bucket, challengerTag, spare, now):
    victim, eff  = nominate + fold                  // identical to Option C §4 steps 1–2
    k            = schedule(eff)                     // M3 primary, M1 fallback (Doc 03.2)
    win          = draw-test per §3 of this document
    outcomes     = TAKEOVER / CHIP / BOUNCE          // identical semantics to Option C

Option A and Option C now differ in exactly one line — the win-decision — which is the isolation the experiment’s validity depends on. Step 0 is complete: both contestants are frozen on paper.

---

Appendix — check exercises (with answers)

1. Why is spare ⊕ victimWord alone not enough, even though both are “random-looking”? Because both can be simultaneously frozen: a given key’s spare bits never change, and an idle victim’s word never changes ⇒ the identical draw replays on every attempt ⇒ a challenger can bounce deterministically forever (the static-pairing bug). Randomness must be guaranteed per attempt, and only the salt provides that unconditionally.
2. Why must finalize come after the XORs rather than finalizing each ingredient separately? Finalizing then XORing re-introduces linear structure at the final step (XOR of two well-mixed values is well-mixed, but XOR with a patterned third input re-imprints its pattern). Mixing last guarantees the tested bits are downstream of every input’s entropy with avalanche applied to the combination.
3. The win-test reads low bits. Would reading the top k bits instead remove the need for finalize? No. The top bits of the raw mixture inherit structure too (e.g., the salt multiply’s high bits are the best-mixed part of that ingredient, but victimWord’s tag occupies high bits with its own pattern). Bit position doesn’t grant fairness; avalanche does. Also, standardizing on low-bits + finalize keeps the test a single AND against a mask.