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.