Comprendre MuSig2 (schéma d’agrégation de signatures)

by
Jean-Luc
My articles My books
Follow on:

Synthèse d’une présentation de @TheoPantamis lors d’un Space Twitter technique consacré à MuSiG2.

MuSig est un schéma d’agrégation de signatures semi-interactif. Ce que permet MuSig c’est de représenter une transaction à signatures multiples par une seule clé publique. Avec MuSig, tous les multisigs basés sur Taproot apparaitront comme une dépense simple. Le mutisig n’aura pas à donner toute une liste de clés publiques et il n’y aura pas d’opcode checkmultisig à faire.

La première conséquence c’est que les scripts sont plus courts car il n’y a qu’une signature et une clé publique. L’autre avantage c’est que ça fait sauter les limites du multisig actuel. Jusque là, quand on utilisait des scripts classiques sans les signatures de Schnorr, un multisig nécessitait d’écrire toutes les clés publiques des différents signataires, de donner le nombre de signatures valides pour pouvoir dépenser les fonds et d’avoir une signature qui représente le quorum voulu (pour faire autrement, il fallait utiliser des techniques compliquées sur ECDSA qui n’ont jamais vraiment été adoptées parce que très complexes à coder). Comme on devait écrire toutes les clés et qu’il fallait autant de signatures qu’il y a de signataires, c’était donc très lourd. En conséquence on était limité par la taille maximale des scripts dans Bitcoin. En effet, au-delà d’une certaine taille, une transaction n’est plus considérée comme standard et ne sera pas diffusée dans le réseau. Le seul moyen de la faire passer c’est de l’envoyer directement à mineur qui accepte de l’intégrer, c’est donc très restrictif. Cette limite saute complètement avec MuSig parce qu’on va pouvoir agréger les signatures grâce aux signatures de Schnorr.

Les algorithmes de signature comme ECDSA ou Schnorr reposent sur la propriété suivante : quand on fait la somme de deux clés privées, la clé publique associée à cette somme est égale à la somme des clés publiques de chaque clé privée de départ. Cette propriété est vraie tout le temps. L’avantage de Schnorr sur ECDSA, c’est que cette propriété est également vraie avec les signatures. C’est-à-dire que si on a une signature pour un même message avec deux clés publiques différentes, en faisant la somme de ces signatures on obtient une signature pour la somme des clés publiques considérées. C’est ça l’élément essentiel qui va être utilisé dans MuSig pour pouvoir réunir les signatures en une seule.

L’histoire de MuSig est assez longue. Une première version de MuSig a été proposée en 2018 par Peter Wuille et Yannick Seurin, cryptographe de l’ANSSI. L’idée centrale c’est qu’on ne peut pas se contenter de faire la somme des clés publiques des différents signataires. On ne peut pas simplement dire : la clé publique du multisig, c’est juste la somme des clés publiques de chaque personne et il suffit ensuite d’additionner les signatures et tout va bien se passer. Un participant malintentionné pourrait en effet attendre de connaitre les clés publiques des autres et ne pas donner sa vraie clé publique, mais une clé qui dépend des clés publiques des autres participants pour faire en sorte qu’à la fin ce soit uniquement sa clé privée qui permette de signer.

Imaginons, par exemple, que je veuille ouvrir un canal avec quelqu’un. Cette personne me donne sa clé publique et je prends une clé publique dont j’ai la clé privée mais, à la place de lui donner cette clé publique, je lui renvoie ma clé publique moins sa clé publique à lui. Si on fait la somme des deux, on obtient ma clé publique. La personne avec qui j’ouvre le canal pense qu’on a construit une clé publique pour laquelle nos deux signatures sont nécessaires pour dépenser les fonds, mais ce n’est pas le cas, ma signature suffit.

Pour éviter ce type d’attaque, la première chose que MuSig a introduite c’est de dire qu’à la place de faire une simple somme, on va faire une combinaison linéaire, c’est-à-dire une somme avec des coefficients qui vont être dépendants de toutes les clés publiques des participants, ce qui fait qu’il n’est pas possible de faire la manipulation présentée précédemment.

L’autre problème de MuSig1 c’est celui des nonces. Les signatures dans ECDSA ou dans Schnorr ont toutes un nonce, un nombre aléatoire qu’on va utiliser une seule fois pour la signature. Le problème c’est qu’on peut choisir les nonces et donc les manipuler de la même façon qu’on peut manipuler les clés publiques et leur somme. Pour éviter cela, la première version de MuSig nécessitait un « commit and reveal ». Chaque participant devait d’abord envoyer aux autres le hachage de son nonce. Il fallait attendre d’avoir reçu les hachages de tout le monde avant de partager les vrais nonces, c’est à dire des points qu’on a tiré aléatoirement sur la courbe mais dont chacun connait la clé privée. Ensuite il fallait vérifier que les nonces correspondaient bien aux hachages reçus précédemment et enfin seulement on pouvait faire la signature avec la certitude que les nonces n’avaient pas été manipulés.

Le premier papier de MuSig avait oublié que les nonces pouvaient être manipulés et n’indiquait pas qu’il fallait d’abord partager les nonces sous forme de hachage. Cette erreur fut facile à corriger en ajoutant cette phase de partage des hachages des nonces avant la signature, mais le problème c’est que ça ajoutait une interaction. Une transaction multisignature nécessitait une première interaction pour partager le hachage des nonces, une autre pour le partage des nonces et une troisième pour l’échange des signature des clés publiques. Ca veut dire trois interactions entre les cosignataires. C’est un problème qui peut paraitre mineur, mais pour un cryptographe ça rend le schéma de signature beaucoup moins intéressant parce que la gestion des sessions de signature va être plus lourde. Il va notamment falloir prévoir ce qui se passe si un des participants se déconnecte ou s’il n’a pas envoyé le bon nonce. Avant MuSig2, plusieurs solutions ont été proposées pour résoudre ce problème, mais, trop chères en temps de calcul, elles ont été abandonnées.

MuSig 2 réalise un tour de force en permettant de se passer de la phase du partage du hachage des nonces. Sa solution trouvée c’est d’envoyer deux ou quatre nonces et non pas simplement un seul, puis de faire une combinaison de ces nonces. Cette combinaison dépendra en outre des nonces des autres, de la clé publique et du message et on ne pourra pas choisir son nonce à l’avance. Cela rend toute manipulation impossible.

MuSig2 reste un schéma de signature interactif. Il faut collaborer avec les autres personnes. Mais l’avantage c’est qu’il n’y a que deux interactions : la première pour partager les nonces et la seconde pour partager sa partie de la signature. On n’a pas besoin de donner le message pour pouvoir donner les nonces à la première étape, et donc ces nonces peuvent être pré-calculés. On peut, par exemple, les dériver d’une Xpub pour éliminer l’étape de partage des nonces et n’envoyer que des signatures. Puisque les participants se sont mis d’accord en amont sur les nonces qu’ils vont utiliser, une fois qu’on a le message, il ne reste plus qu’à s’envoyer les signatures partielles pour pouvoir créer la signature globale.

Et maintenant ?

Les signatures de Schnorr ont été intégrées dans Bitcoin avec Taproot en novembre 2021. L’effort qu’il reste à faire est un travail de spécification pour débloquer toutes les possibilités offertes par Taproot. Taproot ne s’est pas encore, par exemple, traduit par des avancées sur le Lightning Network, parce que justement on attendait d’avoir MuSig2 pour pouvoir masquer toutes les transactions de création et de fermeture des canaux avec un multisig qui n’apparait pas comme tel dans la Timechain. MuSig permettra également de réduire la taille des messages d’annonce des canaux, puisque les signatures sont agrégées.

MuSig permettra en outre de gérer ce qu’on appelle le « tweaking » de clés pubiques. Ca veut dire qu’on peut ajouter des modifications à la clé publique finale pour faire des choses qui ressemblent un peu à ce qu’on fait dans Taproot lorsqu’on cache des scripts dans les clé publiques.

A terme tous les multisigs sur Taproot seront des signatures simples. On ne distinguera plus les multisigs.

Ressources :
– MuSig2 expliqué par Tim Ruffing (vidéo)
– « MuSig2: Simple Two-Round Schnorr Multisignatures » by Jonas Nick, Tim Ruffing
– BIP : https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki