THE BIRTHDAY BOUND — a dart

THE BIRTHDAY BOUND collisions come at √N, not N — why 256-bit hashes buy 128-bit safety

In a room of just 23 people, two share a birthday more likely than not — because what matters is the number of pairs, which grows as the square. The same “birthday paradox” governs hash collisions: among a space of N possible outputs, you expect a collision after only about √N random items, not N. That is why a hash needs double the bits you want in security: a 256-bit hash gives only 128-bit collision resistance. The birthday bound is the attacker’s square-root shortcut, and it sets the size of every digest.

THE TECHNIQUE expected first collision at ~√N, not N (pairs grow as n²)

The demo hashes 1,2,3,… into 16 buckets and reports the first collision — it lands at 4 ≈ √16, far below 16: live demo

HISTORY & CREDIT birthday paradox · birthday attack

“A collision needs about N tries for N outputs.” — only √N: pairs grow quadratically, so collisions arrive at the square root. cited

the pairs · k items make k(k−1)/2 pairs — collision likely once pairs ≈ N.
the bound · expected first collision at ≈ √N — the square-root attack.
the consequence · digests need 2× the bits: 256-bit hash → 128-bit collision resistance.

Collisions arriving at the square root of the space — the paradox that halves every hash’s effective strength. theorem

RECOMMEND FOR I-13 the square-root collision, on the compiler

On the canonical compiler, hashing 1,2,3,… into 16 buckets, the first collision occurs at the 4th item — right at √16:

$ i13 run zd_birthday.i13 # 16 buckets, hash 1,2,3,... RUN OK · 161 step(s) · peak stack 16 · call depth 5 first_collision_at = 4 -- ~sqrt(16), not 16

Recommend as a NULL — a theorem, plainly. The birthday bound is a counting fact about collisions (pairs grow as n², so collisions appear at ~√N); every correct hasher obeys it. That is the B39 gate exactly: a theorem coextensive with the setup, not a mechanism a keeper enacts. i13 grounds the phenomenon (collision at 4 ≈ √16). NULL — the fact that sizes every digest, but a fact, not an axis.