Passer au contenu

Un bref guide pour comprendre les signatures de Schnorr

Avant toute chose, une compréhension même superficielle des signatures normales est requise. Nous vous renvoyons à ces quelques articles :

  1. Qu’est-ce qu’une clé publique? 
  2. Qu’est-ce qu’une clé privée ?
  3. Qu’est-ce que les signatures multiples ?
  4. Comment utiliser les signatures multiples ?
  5. Comment créer une adresse à signatures multiples ?
  6. Qu’est-ce qu’un wallet à signatures multiples ?

Pour résumer brièvement : si vous voulez dépenser des bitcoins depuis une adresse, il vous faut prouver que vous êtes le propriétaire de la clé privée associée à cette adresse. Or il vous faut prouver que vous en êtes le propriétaire sans pour autant révéler votre clé privée – au risque de vous faire voler vos fonds. C’est pour cela qu’il existe les signatures cryptographiques.

Les signatures sont créées à partir d’une équation qui utilisation les données de la transaction et de la clé privée. Le propriétaire de la clé privée peut signer une transaction et dépenser son argent sans se soucier des voleurs, car la clé privée n’est pas révélée et la signature n’est utilisée que pour cette transaction.

Définition succincte

Une signature de Schnorr tire son nom de son inventeur, Claus-Peter Schnorr. En tant que signature, elle est une série d’opérations mathématiques – d’algorithmes – qui permettent de faire le lien entre la clé privée, la clé publique et la signature de la transaction. Elle est considérée par les experts dans le domaine comme la meilleure signature cryptographique car elle n’est absolument pas malléable ; elle offre un niveau conséquent de justesse ; et relativement rapide à vérifier ;  et permet de créer des signatures à partir de plusieurs adresses (les multisigs, ou signatures multiples).

Récapitulation sur les transactions

Le problème – pour ainsi dire – de Bitcoin est que son réseau est passablement lent. Une transaction met 10 minutes environ à être entièrement vérifiée, sinon plus suivant les frais de transaction. Cela est en partie dû à la taille des transactions. Or la taille des transactions ne dépend pas du montant de la transaction mais de la quantité de signatures nécessaires pour envoyer la transaction.

En effet, si vous envoyez plusieurs transactions à un seul destinataire à partir d’une même interface, chaque transaction sera signée individuellement et au final, vous aurez dépensé plus d’argent et aurez demandé plus de place sur la bande-passante que pour une seule transaction avec une seule signature. Ce cas de figure aura l’air étrange pour le néophyte mais il ne l’est pas du tout. Au contraire, il est extrêmement courant et se produit à deux occasions bien distinctes.

Premier cas de figure. Vous effectuez une transaction à signatures multiples. Les multisigs Bitcoin sont du type M-de-N. C’est-à-dire que n’importe quelle combinaison de signatures valides parmi N (~nombre de signataires) permet d’envoyer la transaction, aussi longtemps qu’un minimum de M signatures sont présentes. Une transaction envoyée avec plusieurs signatures est bien plus lourde qu’une transaction individuelle – mais elle est plus sûre. Elle coûte donc plus cher et prend plus de place sur la Blockchain.

Deuxième cas de figure. Lorsque vous effectuez une transaction, vous dépensez un certain nombre de BTC et en récupérez un certain nombre de fractions – les UTXOs ou Unspent Transaction Outputs – qui seront réutilisés par la suite pour faire d’autres transactions. Pour la simplicité utilisons des montants simples. Mettons que vous ayez 1 BTC dans votre wallet et que vous achetiez un service qui coûte o,2 BTC. Vous récupérerez 0,8 BTC. Plus tard, vous verserez à nouveau 1 BTC dans votre wallet pour pouvoir acheter un service qui coûte 1,5 BTC. Lorsque vous dépenserez 1,5 BTC, votre wallet ira créer une transaction à partir de l’adresse qui contient 0,8 BTC et celle qui contient 1 BTC pour créer une transaction à 1,5 BTC. Autrement dit, votre wallet crée depuis plusieurs adresses plusieurs transactions pour en envoyer une seule au destinataire ; mais cette transaction finale est très lourde parce qu’elle contient deux signatures au lieu d’une. Et dans la réalité, vos transactions sont composées d’énormément d’UTXOs d’anciennes transactions et sont donc lourdes.

Pour simplifier les choses, on peut dire que plus un wallet est utilisé, plus il a tendance à créer des transactions lourdes car pleine d’UTXOs qui requièrent chacun une signature pour être utilisé.

Là où les signatures de Schnorr se révèlent salutaires, c’est qu’elles permettent de signer une seule fois plusieurs transactions à la fois, en particulier celles qui émanent de plusieurs adresses pour aller vers un seul destinataire. Une seule signature qui représente plusieurs signatures individuelles.

Schnorr, SegWit et la scalabilité

Or les signatures de Schnorr étaient de l’ordre du rêve jusqu’à ce que SegWit soit implanté dans Bitcoin. SegWit a changé le code de Bitcoin de manière à rendre crédible l’implantation à son tour des signatures de Schnorr. Actuellement, Bitcoin utilise ce qu’on appelle l’algorithme de signature digitale à courbe elliptique, en anglais Elliptic Curve Digital Signature Algorithm abrégé en ECDSA.

Ce qu’a fait SegWit, c’est déplacer les données des signatures dans une autre partie du code des transactions, ce qui a incidemment permis de libérer de la place. In fine, SegWit a déjà permis de créer des transactions de plus faible poids sur le réseau. Les signatures de Schnorr augmenteraient davantage la scalabilité du réseau en économisant 25% de la taille des transactions. Cela accélérerait la validation des transactions et réduirait le coût à payer pour les faire passer. 1 signature pour 1 transaction dans un bloc, même s’il y a plusieurs « petites transactions » au préalables.

Les signatures de Schnorr contiennent en effet seulement 64 bytes au lieu des 71 à 72 des signatures ECDSA au format DER (Distinguished Encoding Rules) actuelles. Elles peuvent potentiellement valider des signatures en lots, jusqu’à 32 signatures à la fois. Pour ce faire, les signatures de Schnorr connaissent la coordonnée R.y, ce dont est incapable ECDSA. R est un point sur la courbe elliptique, produit de la multiplication d’un nonce aléatoire avec un point générateur ; y est une coordonnée sur l’axe de la fonction de hachage.

La conséquence à cela est que si le script n’arrive pas à vérifier une signature, le script lui-même échoue. En termes techniques, les opérateurs CHECKSIG se comportent comme des CHECKSIGVERIFY. En termes profanes, la sécurité est accrue et ne laisse la place à absolument aucune erreur. Jusqu’à présent, les signatures à encodage DER pouvaient ne pas pouvoir vérifier une signature sans avoir à avorter leur script, ce qui laissait la place à des attaques.

Un plus grand anonymat

Cela nous mène à la sécurité accrue qu’offrent les signatures de Schnorr. Une transaction signée selon l’algorithme en question comprend plusieurs adresses. Normalement, ces adresses appartiennent à une seule personne (voir le deuxième cas de figure expliqué ci-dessus).

Mais une des autres conséquences positives est que si vous choisissez d’utiliser le système des MultiSig soit pour vous-même soit avec d’autres participants, vos signatures ne seront pas plus lourdes et surtout, elles auront la même apparence sur le réseau que toute autre transaction.

Si vous voulez pousser le bouchon plus loin, vous pouvez même utiliser CoinJoin, un système pensé par un des développeurs de Bitcoin Core, Gregory Maxwell, qui mélange les transactions de plusieurs utilisations dans une seule opération. Avant, ces transactions étaient très lourdes et pleines de signatures, même si cela les rendaient très sûres. Avec les signatures de Schnorr, les transactions effectuées via CoinJoin auront le même poids qu’une transaction simple, car elles n’auront qu’une signature.

Les attaques contre le réseau

Le troisième avantage des signatures de Schnorr est qu’elles empêchent des esprits mal intentionnées de s’attaquer au réseau Bitcoin via des « spam attacks ». Ces attaques consistent à envoyer le plus de transactions le plus lourdes possibles pour congestionner le réseau et le rendre lent au point d’être inopérant.

Pourquoi est-ce important ? Car les dernières analyses montrent que la folie qui s’est emparé du réseau Bitcoin en mai 2017 n’avait rien d’une adoption de masse. La croissance gigantesque du nombre de transactions ne correspondait pas à un nombre croissant d’utilisateur, mais à une attaque massive visant à montrer que le réseau Bitcoin n’était scalable. Le résultat fut que les frais de transaction ont atteint des nouveaux sommets, que le réseau était lent…et qu’en juin 2017, les développeurs ont décidé de trouver une solution de scalabilité dont SegWit. À ce moment, les attaques ont cessé. L’accroissement du réseau Bitcoin n’était donc pas naturel.

Les signatures de Schnorr permettraient d’éviter ce genre de cas à l’avenir. Comme une seule signature est nécessaire par transaction, il y aura plus de transactions par blocs et donc les spammers devront dépenser bien plus d’argent en transactions pour pouvoir congestionner le réseau comme avec des signatures traditionnelles. Les spammers y perdraient donc leurs plumes, et n’auraient de fait plus de revendication politique puisque du moment que Bitcoin implante les signatures de Schnorr, le réseau devient parfaitement fluide, scalable.

Implantation naïve des signatures de Schnorr

Ici, nous allons exposer comment les signatures fonctionnent d’un point de vue mathématique. Attendez-vous donc à ce que cette partie soit technique.

Soit :

Les lettes majuscules représentent des points sur la courbe elliptique (sauf H) et les minuscules des nombres scalaires.

m = le message

x = la clé privée

G = le générateur

X = la clé publique (X = x*G, clé publique = clé privée * générateur)

(R, s) = la signature (R est la co-ordonnée x d’une valeur aléatoire après multiplication par le générateur, et s est la signature).

H (x, y, z, …) = la fonction de hachage crypto-graphique.

La signature de Schnorr est créée ainsi :

(R, s) = (r*G, r + H(X, R, m) * x)

R = un nonce aléatoire * un générateur (donc un point sur la courbe)

s = un nonce aléatoire + une fonction de hachage (clé publique, point aléatoire sur la courbe, le message (transaction * clé privée)).

Et vérifiée de la sorte :

s*G = R + H(X, R, m) * X

C’est une équation linéaire, les deux côtés doivent être satisfaits pour que la signature soit vérifiée. Elle peut s’exprimer aussi en tant que :

signature * générateur = point sur la courbe + fonction de hachage  (clé publique, point sur la courbe, message (transaction * clé privée)).

Maintenant, la manière dont les transactions sont signées par une seule signature est la suivante.

Création de la signature :

Soit X, la somme de toutes les clés publiques ou X = (Xi + (Xi+1) + (Xi+2)…)

R = la somme des nonces aléatoires des signataires, ou R = (Ri + (Ri+1) + (Ri+2)…)

s = la somme des signatures des signataires, ou s = (si + (si+1) + (si+2)…)

(R, s) = la signature où s est la somme de toutes les signatures

Vérification :

Soit X = la somme de toutes les clés publiques des signataires

s*G = R + H(X, R, m) * X

Mais l’on ne vous a pas tout dit…

Implanter les signatures de Schnorr de la sorte est insuffisant car cela laisse ouverte porte aux attaques des fausses clés (Rogue Key Attack). Dans ce cas de figure, un signataire peut illégitimement dire être le propriétaire d’une clé publique pour contrôler la signature multiple et récupérer les fonds de la transaction. Voilà comment cela marcherait :

A et B veulent créer une Multi-Sig 2-de-2.

A a la paire de clé (xA, XA) (clé privée, clé publique).

B a la paire (xB, XB).

XAB = XA + XB

B envoie une fausse clé publique XBf = XB – XA

Par exemple :

XA = 10

XBt (la vraie clé publique de B) = 11

XBf = XBt (11) – XA (10) = 1

XAB = XA (10) + XBf (1) = 11

Autrement dit, la clé multiple XAB qui provient de la fausse clé publique de B est égale à la vraie clé publique de B. Ce faisant, il peut contrôler la MultiSig.

Du coup, chaque participant doit prouver l’un à l’autre que le clé publique est valide en fonction d’une signature créée par leur clé privée respective. Cela revient donc au même problème que les ECDSA, à savoir le besoin de passer par des transactions sur le Blockchain pour authentifier des signatures individuelles.

La solution Bellare-Neven

Le schéma dit de Bellare-Neven permet justement de contourner ce genre d’attaques.

Création de la signature :

L = H(xi + (Xi+1)…) où L est la somme des clés publiques

R = (ri *G) + ((ri+1) * G) … où R est la somme des points aléatoires sur la courbe des signataires ; ils partagent leur nonce aléatoire avec d’autres signataires.

si = ri + H(L, Xi, R, m) * xi où si est la signature générée pour chaque signataire et où si est le nonce + le hachage (hachage des clés publiques, clé publique des signataires, somme des points aléatoires, message (transaction)) * clé privée des signataires.

(R, s) est la signature finale.

Vérification :

s*F = R + H(L, X1, R, m) * X1 + H(L, X2, R, m) * X2 + …

C’est une équation linéaire, les deux côtés doivent être satisfaits pour que la signature soit vérifiée. Elle peut s’exprimer en tant que :

La somme des signatures * le générateur = la somme des nonces + le hachage (somme des clés publiques, clé publique du signataire 1, somme des nonces, message (transaction)) + clé publique du signataire 1…pour chaque signataire de la MultiSig.

Le problème qui reste est qu’il faut encore montrer la clé publique de chaque participant pour vérifier la signature.

Mu-sig

La solution à ce problème est Mu-sig, qui est un algorithme qui permet de former un agrégat des signatures et des clés publiques. Plutôt que de vérifier la signature en fonction de la clé publique de chaque signataire, Mu-sig permet l’utilisation d’une seule clé publique pour la vérification. Il n’y aura pas besoin de plusieurs clés publiques pour valider une signature, et le fait que la signature est dérivée de plusieurs clés privées sera dissimulé.

Création de la signature :

L = H(Xi + (Xi+1)…) où L est le hachage total des clés publiques

X = ( (H(L, Xi) + Xi) + (H(L, Xi+1) * Xi+1)…)

ou X = la somme des clés publiques hachées + les clés publiques des signataires – le hachage (total haché des clés publiques, clé publique du signataire 1) * la clé publique du signataire 1

R = (ri * G) + ((ri+1) * G)... où R est la somme des points aléatoires sur la courbe des signataires ; ils partagent leur nonce aléatoire avec d’autres signataires.

si = ri + H(X, R, m) * H(L, X) * xi où si est la signature générée pour chaque participant.

si = le nonce aléatoire + hachage (X, somme des points aléatoires des signataires, message (transaction)) * hachage (total haché des clés publiques, X) * clés privés des signataires.

s = (si) + (si+1) + (si+2) …où s est la somme des signatures des signataires.

(R, s) est la signature finale.

Et sa vérification :

s*G = R + H(X, R, m) * X

C’est une équation linéaire, les deux côtés doivent être satisfaits pour que la signature soit vérifiée. Elle peut s’exprimer en tant que :

la somme des signatures des signataires * le générateur = somme des nonces + hachage (X, somme des points des nonces, message (transaction)) * X

Mu-sig permet de valider une signature sans passer par la divulgation de chaque clé publique et utilise à la place X : la somme des clés publiques des signataires. Ainsi, une validation MultiSig n’aura qu’une signature sur la Blockchain. En outre, les transactions inscrites sur la Blockchain sont effectivement moins lourdes car elles forment un agrégat des signatures et des clés publiques.

À ce jour, Mu-sig est la version la plus à jour des signatures de Schnorr.

Sources :

https://bitcointechtalk.com/scaling-bitcoin-schnorr-signatures-abe3b5c275d1

https://medium.com/@SDWouters/why-schnorr-signatures-will-help-solve-2-of-bitcoins-biggest-problems-today-9b7718e7861c

https://coinpupil.com/bitcoin/what-is-bitcoin/what-are-schnorr-signatures/