Des identifiants uniques à l’échelle cosmique

 (jasonfantl.com)
25 points par GN⁺ 2026-02-20 | 4 commentaires | Partager sur WhatsApp
  • Explore comment attribuer des ID absolument non dupliqués à des appareils ou des objets, en comparant les approches aléatoires (random) et déterministes (deterministic)
  • L’approche aléatoire permet, avec un nombre de bits suffisamment élevé, de ramener la probabilité de collision à pratiquement 0, avec différents niveaux allant de UUID (122 bits) jusqu’à la limite de calcul de l’univers entier (798 bits)
  • Pour l’approche déterministe, plusieurs schémas sont proposés, comme le compteur central, la structure hiérarchique déléguée (Dewey), le Binary tree et les tokens, avec une analyse par simulation des caractéristiques de croissance de la longueur des ID pour chaque méthode
  • Une démonstration mathématique montre aussi que tous les schémas déterministes ne peuvent éviter une croissance linéaire dans le pire des cas
  • En conclusion, la génération d’ID aléatoires est la méthode pratique et efficace même à l’échelle cosmique, tandis que les approches déterministes se révèlent inefficaces

Nécessité des identifiants uniques et définition du problème

  • L’identification des objets est à la base de tous les systèmes, de la fabrication à la logistique, en passant par les communications et la sécurité, et l’attribution d’ID sans doublon devient un enjeu central à grande échelle
  • Même si l’humanité s’étendait à l’échelle galactique, il faudrait un système d’ID sans duplication
  • Le problème est formulé ainsi : « comment créer des ID absolument sans doublon ? »

Approche aléatoire (Random)

  • La méthode la plus simple consiste à choisir un nombre au hasard
    • Génération possible partout, sans gestion centrale ni synchronisation
  • La probabilité de collision peut être contrôlée en augmentant le nombre de bits, jusqu’à devenir pratiquement nulle
  • Avec UUID (122 bits), on s’attend à des collisions à partir d’environ $2^{61}$ ID générés
  • En prenant en compte la limite de calcul de l’univers entier (10¹²⁰ opérations), il faut 798 bits
    • À l’échelle atomique (10⁸⁰ éléments), 532 bits suffisent, et pour des nanobots de 1g (10⁵⁶), 372 bits
  • Il est crucial de disposer d’une véritable source d’aléa, avec recommandation d’utiliser un CSPRNG ou une source quantique de nombres aléatoires
    • Les seeds courantes ou les ID constants (par ex. all-zero) doivent être interdits

Approche déterministe (Deterministic)

  • Le schéma du compteur central repose sur un serveur unique qui émet les ID de manière séquentielle
    • En raison des problèmes d’accessibilité, une structure de délégation entre satellites et appareils (Dewey) est proposée
  • Le schéma Dewey : ID hiérarchiques de la forme A.B.C, représentés avec Elias omega coding
    • Selon la structure de l’arbre, la croissance peut être logarithmique ou linéaire
  • Le schéma Binary divise l’espace des ID en arbre binaire, plus efficace que Dewey dans certains cas
  • La 2-Adic Valuation garantit une unicité mathématique, sous forme de variante du schéma Binary
  • Le schéma Token présente une croissance logarithmique dans une structure en chaîne, mais bascule vers une croissance linéaire lorsque la largeur augmente

Preuve de l’inévitabilité de la croissance linéaire

  • En partant du principe que tous les chemins d’attribution d’ID doivent être uniques, on calcule le nombre de chemins possibles
  • Si le nombre de nœuds est n, le nombre d’ID nécessaires croît comme $2^{n-1}$
  • Par conséquent, la longueur des ID est au minimum en O(n), ce qui rend inévitable une croissance linéaire dans le pire des cas
  • Aucun algorithme ne peut conserver une croissance logarithmique dans tous les cas

Simulation de modèles d’expansion

  • Expériences menées avec divers modèles de croissance comme Random Recursive Tree, Preferential Attachment et Fitness Model
    • À petite échelle (2 048 nœuds), Binary obtient de bons résultats, tandis que Dewey et Token varient selon les cas
    • Dans le modèle Preferential, Dewey est le plus efficace
    • Dans le modèle Fitness, Dewey et Binary ont des performances similaires
  • Même dans des expériences à un million de nœuds, Dewey et Token conservent une croissance logarithmique
    • La longueur des ID peut être approximée par une forme ≈ 6.55 × ln(n)

Modèle d’expansion à l’échelle galactique et cosmique

  • La diffusion interplanétaire est modélisée comme un front d’onde avançant à vitesse constante
    • Chaque planète génère environ 10⁹ ID avant de se diffuser vers la suivante
  • Pour un rayon galactique d’environ 2 121 planètes, la longueur des ID atteint environ 288 048 bits
  • En prenant aussi en compte la diffusion intergalactique (environ 7 816 étapes), il faut environ 2,2 milliards de bits (281 MB)
  • Les approches déterministes sont inefficaces, tandis que l’approche aléatoire (798 bits ou moins) est de loin la plus efficace

Sécurité et considérations supplémentaires

  • Pour empêcher la falsification d’ID, on peut appliquer un système de vérification basé sur la signature
    • Avec des ID aléatoires, la clé publique peut servir d’ID ; dans un schéma déterministe, le parent signe la clé de l’enfant
  • Il faut aussi des codes de correction d’erreurs et une gestion de versions
  • Pour les objets qui ne peuvent pas stocker d’ID (par ex. une planète), on peut gérer la situation via le mapping de plusieurs ID
  • La question du maintien d’un ID lors du remplacement de composants, comme dans le bateau de Thésée, est également abordée
  • Concepts liés : Decentralized Identifiers (DID), Ancestry Labeling Schemes

Conclusion

  • Les schémas déterministes sont théoriquement intéressants mais peu pratiques
  • La génération d’ID aléatoires reste réaliste et efficace, même à l’échelle cosmique
  • Ramener la probabilité de collision d’ID à « pratiquement 0 » est le choix le plus sûr et le plus pratique

À lire aussi

4 commentaires

 
mammal 2026-02-20

Lisez absolument l’article original. J’ai vraiment pris plaisir à le lire, car il explique les choses de manière très visuelle avec des formules et des simulations.
 
princox 2026-02-20

On peut sans doute considérer qu’une génération basée sur le temps est linéaire, n’est-ce pas… ?
Je vais devoir jeter un œil au texte original. C’est une histoire intéressante.
 
hmmhmmhm 2026-02-20

Si ça entre en collision, il faut vraiment avoir une malchance cosmique... (?)
 
GN⁺ 2026-02-20
Commentaires Hacker News

  • Cette analyse n’est pas totalement équitable. Lors de la conception des UUID, on tient compte de la localité (locality), donc de la vitesse de la lumière, mais ce facteur est ignoré dans le calcul de la probabilité de collision. En pratique, pour qu’une collision ait un sens, les deux UUID doivent entrer en contact causal (causal contact) après leur création. Appliquer simplement le paradoxe des anniversaires est donc une mauvaise approche. Si l’on tient compte de la localité, la taille nécessaire d’un UUID serait sans doute bien inférieure aux 800 bits évoqués dans l’article. Je n’ai pas fait le calcul, mais j’imagine qu’on ne dépasserait pas 256 bits. J’aime vraiment HN, qui reste l’un des rares endroits où ce type de discussion technique pointilleuse a lieu sérieusement

    • J’avais lu autrefois une hypothèse sur l’expansion de l’univers selon laquelle les galaxies s’éloignent au point de ne plus pouvoir échanger d’informations. D’après cette idée, les formes de vie intelligentes finiraient par converger, pour survivre, vers les zones de plus forte densité de masse. On pourrait donc avoir, avant la mort thermique de l’univers, une sorte de « grand rassemblement » de civilisations extraterrestres. C’est peut-être à ce moment-là que des collisions d’UUID se produiraient. J’imagine les Vogons ruinant les statistiques en collant un UUID sur chaque balise XML
    • J’ai déjà reçu un carton de cartes réseau Intel qui avaient toutes la même adresse MAC. Je me souviens avoir passé plusieurs jours à trouver la cause
    • Quand on discute de probabilités extrêmement faibles, il faut aussi envisager la possibilité que notre compréhension de la cosmologie soit erronée. Le cône de lumière (light cone) n’est peut-être pas la limite causale ultime
    • Il faut tenir compte à la fois du temps et de la localité. Le temps jusqu’à la désintégration des protons et la disparition de la matière n’est que d’environ 10^56 nanosecondes
    • Cette critique est juste. Le texte original est une expérience de pensée amusante, mais il surestime le problème en ignorant la causalité. En réalité, une collision d’UUID n’a de sens qu’au sein de systèmes capables de communiquer entre eux. Ces systèmes sont limités par le cône de lumière. 128 bits suffisent largement pour les systèmes que l’humanité créera pendant mille ans, et 256 bits sont excessifs même à l’échelle de l’univers

  • Lorsqu’on calcule le nombre d’objets adressables, il faut tenir compte du fait que l’adresse de chaque objet doit être stockée quelque part au moins une fois. S’il faut Npb particules pour stocker un bit, alors plus le nombre de bits d’adresse augmente, plus le nombre d’objets adressables diminue. On peut donc exprimer le nombre maximal d’objets adressables par une relation du type Nthg = Np / (Npb * f(Ntng))

  • J’ai déjà dû défendre l’idée qu’un ID aléatoire de 256 bits était suffisant sans vérification de collision. Mes collègues voulaient ajouter une logique complexe de vérification des collisions, mais je leur ai expliqué que 2^256 était d’un ordre de grandeur comparable au nombre d’atomes dans l’univers observable. Je les ai convaincus qu’un datacenter avait bien plus de chances d’exploser des millions de fois avant qu’une collision ne se produise. Au final, nous avons conclu que 128 bits suffisaient déjà

    • Mais dans un environnement distribué où des acteurs non fiables génèrent les ID, une collision malveillante reste possible, donc une vérification est nécessaire. En revanche, dans un système unique, un simple compteur suffit, et avec plusieurs serveurs, on peut répartir les plages via un compteur shardé
    • En fait, le calcul est encore plus simple. Le volume total de données de l’humanité n’atteint toujours pas 1 yottaoctet. D’après le paradoxe des anniversaires, une probabilité de collision de 50 % apparaît autour de 2^128 éléments. Un ID de 256 bits fait 32 octets, donc 2^128 * 32 octets = 10^16 yottaoctets nécessaires. Autrement dit, la probabilité de collision est astronomiquement faible

  • Il existe un calcul selon lequel il faudrait environ 532 bits pour attribuer un ID à chaque atome. Mais en pratique, on voudrait probablement aussi attribuer des ID à des groupes d’atomes, comme des microprocesseurs ou des voitures, donc cela pourrait être plus grand

    • En réalité, il ne faut pas un ID par particule, mais un ID par type de particule. D’après les lois de la physique, des particules identiques sont indiscernables
    • Même en tenant compte des groupes d’atomes, le nombre de bits supplémentaires serait probablement négligeable
    • UUIDv∞ ferait donc au moins 536 bits ? Avec un ID de groupe ou un horodatage, on arriverait peut-être à 1024 bits
    • Faut-il attribuer un nouvel ID à chaque oscillation d’un neutrino ? Heureusement, un seul pour l’électron suffit

  • Il y a une idée consistant à représenter les ID avec un jeu de cartes. Si chacune des 52 cartes est représentée par un caractère Unicode, cela devient lisible, difficile à éditer manuellement et favorable à la reconnaissance de motifs. On pourrait aussi mélanger un vrai jeu et le lire avec une caméra pour s’en servir comme graine aléatoire. Il existe une idée proche avec DiceKeys

    • Mais le plus gros point faible, c’est de « bien mélanger »

  • Belle visualisation, et très bonne intuition. J’ai conçu des bases de données centrées autant que possible sur des identifiants aléatoires très courts. Je considère ce type d’identifiant universel comme le seul véritable « disque d’or ». Dans la gestion des données scientifiques comme en bibliothéconomie, ce concept est sous-estimé. Beaucoup de problèmes dans les grandes organisations auraient pu être résolus avec une meilleure conception des identifiants.
    Lectures associées : Identifiers Deep Dive, Trible Structure

    • L’identité d’une entité peut aussi être définie de manière intrinsèque (intrinsic). Pourquoi pas un contrat de cohérence (consistency contract) ?

  • Je suis en train de lire vers la page 281 de The Galaxy, and the Ground Within de Becky Chambers.
    Exemple de message dans le livre :

    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

    J’adore vraiment cette série. Je trouve fascinant que cet univers multi-espèces utilise un système d’adressage par chemins centralement convenu

    • Dans un esprit similaire, je recommande A Fire Upon The Deep de Vernor Vinge. La façon dont l’étiquetage des communications intergalactiques y est traité est intéressante
    • La scène où ils redoutent le concept de fromage m’a particulièrement marqué. Le deuxième livre de la série, A Closed and Common Orbit, était le meilleur

  • J’ai récemment découvert les Snowflake ID. Ils sont utilisés par Twitter, Discord, Instagram, Mastodon, etc. C’est une façon de réduire la taille des ID en combinant horodatage + aléa, et je trouve dommage que l’article ne les mentionne pas.
    Voir le wiki Snowflake ID et la vidéo de Tom Scott.
    En remplaçant certains bits de l’horodatage Snowflake par de l’aléa, on pourrait sans doute générer 4 milliards d’ID par seconde

    • En réalité, Snowflake a une structure presque identique à UUID v1. Il fait simplement deux fois moins de taille
    • Dans la même veine, il y a aussi DRUUID
    • Mais il est pratiquement impossible que l’univers entier se mette d’accord sur une seule horloge
    • Cette approche ressemble aussi à un BSON ID

  • Je me demande s’il serait possible de fabriquer des ID à partir de phénomènes observables. Grâce à des propriétés différenciées par le temps et la distance, l’unicité pourrait peut-être être garantie. Par exemple, le motif de lumière stellaire à un instant donné ne peut être vu que par une seule personne. C’est un peu comme utiliser du bruit comme source d’entropie, à la manière d’une lampe à lave. Si l’on pouvait définir un repère de coordonnées à l’échelle de l’univers, une combinaison temps local + x + y + z + salt pourrait peut-être produire un ID unique

  • L’approche par UUID aléatoires est bien meilleure du point de vue de la durée de vie. Le nombre d’appareils pouvant fonctionner simultanément est limité et, contrairement aux UUID en arbre, on peut réutiliser les ID quand les appareils sont mis au rebut. En pratique, un algorithme hybride combinant une racine basée sur la localisation + des bits aléatoires en suffixe serait probablement le plus réaliste