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 generated | Collision 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:
- Across milliseconds: Two UUIDs generated in different milliseconds have different timestamp prefixes — they cannot collide regardless of the random bits.
- Within one millisecond: 74 random bits per UUID (rand_a + rand_b). Apply the birthday formula with N = 2⁷⁴:
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
- No UUID deduplication needed: For UUID v4 and UUID v7, you do not need a separate deduplication check for collision prevention — the probability is negligible. Add a
UNIQUEconstraint on the database column as a safety net, not as a primary collision prevention mechanism. - Database
UNIQUEconstraints: UseUNIQUEon UUID primary key columns not to prevent collisions but to catch bugs (e.g. accidentally inserting the same ID twice in application code). - UUID v5 is deterministic, not random: UUID v5 (SHA-1 hash-based) always produces the same output for the same input — it has no collision resistance for different inputs that hash to the same value (SHA-1 collision resistance is limited). For collision-resistant identifiers, use UUID v4 or v7.
Related terms
- Collision — what the birthday problem predicts
- Entropy — the random bits that provide collision resistance
- CSPRNG — the source of cryptographic randomness
- Monotonic Counter — eliminates within-ms collisions
External references
- Wikipedia — Birthday problem
- RFC 9562 §6.1 — UUID uniqueness
- RFC 9562 §6.2 — monotonic counter methods
- OWASP Top 10
- Wikipedia — UUID
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.