Satoshi Nakamoto a conceptualisé Bitcoin en 2008 et a inventé au passage un algorithme de consensus novateur fondé sur la preuve de travail. Ce dernier permet aux nœuds du réseau pair-à-pair d'arriver à un accord sur le registre de propriété et d'assurer le traitement décentralisé des transactions.
Mais cet algorithme est parfois le sujet d'une certaine confusion. D'un côté, il arrive qu'on le confonde avec le mécanisme de preuve de travail lui-même, ou bien avec la fonction de hachage SHA-256 qui intervient dans le procédé. De l'autre, une erreur répandue est de penser qu'il repose sur une application naïve du principe de la « chaîne la plus longue », tel que décrit dans le livre blanc de Bitcoin. Voyons ce qu'il en est réellement.
La preuve de travail
Contrairement à ce que l'on pense, la preuve de travail n'est pas un moyen d'arriver au consensus sur le réseau, même si elle joue un rôle essentiel dans ce processus.
La preuve de travail est en effet un mécanisme de résistance aux attaques Sybil, qui empêche un acteur de multiplier les identités à l'excès pour prendre le contrôle du réseau, ici la confirmation des transactions. Une attaque Sybil est une attaque intervenant au sein d'un réseau ouvert basé sur un système de réputation qui consiste à se dupliquer à moindre coût pour en altérer le fonctionnement. C'est un problème particulièrement présent sur les médias sociaux par exemple, où les comptes de robots sont utilisés en masse pour augmenter la visibilité d'un contenu donné.
La preuve de travail résout ce problème en demandant aux utilisateurs de démontrer de manière objective et quantifiable qu’ils ont dépensé de l’énergie et en discriminant ainsi les participants entre eux1. Dans le cas de Bitcoin, elle sélectionne le mineur qui choisit le nouveau bloc de transactions étant ajouté à la chaîne. Comme l'écrivait Satoshi :
« La preuve de travail résout [...] le problème de la détermination de la représentation dans la prise de décision majoritaire. Si la majorité était basée sur le principe de vote par adresse IP (une adresse IP, une voix), elle pourrait être détournée par toute personne capable de s'octroyer de nombreuses adresses IP. La preuve de travail est essentiellement basée sur la puissance de calcul : un processeur, une voix. La décision majoritaire est représentée par la chaîne la plus longue, sur laquelle le plus grand effort de preuve de travail a été investi. »
L'idée est de requérir une dépense d'énergie externe pour ajouter un bloc à la chaîne, en échange de quoi le mineur reçoit une récompense composée de bitcoins issus de la création monétaire et des frais de transaction.
Plus précisément, la preuve de travail est réalisée par les hachages successifs de l'entête du bloc candidat via la double application2 de la fonction de hachage SHA-256, qui produit des empreintes de 256 bits, soit 32 octets. La preuve consiste à trouver une empreinte qui soit inférieure à une valeur cible déterminée par le protocole, ce qui constitue une collision partielle de la fonction de hachage et rappelle Hashcash. En termes mathématiques, il s'agit de trouver un nonce (n) tel que :
SHA256d( ENTÊTE( n ) ) ⩽ valeur_cible
Puisque la fonction de hachage est supposée impossible à inverser algorithmiquement, le mineur doit se contenter d'essayer un grand nombre de possibilités au hasard pour trouver une empreinte satisfaisant cette inégalité. La probabilité de tomber sur un résultat correct étant connue, cela permet d'estimer une quantité moyenne de travail effectué pour arriver à la solution.
L'empreinte résultante commence nécessairement par un grand nombre de zéros et constitue l'identifiant du bloc. Par exemple, le bloc 630 000 de la chaîne de BTC a pour identifiant :
000000000000000000024bead8df69990852c202db0e0097c1a12ea637d7e96d
Ainsi, la preuve de travail est le bloc lui-même et chaque membre du réseau peut la vérifier facilement en calculant son identifiant.
Le principe de la chaîne la plus longue
Un algorithme de consensus est un mécanisme permettant de parvenir à un accord au sein d'un réseau distribué, qui résout de ce fait le problème des généraux byzantins. Dans le cas des cryptomonnaies, il s'agit de se mettre d'accord sur le registre de propriété qui décrit qui possède quoi. L'algorithme de consensus de Bitcoin s'appelle l'algorithme de consensus de Nakamoto par preuve de travail, en hommage à son créateur, Satoshi Nakamoto.
Dans la section 5 du livre blanc, Satoshi décrivait son algorithme en se basant sur le principe de la chaîne la plus longue. Si ce principe est faillible comme on va le voir, il est néanmoins utile pour se représenter le fonctionnement général du consensus. Voici le processus.
Coordination
« Les nœuds considèrent toujours que la chaîne la plus longue est la chaîne correcte, et continuent à travailler pour la prolonger. »
Tout d'abord, le réseau se comporte de manière attendue : les nœuds se coordonnent en sélectionnant la chaîne la plus longue et les mineurs travaillent à la prolonger. Tout se passe bien et il n'y a qu'une seule branche.
Embranchement
« Si deux nœuds transmettent simultanément des versions différentes du bloc suivant, certains nœuds peuvent recevoir l'une ou l'autre version en premier. Dans ce cas, ils travaillent sur la première version qu'ils ont reçue, mais conservent l'autre branche au cas où elle deviendrait plus longue. »
Puis, un conflit a lieu. Celui-ci peut être créé par un acteur malveillant, mais est généralement engendré de manière accidentelle, à cause de la latence du réseau : deux mineurs valident un bloc à peu près au même moment ce qui fait que les nœuds ne reçoivent pas le même bloc en premier. On assiste alors à un embranchement (appelé fork en anglais) : deux branches différentes également correctes coexistent et il est impossible de déterminer laquelle il faut prolonger.
Notez que ce type d'embranchement accidentel est commun et se produit de temps en temps sur le réseau pour des raisons de latence.
Recoordination
« L'égalité est rompue lorsque la preuve de travail suivante est trouvée et qu'une branche devient plus longue ; les nœuds qui travaillaient sur l'autre branche passent alors sur la chaîne la plus longue. »
Le conflit est enfin résolu lorsqu'une chaîne plus longue (contenant une plus grande quantité de travail accumulée) est partagée sur le réseau. Il se produit alors ce qu'on appelle une recoordination (ou reorganization en anglais) qui réconcilie les nœuds du réseau entre eux.
Les blocs de la branche minoritaire (dits « orphelins ») sont rejetés.
Le fonctionnement de cet algorithme de consensus a deux conséquences :
- La sécurité de confirmation du réseau repose sur la supposition qu'une majorité de la puissance de calcul (« 51 % ») est honnête, et donc sur la concurrence entre les mineurs ;
- La sécurité d'une transaction est statistique, son degré de finalité dépendant de la profondeur à laquelle elle se trouve dans la chaîne (un segment plus long sera plus difficile à récrire pour annuler la transaction).
Bien que l'algorithme de Nakamoto ait des défauts, il est important que ce critère objectif reste en place car il fait partie des éléments qui donnent à Bitcoin sa robustesse. Si un cloisonnement persistant du réseau venait à avoir lieu, par exemple dans le cas extrême où « un pays se [couperait] délibérément et totalement du reste du monde », alors il serait possible pour les deux parties du réseau de se réconcilier une fois la connexion rétablie.
L'ajustement de la difficulté et la quantité de travail accumulée
Dans le livre blanc, Satoshi supposait que la chaîne la plus longue, était nécessairement celle sur laquelle « le plus grand effort de preuve de travail [avait] été investi ». C'est pour cela qu'il a implémenté naïvement le principe de la chaîne la plus longue dans le protocole originel. Ce n'est que le 25 juillet 2010, dans la version 0.3.3 du logiciel, qu'il a redéfini l'algorithme de consensus pour prendre en compte la notion de travail.
Le principe strict de la chaîne la plus longue est bien valide lorsque la difficulté de minage est constante, car alors la quantité moyenne d'énergie dépensée est fonction du nombre de blocs minés. Néanmoins, la difficulté dans Bitcoin n'est pas fixe et subit un ajustement régulier pour faire en sorte que le temps de bloc moyen reste de 10 minutes et que la politique monétaire établie soit respectée.
La difficulté du minage est définie comme une quantité évoluant de manière inversement proportionnelle à la valeur cible du protocole3. Quand la valeur cible diminue, la difficulté à trouver une empreinte satisfaisant l'inégalité augmente. À l'inverse, quand la valeur cible augmente, la difficulté diminue.
Lorsqu'ils minent un bloc, les mineurs incluent dans le bloc un horodatage (timestamp). Cela permet au réseau d'avoir une idée du temps qui passe. Depuis 2016, le temps réseau est le temps médian passé (MTP), qui est défini comme la médiane des horodatages des 11 derniers blocs et qui retarde donc d'environ une heure (6 blocs) sur l'heure UTC. Notez aussi qu'un horodatage ne peut pas se trouver plus de deux heures dans le futur par rapport au temps subjectif du nœud.
L'ajustement de la difficulté se produit tous les 2016 blocs, c'est-à-dire (hormis grosse variation du taux de hachage) toutes les 2 semaines dans le monde réel. L'algorithme d'ajustement est simple : si le temps mesuré dans la période de 2016 blocs est inférieur à 20 160 minutes (temps attendu), alors la difficulté augmente pour se conformer à la puissance de calcul supposée ; s'il est supérieur, alors la difficulté diminue4. Le reciblage est limité à un facteur 4 (multiplication comme division) pour éviter les instabilités. La difficulté de BTC est aujourd'hui 29 570 milliards de fois plus élevée qu'au lancement du réseau en janvier 2009.
Puisque la difficulté a subi une considérable hausse, il aurait été possible d'exploiter le principe de la chaîne la plus longue. Un attaquant disposant d'une certaine puissance de calcul aurait pu générer une branche partant d'un point de la chaîne où la difficulté était très basse5 (typiquement le bloc de genèse), en réécrivant les horodatages pour avoir des intervalles de 10 minutes, et miner une quantité énorme de blocs à la fin pour rattraper la chaîne principale, la difficulté ne pouvant que quadrupler tous les 2016 blocs. L'attaque n'aurait pas été gratuite, mais aurait suffi à détruire Bitcoin dans le cas où une autre solution n'aurait pas été trouvée (ce qui est improbable).
C'est pour cela l'algorithme de consensus a été revu pour prendre en considération le travail, qui est défini comme le nombre moyen de hachages nécessaires pour miner un bloc ou une chaîne de blocs6, plutôt que la longueur de la chaîne pour arriver à un accord sur le réseau. Depuis le 25 juillet 2010, la chaîne à suivre est ainsi déterminée par sa quantité de travail (ou de « preuve de travail ») : la chaîne correcte est la chaîne possédant le plus de travail accumulé. Aujourd'hui le travail de la chaîne de BTC représente plus de 15 000 yottahachages, soit 15 milliards de milliards de milliards de hachages.
Conclusion
Pour que les nœuds du réseau se mettent d'accord sur son registre de propriété, Bitcoin dispose d'un algorithme de consensus appelé l'algorithme de consensus de Nakamoto par preuve de travail. Cet algorithme est à différencier du concept de preuve de travail qui sert de mécanisme de résistance aux attaques Sybil pour sélectionner les mineurs, de sa mise en œuvre qui consiste à produire une collision partielle d'une fonction de hachage et de la fonction de hachage elle-même.
Le consensus se base sur la sélection d'une chaîne de blocs selon sa quantité de travail accumulée, et non strictement de son nombre de blocs comme on l'entend parfois. En effet, si le principe de la chaîne la plus longue tient la route dans une certaine mesure, il ne suffit pas à garantir la robustesse de Bitcoin.
Notes
1. ↑ Il existe d'autres mécanismes de résistance aux attaques Sybil dans les systèmes cryptoéconomiques, ces derniers reposant soit sur l'identification (auquel cas on parle de « preuve d'autorité »), soit sur une quantité d'unités internes au système (auquel cas on parle de « preuve d'enjeu »). La « preuve d'espace » constitue une variante de la preuve de travail, qui repose également sur une énergie externe au système.
2. ↑ Dans le minage, la fonction de hachage SHA-256 est toujours appliquée deux fois, supposément pour éviter les attaques par extension de longueur. La véritable fonction de hachage considérée est donc le double SHA-256.
3. ↑ La difficulté est définie comme diff = cible_max / cible où la valeur cible maximale du réseau est :
cible_max = 0x00ffff × 256(0x1d - 3)
= 0x00000000ffff0000000000000000000000000000000000000000000000000000
4. ↑ La formule d'ajustement de la difficulté est :
nouvelle_cible = ancienne_cible × temps_réel_écoulé / (14 × 24 × 60 × 60)
Le temps réel écoulé est mesuré à partir des horodatages des 2016 derniers blocs, ce qui correspond à 2015 intervalles de temps. L'algorithme est donc défectueux et surestime la puissance de calcul déployée.
5. ↑ Une telle réécriture de chaîne ne pourrait réalistiquement pas être faite aujourd'hui, car des points de contrôle ont été introduits manuellement dans le code pour empêcher une recoordination trop profonde (pratique initiée par Satoshi le 17 juillet 2010). Puisque le dernier point de contrôle est le bloc 295 000 miné le 9 avril 2014, la difficulté est trop haute (6 119 726 089) pour pouvoir rattraper le retard pris sur la chaîne principale.
Il semble également infaisable d'abaisser la difficulté (en espaçant les blocs sur la branche concurrente) pour procéder à la même technique par la suite : le retard pris pour réduire la difficulté serait trop grand.
6. ↑ Le travail d'un bloc est le quotient du nombre d'empreintes possibles (2256) par le nombre d'empreintes satisfaisant le problème :
travail_du_bloc = 2256 / (cible + 1)
Le travail d'une chaîne est la somme des travaux de tous les blocs la composant.
0 Comments