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.