UUID v4は本当に一意なのか？（確率の背後にある数学）

一意の識別子を生成することは、ソフトウェア開発における基本的な課題です。

データベースの主キーであれ、セッションIDであれ、トランザクション追跡であれ、私たちは常にエンティティを一意に識別する方法を必要としています。

この目的のために最も広く採用されている標準が UUID (Universally Unique Identifier) です。

そのバリエーションの中でも、乱数に基づく UUID バージョン4 は、中央の調整を必要としないため、分散システムで特に好まれています。

しかし、すべての開発者は一度は立ち止まって疑問に思ったことがあるでしょう。

「ランダムに生成されるなら、世界のどこかで衝突する可能性があるのではないか？」

この記事では、UUID v4の構造、衝突確率の背後にある数学、そしてそれを安全に生成するための技術的要件について探ります。

1. UUID v4の構造とエントロピー

UUIDは128ビット（16バイト）の数値です。

通常、xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx のような36文字の16進数文字列（ハイフンを含む）として表現されます。

UUID v4の場合、特定のビットがバージョンとバリアントを示すために予約されています。

したがって、合計128ビットからこれらの6つの固定ビットを差し引くと、122ビット の純粋なエントロピーが残ります。

122ビットの可能な組み合わせの数は $2^{122}$ です。

$2^{122} \approx 5.3 \times 10^{36}$

これは正確には 5,316,911,983,139,663,491,615,228,241,121,378,304 です。

この天文学的な数字を視点に入れるために、いくつかの比較を見てみましょう。

「誕生日のパラドックス」として知られる確率論を使用して、 $n$ 個のUUIDを生成した後の衝突確率 $p$ を近似できます。

$p(n) \approx 1 - e^{-\frac{n^2}{2 \times 2^{122}}}$

この式によると：

結論として、宇宙的な規模の話をしていない限り、UUID v4の衝突を心配することは実質的に不要です。その確率は、宝くじに連続して何度も当選するよりも低いです。

しかし、これらの数学的確率は、ある重要な条件が満たされた場合にのみ真となります。それは 「予測不可能な乱数」 の使用です。

多くのプログラミング言語の標準的な乱数関数（例：Cの rand()、Javaの Random、JavaScriptの Math.random()）は、擬似乱数生成器 (PRNG) を使用しています。

これらはシード値に基づく決定論的なものであり、周期が短かったり、識別可能なパターンを持っていたりする可能性があります。

標準的なPRNGでUUIDを生成すると、衝突のリスクが劇的に増加し、セキュリティ上の脆弱性が生じます。

安全なUUIDを生成するには、CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) を使用する必要があります。

CSPRNGには以下の特性があります。

現代のオペレーティングシステムやブラウザは、ハードウェアノイズ（キーボードの打鍵、マウスの動き、ディスクI/Oなど）からエントロピーを収集することでこれを実現しています。

UUID v4は、現代の分散コンピューティングにおける識別子問題に対する最もエレガントで堅牢なソリューションの1つです。

$2^{122}$ という圧倒的な大きさは、私たちに数学的な保証を与えてくれます。

ただし、この保証は 「適切なツール (CSPRNG)」 が使用された場合にのみ有効であることを忘れないでください。

開発者として、利便性の背後にある原理を理解し、適切なセキュリティAPIを利用することは、システムの整合性を維持するために不可欠です。