開発者ツール · UUID ジェネレーター
v4 UUID にはランダム ビットがいくつありますか? 128 ではなく、122
· 仕組み
uuid 暗号化 ブラウザ API
ランダムな UUID 内の 128 ビットのうち 6 つは標準によって固定されており、122 はランダム性のために残されています。この投稿では、衝突の確率を正直に推定する方法と、実際の衝突が数学ではなく壊れた発電機に起因する理由を説明します。
建築家の質問: 複製を手に入れることはできるでしょうか? — 心配はどこから来るのか、なぜ答えはジェネレータに依存するのか
アーキテクトは次のように尋ねます。10 年間にわたって 1 日あたり 10 百万個の UUID を生成した場合、重複することはあるでしょうか?正直な答えは、ジェネレータが暗号的に安全であれば、ほぼ間違いなくそうではありません。発電機が壊れていれば、ほぼ確実にそうです。 RFC 9562 の計算は正確です。122 ランダム ビットを含む v4 UUID の衝突確率は、およそ n² / 2 の 123 乗です。ここで、n は生成される識別子の数です。ほとんどの実際のシステムでは、この確率は無視できます。問題は、この式ではすべてのビットが本当にランダムであると仮定していることです。ジェネレーターがリークしたり反復したり、予測どおりにシードされた場合、式は間違っており、重複が避けられなくなります。 128 ビット レイアウトには、標準によって固定され設定されている 4 つのバージョン ビット (v4 の場合は 0100) と 2 つのバリアント ビット (RFC 9562 の場合は 10) が含まれます。
4 つのバージョン ビットと 2 つのバリアント ビットのうち、どの 6 ビットが話されているか、およびそれらがランダムではなく設定されている理由
これにより、ランダム性のために 122 ビットが残ります。この定式化は、122 ランダム ビットに対して 2 と呼ばれることもあり、一意の値が生成されます。誕生日のパラドックス近似を使用すると、ランダムに生成された n 個の値の間で少なくとも 1 つの衝突が発生する確率は、およそ n² / 2 から 123 分の 1 になります。 n = 1 百万の場合、これは (10^6)² / 2^123 = 10^12 / 9 となります。 3 × 10^36、これは約 10^-25 です。 n = 10 億の場合、まだ約 10^-16 です。これらは「事実上ゼロ」ではありません。誕生日の近似値は、リスクを計算するための具体的な方法を提供します。生成する予定の UUID を数え、その数を 2 乗し、2 の 123 乗で割ります。ジェネレーターがブラウザーの crypto.getRandomValues である場合、すべてのビットはオペレーティング システムのエントロピーによって裏付けられます。それが数学であれば。
簡単に言うと誕生日の近似値です。n 個の識別子間で少なくとも 1 回の衝突が起こる確率は、およそ n の 2 乗を 2 で割って 123 にします。
不適切なまたは繰り返し状態のジェネレーターによって生成された UUID の場合、独立性の仮定が偽であるため、数学モデルは機能しません。テキストに version-4 ニブルが含まれている場合でも、固定されたテスト シード、コピーされたフィクスチャ、またはプロセス スナップショットは値を再生できます。これらは実装上の欠陥であり、122 フィールドの計算が間違っていたという証拠ではありません。別のありふれたソースは、同じリテラル識別子を複数のフィクスチャにコピーし、後でそれらのデータをマージします。重複を調査するときは、ジェネレーター、シード ポリシー、プロセス ライフサイクル、およびインポート履歴を保存します。 1 つの繰り返された値から、独立した CSPRNG 出力が UUID スペースを使い果たしたという主張にジャンプしないでください。
実用的な例 — 指定された生成速度と期間を近似値に組み込んでおり、各ステップが示されているため、独自の数値を置き換えることができます。
ランダム状態の再同期を行わないプロセスのフォーク。 crypto.getRandomValues の代わりに Math.random が使用されるバグ。複数の行で同じ UUID を使用して手作りされ、誤って実稼働環境で使用されたテスト フィクスチャ。範囲制限または状態バグのある UUID ライブラリの古いバージョン。これらのシナリオには誕生日の近似数学は含まれていません。実装の失敗や運用ミスが含まれます。システムの衝突リスクを正直に計算します。UUID の生成率 (1 秒あたり、1 日あたり、1 年あたり) を計算し、システムの実行期間にわたってそれを予測し、その合計を誕生日の計算式に代入します。システムが 5 年間にわたって 1 日あたり 100,000 個の UUID を生成する場合 (合計 182 百万個)、衝突確率は (1. 82 × 10^8)² / 2^123 ≈ 3。 3 × 10^-22、これは無視できます。
重複が実際に発生する場所 — Math.random シード、クローンされた仮想マシン、状態がコピーされたフォークされたプロセス、およびフィクスチャ内のコピーアンドペースト
1 年間で 1 秒あたり 10 百万件 (合計 315 兆件) を生成する場合、確率は (3. 15 × 10^14)² / 2^123 ≈ 10^-10、これはまだ消えるほど小さいです。これらの推定では、すべてのビットが独立していてランダムであると仮定しています。 ToolAcre ジェネレーターは、CSPRNG に基づくランダム性を提供する crypto.getRandomValues を使用します。信頼できるのは操作だけです。衝突の可能性を言い訳にして、適切な認証チェックをスキップしないでください。 UUID は、たとえ 122 ランダム ビットであっても、パスワードでもアクセス トークンでも秘密でもありません。独自性が利点です。予測不可能性は、推測を防ぐ別の (そしてより重要な) 特性です。誕生日の数学は一意性を処理します。有効期間 (この UUID は期限切れになるべきか?)、機密性 (保存前にハッシュする必要があるか?)、または承認 (この UUID を所有していることは呼び出し元について何か証明できるか?) については扱いません。 ToolAcre ジェネレーターは、122 ランダム ビットを含む CSPRNG ベースの UUID を提供します。これは、数学が保持する一意性と予測不可能性が確実であることを意味します。それ以外のすべて (トークンの検証、有効期限、アクセス制御) はアプリケーションの責任です。確率式は、生成された各 UUID が前の世代から独立していることを前提としています。システムが単一の CSPRNG インスタンスから識別子を生成し、各呼び出しが OS から新しいランダム性を引き出す場合、独立性の仮定が維持されます。システムがキャッシュされた CSPRNG 状態または OS の再シードなしでシードされたジェネレーターを使用している場合、この仮定は崩れます。エントロピー ソースが使い果たされた場合 (一部の組み込みシステムまたは負荷がかかっている仮想マシンで発生)、またはプロセス間でランダムな状態がリセットされなかった場合 (CSPRNG を再シードせずにプロセスがフォークした場合)、衝突のリスクは大幅に増加します。
これでカバーされないもの — v1 および v7 の一意性。ランダム性だけではなく、タイムスタンプとクロック シーケンスに依存します。
ToolAcre フォールバックは、バイト配列ごとに crypto.getRandomValues を呼び出し、アプリケーション レベルの PRNG 状態を保持しません。プラットフォームの内部は依然としてブラウザーとオペレーティング システムの責任です。実際の発電機との衝突をシミュレーションすると、理論と実践の違いがわかります。同じシードから開始して Math.random で構築されたジェネレーターは、同一のシーケンスを生成します。最初の UUID 衝突は、誕生日の近似が予測するように、2^60 値 (2^122 の平方根) の後ではなく、生成された数百から数千の値内で発生します。サウンド OS エントロピーからの crypto.getRandomValues を使用するジェネレーターは、理論上の確率 (2^60 UUID 程度) が避けられない場合にのみ衝突を生成しますが、その数は決して到達できないほど大きくなります。弱いエントロピー ソースまたは再利用されたエントロピー ソース (適切に実装されていない UUID ライブラリやテスト フレームワークによくある) を使用するジェネレーターは、その間のどこかで衝突を引き起こします。
要点: 数学を信頼し、ジェネレーターを監査してください。ToolAcre ジェネレーターはブラウザーの CSPRNG を使用します。これは偽装してはいけない部分です
バッチ テストは、定数を返す実装や明白なシーケンスを再生する実装を検出できますが、合格したサンプルは将来の一意性を証明できません。実稼働システムでは、重複した識別子によってデータが破損する場合でも、一意の制約を強制する必要があります。 2 つの有効なソース システムに同じリテラル識別子が既に含まれている可能性があり、フィクスチャが環境間でコピーされる可能性があるため、インポートには特別な注意が必要です。 ToolAcre のテストでは、500 のバッチに 500 の個別の値が含まれていることを確認します。これはこの実装の回帰チェックであり、統計的な保証ではありません。重複が現れた場合は、原因を特定する前に証拠を保存し、生成、インポート、フィクスチャ、およびストレージのパスを検査してください。