Curve Trees, Helios et Selene

Un arbre de Merkle avec des points au lieu de hachages, où prouver un chemin ne prend que quelques kilo-octets

Rappel sur les arbres de Merkle

Un arbre de Merkle hache les données par paires (ou par groupes), puis hache les hachages, jusqu’à une racine unique. Pour prouver qu’un élément est dans l’arbre, on montre le chemin — les nœuds voisins à chaque niveau. Le chemin a une longueur de log n.

Mais nous devons prouver le chemin à divulgation nulle de connaissance — sans montrer ni la feuille ni les voisins. Cela implique d’encoder « le calcul d’un hachage » dans un circuit arithmétique et de prouver ce circuit. Les hachages ordinaires (Keccak, SHA) sont très coûteux dans de tels circuits : des dizaines de milliers de contraintes par hachage.

L’idée des Curve Trees

Utiliser un engagement de Pedersen vectoriel comme « hachage » :

C’est un bon hachage pour notre usage (trouver une collision est aussi difficile que le logarithme discret), et dans un circuit arithmétique il est presque gratuit — à condition que les nombres xᵢ soient des scalaires de la courbe sur laquelle vivent les Gᵢ.

Le problème : les enfants sont des points de la courbe E₁, donc leurs coordonnées sont des éléments du corps de base de E₁. Pour les utiliser comme scalaires, il faut une courbe E₂ dont le corps des scalaires est égal au corps de base de E₁. Au niveau suivant, c’est l’inverse. Une telle paire s’appelle un cycle de courbes.

Helios et Selene

Pour Monero, on a choisi un cycle particulier « ancré » à Ed25519 : les coordonnées des points d’Ed25519 vivent dans le corps F_p, p = 2²⁵⁵ − 19, et l’une des courbes du cycle (Selene) a exactement ce F_p comme corps des scalaires. Les feuilles (coordonnées de O, I, C sur Ed25519) peuvent donc être « hachées » directement sur Selene, puis les coordonnées des points de Selene sur Helios, et ainsi de suite, en alternance.

Les noms viennent des divinités grecques du Soleil (Hélios) et de la Lune (Séléné) : deux courbes qui « tournent » l’une autour de l’autre.

Comment le chemin est prouvé

Pour chaque niveau, le prouveur ne montre pas le point parent lui-même mais sa rerandomisation (le point plus un multiple aléatoire d’un autre générateur), et prouve dans un circuit sur la courbe correspondante :

1. « je connais les enfants, dont l’un est le point rerandomisé du niveau précédent » ;
2. « ces enfants, combinés aux générateurs, donnent le parent (rerandomisé) ».

Pour vérifier efficacement des opérations sur la courbe à l’intérieur du circuit, on utilise des diviseurs (la technique de Liam Eagen) : au lieu d’une multiplication scalaire pas à pas, on prouve une propriété d’une fonction rationnelle sur la courbe, ce qui est bien moins coûteux. Voir Generalized Bulletproofs et diviseurs.

Tous les niveaux sur une courbe sont prouvés par un seul Generalized Bulletproof, ceux sur l’autre — par un second. On obtient deux preuves dont la taille croît avec la profondeur de l’arbre, c’est-à-dire de façon logarithmique avec le nombre de sorties.

Mise à jour de l’arbre

Quand une sortie dépasse le verrouillage de 10 blocs, le nœud l’ajoute à l’arbre et recalcule le chemin jusqu’à la racine. Un engagement vectoriel se met à jour de façon incrémentale : ajouter un enfant revient à ajouter x·Gᵢ au parent, sans recalculer les autres. En cas de réorganisation de la chaîne, les modifications sont annulées.