--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Distribuerad generering av 64-bitars unika ID:n med blockchiffret Sparx64' description: Distribuerad generator av unika 64-bitars ID:n som kombinerar en 30-bitars tidsstämpel, en 17-bitars nod-ID, en 17-bitars lokal räknare och blockchiffret Sparx64 ARX för ID:n som inte kan gissas. language: sv date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Överväg en situation där vi behöver generera unika 64-bitars slumptal, och externa parter ska inte kunna förutsäga nästa eller föregående tal. Här kan vi generera ett slumpmässigt värde på 8 byte, kontrollera om det redan finns i databasen och sedan lagra det om det är unikt. Denna metod har dock flera nackdelar. Vi måste lagra varje genererat tal i en databas för att säkerställa unikhet. Kravet på minst en förfrågan till databasen och tillbaka skapar latensproblem, särskilt i en distribuerad miljö där skalbarhet är avgörande. För att lösa dessa problem introducerar vi Randflake ID: en distribuerad, likformig, oförutsägbar och unik generator för slumpmässiga ID:n. ## Hur fungerar Randflake ID? Randflake ID är inspirerat av Snowflake ID, den allmänt använda k-sorterade ID-genereringsmekanismen utvecklad av X (tidigare Twitter). Snowflake ID använder den aktuella tidsstämpeln, ett nod-ID och en lokal räknare för att generera en identifierare. Vi utökade detta tillvägagångssätt ytterligare för generering av slumpmässiga unika ID:n och lade till ett nytt element i form av en hemlig nyckel. Den centrala idén är att lägga till ett lager av blockchiffer ovanpå den befintliga generatorn för unika ID:n för att uppnå omöjlighet att förutsäga sambandet mellan tal. Ett blockchiffer är en grundläggande kryptografisk funktion som transformerar ett block av klartext med fast längd till ett chiffertextblock av samma längd. Denna transformation styrs av en kryptografisk nyckel. Blockchiffrets särskilda egenskap är dess reversibilitet: det måste vara en envägs-till-envägs-funktion (bijektiv), vilket säkerställer att varje unik indata motsvarar en unik utdata, och vice versa. Denna egenskap är avgörande för dekryptering, eftersom den ursprungliga klartexten kan återställas från chiffertexten när rätt nyckel används. Genom att använda ett blockchiffer som en envägs-till-envägs-funktion kan vi garantera att varje unik indata ger en motsvarande unik utdata inom det definierade intervallet. ## Strukturen och designöverväganden Utifrån dessa grundläggande begrepp, låt oss undersöka hur Randflake ID implementerar dessa idéer i praktiken. Randflake ID-strukturen omfattar en 30-bitars Unix-tidsstämpel med sekundprecision, ett 17-bitars nodidentifierare, en 17-bitars lokal räknare och ett 64-bitars blockchiffer baserat på algoritmen sparx64. Här är några designbeslut: - Vissa VM-instanser i Google Cloud Platform kan synkronisera klockan med en precision på 0,2 ms, men denna noggrannhetsnivå är inte tillgänglig på det publika internet eller hos andra molnleverantörer. - Vi valde sekundprecision eftersom vi endast effektivt kan synkronisera klockan mellan noder inom en upplösning på några millisekunder. - Ett 17-bitars nodidentifierare tillåter 131072 individuella generatorer vid samma ögonblick, vilka kan tilldelas på per-process-, per-kärna- eller per-tråd-basis. - I system med hög genomströmning kan en 17-bitars lokal räknare vara otillräcklig. För att matcha genomströmningen kan vi tilldela flera generatorer, var och en med ett distinkt nod-ID, att arbeta i en och samma process eller tråd. - Vi antog sparx64 som 64-bitars blockchiffer, ett modernt lättviktigt blockchiffer baserat på ARX-konstruktionen. - Randflake ID:n erbjuder intern spårbarhet och avslöjar sitt ursprungliga nod-ID och tidsstämpel endast för dem som innehar den hemliga nyckeln. - Den teoretiska maximala genomströmningen är 17 179 869 184 ID/s, vilket är tillräckligt för de flesta applikationer i global skala. ## Pseudokod för Randflake ID-generering För att ytterligare illustrera processen för generering av Randflake ID:n tillhandahåller följande Python-pseudokod en förenklad implementation: ```python import time import struct from .sparx64 import Sparx64 # Konstanter RANDFLAKE_EPOCH_OFFSET = 1730000000 # Söndag 27 oktober 2024 kl. 03:33:20 UTC # Bitallokering RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bitar för tidsstämpel (livslängd på 34 år) RANDFLAKE_NODE_BITS = 17 # 17 bitar för nod-ID (max 131072 noder) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bitar för sekvens (max 131072 sekvenser) # Härledda 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("