宇宙規模の固有ID

 (jasonfantl.com)
25 ポイント 投稿者 GN⁺ 2026-02-20 | 4件のコメント | WhatsAppで共有
  • 機器やオブジェクトに絶対に重複しないIDを付与する方法を探求し、ランダム(random)方式と決定的(deterministic)方式を比較
  • ランダム方式は十分に大きいビット数を使えば衝突確率を事実上0にでき、UUID(122ビット) から宇宙全体の計算限界(798ビット) までさまざまな水準がある
  • 決定的方式では中央カウンター、委任型階層構造(Dewey)、二分木(Binary)、トークン(Token) など複数のスキームを提案し、各方式のID長の成長特性をシミュレーションで分析
  • すべての決定的スキームは最悪の場合の線形(linear)成長を避けられないという数学的証明も提示
  • 結果として、宇宙規模の拡張でも実用的かつ効率的な方法はランダムID生成であり、決定的方式は非効率であることを確認

固有IDの必要性と問題設定

  • オブジェクト識別は製造、物流、通信、セキュリティなどあらゆるシステムの基盤であり、大規模に拡張した際に重複のないID付与が中核課題となる
  • 人類が銀河規模へ拡張する場合でも、重複のないID体系が必要になる
  • 問題は「どうすれば絶対に重複しないIDを作れるのか」と設定される

ランダム(Random)方式

  • 最も単純な方法は任意の数を選ぶこと
    • 中央管理や同期なしでどこでも生成できる
  • 衝突確率はビット数を増やして制御可能で、事実上0に近づけられる
  • UUID(122ビット) では約 $2^{61}$ 個のIDを生成すると衝突が予想される
  • 宇宙全体の計算限界(10¹²⁰回) を考慮すると798ビットが必要
    • 原子単位(10⁸⁰個)基準では532ビット、1gナノボット(10⁵⁶個)では372ビット
  • 真のランダム性の確保が重要で、CSPRNG や量子乱数源の利用を推奨
    • ありふれたシードや定数ID(例: all-zero)は使用禁止が必要

決定的(Deterministic)方式

  • 中央カウンター方式は単一サーバーが順番にIDを発行
    • アクセシビリティの問題から衛星・機器間の委任構造(Dewey) を提案
  • Deweyスキーム: A.B.C 形式の階層型IDで、Elias omega coding で表現
    • 木構造に応じて対数的または線形成長を示す
  • BinaryスキームはID空間を二分木で分割し、一部のケースではDeweyより効率的
  • 2-Adic Valuation は数学的な固有性を保証し、Binaryの変形形
  • Tokenスキームはチェーン構造では対数的成長を示すが、幅が広がると線形に転じる

線形成長の不可避性の証明

  • すべてのID付与経路が固有でなければならないことを前提に、可能な経路数を計算
  • ノード数が n のとき必要なID数は $2^{n-1}$ に増加
  • したがってID長は最低でも O(n)、すなわち最悪の場合は線形成長が不可避
  • どんなアルゴリズムでも、すべてのケースで対数的成長を維持することはできない

拡張モデルのシミュレーション

  • Random Recursive Tree、Preferential Attachment、Fitness Model など多様な成長モデルで実験
    • 小規模(2,048ノード)ではBinaryが優秀で、Dewey・Tokenは状況によって差が出る
    • PreferentialモデルではDeweyが最も効率的
    • FitnessモデルではDeweyとBinaryが近い性能
  • 100万ノード規模の実験でもDewey・Tokenは対数的成長を維持
    • ID長 ≈ 6.55 × ln(n) の形で近似可能

銀河および宇宙規模の拡張モデル

  • 惑星間拡散は一定速度の波動(front)としてモデル化
    • 各惑星は約10⁹個のIDを生成した後、次の惑星へ拡散
  • 銀河半径は約2,121惑星で、全体へ拡散した場合のID長は約 288,048ビット
  • 銀河間拡散(約7,816段階)まで考慮すると約22億ビット(281MB) が必要
  • 決定的方式は非効率で、ランダム方式(798ビット以下) が圧倒的に効率的

セキュリティおよび追加の考慮事項

  • ID偽造防止のため署名ベースの検証体系を適用可能
    • ランダムIDは公開鍵をIDとして使い、決定的スキームでは親が子の鍵に署名
  • 誤り訂正コードとバージョン管理が必要
  • IDを保存できないオブジェクト(例: 惑星)は複数のIDをマッピングして管理
  • テセウスの船の問題のように、構成要素の交換時にIDを維持するかどうかも議論される
  • 関連概念: Decentralized Identifiers(DID)、Ancestry Labeling Schemes

結論

  • 決定的スキームは理論的には興味深いが、実用性は低い
  • ランダムID生成が宇宙規模でも現実的かつ効率的
  • ID衝突確率を「事実上0」にすることが、最も安全で実用的な選択である

関連記事

4件のコメント

 
mammal 2026-02-20

ぜひ原文を読んでみてください。数式とシミュレーションを可視化しながら説明してくれていて、とても楽しく読めました。
 
princox 2026-02-20

時間ベースで作るものは、線形的なものとして見るべきなんでしょうか……？
原文を少し見てみないといけませんね。興味深い話です。
 
hmmhmmhm 2026-02-20

衝突したら、宇宙規模で運が悪いってことか……(?)
 
GN⁺ 2026-02-20
Hacker News のコメント

  • この分析は完全に公正ではない。UUID の設計では 局所性 (locality)、つまり光速を考慮しているのに、衝突確率の計算ではそれを無視している。実際に衝突が意味を持つには、2 つの UUID が生成後に 因果的接触 (causal contact) する必要がある。したがって単純な誕生日のパラドックス (birthday paradox) を適用するのは誤ったアプローチだ。局所性を考慮すれば、必要な UUID のサイズは記事で述べられている 800 ビットよりはるかに小さいはずだ。数学的な計算はしていないが、256 ビットを超えることはない気がする。HN はこういう 厳密な技術的議論 が真面目に交わされる数少ない場所なので本当に好きだ

    • 昔、銀河が遠ざかって互いに情報交換できなくなる宇宙膨張仮説を読んだことがある。その仮説によれば、知的生命体は生き残るために 質量密度が最も高い場所へ収束 することになる。結局、宇宙の熱的死の前に異星文明が一か所に集まる「大合流」が起きるかもしれない。その頃には UUID 衝突が起きるかもしれない。Vogon たちが XML タグごとに UUID を付けて統計をめちゃくちゃにする様子を想像してしまう
    • 昔 Intel の NIC を箱で受け取ったら、全部同じ MAC アドレス だったことがある。原因を突き止めるのに何日も苦労した記憶がある
    • 極端に低い確率を論じるなら、そもそも私たちが 宇宙論を誤解している可能性 まで考慮すべきだ。光円錐 (light cone) が因果的限界ではないのかもしれない
    • 時間と局所性の両方を考慮すべきだ。陽子が崩壊し物質が消えるまでの時間は、せいぜい約 10^56 ナノ秒にすぎない
    • この批判は正しい。元記事は面白い思考実験だが、因果性を無視して問題を過大評価している。実際、UUID の衝突が意味を持つのは、互いに通信するシステム内だけだ。そうしたシステムは光円錐によって制限される。128 ビット で人類が千年間に作るシステムには十分で、256 ビットは宇宙全体でも過剰だ

  • アドレス指定可能なオブジェクト数を計算するなら、各オブジェクトのアドレスが最低 1 回はどこかに保存されなければならない点を考慮すべきだ。1 ビットを保存するのに Npb 粒子 が必要なら、アドレスのビット数が増えるほどアドレス指定可能なオブジェクト数は減る。したがって Nthg = Np / (Npb * f(Ntng)) のような関係式で、最大のアドレス可能数を求められる

  • 以前、256 ビットのランダム ID なら衝突チェックなしで十分だと主張しなければならなかったことがある。同僚たちは複雑な 衝突検証ロジック を追加しようと言っていたが、2^256 は観測可能な宇宙の原子数に近い規模だと説明した。衝突が起きる前に、データセンターが何百万回も爆発する確率のほうが高いと説得した。結局、128 ビットだけでも十分だという結論に達した

    • ただし分散環境で 信頼できない主体 が ID を生成するなら、悪意ある衝突の可能性があるので検証が必要だ。一方、単一システムなら単純なカウンタで十分で、複数サーバーがあるなら シャーディングされたカウンタ で区間を分ければよい
    • 実は計算はもっと簡単だ。全人類のデータ総量はまだ 1 ヨタバイトにも達していない。誕生日のパラドックスによれば、50% の衝突確率は 2^128 個程度で発生する。256 ビット ID は 32 バイトなので、2^128 * 32 バイト = 10^16 ヨタバイトが必要になる。つまり、衝突確率は天文学的に低い

  • すべての原子に ID を割り当てると仮定すると、約 532 ビットが必要だという計算がある。ただ実際には、原子のグループ（例: マイクロチップ、自動車など）にも ID を付けたくなるだろうから、さらに大きくなるかもしれない

    • 実際には粒子ごとではなく、粒子の種類ごとに 1 つの ID だけで十分だ。物理法則上、同一粒子は区別できないからだ
    • 原子グループを考慮しても、追加されるビット数はほとんどないはずだ
    • UUIDv∞ は最低でも 536 ビットくらいだろうか。グループ ID やタイムスタンプまで入れると 1024 ビットくらいになるかもしれない
    • ニュートリノが振動するたびに ID を新しく割り当てる必要があるだろうか。幸い電子は 1 つで済む

  • トランプのデッキ で ID を表すアイデアがある。52 枚のカードそれぞれを Unicode 文字で表せば読みやすく、手動編集が難しく、パターン認識にも有利だ。実際のカードデッキをシャッフルしてカメラで読み取ればランダムシードとしても使える。似たアイデアとして DiceKeys もある

    • ただし「ちゃんとシャッフルすること」が最大の弱点だ

  • 素晴らしい可視化と洞察だ。私はできるだけ小さなランダム識別子を中心にデータベースを設計してきた。こうした 普遍的識別子 は、事実上唯一の「黄金のディスク」だと思う。科学データ管理や図書館学の分野では、この概念は過小評価されている。大規模組織の問題の多くは、よりよい識別子設計で解決できたはずだ。
    関連記事: Identifiers Deep Dive, Trible Structure

    • エンティティの同一性は 内在的 (intrinsic) に定義することもできる。なぜ 整合性契約 (consistency contract) ではだめなのか？

  • Becky Chambers の『The Galaxy, and the Ground Within』を 281 ページあたりまで読んでいる。
    本の中のメッセージ例:

    Received Message
Encryption: 0
From: GC Transit Authority --- Gora System (path: 487-45411-479-4)
To: Ooli Oht Ouloo (path: 5787-598-66)
Subject: URGENT UPDATE

    このシリーズが本当に大好きだ。多種族宇宙が 中央で合意された経路アドレス体系 を使っている設定が面白い

    • 似た例として Vernor Vinge の『A Fire Upon The Deep』を勧めたい。銀河間通信のラベリング方式が興味深い
    • 特にチーズという概念を恐れる場面が印象的だった。シリーズでは 2 冊目の『A Closed and Common Orbit』が最高だった

  • 最近 Snowflake ID を知った。Twitter、Discord、Instagram、Mastodon などで使われている。タイムスタンプ + ランダムの組み合わせで ID サイズを小さくする方式だが、記事で触れられていなかったのが残念だ。
    Snowflake ID の Wikipedia, Tom Scott の動画 を参照。
    Snowflake タイムスタンプの一部ビットをランダムに置き換えれば、毎秒 40 億個の ID を作れそうだ

    • 実際のところ Snowflake は UUID v1 とほぼ同じ構造だ。ただ半分のサイズなだけだ
    • 似たアイデアとして DRUUID もある
    • だが宇宙全体が 1 つの時計 に同意するのはほぼ不可能だ
    • この方式は BSON ID にも似ている

  • 観測可能な現象 をベースに ID を作れないか気になる。時間と距離で区別される特性のおかげで、一意性が保証されるかもしれない。たとえば、ある時点の星明かりのパターンは 1 人にしか見えない。ラバランプ をノイズからエントロピーを得るのに使うのと似ている。もし宇宙全体の座標系を定義できるなら、ローカル時刻 + x + y + z + salt の組み合わせで一意な ID を作れそうだ

  • ランダム UUID 方式は寿命の面ではるかに優れている。同時に稼働可能なデバイス数には限りがあり、ツリー型 UUID と違って、デバイスが廃棄されれば ID を再利用できる。現実的には 位置ベースのルート + ランダムな下位ビット を混ぜたハイブリッドアルゴリズムが最も実用的だと思う