--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Sparx64ブロック暗号を用いた分散64ビット一意ID生成' description: 30ビットのタイムスタンプ、17ビットのノードID、17ビットのローカルカウンタを組み合わせ、推測不可能なIDを生成するためにSparx64 ARXブロック暗号を用いる、分散型64ビット一意ID生成器。 language: ja date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- ある状況を考えてみましょう。外部の第三者が次の番号や前の番号を予測できないようにしながら、一意の64ビット乱数を生成する必要があるとします。 ここでは、8バイトの乱数値を生成し、それがデータベース内に既に存在するかを確認し、一意であれば保存する、という方法が考えられます。 しかしながら、この方法にはいくつかの欠点があります。一意性を保証するためには、生成したすべての番号をデータベースに保存しなければなりません。また、データベースへの少なくとも一回のラウンドトリップが必要となるため、特にスケーラビリティが重要となる分散環境においては、レイテンシの問題が生じます。 これらの問題を解決するために、我々は分散型、一様性、予測不可能性、一意性を備えた乱数ID生成器であるRandflake IDを導入します。 ## Randflake IDはどのように機能するか Randflake IDは、X（旧Twitter）によって開発され、広く利用されているk-sortable ID生成方式であるSnowflake IDに着想を得ています。 Snowflake IDは、現在のタイムスタンプ、ノードID、およびローカルカウンタを用いて識別子を生成します。 我々は、このアプローチをさらに発展させ、乱数による一意ID生成へと拡張するとともに、新たに秘密鍵の要素を追加しました。 主要な着想は、既存の一意ID生成器にブロック暗号層を追加することにより、数値間の関係を予測することが実質的に不可能となるようにすることです。 ブロック暗号とは、固定長の平文ブロックを、同じ長さの暗号文ブロックへと変換する基本的な暗号関数です。この変換は暗号鍵によって制御されます。ブロック暗号の特徴的な性質は可逆性にあります。すなわち、各一意の入力が一意の出力に対応し、その逆も成り立つよう、一対一（全単射）の関数でなければなりません。この性質は復号にとって不可欠であり、正しい鍵が適用された場合に暗号文から元の平文を復元することを可能にします。 ブロック暗号を一対一関数として用いることにより、各一意の入力が、定義された範囲内において対応する一意の出力を生成することを保証できます。 ## 構造と設計上の考慮事項 これらの基本的概念を踏まえ、Randflake IDがこれらの着想を実際にどのように実装しているかを検討します。 Randflake IDの構造は、秒精度の30ビットUnixタイムスタンプ、17ビットのノード識別子、17ビットのローカルカウンタ、そしてsparx64アルゴリズムに基づく64ビットブロック暗号から構成されています。 設計上の決定事項は以下のとおりです。 - Google Cloud PlatformのいくつかのVMインスタンスは、0.2ミリ秒の精度でクロックを同期できますが、そのような精度はパブリックインターネットや他のクラウドプロバイダでは利用できません。 - ノード間でクロックを効果的に同期できるのは数ミリ秒の分解能に限られるため、秒精度を採用しました。 - 17ビットのノード識別子は、同時に131072個の個別の生成器を割り当てることを可能にし、プロセス単位、コア単位、またはスレッド単位で割り当てることができます。 - 高スループットのシステムにおいては、17ビットのローカルカウンタでは不十分となる可能性があります。スループットに対応するため、単一のプロセスまたはスレッド内で、それぞれ異なるノードIDを持つ複数の生成器を割り当てることができます。 - 我々は64ビットブロック暗号として、現代的な軽量ARXベースのブロック暗号であるsparx64を採用しました。 - Randflake IDは内部的なトレーサビリティを備えており、その発生元のノードIDおよびタイムスタンプは、秘密鍵を保有する者にのみ明らかになります。 - 理論上の最大スループットは17,179,869,184 ID/秒であり、これはほとんどのグローバル規模のアプリケーションにとって十分な水準です。 ## Randflake ID生成の擬似コード Randflake IDの生成過程をさらに説明するために、以下のPythonによる擬似コードは簡略化された実装を示しています。 ```python import time import struct from .sparx64 import Sparx64 # 定数 RANDFLAKE_EPOCH_OFFSET = 1730000000 # 2024年10月27日（日曜日）3:33:20 AM UTC # ビット割り当て RANDFLAKE_TIMESTAMP_BITS = 30 # タイムスタンプ用30ビット（寿命34年） RANDFLAKE_NODE_BITS = 17 # ノードID用17ビット（最大131072ノード） RANDFLAKE_SEQUENCE_BITS = 17 # シーケンス用17ビット（最大131072シーケンス） # 導出定数 RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("