--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Distribueret generering af 64-bit unikke ID''er med Sparx64-blokchiffer' description: Distribueret 64-bit unik ID-generator, der kombinerer et 30-bit tidsstempel, et 17-bit node-ID, en 17-bit lokal tæller og Sparx64 ARX-blokchifferet for ID'er, der ikke kan gættes. language: da date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Overvej en situation, hvor vi skal generere unikke 64-bit tilfældige tal, og eksterne parter ikke må kunne forudsige det næste eller forrige tal. Her kan vi generere en 8-byte tilfældig værdi, kontrollere, om den allerede findes i databasen, og derefter gemme den, hvis den er unik. Denne metode har dog flere ulemper. Vi er nødt til at gemme hvert genereret tal i en database for at sikre unikhed. Kravet om mindst én rundrejse til databasen skaber latenstidsproblemer, især i et distribueret miljø, hvor skalerbarhed er afgørende. For at løse disse problemer introducerer vi Randflake ID: en distribueret, uniform, uforudsigelig og unik generator af tilfældige ID'er. ## Hvordan fungerer Randflake ID? Randflake ID er inspireret af Snowflake ID, den udbredte k-sorterede ID-genereringsmekanisme udviklet af X (tidligere Twitter). Snowflake ID bruger det aktuelle tidsstempel, et node-ID og en lokal tæller til at generere en identifikator. Vi udvidede denne tilgang yderligere til generering af tilfældige unikke ID'er og tilføjede et nyt element i form af en hemmelig nøgle. Den centrale idé er at tilføje et blokchiffer-lag til den eksisterende generator af unikke ID'er for at opnå umulighed ved at forudsige sammenhængen mellem tal. En blokchiffer er en grundlæggende kryptografisk funktion, der transformerer en blok af klartekst med fast længde til en chifferblok af samme længde. Denne transformation styres af en kryptografisk nøgle. Blokchifferens særlige kendetegn er dens reversibilitet: den skal være en en-til-en (bijektiv) funktion, hvilket sikrer, at hvert unikt input svarer til et unikt output, og omvendt. Denne egenskab er afgørende for dekryptering, idet den gør det muligt at genskabe den oprindelige klartekst fra chifferteksten, når den korrekte nøgle anvendes. Ved at anvende en blokchiffer som en en-til-en-funktion kan vi garantere, at hvert unikt input frembringer et tilsvarende unikt output inden for det definerede interval. ## Strukturen og designovervejelser Med udgangspunkt i disse grundlæggende begreber undersøger vi nu, hvordan Randflake ID implementerer disse idéer i praksis. Randflake ID-strukturen omfatter et 30-bit unix-tidsstempel med sekundpræcision, et 17-bit node-identifikator, en 17-bit lokal tæller og en 64-bit blokchiffer baseret på algoritmen sparx64. Her er nogle designbeslutninger: - Nogle VM-instanser i Google Cloud Platform kan synkronisere uret med en præcision på 0,2 ms, men dette niveau af nøjagtighed er ikke tilgængeligt på det offentlige internet eller hos andre cloududbydere. - Vi valgte sekundpræcision, fordi vi effektivt kun kan synkronisere uret mellem noder med opløsning på et par millisekunder. - Et 17-bit node-identifikator tillader 131072 individuelle generatorer samtidigt, som kan tildeles på en per-proces-, per-kerne- eller per-tråd-basis. - I systemer med høj gennemstrømning kan en 17-bit lokal tæller være utilstrækkelig. For at matche gennemstrømningen kan vi tildele flere generatorer, hver med et særskilt node-ID, til at arbejde i samme proces eller tråd. - Vi valgte sparx64 som 64-bit blokchiffer, en moderne letvægts blokchiffer baseret på ARX-konstruktionen. - Randflake ID'er tilbyder intern sporbarhed, idet de kun afslører deres oprindelige node-ID og tidsstempel over for dem, der er i besiddelse af den hemmelige nøgle. - Den teoretiske maksimale gennemstrømning er 17.179.869.184 ID'er/s, hvilket er tilstrækkeligt til de fleste applikationer i global skala. ## Pseudokode for generering af Randflake ID For yderligere at illustrere genereringsprocessen for Randflake ID giver følgende Python-pseudokode en forenklet implementering: ```python import time import struct from .sparx64 import Sparx64 # Konstanter RANDFLAKE_EPOCH_OFFSET = 1730000000 # Søndag, 27. oktober 2024 kl. 03:33:20 UTC # Allokering af bits RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bits til tidsstempel (levetid på 34 år) RANDFLAKE_NODE_BITS = 17 # 17 bits til node-id (maks. 131072 noder) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bits til sekvens (maks. 131072 sekvenser) # Afledte konstanter 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("