Technique › FCMP++

Rerandomisation des entrées

Comment dépenser une sortie de l’arbre sans montrer laquelle

En bref

Dans FCMP++, une entrée de transaction n’est pas une référence à une sortie mais une copie « repeinte » de celle-ci : un multiple aléatoire d’un générateur distinct est ajouté à chaque point de la sortie. Les points obtenus sont indiscernables de points aléatoires, mais celui qui dépense connaît la « peinture » et peut prouver : (1) qu’en la retirant on obtient une certaine feuille de l’arbre, et (2) qu’il connaît la clé de cette feuille.

Pourquoi rerandomiser

Une preuve d’appartenance prouve l’affirmation « le point X est une feuille de l’arbre ». Si l’on publie la sortie O elle-même, il n’y a plus rien à cacher : tout le monde voit quelle sortie est dépensée. Si l’on ne publie rien, il n’y a rien à quoi rattacher la key image et l’engagement du montant. Il faut un juste milieu : publier quelque chose de mathématiquement lié à la sortie, dont seul celui qui dépense voit le lien.

Cette astuce, c’est la rerandomisation. Dans RingCT, une astuce similaire était la pseudo-sortie C̃ : le même engagement de montant, mais avec un nouveau masque. FCMP++ applique la même idée à chaque partie de la sortie.

De quoi se compose une feuille

leaf = ( O.x, I.x, C.x ) coordonnées x de trois points Ed25519 : la clé de sortie O, le générateur de key image I = Hp(O), l’engagement C

O et C proviennent directement de la sortie sur la chaîne ; I est calculé par le nœud lorsqu’il ajoute la sortie à l’arbre. Seules les coordonnées (des nombres) entrent dans l’arbre, pas les points eux-mêmes — ce qui les rend plus faciles à « hacher » au niveau suivant (voir Curve Trees).

Les formules de rerandomisation

Celui qui dépense choisit quatre scalaires aléatoires r_o, r_i, r_r_i, r_c et publie :

Publié	Formule	Ce que cela cache
Õ	`O + r_o·T`	quelle clé de sortie est dépensée
Ĩ	`I + r_i·U`	le générateur de key image de cette sortie
R	`r_i·V + r_r_i·T`	un engagement sur `r_i` — nécessaire pour relier Ĩ à la key image
C̃	`C + r_c·G`	quel engagement de montant est dépensé (comme la pseudo-sortie de RingCT)

T, U, V sont des générateurs fixes obtenus par hachage vers un point ; personne ne connaît leurs logarithmes par rapport à G ni les uns par rapport aux autres. C’est essentiel : si quelqu’un connaissait T = t·G, il pourrait « repeindre » une composante en une autre.

Ce qui est prouvé sur ces points

La transaction contient deux preuves qui se répartissent le travail :

La preuve d’appartenance (dans un circuit arithmétique sur Helios/Selene) prouve : il existe dans l’arbre de racine ρ une feuille (O, I, C), et il existe r_o, r_i, r_r_i, r_c tels que les Õ, Ĩ, R, C̃ publiés respectent les formules ci-dessus.
SA+L (hors du circuit, sur Ed25519) prouve : celui qui dépense connaît x, y tels que Õ = x·G + (y + r_o)·T, et la key image est L = x·I — en utilisant uniquement les Õ, Ĩ, R publiés.

Notez que la preuve d’appartenance ne sait rien des clés de dépense, et que SA+L ne sait rien de l’arbre. Cette séparation permet par exemple de déléguer la preuve d’appartenance à un autre appareil sans lui donner le droit de dépenser.

Pourquoi c’est sûr

Dissimulation : r_o·T est un point aléatoire du sous-groupe, donc Õ est uniformément distribué quelle que soit l’allure de O. Comparer Õ aux sorties ne sert à rien — l’outil le montre.
Pas de fausses feuilles : pour « retirer la peinture » d’un point inventé et tomber sur une vraie feuille, il faudrait résoudre un logarithme discret entre générateurs.
Pas d’échange de montant : l’équilibre est vérifié sur C̃, et la preuve d’appartenance garantit que C̃ ne diffère du vrai C de la feuille que d’un multiple de G — le montant est donc le même.
Pas de double dépense : L = x·I ne dépend que de la sortie, pas de r ; une seconde dépense donne le même L.