Generalized Bulletproofs et diviseurs

Ce sur quoi repose la preuve du chemin dans l’arbre — sans trusted setup

Ce qu’est un « circuit arithmétique »

Tout calcul peut être décomposé en étapes élémentaires « multiplier deux nombres » et « additionner avec des coefficients » dans un corps fini. Un ensemble de telles étapes forme un circuit arithmétique. Une preuve à divulgation nulle de connaissance montre « je connais des valeurs pour tous les fils du circuit telles que toutes les équations sont satisfaites » sans révéler ces valeurs.

Dans Bulletproofs, le circuit est simple et fixe : « ces 64 nombres sont des bits, et leur somme donne le montant ». Dans FCMP++, il est plus complexe : à chaque niveau de l’arbre, il faut vérifier que l’enfant choisi fait partie des enfants du nœud et que le nœud est correctement calculé à partir d’eux.

Generalized Bulletproofs

Les Bulletproofs ordinaires prennent en entrée des engagements de Pedersen séparés. Les Generalized Bulletproofs (Eagen, Kamp, Parker et al.) permettent d’injecter dans le circuit des engagements vectoriels — un seul point fixe de nombreux nombres à la fois. C’est exactement ce qu’il faut pour l’arbre : le « hachage » d’un nœud est un engagement vectoriel sur les coordonnées de ses enfants (voir Curve Trees). Le circuit reçoit le nœud en entrée et peut raisonner sur son contenu.

Mêmes propriétés que Bulletproofs :

• pas de trusted setup ;
• la taille de la preuve croît de façon logarithmique avec la taille du circuit ;
• la vérification est linéaire en la taille du circuit mais se prête bien au traitement par lots — vérifier de nombreuses preuves ensemble coûte moins cher que une par une.

Le problème : la multiplication scalaire dans un circuit

La rerandomisation exige de vérifier dans le circuit quelque chose comme Õ = O + r_o·T. Multiplier « de front » un point par un scalaire de 255 bits, ce sont des centaines de doublements et d’additions de points, chacun nécessitant plusieurs multiplications dans le corps. Cela représente des milliers de contraintes par opération, et la preuve serait énorme.

Les diviseurs : vérifier au lieu de calculer

L’idée de Liam Eagen (« Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity ») : pour s’assurer que des points P₁ … Pₙ ont une somme nulle, il n’est pas nécessaire de les additionner. Il suffit de présenter une fonction rationnelle f sur la courbe dont les zéros sont exactement ces points (son diviseur) et de vérifier une seule identité algébrique en un point aléatoire (un défi du vérificateur).

La multiplication r·T s’écrit comme une somme Σ bᵢ·(2ⁱ·T) sur les bits de r, c’est-à-dire comme une somme de points — et se vérifie avec un seul diviseur. Le nombre de contraintes baisse d’environ un ordre de grandeur.

Deux circuits — deux courbes

Les niveaux de l’arbre alternent entre Selene et Helios. L’arithmétique de chaque niveau est naturelle dans le corps de l’une des courbes, si bien que la preuve d’appartenance se compose de deux Generalized Bulletproofs : l’un sur Selene (les niveaux Selene et la vérification de la rerandomisation de la feuille, dont les coordonnées sont des éléments du corps d’Ed25519), l’autre sur Helios. Ils sont reliés par des nœuds rerandomisés communs.

Taille et coût

La taille de la preuve dépend de la profondeur de l’arbre et de la largeur des nœuds. Avec des centaines de millions de sorties et des nœuds de plusieurs dizaines d’enfants, la profondeur n’est que de quelques niveaux. En gros, une entrée FCMP++ occupe plusieurs kilo-octets, et sa vérification coûte un ordre de grandeur de plus que CLSAG ; les développeurs continuent d’optimiser les deux (vérification par lots, preuves multi-entrées). Les chiffres exacts figurent dans les rapports de benchmarks de la version.