Contre-vérités et pratiques malhonnêtes de pseudo-chercheurs dans le monde de la cryptofinance

Nous écrivons ce post pour mettre en lumière l’incompétence et la malhonnêteté intellectuelle des deux pseudos-chercheurs Peter Rizun et Gun Sirer. Nous rendons compte ici de leur article intitulé « Selfish Mining Re-examined » récemment accepté pour publication dans la conférence Financial Cryptography 2020. L’article est disponible sur le site de la conférence.

Un article de simulations sans code public

Écrire un rapport complet sur l’article n’est pas pas notre but. Il serait de toute manière compliqué à établir car l’article n’est qu’une suite de commentaires sans démonstration, parfois incorrectes ou malhonnêtes à la suite de simulations impossibles à reproduire étant donné que le code informatique n’a pas été rendu public. Il n’y a en tout cas aucune référence en ce sens dans l’article. Disons tout de suite qu’une famille de ces simulations est très certainement fausse (voir plus bas). Est-ce la coutume dans les conférences d’informatique de publier des articles de simulations sans rendre le code public ? En soi, cela nous semble déjà constituer un sérieux problème mais il y a pire. L’article comporte à la fois des réelles contre-vérités scientifiques mais aussi des jugements erronés et dégradants qui n’ont absolument rien à faire dans un article scientifique. Commençons par relever ces derniers.

Des propos malhonnêtes

Il y a tout d’abord cette phrase en introduction visant à discréditer des contributions scientifiques (page 2).

Ever since its introduction, the selfish mining paper has attracted a cult of denialism [8,16,35]. Leaving aside claims that stem from an inaccurate model of how the Bitcoin protocol and pooling work [12]…

L’air de rien, l’article renvoie à plusieurs références comme s’il était entendu par tous que les articles cités niait la réalité du minage égoïste. C’est totalement faux. Regardons de plus près certaines de ces références [8], [12] et [16]. Tout d’abord, [8] renvoie à On Subversive Miner Strategies and Block Withholding Attack in Bitcoin Digital Currency, un article de Lear Bahack et Nicolas Courtois. Pour information, Lear Bahack est l’un des premiers à avoir mis en évidence l’existence de stratégies déviantes performantes dans le réseau Bitcoin, en décembre 2013, juste quelques semaines après l’article d’Eyal et Sirer. Comme cela arrive souvent en science, cette année-là, deux articles sont sortis quasiment simultanément sur le même sujet. Celui d’Eyal et Sirer, étant paru le premier, il a fini par s’imposer. Mais comment et de quel droit peut-on laisser croire aux lecteurs que l’inventeur d’une stratégie, en réalité nie son existence ? La stratégie de minage égoïste s’appelle pourtant « st1 » dans le premier article de Bahack en 2013. Il s’agit d’une insulte qui lui est faite, visant à nier son indéniable contribution à Bitcoin dans le but probable de s’approprier toute la gloire de la découverte. Par ailleurs, l’article de Bahack et Courtois [8] rédigé et rendu public en 2014 ne nie pas du tout la réalité du minage égoïste. Ils soulignent au contraire que la stratégie a été confirmée par des simulations. On lit en effet page 7 : « it was confirmed by computer simulations ».

La référence [16] renvoie à un article de blog d’Edward Felten, un informaticien américain célèbre, co-auteur d’un cours en ligne et d’un livre à succès d’introduction au Bitcoin. Lui non plus, ne nie pas les résultats d’Eyal et Sirer. Par contre, il lui semble aussi difficile d’imaginer un groupe cohérent de mineurs égoïstes. Il n’y a là encore aucun déni de la réalité du minage égoïste. Essentiellement, ce que remet en cause Felten, ce n’est pas l’article sur le minage égoïste de Sirer et Eyal, c’est l’affirmation péremptoire « Bitcoin is broken » formulée par Gun Sirer sur son blog. D’où sa réponse et le titre de l’article de blog « Bitcoin is not so broken after all ».

Enfin, dans l’article [16] que nous avons écrit, On Profitability of Selfish Mining, loin de nier la réalité de l’efficacité de la stratégie, nous retrouvons au contraire les résultats d’Eyal et Sirer en utilisant une autre approche basée sur des mathématiques de Poisson, suivant en cela l’approche originel de Satoshi dans son papier fondateur. L’article cherche en plus à comprendre la source de l’attaque et propose une modification raisonnable du protocole Bitcoin qui rend inopérantes des attaques de rétention de blocs comme le minage égoïste.  Nous montrons que l’attaque exploite en réalité un beugue dans l’algorithme d’ajustement de difficulté de Bitcoin qui ignore la production de blocs orphelins et, en présence d’un attaquant, sous-estime la réelle puissance de hachage déployée sur le réseau. Cette stratégie, perdante sur le court terme finit par être gagnante après un ajustement de difficulté et après avoir récupéré tout l’argent gaspillé pour faire baisser la difficulté. Nous ne nions donc pas du tout la réalité du minage égoïste ni son effet. Au contraire, nous l’étudions, nous retrouvons la formule d’Eyal-Sirer pour le taux de hachage apparent de la stratégie et nous proposons un regard nouveau sur cette stratégie. Nous démontrons en particulier que la stratégie ne peut être efficace que sur le long terme. Nous faire passer pour des révisionistes est intellectuellement totalement malhonnête.

Voici un autre exemple de propos malhonnête nous mettant en cause (page 5).

Since its expected revenue per unit time is greater than if it were mining honestly (14.40 blocks per day), intermittent selfish mining is profitable for attack durations significantly shorter than the 70 days computed in [16].

Le calcul que nous avons mené dans [16] ne concerne absolument pas la stratégie « Intermittent Selfish Mining » (ISM) considéré par les auteurs. Ces derniers mélangent volontairement nos calculs (rigoureusement exacts) concernant le temps mis avant que la stratégie de minage égoïste devienne rentable [16] et leurs simulations concernant la stratégie ISM. Ce sont deux stratégies différentes et ISM n’a pas été étudié dans [16]. L’affirmation ci-dessus est donc totalement malhonnête. Elle fait suite à des attaques répétées sur les réseaux sociaux dont nous avons été victimes à plusieurs reprises. Rizun et Sirer ne cessent de discréditer nos travaux en disant qu’ils sont faux sans jamais pointer l’erreur que nous aurions commise. Nous nous limitons à donner deux exemples parmi d’autres.
A travers ce tweet, on nous reproche un compte-rendu de notre article dans un journal pour bitcoiners. Est-il besoin de préciser que nous ne connaissions pas l’auteur de l’article avant de le découvrir dans le magazine btcmanager.com et que nous n’avons jamais été en contact avec lui ni hier, ni même aujourd’hui ?

Bien évidemment, ni Sirer ni personne n’a donné l’« erreur » qui n’existe pas. Notons que son co-auteur Ittay Eyal a pourtant scandaleusement « liké » son tweet. Il n’est pas le seul à « liker » des tweets scandaleux. Inutile d’en établir une liste. Ce n’est pas le propos ici. Mais il semble qu’une partie importante de la communauté académique semble préférer le copinage à la vérité.

Autre exemple. Ici aussi, Rizun affirme que notre calcul est faux sans en apporter la preuve et laisse entendre sournoisement que cela est bien connu de tous !

Mais ce n’est hélas pas tout. L’affirmation de Rizun &al reportée plus haut est aussi fausse comme nous allons le voir.

Des contre-vérités scientifiques

Tout d’abord, repartons du début. L’article de Rizun & al met en avant une stratégie appelée « Intermittent Selfish Mining ». Personnellement, nous avons découvert cette stratégie pour la première fois par un tweet de Vitalik Buterin mystérieusement effacé par son auteur. Pourquoi l’a-t-il effacé ? Nous l’ignorons. Il s’agit en vérité d’une réponse de Vitalik Buterin à un tweet, ce qui complique la possibilité de retrouver sa trace. Nous connaissons des moyens de retrouver des tweets effacés mais pas des réponses effacées à des tweets. Si certains connaissent des méthodes pour cela, qu’ils se manifestent.

Ne reste plus aujourd’hui sur Twitter qu’une réponse apportée par l’un de nous.  Cela dit, le fait que Vitalik Buterin ait effacé sa réponse n’est au fond pas très important. La stratégie proposée est naturelle et il est très probable que d’autres avant lui en aient eu l’idée dans des forums sur internet. Quoiqu’il en soit, le point est que Rizun & al se contentent de remercier Vitalik Buterin et laissent croire aux lecteurs qu’ils sont les inventeurs de cette stratégie, ce qui est faux.

Venons-en maintenant à la stratégie elle-même et à son étude. La stratégie est faite de répétitions de cycles. Chaque cycle est composée de deux phases. Dans la première phase, le mineur mine de manière égoïste et dans la deuxième, il mine honnêtement. Le but de la première phase est de faire tomber la difficulté tout en continuant à engranger des récompenses de blocs, puis de profiter au maximum dans une deuxième phase d’une difficulté réduite pour valider plus simplement des blocs et ainsi doper son revenu. Il n’est pas surprenant de constater comme le font les auteurs que la stratégie est rentable pour des taux de hachage de l’attaquant assez important (sans qu’il ne dépasse 50%). Ci-dessous, nous calculons explicitement le taux de hachage apparent long-terme de la stratégie, un calcul qui a manifestement échappé aux auteurs puisqu’ils ne font que des simulations. Nous y reviendrons. Mais le problème n’est pas là. Il concerne le temps mis avant que la stratégie ne devienne rentable.

Rizun & al affirme que la stratégie ISM devient rentable bien plus tôt qu’on ne pourrait l’imaginer, à partir seulement d’un instant qui vient en moyenne avant un deuxième ajustement de difficulté. Les auteurs mettent bien en évidence ce fait dont ils semblent fiers. Il est affirmé avec force à plusieurs reprises, notamment à la fin de leur introduction et dans leur conclusion.

Malheureusement, cette affirmation est fausse ou tout au mieux, cela ne correspond absolument pas à la notion habituelle communément admise de rentabilité. L’immense majorité des gens considère en effet qu’une stratégie est rentable à partir d’un instant donné si le PnL (revenu net de la stratégie i.e., différence entre revenue et coûts) reste toujours positif à partir de cet instant. Autrement dit, si à partir de cet instant, « c’est tout bénéf » comme on dit. Dans le cas du minage où les coûts par unité de temps sont indépendants de la stratégie, ce qui compte est le revenu engrangé par le mineur déviant auquel on retranche le revenu qu’il aurait gagné en minant honnêtement. C’est cette quantité qui permet de dire quand une stratégie déviante devient rentable. Et il s’avère que la stratégie ISM est effectivement rentable un peu avant le deuxième ajustement de difficulté. Mais ce n’est que temporaire et rapidement après, elle ne l’est plus. Puis elle le redevient, puis est de nouveau perdante, etc. Avec q=0.1 et γ=0.9, ce n’est qu’après plus de 13 ajustements de difficultés en moyenne que la stratégie devient définitivement rentable. Par comparaison, la stratégie de minage égoïste classique met juste cinq ajustements de difficulté avant d’être définitivement rentable. Voir les calculs détaillés ici. Il est aisé de comprendre cela intuitivement. Pour la stratégie de minage égoïste, le paramètre de difficulté se stabilise après seulement un premier ajustement de difficulté. Au début, le mineur égoïste souffre pour faire baisser la difficulté mais une fois fait, elle n’augmente plus. Il n’a plus alors qu’à récupérer l’argent perdu au début de la stratégie lorsque le mineur minait à perte pour faire tomber la difficulté. Tandis que pour la stratégie ISM, le mineur profite pleinement d’une difficulté réduite en minant honnêtement dans une deuxième phase. Cependant, à l’issue de cette seconde phase, le paramètre de difficulté augmente de nouveau, redevient égale à son niveau normal d’avant le début de l’attaque et le mineur ISM, tel Sysiphe va devoir souffrir de nouveau pour le faire baisser. Au final, la stratégie alterne phase où le mineur est gagnant et phase où il est perdant. Puis, à moment donné, la stratégie devient définitivement rentable. Nous avons représenté ci-dessous (Figure 1) le gain net moyen du mineur déviant en fonction de la progression de la blockchain officielle.

Figure 1. Différence entre le revenu d’un mineur déviant suivant la stratégie ISM et le revenu qu’il aurait touché en minant honnêtement. La progression de la blockchain est représentée en abscisse : chaque unité représente un nouvel ajustement de difficulté. Le revenu du mineur est représenté en ordonnées : chaque unité représente la valeur moyenne contenue dans un bloc (« coinbase » et frais de transactions).

Par comparaison, le gain net moyen du mineur SM en fonction de la progression de la blockchain officielle est représenté ci-dessous (Figure 2).

Figure 2. Différence entre le revenu d’un mineur déviant suivant la stratégie SM (minage égoïste) et le revenu qu’il aurait touché en minant honnêtement. La progression de la blockchain est représentée en abscisse : chaque unité représente un nouvel ajustement de difficulté. Le revenu du mineur est représenté en ordonnées : chaque unité représente la valeur moyenne contenue dans un bloc (« coinbase » et frais de transactions).

Par ailleurs, dans leur introduction, Rizun & al affirment sans en apporter la moindre preuve que le calcul de cinq ajustements de difficulté avant que la stratégie de minage égoïste ne devienne rentable pour q=0.1 et γ=0.9 est faux.

Grunspan & Perez-Marco [16] formalized such a time-based revenue model for selfish mining and calculated that an attacker with 10% of the network hash rate and with a
parameter of 0.9 must maintain the attack for 10 weeks. Their calculation is incorrect because they fail to account for the profit earned by the attacker in the difficulty period following the attack. Their revenue calculation stops one difficulty period too early, when selfish mining ends.

Nous avons une nouvelle fois vérifié notre calcul et contrairement à ce qui est avancé sans preuve ci-dessus, il est tout à fait correct. Il est faux de dire que nous ne prenons pas en compte les profits de l’attaquant réalisé une fois la difficulté diminuée et il est faux de dire que notre calcul s’arrête une période trop tôt. Nous le reproduisons ici une nouvelle fois. Il se trouve déjà ici (Section 6 page 14) et nous l’avons aussi reproduit ici (Exemple 3.8 page 11). Le voici de nouveau.

Avant ajustement de difficulté, l’attaquant a miné en moyenne q'.n_{0} blocs pendant un temps égale à \delta . n_{0} . \tau_{0} où q’ est le taux de hachage apparent calculé dans l’article d’Eyal et Sirer (q’=R_{pool} avec leur notation), n_{0}=2016, δ est le paramètre d’ajustement de la difficulté et \tau_{0}=10 minutes. S’il avait miné honnêtement durant tout ce temps, il aurait miné en moyenne q.\delta .n_{0} blocs. D’où une perte à l’issue de cette période de (q.\delta-q').n_{0} blocs. D’autre part, après ajustement de difficulté, les blocs officiels parviennent en moyenne tous les \tau_{0} et donc pendant une durée de minage t, l’attaquant gagne les récompenses contenues dans q'  \frac{t}{\tau_{0}} blocs alors que s’il minait honnêtement, il gagnerait simplement les récompenses contenues dans q \frac{t}{\tau_{0}} blocs. D’où un gain de (q' - q)\frac{t}{\tau_{0}} blocs en moyenne. Au final, après avoir miné jusqu’à faire tomber la difficulté puis ensuite pendant une durée supplémentaire de minage t, le gain net moyen de l’attaquant est

\displaystyle(q' - q)  \frac{t}{\tau_{0}} - (q \delta - q') n_{0} = (q' - q) . \frac{t -t_0}{\tau_{0}}

avec t_{0} = \frac{q \delta - q'}{q' - q} n_{0} \tau_{0}. En prenant γ=0.9 et q=0.1, le calcul montre que t_{0}=4 n_{0} \tau_{0}. Donc, la stratégie SM n’est rentable qu’après 5 ajustements de difficulté, ce qui correspond à un peu plus de 10 semaines de minage. Le calcul est donc bien exact contrairement à ce qui est affirmé sans preuve par Rizun & al. Des simulateurs de minage égoïste disponibles en ligne confirment évidemment ces calculs. On pourra se reporter par exemple à ce site réalisé par un étudiant de l’Université de Padoue. Son code est naturellement public comme il se doit et toutes ses simulations sont en accord avec les résultats théoriques qu’on peut obtenir par ailleurs.

Taux de hachage apparent ISM

L’un des clous de l’article de Rizun & al est la constatation par simulations que la stratégie ISM est une stratégie déviante plus profitable que la stratégie honnête dès lors que l’attaquant dispose d’environ 37% de puissance de hachage relative. Nous avons donné dans un nouvel article deux démonstrations très simples de ce fait en donnant en même temps une formule fermée pour le taux de hachage apparent q » de la stratégie (nous laissons la notation q’ pour le taux de hachage apparent long-terme de la strratégie SM) qui est explicitement

q'' = \displaystyle\frac{q (1 - 4 q^2 + 2 q^3) (1 + \gamma + (3 - 4 \gamma) q + (5 \gamma- 11) q^2 + (5 - 2 \gamma) q^3)}{2 - 2 q - 11 q^2 + 10 q^3 + 18 q^4 - 20 q^5+ 5 q^6}

Ci-dessous une démonstration élémentaire.

Si l’on note δ>1 le paramètre d’ajustement de difficulté après une première phase de minage ISM i.e., une phase de n_{0}=2016 blocs officiels où le mineur mine entièrement de façon égoïste, alors au bout de cette période dont la durée est n_{0}\tau_{0} \delta (avec \tau_{0}=10 minutes), le mineur a miné q' \cdot n_{0} blocs. Considérons maintenant la deuxième phase. Durant celle-ci, les blocs arrivent tous les \frac{\tau_{0}}{\delta}. Donc, la durée de la deuxième phase est \frac{n_{0} \tau_{0}}{\delta}. Au bout de celle-ci, l’attaquant a miné en moyenne q n_{0} blocs car il emploie alors une stratégie honnête. Par suite, au bout d’un cycle d’attaque, l’attaquant a miné en moyenne (q + q') n_{0} blocs et a mis pour cela \left( \delta + \displaystyle\frac{1}{\delta} \right) n_{0} \tau_{0}. D’où un taux de hachage apparent long-terme donné par

q'' =\displaystyle \frac{q + q'}{\delta + \frac{1}{\delta}}

On obtient alors la première formule annoncée plus haut pour q'' en remplaçant q’ par sa valeur. La solution de l’équation q''= q pour γ=0 donne bien un seuil égale à q''=0,365078, soit environ 37% comme annoncé par Rizun & al. Comment les auteurs qui se permettent de donner des leçons aux autres chercheurs ont-ils pu passer à côté d’une formule aussi simple à trouver ? La seule « difficulté » (c’est le cas de le dire) est le calcul de δ, paramètre d’ajustement de difficulté. Or, avec les notations de l’article d’Eyal et Sirer, on a simplement \delta = \displaystyle \frac{1}{r_{pool}+r_{others}}. Et on ne voit pas comment on peut faire l’impasse de cette formule lorsqu’on écrit avec justesse R_{pool} = \displaystyle\frac{r_{pool}}{r_{pool} + r_{others}} comme c’est fait dans l’article Majority is not enough. Comment Sirer peut-il passer à côté de ce fait dans un article qui précisément tourne autour du paramètre d’ajustement de difficulté ? L’explication la plus rationnelle est qu’il l’ignorait, ce qui nous conduit à émettre de sérieux doutes sur sa réelle contribution à son article co-écrit avec Ittay Eyal.

Une famille de simulations probablement fausse

Le fait qu’Ethereum prend désormais en compte la production de certains blocs orphelins (oncles) dans son algorithme d’ajustement de la difficulté n’est pas une chose forcément très connue du plus grand nombre. L’algorithme choisi est intéressant et pourrait servir de modèle pour Bitcoin. Il rend Ethereum beaucoup moins vulnérable au minage égoïste qu’au début de son existence malgré un protocole toujours dangereux qui encourage les attaques sur le réseau en rémunérant les oncles. Pour cette raison et au contraire de Bitcoin, une attaque de rétention de blocs sur Ethereum sera toujours payante, qu’elle réussisse ou non. Les principales références sur ce sujet se trouvent ici, ici et ici. Cependant, vu les simulations concernant le minage égoïste dans Ethereum et les commentaires qui les accompagnent dans l’article de Rizun & al, tout porte à croire que les auteurs n’ont pas simulé Ethereum dans sa version actuelle avec un ajustement de difficulté complexe qui prend en compte la production d’oncles et intervient à chaque bloc. Il est impossible d’en dire plus et d’être catégorique car une nouvelle fois, le code n’est pas public.

Conclusion

L’article de Rizun & al est un papier de simulations pures qui ne rend pas public son code. Il présente des contre-vérités et des propos malhonnêtes qui n’ont pas leur place dans un article scientifique sérieux. Il témoigne d’une méconnaissance de la notion de rentabilité. Les simulations concernant Ethereum sont probablement fausses. Le taux de hachage apparent long-terme de la stratégie ISM observé par simulations peut s’obtenir en formule fermée par des techniques élémentaires.

Nous avons été directement mis en cause dans un article pseudo-scientifique. Mais nous ne sommes pas dupes. Il y a des enjeux financiers qui dépassent nos petites personnes. Les deux auteurs, Gun Sirer et Peter Rizun sont chacuns engagés dans des projets de cryptomonnaies alternatives et ont tous les deux des intérêts à discréditer Bitcoin et à faire croire qu’il est beaucoup plus vulnérable qu’il n’y paraît dans le but de vendre leur camelote. Contrairement à nous et à beaucoup d’autres scientifiques, ils sont directement partie prenante d’entreprises privées qui gèrent des millions de dollars. Ils ont réussi à monnayer leur crédibilité scientifique et il est important pour eux de continuer à se faire passer pour des experts des cryptomonnaies qu’ils ne sont pas. Mais au fond, de telles attaques mesquines ne sont qu’au mieux des pitreries. Plus on attaque Bitcoin, plus il se renforce.

S’il souhaite aller plus loin, le lecteur trouvera un traitement rigoureux des problèmes soulevés dans ce billet dans un nouvel article de recherche que nous venons d’écrire.

Cyril Grunspan & Ricardo Pérez-Marco

 

Sur le minage égoïste

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.

 

Tintin, L’Oreille Cassée, Hergé, 1937.

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)] = qbb désigne la récompense moyenne contenue dans un bloc et \mathbb{E}[\xi] = \tau_0 avec \tau_0 = 600s. 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.

Le Déserteur, Boris Vian, 1954

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 :

  1. 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)
  2. 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
  3. 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}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 Rpool 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}\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}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.

Proust et Einstein

Marcel Proust (1871 – 1922), circa 1910 (Photo by Hulton Archive/Getty Images)

Voici le texte d’un exposé donné au Centre Culturel Français d’Helsinki le Vendredi 2 décembre 2005. J’y avais été gentiment invité pour donner un exposé sur Proust et Einstein. Il s’agit d’un texte que je croyais perdu et que je viens de retrouver dans un vieux disque dur.  Les amateurs de Proust apprécieront peut-être… Si le sujet vous intéresse, je vous invite à lire le superbe livre de Thibault Damour : Si Einstein m’était conté paru lors du centenaire de « l’année miraculeuse » 1905.

I. Pertinence du sujet

1. Idée bizarre

L’idée d’un rapprochement entre Proust et Einstein peut sembler étrange. La mémoire collective conserve en effet l’image du savant facétieux qui tire la langue et celle du jeune dandy, l’orchidée à la boutonnière. Proust lui-même, dans une lettre adressée au Duc de Guiche, son ami physicien en décembre 1921 s’étonnait d’un tel rapprochement :

On a beau m’écrire que je dérive de lui ou lui de moi, je ne comprends pas un seul mot à ses théories, ne sachant pas l’algèbre. Et je doute pour ma part qu’il ait lu mes romans. Nous avons paraît-il une manière analogue de déformer le temps. Mais je ne puis m’en rendre compte pour moi…

Proust nul en maths

En effet, Proust a toujours été « nul » en maths. Quand il était élève au lycée Condorcet à Paris, c’est son père et parfois son petit frère qui faisaient ses devoirs à la maison. Lorsque Proust utilise des comparaisons scientifiques, la moitié du temps, il se trompe. Par exemple, il ne connaît pas la composition de l’eau. Il écrit qu’elle est constituée d’oxygène et d’azote (d’ailleurs des éditeurs de la Recherche sont allés jusqu’à corriger le texte de Proust !). En décrivant le baiser d’Albertine, il croit que les contraires se repoussent alors qu’ils s’attirent… Marcel ne semble avoir été intéressé que par la biologie sous l’influence de son père qui était épidémiologiste et de son frère qui deviendra un grand professeur de médecine. Dans le grand roman de Proust, A La Recherche du Temps perdu, les scientifiques n’ont pas le beau rôle. Charlus qui ne peut s’empêcher de parler d’homosexualité est « rasant comme un savant qui ne parle que de sa discipline ». A Morel qui prend prétexte de suivre des cours du soir de mathématiques pour ne pas voir Charlus, celui-ci lui répond d’un air rageur : « on ne comprend jamais rien à un cours d’algèbre ! ». Il n’y a pas vraiment de grand savant dans la Recherche. Celui qui pourrait y ressembler le plus, Brichot — parce qu’il règne comme un roi avec sa cour à la Sorbonne — est certainement très érudit, il connaît l’étymologie de beaucoup de mots mais en dehors de cela, il est incapable de comprendre et d’expliquer le monde. Et symboliquement, il sera frappé de cécité.

2. De nombreuses références scientifiques

 Pourtant la science est présente chez Proust. Des critiques ont relevé que la Recherche était remplie de près de cinq cents références à la science avec parfois l’emploi de termes compliqués : une référence toutes les dix ou quinze pages dans la Recherche.

Ce qu’elles expriment

Ainsi, la biologie explique l’homosexualité. La botanique décrit les relations homosexuelles. Vinteuil, le grand musicien s’appelait en réalité Vington dans des brouillons de la Recherche et était un savant ; son « audace » est la même que « celle d’un Lavoisier ou d’un Ampère » ; la chimie explique la jalousie de Swann ; l’électricité décrit « les yeux d’Albertine » ; l’atelier d’Elstir, le grand peintre du roman, est un « laboratoire de création du monde ».

3. Histoire du rapprochement entre Proust et Einstein

Les similitudes entre Proust et Einstein dans leurs travaux ont alimenté les correspondances et les articles de presse du début du siècle dernier et maints ouvrages français ou anglo-saxons ensuite. Je vais en dire quelques mots sous un angle historique.

De leur vivant :

a) historique

De leur vivant déjà, on avait esquissé un tel rapprochement. Le premier à l’avoir relevé est un mathématicien, sous préfet à Bagnères-de-Bigorre. Camille Vettard en 1920 le développe dans la préface-dédicace à Proust de son livre Pauper Le Grand. Vettard avait envoyé le manuscrit à Proust dans l’espoir d’être publié mais il ne le sera jamais malgré l’appui de Proust auprès de Gaston Gallimard et de Jacques Rivière. Proust et Vettard échangeront alors une correspondance de près de cinquante lettres.

Les premières publications faisant allusion à ce lien entre Proust et Einstein seront celles de Jacques-Emile Blanche, l’auteur du célèbre portrait de Proust qui se trouve au Musée d’Orsay, dans sa préface à Dates, un livre de critiques d’art, en janvier 1921. Suivie des articles de Paul Souday en mai 1921 dans Le Temps et de Roger Allard dans la N.R.F. en juin 1922.

La préface de Vettard ne sera finalement publiée que dans le « Courrier des Lecteurs » de la N.R.F. en août 1922 sous le titre Proust et Einstein. Elle ne passera pas inaperçue  puisque deux journaux en écriront des comptes-rendus : L’Echo de Paris et L’Opinion en août 1922. Proust sera très fier de cette comparaison. Peu de temps après, il écrit à sa nièce Suzy :

Depuis qu’un mathématicien, sous-préfet je crois aussi, a fait un article Proust et Einstein, je me sens beaucoup plus digne d’être ton oncle. Tu as peut-être lu un fragment de cet article dans L’Echo de Paris.

Il faut souligner le mérite de Vettard pour avoir perçu une correspondance entre Proust et Einstein, alors que les trois derniers volumes de la Recherche n’avaient pas encore été publiés.

b) Le contenu
On ne comprenait pas Einstein

Qu’il s’agisse d’Allard, de Souday, de Vettard ou de tous les autres, à cette époque, il nous apparaît aujourd’hui que ces auteurs ne comprenaient pas la théorie de la relativité. Ils se contentaient de souligner des similitudes dans la représentation du temps ou dans le style, sans savoir bien l’expliquer. Dans les années 20, Einstein avait la réputation d’être incompréhensible. Tout le monde en parlait mais mal et sans le comprendre. Charlie Chaplin lui disait d’ailleurs :

Moi, on m’acclame parce que tout le monde me comprend, et vous, on vous acclame parce que personne ne vous comprend !

C’est à cause de cette réputation d’obscurité d’Einstein que Jacques Rivière, avant de changer d’opinion, a d’abord refusé l’article de Vettard. Il avait peur de cette comparaison, qui risquait de donner l’impression que Proust était « aussi abstrait et incompréhensible qu’un Einstein ».

Proust et Bergson

En fait, ce rapprochement avec Einstein qui a flatté Proust a eu le mérite de le faire réagir sur un autre rapprochement avec Bergson. C’est parce qu’il pouvait comprendre Bergson qu’il se sentait capable de réfuter ce rapport et de nier tout influence comme il l’a fait dans un article paru dans Le Temps en 1922.

Après la mort de Proust

Depuis la mort de Proust, c’est devenu un lieu commun que mettre en avant son attitude scientifique.

Dans le numéro de décembre 1922 de la N.R.F., Jacques Rivière annonce la mort de Proust en ces termes : « Les découvertes que [Proust] a faites dans l’esprit et dans le cœur humains seront considérées un jour comme aussi capitales et du même ordre que celles de Képler en astronomie, de Claude Bernard en physiologie ou d’Auguste Comte dans l’interprétation des sciences ». Dans le numéro d’hommage à Proust en 1923, Camille Vettard écrira un article sur Proust et le Temps qui reprend les grandes lignes de son article de l’année précédente sur Proust et Einstein. Dans ce même numéro, André Maurois publie un article intitulé L’Atittude scientifique de Proust.

Etant donné que la relativité n’était pas enseignée en France jusqu’en 1960, ni vulgarisée, et qu’elle est devenue quasiment tabou à partir de 1925 jusqu’à ce que l’Etat Français se décide à construire des bombes atomiques, il est normal que les seuls critiques à avoir parlé du lien entre Proust et Einstein soient anglais et américains. Par exemple : Edmund Wilson, Maurice Beznos, John Erickson. Après 70, parmi les français, citons Julien Gracq dans En lisant, en écrivant. Mais surtout, je renvois les auditeurs intéressés aux derniers ouvrages de Thibault Damour, professeur de physique à l’Institut des Hautes Etudes Scientifiques, Si Einstein m’était conté et de François Vannucci, professeur de physique à l’Université Paris VII, Marcel Proust à la recherche de la science.

A mon tour, je vais analyser la pertinence du rapprochement entre Proust et Einstein.

II. Parallèles biographiques

Un exposé sur Proust et Einstein ne peut évidemment négliger les parallèles qu’on peut observer dans la vie de l’un et de l’autre.

1. Vocation

Très jeunes, ils ont tous les deux la vocation de devenir écrivain pour l’un, physicien pour l’autre. A son père qui voulait qu’il suive des études de droit pour devenir diplomate, Proust répond encore adolescent : « tout ce que je pourrais faire en dehors de la littérature ne sera que du temps perdu ». Einstein écolier, dans une composition en français écrit : « Si j’avais le bonheur de passer heureusement mes examens, j’irai à l’école Polytechnique de Zürich. J’y resterai quatre ans pour étudier les mathématiques et la physique » (voir A. Pais, « Subtle is the Lord… » : The Science and The Life of Albert Einstein, Oxford (1982).

2. Judaïsme

Proust et Einstein sont de la même génération. Proust est né en 1871 à Auteuil tandis qu’Einstein est né en 1879 à Ulm en Allemagne. Tous les deux sont juifs (Marcel Proust par sa mère seulement) et issus de familles intégrées dans la société malgré l’antisémitisme ambiant. Einstein subira toute sa vie l’antisémitisme. Par exemple, en 1920 un club anti-relativité  baptisé « Association des savants allemands » dénonce la « physique juive » en Allemagne. Pour échapper à ces persécutions, il devra changer de pays, s’installera aux Etats-Unis, et malgré tout, il recevra toute sa vie des lettres « Mort aux juifs ». Il s’engagera dans le pacifisme et le sionisme. C’est ainsi que toute la correspondance d’Einstein se trouve à l’Université Hébraïque de Jérusalem. C’est aussi pourquoi il n’a pas de sépulture car il avait peur qu’elle ne soit profanée.

Proust, lui, bien qu’élevé dans le catholicisme comme son frère et ayant des amis d’extrême droite comme Léon Daudet, s’est engagé dans la défense de Dreyfus et se disait « le premier dreyfusard ». Il donnait de grands dîners « de dreyfusards » dans l’appartement de ses parents. On retrouve les échos de l’Affaire Dreyfus dans la Recherche et, entre autre, à travers l’histoire du personnage de Swann.

3. Des débuts décevants 

Tous les deux, Proust et Einstein ont eu des débuts décevants. Einstein ne rentre à l’Ecole Polytechnique de Zürich qu’à sa seconde tentative en 1896. Diplomé en 1901, il ne trouve pas de poste universitaire et de 1903 à 1908 il n’est qu’un employé de troisième rang à l’Office fédéral des brevets de Berne où il travaille huit heures par jour. Proust, quant à lui, au début du siècle dernier n’est qu’un écrivain mondain sans lecteur. Les Plaisirs et les Jours, sa première véritable publication, en effet, ne rencontre pas le public. A cause de cette réputation d’écrivain mondain, Gide refusera tout d’abord la publication de Du côté de chez Swann  en 1913 – a-t-il seulement ouvert le paquet contenant le manuscrit ? – et Proust devra publier à compte d’auteur chez Grasset.

4. Des parcours semblables

Ils auront des parcours étonnement semblables. L’année 1905 sera pour tous les deux le point de départ de leur œuvre. Pour Proust, en effet, certains essayistes datent le début de l’écriture de la Recherche en cette année 1905 où il vient de publier Sur la lecture, la préface de sa traduction d’un livre de Ruskin, Les Sésames et les Lys. Einstein, lui, envoie ses articles révolutionnaires en juin 1905 à Annalen der Physik.

Tous les deux ont eu un jour une révélation. Un jour de mai 1905, en se promenant avec son ami Michele Besso dans les faubourgs de Berne, Einstein a (comme il le dira plus tard à son gendre) une « vision » qui le conduira à la théorie de la relativité restreinte. De même, Proust, en trempant une biscotte dans une tasse de thé que lui avait apportée Mme Cottin, sa femme de chambre, sera le sujet d’une expérience de mémoire involontaire, qu’il transposera en une madeleine dans la Recherche.

Tous les deux mettront à profit les années de guerre pour développer leur œuvre. Einstein, pour corriger une erreur de calcul et aboutir à la relativité générale ; Proust pour enrichir la Recherche avec le « roman d’Albertine ».

Ils connaitront tous les deux la gloire la même année. En 1919, l’expédition d’Eddington sur l’île du Prince (dans le Golfe de Guinée) confirme la théorie d’Einstein. Il devient ainsi le plus grand savant du siècle. Proust connaît lui aussi la gloire en 1919 avec l’attribution du prix Goncourt pour son livre A l’Ombre des Jeunes Filles en Fleurs.

En 1920, Einstein fait une tournée triomphale aux Etats-Unis et en Angleterre au pays de Newton. Proust, lui, reçoit la légion d’honneur.

Einstein décédera plus de trente ans après la mort de Proust mais tous les deux travailleront avec acharnement jusqu’à leur dernier jour à l’œuvre de leur vie.

5. La rencontre ratée

Malheureusement, malgré tous ces points communs, ces deux génies ne se rencontreront jamais. Einstein, auréolé de son prix Nobel, arrive en France fin mars 1922. La visite rendue possible grâce au ministre allemand Walther Rathenau, au ministre français Painlevé (scientifique lui-même) et à Paul Langevin (professeur au collège de France) aurait dû rester discrète. Einstein, échaudé par les débordements accompagnant ses visites aux Etats-Unis et en Angleterre hésitait à venir en France. Mais, finalement il accepte, en partie pour servir la cause de la réconciliation franco-allemande. Il aurait dû venir donner dans l’intimité trois exposés devant des chercheurs uniquement mais les journaux ont eu vent de la visite fin mars 1922 et se déchaînent. Einstein ravive la fracture de la France divisée par l’Affaire Dreyfus. Il est perçu comme un « boche », un « juif » et « un espion bolchevique ». Les journaux sont incapables de vulgariser la relativité et n’en parle que d’un ton humoristique. Einstein, lui a su faire un bon exposé conformément à son principe : « Si vous ne pouvez expliquer un concept à un enfant de six ans, c’est que vous ne le comprenez pas complètement ». Des amis de Proust sont dans l’assistance : le duc de Guiche (sans doute) comme physicien et les mondaines Anna de Noailles, la princesse Edmond de Polignac et la comtesse Henri Greffülhe. Il est à noter la part des femmes et de la mondanité dans la diffusion de la relativité comme dans celle de l’œuvre proustienne. Proust, malade (il va mourir en novembre) n’a pas pu assister à cette séance du 31 mars 1922 au Collège de France mais ses amis ont pu lui en en faire un compte-rendu, sans doute bien erroné.

III. Le Temps

Afin de pouvoir comprendre les similitudes dans l’expression du temps du savant et de l’écrivain, voici une brève présentation de la place du temps dans la relativité d’Einstein.

1.  La théorie de la relativité d’Einstein

Avant Einstein, on considérait deux catégories entièrement séparées : le temps et l’espace. Dans son article de juin 1905, Einstein bouleverse cette vision. Avec deux postulats qui ne vont pas à l’encontre du sens commun (et c’est aussi pour cela que la relativité a été accepté plus facilement que son autre article sur les quanta de lumière qui fonde la théorie quantique) il a révolutionné l’espace et le temps. Premier postulat : les lois de la physique s’expriment de la même façon dans tous les systèmes de référence possibles pourvu que ces systèmes se déplacent l’un par rapport à l’autre à vitesse constante. Si des voisins s’éloignent de moi à une vitesse constante, les lois de la physique s’exprimeront de la même façon dans les deux systèmes de référence : le leur et le mien. Il en est de même des expériences d’électricité ou de magnétisme. Certes, les coordonnées d’un objet étudié ne seront pas les mêmes mais les lois de la physique qui régissent son mouvement seront identiques. Deuxième postulat : pour moi comme pour mes voisins dans leur système de référence, la vitesse de la lumière est la même. Avec ces deux postulats très simples, Einstein aboutit par le raisonnement à un nouveau concept : l’espace-temps, où le temps et l’espace sont indissociables, ainsi qu’à une nouvelle géométrie et une nouvelle méthode pour calculer les distances qui n’est plus basée sur le théorème de Pythagore. Il n’y a donc plus d’un côté l’espace apparenté à l’éther où se déroulerait des expériences et où les corps en mouvement se déplaceraient à la manière d’acteurs dans un théâtre, et de l’autre un temps absolu comme un espèce de poumon de l’univers. Le temps, selon Einstein ne passe pas. L’image qu’on en avait d’un sablier qui coulerait toujours est fausse. En particulier, cela n’a plus de sens de dire simplement : « maintenant ». Comme le disait Einstein en 1955, dans une lettre à la veuve de son ami italien Michele Besso (celui-là même qui accompagnait Einstein dans sa promenade dans les faubourgs de Berne où il a eu l’intuition de la relativité) : « Pour nous autres physiciens, la séparation entre passé, présent et avenir, ne garde que la valeur d’une illusion, si tenace soit elle ». Pour illustrer mon propos, l’une des conséquences de la théorie de la relativité est le paradoxe dit de Langevin – qui a d’ailleurs été vérifié expérimentalement sous d’autres formes. Un jumeau reste sur terre dans son village. L’autre fait un parcours dans le cosmos et revient. A son retour, il constate que son frère qui est resté sur terre aura vieilli plus que lui.

J’ajoute, pour terminer ce très cours survol de la théorie de la relativité restreinte d’Einstein, qu’il en a déduit sa célèbre relation entre énergie et masse E=MC² dans son article publié en septembre 1905.

2. Le duc de Guiche explique la relativité à Proust

Proust n’a pas connu cette théorie dans ces termes puisque le Duc de Guiche, son ami physicien qui rentrera à l’Académie des Sciences ne lui en avait donné qu’une explication triviale dans une lettre :

Voici pourtant un excellent résumé de ses théories : deux marseillais se disputent sur la vitesse des autos, des avions, de l’électricité etc… « Bien mieux dit l’un d’eux ; tu es sur la Canebière ; je couche avec ta femme à Pékin – instantanément, tu es cocu » Eh, bien ça n’est pas vrai. 

3. Les anachronismes

Est-il vraiment pertinent d’évoquer la relativité dans l’œuvre de Proust, alors que lorsqu’il parle du temps, il semble le faire très mal ?

Nous savons en effet que la Recherche est remplie d’anachronismes. Par exemple, Swann renaît subitement dans quelques pages du Temps Retrouvé avant de disparaître de nouveau. De toute évidence, la Recherche n’est pas une affaire de chronologie. L’anachronisme le plus marquant apparaît dans Le Temps Retrouvé. Il y a deux événements dans l’œuvre de Proust dont on ne sait lequel est antérieur et lequel est postérieur : l’épisode où le Narrateur adulte trempe une madeleine dans son thé dans Du côté de chez Swann et celui où le héros du Temps Retrouvé bute sur les pavés mal équarris de la cour de l’Hôtel de Guermantes. En effet,

comme le dit le Narrateur, toute la Recherche est sortie d’une tasse de thé, tous les volumes sont des livres de souvenirs qui ont été écrits après que le héros adulte eut éprouvé une sensation de bonheur en mangeant une madeleine. Donc, l’épisode de la madeleine est postérieur au second. Or, il le présente dans Le Temps Retrouvé comme antérieur. On y lit (p. 256 GF) : « Mais cette fois j’étais bien décidé à ne pas me résigner à ignorer pourquoi, comme je l’avais fait le jour où j’avais goûté d’une madeleine trempée dans une infusion. » Comme si le jour de la madeleine précédait celui où il vient de buter sur les pavés de la cour de l’Hôtel de Guermantes. Il y a donc ici une contradiction.

4. Le temps du récit

Parle-t-il mal du temps, ou crée-t-il une ambiguïté volontaire pour ne pas présenter un temps linéaire ? Plus encore que quelques anachronismes, ce qui frappe le lecteur, c’est qu’il ne sait pas quel est le temps du récit. Est-il écrit au présent (« D’ailleurs dans ce livre où tout est inventé) ? Au passé composé (« Longtemps je me suis couché de bonne heure ») ? Au passé simple (« Et presque tout de suite je la reconnus ») ? A l’imparfait (« Je venais de comprendre… ») ? Au conditionnel (« du moins, ne manquerais-je pas d’abord d’y décrire les hommes… ») ? Ou au futur ? Dans un passage de Sodome et Gomorrhe, l’auteur mêle d’ailleurs tous les temps dans la même phrase (Bouquins, 607) :

Certes ces causes d’erreur étaient loin d’être les seules, mais je n’ai plus le temps, avant mon départ pour Balbec (où pour mon malheur je vais faire un second séjour qui sera aussi le dernier), de commencer des peintures qui trouveront leur place bien plus tard.

A l’époque de Proust, on avait remarqué certains problèmes de temps. Benjamin Crémieux, en l’occurrence (un grand critique français d’origine juive, mort tragiquement à Buchenwald en 1944) avait fait part à Proust de certains anachronimes. Celui-ci lui avait répondu en août 1922 :

Je crois que les anachronismes dont vous avez la bonne grâce de me féliciter ne sont pas dans mon livre. Je ne le jure pas et cela m’ennuierait trop d’ouvrir cet assommant ouvrage pour vous répondre avec certitude. Mais enfin, autant que je me souviens, entre la soirée Guermantes et le deuxième séjour à Balbec, il y a un grand intervalle de temps. Einsteinisons-le si vous voulez pour plus de commodités.

Avec cette réponse sous forme de boutade, l’auteur ne donne-t-il pas inconsciemment ce qu’est sa vision du Temps dans la Recherche ?

5.   Allusions à la relativité chez Proust

En vérité, Proust évoque en plusieurs endroits la relativité dans ses manuscrits. Tout d’abord, le nom du physicien est présent dans une esquisse d’A l’Ombre des Jeunes Filles en Fleurs :

Le visage de ces jeunes filles (très Einstein mais ne pas le dire, cela ne fera qu’embrouiller) n’occupe pas dans l’espace une grandeur, une forme permanente.

Par ailleurs, Proust fait aussi allusion à l’expédition d’Eddington en 1919 qui a confirmé les prédictions d’Einstein. Dans Le Côté de Guermantes I, Proust écrit en effet :

Je tenais mon esprit préparé comme ces plaques sensibles que les astronomes vont installer en Afrique aux Antilles, en vue de l’observation scrupuleuse d’une comète ou d’une éclipse.

Proust était sans doute au courant de l’existence de géométrie non-euclidienne car il écrit dans Sodome et Gomorrhe sur le ton de la plaisanterie :

Apprendre qu’il existe […] un univers où la ligne droite n’est plus le chemin le plus court […] eût beaucoup moins étonné Albertine que d’entendre le mécanicien lui dire qu’il était facile d’aller dans un même après-midi à Saint-Jean et à la Raspelière. (Folio SG, 385)

6. Une approche de la relativité chez Proust : l’église de Combray

Proust ne fait pas seulement allusion à l’existence de la relativité dans son livre. Dans Matinée chez la Princesse de Guermantes, c’est-à-dire dans certains brouillons du Temps Retrouvé datés de 1911, il dit chercher à emprunter le « langage de la géométrie » pour placer son roman « dans le Temps ». Et, dans certains passages de la Recherche, il donne sans le vouloir une image assez juste de la relativité. Notamment celui où Proust décrit l’église de Combray dans Du côté de chez Swann (n’oublions pas l’importance de cette église, c’est elle qui a donné au héros l’intuition de placer son roman « dans le Temps »). Il parle d’

un édifice occupant, si l’on peut dire, un espace à quatre dimensions – la quatrième étant celle du Temps -, déployant à travers les siècles son vaisseau qui, de travée en travée, de chapelle en chapelle, semblait vaincre et franchir non pas seulement quelques mètres, mais des époques successives d’où il sortait victorieux.

En rupture avec la vision newtonienne de l’espace et du temps, l’église de Combray est ainsi plongée dans l’espace-temps. De plus, dans cette nouvelle géométrie de l’espace-temps, Proust a même l’intuition d’une nouvelle métrique qui décrirait la distance entre deux événements. Dans Le Temps Retrouvé, en reprenant la description de l’église de Combray, il écrit en effet :

dans ce vaste tableau verdoyant je reconnus peint […] le clocher de l’église de Combray. Non pas une figuration de ce clocher, ce clocher lui-même qui, mettant ainsi sous mes yeux la distance des lieues et des années était venu […] s’inscrire dans le carreau de ma fenêtre.

Il est ici question de « la distance des lieues et des années » comme si Proust avait l’intuition que la distance devait prendre en compte la position non seulement dans l’espace mais aussi dans le temps, en accord avec la vision géométrique de l’espace-temps quadri-dimensionnel d’Einstein et Minkowski.

 7. Une autre approche : les « échasses »

Mais ce qui est frappant, c’est que c’est sur une image de l’espace-temps que Proust conclut la Recherche sous la forme d’hommes « juchés sur des échasses ». Il exprime d’abord l’ambition de « décrire l’homme comme ayant la longueur non de son corps mais de ses années ». En parlant de sa vie, le Narrateur écrit et c’est la dernière phrase du Temps Retrouvé :

Du moins, si elle m’était laissée assez longtemps pour accomplir mon œuvre, ne manquerais-je pas d’abord d’y décrire les hommes (cela dût-il les faire ressembler à des êtres monstrueux) comme occupant une place si considérable, à coté de celle si restreinte qui leur est réservée dans l’espace, une place au contraire prolongée sans mesure – puisqu’ils touchent simultanément comme des géants plongés dans les années, à des époques si distantes, entre lesquelles tant de jours sont venus se placer – dans le Temps. 

Cette image de la vie d’un homme est tout à fait conforme à celle que pourrait donner Einstein de la ligne d’univers de l’homme. Celle-ci comme l’écrit Thibault Damour

trace un tube qui s’étend de bas en haut de l’espace-temps. Ce tube correspond aux « échasses » de Proust. Notons d’ailleurs que l’intuition de Proust était correcte : ce tube occupe une place beaucoup plus considérable dans le temps que dans l’espace. En effet, mesurant comme il a été indiqué, les durées en secondes, et les distances en secondes-lumières, ce tube a une hauteur (temporelle) de quelques milliards de secondes, alors que sa largeur (spatiale) est seulement de quelques milliardièmes de secondes-lumières. Autrement dit, le rapport entre sa hauteur et sa largeur est de l’ordre du milliard de milliard.

En conclusion, s’ils sont morts tous les deux en voulant écrire et chercher jusqu’au bout, ce n’est sans doute pas un hasard. Proust et Einstein, chacun dans leur discipline, les lettres et les sciences, tels deux éclaireurs sur les chemins opposés de Combray, se rejoignent « dans le Temps ». 

« One-CPU-one-vote » sinon rien…

One CPU ONE VOTE

Proof-of-work is essentially one-CPU-one-vote

Je croyais en avoir fini de « Scaling Bitcoin 2017 » et pourtant un article de Bitconseil relayé par bitcoin.fr m’a conduit à examiner un article exposé lors de cette conférence malheureuse. Il s’agit de Bobtail: A Proof-of-Work Target that Minimizes Blockchain Mining Variance écrit par Brian Levine et George Bissias.

Signalons que c’est loin d’être le premier article sur le thème des blockchains écrits par ces deux chercheurs. Sur leurs sites personnels, on peut découvrir une longue liste d’articles de recherche ayant été présentés dans des conférences. En particulier deux de leurs récents papiers ont été acceptés par « Scaling Bitcoin 2017 ».

Les auteurs souhaitent changer la preuve de travail de Bitcoin. Ils en proposent une autre donnant lieu à un temps de découverte des blocs (temps dit interblocs) possédant une variance plus faible, ce qui aurait pour conséquence d’augmenter sensiblement la sécurité du réseau. Il semblerait (on veut bien les croire) que 5% des blocs minés par le réseau Bitcoin l’a été en plus de 40 minutes alors que la moyenne est de 10 minutes. Passer plus de temps que prévu à miner 6 ou 7 blocs laissent davantage de temps aux éventuels escrocs pour réaliser une attaque à la double-dépense. C’est vrai. Et nous avons quantifié cela avec Ricardo Perez-Marco dans Double Spend Races.

Un principe fondateur

Il faut comprendre un principe fondateur du bitcoin : on peut rentrer et sortir du réseau à tout moment, se mettre à miner quand bon nous semble mais quoiqu’il arrive si à un instant donné deux mineurs possède la même puissance de calcul (plus exactement la même puissance de hachage relativement à SHA256), leur probabilité de découvrir le prochain bloc est la même. Ceci est énoncé sobrement par Satoshi Nakamoto à travers la formule : « Proof-of-work is essentially one-CPU-one-vote. » (section 4 de l’article fondateur du Bitcoin).

Le « one-CPU-one-vote » est l’équivalent d’une maxime latine, toujours vraie pour ceux qui en suivraient le principe même si bien sûr l’empire romain n’existe plus. Dans un langage moderne, cela signifie que deux entreprises de minage possèdant à moment donné la même puissance de hachage ont à cet instant la même probabilité de découvrir le nouveau bloc.

Une expérience de pensée

Considérons trois mineurs (ou trois entreprises de minage) A, B et C possédant exactement le même matériel informatique (donc la même puissance de hachage). A l’instant initial, seuls A et B sont connectés sur le réseau qui peut contenir bien sûr d’autres mineurs en plus de A et B. Supposons que A et B aient déjà passé t secondes à chercher à résoudre la preuve de travail qui octroie – à celui qui la trouve – la récompense contenue dans le prochain bloc. Mais sans y parvenir. A ce moment-là B jette l’éponge : il arrête de miner.  Le mineur C au contraire se connecte. Il prend la place de B et se met à miner. On imagine en outre que tous les autres mineurs ayant commencé à miner en t=0 sont toujours présents et cherchent jusqu’au bout à résoudre le problème de preuve de travail ou bien sont remplacés dans leur globalité par d’autres mineurs possédant la même puissance de hachage qu’eux, de sorte que la puissance de hachage globale n’a pas fondamentalement été modifiée. Par conséquent pour A, la situation est resté inchangée. Il possède toujours la même puissance de hachage relative qui est aussi celle de C. En vertu du principe « one-CPU-one-vote », A et C qui possèdent la même puissance de hachage possèdent aussi la même probabilité de découvrir la preuve de travail. Pourtant, C vient de se connecter alors que A a déjà cherché pendant t secondes. C’est donc que tout le temps passé par A à miner en vain (entre 0 et t) est du temps perdu. Il ne lui est d’aucune utilité et ne permet pas d’orienter ses recherches dans la bonne direction. La probabilité que A mette encore s secondes avant de trouver le résultat est la même que la probabilité que C mette lui-aussi plus de s secondes à résoudre le problème. Et ceci, même si A a déjà cherché pendant t secondes alors que C était déconnecté du réseau. Autrement dit, si on note T la probabilité de découvrir le nouveau bloc (pour A comme pour B ou C qui possèdent tous le même matériel), on a la relation :

P (T>t+s|T>t) = P (T>s)

Le membre de gauche représente la probabilité qu’a A de mettre encore plus de s secondes avant de trouver le résultat sachant qu’il a déja cherché pendant t secondes et le membre de droite représente la probabilité qu’a C de mettre plus de s secondes avant de trouver le résultat. Notons qu’on a juste besoin du fait que les conditions de minage sont les mêmes en t et à l’instant initial pour A comme pour C et qu’en t, la puissance de hachage relative de A n’a pas changé. En particulier,  on’a pas besoin que B et C existent réellement. J’ai juste introduit B pour dire que l’arrivée de C ne modifie pas fondamentalement la puissance de hachage globale du réseau. L’égalité est donc une conséquence directe du principe « one-CPU-one-vote ».

Modulo un argument de continuité faible, l’équation précédente montre que T suit une loi exponentielle.

Une loi nécessairement exponentielle

Chaque mineur a donc une probabilité de découvrir un bloc qui suit une loi exponentielle. En particulier l’ensemble du réseau possède un temps de découverte interbloc exponentiel car c’est Inf(T1,..,Tn) où T1,..,Tn sont les temps de validation de tous les mineurs (leur nombre est arbitrairement noté n) en compétition pour résoudre le problème. Les variables aléatoires T1,..,Tn sont indépendantes et suivent toutes des lois exponentielles. Il en résulte que Inf(T1,..,Tn) suit aussi une loi exponentielle. On applique ici un résultat classique de théorie des probabilités. Donc, le temps de minage interblocs suit une loi exponentielle et c’est une conséquence directe du principe « One-CPU-one-vote ». Il est par ailleurs facile de voir qu’une loi exponentielle dépend d’un seul paramètre (sa moyenne) et que son écart-type est égale à sa moyenne. Autrement dit, on ne peut pas réduire la variance d’une loi exponentielle sans réduire également sa moyenne. La moyenne de découverte des temps interblocs étant fixée égale à 10 minutes, on ne peut changer sa variance (égale au carré de la moyenne).

Dans le cadre du Bitcoin tel qu’il a été conçu par Satoshi Nakamoto, le fait que le temps de  recherche d’une preuve de travail suive une loi exponentielle découle  naturellement de la construction de cette preuve de travail avec la fonction de hachage SHA256 – supposée parfaite. Inverser SHA256 n’est possible que par brute-force et il y a tellement de candidats possibles que le peu qu’un mineur a déjà testé ne lui permet pas d’en savoir plus sur l’inverse ou les inverses recherchées.

Alors quoi ? Changer la preuve de travail pour réduire la variance ? Mais oui, pourquoi pas mais il faut savoir que cela remet en cause l’un des principes de base du Bitcoin. Une tentative de fork du Bitcoin qui souhaiterait implémenter cette nouvelle preuve de travail avec variance réduite pourrait-elle réellement prétendre encore s’appeler Bitcoin ? Peut-on encore appeler Bitcoin une cryptomonnaie qui ne respecte pas la règle « One-CPU-one-vote » ? A la limite, le principe pourrait être intéressant pour un réseau d’où l’on ne pourrait entrer et sortir à tout moment. Mais là encore, ce n’est pas Bitcoin.

Note : l’image est la couverture d’un petit livre édité par la maison d’édition italienne Antonio Tombolini Editore. Il s’agit d’une édition commentée de l’article fondateur du Bitcoin. Je décline toute responsabilité concernant les commentaires qu’on pourrait trouver dans ce livre que je n’ai pas lu. Je félicite néanmoins l’éditeur pour son excellente initiative.

PS. Encore plus pourri que je ne pensais !

En fait, j’étais extrêmement naïf concernant l’organisation de « Scaling Bitcoin 2017 » mais maintenant le pot au rose est découvert. L’événement est notamment financé par des ICO qui ont bien sûr autant à voir avec le bitcoin qu’une bouteille de coca-cola. Mais ce n’est pas tout. Les orateurs sont également pour certains parties prenantes de ces ICO qui ont donc payé plusieurs millions de dollars pour monter sur l’estrade… On est bien sûr très loin de Satoshi minant seul ses premiers blocs du bitcoin… Honte à ce comité pourri !

Quelques réactions à notre lettre ouverte

Rappelons les faits. Voir notre précédent article pour connaître le début de l’histoire.

– Nos deux propositions à « Scaling Bitcoin » ont été rejetées.

– Le programme de la conférence montre un recoupement entre les membres du comité et les orateurs (trois personnes).

– Le co-auteur du « chair » de la conférence a été invité à présenter leur dernier article.

Réactions folkoriques sur Twitter

Certains membres du comité ont réagi de manière surprenante sur Twitter. Voici un résumé. Pour connaître l’intégralité (mais c’est franchement sans intérêt), il suffit de consulter mon compte twitter.

Ethan Heilman, le « chair » de la conférence a soutenu qu’il s’agissait de pratiques courantes (ce qui est bien sûr faux) et qu’il n’y avait pas lieu de crier au scandale. Il a donné un lien vers une conférence annuelle intitulée « Financial Cryptography and Data Security » où il y a effectivement un recoupement.

Il a oublié de préciser que dans ce cas, et contrairement à « Scaling Bitcoin », la soumission est anonyme. Comme précisé sur leur site, « The regular and short paper submissions must be anonymous, with no author names, affiliations, acknowledgments, or obvious references. » Mis devant cette évidence, il a cessé de répondre.

Paul Sztorc, la personne du comité qui aurait vu l’article s’est spontanément manifestée de manière extrêmement grossière nous proposant immédiatement un rendez-vous sur YouTube pour nous « humilier » en direct. Il est évident qu’il n’est pas question pour nous de participer à une telle farce. Nous lui avons répondu : « Maths is not circus », lui demandant au contraire de nous faire parvenir son rapport sur l’article puisqu’il est d’usage que les « reviewers » écrivent un rapport sur les propositions reçues. Il a alors cessé de répondre, probablement parce qu’il n’a rien écrit. Vu son niveau (affligeant), même s’il a fait l’effort d’ouvrir l’article, je doute qu’il ait pu comprendre quoique ce soit.

Enfin, Peter Rizun qui est orateur au prochain « Scaling Bitcoin » et également « managing editor » de Ledger, une revue scientifique spécialisée sur la blockchain (à ne pas confondre avec Ledger, la start-up française fondée par Eric Larchevêque), nous a invité à lui soumettre notre papier de manière assez particulière : « Please, send us your boring article! ». Assez interloqués par le ton employé par un éditeur qui nous adresse la parole pour la première fois, nous avons cherché à alerter les autres éditeurs de Ledger du comportement pour le moins surprenant d’un des leurs. J’ai aussi voulu attirer l’attention du chancelier de l’Université de Pittsburgh qui édite la revue. Est-ce à cause de cela que finalement Peter Rizun nous a présenté ses excuses même si celles-ci sont pour le moins alambiquées ? Inutile d’en dire davantage.

Il nous paraît donc de toute évidence et aujourd’hui encore plus qu’hier que l’organisation de la prochaine conférence « Scaling Bitcoin » est une véritable farce. Tout se passe comme s’il s’agissait d’une bande de copains qui s’invitent entre eux et se défendent les uns les autres. Par ailleurs, il n’est pas possible de mettre de côté la liste impressionnante de sponsors. Cela saute aux yeux : il y a énormément d’argent en jeu et on peut comprendre que la pression doit être forte de la part de ceux qui veulent monter sur le devant de la scène.

En guise de résumé, je recopie un message de soutien en anglais reçu sur Medium de la part d’un dénommé « Alphonse Pace » que je ne connais pas  :

« Scaling Bitcoin is garbage now. Shame that such a good conference has been hijacked. ».

Et pour finir, aucune nouvelle de l’Université de Stanford qui doit préférer les sous des sponsors au scandale. C’est malheureusement ce que je suis en train de commencer à penser… Make America great again!

Lettre ouverte au président de l’université de Stanford et à la communauté Bitcoin

Ci-dessous la version française d’une lettre ouverte au président de l’université de Stanford et à la communauté Bitcoin. La version anglaise (officielle) est publiée sur Medium.

Le 4 et 5 novembre prochain aura lieu une grande conférence sur le bitcoin donnée à l’Université de Stanford. Il s’agit d’un cycle de conférences organisées chaque année par le comité « Scaling Bitcoin » qui s’est imposé comme une référence parmi toutes les conférences semblables. Fréquenté par une grande partie de l’écosystème bitcoin, c’est l’occasion d’assister aux dernières propositions pour développer encore davantage les possibilités du bitcoin.

Comme son nom l’indique, la conférence est centrée habituellement sur les problèmes d’échelle du bitcoin, sujet sur lequel la communauté n’en finit pas de se diviser et de débattre. Mais les thèmes de la conférence dépassent les seuls problèmes d’échelle. L’accent est mis également sur les problèmes de sécurité, d’anonymat et de fongibilité.

La conférence « scaling bitcoin » est itinérante et a pour principe de changer de continent à chaque fois. Nous étions nombreux à nous réjouir qu’elle ait lieu cette année à l’Université de Stanford après Milan l’an dernier. C’est une juste récompense vu toutes les activités de cette université en termes d’enseignement du fonctionnement des cryptomonnaies et de recherche sur ce thème.

La conférence marque ainsi un rapprochement symbolique entre le monde universitaire qui a longtemps dédaigné le bitcoin et le monde des cypherpunks au sein duquel il a fait la première fois son apparition.

On était donc en droit d’espérer le meilleur du monde académique au service du bitcoin. Or, c’est malheureusement tout le contraire qui est en train de se produire.

Nous avions soumis deux propositions d’exposé. La première était centrée sur l’un de nos articles sorti en février dernier. Cet article revoit et corrige le calcul approximatif de Satoshi concernant la probabilité de double-dépense et, pour la première fois, nous démontrions que cette probabilité tend bien exponentiellement vers zéro en fonction du nombre de confirmations, un résultat souvent annoncé mais jamais démontré. Notre deuxième proposition consistait en une étude de la stabilité des blockchains ; nous souhaitions disserter sur la convergence entre les intérêts privés et les intérêts publics en mettant en lumière des cas possibles d’instabilité jamais véritablement étudiés.

Ces deux propositions ont été rejetées. Nous étions bien sûr surpris et déçus car nous pensions sincèrement que nos travaux qui étudient le cœur du fonctionnement d’une blockchain en apportant des résultats mathématiques concrets avaient de bonnes chances d’être acceptées. Cela n’a pas été le cas. Soit.

Passée la déception d’avoir été rejetés, nous avons par curiosité jeté un coup d’oeil au programme finalement retenu. A côté d’une liste des exposés et des orateurs, se trouve la liste des personnes formant le comité de sélection.

Pour une question d’éthique, on était en droit d’attendre d’une grande institution comme Stanford que ces deux listes soient totalement disjointes. On ne peut être juge et partie. On ne peut pas examiner la qualité de nombreux travaux puis au final décréter que le meilleur, c’est le sien.

Les membres de ce comité de sélection n’ont manifestement pas la même opinion. Parmi les orateurs qui font partie des heureux élus, on compte ainsi trois membres de ce comité. Ils vont donc chacun faire un exposé après avoir examiné et décidé de rejeter les propositions des autres…

Il est possible que le comité se soit divisé les articles reçus et qu’aucun ne de ces auteurs n’ait voté pour lui-même mais seulement pour un de ses collègues, ce qui rend le scandale moins gros ou moins visible. Mais il demeure. Comment peut-on décemment accepter d’être membre d’une telle commission tout en étant force de propositions pour devenir orateur ?

A ces trois « anomalies », on doit en ajouter une quatrième plus sournoise. Le co-auteur du dernier article de celui désigné comme étant le  « Program Chair » de la conférence a été également invité à donner un exposé !

Par ailleurs, mais à ce point, c’est presque anecdotique : le « chair » de la conférence se présente comme un simple « PHD student » sur sa page personnelle, ce qui est surprenant car il s’agit en général d’une personne expérimentée qui se porte garant du bon déroulement des événements et du choix du comité.

Manifestement des règles élémentaires d’éthique scientifique mondialement acceptées n’ont pas ici été respectées. Est-ce que le but de la conférence est vraiment de donner au bitcoin ses lettres de noblesse ou au contraire de faire des petites carrières universitaires sur le dos du bitcoin ?

Au final, on se pose forcément la question : Satoshi Nakamoto aurait-il vraiment été invité par un tel comité de sélection ?

Cyril Grunspan (ESILV, France)

Ricardo Perez-Marco (CNRS, U. Paris VII, France)

Comment inverser une fonction ?

Je n’aurais jamais imaginé découvrir avec la célèbre fonction de Black-Scholes à quel point il peut être difficile d’inverser une fonction. Le problème n’est pas numérique ; il y a de nombreux algorithmes performants pour cela même s’ils ne sont pas tous connus du plus grand nombre. Il s’agit d’un problème d’asymptotiques : sous certaines hypothèses (grande ou petite maturité par exemple), il faut trouver le développement asymptotique de la volatilité en fonction du prix de l’option.

Je m’étais frotté à ce problème quand j’étais « quant » à Londres il y a plusieurs années et j’avais juste été capable de donner les premiers termes du développement. J’avais fini par abandonner complètement après avoir vu circuler un long article de Roger Lee et d’un de ses étudiants sur ce sujet au moment où je finissais de rédiger le mien. L’article de Lee a depuis été cité près d’une centaine de fois mais j’en avais toujours gardé un sentiment étrange ; je n’avais pas réussi à lire et comprendre vraiment en profondeur l’article de Lee (qui aujourd’hui encore reste abscons pour moi) et je restais persuadé que le problème devait se résoudre autrement et plus simplement.

C’est à ce moment que je suis revenu voir mon ami Joris van der Hoeven et très rapidement, tout s’est éclairé… Au final, nous répondons non seulement au problème posé mais en plus, nous donnons des algorithmes effectifs pour inverser des fonctions connues comme la fonction de Gauss, la fonction de Lambert, la fonction Gamma incomplète ou plus généralement des fonctions de type « exp-log » qui sont hautement tangentes à l’identité… Notre article est disponible ici.

Insistons sur le fait que le problème n’est pas simple a priori. Si une fonction est analytique au voisinage d’un point, son inverse fonctionnelle (lorsqu’elle existe) s’obtient facilement grâce au théorème des fonctions implicites. Cependant, si la fonction considérée n’est pas analytique en ce point, les choses sont nettement plus compliquées…

Donnons un exemple qui dépasse le cadre de la finance : étant donné y très proche de 1^{-}, trouver x tel que

\frac{1}{\sqrt{2 \pi}}\int^x_{- \infty} e^{-\frac{t^2}{2}} dt = y.

Peut-on exprimer x en fonction de y ? Au fond, inverser Black-Scholes n’est pas plus compliqué que résoudre ce problème déjà ancien…

Inversion de la formule de Black-Scholes

Voici la formule de Black-Scholes :

BS(S,K,T,\sigma) = S Q(d_+)-K Q(d_-)

Ici, S, K, T, \sigma désignent respectivement le prix du sous-jacent considéré (le prix d’une action par exemple ou un taux d’intérêt), le strike de l’option, la maturité de l’option et la volatilité. La fonction Q est la fonction Gaussienne Q(x)=\frac{1}{\sqrt{2 \pi}}\int^x_{- \infty} e^{-\frac{t^2}{2}} dt et d_{\pm}=\frac{\log \left( \frac{S}{K} \right) \pm\frac{\sigma^2 T}{2}}{\sigma \sqrt{T}}. Pour simplifier, on a supposé que le taux d’intérêt était nul.

Dans les années 70, Black-Scholes et Merton voulaient calculer le prix d’une option BS(S,K,T,\sigma) en fonction d’un paramètre appelé volatilité \sigma. Aujourd’hui, on veut au contraire calculer \sigma en fonction du prix de l’option…

Il y a au moins une raison à vouloir inverser Black-Scholes de manière théorique. Issus de modèles stochastiques décrivant la dynamique des actifs financiers, les prix d’options sont solutions d’équations aux dérivées partielles de la forme

\partial_{\tau} y = L.y

où \tau désigne le temps restant avant que l’option ne parvienne à maturité et L est un opérateur différentiel d’espace dont les variables sont des fonctions des paramètres du modèle. La plupart du temps, l’équation ci-dessus n’a pas de solution fermée exacte car les modèles considérés sont bien plus compliqués que celui de Black-Scholes. Et s’ils le sont, c’est bien sûr que le modèle de Black-Scholes ne parvient pas à décrire la réalité des marchés financiers et à expliquer notamment l’existence d’un « smile » de volatilité.

On est donc réduit à rechercher des approximations du résultat, ce qui conduit à des calculs de développements asymptotiques de prix d’option sous certaines hypothèses comme {\tau}\ll 1 ou {\tau}\gg 1 par exemple.

Différentes techniques ont été développées à cet effet. Il s’agit souvent de méthodes de perturbations utilisées en physique. On pourra consulter par exemple le livre d’Ivan AvramidiHeat Kernel Method and its Applications, professeur de mathématiques à l’École des mines du Nouveau-Mexique.

Or, on souhaite calculer non seulement le prix de l’option mais également et surtout sa volatilité implicite (dans le cadre d’une option vanille). Il faut voir cela comme d’un héritage. Black-Scholes est certes désuet mais on veut tout de même conserver les apparences et en particulier on souhaite toujours pouvoir manipuler le \sigma présent dans la  formule de Black-Scholes que l’on appelle volatilité implicite (il s’agit d’une mauvaise traduction de l’anglais implied volatility).

Bref, il s’agit d’opérer une transformation : passer d’un développement en prix à un développement en volatilité implicite. En théorie, il suffit d’appliquer pour cela la fonction inverse de la fonction de Black-Scholes. Seulement voilà, la fonction de Black-Scholes n’est pas analytique autour de {\tau}=0 ni de \tau=\infty. Ce n’est pas étonnant vu que le pay-off de l’option S\longmapsto (S-K)_+ = Max(S-K,0) n’est lui-même pas analytique et que la fonction gaussienne Q n’est-elle même pas analytique en +\infty comme on l’a rappelé plus haut… Cela rend la transformation plus compliquée.

A l’aide d’un petit tour de passe-passe, on peut montrer que le développement de la formule de Black-Scholes en temps très petit ou au contraire dans la limite où \tau est très grand est toujours de la forme :

y(x) = x + \alpha \log x + \varphi_0 + \sum_{i = 1}^n  \frac{\varphi_i}{x^i} + {\footnotesize \mathscr{O}} \left( \frac{1}{x^n}\right)

Si \tau\ll 1, on a \alpha = \frac{3}{2}, x=\frac{\log^2 \left( \frac{K}{S} \right)}{2\sigma^2 \tau} et y=-\log(\frac{C-(S-K)_+}{S}). Si \tau\gg 1, on a \alpha=\frac{1}{2} , x=\frac{\sigma^2 \tau}{8} et y=-\log(\frac{S-C}{S}). Dans les deux cas, C désigne le prix Black-Scholes C=BS(S,K,T,\sigma), \varphi_0, \varphi_1, ... sont des réels indépendants de \sigma et x\gg 1. Inverser Black-Scholes consiste donc à trouver x en fonction de y.

Fonctions hautement tangentes à l’identité

Plus généralement, on peut s’intéresser à une fonction réelle \phi dont le développement asymptotique en fonction de x\gg 1 est de la forme

\phi(x) = x + \phi_0 + \frac{\phi_1}{x} + \frac{\phi_2}{x^2} + \cdots+\frac{\phi_n}{x^n} +\mathscr{O} (x^{- n - 1 / 2})

pour tout entier n et où, cette fois-ci, \phi_0, \phi_1,... désignent des fonctions polynomiales en \log(x). Une telle fonction \phi est dite hautement tangente à l’identité. Elle est nécessairement inversible au voisinage de +\infty. Cependant son inverse fonctionnelle \phi^{<-1>} n’est pas simple à obtenir. Une idée pour obtenir le résultat est de considérer le problème non plus dans un ensemble de fonctions réelles mais dans un anneau algébrique du type {\Bbb A}={\Bbb R}[\log x][[\frac{1}{x}]]. Dans ce cas, le problème de la recherche de l’inverse fonctionnelle de \phi est semblable à un problème de recherche de zéro d’une fonction. En effet, la fonction \phi^{<-1>} est solution de l’équation

\phi(g) = x

qui peut se résoudre à l’aide d’une simple méthode de Newton en partant par exemple de g=x. L’existence d’une valuation sur {\Bbb A} (la valuation est définie par v(\frac{1}{x})=1 et v\left(\log(x)\right)=0) simplifie les choses et permet de majorer l’erreur entre la solution théorique et la solution approchée. En général, le bon cadre pour traiter ce genre de problème est de considérer \phi (x) comme une transsérie formelle et d’appliquer des résultats théoriques d’inverses fonctionnelles connues pour les transséries. Cependant, la signification analytique du résultat est perdue en général…

Nous montrons qu’un algorithme du type Newton peut encore s’appliquer dans un cadre purement analytique en travaillant sur un corps de Hardy muni d’une fonction dite raide (voir la définition dans notre article) permettant encore de définir une valuation. C’est le cas par exemple des fonctions dites « exp-log ». Tout découle de là…

Je n’aurais jamais su tout cela si je n’étais pas allé voir régulièrement Joris dans son bureau à l’X. Pour les lecteurs curieux, je signale qu’un travail colossal sur les transséries vient de paraître, écrit par Joris conjointement avec deux collaborateurs. Et encore, il ne s’agit que du premier tome…

Si vous voulez voir la formule donnant l’inverse fonctionnelle de la fonction y(x) donnée à la fin de la section précédente, jetez un coup d’oeil à la dernière page de l’article !

Merci Joris !

Supplément à l’étude du Bitcoin

Voici (en anglais) l’article que j’ai coécrit avec Ricardo Perez-Marco sur l’étude des probabilités de double-dépense dans le réseau Bitcoin. Il s’agit notamment d’une correction à l’article fondateur du Bitcoin, Bitcoin: A Peer-to-Peer Electronic Cash System. Nous donnons une formule fermée pour la probabilité de réussite de double-dépense et nous prouvons le fait que cette probabilité tend exponentiellement vers zéro en fonction du nombre z de confirmations requises, un résultat souvent cité mais jamais démontré. Enfin, nous menons une analyse plus fine de cette tentative de double dépense en prenant en compte le temps mis par les honnêtes mineurs pour miner z blocs, une information disponible par le marchand qui s’apprête à envoyer son bien de consommation au possible attaquant.

J’ai écrit « correction ». C’est un mot un peu fort mais pourtant, on a beau le tourner dans tous les sens, la partie mathématique de l’article (section 11 « Calculations ») est légèrement incorrecte.

Le raisonnement de Satoshi

Son approximation

Satoshi estime que les mineurs honnêtes qui disposent d’une puissance de calcul relative égale à p mettent exactement \frac{z.\tau_0}{p} pour miner z blocs avec \tau_0 = 10 minutes. C’est évidemment une grossière approximation. En réalité, les honnêtes mineurs mettent en moyenne \frac{\tau_0}{p} pour miner un bloc et \frac{z.\tau_0}{p} pour miner z blocs. Cette approximation sert ensuite à Satoshi pour dire que pendant ce temps, l’attaquant qui cherche à réaliser une double-dépense a réussi à miner {\bf N'}(\frac{z\tau_0}{p}){\bf N'} est un processus de Poisson d’intensité qq = 1-p est la puissance de calcul relative dont dispose l’attaquant. Le fait qu’il y ait ici un processus de Poisson est tout à fait naturel. Cela vient du fait que la fonction de hachage SHA256 est supposée parfaite. Cette hypothèse a pour conséquence que le temps de minage inter-bloc suit une loi exponentielle et que le processus de comptage qui compte le nombre de blocs minés est un processus de Poisson. Par suite, le nombre de blocs minés par l’attaquant suit une loi de Poisson d’intensité \frac{q.z\tau_0}{p}. C’est ce qu’a écrit Satoshi.

Le calcul final

La probabilité de réussite de double-dépense s’obtient ensuite simplement en utilisant la formule des probabilités totales : P(A) = \sum_{k} P(A | B_k).P(B_k). Ici, A désigne l’événement « l’attaquant réussit son attaque » et B_k désigne l’événement « l’attaquant a réussi a miné k blocs au moment où les honnêtes mineurs viennent de miner z blocs ». La probabilité P(B_k) a été vue plus haut. Ici z est fixé.

Lorsque k>z, on a bien sûr P(A | B_k) = 1 et lorsque k<z, l’attaquant a autant de chance qu’un joueur qui joue contre la banque à pile ou face avec un retard de z-k : à chaque lancer de pièce de monnaie truquée en faveur de la banque (la banque a une probabilité p de gagner) le joueur avance ou recule de 1. S’il finit par rattraper la banque, il a gagné. Ce calcul est classique. Satoshi renvoie au célèbre livre de Feller An introduction to probability theory and its applications. C’est un exemple élémentaire de marche aléatoire. On a P(A | B_k) = (\frac{q}{p})^{z-k}. D’où la formule finale que donne Satoshi en réarrangeant un peu les termes de sa somme : P(A) = 1-\sum_{k=0}^{z}\frac{\lambda^k e^{-\lambda}}{k!}(1-(\frac{q}{p})^{z-k}) à la suite de quoi, Satoshi présente un petit code en C pour calculer numériquement cette somme.

Le vrai calcul

Une loi binomiale négative

Seulement voilà, le temps mis par les honnêtes mineurs est aléatoire et n’a aucune raison d’être égale à sa moyenne \frac{z.\tau_0}{p}. La formule donnée plus haut pour P(A) est fausse. En réalité, si l’on désigne par {\bf S}_z le temps mis par les honnêtes mineurs pour miner z blocs, la loi de {\bf S}_z est une loi Gamma de paramètre (z,\tau_0) et le nombre de blocs minés par l’attaquant au moment où les honnêtes mineurs découvrent leur zème bloc est {\bf N'}({\bf S}_z). Un petit calcul montre que la loi de {\bf N'}({\bf S}_z) est une loi binomiale négative de paramètre (z,p). C’est normal. Tout se passe en effet comme si la course au minage était un tirage multiple avec remise d’une urne remplie de boules noires et blanches jusqu’à l’obtention de z boules blanches. Tirer une boule noire signifie : « l’attaquant découvre un nouveau bloc » et tirer une boule blanche signifie « les honnêtes mineurs découvrent un nouveau bloc ». Au total, le nombre de boules noires tirées représente le nombre de blocs minés par l’attaquant au moment où les honnêtes mineurs découvrent leur zème bloc…

La formule de Meni Rosenfeld

La véritable probabilité de réussite P(z) de double dépense est P(z) = P[{\bf N'}({\bf S}_z) >z]+\sum_{k=0}^{z} P[{\bf N'}({\bf S}_z) = k] (\frac{q}{p})^{z-k}. En utilisant le fait que {\bf N'}({\bf S}_z) est une loi binomiale négative de paramètre (z,p) comme expliqué ci-dessus, on en déduit que  P(z) = 1-\sum_{k=0}^{z-1}(p^z.q^k-q^z.p^k)\dbinom{k+z-1}{k}. Nous ne le savions pas au moment de la rédaction de notre article, nous ne l’avons découvert qu’après mais cette formule avait déjà été publiée par Meni Rosenfled dès décembre 2012 dans Analysis of hashrate-based double-spending… Notons que Meni Rosenfeld vient tout juste de publier un article qui a l’air fort intéressant : Decentralized Prediction Market without Arbiters.

Une formule fermée

En fait, on peut triturer la formule de Rosenfeld pour obtenir une formule fermée. Cela vient de ce que la fonction de répartition d’une loi binomiale négative est une certaine fonction bêta incomplète régularisée. On montre que la probabilité de réussite de double-dépense est tout simplement P(z) = I_{s}(z,\frac{1}{2}) avec s = 4 p q, q = 1-p et I_x(a,b) = \frac{\Gamma(a+b)}{\Gamma(a).\Gamma(b)}.\int_0^x t^{a-1} (1-t)^{b-1} dt\Gamma est la célèbre fonction Gamma : \Gamma(x) = \int_{0}^{\infty} t^{x-1} e^{-t} dt pour x>0. Notons que la fonction beta régularisée incomplète est une fonction extrêmement classique et implémentée dans tous les logiciels de calcul moderne. En R par exemple, la fonction qu’il suffit d’invoquer est « pbeta ». Et inutile pour cela de charger des packages…

Autrement dit, Satoshi s’est fatigué pour rien ! En menant un calcul correct, sans aucune approximation, on obtient une formule élémentaire pour la probabilité de réussite de double-dépense. La conclusion que l’on peut en tirer, je crois, est que Satoshi était un génie mais n’était pas un vrai mathématicien. Certains avaient avancé le nom de John Nash mais cela nous semble impossible.

Des asymptotiques…

Ensuite, nous avons calculé l’asymptotique de P(z). Grâce à notre formule fermée mettant en jeu une fonction bêta, il est facile de montrer que P(z)\sim \frac{s^z}{\sqrt{\pi (1-s) z}} avec toujours s= 4 p q. Quant à la probabilité (erronée) de Satoshi que l’on note P_{SN} (z), nous montrons que l’on a P_{SN} (z)\sim \frac{e^{-z c(\frac{q}{p})}}{2} avec c(x)=x-1-\log(x). Il est vrai que cette probabilité tend exponentiellement vers 0 mais simplement, la formule est fausse !

Comparaison entre les deux probabilités

D’après les formules données pour P(z) et P_{SN}(z), il s’avère que Satoshi a sous-estimé la probabilité de double-dépense. On a clairement d’après les formules ci-dessus : P(z)\prec P_{SN}(z). On peut aussi s’amuser à calculer un rang explicite à partir duquel Satoshi s’est (vraiment) trompé, i.e., un rang à partir duquel on a P(z)< P_{SN}(z)… Cela donne lieu à des calculs d’inégalités un peu pénible avec les fonctions Gamma. Il ne s’agit que d’un jeu mathématique…

Une analyse plus fine

Enfin, on calcule la probabilité de réussite de double-dépense P(z,\kappa) sachant que les honnêtes mineurs ont mis \kappa \tau pour miner z blocs avec \tau = \frac{z.\tau_0}{p} (cf plus haut). Autrement dit, \kappa mesure l’écart par rapport à l’hypothèse de Satoshi… Là encore, on obtient une formule fermée bien que légèrement plus compliquée que celle donnant P(z). Explicitement, on a P(z,\kappa) = 1 - Q(z,\kappa z\frac{q}{p}) + (\frac{q}{p})^z e^{\kappa z \frac{p-q}{p}} Q(z,\kappa z)Q désigne la fonction Gamma régularisée incomplète. On analyse cette fonction de \kappa, P(z,\kappa). Notons que P_{SN}(z) = P(z,1).

A la fin de l’article, nous avons publié des tables pour P(z,\kappa) en fonction de z et q = 1-p.

Author’s Bitcoin Beer Address

Je dois dire que ce fut un plaisir pour moi de travailler avec Ricardo. J’espère que notre collaboration ne se terminera pas là. Les maths du bitcoin sont évidemment loin d’être finies d’explorer !

Si vous avez aimé notre travail et souhaitez encourager notre recherche (au pub), vous pouvez nous envoyer des sous ! Voici notre ABBA (Author’s Bitcoin Beer Address) :

1KrqVxqQFyUY9WuWcR5EHGVvhCS841LPLn

Vous pouvez aussi plus sobrement financer notre séminaire de cryptofinance pour nous donner les moyens de développer la recherche académique autour du bitcoin et de la blockchain.

Séminaire de Cryptofinance

Last, but not least, nous avons naturellement dédié cet article à André Warusfel qui fut notre professeur de mathématiques bien-aimé et qui est décédé récemment. Cher Warus, vous auriez certainement apprécié le bitcoin et ses mathématiques !

IOTA : pour en finir avec la blockchain !

« A vous de travailler ! »

La première fois que j’ai découvert le projet Iota, j’ai immédiatement pensé – nous sommes peu de chose – à la sympathique caissière d’une des boucheries de quartier à laquelle je me rends parfois pour faire mes courses (oui, j’ai la chance d’habiter un quartier où il y a encore quelques commerces dit de « proximité »)… Elle a en effet l’habitude de recevoir ses clients qui souhaitent payer par carte bancaire, en leur présentant un terminal de paiement électronique et de les apostropher ainsi avec un air malicieux  : « A vous de travailler ! » – feignant de croire que composer son code secret à quatre chiffres est un exercice qui mérite toute notre attention…

Derrière sa boutade qui la fait rire à chaque fois, sait-elle seulement qu’il y a là ainsi résumé les derniers développements les plus ingénieux concernant les systèmes de paiement modernes ? Développements qui pourraient jouer un rôle considérable dans le fameux internet des objets encore en gestation, les transferts d’ordre et les possibilités de micro-paiements…

Capture-d’écran-2014-10-11-à-19.27.37

 

Des développeurs, des mineurs, des utilisateurs, une blockchain

Reprenons Bitcoin et tous ses successeurs, Ethereum compris. Une crypto-monnaie, c’est en général : des développeurs, des mineurs et une blockchain. Le tout s’appuie sur une caution scientifique qui peut prendre la forme d’une simple prépublication, ou d’une fondation. (Ouvrons une parenthèse. Ce qui s’est passé le 2 août à l’Université de Stanford est à ce titre significatif. Le génial et modeste Dan Boneh – je signale l’ouverture de son cours en ligne élémentaire de cryptographie I le 5 septembre prochain sur Coursera – s’est adressé à un public averti de développeurs de Bitcoin Core et de mineurs dont certains venaient de très loin, en brossant plusieurs défis futurs à relever. Le texte de son intervention est disponible à cette adresse. A lire pour tous les matheux « bitcoiners »…)

Toutes les cryptomonnaies partagent un même modèle : une distinction claire et nette entre les utilisateurs qui ne sont là que pour donner des ordres et passer de nouvelles transactions et les mineurs qui regroupent toutes ces transactions, vérifient qu’il n’y a pas de fraude, les enregistrent dans des blocs et se portent garant de la sécurité du réseau. En théorie, tout le monde peut être mineur. Mais en pratique, le minage est l’affaire de véritables entreprises essentiellement basées dans des zones géographiques où le coût de l’électricité est (quasiment) nul.

Un mot tout de même ici sur les cryptomonnaies avec preuve d’enjeu (telle est la traduction douteuse ? retenue par Wikipedia pour « Proof of Stake »). Dans ce cas, le minage est un peu particulier car il est complètement virtuel et ne nécessite pas de matériel informatique performant pour mener des calculs. Voir la page 231 du livre de Princeton sur le Bitcoin dans cette édition.  La distinction entre utilisateurs réels et mineurs qui sécurisent le réseau est donc moins forte que dans le cas de cryptomonnaies avec preuves de travail car participer à la « loterie » du nouveau bloc est accessible à tous ; tout le monde peut participer sans effort particulier… Il n’en reste pas moins qu’on n’a pas toujours forcément envie de participer à la grande loterie du minage – surtout si on n’est pas très riche car alors on a très peu de chance de gagner… Le modèle reste le même : une blockchain et des mineurs.

Vu sous cet angle, la différence avec le monde traditionnel de la finance n’est pas flagrante puisque dans ce monde qui est le nôtre, la sécurité des transactions est en général apportée par des banques qui se basent sur des réglementations internationales. Et pas plus le client de sa boucherie de quartier qui paye avec sa carte bancaire que le spéculateur qui achète ou vend ses bitcoins sur une plateforme d’échange, nul n’a l’impression, avec son opération, de participer à la sécurité du réseau qu’il utilise. Il a au contraire le vague sentiment de créer un problème qui sera géré par des personnes compétentes (on est en droit de l’espérer !).

Pour en finir avec la blockchain !

Et puis voilà IOTA qui vient tout changer… Au départ, il y a une start-up en 2014 qui cherche à développer de nouveaux types de microprocesseurs afin de donner vie à un certain internet des objets (on reconnaît dans le début d’IOTA, l’acronyme « IOT » pour « Internet of Things »). Les développeurs comprennent vite qu’il manque une technologie faisant le lien entre tous les objets connectés. On voudrait pouvoir les relier autour d’une blockchain d’autant plus que David Sønstebø et Sergey Ivancheglo qui sont à la tête du projet sont de grands connaisseurs des blockchains et des cryptomonnaies. Mais aucune ne peut convenir en pratique. En effet, aucune n’assure la possibilité de micro-transactions sans frais de transaction. De plus, toutes les blockchains connues possèdent des problèmes d’échelle qui peuvent se révéler trop contraignants.

Dans le même temps, sur le forum Nxt que fréquentait régulièrement Serguey à ses débuts sous le pseudonyme « Come-from-Beyond » (certains imaginent même pour cela qu’il est l’énigmatique créateur de cette cryptomonnaie apparue fin 2013), des internautes se mettent à réfléchir à une autre façon d’organiser les transactions que par blocs. Et si, au lieu de regrouper les transactions par paquet, on les laissait libres individuellement tout en les reliant astucieusement les unes aux autres ? Après tout, dès 2013, avec le protocole GHOST, Aviv Zohar et Yonatan Sompolinsky avaient bien ouvert la voie en invitant à prendre en compte toute la structure d’arbre des transactions afin de renforcer le protocole des cryptomonnaies existantes (Vitalik Buterin reprendra du reste cette proposition dans Ethereum).

Mais comment peut-on relier des transactions entre elles s’il n’y a pas de blocs ni de mineurs ?  On pourrait obliger chaque nouvelle transaction X, pour pouvoir exister, à approuver des transactions passées. Il faudrait pour cela qu’au moment d’enregistrer X sur le réseau, on soit obligé de sélectionner des transactions déjà existantes. Dans la rédaction de X, il faudrait donc contraindre l’utilisateur à choisir des transactions passées, vérifier qu’il n’y a pas d’incompatibilité entre elles et l’obliger à résoudre un problème du type preuve de travail – dont on peut espérer qu’il serve à sécuriser le réseau. Il n’y aurait plus de bloc mais toute transaction constituerait en quelque sorte un mini-bloc.

Telle était l’idée qui commençait à émerger sur le forum de Nxt et dans les les premiers essais réalisés par David et Serguey. En passant une transaction, l’utilisateur n’agirait donc plus seulement dans son propre intérêt mais aussi dans l’intérêt de tous. Une simple transaction servirait à sécuriser l’ensemble du réseau… Il n’y aurait plus de registre commun consultable par tous et qui augmente d’une page toutes les dix minutes en moyenne comme pour le Bitcoin. Il n’y aurait tout simplement plus de blockchain ! De quoi réjouir tous ceux  qui n’en peuvent plus de voir ce mot galvaudé et repris par des gens servant des intérêts tout autre de ce pourquoi il a été crée à l’origine… Il reste bien sûr à imaginer concrètement le protocole et les règles pour éviter les tentatives de doubles dépenses mais d’immenses possibilités nouvelles semblent s’offrir à nous… Au lieu d’une suite linéaire de blocs, on serait ainsi conduit à voir l’ensemble des transactions comme un graphe orienté acyclique. Nous sommes en 2015, le projet IOTA est en train de se former.

Markov est dans la place…

Et puis voici maintenant Sergei Popov qui apporte son expertise mathématiques. Sergei est un grand mathématicien, professeur à l’université Unicamp au Brésil et membre de la communauté Nxt. Grâce à lui, IOTA va gagner une caution scientifique. Il va formaliser les idées de David et Serguey et écrire le papier fondateur d’IOTA.

L’idée ingénieuse qu’il a eue est d’avoir en quelque sorte « probabilisé » le graphe acyclique des transactions cité plus haut, c’est-à-dire de l’avoir transformé en une véritable chaîne de Markov.

Concrètement ici, ce qui permet d’éviter les tentatives d’escroquerie à la double dépense, c’est la possibilité d’explorer cette chaîne de transactions en tant que chaîne de Markov comme le ferait un randonneur par une méthode du type Monte-Carlo. Les résultats de ces randonnées aléatoires permettent de disqualifier les transactions frauduleuses.

Essayons d’expliquer brièvement le fonctionnement d’IOTA. Ce qui permet d’apporter de la confiance au réseau, ce n’est plus le nombre de blocs qui recouvre une transaction donnée (dans le Bitcoin, si une transaction est enfouie sous six ou sept blocs, elle est considérée comme absolument sure). Ici, chaque transaction possède un poids cumulé qui évolue au cours du temps. Il est défini comme le nombre de transactions ultérieures qui l’ont approuvées directement ou indirectement. Plus exactement, c’est la somme de la puissance de travail utilisée par toutes ces transactions.

Une transaction légale va naturellement devenir « lourde » du fait de toutes les transactions qui vont venir après et progressivement pointer vers elle. Et de même que dans le Bitcoin, un vendeur attend qu’une transaction donnée soit recouverte par six ou sept blocs avant de pouvoir donner son bien de consommation au client, de même ici, le vendeur va attendre que la transaction du client ait atteint un certain poids cumulé critique.

Au moment de sa rédaction, une nouvelle transaction va choisir grâce à l’algorithme de Popov deux transactions en attente de validation. Ces deux transactions sont le résultat de deux randonnées aléatoires par une méthode de Monte-Carlo en partant d’un endroit du graphe extrêmement sur (pas besoin de remonter à l’origine). Pour éviter d’approuver des tentatives de fraude, il faut donc trouver une bonne mesure de probabilité qui permet de rester sur la partie du graphe qui ne contient que des transactions honnêtes.

Quelle probabilité choisir ?

Moralement, une transaction honnête a un poids nettement plus important qu’une transaction frauduleuse (il n’y a pas véritablement de transaction illégale mais j’entends par transaction frauduleuse une transaction qui reflète une tentative de double dépense). En effet, dans un fonctionnement normal, une transaction honnête est reprise par l’ensemble du réseau tandis qu’une tentative de double dépense n’est choisie que par un attaquant. On considère ici qu’il n’est pas possible de détenir seul plus de la moitié de la puissance de calcul du réseau.

La mesure de probabilité doit donc être choisie de sorte qu’il soit quasiment improbable de passer d’un site x du graphe possédant un poids cumulé H(x) important à un autre site y qui lui soit relié mais possédant un poids H(y) très faible. Au passage, notons qu’une transaction qui pointe vers y pointe a fortiori vers x, de sorte que H(x) > H(y). Il est alors naturel de prendre pour mesure de probabilité une mesure telle que la probabilité de passer de x à y soit proportionnelle à exp(-(H(x)-H(y)). Et voilà la probabilité sur la chaîne de Markov… Au final, c’est la croissance rapide de l’exponentielle qui rend très improbable la possibilité de sauter d’une partie honnête du graphe à une partie malhonnête…

De plus, si par malheur, les deux transactions choisies étaient incompatibles entre elles (parce que l’une d’elle provient d’une tentative de double dépense par exemple) alors, l’algorithme de Popov ne retient que la transaction la plus susceptible d’être acceptée par les autres. Il faut pour cela répéter plusieurs randonnées aléatoires et obtenir in fine une mesure de probabilité sur l’ensemble des extrémités du graphe.

A-t-on touché le sommet avec IOTA ? On est en droit de le penser…

desierto

Notons pour le folklore qu’on peut toujours imaginer la présence de mineurs dans ce réseau mais vu qu’il n’y a pas de bloc, il n’y a pas non plus de récompense. Le seul travail de minage possible consiste à émettre une transaction vide (sans transfert d’argent). Ce travail n’est pas rémunéré mais comme toutes les autres transactions, il sécurise le réseau car il contribue à augmenter le poids cumulé des transactions honnêtes.

Tirons également la conséquence du fait qu’il n’y a plus de blockchain. Plus de blockchain signifie plus de mineurs classiques et donc plus de création monétaire. C’est donc que toute la quantité de monnaie a été émise dès le début…

Ce qu’il y a de fascinant dans l’histoire de l’humanité, c’est que bien souvent, les inventions n’arrivent pas seules à un endroit donné mais bien souvent simultanément à plusieurs endroits différents. Il en est ainsi de l’invention de l’écriture notamment. Si j’écris cela, c’est qu’il se trouve qu’indépendamment des débuts d’IOTA, Sergio Lerner sur son blog imaginait lui aussi mettre fin à la distinction entre mineurs et utilisateurs. Mais trop préoccupé par la réussite de Rootstock, il ne lui a sans doute pas été possible de développer son intuition et d’implémenter ses DAGcoins…

Il y a maintenant une communauté d’utilisateurs d’IOTA : plus de trois cents pages de fils de discussion sur bitcointalk et un forum de plus en plus actif sur le site d’Iotatoken. On imagine sans mal des objets connectés qui passent des ordres sur Iotatoken. Et le tout, évidemment sans frais de transaction…

XQ7L078W

Que dire de plus ? L’article de Popov contient d’autres petits calculs extrêmement intéressants comme une utilisation totalement naturelle (mais que je n’ai jamais vu ailleurs) de la théorie des grandes déviations pour prouver qu’IOTA résiste à un certain scénario d’attaque. Tout ne peut être dit en un article… Je vous laisse visiter le site d’IOTA.

Bravo à Serguei Popov, David Sønstebø et Sergey Ivancheglo… Chapeau bas messieurs !