Collisions and the birthday problem

01 / Reconstruct the incident

Two records share a key. That does not yet tell us why.

During an upload rollout, support reports that an attachment opened from one account belongs to another. The database shows two upload requests using the same 64-bit public ID. The ID service generated five billion IDs over its lifetime, but the report does not establish that the generator emitted the duplicate. A tenant-scoping omission, string truncation, a stale cache entry, or an application retry that reused a request ID could produce the same visible symptom.

First preserve the affected rows and request traces. Check which exact bytes were generated, which database constraint accepted them, how the lookup was scoped, and whether the duplicate appears in the generator's raw output or only after serialization and storage. We will use five billion uniformly generated 64-bit values as a scale example, not as a claim about this service's actual event history.

Case file / Upload identifiers A duplicate key became a cross-account data exposure.

Observed: Two uploads resolve through the same public ID.
Namespace: 64 generated bits, or 2⁶⁴ possible values.
Scale example: 5,000,000,000 IDs over the service's lifetime.
Impact: A lookup may return the wrong customer's attachment.

In practice · An upload incident review Collision probability

“We saw one duplicate. Is the random generator the cause?”

— An engineer coordinating the incident investigation

A technically grounded answerThe duplicate is evidence of a key reuse somewhere in the path, not proof that two independent random draws matched. Check the raw generated values, database uniqueness constraints, tenant scope, request retries, encoding and truncation, and cache behavior. Then compare the observed count and time window with the generator's modeled collision probability.

Where the term helpsUse the birthday calculation to ask whether random duplication is credible at this volume. Trace the actual value from generation through persistence and lookup to locate the cause; contain the access issue while preserving evidence.

02 / Count the pairs

A new value can collide with every value already generated.

Suppose an identifier is selected uniformly from a namespace with N possible values, independently on each draw. The first draw cannot collide. The second has one prior value to match, the third has two, and draw n has n - 1 earlier values. Across n generated IDs, there are n(n - 1) / 2 possible pairs that might match.

For a 64-bit namespace, N = 2⁶⁴ ≈ 1.8447 × 10¹⁹. Five billion generated values create about 5×10⁹ × (5×10⁹ - 1) / 2 ≈ 1.25 × 10¹⁹ pairs. Each particular pair matches with probability 1/N. The pair count is already on the order of the namespace size, so “64 bits is huge” is not enough context: there are a lot of chances to match.

01 / Possible valuesN = 2⁶⁴

A 64-bit uniformly chosen namespace.

02 / Generated IDsn = 5 × 10⁹

Lifetime total in this illustrative scenario.

03 / Candidate pairsn(n − 1) / 2 ≈ 1.25 × 10¹⁹

Each pair has a 1/N chance to match.

This is the birthday problem: collisions become likely much earlier than the point where the namespace is full. For about a 50% chance of at least one collision, the count is roughly √(2N ln 2), or approximately 1.177√N. In a 64-bit space that is about 5.06 billion draws, far below 2⁶⁴. This is an approximate threshold, not a safe capacity guarantee.

03 / Estimate collision risk

The birthday approximation turns pair counts into a chance.

Let λ = n(n - 1) / (2N) be the expected number of matching pairs. When collisions are individually rare and the namespace is large relative to the sample, the probability of at least one collision is well approximated by P ≈ 1 - e^-λ. For five billion independent 64-bit draws, λ ≈ 0.6776, so P ≈ 1 - e^-0.6776 ≈ 0.492, or about 49.2%.

This probability is for at least one matching pair in all five billion draws. It is not the chance that each ID is duplicated, nor does it predict which pair will match or when. The expected number of matching pairs (0.6776) and the probability of one or more (49.2%) are related but different quantities.

In practice · A capacity review for a generated-ID service Birthday bound

“Could we keep the 64-bit format if our next release generates another billion IDs?”

— A developer estimating the next identifier cohort

A technically grounded answerIf these are another billion independent uniform draws in the same namespace and existing IDs remain in use, calculate with the cumulative total of six billion, not only the new cohort. The approximation gives λ ≈ 0.976 and about 62.3% chance of at least one collision across that cumulative set. That does not mean a collision is certain in this release or that every ID has a 62.3% risk; confirm retention, uniqueness scope, and generation behavior before making a design decision.

Where the term helpsUse the cumulative number of simultaneously relevant or lifetime-generated IDs that share a uniqueness namespace. State whether expired identifiers can be reused and whether uniqueness is global, regional, or tenant-scoped.

04 / Test the explanation

Use observations to separate random collisions from key reuse.

The birthday model estimates a baseline for independent draws. Production incidents also include bugs that can make repeated values far more likely. An ID may be generated once and reused on retry; a 128-bit value may be truncated to 32 bits by a database column; a lookup may drop the tenant predicate; or a cache may return an entry under a normalized key that collides with another input. Increasing randomness would not repair these failures.

Preserve the observation. Capture raw request IDs, stored values, row keys, timestamps, and the lookup path before cleanup or retry obscures them.
Check the uniqueness boundary. Confirm which columns and scope are unique: global, per tenant, per region, or only within a table.
Trace transformations. Compare bytes before and after encoding, case folding, truncation, parsing, serialization, and database storage.
Inspect generator state. Look for process restarts with repeated seeds, clock-based values, counter resets, duplicated worker state, and retries that reuse a value.
Recalculate the real scale. Count IDs in the actual namespace and retention window; include old IDs that still block reuse and exclude values that truly occupy another namespace.
Contain the impact. Repair access checks and uniqueness constraints, then decide whether the generator design also needs more bits or a collision-resolution strategy.

Diagnostic discipline

A duplicate is a fact to explain, not a diagnosis.

For the incident, test at least two hypotheses: the raw generator emitted the same value, or a distinct value became the same lookup key later. Identify the log field, stored bytes, or constraint behavior that would distinguish them. If you cannot observe the value at the generation boundary, mark that uncertainty instead of treating the probability estimate as proof.

05 / Change the assumptions

See how namespace width and sample count move the risk.

Enter the number of bits and the cumulative number of IDs in one shared namespace. The calculator uses 1 - exp(-n(n - 1)/(2N)), with N = 2^b. It models independent uniform samples and reports an approximation; it does not measure a generator or account for retries, partitions, or biased output.

Namespace bits IDs in this namespace

Modeled chance of at least one collision 49.22%

N = 2⁶⁴; expected matching pairs λ ≈ 0.6776.

Approx. 50% threshold5,056,937,541 IDs

Sample count vs. namespace5000000000 / 2⁶⁴

Assumption: independent uniform draws, same namespace, no value reuse. Approximation: birthday/Poisson bound.

At the default 64 bits and five billion IDs, the estimate is about 49.2%, and the approximate 50% point is 5.06 billion IDs. Change the width to 128 bits: at the same volume, the estimate becomes about 3.67 × 10⁻²⁰ as a probability, effectively negligible for this illustrative count. If changing the input changes the estimate sharply, check that you have not also changed the actual uniqueness scope or count.

06 / Practice in code

Keep the assumptions visible in the function name and comments.

The TypeScript and Go examples compute the expected pair count and apply the same Poisson approximation as the lab. Both handle fewer than two samples as zero collision chance and reject unsupported input ranges. expm1 keeps small probabilities from losing precision when subtracting a value very close to 1 from 1.

The examples are planning helpers, not collision detectors. If your real generator has nonuniform output, repeated process state, or a different uniqueness boundary, measure and inspect that system rather than passing a nominal bit count to this model.

Compare the same probability model in TypeScript and Go.

Both examples estimate at least one collision among independent uniform IDs.

Read in

Compare with

Compare languages

TypeScriptBirthday approximation for generated IDs

collisions.ts

/**
 * Estimate the chance of at least one collision among uniformly and
 * independently sampled IDs from a 2^bits-sized namespace.
 *
 * Uses the birthday/Poisson approximation: 1 - exp(-n(n-1)/(2N)).
 * This is an estimate, not a security proof or a model of a biased generator.
 */
export function estimateCollisionProbability(samples: number, bits: number): number {
	if (!Number.isSafeInteger(samples) || samples < 0) {
		throw new RangeError('samples must be a non-negative safe integer');
	}
	if (!Number.isSafeInteger(bits) || bits < 1 || bits > 1023) {
		throw new RangeError('bits must be an integer from 1 through 1023');
	}
	if (samples < 2) return 0;

	const namespaceSize = 2 ** bits;
	if (samples >= namespaceSize) return 1;

	const expectedPairs = (samples * (samples - 1)) / 2 / namespaceSize;
	return -Math.expm1(-expectedPairs);
}

const estimated = estimateCollisionProbability(5_000_000_000, 64);
console.log(`64-bit namespace, 5 billion IDs: ${(estimated * 100).toFixed(1)}%`);
// Output: 64-bit namespace, 5 billion IDs: 49.2%

GoBirthday approximation for generated IDs

collisions.go

package main

import (
	"errors"
	"fmt"
	"math"
)

// estimateCollisionProbability estimates the chance of at least one collision
// among uniformly and independently sampled IDs from a namespace of size 2^bits.
// It uses the birthday/Poisson approximation: 1 - exp(-n(n-1)/(2N)).
func estimateCollisionProbability(samples uint64, bits uint) (float64, error) {
	if bits == 0 || bits > 1023 {
		return 0, errors.New("bits must be from 1 through 1023")
	}
	if samples < 2 {
		return 0, nil
	}
	namespaceSize := math.Exp2(float64(bits))
	if float64(samples) >= namespaceSize {
		return 1, nil
	}
	n := float64(samples)
	expectedPairs := (n * (n - 1) / 2) / namespaceSize
	return -math.Expm1(-expectedPairs), nil
}

func main() {
	p, err := estimateCollisionProbability(5_000_000_000, 64)
	if err != nil {
		panic(err)
	}
	fmt.Printf("64-bit namespace, 5 billion IDs: %.1f%%\n", p*100)
}

07 / Choose the right response

Collision probability answers a different question from hash security.

For random IDs, birthday analysis helps size a namespace and plan a uniqueness check or collision-resolution path. For cryptographic hashes, a generic birthday argument says that finding some collision in an ideal b-bit hash takes on the order of 2^b/2 work. That is not the same as finding a preimage for a chosen value, and it does not establish that a particular hash function is secure. Real designs must follow current cryptographic guidance and account for known attacks, output truncation, and the protocol's purpose.

In practice · A design review for a content-addressed cache Accidental ID collisions and adversarial hash collisions

“If the birthday bound says collisions happen around 2 to the half-width, can we use a short hash as our cache key?”

— A reviewer assessing a cache-key proposal

A technically grounded answerThe birthday scale is a warning, not a complete design rule. For random identifiers it estimates the chance of accidental duplicates in a chosen population. For an adversarial hash setting, the attacker can choose inputs and the hash's actual collision resistance matters; a collision can also have a different consequence from a preimage. Use a vetted hash and output length appropriate to the threat model, and preserve an authoritative check against the underlying content or record.

Where the term helpsUse the birthday model for accidental duplicates in a stated population. Treat cryptographic collision resistance as a security property of a specific primitive and protocol, not a label inferred from this calculator.

Transfer exercise

A regional service reports duplicates after adding a second generator.

The IDs are 96 bits, and each region claims its own 2-billion-ID cohort. The database uniqueness constraint is global. Determine what count belongs in the birthday model if both regions draw independently from the same full namespace. Then list evidence that could distinguish a genuine random collision from duplicated generator state or a lookup bug. State which assumption you would verify first and why.