BITCOIN

BITCOIN

BITCOIN

[Article rédigé par Gautier MARIN-DAGANNAUD pour Ethereum France]

Préambule : Un petit historique

Le terme blockchain désigne un concept abstrait qui peut être implémenté de multiples manières. Le concept a été défini pour la première fois par Satoshi Nakamoto en 2008 et déployé pour supporter la plateforme Bitcoin en 2009. Bien que la blockchain Ethereum soit différente de la blockchain Bitcoin sur bien des points, ces deux plateformes partagent les mêmes principes fondamentaux. Avant de s’attaquer à Ethereum, il va donc falloir passer par Bitcoin.

Bitcoin est un système de paiement digital s’appuyant sur une crypto-monnaie du même nom. Comme dans tout système de paiement dématérialisé, il est nécessaire de maintenir un registre des comptes pour connaitre la balance de chaque utilisateur. Dans le monde « réel », ce sont les banques qui tiennent ce registre. Si l’on souhaite envoyer de l’argent à quelqu’un, il faut en faire la requête à la banque, puisque c’est elle qui tient les comptes. On parle d’organisme centralisé.
La centralisation a de nombreux avantages, notamment celui d’introduire un tiers de confiance auquel on peut se rapporter en cas de litige, mais elle a également beaucoup de défauts. Entre autres, la concentration de donnée réduit la sécurité du système et entraîne une concentration de pouvoir. Dans le cas des banques, l’opacité du système a rendu méfiant de nombreux utilisateurs, notamment à la suite de la crise de 2008. C’est dans ce contexte qu’est née l’idée Bitcoin.

Le principe fondamental de Bitcoin est relativement simple : au lieu que le registre soit maintenu par un seul organisme privé, il est maintenu de manière décentralisée. En clair, chaque ordinateur du réseau (appelé noeud) contient une copie du registre et aide à le maintenir à jour. Dès qu’un noeud reçoit une transaction, il la relaie au noeud suivant, puis valide la transaction et met à jour le registre. Le registre est protégé par cette décentralisation : un ou plusieurs noeuds peuvent être altérés ou détruits, le registre sera conservé tant que subsistera au moins un noeud honnête.

2 systèmes de maintien d’un registre : Centralisé vs Décentralisé

2 systèmes de maintien d’un registre : Centralisé vs Décentralisé

Une image souvent utilisée pour représenter la blockchain est celle d’un grand livre des comptes public, infalsifiable et indestructible. Mais ce système est-il vraiment infaillible ? Eh bien, pas vraiment… La décentralisation implique de nombreux challenges techniques plus ou moins évidents à surmonter.

Le challenge principal d’un réseau décentralisé est de s’accorder sur la validité des transactions. Valider une transaction est un processus à plusieurs niveaux : il faut (I) identifier l’émetteur comme légitime (rappelons que tout utilisateur de Bitcoin interagit avec le réseau de manière anonyme), (II) vérifier qu’il possède suffisamment de fond pour effectuer la transaction et (III) ordonner chronologiquement les transactions.

Chaque noeud peut vérifier indépendamment ces conditions assez facilement mais, à l’échelle du réseau, il est beaucoup plus compliqué de trouver un consensus. En effet, n’importe quelle personne possédant un ordinateur peut se connecter de façon anonyme et participer au maintien du registre, ce qui implique qu’un noeud ne peut à priori pas faire confiance aux autres. Permettre à un système décentralisé de s’accorder sans que les participants aient besoin de se faire confiance est, en somme, ce que permet de faire la technologie blockchain.

[Article rédigé par Gautier MARIN-DAGANNAUD pour Ethereum France]

Plan de l’article

I. Identifier l’émetteur comme légitime

I.1. La paire clé privée/ clé publique
I.2. De l’immense diversité des adresses
I.3. Multisignature : un mécanisme bien pratique
I.4. Protéger sa clé privée

II. UTXOs, ou comment s’assurer que l’émetteur possède bien les fonds suffisants

III. Ordonner chronologiquement les transactions à l’échelle du réseau : la blockchain

III.1. Modèle sans consensus
III.2. Les bases de la Blockchain
III.3. Preuve de travail (PoW)
III.4. Temps de latence
III.5. Nouvelle règle, nouveaux problèmes
III.6. Des noeuds et des arbres

Nb : Dans le début de cet article, nous considérerons le client (i.e. le programme utilisé pour produire des transactions) comme un noeud à part entière.

I. Identifier l’émetteur comme légitime

1. La paire clé privée/ clé publique

En théorie, lorsqu’un noeud reçoit une transaction transférant une certaine somme de Alice à Bob, il n’a aucun moyen de savoir si Alice est bien l’émetteur de cette transaction.

Pour résoudre ce problème, Bitcoin utilise un système courant en cryptographie basé sur une combinaison clé privée/clé publique. La clé publique, ou adresse, est visible par tous (ndlr: par souci de simplification, nous ferons à ce stade la confusion clé publique/adresse). En pratique, lorsque Alice initie une transaction à destination de Bob, c’est à son adresse qu’elle envoie l’argent.

Exemple de transaction Bitcoin. À gauche : adresse de l’émetteur. À droite : adresse du destinataire

Exemple de transaction Bitcoin. À gauche : adresse de l’émetteur. À droite : adresse du destinataire

Cette adresse est directement reliée à la clé privée de Bob, qui est en quelques sorte le mot de passe associé à cette clé. À vrai dire, l’adresse est générée à partir de la clé privée grâce à de complexes fonctions mathématiques dont il suffit de retenir qu’elles fonctionnent à sens unique. Ainsi, en appliquant ces fonctions à une clé privé (P), on obtiendra toujours la même adresse (A), mais il n’est pas possible, connaissant (A), de retrouver (P). Le possesseur de (P) peut donc facilement prouver qu’il possède bien les fonds stockés à l’adresse (A).

Le problème est-il résolu ? Pas encore. Il faut bien comprendre que le système Bitcoin fonctionne de manière décentralisée. Cela implique que vous ne pouvez pas simplement donner votre clé privée au réseau pour prouver que vous possédez les fonds, comme vous donneriez votre mot de passe à une banque en ligne. En effet, un noeud qui recevrait votre clé privée serait en mesure de la réutiliser pour dépenser votre argent (de même que la banque en ligne pourrait en théorie dépenser vos fonds, puisqu’elle connait votre mot de passe). Il est donc nécessaire de trouver un moyen de prouver au réseau que l’on possède la clé privée, sans fournir la clé elle-même. Cette preuve, c’est la signature digitale.

L’idée est simple : au lieu de fournir au réseau la clé privée, on fournit une signature digitale générée à partir de la clé privée et de la transaction considérée. La signature digitale est une preuve que l’émetteur possédait bien la clé privée associée à l’adresse d’émission au moment où il a initié la transaction. Cette signature est passée avec la transaction au réseau, ce qui permet à chaque noeud de valider cette dernière sans avoir accès à la clé privée de l’émetteur.

Validation d'une transaction (1)

Validation d’une transaction (1)

Cette idée est bien sympathique, mais n’a-t-on pas simplement déplacé le problème ? Le noeud ne peut-il pas réutiliser une signature pour valider une autre transaction depuis la même adresse ?
Non. Cette fois-ci, ce n’est pas possible. En effet, une signature digitale est différente à chaque transaction émise, de telle sorte qu’il est impossible de prendre la signature digitale d’une transaction pour tenter de valider une autre transaction. Pour y voir un peu plus clair, intéressons nous de plus près à l’algorithme de vérification d’une transaction (ndlr : ce qui suit est une vulgarisation de https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm).

De manière synthétique, la signature digitale est une fonction F prenant en paramètre la clé privée de l’émetteur (p) et le message émis (m). Pour vérifier si la signature est valide, chaque noeud applique une autre fonction V prenant en paramètre l’adresse publique de l’émetteur (a), le message (m) et la signature digitale (s), et qui renvoie vrai ou faux. Il est important de noter que la fonction F est à sens unique, de sorte qu’il est impossible de deviner la clé privée à partir de la signature. Cela implique également une interdépendance entre la signature et le message : F donnera une toujours la même signature pour un message et une clé privée donnés, mais le moindre changement de l’un des deux paramètres aura pour effet d’altérer radicalement la signature. Ainsi, une signature digitale ne pourra jamais être réutilisée. Cela empêche également les noeuds qui relaient la transaction de la modifier au passage. En effet, si l’intégrité du message est corrompue (m devient m’), V renverra faux car le message en entrée n’est plus le même que celui qui avait été passé en paramètre de F.

Validation d'une transaction (2)

Validation d’une transaction (2)

NB : sur le schéma de la transaction, l’adresse du destinataire apparait distincte du message. En réalité, on peut considérer qu’elle est inclue dans m, de telle sorte qu’un noeud ne puisse pas la modifier sans invalider la signature

2. De l’immense diversité des adresses

Jusqu’ici, nous avons fait la confusion clé publique/adresse. Rigoureusement parlant, ces deux termes ne désignent pas exactement la même chose, bien qu’ils remplissent la même fonction. Simplement, une adresse est une version digeste de la clé publique, adaptée à l’utilisation par des humains (comprendre plus courte et plus lisible). Pour obtenir une adresse, il suffit d’appliquer quelques transformations mathématiques à la clé publique, et le tour est joué !
Autre précision importante : lorsque vous créez une paire clé privée/clé publique, vous la créez indépendamment du réseau. En d’autres termes, le réseau ne parcourt pas la liste des adresses déjà utilisées pour vous en proposer une « valide ». Pourquoi ?

La raison se trouve dans le mécanisme de génération d’une adresse. Une adresse est, comme on l’a vu, générée à partir d’une clé publique, qui est elle-même générée à partir d’une clé privée. Ainsi, pour fournir une adresse non utilisée, le réseau devrait générer une clé privée ! Si vous avez bien saisi le principe d’un système décentralisé, vous comprenez donc pourquoi il est impensable que cela fonctionne de cette façon (on ne donne JAMAIS sa clé privée au réseau).

Mais alors, est-il possible que deux personnes génèrent la même paire clé privée/clé publique ? En théorie, oui. Dans ce cas, les deux personnes auraient accès aux fonds stockés à l’adresse correspondante. Rassurez vous cependant, la probabilité que votre clé privée aléatoirement générée donne une adresse déjà utilisée est quasiment nulle.
Pour vous en convaincre, voici un nombre très grand : 2160. Ce nombre représente le nombre total d’adresse Bitcoin possible. En comparaison, il y a environ 263 grains de sable sur terre. Si chacun de ces grains contenait une Terre avec autant de grain de sable, le nombre total de grain de sable serait de 2126, ce qui est encore très inférieur à 2160.
Il est donc mathématiquement impossible (enfin, presque !) que quelqu’un génère une clé privée donnant une adresse déjà utilisée.

Allons encore plus loin, serait-il possible qu’un ordinateur génère des milliers de clés privées, vérifie si l’adresse correspondante a une balance non nulle et, le cas échéant, vire les fonds sur sa propre adresse ? Encore une fois, cette attaque, sans être complètement impossible, est très difficilement réalisable.
Pour s’en convaincre, simplifions le problème et imaginons qu’un programmeur malicieux souhaite trouver la clé privée associée à une adresse spécifique. Supposons que ce programmeur possède un ordinateur capable de générer un milliard (~230) de clés privées par seconde. Il lui faudrait alors en moyenne 2130 secondes pour trouver la bonne clé. Supposons maintenant qu’il possède 1 milliard de milliards de ces ordinateurs, il ne lui faudrait alors plus « que » 270secondes, ou 245 années. Sachant que l’univers est âgé de 234 années, il ferait mieux de s’y mettre maintenant !

3. Multisignature : un mécanisme bien pratique

Jusqu’ici, chacune des adresses que nous avons vues est contrôlée par une unique clé privée. Cependant, il s’est rapidement avéré qu’il serait bien pratique qu’une adresse puisse être contrôlée par plusieurs personnes. Pour ce faire, on a recourt à un mécanisme appelé multisignature, permettant d’effectuer des « m-parmi-n » transactions, où « m » fait référence au nombre de signataires nécéssaire parmi les « n » possesseurs de l’adresse pour débloquer les fonds.
Par exemple, un couple souhaitant avoir une adresse commune utiliserait des « 2-parmi-2 » transactions. Pour autoriser une transaction, il faudrait que les deux conjoints la signent.

Un autre cas envisageable est celui d’une entreprise. Considérons l’exemple suivant : une entreprise souhaite placer les fonds qu’elle utilise pour ses dépenses courantes à une adresse Bitcoin administrée par un bureau de 10 personnes. Une stratégie envisageable serait de créer une «  6-parmi-10 »  adresse. La majorité des voix serait alors requise pour dépenser les fonds.

Le mécanisme de création d’une « m-parmi-n » adresse peut être formalisé comme suit :

  1. Les n parties prenantes génèrent une paire clé privée/clé publique (on a donc n paires)
  2. À partir des n clé publique, générer une « m-parmi-n » adresse grâce à une fonction spécialeaddmultisigaddress

4. Protéger sa clé privée

Si vous avez bien suivi, vous devez avoir compris à quel point votre clé privée est précieuse. Si vous l’égarez, personne ne sera en mesure de la retrouver, et les fonds associés à l’adresse correspondante seront définitivement perdus.

Le système de mulltisignature peut être utilisé pour protéger une clé privée (ou plutôt les fonds disponibles à une adresse). Par exemple, vous pourriez créer une « 2-parmi-3 » adresse, garder l’une des clés en votre possession, confier la seconde à un tiers de confiance (comme une banque) et conserver la dernière en lieu sûr. Pour effectuer une transaction, vous auriez à envoyer une requête au tiers de confiance, qui fournirait la deuxième signature requise (la première étant celle de la clé en votre possession) en échange d’une preuve d’identité. Dans le cas où vous perdriez votre clé, il suffirait de récupérer celle stockée en lieu sûr pour avoir accès aux fonds.
Bien évidemment, il est possible d’augmenter le nombre de clés pour baisser la probabilité de perdre l’accès à votre argent (« 2-parmi-4 »,  « 2-parmi-5 »), mais cela se fait au détriment de la sécurité de votre adresse. En effet, plus il y a de clés, plus la probabilité que quelqu’un mette la main sur au moins deux d’entre elles est importante. Tout est affaire de compromis…

En pratique, très peu de wallet permettent une protection via multi-signature. C’est pourquoi il est primordial de sauvegarder (backup) sa clé privée dans plusieurs endroits sûrs. Entre autres, vous pouvez garder une copie sur votre ordinateur, une dans une clé usb et une imprimée sur papier (ce n’est pas un conseil, juste un exemple).

Dernière petite précision, concernant Ethereum cette fois. Les wallet Ethereum vous demandent généralement un mot de passe pour générer une paire clé privée/clé publique. Cela ajoute un niveau de sécurité à votre compte : si quelqu’un obtenait votre clé privée (encryptée avec votre mot de passe), il ne pourrait pas accéder à vos fonds sans ce mot de passe.
Certains wallet comme MyEtherWallet vous fournissent votre clé privée non encryptée. Bien que plus facile à utiliser (pas besoin de taper le mot de passe), elle est également plus vulnérable, donc faites bien attention !
Dans tous les cas, n’oubliez pas de sauvegarder votre clé privée ET votre mot de passe ! Pour plus d’informations :https://www.ethereum-france.com/creer-et-gerer-son-portefeuille-dether-en-2-minutes-avec-myetherwallet-com/.

[Article rédigé par Gautier MARIN-DAGANNAUD pour Ethereum France]

II. UTXOs, ou comment s’assurer que l’émetteur possède suffisamment de fonds

Contrairement aux banques traditionnelles (et à Ethereum !), le registre maintenu par le réseau de noeuds ne contient pas la balance associée à chaque adresse.

Pour calculer la balance d’un compte (NB : on définit par compte une paire clé privée/clé publique), un noeud fait la somme des « sorties de transaction non dépensées » (Unspent Transaction Output ou UTXO) associées à l’adresse du compte considéré.
Derrière ce nom barbare se cache une réalité relativement simple : pour justifier sa validité, toute transaction référence en entrée une ou plusieurs transactions passées dont la somme des sorties est supérieure ou égale à son montant. Ce mécanisme de référencement entraine la formation d’une chaine de transaction.

La chaîne de transaction a une propriété fondamentale : une transaction peut référencer de multiples UTXOs en entrée et en sortie, mais un UTXO spécifique ne peux être utilisé qu’une fois en tant qu’entrée. Cela permet d’empêcher que la même somme d’argent ne soit dépensée deux fois.
Les UTXOs sont stockés dans une base de données dont chaque noeud possède une copie. À chaque transaction validée, la base de données est mise à jour.

Pour mieux comprendre, considérons l’exemple suivant. Supposons que Alice souhaite envoyer 15 BTC à Bob. Pour ce faire, elle doit, lors de l’initiation de la transaction, renseigner en entrée une ou plusieurs transactions lui ayant été adressées, dont les sorties n’ont pas été dépensées et dont la valeur totale est supérieure ou égale à 15 BTC.
Le schéma ci-après illustre de manière très simplifiée le fonctionnement de la chaîne de transaction ayant amenée à cette opération. On suppose qu’à T<0 la base de données des UTXOs ne contient que deux UTXOs, l’un de valeur 14 BTC, affecté à l’adresse de Carl, et l’autre de valeur 4 BTC, affecté à l’adresse de David. À T=0, Carl et David effectuent une transaction à destination de Alice puis, à T=1, Alice effectue une transaction à destination de Bob.

Chaîne de transaction Bitcoin simplifiée

Comme indiqué sur le schéma, toute transaction doit indiquer une ou plusieurs entrées, chacune référençant une sortie de transaction non dépensée (c’est à dire présente dans la base de données des UTXOs) et dont l’adresse correspond à l’adresse de l’émetteur. Pour pouvoir utiliser cet UTXO, il faut que l’émetteur fournisse une signature digitale qui prouve qu’il possède bien la clé privée associée à l’adresse de l’UTXO.
Notez aussi que pour chaque transaction, la somme des entrées est égale à la somme des sorties. Par exemple, pour la transaction 5, Alice souhaite envoyer 15 BTC à Bob. Elle doit donc référencer des UTXOs dont la somme des montants est supérieur ou égale à 15 BTC. Il est important de bien comprendre que les UTXOs ne sont pas divisibles. Alice doit donc utiliser ses 2 UTXOs, dont la valeur totale est de 16 BTC. Pour récupérer le change de 1 BTC, Alice « crée » une sortie de 1 BTC affectée à son adresse. Alors, la base de données des UTXOs ajoute un UTXO de valeur 1 BTC, que Alice sera en mesure d’utiliser plus tard.
Dans le cas où la somme des entrées n’est pas égale à la somme des sorties, la différence (Total sortie – Total entrée) est considérée comme un frais de transaction et peut être affectée au mineur de la transaction (nous verrons ce que cela signifie un peu plus tard).

Bien entendu, la chaine de transaction Bitcoin est en pratique beaucoup plus massive que celle présentée ci-dessus. Lorsqu’un noeud se connecte au réseau pour la première fois, il doit constituer sa base de données des UTXOs. Pour ce faire, il parcourt l’ensemble de toutes les transactions jamais effectuées et enregistre dans la base toute sortie de transaction non dépensée. Ce processus est long, il peut prendre jusqu’à plusieurs heures, mais n’a besoin d’être effectué qu’une seule fois. Après, un noeud synchronise sa base de données en temps réel.

À ce stade, il nous reste une question à éclaircir : d’où vient l’argent ? En effet, si pour dépenser des Bitcoin il faut référencer une ou plusieurs transactions où l’on a reçu au moins autant de Bitcoin, comment ces Bitcoin sont-il apparus à l’origine ? En réalité, la création de Bitcoin est en lien étroit avec le système de blockchain et de Mining. Nous verrons tout cela en détails dans très peu de temps. Pour l’instant, retenez simplement que des bitcoin « sortis de nul part » peuvent être attribués à certains noeuds à certains moments de la vie de la blockchain.

Nous pouvons désormais exprimer en paradigme le mécanisme de validation d’une transaction par un noeud :

  1. Pour chaque entrée dans la transaction :
    – Si l’UTXO référencé n’est pas dans la base de données des UTXOs, retourner une erreur
    – Si la signature fournie ne correspond pas à celle du propriétaire de l’UTXO (i.e. pas la même adresse), retourner une erreur
  2. Si la somme des montants des UTXOs référencés en entrée n’est pas égale à la somme des montants des UTXOs en sortie, retourner une erreur
  3. Mettre à jour la base de données des UTXOs

Et voilà, vous savez désormais comment les transactions sont validées ! Nous allons maintenant pouvoir aborder le fonctionnement de la blockchain en toute sérénité !

[Article rédigé par Gautier MARIN-DAGANNAUD pour Ethereum France]

III. Ordonner chronologiquement les transactions à l’échelle du réseau : la blockchain

Nous avons vu comment les transactions sont validées individuellement au niveau de chaque noeud. Il est temps désormais de passer au niveau supérieur, et de voir comment le réseau s’organise dans son ensemble.

1. Modèle sans consensus

Un des principaux challenges d’un système décentralisé est de parvenir à un consensus. Ce challenge est particulièrement compliqué lorsque les noeuds de ce système sont anonymes, atomisés et pas nécessairement bien intentionnés. Jusqu’ici, nous avons vu que le registre des comptes était entretenu par des noeuds qui en possèdent chacun une copie. Cependant, pour que l’on sache exactement qui possède quoi, il faut que le réseau s’accorde sur une version du registre. Afin de mieux comprendre, considérons l’exemple suivant, où le réseau n’aurait pas de moyen de s’accorder.

Alice souhaite attaquer le réseau en dépensant deux fois la même somme d’argent (double-spend attack). Nous supposons qu’aucun noeud ne modifie malicieusement le registre. Ainsi, chaque noeud met à jour sa version du registre à chaque fois qu’il reçoit une transaction valide.
Alice crée une première transaction (Tx 1) à destination de Bob, d’un montant de 15 BTC, en échange de quoi Bob lui envoie un objet. Une fois l’objet reçu, elle crée une seconde transaction (Tx 2) à destination d’elle-même et référence en entrée les même UTXOs que pour la transaction précédente.

Double-spend attack dans modèle sans consensus

Double-spend attack dans modèle sans consensus

Ici, du fait de la différence de temps de propagation, le noeud N reçoit la transaction 1 après la transaction 2. N a déjà mis à jour sa base de données des UTXOs, il considère donc la transaction 1 comme invalide, car elle utilise en entrée un UTXO qui n’est plus dans sa base. De manière générale, le réseau n’est pas d’accord sur qui possède les 15 BTC. On peut penser qu’il suffirait d’ajouter la date d’initiation à la transaction, mais il faut se rappeler que le système est décentralisé, et que les noeuds ne doivent à priori pas se faire confiance. En effet, il serait très simple de manipuler cette date pour tromper le réseau. Ce n’est donc pas une solution viable.

2. Les bases de la Blockchain

Pour pallier ce problème, Bitcoin propose d’enregistrer de manière ordonnée et horodatée les transactions dans une chaîne de blocs avec laquelle chaque noeud se synchronise : c’est la blockchain. Toutes les 10 minutes, un nouveau bloc de transactions est ajouté à la chaîne. On considère que toutes les transactions d’un même bloc ont eu lieu au même moment.
Chaque bloc est constitué de deux parties : une liste de transactions, c’est son contenu, et un en-tête, qui décrit certaines informations relatives au bloc (plus de détails dans la partie Preuve de travail).

L’ajout de bloc s’effectue au niveau de chaque noeud. Ainsi, tous les noeuds possèdent une copie de la blockchain identique (à quelques subtilités près). Chaque bloc référence le bloc précédent, ce qui forme une chaine de bloc, qui s’étend jusqu’au genesis bloc, le tout premier bloc jamais créé.

Il est important de ne pas confondre la chaine de bloc et la chaine de transaction que nous avons évoquée dans l’article précédent. Chaque transaction contenue dans un bloc référence en entrée une ou plusieurs transactions ayant été incluses dans des blocs précédents, formant une chaîne de transaction dont les branches sont multiples. Les blocs sont quant à eux reliés les uns aux autres, chacun pointant vers le bloc précédent, ce qui forme une chaine de bloc qui, sur le long terme, est constituée d’une branche unique.

Fonctionnement simplifié de la blockchain

Fonctionnement simplifié de la blockchain

Le problème présenté dans l’exemple du modèle sans consensus est donc (en partie) résolu. Il suffit que Bob attende que la transaction soit incluse dans un bloc avant d’envoyer le produit. La blockchain étant identique pour chaque noeud, il n’y aura pas de désaccord, l’argent est bien à lui !
Sauf que… pas tout à fait. Certaines attaques sont encore possible. Pour comprendre lesquelles, il convient de s’intéresser au mécanisme de création d’un nouveau bloc.

3. Preuve de travail (PoW)

Lorsqu’un noeud reçoit une nouvelle transaction, il la place dans ce qu’on appelle « l’ensemble des transactions non confirmées ». Cet ensemble est propre à chaque noeud, et peut différer d’un noeud à l’autre, du fait du temps de propagation des transactions sur le réseau. C’est une sorte de liste d’attente pour transactions, qui en sortent une fois qu’elles sont incluses dans un bloc.
N’importe quel noeud peut collecter un certain nombre de transactions dans sa liste, vérifier leur validité et former un bloc. Cependant, le bloc n’est pas valide tant que la « preuve de travail » (de l’anglais Proof of Work ou PoW) associée au bloc n’est pas valide. Cela permet entre autres au réseau de ne pas avoir à choisir entre des milliers de blocs possibles mais de s’accorder sur un seul candidat (i.e. sur un set de transactions valides).
Attention, il faut bien faire la différence entre set de transactions valide et bloc valide. Un set de transactions est valide si l’ensemble de ses transactions est valide (pour rappel, un set de transactions constitue le contenu d’un bloc). Un bloc est quant à lui valide si son set de transactions est valide ET si la preuve de travail associée à ce bloc est valide (+ 2 autres conditions, cf. algorithme de validation de bloc plus bas). La preuve de travail n’est pas une preuve de validité du set de transactions, mais une preuve que le mineur a résolu le problème mathématique de non-dépassement de seuil correspondant au bloc (expliqué ci-après).

Il est essentiel de bien comprendre ce qu’est la preuve de travail, car c’est l’un des mécanismes de sécurité fondamentaux du réseau.
Une fois que les transactions non confirmées sont validées et incluses dans le bloc en préparation, le noeud calcule l’en-tête du bloc. Cet en-tête contient 6 éléments : la version du bloc (définit son type et les règles qu’il suit), l’empreinte (que nous appellerons hash) du bloc précédent, la racine de l’arbre de transactions (plus de précisions plus bas), la date, la difficulté et un nonce.

À ce stade, il nous faut expliquer ce qu’est une fonction de hachage. Une fonction de hachage est une fonction à sens unique qui produit un hash à partir d’un message donné. Comme pour les fonctions vues dans la partie clé privée/clé publique, il n’est pas possible de retrouver le message à partir du hash, et tout changement même infime dans le message implique un important changement du hash (NB : On parle ici de message, mais on peut très bien produire un hash à partir d’un fichier. Après tout, un fichier n’est qu’un gros message informatique).
Bitcoin utilise la fonction de hachage SHA-256, qui produit un hash de 256 bits de longueur (voir ci-dessous).

hash

Voyez à quel point le hash change après simple ajout d’un point d’exclamation !

Revenons à notre en-tête. Pour le moment, nous ne nous attarderons pas sur les 4 premiers éléments (nous supposons qu’ils sont facilement identifiables). Restent la difficulté et le nonce. C’est sur ces deux éléments que va s’effectuer la preuve de travail.

L’idée est la suivante : le hash de l’en-tête du bloc doit, pour que la preuve de travail soit valide, être inférieur à un certain nombre que l’on nomme seuil et qui est défini par la difficulté. Comme les 4 premières informations changent à chaque bloc et qu’il est impossible de prédire la valeur du hash sans appliquer la fonction SHA-256, la seule manière d’obtenir un hash valide est de tester différents nonce jusqu’à obtenir un hash correspondant au niveau de difficulté.

En regardant la forme d’un hash, il est légitime de se demander comment on peut comparer un tel message avec un nombre. En réalité, le hash est un nombre hexadécimal, ce qui signifie que les chiffres qui le composent sont dans l’ensemble {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}, où (a,b,c,d,e,f) correspond à (10,11,12,13,14,15). Pour convertir le hash en base décimale (celle que nous utilisons tous les jours), il faut multiplier chaque chiffre par 16i, i étant la position du chiffre dans le hash, en partant de la droite et à partir de 0.

Exemple : 2ba5 = 2*163 + 11*162 + 10*161 + 5*160 = 8192 + 2816 + 160 + 5 = 11 173.

Un hash est composé de 64 chiffres, sa valeur est donc majorée par 1664. Le seuil fixe une limite inférieure à 1664, afin que la recherche de hash ne soit pas triviale (en d’autres termes, qu’elle demande un effort de calcul à l’ordinateur).

Par exemple, si on place un seuil à 1658, l’ordinateur devra calculer des hash en incrémentant le nonce à chaque échec, jusqu’à en trouver un inférieur à 1658, ou qui commence par 000000 (64-58=6 zéros), ce qui revient au même. En effet, un hash de la forme 000000xxx….xxxx sera forcément inférieure à 1658, puisque toute somme de termes de la forme x*16i où i<58 et x<16 ne peut jamais dépasser 1658.

On comprend ici que plus le seuil est bas, plus le nombre de 0 requis en début de hash est important, et donc plus il est difficile de trouver un nonce valide.

Vérification de la validité de l’en-tête du bloc

Vérification de la validité de l’en-tête du bloc

En paradigme, la preuve de travail peut être exprimée comme suit :

Tant que (valeur du hash) ≥ seuil :

1.  Calculer le hash de l’en-tête du bloc
2.  Si (valeur du hash) < seuil, retourner le hash
Sinon, incrémenter le nonce de 1 (=ajouter 1 au nonce)

Pour un noeud seul, il faudrait en moyenne plusieurs années pour trouver un bloc valide. À l’échelle du réseau, la difficulté est établie de telle sorte qu’il faut en moyenne 10 minutes pour qu’un noeud trouve un bloc valide. Le noeud « gagnant » ajoute son bloc à la chaîne, on dit qu’il a « miné le bloc ». Il reçoit en compensation une somme fixe déterminée par le réseau (25 BTC aujourd’hui) ainsi que les éventuels frais de transaction (voir partie 1 pour la définition de frais de transaction).
Bitcoin encourage donc les mineurs à entretenir le réseau en les récompensant par une rémunération. C’est par ailleurs de cette manière que les bitcoin sont introduits dans l’écosystème (une chaîne de transactions commence toujours par un UTXO attribué à un mineur).

La preuve de travail a une autre implication d’importance : plus un mineur possède une capacité de calcul élevée, plus la probabilité qu’il trouve le prochain bloc est élevée. C’est pourquoi on a vu se former des « pool », ou coopératives, de mineurs qui mettent en commun leurs capacité de calcul afin de régulariser leur revenus.
La puissance de calcul d’un mineur par rapport à l’ensemble du réseau permet d’estimer ses chances de gagner seul la course au nonce qui produira le hash valide. En pratique, elles sont extrêmement faibles. En revanche, dans une coopérative, la mise en commun de la puissance de calcul permet de trouver des nonces valides plus régulièrement et d’assurer de fait des revenus plus stables aux mineurs qui y participent.

À noter également : plus il y a d’ordinateurs dans le réseau, plus le temps moyen pour trouver un bloc est faible. Pour conserver un temps moyen de bloc à 10 minutes, le réseau ajuste la difficulté tous les 2016 blocs. Le pourquoi de ces 10 minutes sera discuté dans un prochain article.

Dès qu’un mineur a trouvé un bloc valide, il le transmet au réseau. Chaque noeud qui reçoit ce bloc vérifie sa validité grâce à l’algorithme suivant :

  1.  Vérifier que le bloc précédent existe et est valide (revient à vérifier que le hash du  dernier bloc correspond bien à l’élément « hash du bloc précédent » référencé en en-tête du bloc en cours de vérification)
  2.  Vérifier que la date du bloc est supérieure à la date du bloc précédent et inférieure à 2h après
  3.  Vérifier que la preuve de travail est valide (i.e. le hash de l’en-tête du bloc est inférieur au seuil)
  4.  Vérifier l’ensemble des transactions. Si l’une d’entre elles retourne une erreur, stopper et retourner FAUX
  5.  Mettre à jour l’ensemble des transactions non vérifiées et retourner VRAI

Si l’algorithme retourne vrai, le bloc est considéré valide et le noeud l’ajoute à la blockchain. Dans le cas où ce noeud est un mineur, il se met alors à la recherche du prochain bloc : il collecte un nouveau set de transactions dans l’ensemble des transactions non vérifiées et recommence la preuve de travail pour ce set.

4. Temps de latence

Une considération technique à prendre en compte est le temps de latence. Le temps de latence, ou temps de propagation, est le délai entre le moment auquel un bloc valide est émis par un mineur et celui où il est reçu par un noeud. En moyenne, il est de 12.6 secondes. Ce délai explique pourquoi, en fin de chaîne, les noeuds peuvent pendant un certain temps ne pas avoir la même copie de la blockchain (ce sont les subtilités dont nous avions parlé plus haut). En effet, tant que le bloc valide ne s’est pas propagé jusqu’à un mineur donné, celui-ci continue de chercher le prochain bloc. En moyenne, un bloc concurrent valide (pouvant contenir un set différent de transactions valides) peut donc être trouvé pendant 12.6 secondes après que le premier bloc valide ait été trouvé. Dans ce cas, deux blocs valides circulent sur le réseau. Chaque mineur cherche le prochain bloc à partir du premier bloc qu’il reçoit.

En pratique, un mineur recevant un bloc concurrent (donc ayant déjà reçu un bloc valide) ne le rejette pas. Il crée un « fork » (voir schéma ci-après) et mine sur la chaîne du premier bloc qu’il a reçu (i.e. l’élément « hash de l’en-tête du bloc précédent » du bloc qu’il tente de créer a pour valeur celui du premier bloc valide reçu). Si il reçoit un nouveau bloc valide, il passera sur la chaîne dont le dernier bloc est celui à partir duquel le nouveau bloc valide a été miné. C’est une règle fondamentale de la blockchain : la chaîne la plus longue l’emporte toujours.

Switch sur la chaîne la plus longue

Switch sur la chaîne la plus longue

Ainsi, la chaîne retrouve son unicité dès qu’un nouveau bloc (N) est créé, à moins qu’un mineur travaillant sur la chaîne la plus courte trouve un nouveau bloc concurrent dans le temps de latence suivant l’émission du bloc (N).

Dans certains cas extrêmes, des fork peuvent subsister sur de nombreux blocs, mais la règle de la chaîne la plus longue permet d’aboutir à une stabilisation de la chaine au bout d’un certain temps.

5. Nouvelle règle, nouveaux problèmes

Vous souvenez-vous des attaques que nous avions évoqué avant d’aborder la preuve de travail ? Il est temps de les expliquer. La règle de la chaîne la plus longue est bien pratique pour stabiliser la chaîne de blocs et garantir son unicité, mais elle ouvre aussi la porte à une nouvelle forme de double-spend attack.

Reprenons l’exemple de Alice et Bob. Alice envoie 15 BTC à Bob en échange d’un produit. Bob attend que la transaction soit incluse dans la blockchain, puis envoie le produit. Alice crée alors un fork dans la chaîne en amont du bloc dans lequel la transaction à destination de Bob a été incluse, et remplace cette dernière par une autre transaction où elle s’envoie la somme à elle-même. Si Alice parvient à proposer une chaîne plus longue que la chaîne principale, alors tout le réseau adoptera la nouvelle chaîne proposée par Alice, et Bob perdra ses 15 BTC.

forkalice

Bien que théoriquement possible, cette attaque est en réalité très difficile à mener. En effet, pendant que Alice travaille sur sa chaîne, l’ensemble du réseau travaille sur la chaîne principale. Alice, au même titre que l’ensemble des noeuds du réseau, n’a aucun moyen de calculer facilement le prochain bloc (rappelons que dans la preuve de travail le « hash de l’en-tête du bloc précédent » est un des paramètres d’entrée).

Pour qu’elle soit certaine de gagner la « course » à la chaîne la plus longue, il faudrait qu’elle possède une capacité de calcul supérieure à celle du reste du réseau. En d’autres termes, il faudrait qu’elle possède au moins 51% de la capacité totale de calcul du réseau : c’est pourquoi on appelle ce type d’attaque une « attaque 51% ».
Cette attaque explique pourquoi la fin de chaîne est considérée comme moins sécurisée. En effet, plus on part avec un « retard » de blocs important par rapport à la chaîne principale et plus il est compliqué de proposer une chaine plus longue (la difficulté de l’attaque augmente exponentiellement à mesure que l’on recule dans la chaine). On pourrait penser qu’un attaquant puisse décider de laisser son ordinateur tourner pour tenter de rattraper la chaine principale. Même si la probabilité est très faible, en attendant suffisamment longtemps, il pourrait peut-être finir par gagner. Cependant, cette stratégie n’est pas viable économiquement. Le temps moyen pour rattraper la chaine principale en partant avec un retard considérable est si important que la facture d’électricité associée serait colossale. Pour réduire ce temps, il faudrait posséder plus d’ordinateurs, et donc payer plus d’électricité. Une attaque est donc dans tous les cas très coûteuse à réaliser, et ce coût augmente avec le retard par rapport à la chaine principale.

De manière générale, il est conseillé, par mesure de précaution, d’attendre plusieurs blocs avant de considérer une transaction finalisée. En effet, certaines coopératives ont atteint des capacités de calcul très élevées, et pourraient potentiellement mener une attaque à bien. Une coopérative n’a en théorie pas besoin de posséder plus de la moitié de la capacité de calcul du réseau pour mener une attaque à bien. Plus elle a de capacité de calcul, plus ses chances de réussites sont élevées (simplement, la coopérative est certaine de réussir en un temps fini si elle possède plus de 50% de la capacité de calcul du réseau).

attaquefork

Rassurez-vous cependant, les coopératives n’ont de manière rationnelle que peu d’intérêt à effectuer ce genre attaque. En effet, lors d’une attaque, une coopérative peut uniquement inverser une transaction qu’elle a effectuée, elle n’est pas en mesure d’inverser la transaction d’une autre personne, de créer des Bitcoin ou d’envoyer des Bitcoin qui ne lui appartiennent pas. Il en résulte que le bénéfice potentiel est en moyenne négatif tant qu’elle possède moins de 50% de la capacité de calcul du réseau.
De plus, une coopérative n’est pas une entité guidée par une volonté unique, mais est un ensemble constitué d’une multitude de mineurs individuels. Le gérant de la coopérative peut décider de ne pas être honnête, mais, dans ce cas, rien n’empêche les mineurs de quitter la coopérative pour en rejoindre une honnête. Tant que les mineurs constituant une coopérative seront attentifs à la politique de cette dernière (et honnêtes), le risque est minime.

NB : Un article détaillé sur les coopératives, les probabilités de succès d’une double-spend attack et la centralisation du réseau sera disponible prochainement.

 6. Des noeuds et des arbres

Comme indiqué dans le schéma « Fonctionnement simplifié de la Blockchain », l’en-tête d’un bloc contient la racine de l’arbre des transactions.
Chaque bloc contient une liste de transactions organisée dans un arbre de Merkle. Un arbre de Merkle est un arbre binaire dont les feuilles (c’est à dire les éléments de plus bas niveau) sont les transactions, et dont les noeuds intermédiaires sont soit des hash de somme de noeuds intermédiaires, soit des hash de transactions. Le noeud de plus haut niveau est appelé racine, c’est lui qui est inclus dans l’en-tête du bloc.
Attention à ne pas confondre noeud du réseau et noeud d’arbre de Merkle. Le terme noeud dans un arbre binaire désigne les éléments de cet arbre.

Bloc Bitcoin simplifié

Bloc Bitcoin simplifié

L’arbre de Merkle est essentiel à la scalabilité du réseau, c’est à dire à sa capacité à monter en charge. Pour en comprendre la raison, il nous faut d’abord revenir sur la notion de noeud sur le réseau et leur typologie.

Jusqu’à maintenant, nous avons considéré que tout ordinateur connecté au réseau était un noeud vérifiant l’intégralité de la blockchain. En réalité, ce n’est pas tout à fait le cas. Grossièrement, on distingue 3 types de noeuds : les noeuds complets (« full node »), les mineurs et les noeuds légers (« lightweight-node »).
Les premiers sont les noeuds auxquels je vous ai habitués depuis le début de l’article. Ce sont des noeuds vérificateurs : à chaque bloc reçu, ils vérifient l’ensemble des transactions, ainsi que la preuve de travail. Lors de sa première connexion au réseau, un noeud complet télécharge donc l’historique complet de la blockchain, et vérifie au passage toutes les transactions.
Les mineurs quant à eux sont des noeuds complets qui consacrent une partie de leur capacité de calcul à la preuve de travail : ce sont eux qui produisent les blocs.
NB : Si le mineur fait partie d’une coopérative, il ne se connecte pas forcément en tant que noeud complet. La coopérative utilise un nombre de noeuds complets en général inférieur au nombre de mineurs qui la composent.

Les noeuds complets sont indispensables au réseau, mais ils sont également très contraignants à l’usage.
Aujourd’hui, un noeud complet requiert environ 80 Go d’espace disque et 2 Go de RAM. Beaucoup d’utilisateurs n’ont pas autant d’espace, et il est impensable d’envisager l’installation d’un noeud complet sur mobile ! De plus, un noeud complet vérifie l’ensemble des transactions à chaque nouveau bloc, ce qui demande beaucoup de ressources.
À l’inverse, un client léger ne télécharge que les en-têtes des blocs (+ éventuellement quelques transactions qui l’intéressent), ce qui permet de garantir la validité de la preuve de travail et l’intégrité de la chaine de transactions tout en économisant beaucoup d’espace mémoire. En effet, un arbre de Merkle est structuré de telle sorte que tout changement au niveau d’une des feuilles se répercute de noeud en noeud jusqu’à la racine. Par conséquent, si un noeud complet malicieux tentait de remplacer une transaction par une autre dans un bloc donné, un client léger serait capable de repérer la fraude en constatant que le « hash du bloc précédent » du bloc suivant n’a plus la même valeur.

Un client léger doit néanmoins être capable de vérifier la validité des transactions qui le concernent. N’ayant pas de base des UTXOs, il ne peut pas faire une vérification formelle comme celle que nous avons vu dans la partie 1. À la place, il utilise la profondeur du bloc comme garantie de validité. Pour savoir si une transaction lui étant adressée a été incluse dans un bloc, le client léger envoie ce que l’on appelle un filtre de Bloom au réseau. Ce dernier indique que si une transaction est envoyée à une des adresses ayant de l’intérêt pour le client, alors la branche de l’arbre de Merkle correspondante sera téléchargée en plus du header du bloc. Ainsi, le client léger sait dans quels blocs sont incluses les transactions qu’il reçoit. Ensuite, il attend qu’un nombre X de blocs (appelés confirmations) soient ajoutés à la chaîne. Ces X blocs garantissent que suffisamment de travail a été effectué depuis l’ajout de la transaction. Si, par exemple, X=39, le client considèrera une transaction reçue comme valide une fois que 39 blocs auront été ajoutés à la suite de celui qui la contient.

Si les noeuds légers sont très utiles, ils n’en restent pas moins à double tranchant. L’une des principales forces du réseau Bitcoin est la faible dose de confiance requise entre les utilisateurs. Le seul moyen d’être assuré de la validité des transactions est d’utiliser un client noeud complet.
Pour vous en convaincre, considérez un réseau où la plupart des noeuds seraient des noeuds légers. Dans ce cas, il suffirait de corrompre les quelques noeuds complets du réseau pour pouvoir le manipuler, car personne d’autre qu’eux ne valide les transactions.
Il est donc conseillé d’utiliser un client noeud complet pour pouvoir profiter pleinement de l’aspect décentralisé du réseau.

En pratique, le client que vous utilisez pour vous connecter définit votre type de noeud.
Sur Ethereum, Mist est un client noeud complet. Bitcoin propose des SPV-clients (comme Multibit), qui permettent de se connecter en tant que noeud léger. La politique de ces clients est de faire confiance à la majorité des mineurs.

Enfin, la plupart des webwallets ne vous connectent même pas au réseau, ce sont eux qui s’y connectent à votre place. Ce sont donc des services centralisés, dans lesquels vous prenez le risque de placer votre confiance. À bon entendeur !

[Article rédigé par Gautier MARIN-DAGANNAUD pour Ethereum France]

Leave a Reply