Minage égoïste et controverse mathématique : Bitcoin est-il cassé ?

Dans un article paru en 2013 et intitulé « Majority is not enough: Bitcoin mining is vulnerable », Ittay Eyal et Emin Gün Sirer s’intéressent à la possibilité pour un groupe de mineurs de pratiquer un minage dit « égoïste », où ils ne dévoileraient leurs blocs minés au reste du réseau que lorsque certaines conditions seraint réunies, leur assurant, d’après les auteurs, un revenu plus important que leur part « équitable ». Cet article a donné lieu à de nombreuses réactions, et la publication récente (par Sirer et d’autres) d’un nouveau papier, « Selfish Mining Re-examined », a rouvert la controverse. Nous nous efforcerons ici de présenter et d’analyser les arguments des différentes partie prenantes de ce débat passionnant, pour tenter d’en rendre plus accessible la teneur.

Pourquoi c’est important ?

Une première question, à laquelle il faut répondre d’emblée, est la suivante : pourquoi au juste est-il pertinent de s’intéresser à cette problématique ?

Au cœur du fonctionnement de Bitcoin et, à vrai dire, de l’ensemble des cryptomonnaies dont le consensus repose sur la preuve de travail (Proof of Work) se trouve l’idée, fondamentale, que les intérêts des mineurs sont alignés avec ceux du reste du réseau. Cet alignement est garanti par un ensemble de motivations, des incentives, poussant les mineurs à agir honnêtement, à se conformer aux règles du protocole. Ce jeu d’incentives, bien sûr, est représenté par les récompenses de blocs en bitcoins que touchent les mineurs à chaque fois qu’ils minent un nouveau bloc. Cette récompense, composée à la fois de bitcoins nouveaux et de frais de transaction, doit donc pouvoir garantir l’intégrité du réseau en donnant aux mineurs une raison suffisante de se comporter honnêtement.

Contraposée : une stratégie de minage déviante ne sera pratiquée par des mineurs rationnels que si elle est plus rentable que le minage honnête. Dès lors, la complexe question de savoir si, oui ou non, les intérêts des mineurs sont alignés avec ceux de l’ensemble du réseau, peut se ramener à une interrogation plus « simple » : existe-t-il une stratégie de minage déviante plus rentable que le minage honnête ?

Dans leur article de 2013, Eyal et Sirer affirment avoir trouvé une telle stratégie, en la personne du minage égoïste. Sirer va même jusqu’à déclarer, à travers un article de blog introduisant le papier de recherche, que Bitcoin est cassé (« Bitcoin is broken »). Mais qu’en est-il réellement ?

La stratégie de minage égoïste

Dans leur papier, les 2 chercheurs décrivent une stratégie dans laquelle un ensemble de mineurs (une pool) décident de participer au minage, mais sans dévoiler au reste du réseau les blocs qu’ils trouvent – d’où le terme minage égoïste (ou selfish mining). Ou plutôt, en ne les dévoilant qu’à un moment bien choisi pour permettre à la pool de rendre caduque la chaîne « officielle », invalidant ainsi les récompenses obtenues par les mineurs honnêtes et les « transférant » aux mineurs de la pool. Selon Eyal et Sirer, la pool réussit son coup, même s’il contrôle bien moins que la moitié de la hashrate total du réseau. Mais nous y reviendrons. Pour l’instant, regardons plus en détail comment fonctionne cette stratégie.

Lorsque l’attaque commence, la pool égoïste et les mineurs honnêtes partent du dernier bloc de la chaîne « officielle » et tentent de miner le prochain. 2 cas de figure sont alors possibles :

1. Les mineurs honnêtes trouvent un nouveau bloc en premier et le diffusent à l’ensemble du réseau. C’est le cas le plus probable, puisque les mineurs honnêtes rassemblent, par hypothèse, plus de la moitié de la puissance de calcul totale ;
2. Les mineurs égoïstes trouvent un nouveau bloc en premier et le gardent secret. Ce cas est moins probable, mais peut tout de même se présenter.

Dans le cas numéro 1 (les mineurs honnêtes trouvent un bloc en premier), les mineurs de la pool acceptent le nouveau bloc et on se retrouve alors dans la même situation qu’au début de l’attaque. À proprement parler, c’est comme si l’attaque n’avait jamais eu lieu, puisqu’il est normal que les mineurs soient en concurrence pour trouver un bloc avant les autres. Il suffit donc aux mineurs égoïstes de continuer à miner comme si de rien n’était jusqu’à ce qu’au bout d’un moment, le cas numéro 2 (les mineurs égoïstes trouvent un bloc en premier) se produise. Dès cet instant, une course secrète commence entre la pool et le reste du réseau.

Si la pool égoïste a trouvé le bloc en premier, il a maintenant un bloc d’avance sur le réseau, mais comme il n’a pas encore publié ce bloc, personne à l’extérieur n’est au courant. On se retrouve de nouveau avec 2 cas de figure possibles :

2.1. Les mineurs honnêtes rattrapent leur retard et minent un nouveau bloc. La pool publie alors le sien, donnant lieu à une bifurcation de la chaîne (un fork). Nous verrons, dans quelques instants, comment cette bifurcation est résolue, mais il est intéressant de noter, à ce stade, que les mineurs égoïstes ne sont pas certains (loin s’en faut) d’imposer leur chaîne au reste du réseau ;

2.2. Les mineurs égoïstes creusent leur avance en minant un nouveau bloc au-dessus de celui qu’ils ont déjà miné. Leur chaîne secrète mesure maintenant 2 blocs de plus que la chaîne publique « officielle ». À ce stade, leur attaque a réussi : ils la continueront aussi longtemps que possible pour en maximiser le butin, mais ils peuvent l’interrompre dès que la situation menacera de se renverser.

Résolution du fork. Dans le cas 2.1. où deux chaines publiées coexistent, les mineurs choisissent sur quelle chaîne miner (et donc quelle chaîne prolonger) en fonction d’une règle simple inscrite dans le protocole : premier arrivé, premier servi. Si un mineur reçoit d’abord le bloc des mineurs honnêtes, alors il continue à miner sur la chaîne qui se termine par ce bloc. Si, à l’inverse, il reçoit d’abord celui de la pool, alors il minera sur la chaîne des mineurs égoïstes. Bien entendu, les mineurs égoïstes ont eu connaissance de leur propre bloc en premier, donc ils continuent à miner sur leur chaîne – de même, le ou les mineurs honnêtes qui ont trouvé l’autre bloc continuent de miner sur leur chaîne. Mais la diffusion en pair-à-pair des nouveaux blocs au sein du réseau déterminera si certains mineurs honnêtes se rangent, sans le vouloir, du côté des mineurs égoïstes. En jouant sur la dissémination de noeuds de minage un peu partout au sein du réseau, la pool peut augmenter la proportion de ces derniers et s’assurer de plus grandes chances de victoire. Eh, oui ! C’est bien de cela dont il est question. Tôt ou tard, un nouveau bloc sera découvert et l’une des 2 chaînes dépassera l’autre, forçant tous les mineurs à converger sur la première en abandonnant la seconde.

Si ce bloc appartient à la chaîne « officielle » des mineurs honnêtes, alors le bloc des égoïstes est invalidé et il ne gagnent rien (voire perdent, puisqu’ils ont dû dépenser de l’énergie). S’il appartient à la chaîne « égoïste », alors les mineurs de la pool gagnent – soit les récompenses des 2 blocs si c’est l’un d’entre eux qui mine le deuxième bloc, soit une seule récompense (celle du premier bloc) si c’est un mineur honnête embarqué malgré lui sur leur chaîne qui trouve le deuxième bloc.

Profiter de son avance. Dans le cas 2.2 où les mineurs égoïstes ont consolidé leur avance et ont, sur leur chaîne privée, 2 blocs de plus que la chaîne « officielle », ces derniers continuent à miner égoïstement (en secret), tant que leur avance reste strictement supérieure à un bloc. Ils peuvent ainsi avoir 2, 3, 4, 5 blocs d’avance, voire plus s’ils ont de la chance.

Tant que leur avance n’est pas menacée, les mineurs égoïstes gardent leur chaîne secrète et continuent de miner dessus.

Dès que la chaîne officielle a rattrapé son retard au point que la différence de longueur entre les 2 n’est plus que d’un bloc, les mineurs de la pool révèlent leur chaîne. Celle-ci étant plus longue (d’un bloc), les autres n’ont d’autre choix que d’abandonner la leur (et les récompenses de blocs associées) pour rejoindre celle des attaquants, qui empochent les récompenses de leurs blocs.

Dès que l’écart passe sous le seuil des 2 blocs, les mineurs égoïstes publient leur chaîne secrète. Celle-ci étant plus longue, tout le réseau converge sur cette chaîne. Avant la publication de la chaîne secrète, les mineurs honnêtes qui ont trouvé les 2 blocs de la chaîne « officielle » ont gagné les récompenses de blocs associées. Mais parce qu’une nouvelle chaîne plus longue est publiée, leurs blocs (et donc leurs récompenses) sont invalidés.

Une stratégie rentable et contagieuse

Dans le cadre du fonctionnement normal du réseau Bitcoin, les chances pour un mineur de trouver un bloc sont proportionnelles à sa puissance de calcul. Il en découle une certaine notion d’équité : si un mineur possède 5 % de la puissance de calcul totale du réseau, il minera en moyenne 5 % des blocs, et son revenu « équitable » correspond aux récompenses de ces blocs (en moyenne à 5 % du revenu total perçu par l’ensemble des mineurs sur la période considérée).

La stratégie de minage égoïste envisagée par Eyal et Sirer permet d’altérer cette répartition équitable des revenus. Si l’attaque réussit, les mineurs de la pool égoïste obtiennent une part du revenu total bien supérieure à celle à laquelle leur part de la hashrate total leur donne droit en théorie.

Ce qu’il faut bien voir ici et que soulignent les 2 chercheurs, c’est que l’asymétrie de l’information entre la chaîne « officielle » publique et la chaîne privée des attaquants place ces derniers en position de force en leur permettant de choisir pertinemment quand abandonner (pour mieux repartir) et quand finaliser l’attaque pour en tirer le maximum de profits.

Au final, les mineurs égoïstes n’ont pas du tout besoin d’avoir une part très importante de la puissance de calcul totale pour que l’attaque réussisse. Pire encore, des mineurs rationnels cherchant à maximiser leur profit pourraient rejoindre la pool qui les accepterait, car cela augmenterait encore plus le profit de tous. Poussée à l’extrême, cette situation aboutirait vite à une pool concentrant plus de 51 % de la hashrate totale et donc à la fin de Bitcoin tel que nous le connaissons.

Quelle définition de la rentabilité ?

C’est en tout cas ce que pense Sirer au vu des résultats qu’il a obtenus. C’est aussi ce qu’il affirme au travers de son péremptoire « Bitcoin is broken ». Mais les choses sont-elles aussi sombres qu’elles le paraissent ?

Dans un article paru en 2019 et intitulé « De la profitabilité du minage égoïste (On Profitability of Selfish Mining) », Grunspan et Pérez-Marco, dont nous avons déjà eu l’occasion d’analyser ici un article de recherche, remettent en cause les résultats obtenus par Eyal et Sirer.

En effet, et cela n’aura pas échappé aux plus attentifs lecteurs, la définition de la rentabilité mise en avant par Eyal et Sirer est particulière. Dans leur papier, le minage égoïste est rentable si les mineurs de la pool réussissent à obtenir une part de revenus plus importante que leur part de la hashrate (autrement dit, une part non « équitable »), et ce, même si, au passage, ils diminuent le revenu par unité de temps de l’ensemble des mineurs, honnêtes ou égoïstes.

Cette définition si particulière de la rentabilité est liée à la modélisation que font Eyal et Sirer du problème, qui se contente d’observer pour chaque bloc si les mineurs égoïstes le minent (et en perçoivent la récompense) ou non. Le fait que, ce faisant, les attaquants ralentissent le rythme de production des blocs au point de pouvoir gagner moins de bitcoins pendant la durée de l’attaque que s’ils minaient honnêtement, échappe à leur analyse.

Toutefois, Grunspan et Pérez-Marco, reprenant le travail de leurs prédécesseurs en y incluant la variable temporelle, tombent sur des résultats pas si éloignés des leurs. Même au sens traditionnel de la rentabilité (les rentrées d’argent par unité de temps), la stratégie de minage égoïste est plus rentable que le minage honnête au bout d’un certain temps. Ce « au bout d’un certain temps » est primordial. Les attaquants doivent attendre un ajustement de difficulté à la baisse pour que leur rentabilité dépasse celle des mineurs honnêtes. Le moyen le plus sûr pour les attaquants est donc de commencer leur attaque juste après l’ajustement de difficulté précédent. De cette façon, l’impact de la disparition apparente de leur puissance de calcul du réseau, par moment, pendant la période d’environ 2 semaines qui sépare 2 ajustements, sera d’autant plus important. Ensuite, suivant leur part de la hashrate totale et l’efficacité avec laquelle leurs blocs sont propagés au reste du réseau (ce qui, rappelons-le, permet que des mineurs honnêtes minent sur leur bloc en cas de fork), la durée avant que la stratégie ne devienne rentable varie. Elle est d’autant plus courte que la part du pool dans la puissance de calcul totale est importante et que la diffusion de ses blocs est efficace (de 2 semaines pour une pool déjà importante à plusieurs mois pour une pool plus minoritaire). On perd donc ici l’un des résultats les plus importants d’Eyal et Sirer, à savoir qu’une pool, même toute petite, pouvait menacer Bitcoin. Il apparaît ici qu’il le peut, certes, mais au bout d’un temps très long.

Grunspan et Pérez-Marco observent également, comme Eyal et Sirer, que la rentabilité supérieure du minage égoïste risque d’attirer les mineurs rationnels dans la pool et que les mineurs déjà présents dans la pool ont toutes les raisons de les accepter, car plus il y a de mineurs égoïstes, plus la rentabilité par mineur égoïste est importante. On retrouve donc a priori le résultat inquiétant mis en avant précédemment et justifiant l’apocalyptique « Bitcoin is broken ».

Sauf que, nuancent nos 2 chercheurs français, une telle convergence des mineurs au sein de la pool implique qu’ils aient tous connaissance de la technique et de sa rentabilité supérieure, et même qu’ils savent exactement quel pool la pratique et à quel moment. Non seulement le caractère secret de l’attaque, si nécessaire à sa réussite, semble évincé, mais vue la durée nécessaire pour que l’attaque devienne réellement rentable, il y a toutes les chances pour que des contre-mesures soient prises entre temps pour la faire échouer. Cela est surtout valable si la pool n’est pas très grosse, comme nous l’avons vu, quelques lignes plus haut.

Le minage égoïste réexaminé

Dans un nouveau papier intitulé « Selfish Mining re-examined », Negy, Rizun et Sirer reprennent les travaux de 2013 en intégrant les critiques qui y ont été apportées. Cela prend en compte notamment le facteur temporel qui pousse les auteurs à envisager une nouvelle stratégie : le minage égoïste intermittent (Intermittent Selfish Mining, rien à voir avec le monde du spectacle). Dans celle-ci, le ou les attaquants commencent par appliquer la procédure du minage égoïste vu plus tôt pendant toute une période, afin de faire baisser la difficulté de minage. Puis, l’ajustement survient, et les attaquants se mettent à miner honnêtement en profitant d’un meilleur rythme de découverte des blocs grâce à l’ajustement de la difficulté.

Cependant, il y a un « mais ». Ou plutôt, un « meh ». Sans rentrer dans les détails stériles du conflit qui semble opposer Sirer à certains détracteurs (et notamment notre duo de chercheurs français), les auteurs de ce nouveau papier semblent bien ne tirer que partiellement parti des apports de leurs critiques. De plus, même si Negy, Rizun et Sirer affirment que la stratégie du minage égoïste intermittent (MEI) est au bout d’un moment plus rentable que le minage honnête (même au sens traditionnel comparant le revenu par unité de temps du MEI à celui du minage honnête), ce résultat est basé sur des simulations dont le code n’est pas accessible, et aucune démonstration vérifiable n’est donnée. Notons tout de même que les simulations de Sirer et al. et des calculs menés par Grunspan et Pérez-Marco parviennent à un même résultat : il faut à la pool une part de la hashrate total assez importante (au moins 37 %) pour que l’attaque soit rentable. On est donc loin de l’attaque possible pour un groupe de mineurs très minoritaire annoncée en 2013.

La discussion scientifique est un processus qui n’est pas sans friction. Le cas qui nous a occupés ici en est un exemple. Mais nous avons tâché, dans cet article, de détourner notre regard des algarades diverses, pour nous concentrer sur le sujet d’étude. Que peut-on en dire ? Que les avis divergent sur la durée au bout de laquelle la stratégie de minage égoïste, puis celle de minage égoïste intermittent,sont rentables. Mais convergent pour dire que ces deux techniques sont bien rentables au bout d’un certain temps (mais tout de même, la différence est de taille).

Ce qui saute aux yeux, en revanche, c’est comment nous sommes passés d’un premier papier annonçant la centralisation (et donc la fin) inéluctable de Bitcoin à cause d’un mauvais alignement des incentives des mineurs, à une conclusion beaucoup plus sobre où une pool de minage disposant d’une puissance de calcul non négligeable serait en mesure, au bout d’un temps plus ou moins long, de dégager un revenu supérieur à celui des mineurs honnêtes.

À la réflexion, le fait qu’une pool de minage contrôlant près de 40 % de la hashrate totale soit capable d’influer sur la difficulté et son mécanisme d’ajustement au poins d’en perturber l’équilibre ne semble ni aussi étonnant ni aussi catostrophique que certains voudraient le faire entendre.

Sources

Les papiers de recherche

Majority is not Enough : Bitcoin Mining is Vulnerable (Ittay Eyal, Emin Gün Sirer)

On profitability of selfish mining (Cyril Grunspan, Ricardo Pérez-Marco)

Selfish Mining Re-Examined (Kevin Alarcón Negy, Peter Rizun, Emin Gün Sirer

Les articles de blog

Bitcoin is Broken (Ittay Eyal et Emin Gün Sirer)

Contre-vérités et pratiques malhonnêtes de pseudo-chercheurs dans le monde de la crypto-finance (Cyril Grunspan)