mai 2018 – cyrilgrunspan.fr

One should always play fair when one has the winning cards.

Ci-dessous un résumé détaillé de notre article On Profitability of Selfish Mining écrit en collaboration avec Ricardo Perez-Marco.

1 « Bitcoin is broken »?

Après avoir travaillé sur l’article fondateur de Satoshi Nakamoto, il nous a paru naturel de se pencher sur l’une des attaques les plus commentées sur Bitcoin : la stratégie dite du minage égoïste.

Que n’a-t-on écrit sur ce sujet ! Comme bien souvent, tout est parti d’une discussion sur le forum bitcointalk en décembre 2010. Celui-ci a donné lieu à plusieurs articles (citons Meni Rosenfeld en 2011 et Lear Bahack en 2013). L’un d’entre eux s’est imposé dans cette vaste littérature (443 citations à ce jour sur Google Scholar): Majority is not Enough: Bitcoin Mining is vulnerable.

Ecrit par un professeur de l’université Cornell et un étudiant en thèse devenu professeur assistant au « Technion » en Israël, l’article développe un formalisme bien connu des informaticiens : la théorie des automates (ou « state machine » en anglais). Les auteurs modélisent la stratégie du minage par une chaîne de Markov cachée qui dépend essentiellement d’un paramètre noté γ représentant en quelque sorte la « connectivité » du mineur (voir plus loin).

Ils concluent que si le taux de hachage du mineur est supérieur à $q_{\min} = \frac{1 - \gamma}{3 - 2 \gamma}$ alors la meilleure stratégie pour le mineur consiste à suivre une stratégie déviante de rétention des blocs. En particulier, si $q > \frac{1}{3}$ alors quelle que soit la « connectivité » du mineur, celui-ci a toujours intérêt à suivre une autre stratégie que la stratégie « honnête » consistant à publier les blocs dès qu’ils les découvrent avec une preuve de travail correcte.

Il s’en est suivi des dizaines et dizaines d’articles censés améliorer ladite stratégie et/ou proposant des modifications possibles du protocole Bitcoin, pour le rendre moins vulnérable à de telles attaques. Le professeur de l’université Cornell évoqué plus haut n’a pas hésité à publier sur son blog : « Bitcoin is broken »…

La communauté scientifique semble avoir avalisé cette conclusion. Elle est même enseignée dans un « mooc » proposée par l’Université de Princeton et dans un livre à l’appui du cours. Précisons tout de même, pour nuancer, que cette communauté se réduisait jusqu’à peu à quelques chercheurs seulement se retrouvant généralement dans des conférences comme celle organisée annuellement par l’International Financial Cryptography Association ou Scaling Bitcoin. Même si la stratégie n’a apparemment jamais été mise en pratique (seules quelques personnes affirment l’avoir détectée), l’attaque est considérée comme théoriquement dévastatrice.

Néanmoins, la plupart des articles lus autour du sujet ne nous semblent pas convaincants. Ils se contentent de répéter que la stratégie est efficace car les honnêtes mineurs sont amenés à brûler de l’énergie pour rien ou bien que la proportion des blocs minés par le mineur égoïste dans la blockchain officielle est supérieure à ce qu’il serait s’il minait honnêtement comme les autres mineurs. Une étude quantitative supplémentaire nous a paru nécessaire qui prendrait en compte à la fois le coût de l’attaque et sa durée.

Pour commencer, afin de pouvoir décider si une stratégie est plus rentable qu’une autre, il convient de définir ce qu’on entend précisément par stratégie ainsi que la notion de taux de rentabilité d’une stratégie qui est la notion clé pour tout problème de stratégie de minage.

2 Stratégie et taux de rentabilité

2.1 Définition d’une stratégie

Une stratégie de minage est faite de cycles d’attaque indépendants les uns des autres. Dans chaque cycle, le mineur mine sur une même fourche (« fork » en anglais). La stratégie prend en compte l’état du réseau et des blocs qui ont été précédemment découverts, et indique à chaque instant au mineur le bloc sur lequel il doit miner . Toute stratégie se caractérise par l’instant aléatoire où le mineur revient à son état initial et où le cycle de la stratégie prend fin. Mathématiquement, il s’agit d’un temps d’arrêt.

Pour des raisons techniques, nous ne considérerons que les stratégies dont les temps d’arrêt sont intégrables. Cela ne change en rien la généralité de notre étude. En effet, quel mineur aurait envie de se lancer dans une attaque qui dure en moyenne une éternité ? Cela n’a pas de sens.

Dans la suite, nous confondons parfois « stratégie » et « cycle d’attaque ». Mais en toute rigueur, ces notions sont différentes. Une stratégie est un cycle répété sans arrêt. De fait, un mineur qui suit une stratégie donnée est un peu comme un Sisyphe aveugle transportant sans cesse un rocher au sommet d’une montagne toujours différente et dont il ignore a priori la hauteur.

Sisyphe (1548-1549), Le Titien, Museo del Prado Madrid.

Par exemple, le cycle de la stratégie dite « honnête » dure en moyenne 10 minutes. Elle consiste à sélectionner le dernier bloc officiel de la blockchain officielle et à miner par dessus. L’instant de fin est le temps d’arrêt $T \wedge T'$ (avec par définition $x\wedge y = {\text Inf}(x,y)$ pour tous réels $x$ et $y$ ) où $T'$ désigne le temps de minage interbloc du mineur et $T$ est le temps de minage interbloc du reste du réseau : le mineur mine tant qu’un bloc n’a pas été découvert et dès qu’un bloc est validé par une preuve de travail, le cycle de la stratégie prend fin.

Un mineur honnête n’est rien d’autre qu’un mineur qui répète inlassablement cette stratégie « honnête ». Nous allons décrire plus bas la stratégie « égoïste ». Mais pour l’instant, il n’est pas utile de rentrer dans les détails.

2.2 Taux de rentabilité d’une stratégie

Nous nous posons maintenant la question de la rentabilité d’une stratégie donnée. Cette réflexion est fondamentale et doit constituer le point de départ de toute discussion sur les stratégies de minage. Quand peut-on dire qu’une stratégie est meilleure qu’une autre ? Suivant quel critère quantitatif ?

La bonne notion est celle de pertes et profits PnL (« Profit and Loss » en anglais) par unité de temps. En particulier, aucun argument ne doit être accepté s’il ne prend pas en compte le temps de minage dans les calculs. Gagner un euro ou un bitcoin en 1h, ce n’est pas la même chose que gagner la même somme en un an.

Il faut aussi prendre en compte le coût dépensé pour parvenir à cette fin. Nous considérons donc qu’une stratégie $\xi$ est moins bonne qu’une stratégie $\xi'$ si répétée un grand nombre de fois, la stratégie $\xi$ donne de moins bons résultats que la stratégie $\xi'$ .

Concrètement, supposons que tout compte fait, la stratégie $\xi$ rapporte $R(\xi)$ (R pour revenu), coûte $C(\xi)$ (C pour coût) et dure $\xi$ . En écrivant cela, nous désignons volontairement par la même lettre grecque $\xi$ le temps d’arrêt indiquant la fin de la stratégie et la stratégie elle-même. Toutes ces variables sont aléatoires. On suppose que la stratégie est répétée $n$ fois avec $n$ « grand » (il y a donc $n$ cycles). Au final et avec des notations évidentes, le mineur aura gagné $R(\xi_1) + \ldots + R(\xi_n)$ et aura dépensé $C(\xi_1) + \ldots + C(\xi_n)$ . Le PnL moyen par unité de temps est donc $\frac{R(\xi_1) + \ldots + R(\xi_n) - C(\xi_1) - \ldots - C(\xi_n)}{\xi_1 + \ldots \xi_n}$ .

En divisant par $n$ chacun des membres de la fraction, on obtient $\frac{\frac{R (\xi_1) + \ldots + R (\xi_n)}{n} - \frac{C (\xi_1) + \ldots + C(\xi_n)}{n}}{\frac{\xi_1 + \ldots \xi_n}{n}}$ . En supposant également que les variables aléatoires $R(\xi)$ et $C(\xi)$ sont intégrables (ce fait peut du reste se démontrer sous l’hypothèse « $\xi$ intégrable » que nous avons faite plus haut. Mais il n’est pas nécessaire d’entrer dans les détails techniques ici), la loi des grands nombres montre que ce PnL moyen par unité de temps converge vers $\frac{\mathbb{E}[R(\xi)] -\mathbb{E}[C(\xi)]}{\mathbb{E}[\xi]}$ . C’est donc cette quantité qui va servir d’indicateur de rentabilité.

Par ailleurs, supposons que deux stratégies $\xi$ et $\xi'$ soient également coûteuses i.e. possèdent le même coût par unité de temps. C’est le cas si les deux stratégies de minage nécessitent l’emploi du même matériel (informatique et humain). Alors, dans ce cas,
$\frac{\mathbb{E}[C(\xi)]}{\mathbb{E}[\xi]} = \frac{\mathbb{E}[C(\xi')]}{\mathbb{E}[\xi']}$ et la condition « $\xi$ est moins profitable que $\xi'$ » équivaut à $\frac{\mathbb{E}[R(\xi)]}{\mathbb{E}[\xi]} \leq \frac{\mathbb{E}[R(\xi')]}{\mathbb{E}[\xi']}$ .

Les Joueurs d’échecs, Le Caravage, 1573–1610 ; école. Venise, Galleria dell’Accademia.

Il nous apparaît donc important de dégager la notion de taux de rentabilité d’une stratégie donnée.

Définition 1. Le taux de rentabilité d’une stratégie rapportant un revenu
$R(\xi)$ en un temps $\xi$ est $P(\xi)$ avec $P(\xi) = \frac{\mathbb{E} [R (\xi)]}{\mathbb{E}[\xi]}$ (P pour « profitability ratio» en anglais).

Le raisonnement précédent montre l’assertion ci-dessous.

Proposition 2. Soient $\xi$ et $\xi'$ deux stratégies possèdant le même coût de fonctionnement par unité de temps. Alors, $\xi$ est moins rentable que $\xi'$ si et seulement si $P(\xi) \leq P(\xi')$ .

À titre d’exemple, considérons la stratégie « honnête » pour un mineur qui possède un taux de hachage relatif égal à $q$ . En conservant les notations de la section 2.1, on a $\xi = T \wedge T'$ , $\mathbb{E}[R(\xi)] = qb$ où $b$ désigne la récompense moyenne contenue dans un bloc et $\mathbb{E}[\xi] = \tau_0$ avec $\tau_0 = 600$ s. Donc, le taux de rentabilité de la stratégie honnête est $P(\xi) = \frac{qb}{\tau_0}$ .

2.3 L’honnêteté paie toujours…

Affiche pour le film La Vie d’un honnête homme, Sacha Guitry, 1953

Ayant posé les bases de toute analyse de stratégie de minage, nous allons montrer que la meilleure stratégie de minage est la stratégie honnête.

Lemme 3. Soit $N'(t)$ un processus de Poisson d’intensité $\alpha'$ et $\xi$ un temps d’arrêt intégrable non-nul. Alors, $N'(\xi)$ est intégrable et $\frac{\mathbb{E} [N'(\xi)]}{\mathbb{E}[\xi]} = \alpha'$ .

La preuve s’appuie sur un résultat classique : si $N'(t)$ est un processus de Poisson d’intensité $\alpha'$ , alors le processus de Poisson dit « compensé » $N'(t) - \alpha' t$ est une martingale. Puis, on utilise le théorème d’arrêt de Doob. On en déduit alors le résultat fondamental sur les stratégies de minage.

Théorème 4. Soit un mineur dont la vitesse de validation des blocs est en moyenne égale à $\alpha'$ et soit $\xi$ une stratégie de minage intégrable non-nulle. Alors $P(\xi) \leqslant \alpha' b$ . De plus, on a l’égalité si $P(\xi) = N'(\xi)$ .

En effet, le nombre de blocs découverts par le mineur suit un processus de Poisson $N'$ et le revenu de la stratégie $\xi$ ne peut excéder le nombre de blocs découverts par le mineur durant $\xi$ (sans tenir compte des variations de frais de transaction d’un bloc à l’autre) : $R (\xi) \leqslant N' (\xi) b$ . D’où le résultat d’après le Lemme précédent.

En d’autres termes, le théorème exprime le corollaire suivant.

Corollaire 5. Soit un mineur dont la vitesse de validation des blocs est en moyenne égale à $\alpha'$ . Si, à la fin d’une stratégie (intégrable non-nulle) $\xi$ , tous les blocs minés par le mineur finissent dans la blockchain officielle, alors $P (\xi) = \alpha' b$ . En particulier, la stratégie honnête maximise le taux de rentabilité parmi toutes les stratégies possibles.

A bien y réfléchir, ce corrollaire qui exprime un résultat de « confiance » très profond est assez important. Il explique pourquoi Bitcoin constitue une avancée majeure en théorie des systèmes distribués. Il n’était nullement évident a priori de parvenir à une telle conclusion.

2.4… Mais faut-il revenir dans le droit chemin ?

Alors, l’affaire est-elle pliée ? Le minage égoïste est-il une hérésie ? A priori, il n’y a même pas besoin de décrire la stratégie de minage égoïste. D’après le Corollaire 5 ci-dessus, la stratégie « égoïste » ne pourra être que moins rentable que la stratégie honnête.

En réalité, c’est un peu plus subtil. Si un mineur déviant ayant adopté depuis longtemps une autre stratégie que la stratégie honnête se repent et décide de miner de nouveau honnêtement, le taux de rendement de sa stratégie va certes augmenter sur le court terme mais il va rapidement (au bout de quinze jours) se retrouver dans la même situation qu’au départ avec une vitesse de minage égale à $\alpha' = \frac{q}{\tau_0}$ avec $\tau_0 = 600$ sec. et celle-ci peut être très inférieure à la vitesse de minage des blocs auquel il a pu être habitué en suivant une stratégie alternative.

Il faut en effet distinguer stratégie « honnête depuis le début » où $P (\xi) = \frac{qb}{\tau_0}$ et la stratégie « repentie » où pendant un temps $P (\xi) = \alpha' b$ avec pourquoi pas $\alpha' > \frac{q}{\tau_0}$ mais qui conduit inévitablement à $\alpha' = \frac{q}{\tau_0}$ et $P (\xi) = \frac{qb}{\tau_0}$ après un ajustement de la difficulté.

En réalité, rien n’interdit que l’on ait $P(\xi) \leq \alpha' b$ et en même temps $P(\xi) > \frac{qb}{\tau_0}$ , ceci parce que la stratégie parvient à maintenir une vitesse de découverte des blocs $\alpha'$ supérieure à $\frac{q}{\tau_0}$ . C’est exactement ce qu’il se passe (parfois) avec la stratégie de minage égoïste.

Un apparté concernant le minage et l’ajustement de difficulté

Tous les mineurs en compétition sur le réseau Bitcoin n’ont pas à résoudre le même problème et il y a à chaque fois plus d’une solution possible.

Cependant tous les problèmes de minage se caractérisent par un paramètre essentiel, la difficulté de minage qui change à chaque fois que l’on dispose d’une suite de 2016 blocs validés les uns à la suite des autres.

Pour trouver un bloc, un mineur doit calculer en moyenne une fraction de tous les hashs possibles qui est proportionnelle à la difficulté de minage. Si la difficulté de minage est divisée par un facteur $\delta$ , alors la vitesse de découverte des blocs est multipliée par $\delta$ (en supposant bien sûr que le matériel du mineur reste le même).

Le paramètre $\delta$ est calculé automatiquement par le protocole de la manière suivante : tous les blocs sont horodatés (grâce au paramètre « timestamp » dans l’en-tête des blocs). Ceci permet d’évaluer le temps noté $\tilde{S}_{n_0}$ mis pour valider les $n_0 = 2016$ derniers blocs.

Notons qu’il y a des anomalies dans la suite des « timestamps » mais au bout de $n_0$ blocs, l’erreur est inférieure à une ou deux heures. Sur 15 jours en moyenne, cela correspond généralement à une erreur inférieure à 1%.

La formule d’ajustement de la difficulté est $\delta = \frac{\tilde{S}_{n_0}}{n_0 \tau_0}$ avec $\tau_0 = 600$ sec. D’où l’on voit que si le réseau a été très lent, il se corrige après 2016 blocs et les blocs parviennent plus rapidement par la suite. C’est ainsi que normalement les blocs apparaissent en moyenne tous les 10 minutes.

2.5 Taux de rentabilité d’une stratégie et ajustement de la difficulté

L’effet d’un ajustement de la difficulté est le même pour tous les mineurs. Le revenu du mineur à la fin de sa stratégie $\xi$ ne change pas avec un ajustement de la difficulté : $\mathbb{E}[R(\xi)]$ est invariant par changement de difficulté.

Par contre, après ajustement de la difficulté, la durée moyenne de la stratégie est modifiée. Avec les notations de l’apparté ci-dessus, $\mathbb{E} [\xi]$ est multipliée par $\frac{1}{\delta}$ à chaque ajustement de difficulté avec $\delta = \frac{\tilde{S}_{n_0}}{n_0 \tau_0}$ et $\tau_0 = 600$ sec. Par suite, après ajustement de la difficulté, $P (\xi)$ est transformé en $\delta \cdot P (\xi)$ .

En général, si l’équilibre des forces entre mineurs reste le même, l’ajustement de la difficulté se stabilise autour de 1 : $\mathbb{E}[\delta] = 1$ . Mais si, par exemple une ferme de minage décide d’arrêter de miner, alors le temps moyen de minage interblocs va augmenter et au bout de 2016 blocs, la difficulté va subitement diminuer. A partir de ce moment, la vitesse de validation des blocs va être multipliée par un facteur $\delta > 1$ .

2.6 De l’ennui d’être seul…

Le Vieil Homme Triste (1890), Vincent Van Gogh, Musée Kröller-Müller, Otterlo

Autre fait contraire à l’intuition : assassiner tous ses concurrents mineurs ou plus sobrement les voir tous disparaître simultanément n’apporte pas de supplément de rentabilité. En tout cas, pas immédiatement… Même si un mineur reste seul en piste pour valider tous les blocs, il ne deviendra pas plus riche pour autant ! En effet, en temps normal, le taux de rentabilité du mineur est $qb$ divisé par $\tau_0$ car il y a un nouveau bloc en moyenne toutes les 10 minutes et une probabilité $q$ qu’il soit découvert par notre mineur. Dans le cas où il serait tout seul à miner, son taux de rentabilité est cette fois-ci $b$ divisé par $\frac{\tau_0}{q}$ . En effet, il y a en moyenne un bloc tous les $\frac{\tau_0}{q}$ et une probabilité égale à 1 que ce bloc soit découvert par le mineur. On a $\frac{q}{\tau_0} = \frac{1}{\frac{\tau_0}{q}}$ . Donc, le taux de rentabilité est le même ! Par contre, après un ajustement de la difficulté, le taux de rentabilité du mineur solitaire est multiplié par $\frac{1}{q}$ car les blocs apparaîtront alors en moyenne toutes les 10 minutes, soit beaucoup plus rapidement qu’avant…

3 Stratégie de désertion

Soit un mineur donné de puissance de hachage relative égale à $q$ sur Bitcoin. Il a le choix entre rester sur Bitcoin ou miner sur une autre cryptomonnaie possédant un mécanisme de validation des blocs similaire à Bitcoin avec des preuves de travail et une même fonction de hachage (Bcash par exemple). Changer de blockchain de référence est aussi simple pour lui que d’appuyer sur un bouton. En effet, les algorithmes de preuve de travail sont les mêmes (basés sur la même fonction de hachage SHA256). Supposons que miner sur Bitcoin soit un peu plus rentable que miner sur l’autre cryptomonnaie d’un facteur $\rho$ .

Voici ce que peut faire un mineur pour augmenter son profit. On suppose qu’initialement il mine sur Bitcoin. Pendant un temps, il se retire complètement de Bitcoin et décide de miner uniquement sur Bcash. Il en résulte une diminution de la puissance de hachage totale sur Bitcoin qui se traduit au bout de 2016 blocs par une baisse sensible de la difficulté d’un facteur dont la moyenne est $p = 1-q$ . Par suite, au bout de 2016 blocs, le taux de rentabilité du minage « honnête » sur Bitcoin devient tellement important que la meilleure stratégie du mineur consiste maintenant à retourner sur Bitcoin.

Concrètement, si $\frac{1}{p} > \rho$ , alors le mineur a intérêt à passer régulièrement d’une blockchain à l’autre, ce qui est mauvais pour la vitesse de validation des transactions. Elle est régulièrement ralentie par ce yo-yo des mineurs entre les deux blockchains. Il en résulte que tout fork d’une cryptomonnaie conservant le même algorithme de preuve de travail est potentiellement dangereux pour la stabilité de la blockchain initiale.

Remarquons au passage que si un mineur se retire de Bitcoin, cela ne modifie pas la rentabilité des autres mineurs (voir section 2.6 ci-dessus). En résumé, la stratégie consistant à déserter momentanément Bitcoin pour Bcash est une stratégie qui permet de faire baisser la difficulté sur Bitcoin rendant l’activité de minage plus lucrative après un ajustement de la difficulté et ceci en continuant à gagner de l’argent (grâce aux blocs minés sur Bcash). Elle ne fait pas baisser la rentabilité des autres mineurs (honnêtes) et ne permet pas de stabiliser la difficulté puisqu’après un retour sur Bitcoin et un nouveau cycle de 2016 blocs, la difficulté va inévitablement remonter.

4 Stratégie égoïste

4.1 Un résumé

Nous allons décrire ci-dessous cette stratégie. Mais d’ores et déjà, voici un résumé de l’effet de la stratégie de minage égoïste. Il s’agit d’une stratégie concurrente de la stratégie de désertion évoquée plus haut. Elle partage avec elle trois caractéristiques essentielles :

avant ajustement de la difficulté, le taux de rentabilité du mineur (égoïste) diminue mais le mineur continue à gagner de l’argent
la difficulté baisse après 2016 blocs
après ajustement de la difficulté, le taux de rentabilité du mineur augmente sensiblement et devient même dans certains cas supérieur à ce qu’il était avant ajustement de la difficulté.

Mais la différence majeure avec la stratégie de désertion est la suivante :

la difficulté se stabilise après un ajustement de difficulté

En outre,

le taux de rentabilité des honnêtes mineurs baisse (il est inférieur à ce qu’il serait sans mineur égoïste)

Insistons sur le fait que ceci ne contredit pas le Corollaire 5. A chaque instant, le mineur a certes plus intérêt à être honnête que malhonnête. Mais il s’agit d’un raisonnement à court terme. Si le mineur égoïste se repent et décide de miner honnêtement, il va gagner plus très rapidement. Mais après 2016 blocs la difficulté va augmenter de nouveau et on reviendra à la situation initiale.
Si le mineur reste égoïste, il gagnera toujours plus que s’il minait honnêtement dans les conditions de départ. Et sauf modification de l’équilibre des forces parmi les mineurs, l’avantage que peut en tirer le mineur égoïste va perdurer avec le temps puisque la difficulté sera stable.

4.2 Description

Un mineur égoïste ne révèle pas immédiatement les blocs qu’il mine. Il les garde secrets et ne révèle l’existence de certains d’entre eux qu’au fur et à mesure des découvertes que peuvent faire les honnêtes mineurs.

L’élément déclencheur qui conduit un mineur égoïste à rendre public un bloc miné est toujours du ressort des honnêtes mineurs à une exception près que nous verrons plus tard. Si les honnêtes mineurs découvrent un bloc, alors le mineur égoïste en révèle lui-même un ou plusieurs qu’il tenait secrets (si du moins il en a en réserve). Mais jamais un mineur égoïste ne va prendre seul la décision de publier un bloc.

Concrètement, dans la stratégie décrite dans l’article Majority is not Enough: Bitcoin Mining is Vulnerable, le mineur égoïste publie :

deux blocs si son avance sur la chaîne de blocs officielle est égale à deux et que les honnêtes mineurs découvrent un nouveau bloc (l’avance passe donc de deux à un dans ce cas)
le plus vieux bloc miné si l’avance du mineur est supérieure à deux, à l’instant où les honnêtes mineurs découvrent un bloc
le dernier bloc miné si le mineur n’a qu’un seul bloc d’avance et qu’il est subitement rejoint par les honnêtes mineurs.

Dans tous ces cas, tous les blocs du mineur égoïste sortent de son chapeau au moment-même où l’un des honnêtes mineurs découvre un bloc. Ils étaient déjà minés mais ne sont révélés qu’à cet instant…

Il y a en vérité un cas et un seul où le mineur égoïste publie un bloc immédiatement sans le garder secret. C’est lorsque l’un de ses blocs est en compétition ouverte avec un bloc “honnête” du réseau. C’est le cas si le mineur égoïste découvre un bloc au tout début de la stratégie puis est rejoint par les honnêtes mineurs qui en découvrent un à leur tour. Si le mineur trouve un nouveau bloc avant les autres mineurs honnêtes, le mineur égoïste va sans attendre publier son nouveau bloc et l’attaque prendra fin à cet instant.

Dans les cas 1 et 2 ci-dessus, les blocs du mineur égoïste finissent par s’imposer car ils appartiennent à une chaîne plus longue qui finira tôt ou tard par être révélée entièrement.

Dans le troisième cas, il s’établit un « duel » entre les deux propositions de blocs. Le bloc des honnêtes mineurs ayant été publié quelques instants avant le bloc du mineur égoïste, il a plus de chance d’être repris par tout le réseau et de devenir le nouveau dernier bloc officiel. On peut cependant imaginer qu’une fraction γ des honnêtes mineurs va reconnaître le bloc du mineur égoïste et chercher à miner par dessus. Il est difficile d’imaginer un paramètre γ constant dans le temps (γ proche de 1 est aussi une vue de l’esprit). Cependant, la stratégie est aussi efficace avec $\gamma = 0$ (pour $q \geqslant \frac{1}{3}$ ) bien qu’elle soit plus efficace avec $\gamma = 1$ .

Duel au Gourdin (1819-1823), Francisco de Goya (1746-1828), Huile sur plâtre transférée à la toile, Museo Nacional del Prado, Madrid

Dans tous les autres cas, le mineur égoïste se contente d’ajouter des blocs les uns à la suite des autres sur une fourche (« fork ») tenue secrète.

4.3 Taux de rentabilité de la stratégie égoïste

Notons $\xi$ la stratégie égoïste. Admettons que l’on ait prouvé que $\xi$ est une stratégie intégrable non-nulle p.s et que les espérances $\mathbb{E}[N'(\xi)]$ et $\mathbb{E}[N(\xi)]$ sont finies. Dans toute la suite, on note $T_i$ (resp. $T'_i$ ) les temps de minage interblocs des honnêtes mineurs (resp. du mineur égoïste) et $S_i$ (resp. $S'_i$ ) l’instant de découverte des blocs des mineurs honnêts (resp. du mineur égoiste).

4.3.1 Durée de l’attaque

Notons qu’on a toujours $N'(\xi) = N (\xi) + 1$ sauf si $T_1 \leq T'_1$ ou si $S'_1 \leq S_1 \leq S_2 \leq S'_2$ . Dans ces deux cas on a $N'(\xi) = N(\xi)-1$ . Par suite, $N'(\xi) = N (\xi) + 1 - 2 \cdot 1_{\{ T_1 \leq T'_1 \} \cup \{ S'_1 \leq S_1 \leq S_2 \leq S'_2 \}}$ . Donc, $\mathbb{E} [N' (\xi)] = \mathbb{E} [N (\xi) + 1] - 2 (p + p^2 q)$ . En appliquant le théorème d’arrêt des martingales, on peut en déduire : $\alpha' \mathbb{E} [\xi] = \alpha \mathbb{E} [\xi] + 1 - 2 p (1 + pq)$ . D’où, $\mathbb{E} [\xi] = \frac{(1 + pq) (p - q) + pq}{\alpha - \alpha'}\label{fdu}$ .

4.3.2 Revenu du mineur égoïste

Après une attaque, le mineur égoïste n’est le propriétaire d’aucun bloc orphelin sauf s’il y a eu une compétition ouverte entre le mineur et le reste du réseau dont l’issue lui a été défavorable malgré le soutien d’une fraction $\gamma$ des mineurs honnêtes. Dans tous les autres cas, les blocs minés par le mineur égoïste finissent tous dans la blockchain officielle. Autrement dit, $R (\xi) = N' (\xi) -1_{A \cap B}$ où $A$ est l’événement $\{ S'_1 \leq S_1 \leq S'_2 \}$ et $B$ est l’événement « le conflit est résolu par la fraction $1-\gamma$ des honnêtes mineurs ». On a $\mathbb{E}[N'(\xi)] = \alpha' \mathbb{E}[\xi]$ . Par suite, en utilisant le résultat de la section précédente, on obtient $P (\xi) = \alpha' b - (1 - \gamma) \frac{p^2 q (\alpha - \alpha') b}{(1 + pq) (p - q) + pq} \label{pxi}$ .

4.3.3 Une forme compacte

Il reste à voir que $\xi$ est intégrable, ainsi que $N (\xi)$ et $N'(\xi)$ . Pour cela, il suffit d’écrire $\xi$ sous la forme compacte suivante : $\xi = T_1 \wedge T'_1 + \xi' \cdot 1_{T'_1 \leq T_1} + (T_2 \wedge T'_2) 1_{T'_1 \leq T_1 \leq S'_2}$ avec $\xi' = (T-T_1') \wedge T_2'+\text{Inf} \{ t > 0 / N (T_1'+t +(T-T_1')\wedge T_2')-N(T_1')\geqslant N'(T_1'+t+(T-T_1') \wedge T_2')- N'(T_1') \}$
La propriété de Markov forte montre que conditionnellement à $T'_1$ , $N (t + T'_1) - N (T'_1)$ et $N' (t + T'_1) - N' (T'_1)$ sont des processus de Poisson d’intensité $\alpha$ et $\alpha'$ Par suite, l’intégrabilité de $\xi, N (\xi)$ et $N' (\xi)$ découle du lemme suivant.

Lemme 6. Soit $\tilde{N}$ et $\tilde{N}'$ deux processus de Poisson d’intensité $\alpha$ et $\alpha'$ avec $\tilde{N} (0) = \tilde{N}' (0) = 0$ et $\alpha' \leq \alpha$ . Posons $\tilde{\tau} = \text{Inf} \{ t > 0 / \tilde{N} (t) = \tilde{N}' (t) + 1 \}$ . Alors, $\tilde{\tau} \leq \infty$ p.s., $\tilde{\tau}$ est intégrable, $\mathbb{E} [\tilde{\tau}] = \frac{1}{\alpha - \alpha'}, \mathbb{E} [\tilde{N} (\tilde{\tau})] = \frac{\alpha}{\alpha - \alpha'}$ et $\mathbb{E} [\tilde{N}' (\tilde{\tau})] = \frac{\alpha'}{\alpha - \alpha'}$ .

4.4 Taux de hachage relatif apparent

Supposons que nous soyons maintenant intéressés par le revenu par unité de blocs et non pas par unité de temps. C’est en quelque sorte le taux de hachage relatif apparent du mineur car il correspond à la proportion des blocs minés par le mineur dans la blockchain officielle. Notons le $q'$ .

Les Tricheurs, Caravage, 1594-1595, musée d’art Kimbell, Fort Worth (États-Unis)

4.4.1Nombre moyen de blocs officiels minés durant une attaque

Il est facile de voir que quelle que soit l’issue de la stratégie égoïste $\xi$ , le nombre de blocs officiels minés à la fin de l’attaque est égale à $\frac{N (\xi) + N' (\xi) + 1}{2}$ . En remplaçant $\mathbb{E} [N(\xi)]$ et $\mathbb{E} [N'(\xi)]$ par $\alpha \mathbb{E} [\xi]$ $\alpha' \mathbb{E} [\xi]$ et en reprenant le calcul de $\mathbb{E} [\xi]$ vu plus haut, on obtient $\mathbb{E}\left[ \frac{N(\xi)+N'(\xi)+1}{2} \right] = 1+\frac{p^2 q}{p - q}$

4.4.2 Où l’on retrouve une formule connue…

Par suite, le nombre moyen $x$ de cycles d’attaques nécessaires afin de miner $n$ blocs officiels ( $n$ quelconque) est donné par $x = \frac{n}{1 + \frac{p^2 q}{p - q}}$ .

Chaque attaque rapporte en moyenne $\mathbb{E} [R (\xi)]$ au mineur égoïste. Par suite, d’après les calculs précédents, la proportion moyenne $q'$ de blocs minés par le mineur égoïste vaut $q' = x \frac{\mathbb{E} [R (\xi)]}{n b} = \frac{((1 + pq) (p - q) + pq) q - (1 - \gamma) p^2 q (p - q)}{p^2 q + p - q}$ .

On peut reécrire cette expression sous la forme $q' = \frac{q (1 - q)^2 (4 q + \gamma (1 - 2 q)) - q^3}{1 - q (1 + q (2 - q))}$ qui correspond exactement à la formule (8) pour R_pool dans l’article cité plus haut Majority is not Enough: Bitcoin Mining is Vulnerable.

4.5 Minage égoïste et ajustement de la difficulté

Regardons maintenant l’effet de la stratégie égoïste après que $n_0 = 2016$ blocs aient été minés.

4.5.1 Valeur moyenne de l’ajustement de la difficulté.

Posons comme précédemment $\delta = \frac{\tilde{S}_{n_0}}{n_0 \tau_0}$ où $\tilde{S}_{n_0}$ est le temps mis par le réseau pour valider $n_0$ blocs. Pour obtenir $\mathbb{E} [\delta]$ , il suffit de multiplier le nombre moyen de cycles nécessaire pour valider $n_0$ blocs par la durée moyenne d’une attaque (voir les sections 4.3.1 et 4.4.1). On obtient la proposition suivante.

Proposition 7. On a $\mathbb{E}[\delta] = \frac{p - q + pq (p - q) + pq}{p^2 q + p - q}$ .

4.5.2 Nouveau taux de rendement de la stratégie après un ajustement de la difficulté

D’après la Section 2.5, le taux de rendement de la stratégie est affecté par tout ajustement de la difficulté.

Théorème 8. Après un premier ajustement de la difficulté, le taux de rendement de la stratégie égoïste devient égal au taux de hachage apparent. Autrement dit, $P (\xi) = q' \frac{b}{\tau_0}$ .

En effet, après un ajustement de la difficulté, les vitesses de validation des blocs $\alpha$ et $\alpha'$ qui valaient précédemment $\frac{pb}{\tau_0}$ et $\frac{qb}{\tau_0}$ sont multipliées chacune par $\delta$ dont la valeur moyenne est donnée ci-dessus. Par suite, la nouvelle valeur pour le taux de rendement de la stratégie $\xi$ est $P(\xi) = \left( qb - (1 - \gamma) \frac{p^2 q (p - q) b}{(1 + pq) (p - q) + pq} \right) \cdot \frac{p - q + pq (p - q) + pq}{p^2 q + p - q} \cdot \frac{b}{\tau_0}$ . La formule se simplifie en $P (\xi) = q' \frac{b}{\tau_0}$ .

Ainsi, en menant le calcul correctement, nous retrouvons la conclusion de l’article Majority is not Enough: Bitcoin Mining is Vulnerable qui est donc vraie mais seulement après une période d’ajustement de 2016 blocs.

Corollaire 9. Après un ajustement de la difficulté, la stratégie égoïste devient plus rentable que la stratégie « rester toujours honnête » si $\gamma > \frac{p - 2 q}{p - q} = \frac{1 - 3 q}{1 - 2 q}$

D’après la formule pour $q'$ , le calcul montre que $q' > q$ équivaut à $\gamma > \frac{p - 2 q}{p - q}$ . Cette condition est équivalente à $q > \frac{1 - \gamma}{3 - 2 \gamma}$ qui apparaît ainsi dans l’article précité (formule (9)).

4.6 Taux de rentabilité des honnêtes mineurs en présence de mineurs égoïstes

Tintin, Les Bijoux de la Castafiore, Hergé, 1962.

Au cours d’un cycle d’attaque par un mineur égoïste, les mineurs honnêtes ne parviennent à placer un bloc dans la blockchain officielle que dans les trois cas suivants :

les mineurs honnêtes découvrent un bloc avant le mineur égoïste : $T_1 \leq T_1'$
En cas de conflit, une fraction $\gamma$ des mineurs honnêtes découvrent un bloc avant le mineur égoïste
En cas de conflit, une fraction $1-\gamma$ des mineurs honnêtes découvrent un bloc avant le mineur égoïste

Dans les deux premiers cas, les mineurs honnêtes empochent un bloc. Dans le troisième cas, les mineurs honnêtes empochent deux blocs (le dernier bloc ainsi que le bloc qui était en litige). Par suite, l’espérance du revenu $R_H (\xi)$ des mineurs honnêtes au cours d’une attaque est
$\mathbb{E} [R_H (\xi)] = (p + pq \cdot \gamma p + 2 pq \cdot (1 - \gamma) p) b$

En présence d’un mineur égoïste qui répèterait $n$ fois son attaque, et avec des notations évidentes, le revenu par unité de temps des mineurs honnêtes est $\frac{R_H (\xi_1) + \ldots + R_H (\xi_n)}{\xi_1 + \ldots + \xi_n}$ . En utilisant de nouveau la loi des grands nombres, il en résulte que le taux de rentabilité des honnêtes mineurs en présence d’un mineur égoïste est $P_H (\xi) = \frac{\mathbb{E}[R_H(\xi)]}{\mathbb{E}[\xi]}$ . D’après la formule précédente pour $\mathbb{E} [R_H (\xi)]$ et la Section 4.3.1, on en déduit que $P_H (\xi) = \frac{p (1 + \gamma pq + 2 (1 - \gamma) pq) b}{(1 + pq) (p - q) + pq} (\alpha - \alpha')$ .
Donc, avant ajustement de la difficulté, on a $P_H (\xi) = \frac{p (p - q) (1 + \gamma pq + 2 (1 - \gamma) pq)}{p - q + pq + pq (p - q)} \frac{b}{\tau_0}$ .
De plus, suivant la Proposition 7, après ajustement de la difficulté, on a
$P_H (\xi) = \frac{p (p - q) (1 + \gamma pq + 2 (1 - \gamma) pq)}{p^2 q + p - q} \frac{b}{\tau_0}$ .

Il est possible que l’on ait $P_H (\xi) \leq \frac{pb}{\tau_0}$ . Le calcul montre que c’est le cas si $\gamma > \frac{p - 2 q}{p - q}$ ou de manière équivalente $q > \frac{1 - \gamma}{3 - 2 \gamma}$ , ce qui, d’après le Corollaire 9 est exactement la condition pour que l’attaque devienne rentable pour le mineur égoïste i.e., $P (\xi) > \frac{qb}{\tau_0}$ .

4.7 Et après un nouvel ajustement de la difficulté ?

La difficulté étant ajustée une première fois, si l’équilibre des forces au sein des mineurs n’est pas modifié et si le mineur égoïste persiste dans sa stratégie déviante, le réseau suit un rythme de croisière et la difficulté n’est plus ajustée. Il n’y a qu’à reprendre la formule donnant $\mathbb{E}[\xi]$ pour se rendre compte alors qu’après un premier ajustement de la difficulté, on a $\mathbb{E}[\delta] = 1$ . Donc, sous la condition $q > \frac{1 - \gamma}{3 - 2 \gamma}$ , le mineur arrive à maintenir un taux de rendement important avec la stratégie égoïste, bien plus important que le taux de rendement de la stratégie « honnête depuis toujours ».

5 Une attaque sur la formule d’ajustement de la difficulté

La bataille de Gaugamèles – Relief en ivoire inspiré d’une peinture de Charles Le Brun (1669) au musée du Louvre – Museo Arqueológico Nacional – Madrid

Alors, d’où vient le problème ? La difficulté est censée refléter la puissance de calcul employée pour valider les blocs mais elle ne le fait pas. Elle sous-estime nettement la puissance de hachage réel sur le réseau. En présence d’un mineur égoïste, il n’y a pas moins d’acteurs, mais seules les actions des honnêtes mineurs sont prises en compte par la formule. En effet, la blockchain officielle n’avance plus qu’au rythme des honnêtes mineurs. Sauf exception (lorsqu’il y a compétition ouverte entre deux blocs), ce n’est que lorsqu’un mineur honnête découvre un bloc que la blockchain officielle a une chance d’avancer. Une chance seulement car par principe de la stratégie, si le mineur égoïste a beaucoup d’avance, tous les derniers blocs « honnêtement » minés vont finir par être effacés. Tout ceci ralentit considérablement l’avancée de la blockchain. Et au final, l’ajustement de la difficulté rend l’attaque très lucrative (sous condition sur $q$ ).

Autrement dit, le mineur égoïste vit caché, comme s’il n’était pas connecté sur le réseau. Ceci constitue bien sûr une aberration. Comment faire pour que la formule prenne réellement en compte le travail de tous les mineurs, pas seulement celui des mineurs honnêtes ?

6 Changer de formule d’ajustement de la difficulté

6.1 Prendre en compte la production de blocs orphelins

L’idée est qu’un mineur égoïste, tout égoïste qu’il est, laisse des traces. Il s’agit des blocs minés par les honnêtes mineurs qui sont effacés de la blockchain officielle et des blocs minés par le mineur égoïste lui-même qu’il n’est pas parvenu à placer dans la blockchain officielle (à la suite d’un conflit public dont la résolution lui a été défavorable). Ces blocs minés sont des blocs dits « orphelins ». Ils ne sont pas propagés par le réseau Bitcoin et de fait, il est difficile d’en avoir une valeur exacte. On estime cependant (selon des informations transmises par certains nœuds du réseau) que leur nombre est généralement faible et stable. La production de blocs orphelins est d’environ 1 à 2 % par bloc « officiel ».

Propager tous ces blocs orphelins n’aurait que peu d’intérêt et ralentirait le réseau inutilement. Par contre, si les nœuds du réseau pouvaient propager les preuves de travail très légères accompagnant la création de ces blocs le réseau y gagnerait en stabilité.

Il suffirait que les mineurs insèrent les preuves de travail des « oncles » dans les blocs qu’ils constituent (un « oncle » est un bloc orphelin qui était en compétition avec le bloc parent du bloc nouvellement miné par le mineur).

On pourrait même inciter les mineurs à le faire en décrétant qu’en cas de compétition entre deux blocs, le nœud devrait propager en priorité celui qui aurait détecté le plus d’ « oncles » possibles. Au bout de 2016 blocs, la formule d’ajustement de la difficulté ferait le bilan de tous les blocs orphelins minés. En supposant leur nombre égal à $n'$ , la nouvelle formule d’ajustement serait: $D_{{nouveau}} = D_{{ancien}} \cdot \frac{(n_0 + n') \tau_0}{\tilde{S}_{n_0}} \label{f}$ où $D_{{ancien}}$ désigne la difficulté de minage d’avant l’ajustement de la difficulté et $D_{{nouveau}}$ la difficulté de minage d’après l’ajustement. Autrement dit, au lieu de prendre pour ajustement de la difficulté $\delta = \frac{\tilde{S}_{n_0}}{n_0 \tau_0}$ , on aurait $\delta = \frac{\tilde{S}_{n_0}}{(n_0 + n') \tau_0}$ . Notons par ailleurs (mais c’est anecdotique) que la formule d’ajustement de la difficulté implémentée dans Bitcoin contient un beugue originel puisque seulement 2015 blocs sont pris en compte au lieu de 2016.

6.2 Une rapide analyse de la nouvelle formule

Un calcul simple montre que la formule aurait du sens. En effet, soit $\omega$ le pourcentage de blocs orphelins minés parmi tous les blocs observés durant une période de $\tau_0 = 600$ sec. En moyenne, tous les $\tau_0$ , seule une fraction $1 - \omega$ des blocs minés va s’ajouter à la blockchain officielle. Pour obtenir $n_0 = 2016$ blocs, il faut donc patienter pendant $\tilde{S}_{n_0} = \frac{n_0 \tau_0}{1 - \omega}$ et après que $n_0$ blocs aient été validés, on observe en moyenne $n' = \frac{n_0 \omega}{1 - \omega}$ blocs orphelins. D’où $\frac{(n_0 + n') \tau_0}{\tilde{S}_{n_0}} = 1$ . Par suite, avec la formule que nous proposons pour l’ajustement de la difficulté, la difficulté de minage ne baisserait pas en présence d’un mineur égoïste et donc son attaque ne deviendrait pas rentable à ce moment-là. La possibilité de l’attaque ne disparaîtrait pas pour autant et ferait toujours perdre de l’argent aux honnêtes mineurs (le taux de rendement de la stratégie « honnête » diminue sensiblement en présence d’un mineur égoïste) mais la stratégie ferait perdre de l’argent à l’attaquant même après un ajustement de la difficulté, ce qui lui ferait peut-être passer l’envie de se lancer dans une stratégie déviante… En gros, la stratégie égoïste deviendrait une attaque comme une autre (une attaque de spam par exemple) qui est coûteuse pour l’attaquant.

7 Conclusion

La stratégie de minage égoïste est une stratégie déviante qui, à court terme fait perdre de l’argent aussi bien aux honnêtes mineurs qu’à l’attaquant. Elle se manifeste par une production accrue de blocs orphelins et un ralentissement de la croissance de la blockchain officielle. Cependant, après que 2016 blocs aient été minés officiellement, le paramètre indiquant la difficulté de minage s’ajuste à la baisse et la vitesse de production des blocs augmente considérablement. Ceci entraîne une hausse sensible du taux de rentabilité de la stratégie de minage égoïste qui peut devenir supérieur au taux de rendement de la stratégie « honnête depuis toujours et à jamais ». En particulier, si le taux de hachage relatif de l’attaquant est supérieur à 33,33%, c’est toujours le cas. Ceci entraîne aussi une diminution du taux de rentabilité des honnêtes mineurs. Après cette mise à niveau à la baisse de la difficulté de minage, le paramètre de difficulté reste à peu près constant et le taux de rendement de la stratégie égoïste se stabilise à un niveau anormalement élevé.

La stratégie de minage égoïste est donc une véritable attaque sur Bitcoin mais pas pour les raisons qui sont généralement avancées car à notre connaissance, aucune étude ne prend véritablement en compte la durée de l’attaque ni – et c’est le plus important – le taux de rentabilité de la stratégie. Or, ce n’est pas parce qu’un attaquant arrive à placer plus de blocs dans la blockchain officielle qu’il ne le ferait en minant honnêtement que la stratégie doit être considérée comme « profitable » pour le mineur. Même si celui-ci arrivait à miner tous les blocs possibles, il pourrait perdre de l’argent. Il faut en effet prendre en compte le coût de l’attaque et sa durée. Cette analyse temporelle ne peut être menée rigoureusement que dans un cadre « poissonnien » en raisonnant avec des temps d’arrêt et des martingales comme nous l’avons fait. En particulier, elle peut difficilement être menée en considérant seulement la chaîne de Markov représentant les états du système (« state machine ») puisqu’une telle étude – intéressante au demeurant – décrit uniquement l’état stationnaire du système. Néanmoins cet état asymptotique arrive en moyenne après une première période de minage donnant lieu à un ajustement du paramètre de la difficulté. Au final, nous retrouvons le résultat principal présenté dans Majority is not Enough: Bitcoin Mining is Vulnerable mais les effets de la stratégie ne peuvent se faire sentir qu’à condition que le paramètre de difficulté baisse franchement. Il faut attendre pour cela plus de quinze jours en moyenne.

En réalité, si l’on y prend garde, la stratégie de minage égoïste fonctionne car elle exploite une faiblesse dans la formule d’ajustement de la difficulté. Le paramètre de difficulté est censé refléter la production réelle de toute la puissance de travail déployée sur le réseau. C’est pour cela que les blocs sont horodatés, afin de connaître le temps mis pour valider les blocs et faire en sorte qu’ils apparaissent en moyenne toutes les dix minutes. Mais en présence d’un mineur égoïste, ce n’est pas le cas.

Nous avons proposé une formule qui corrige cette anomalie en prenant en compte la production de blocs orphelins. Cette formule si elle était reprise n’annulerait pas pour autant l’attaque mais la rendrait coûteuse même après un ajustement de difficulté, ce qui ferait peut-être passer l’envie à un éventuel mineur de devenir égoïste.

Mois : mai 2018

Sur le minage égoïste