Aller au contenu
Financial Context Wiki

Accumulateurs cryptographiques

Un guide des accumulateurs cryptographiques axé sur la vérification, couvrant les conceptions fondées sur RSA et le hachage, les témoins d'appartenance et de non-appartenance, les mises à jour dynamiques, les usages dans les chaînes de blocs et les risques opérationnels.

Mis à jour

À des fins éducatives uniquement ; ceci ne constitue ni un conseil en investissement ni un conseil de mise en œuvre cryptographique. Une preuve d’accumulateur authentifie une affirmation par rapport à un engagement donné, et non les données sous-jacentes, l’état du consensus ou la disponibilité des données.

Réponse directe

Un accumulateur cryptographique engage un ensemble au moyen d’une valeur courte et permet à un vérificateur de contrôler, à l’aide d’un témoin concis, qu’un élément appartient à l’ensemble engagé. Certains schémas prouvent également la non-appartenance. Le vérificateur a besoin de la valeur de l’accumulateur, de l’élément, du témoin et des paramètres publics du schéma, mais pas de tous les autres éléments de l’ensemble.

Un accumulateur est statique s’il doit être reconstruit après une modification de l’ensemble, dynamique si des ajouts ou des suppressions permettent de mettre à jour efficacement l’accumulateur et les témoins, et universel s’il prend en charge les preuves d’appartenance et de non-appartenance. Ces qualificatifs décrivent des capacités distinctes ; un schéma dynamique n’est pas nécessairement universel.

Les chaînes de blocs peuvent engager des transactions, des sorties non dépensées, des comptes, des validateurs ou des registres de révocation. Un engagement plus petit peut réduire l’état conservé par certains participants, mais le système doit toujours distribuer les données sous-jacentes et les témoins à jour, authentifier les mises à jour, gérer les réorganisations de la chaîne et définir qui peut modifier l’ensemble.

Fonctionnement

  1. Définir précisément l’ensemble. Il faut préciser l’encodage canonique des éléments, le traitement des doublons, les règles d’ordre le cas échéant, la séparation des domaines et la version exacte de l’engagement. Une preuve portant sur un encodage ou une racine d’état ne dit rien au sujet d’un autre.

  2. Exécuter la configuration du schéma. Un accumulateur fondé sur le hachage peut n’utiliser que des paramètres de hachage publics. Un accumulateur RSA emploie un groupe d’ordre inconnu, généralement dérivé d’un module RSA N ; la sécurité exige que les parties non autorisées ne puissent pas exploiter sa factorisation. D’autres schémas peuvent utiliser des couplages, des groupes de classes, des réseaux euclidiens ou des paramètres publics supplémentaires assortis d’hypothèses de confiance différentes.

  3. Représenter les éléments dans la structure algébrique. Dans une construction RSA simplifiée, chaque élément x_i est associé de manière déterministe à un représentant premier distinct p_i. Avec la base g, l’accumulateur est :

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. Créer un témoin d’appartenance. Pour l’élément représenté par p_i, son facteur est omis de l’exposant :

    w_i = g^(product of p_j for all j != i) mod N

  5. Vérifier par rapport à l’accumulateur exact. Le vérificateur contrôle les entrées canoniques et évalue :

    w_i^(p_i) mod N = A

    Selon l’hypothèse de sécurité du schéma, produire cette égalité pour un élément extérieur à l’ensemble accumulé doit être irréalisable. L’égalité n’établit pas que l’élément lui-même est véridique ou autorisé.

  6. Traiter séparément les mises à jour et la non-appartenance. Les schémas dynamiques définissent comment les ajouts et les suppressions modifient A et comment les témoins concernés sont actualisés. Les schémas universels ajoutent un témoin de non-appartenance et un algorithme de vérification distincts. Les implémentations doivent rejeter les témoins obsolètes et les mises à jour liées à un état différent.

  7. Comparer les structures fondées sur le hachage selon leurs coûts réels. Un arbre de Merkle est un accumulateur fondé sur le hachage au sens large : sa racine est courte, tandis qu’une preuve d’appartenance contient les hachages frères le long d’un chemin et croît donc de manière logarithmique avec le nombre de feuilles. Les schémas de type RSA peuvent offrir des témoins individuels de taille constante, mais la génération des preuves, la maintenance des témoins, la configuration et les calculs ont des coûts différents.

Exemples pratiques

  • Taille d’une preuve de Merkle. Un arbre de Merkle binaire équilibré comportant 1,048,576 = 2^20 feuilles nécessite 20 hachages frères pour un chemin d’inclusion. Avec des hachages de 32 octets, cela représente 20 * 32 = 640 bytes avant les données de la feuille, les bits de position et le surcoût de sérialisation. La racine reste longue de 32 octets.
  • Une taille constante n’implique pas un travail constant. Dans la construction RSA simplifiée, A et chaque w_i restent un unique élément du groupe à mesure que l’ensemble grandit. L’exposant produit, la génération des représentants premiers, les mises à jour par lots et la distribution des témoins actualisés peuvent néanmoins exiger des calculs ou des données auxiliaires considérables.
  • Un accumulateur d’UTXO modifie la répartition du stockage. Un nœud à état compact peut conserver un accumulateur de sorties non dépensées et valider une dépense uniquement lorsqu’il reçoit la sortie accompagnée d’une preuve d’appartenance à jour. D’autres participants doivent toujours conserver suffisamment d’état pour produire ces preuves, et les mises à jour doivent retirer les sorties dépensées et ajouter les sorties nouvellement créées.
  • La révocation obéit à la même limite. Le titulaire d’un justificatif peut prouver qu’un identifiant figure toujours dans un accumulateur de membres actifs, ou utiliser une conception universelle pour prouver qu’il est absent d’un ensemble de révocation. La preuve authentifie l’ensemble engagé par l’émetteur ; elle ne prouve pas que celui-ci a appliqué une politique de révocation juste ou correcte.

Risques

  • Utiliser des encodages d’éléments ambigus ou non canoniques, permettant au même élément logique d’être représenté différemment.
  • Associer incorrectement les éléments à des représentants premiers ou omettre les contrôles de collision exigés par le schéma.
  • Faire confiance à un module RSA dont la factorisation pourrait être connue de la partie chargée de la configuration ou d’un attaquant.
  • Considérer une cérémonie de configuration multipartite comme sûre sans vérifier sa transcription, les hypothèses relatives aux participants et la liaison des paramètres.
  • Autoriser un administrateur à remplacer les paramètres publics ou les versions de l’accumulateur sans règles de migration authentifiées.
  • Vérifier un témoin par rapport à une valeur d’accumulateur obsolète, non finalisée ou choisie par un attaquant.
  • Appliquer un ajout, une suppression ou une mise à jour de témoin provenant du mauvais bloc, embranchement, époque ou de la mauvaise version de l’ensemble.
  • Supposer qu’un témoin d’appartenance prouve également la validité, la propriété, l’autorisation ou la valeur économique de l’élément.
  • Supposer qu’un engagement court rend l’ensemble sous-jacent disponible ou récupérable.
  • Perdre les données ou le service nécessaires pour construire les témoins à jour, rendant un état valide inutilisable.
  • Omettre la prise en charge de la non-appartenance alors qu’une application dépend implicitement de preuves d’absence.
  • Confondre un chemin de Merkle, un témoin RSA, une ouverture polynomiale et une preuve de validité comme s’il s’agissait d’objets interchangeables.
  • Ignorer le coût des suppressions, le trafic d’actualisation des témoins, la latence de génération des preuves ou les entrées visant un déni de service.
  • Ne pas lier les preuves à un protocole, une chaîne, un contrat, une racine d’état, un domaine et une version de sérialisation.
  • S’appuyer sur une seule implémentation non auditée ou sur une arithmétique personnalisée sans vecteurs de test indépendants.
  • Supposer que la sécurité classique de RSA, des couplages ou du logarithme discret résistera à un ordinateur quantique d’une puissance cryptographique pertinente.

Idées reçues

  • L’accumulateur contient une copie compressée de l’ensemble. Il s’agit d’un engagement contraignant, et non d’une archive réversible.
  • Tous les accumulateurs prouvent l’absence. La non-appartenance nécessite un schéma conçu et vérifié pour cette capacité.
  • Un témoin de taille constante entraîne un coût total constant. La configuration, la génération des preuves, les mises à jour, le stockage et la distribution des témoins restent des coûts distincts.
  • Sans état signifie que personne ne stocke d’état. Certains acteurs doivent conserver ou reconstruire suffisamment de données pour créer les éléments, les mises à jour et les témoins.
  • Une preuve valide rend vrai l’élément engagé. Elle ne fait que relier l’élément à un engagement authentifié selon des hypothèses données.
  • Les arbres de Merkle et les accumulateurs RSA ont le même profil de confiance et de performance. Ils servent tous deux à engager un ensemble, mais reposent sur des hypothèses, des tailles de preuve, des procédures de mise à jour et des modes de défaillance différents.

Sujets connexes

Sources

Navigation

Rechercher dans le wiki...