Definition

The birthday problem (also called the birthday paradox) is a probability result showing that in a group of randomly chosen values from a large space, the probability of two values being equal grows surprisingly quickly — proportional to the square of the number of values, not linearly. It is named after the observation that in a group of just 23 people, there is a 50% chance that two share a birthday (out of 365 possible birthdays).

In the context of UUIDs, the birthday problem determines the number of UUIDs that must be generated before a collision (two identical UUIDs) becomes statistically likely.

The birthday formula

The probability that at least one collision exists among n generated UUIDs from a space of size N is approximately:

P(collision) ≈ 1 − e^(−n² / 2N)

For 50% collision probability: n ≈ √(2N × ln(2))

Applied to UUID v4 (N = 2¹²²):

n₅₀% ≈ √(2 × 2¹²² × 0.693)
     ≈ √(2¹²³ × 0.693)
     ≈ 2.6 × 10¹⁸ UUIDs

At 1 billion UUIDs generated per second continuously: 2.6 × 10¹⁸ / 10⁹ = 2.6 × 10⁹ seconds ≈ 86 years.

This is why UUID v4 collision is treated as impossible in practice. The Wikipedia birthday problem article provides the full derivation.

UUID v4 collision probability table

UUIDs generatedCollision probability
1,000~3 × 10⁻²⁹ (essentially zero)
1,000,000~3 × 10⁻²³
1,000,000,000~3 × 10⁻¹⁷
10¹⁵ (one quadrillion)~3 × 10⁻⁷ (0.00003%)
2.6 × 10¹⁸~50%

At the scale of any real application — even the world’s largest databases with billions of rows — the collision probability for UUID v4 is so small it is not worth engineering around.

UUID v7 collision analysis

UUID v7 separates the problem by millisecond:

n₅₀% ≈ √(2 × 2⁷⁴ × 0.693) ≈ 1.6 × 10¹¹ UUIDs per millisecond

Reaching 1% collision probability within a single millisecond requires approximately 7 billion UUIDs in that millisecond — far beyond any single-node generation rate. For multi-node systems generating rapid bursts, the monotonic counter (RFC 9562 §6.2 Method 1) replaces the random rand_a bits with a counter, eliminating within-millisecond collisions entirely on each node.

The difference between collision and unpredictability

The birthday problem addresses collision — two values being accidentally equal. It says nothing about predictability — whether an attacker can guess a future UUID value.

UUID v4 is both collision-resistant and unpredictable (122 bits of CSPRNG output). UUID v7 is collision-resistant but semi-predictable — knowing the timestamp narrows the UUID space to 2⁷⁴ possibilities for that millisecond. For most applications (database primary keys, event IDs) this is irrelevant. For security-sensitive uses (session tokens, capability grants), use dedicated cryptographic random bytes, not UUIDs. The OWASP Top 10 covers the distinction between identifiers and secrets.

Practical implications

External references

Frequently asked questions

How does the birthday problem apply to UUID collision probability?

The birthday paradox shows that the probability of a collision grows with the square of the number of values generated, not linearly. For UUID v4 with 2¹²² possible values, the probability of at least one collision among n generated UUIDs is approximately 1 − e^(−n²/2^123). To reach 50% collision probability, you need approximately 2.7 × 10¹⁸ UUIDs — roughly 86 years of generation at 1 billion UUIDs per second. This is treated as impossible in practice. The Wikipedia birthday problem article covers the full probability derivation.

Is UUID v7 more or less collision-resistant than UUID v4?

UUID v7 has less collision resistance within a single millisecond — it carries only 74 bits of randomness (versus 122 for UUID v4) per millisecond time window. Two UUID v7 values generated in the same millisecond collide with probability 1/2⁷⁴ per pair — about 1 in 18 quadrillion. Across different milliseconds, collision is impossible because the 48-bit timestamp prefix differs. For typical applications generating fewer than millions of IDs per millisecond, UUID v7 is collision-safe in practice. RFC 9562 §6.1 discusses UUID uniqueness considerations.

At what scale does UUID collision become a real concern?

For UUID v4, collision is not a practical concern at any realistic scale — 2.7 × 10¹⁸ IDs at 1 billion/second takes 86 years. For UUID v7 within a single millisecond, collision probability reaches 1% at approximately 6.1 million UUIDs in the same millisecond on the same node (from the birthday formula applied to 2⁷⁴ values). Real systems generating millions of UUIDs per millisecond should use the monotonic counter (Method 1 in RFC 9562 §6.2) which eliminates within-millisecond collisions entirely by using a counter instead of random bits in rand_a.