--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: elosztott, 64 bites egyedi azonosító-generálás Sparx64 blokk-titkosítóval' description: Elosztott, 64 bites egyedi azonosítógenerátor, amely egy 30 bites időbélyeget, 17 bites csomópontazonosítót, 17 bites helyi számlálót és a Sparx64 ARX blokk-titkosítót kombinálja a kitalálhatatlan azonosítók érdekében. language: hu date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Tekintsünk egy olyan helyzetet, amikor egyedi, 64 bites véletlen számokat kell generálnunk, és külső felek ne tudják megjósolni a következő vagy az előző számot. Ebben az esetben generálhatunk egy 8 bájtos véletlen értéket, ellenőrizhetjük, hogy az már létezik-e az adatbázisban, majd tárolhatjuk, ha egyedi. Ennek a módszernek azonban számos hátránya van. Minden generált számot adatbázisban kell tárolnunk az egyediség biztosításához. Az, hogy legalább egy adatbázis-kéréssel kell körbejárnunk, késleltetési problémákat okoz, különösen elosztott környezetben, ahol a skálázhatóság kulcsfontosságú. Ezen problémák megoldására vezetjük be a Randflake ID-t: egy elosztott, egyenletes, kiszámíthatatlan és egyedi véletlen azonosító-generátort. ## Hogyan működik a Randflake ID? A Randflake ID a Snowflake ID-ból indul ki, amely az X (korábban Twitter) által kifejlesztett, széles körben használt, k-rendezett azonosító-generálási mechanizmus. A Snowflake ID az aktuális időbélyeget, egy csomóponti azonosítót (node ID) és egy helyi számlálót használ az azonosító előállítására. Ezt a megközelítést tovább bővítettük véletlen egyedi azonosítók generálására, és egy új titkos kulcs elemmel egészítettük ki. A kulcsgondolat az, hogy a meglévő egyedi azonosító-generátorhoz blokk-titkosító réteget adunk, hogy a számok közötti összefüggés megjóslása megvalósíthatatlan legyen. A blokk-titkosító egy alapvető kriptográfiai függvény, amely a rögzített hosszúságú nyílt szöveg blokkját azonos hosszúságú titkosszöveg-blokká alakítja. Ezt az átalakítást egy kriptográfiai kulcs szabályozza. A blokk-titkosító megkülönböztető jellemzője a visszafordíthatósága: egy-egyértelmű (bijektív) függvénynek kell lennie, amely biztosítja, hogy minden egyedi bemenet egyedi kimenetnek felel meg, és fordítva. Ez a tulajdonság alapvető fontosságú a visszafejtéshez, mivel a helyes kulcs alkalmazásakor az eredeti nyílt szöveg visszanyerhető a titkosszövegből. Ha a blokk-titkosítót egy-egyértelmű függvényként alkalmazzuk, garantálhatjuk, hogy minden egyedi bemenet a definiált tartományon belül egy megfelelő egyedi kimenetet állít elő. ## A szerkezet és a tervezési szempontok Ezekre az alapfogalmakra építve vizsgáljuk meg, hogyan valósítja meg a Randflake ID ezeket az elveket a gyakorlatban. A Randflake ID szerkezete egy 30 bites, másodperc pontosságú unix időbélyeget, egy 17 bites csomópont-azonosítót, egy 17 bites helyi számlálót és a sparx64 algoritmuson alapuló 64 bites blokk-titkosítót tartalmaz. Néhány tervezési döntés: - A Google Cloud Platform egyes virtuális géppéldányai 0,2 ms pontossággal tudják szinkronizálni az órát, de ez a pontosság nem érhető el a nyilvános internetenvagy más felhőszolgáltatóknál. - Másodperc pontosságot választottunk, mert a csomópontok közötti óraszinkronizálást csak néhány milliszekundumos felbontáson tudjuk hatékonyan megvalósítani. - A 17 bites csomópont-azonosító egyidejűleg 131072 egyedi generátort tesz lehetővé, amelyek folyamatonként, magonként vagy szálanként rendelhetők hozzá. - Nagy átviteli sebességű rendszerekben a 17 bites helyi számláló elégtelen lehet. Az átviteli sebesség illesztéséhez több generátort rendelhetünk hozzá, mindegyiket egyedi csomópont-azonosítóval, hogy egyetlen folyamatban vagy szálon működjenek. - A 64 bites blokk-titkosítóként a sparx64 algoritmust alkalmaztuk, amely egy modern, könnyűsúlyú, ARX-alapú blokk-titkosító. - A Randflake azonosítók belső nyomonkövethetőséget biztosítanak: eredeti csomópont-azonosítójukat és időbélyegüket csak a titkos kulccsal rendelkezők láthatják. - Az elméleti maximális átviteli sebesség 17 179 869 184 azonosító/s, ami a legtöbb globális méretű alkalmazás számára elegendő. ## A Randflake ID generálás álkódja A Randflake ID generálási folyamatának további szemléltetésére a következő Python-álkód egyszerűsített megvalósítást nyújt: ```python import time import struct from .sparx64 import Sparx64 # Konstansok RANDFLAKE_EPOCH_OFFSET = 1730000000 # Vasárnap, 2024. október 27., 3:33:20 UTC # Bitkiosztás RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bit az időbélyegnek (34 éves élettartam) RANDFLAKE_NODE_BITS = 17 # 17 bit a csomópont-azonosítónak (legfeljebb 131072 csomópont) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bit a sorszámnak (legfeljebb 131072 sorszám) # Származtatott konstansok 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("