Ce que les preuves d’appartenance à chaîne complète nous apprennent

Les systèmes de confidentialité qui cachent un acteur parmi d'autres sont limités par le nombre de ces autres. Une signature de cercle cache l'entrée réelle parmi un nombre fixe de leurres, et la taille de ce cercle est bornée par le coût de la signature. Un petit ensemble est une garantie faible, et elle se dégrade encore sous analyse statistique sur de nombreuses transactions.

L'amélioration évidente consiste à prendre tout comme ensemble : prouver l'appartenance à l'historique entier des sorties plutôt qu'à un échantillon de seize. Si cela n'a pas été fait plus tôt, c'est une question de coût. Une preuve naïve sur des millions d'éléments ne s'attache pas à chaque transaction.

La construction qui a rendu cela tractable bâtit l'ensemble comme un arbre d'engagements et prouve un chemin à travers lui en connaissance nulle, couche par couche. La technique est connue dans la littérature sous le nom d'arbres de courbes.

L'astuce d'efficacité consiste à alterner entre deux courbes elliptiques arrangées de sorte que le corps des scalaires de l'une soit le corps de base de l'autre. Une arithmétique coûteuse à exprimer dans une preuve sur une courbe devient native dans l'autre, si bien que chaque couche de l'arbre est prouvée sur la courbe où ses opérations sont bon marché, et la preuve passe de l'une à l'autre. Il en résulte une preuve d'appartenance dont la taille et le coût de vérification croissent avec la profondeur de l'arbre plutôt qu'avec la taille de l'ensemble.

À côté de cela se trouvent des travaux sur la preuve efficace de relations de logarithme discret, et sur la généralisation de l'argument Bulletproofs aux formes dont ces preuves ont besoin. Le résumé pour un ingénieur : la primitive a cessé d'être théorique.

Dès qu'on sait prouver l'appartenance à un grand ensemble engagé pour un coût raisonnable, toute une famille de problèmes se ramène à une seule forme.

Chacun de ces cas est aujourd'hui résolu en remettant un identifiant à un vérificateur qui en sait alors plus qu'il n'en a besoin. La formulation par preuve d'appartenance sépare la question « y avez-vous droit » de la question « qui êtes-vous », et seule la première doit recevoir une réponse.

• L'éligibilité au vote, sans révéler quel électeur
• La possession d'un titre ou d'une qualification, sans révéler le titulaire
• L'appartenance à un ensemble sanctionné ou exclu, ou la preuve d'en être absent
• Le droit à une prestation, sans divulguer son identité à celui qui l'accorde
• Un âge ou un attribut de seuil, prouvé contre un justificatif émis plutôt que par un scan de document

Une preuve d'appartenance seule autorise une réutilisation illimitée, aussi les systèmes l'accompagnent-ils d'un annulateur : une valeur dérivée de manière déterministe du justificatif secret, publiée quand le droit est exercé, qui permet à tous de voir que ce droit a été utilisé sans apprendre par qui.

La subtilité est la portée. Un annulateur dérivé du seul justificatif chaîne tous les usages dans tous les contextes, ce qui reconstruit une identité pseudonyme et détruit une bonne part du gain. Lier l'annulateur au contexte, pour que le même justificatif produise des annulateurs non chaînables dans des scrutins ou des services différents, est ce qui sépare un système de confidentialité d'un système de pseudonymes.

C'est le détail le plus souvent raté dans les conceptions dérivées, et ce n'est pas une faiblesse cryptographique. C'est une décision de spécification.

La génération de preuve est lourde comparée à une signature, et lourde sur un appareil contraint peut vouloir dire des secondes ou un prouveur délégué, ce qui réintroduit une partie prenante à considérer. La vérification est moins coûteuse mais pas gratuite, et elle se multiplie par le nombre de vérificateurs.

Il y a aussi le problème de la maintenance de l'ensemble. L'arbre doit être construit, mis à jour et publié, et chaque participant a besoin d'une vue cohérente de sa racine. Dans une chaîne de blocs, cette infrastructure existe déjà. En dehors, elle doit être conçue, et cette conception porte des questions de gouvernance sur qui publie la racine et comment se règle un désaccord.

Ce sont ces questions-là qui décident si une proposition est déployable, et ce sont des questions de systèmes plutôt que de cryptographie.

Les primitives cryptographiques atteignent les systèmes grand public des années après être devenues praticables, et généralement par l'intermédiaire de gens qui les ont comprises alors qu'elles étaient encore malcommodes. Les preuves d'appartenance à grande échelle ressemblent à l'une de ces primitives.

La raison de lire les travaux Monero en particulier, c'est qu'ils sont construits en conditions adverses, avec de vraies contraintes de taille de preuve, de coût de vérification et de compatibilité. La recherche écrite sous ces contraintes se transpose généralement mieux que celle écrite sans.