Des identifiants uniques à l’échelle cosmique

• 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