Signatures en anneau

Comment prouver « je possède l’une de ces clés » sans dire laquelle

D’abord — une simple signature de Schnorr

Pour comprendre les anneaux, voyons d’abord comment prouver la connaissance d’une seule clé x pour P = x·G :

1. Le signataire choisit un α aléatoire et calcule α·G.
2. Il calcule le défi c = Hs(message ‖ α·G).
3. Il calcule la réponse s = α − c·x. La signature est (c, s).
4. Le vérificateur reconstitue s·G + c·P = (α − cx)·G + c·x·G = α·G et vérifie que Hs(message ‖ α·G) = c.

Sans connaître x, on ne peut pas trouver de s pour un c donné : c dépend de α·G, qui doit être fixé avant de connaître c.

L’idée de l’anneau : boucler la chaîne des défis

Nous avons maintenant n clés publiques P₀ … Pₙ₋₁ et ne connaissons la clé que d’une seule, disons Pπ. L’astuce : chaque défi est calculé à partir du maillon précédent, et la chaîne se referme en anneau.

1. À la position π de la vraie clé, on prend un α aléatoire et on calcule le défi suivant : c_{π+1} = Hs(m ‖ α·G).
2. Pour chaque clé suivante (étrangère), on choisit un sᵢ aléatoire et on calcule c_{i+1} = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ). On fait le tour de l’anneau.
3. On revient à π en connaissant désormais c_π. Pour que l’anneau se referme, il faut s_π·G + c_π·P_π = α·G, c’est-à-dire s_π = α − c_π·x. Cela ne peut être calculé qu’en connaissant x.
4. Signature : (c₀, s₀, s₁, …, sₙ₋₁).

Le vérificateur part de c₀, parcourt chaque maillon avec la même formule et vérifie qu’il revient au même c₀. Tous les maillons se ressemblent — impossible de dire, à partir de la signature, où la « fermeture » a eu lieu.

Liabilité : LSAG

Une simple signature en anneau n’empêche pas de dépenser deux fois la même sortie dans des anneaux différents. Monero utilise donc une signature liable (linkable) : le signataire publie une key image I = x·Hp(P_π) et prouve en plus, à chaque maillon, que le même x relie I et Hp(Pᵢ) :

Deux utilisations de la même clé donnent le même I — et le réseau rejette la seconde dépense.

MLSAG → CLSAG

Dans RingCT, il faut prouver non pas une mais deux affirmations par membre de l’anneau : la connaissance de la clé de la sortie, et que la différence des engagements est un engagement à zéro (voir RingCT). Au début (2017), on le faisait avec MLSAG — en gros deux anneaux collés ensemble : deux valeurs s par membre de l’anneau.

En octobre 2020 (hard fork v13), il a été remplacé par CLSAG (Concise LSAG) : les deux clés d’une position sont fusionnées en une seule par une combinaison linéaire aléatoire à coefficients issus de hachages. Un seul s par membre de l’anneau. La signature est devenue environ 25 % plus petite et plus rapide à vérifier.

Historique de la taille des anneaux

Pourquoi fixe ? Si chacun choisissait la sienne, une taille d’anneau non standard trahirait le portefeuille utilisé.

Pourquoi pas 1000 ?

La taille et le temps de vérification de CLSAG croissent linéairement avec la taille de l’anneau. Un anneau de 1000 membres, c’est ~32 Ko par entrée et une synchronisation des nœuds des dizaines de fois plus lente. Des schémas de taille logarithmique (Triptych, Arcturus, Seraphis) ont été étudiés, mais Monero a finalement choisi l’option radicale — FCMP++, où l’« anneau » est toute la blockchain.