Démystifions Blockchain

Il y a près de dix ans, un article publié sous le nom de Nakamoto décrivait un algorithme mettant en œuvre le Bitcoin. Au-delà de l’avenir de cette cryptomonnaie, beaucoup s’accordent à prédire le remplacement d’institutions financières centralisées par des algorithmes répartis, comme celui de Nakamoto. Le but ici est de démystifier cet algorithme ainsi que le problème qu’il résout, en partant de deux choses que l’on sait de Nakamoto. Il n’est jamais allé à Marrakech et il ne connaît pas l’algorithmique répartie.

Si Nakamoto était allé à Marrakech…

Il aurait visité la Place Jamaa El Fnaa, une place classée au patrimoine immatériel de l’humanité, mais dans laquelle on fait le commerce de choses très matérielles. Nakamoto aurait peut-être été tenté d’acheter des tapis. Il serait peut-être allé à la porte d’argent, une des nombreuses boutiques de la place. Le patron, que j’appellerais Ali pour des raisons de confidentialité, y stocke une collection unique de quelques milliers de tapis venus de villages de l’Atlas. Ali en vend aux touristes. Mais il paye aussi ses employés avec ses tapis. A leur tour, les employés payent aussi avec, d’autres commerçants.

Contrairement aux touristes, ces commerçants laissent leurs tapis dans la caverne d’Ali. Ce dernier note sur son cahier toutes les transactions effectuées. Quand Serge le vendeur de babouches « donne » un tapis à Lahcen le vendeur d’olives, cela est noté par Ali dans son cahier. Si Lahcen donne ensuite son tapis à Lhoucein, vendeur d’épices, cela est noté plus bas dans le cahier.  Nakamoto aurait aimé cette monnaie indépendante. Mais il aurait moins aimé qu’elle soit contrôlée par une seule personne : Ali.

Nakamoto aurait proposé aux commerçants son algorithme décentralisé. Il est facile de se passer de Ali, s’il ne s’agit que d’assurer que personne ne donne un tapis qu’il n’a jamais possédé. En effet, les nouvelles vont très vite sur la place et si quelqu’un donne un tapis à Serge, les commerçants l’apprennent vite. Tout se passe comme si tout le monde possédait une copie du cahier des transactions. Lahcen n’acceptera jamais de Serge un tapis que ce dernier n’a jamais possédé ou ne possède plus.

Mais comment éviter la double dépense ? 

Comment éviter que Serge ne triche en donnant son tapis à la fois à Lahcen et à Lhoucein ? Ce problème est trivialement résolu si les transactions passent par Ali. Mais comment faire sans passer par une entité centrale ? C’est précisément le problème posé dans l’article de Nakamoto. Ce dernier, expert en algorithmique classique, sait que le monde des problèmes informatiques centralisés est divisé en deux classes : la classe P des problèmes qui peuvent être résolus par des algorithmes polynomiaux (rapides) et la classe NP des problèmes dont on peut vérifier les solutions rapidement, mais qui semblent n’être solubles que par des algorithmes exponentiels (lents). Très intuitivement, l’idée de l’article de Nakamoto est d’utiliser un problème de la classe NP pour élire des coordinateurs qui jouent temporairement le rôle d’ Ali en ordonnançant des transactions.

Voici comment s’exécuterait l’algorithme de Nakamoto à Marrakech.

La transaction consistant pour Serge à donner son tapis à Lahcen est diffusée sur la place. Elle n’est validée que lorsqu’un coordinateur décide de son classement dans le cahier des transactions. N’importe qui peut prétendre à ce rôle de coordinateur : celui qui est élu pour coordonner gagne un tapis. L’idée de Nakamoto, inspirée de [2], est de demander aux prétendants au rôle de coordinateur de résoudre une sorte d’immense Sudoku, fabriqué avec des nombres générés de la transaction de Serge à Lahcen, mais avec énormément de cases vides. Le Sudoku ne peut être résolu qu’en le remplissant au hasard et la probabilité que deux candidats y arrivent en même temps est proche de zéro. Si un candidat résout le Sudoku, il diffuse sa solution avec la transaction. Lahcen vérifie que la solution est juste et accepte la transaction de Serge.

Mais l’algorithme est cher, et peu démocratique. La surenchère des moyens informatiques utilisés pour avoir une plus grande chance d’être coordinateur de transactions Bitcoin conduit aujourd’hui à une consommation d’énergie équivalente à celle d’un pays industrialisé. De plus, la latence est grande car, même si la probabilité d’élire deux coordinateurs au même moment est faible, elle est non nulle. Pour éviter une double dépense, il est nécessaire d’attendre qu’une transaction soit largement diffusée (Serge → Lahcen) pour s’assurer qu’aucune transaction conflictuelle (Serge → Lhoucein) n’ait été validée par un coordinateur concurrent. Par ailleurs, l’algorithme de Nakamoto remplace un coordinateur perpétuel par des coordinateurs temporaires. Même si la motivation de Nakamoto était de s’affranchir d’un contrôle centralisé, son algorithme n’empêche pas vraiment cela. Une institution qui réunirait une grosse puissance de calcul contrôlerait la monnaie. C’est d’ailleurs un peu le cas aujourd’hui car les coordinateurs viennent d’un tout petit sous-ensemble de régions du monde.

Des centaines d’alternatives à l’algorithme de Bitcoin ont été proposées.

Aucune n’a réussi à combiner à la fois de bonnes performances avec un haut niveau de fiabilité, même quand elles supposent un système fermé ou le nombre total de participants est connu. Cela n’est pas surprenant. Toutes ces alternatives essayent de reproduire l’idée de Nakamoto : remplacer un coordinateur perpétuel par des coordinateurs temporaires afin d’assurer que toutes les copies du cahier des transactions obéissent au même ordre total. Il s’agît de résoudre le problème de consensus. Or, on se heurte ici à un résultat fondamental d’algorithmique répartie : ce problème est impossible de manière déterministe si le temps de communication n’est pas borné (asynchronisme) et l’un des participants peut être incorrect [3]. Toutes les alternatives qui tentent d’assurer que les copies du cahier des transactions sont exactement les mêmes contournent l’impossibilité du consensus en adoptant des solutions probabilistes et/ou synchrones, c’est à dire coûteuses et lentes. Certes le consensus est suffisant pour éviter la double dépense, mais est-il nécessaire ? La réponse est non.

Si Nakamoto avait connu l’algorithmique répartie…

Il saurait que les problèmes informatiques impliquant plusieurs machines se divisent aussi en deux catégories. Il y a d’un côté les problèmes difficiles, qui sont similaires au consensus dans le sens où ils ne peuvent être résolus dans un contexte asynchrone, et ceux considérés faciles, qui sont solvables dans un contexte asynchrone. Nakamoto se serait demandé si le problème de la double dépense est un problème difficile ? Il aurait réalisé que la réponse est non.

La démonstration, elle, n’est pas facile [4]. Mais pour en donner l’idée, revenons à l’exemple illustrant le problème de la double dépense. Supposons que Serge veuille tricher et donner le même tapis à Lahcen et à Lhoucein. Imaginons pour simplifier la discussion ici que le système est fermé et composé de 1000 participants dont au maximum 100 pourraient ne pas se comporter de manière correcte. Les corrects, eux, n’acceptent jamais deux transactions conflictuelles. Si Lahcen apprend qu’un quorum formé de 501 participants accepte la transaction stipulant que le tapis de Serge lui est destiné, il sait qu’il peut l’accepter. Il sera impossible à Serge de convaincre un autre quorum que le tapis va à Lhoucein. Si le système est ouvert, on peut mettre en œuvre une idée similaire aux quorums grâce à un mécanisme d’échantillonnage uniforme.

Épilogue

L’algorithme de Nakamoto résout le consensus : un problème difficile et universel. Quand on le résout, on peut résoudre tous les problèmes répartis. Il n’est pas surprenant que l’algorithme de Nakamoto soit inefficace. Mais le problème de la double dépense, suffisant pour la mise en œuvre d’une cryptomonnaie, est beaucoup plus facile que le consensus et ses solutions peuvent être bien moins inefficaces.

Rachid Guerraoui, Professeur au Collège de France et à l’EPFL.

Références

[1] S. Nakamoto. Bitcoin : a peer-to-peer electronic cash system. 2008.

[2] C. Dwork et M. Naor. Pricing vis processing or combatting junk mail. Annual Cryptology Conference. 1992.

[3] M. Fisher, N, Lynch and M. Paterson. Impossibility of Consensus with one faulty process. Journal of the ACM 1985.

[4] R. Guerraoui, P. Kouznetsov, M. Monti, M. Pavlovic et A. Seredinshi. AT2 : Asynchronous Trustworthy Transfers. Arxiv 2018.