Transactions Bitcoins & Signatures numérique

Le Bitcoin est une monnaie numérique, ou cryptomonnaie, créer en 2009 par la personne ou le groupe de personnes connues sous le pseudonyme de Satoshi Nakamoto. Une cryptomonnaie est une monnaie numérique, dématérialisée et sans organisme centralisé ou autorité centrale de régulation (banques). Le Bitcoin repose pour ce faire sur un réseau pair à pair et sur l'utilisation de la blockchain.

Blockchain

Registre des transactions

La blockchain se présente comme un réseau pair à pair dans lequel chacun des nœuds possède une copie du registre contenant l'intégralité de transactions de Bitcoin ayant eu lieu. Lorsqu'un utilisateur désir créer une nouvelle transaction, il lui suffit de l'ajouter dans le registre. Cette transaction va ensuite être propagée dans les nœuds voisins afin que chacun des nœuds ait la dite transaction inscrite dans son registre. Ainsi, les nœuds du réseau vont s'échanger en permanence les nouvelles transactions qui ont été créée dans leur registre ou qu'ils ont reçu depuis un autre nœud.

Notion de bloc

Du fait des échanges constant entre les blocs et de la création permanente de nouvelles transactions, on obtient très rapidement des registres qui n'ont plus rien à voir d'un bout à l'autre du réseau. De plus, rien n'empêche pour l'instant la double dépense, le fait de dépenser à un bout de réseau des Bitcoins et de les re-dépenser à l'autre bout du réseau. afin d'éviter cela, on introduit la notion de bloc. En pratique, chaque nouvelle transaction n'est pas ajouté directement à la liste de transactions effectives, mais à une liste d'attente. lors de l'ajout à cette liste d'attente, on vérifie que les Bitcoins n'ont pas déjà été dépensés. Toutes les 10 minutes environ, afin de synchroniser les transactions sur le réseau, on choisit l'une des listes d'attente de l'un des nœuds du réseau, et on déclare que cette liste d'attente est validée. A partir de maintenant, tous les nœuds du réseau vont supprimer leur liste d'attente et accepter celle du nœud choisi afin de l'ajouter à son registre : c'est le nouveau bloc. le registre va donc prendre la forme d'une suite de blocs contenant chacun une liste de transactions, d'où la chaîne de blocs.

On remarque qu'il peut arriver qu'une transaction ayant été inscrite ne soit pas validée (si elle n'était pas dans la liste d'attente du nœud choisi). dans ce cas, il faut que l'utilisateur vérifie que sa transaction ait bien été validée et la re-crée le cas échéant.

Il peut également arriver que plusieurs blocs soient choisis simultanément. Dans ce cas, les deux nouveaux blocs se propagent en même temps mais les nœuds ne vont travailler qu'avec la chaîne la plus longue. Rapidement, l'une va prendre le pas sur l'autre et la chaîne la plus courte va être supprimée. En pratique, il convient pour les utilisateurs d'attendre environ une heure après la transaction pour vérifier que celle-ci ait bien été validée avant de la considérer effective.

Nonce & preuve de travail

Dans la partie précédente, nous avons délibérément laisser dans le flou une notion pourtant essentielle : comment choisit-on le nœud qui validera sa liste d'attente et créera ainsi le nouveau bloc ?

Pour ce faire, on demande aux nœuds de trouver un identifiant pour le nouveau bloc. le premier nœud qui trouve cet identifiant peut faire valider sa liste d'attente, c'est ce qu'on appelle la preuve de travail. Mais trouver cet identifiant n'est pas chose aisée. Chacun des nœuds devra résoudre une suite de calculs mathématiques très complexes afin de trouver ce qu'on appelle un Nonce, qui est un nombre arbitraire destiné à n'être utilisé qu'une seule fois. La complexité de la suite de calcul permettant de déterminer ce nonce est ajustée en permanence afin que le temps permettant de parvenir au résultat prenne toujours environ 10 minutes, malgré la puissance de calcul augmentant en permanence. De plus, la valeur du nonce dépends d'un hachage du bloc précédent. Ainsi, les calculs permettant de déterminer le nouveau nonce ne peuvent commencer qu'une fois que le bloc précédent à été validé, et il est impossible de modifier une transaction dans un blocs sans avoir besoin de recalculer l'intégralité de la chaîne de blocs, ce qui est impossible en pratique car cela demanderait de posséder une puissance de calcul supérieure à 50% de l'intégralité de la puissance de calcul de tout le réseau (pour info : même si Google mettais l’intégralité de sa puissance de calcul, il n'aurait même pas 1% de la puissance de calcul du réseau).

Nous remarquons donc que pour que le réseau soit sécurisé et que la monnaie puisse continuer d'exister, il faut que les utilisateurs mettent leur puissance de calcul au service du Bitcoin. Pour inciter les utilisateurs à faire cela, ils sont tout simplement payés en Bitcoin pour le faire. en effet, lorsqu'un nœud valide sa liste d'attente, il reçoit 25 Bitcoin qui sont ajoutée à la masse monétaire du réseau, c'est ce qu'on appelle le minage de Bitcoin. c'est d'ailleurs le seul moyen de créer de la masse monétaire avec le Bitcoin. Cependant, la récompense en Bitcoin va décroître au fil du temps et cette masse monétaire va converger vers 21 000 000 de Bitcoins.

Transactions Bitcoins

Ecriture dans le registre

Afin de créer une nouvelle transaction en Bitcoin, il faut inscrire dans son registre la nouvelle transaction. Par exemple, Si Flavien veut donner 2 Bitcoin à Thomas, il écrira dans le registre :

- Moi, Flavien, donne 2 ฿ à Thomas

une fois cette transaction inscrite dans le registre, elle sera propagée sur le réseau comme nous l'avons vu dans la partie sur la Blockchain.

Référence vers une ancienne transaction

Afin de vérifier qu'un utilisateur puisse dépenser les Bitcoin de sa transaction, on n'utilise pas ici un système de solde, comme il peut y avoir avec le système bancaire. l'utilisateur ne va pas soustraire les Bitcoins de sa transaction à son solde total, on va à la place référencer une ancienne transaction, celle qui nous a permis d'avoir les Bitcoins que l'on souhaite dépenser. Si l'on reprend notre exemple ci-dessus, on obtient :

- Moi, Flavien, donne 2 ฿ à Thomas, en utilisant les 2 ฿ que m'a donné Jean-José dans la transaction n°xxx

Evidemment, une transaction ne peut être référencée qu'une seule fois, et ce afin d'éviter la double dépense de Bitcoins. par exemple, après la transaction précédente, la transaction suivante serait impossible.

- Moi, Flavien, donne 2 ฿ à Jean-Michel, en utilisant les 2 ฿ que m'a donné Jean-José dans la transaction n°xxx

De plus, si la transaction référencée contient plus de Bitcoins que la nouvelle transaction, une nouvelle transaction est crée afin de se rembourser la différence :

- Moi, Flavien, donne 2 ฿ à Thomas, en utilisant les 9 ฿ que m'a donné Jean-José dans la transaction n°xxx

- Moi, Flavien, me rembourse 7 ฿ qu'il me reste de la transaction n°yyy

Signature numérique

Lors d'une transaction Bitcoin, il faut pouvoir authentifier la personne effectuant la transaction. pour ce faire, on utilise une signature numérique.

principe de la signature numérique

Un système de signature numérique repose sur la cryptographie asymétrique. Un algorithme de cryptographie asymétrique permet d'avoir deux clés de cryptage différentes, l'une permettant de chiffrer le message et l'autre de le déchiffrer. Dans la plupart des système à cryptographie asymétrique, on utilise la clé publique pour chiffrer, afin que tout le monde puisse nous envoyer un message par exemple, et on utilise ensuite la clé privée pour déchiffrer, afin d'être le seul à pouvoir lire le dit message. Dans les système de signature numérique, c'est l'inverse : la clé privée permet de chiffrer le message afin de signer et la clé publique va permettre à tout les utilisateur de déchiffrer le message afin de vérifier la signature.

Application pour le Bitcoin

Pour les transaction de Bitcoin, chaque utilisateur possède une clé privée. cette clé va permettre à l'utilisateur d'ajouter une signature à sa transaction, chiffrée avec cette clé privée. Cette signature va dépendre d'un hachage de la transaction, de façon à ce que chacune des signatures d'un utilisateur soit différentes. ensuite, chaque utilisateur aura également une clé publique permettant à tout les autres utilisateur de vérifier la provenance de la signature et donc l'identité de celui qui effectue la transaction.

L'algorithme utilisé aujourd'hui pour chiffrer les signatures numérique est l'algorithme ECDSA, reposant sur la cryptographie sur les courbes elliptiques. C'est cet algorithme qui sera présenté dans la suite du wiki. Cependant, il est possible que cet algorithme change prochainement au profit du schéma de signature de Schnorr, plus simple et plus rapide, permettant d'avoir des signatures plus courte pour une sécurité équivalente. Si le schéma de signature de Schnorr n'a pas été utilisé jusqu’à maintenant, c'est principalement en raison d'une protection par un brevet, mais l'algorithme est tombé récemment dans le domaine publique.

Elliptic Curve Cryptography

La cryptographie sur les courbes elliptiques (en anglais, elliptic curve cryptography ou ECC) regroupe un ensemble de techniques cryptographiques qui utilisent une ou plusieurs propriétés des courbes elliptiques. Les premières utilisations de ces courbes remontent en 1985 de manière indépendante par Neal Koblitz et Victor Miller.

Propriétés utiles d’une courbe elliptique

- Une courbe elliptique est symétrique par rapport à l’axe des abscisses.
- Une droite passant par 2 points de la courbe coupe cette dernière en un 3ème points.

Ces deux propriétés nous permettent d'effectuer l'opération "dot" illustrée sur le schéma ci-contre qui nous sera très utile pour l'algorithme de signature.

Opération sur la courbe => P . Q -> R

Les plus de ECC

ECC permet de garantir la même sécurité que RSA mais avec des clés bien plus courte, ce qui permet d'améliorer les temps de calcul. Par exemple avec une clé ECC de 256 bits, on obtient la même sécurité que le système RSA avec un clé de 3072 bits. En allant un peu plus pour atteindre une sécurité dite "Top Secret" par la NSA le système ECC nécessite une taille de clé de 384 bits contre 7680 pour RSA.

Elliptic Curve Digital Signature Algorithm

Elliptic Curve Digital Signature Algorithm (ECDSA) est un algorithme de signature numérique à clé publique et privée. Cet algorithme se base sur la cryptographie sur les courbes elliptiques vu précédemment. Cet algorithme a été proposée pour la première fois en 1992 par Scott Vanstone.

Données d'entrée de ECDSA

- Formule de la courbe => y² = x³ + ax + b (courbe elliptique sur un corps d'entiers fini modulo p avec p un nombre premier).
- Un point de la courbe (appelé point de base) => G.
- L’ordre de G => n. Le plus petit entier tel que n . G donne O le point à l’infini de la courbe, pour que tous les entiers entre 1 et n-1 soit modulo n. De plus n doit être premier pour que l’anneau Z/nZ soit un corps. Ce nombre correspond au plus grand nombre possible pour une clé, l'ordre de n donne donc la taille de la clé.

Génération des clés

Chaque personne doit avoir une clé privée et une clé publique.

- Clé privée a : un nombre entre 1 et n-1.
- Clé publique A : a . G.

Signature

Pour signer :

- On choisit on nombre aléatoire k entre 1 et n - 1.
- On calcule le point K = k . G.
- On garde la composante $K_{x}$ qu'on appellera r.
- On calcule un nombre z qui correspond au résultat d'un hachage cryptographique sur le message à signer.
- On calcule ensuite un nombre $s=k^{-1}.(z+ra){\bmod {n}}$.
- La signature correspond au couple (r,s).

Vérification

Pour vérifier la signature :

- On calcul un nombre $w=s^{-1}{\bmod {n}}$.
- On calcul deux coefficients $u_{1}=zw{\bmod {n}}$ et $u_{2}=rw{\bmod {n}}$.
- On peut donc calculer ce qu'on appelle le point de vérification de la signature $S=u_{1}.G+u_{2}.A$
- Si $S_{x}=r$ la signature est valide.

Pour les transaction BitCoin

La courbe utilisée pour le BitCoin est Secp256k1 dont l’équation est y² = x³ + 7. Cette courbe est utilisée pour des raisons de performance de calcul.

- Gx = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
- Gy = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
- n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Exemple de signature et vérificaction

Voici un exemple d'échange de messages entre Alice et Bob. Alice envoie un message et Bob et ce dernier veut s'assurer que le message à bien été envoyé par Alice.

Données de base

Les deux utilisateurs connaissent à l'avance la courbe qui a pour formule $y^{2}=x^{3}-2x+15$.

Le point générateur $G=[4,5]$ et $n=23$.

La clé privée d'Alice est $a=3$.

Sa clé publique est donc $A=a.G=3.[4,5]=[13,22]$ qu'elle partage à Bob.

Signature d'Alice

Alice prend un nombre aléatoire entre 1 et n-1 (22) $k=19$.

$K=k.G=19.[4,5]=[9,17]$.

Donc $r=9$.

Alice prend ensuite le haché du message $z=10$ par exemple.

Elle calcul ensuite $s=k^{-1}.(z+ra){\bmod {n}}=19^{-1}.(10+9.3){\bmod {2}}3=17.14{\bmod {2}}3=8$.

Alice a donc sa signature $(r,s)=(9,8)$ qu'elle envoie avec son message pour Bob.

Vérification de Bob

Bob reçoit le message et va tenter de vérifier si la signature vient bien d'Alice. Il calcule donc $w=s^{-1}{\bmod {n}}=8^{-1}{\bmod {2}}3=3$.

Il calcule ensuite les deux coefficients :

- $u_{1}=zw{\bmod {n}}=10.3{\bmod {2}}3=7$
- $u_{2}=rw{\bmod {n}}=9.3{\bmod {2}}3=4$

Bob peut désormais calculer le point de vérification de la signature $S=u_{1}.G+u_{2}.A=7.[4,5]+4.[13,22]=[13,22]+[10,12]=[9,17]$

r est bien égal à $S_{x}$ donc la signature est valide.

Sources

- https://blockchainfrance.net/decouvrir-la-blockchain/c-est-quoi-la-blockchain/
- https://www.cryptocompare.com/wallets/guides/how-do-digital-signatures-in-bitcoin-work/
- https://bitcoin.fr/signatures-de-schnorr-et-scalabilite/
- https://eprint.iacr.org/2018/068.pdf
- https://fr.wikipedia.org/wiki/Elliptic_curve_digital_signature_algorithm
- https://fr.wikipedia.org/wiki/Cryptographie_sur_les_courbes_elliptiques
- https://www.youtube.com/watch?v=du34gPopY5Y
- https://www.youtube.com/watch?v=dCvB-mhkT0w
- https://www.youtube.com/watch?v=6TI5YOpnrgI
- https://trustica.cz/en/2018/06/07/elliptic-curve-digital-signature-algorithm/

Créer par Thomas De Iseppi et Flavien Stemmelen