Bitcoin et contenu en calcul

Quand on examine le protocole technique du bitcoin, on tombe sur un point apparemment insignifiant qui le complique bizarrement et semble mystérieux concernant la mesure de la longueur d'une blockchain. En réalité il est important. Beaucoup plus, c'est la mise en œuvre pratique — pour la première fois semble-t-il— d'une idée théorique fondamentale de la théorie du calcul : l'idée que certaines chaînes de caractères ne peuvent résulter que d'un long calcul, autrement dit qu'elles possèdent un « contenu intrinsèque en calcul », ou selon les termes de la théorie «une grande profondeur logique de Bennett ».

Dans le cas du bitcoin, la présence de cette propriété n'est pas assurée par une démonstration en bonne et due forme, mais seulement par le savoir faire des cryptologues. Il n'en reste pas moins que cette idée est décisive pour que l'ensemble du protocole tienne debout. Il n'est pas sûr que ceux qui ont conçu le détail du protocole bitcoin aient eu pleinement conscience de ce qu'ils faisaient : ils donnaient une forme réelle et pratique à une idée qui jusque là restait théorique et sans application.

Ce qui est mentionné dans le document initial de 2008 de Satoshi Nakamoto (ici)  décrivant les principes généraux du protocole bitcoin est sans ambiguïté pour qui sait lire. L'anonyme Satoshi Nakamoto écrit : « The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it ». Remarquez le  « invested in it », nous allons comprendre son extrême importance. Expliquons tout cela.

La valeur de la blockchain

Le fichier de toutes les transactions bitcoin appelé la blockchain (parfois écrit block chain) est la mémoire centrale et unique de la crypto-monnaie. C'est lui qui détermine ce qu'il y a sur les comptes : pour savoir qui possède quoi, on lit ce fichier. C'est le consensus sur ce qui y est écrit qui détermine la richesse en bitcoins de chaque compte, dont le total aujourd'hui (15/02/2015) dépasse 3,5 milliards de dollars. Ce fichier est complété toutes les 10 minutes environ par une nouvelle page (block) ajoutée par le mineur gagnant les 25 bitcoins du concours permanent destiné à rémunérer ceux qui acceptent de gérer le protocole de la monnaie (les « mineurs »).

Pour gagner, il faut être le premier à résoudre une énigme assez difficile. La difficulté de cette énigme est ajustée régulièrement (toutes les deux semaines, précisément tous les 2016 blocks) pour que l'ensemble des mineurs qui mènent des calculs ne la résolve qu'en 10 minutes environ. S'ils vont trop vite, le protocole accroît automatiquement la difficulté des nouvelles énigmes, s'ils ne réussissent plus en 10 minutes le protocole diminue la difficulté.

Il en résulte que si 50 000 mineurs (estimation proposée ici) sont au travail, alors résoudre l'énigme demande environ 50000 fois dix minutes (à peu près un an) avec le dispositif moyen d'un mineur... et donc beaucoup plus pour une machine ordinaire de bureau. Comme la solution de l'énigme est inscrite sur la blockchain avec la nouvelle page ajoutée, celle-ci porte des données qui attestent qu'elle a demandé un important travail de calcul pour sa constitution. La blockchain a donc, en elle, un contenu qui résulte d'un long calcul, cela en chaque page. Le total de ce qui est ainsi inscrit dans la blockchain est énorme puisque puisqu'elle comporte environ 300 000 pages aujourd'hui.

La solution donnée par le gagnant à l'énigme qui lui était posée est mise dans la page qui est ajoutée à la blockchain. Chacun peut vérifier (rapidement) que le gagnant n'a pas triché (c'est-à-dire a correctement résolu le problème qui lui était soumis) car cela demande peu de calcul : résoudre l'énigme est long et difficile, vérifier que celui qui le résout l'a vraiment résolue est facile.

Cette inscription dans la blockchain du résultat de longs calculs rend la création d'une fausse blockchain très difficile, et impossible en pratique, sauf peut-être pour un attaquant près à investir plusieurs centaines de millions d'euros (voir le texte précédent de ce blog). Pour dire tout cela simplement : faire une simili-blockchain est impossible car cela coûterait une fortune. Plus simplement encore : la blockchain est très chère.

Quand plusieurs blockchains concurrentes sont présentes (blockchain fork) sur le réseau pair à pair du bitcoin, par exemple à la suite du succès presque au même moment en deux endroits éloignés du réseau de deux mineurs, les mineurs ont la consigne (programmée dans les logiciels qu'ils utilisent) de choisir entre les différentes blockchains dont ils sont informés de l'existence. Pour que tout le monde choisisse la même blockchain (recherche d'un consensus) la consigne est de « choisir la plus longue des blockchains ». C'est ce qu'ils font tous, avec pour effet d'éliminer les blockchains sauf une, la plus longue. Cela reconstitue un état cohérent du système (une seule blockchain) et donc une liste de transactions valides qui sera la même pour tous.

Le critère « choisir la blockchain la plus longue » dans un premier temps signifiait « choisir la blockchain ayant le plus grand nombre de pages ». On s'est aperçu que c'était dangereux car n'importe qui pouvait faire une fausse blockchain ayant un nombre de pages plus grand que les autres en reconstruisant tout depuis le début et ne faisant pas évoluer la difficulté des problèmes posés aussi rapidement que pour la vraie blockchain, et donc en ne résolvant pour chaque page nouvelle que des problèmes faciles. Si le critère « plus longue blockchain » avait signifié « chaîne ayant la plus grand nombre de pages », il aurait été facile de perturber gravement la blockchain et... le bitcoin n'existerait sans doute plus depuis longtemps.

La longueur de la chaîne est maintenant définie par « la chaîne ayant un taux de hash cumulé  (on additionne la difficultés moyennes de chaque block) le plus élevé » (ici). Autrement dit, ce qui compte est la quantité de calculs réellement déposée dans la blockchain, et c'est celle qui en contient le plus qui est considérée comme seule valide. Il n'est plus possible de fabriquer une fausse blockchain entière à moindre coût. Faire une simili-blockchain exige vraiment un calcul cumulé au moins aussi grand que celui inscrit dans la vraie blockchain.

Faire une fausse blockchain n'est possible que pour celui qui dispose à lui seul d'une capacité à calculer des hash plus grande que celle tous les autres réunis. C'est l'idée des attaques 51%, qui sont potentiellement dévastatrices (ici)

La définition de la «longueur d'une blockchain » telle que l'utilise le protocole bitcoin est donc un détail crucial. Elle signifie sans le moindre doute que la blockchain contient du calcul et que c'est ce contenu en calcul qui la singularise des autres éventuelles fausses blockchains qu'on pourrait tenter de lui substituer. La notion de contenu en calcul est au cœur du protocole bitcoin.

Cette idée de « contenu en calcul » pourtant essentielle à la solidité du protocole n'est pas très clairement perçue. La preuve la plus simple en est que la valeur totale de la blockchain qui détermine le choix entre diverses blockchains différentes quand il y a « fork » n'est publiée nulle part. On l'obtient à partir des difficultés des énigmes de chaque page et on peut l'évaluer en février 2015 à environ 10^24 calculs de SHA256.

La théorie

Il se trouve qu'une notion de contenu en calcul (à ne pas confonde avec la notion que contenu en information ou complexité de Kolmogorov) a été introduite en théorie de la complexité en 1988 par Charles Bennett... sans bien sûr faire référence au bitcoin qui n'existait pas (voir ici)

Charles Bennett en proposait une définition abstraite ne se basant pas sur des calculs de fonction de hachage, mais sur un modèle abstrait de calculateur universel (les machines « efficiently universal »). Pour Bennett la mesure de contenu en calcul qu'il nomme profondeur logique (logical depth) d'une chaîne de caractère S est le temps de calcul d'un court programme produisant S. Prendre le temps de calcul du plus court programme produisant S, convient en première approximation («court» ayant un sens parfaitement précis si on choisit une machine universelle). Une série d'arguments proposée par Bennett justifie la définition de Bennett, voir ici.

La notion est rattachée à la complexité de Kolmogorov (puisqu'elle se base sur les courts programmes produisant S) mais elle n'y est pas équivalente.

La leçon de ce travail théorique sur la complexité des objets numériques est qu'il y a deux façons principales de considérer la « valeur d'une chaîne de caractères » :

(a) la quantité d'informations qu'il faut, au minimum, pour la décrire ; c'est le contenu incompressible en information de S ou complexité de Kolmogorov de S.

(b) la richesse en calcul de la chaîne ; c'est sa profondeur logique, qui est première approximation mesurable par le temps de calcul mis par un programme aussi court que possible produisant S.

Le «théorème de la croissante lente» de Bennett stipule qu'une chaîne ayant une grande profondeur logique (c'est-à-dire un fort contenu en calcul au sens de la théorie) ne peut pas être créée rapidement par un algorithme déterministe, et ne peut l'être rapidement qu'avec une probabilité infinitésimale par un algorithme probabiliste (opérant des tirages au sort). Ce théorème est une confirmation que la profondeur logique de Bennett est bien une mesure de contenu en calcul : pour avoir une chaîne de caractère ayant une grande profondeur logique, la seule méthode est de mener beaucoup de calculs à partir d'une de ses représentations courtes.

Bennett propose une série de procédés théoriques pour engendrer des chaînes ayant une grande profondeur logique, mais aucun ne semble jamais avoir eu de l'importance dans une application réelle.

Deux contenus en calcul ?

Dans les deux cas (la blockchain du bitcoin et la profondeur logique de Bennett), l'idée est la même : une chaîne de caractères possédant un fort contenu en calcul est impossible à imiter rapidement, ou, ce qui revient au même, ne peut être obtenu qu'en mettant en œuvre de lourds et coûteux moyens (en argent ou en temps et/ou en énergie).

Avec la blockchain dont le contenu en calcul assure la solidité de la cryptomonnaie bitcoin, on dispose d'une version concrète et matérielle de l'idée de Bennett. C'est remarquable et cela confirme indirectement qu'avec ce nouveau type de protocole, il se produit quelque chose de radicalement nouveau qui marque un pas dans l'évolution de la science du calcul. En devenant capable de mettre de la valeur dans une chaîne de caractères, et en utilisant cette valeur comme verrou pour garantir un protocole, on invente une nouvelle façon d'utiliser la puissance de nos machines, et on révolutionne l'informatique. Dès lors, qu'avec cette idée fondamentale et nouvelle, on crée des applications jugées impossible auparavant — comme une monnaie purement numérique —  ne doit pas nous surprendre !

Démonstration ou conjectures ?

Est-il est possible de démontrer que les blockchain du bitcoin ont une grande profondeur logique ? Peut-être, mais c'est sans doute difficile, car pour cela il faudrait commencer par démontrer plusieurs propriétés de la fonction SHA256 justifiant que les preuves de travail qui utilisées par le bitcoin en sont véritablement, autrement dit qu'il n'existe aucun raccourci permettant de rapidement résoudre les énigmes posées aux mineurs.

La pratique concrète et la théorie de la complexité, chacune à leur façon utilise aujourd'hui une notion de « contenu intrinsèque en calcul ». Pour le bitcoin c'est une notion essentielle et il faut espérer que personne ne viendra montrer que ce que nous conjecturons être du calcul impossible à accélérer et à mener à moindre coût est faisable rapidement sans dépense.

La théorie serait utile si elle réussissait à aller plus loin qu'elle ne le fait aujourd'hui. Elle pourrait proposer des modèles de blockchain différentes, contenant du calcul au sens fort et mathématiquement attesté. Cela permettrait de consolider les protocoles des monnaies cryptographiques, qui cesseraient de s'appuyer sur des conjectures (concernant les fonctions SHA256) ce qui est un peu ennuyeux. Même s'il semble peu probable que cela se produise rapidement, il est bon d'en avoir conscience et de comprendre la nature profonde de ce que les cryptologues ont tenté de faire sans peut-être s'en rendre compte.

Une fois encore la théorie du calcul et les urgences de la cryptographie sont en décalage, obligeant les protocoles utilisés à reposer sur des conjectures plutôt que sur des théorèmes. Décidément, les mathématiques sont toujours en retard sur les nécessités pratiques. La théorie et la pratique des mathématiques de la complexité exigent toujours plus de chercheurs en mathématiques !

 

Trois remarques pour finir

A. Théorème de croissance lente

Le protocole bitcoin repose sur une forme de la loi de la croissance lente de Bennett. Celle-ci est importante, et c'est certain, elle le sera de plus en plus.

B. Contenu en calcul facile à contrôler

Avec le bitcoin les chaînes «profondes» sont facilement vérifiables : sous les hypothèses adéquates à propos de la fonction de hachage SHA256, s'assurer que la blockchain a un fort contenu en calcul est facile. Cette visibilité d'un contenu en calcul ne va pas de soi en général : il est facile de concevoir une chaîne profonde dont la profondeur est difficile à établir ; il suffit de la chiffrer. Le bitcoin utilise une catégorie particulière de chaînes profondes.

Cette facilité de vérification que la blockchain est profonde montre que posséder un contenu en calcul (« être profond » ) n'est pas nécessairement une propriété cachée. C'est peut-être un début d'explication au fait que nous reconnaissons facilement sans presque jamais nous tromper qu'une structure de notre environnement est vivante. Tous les êtres vivants sont profonds, nous classons facilement les structures du monde selon ce critère vivant/non-vivant, qui, de notre situation sur terre, est presque toujours équivalente à profond/non-profond ».

C. Fractale, beauté ?

Les fractales sont belles, non pas parce qu'elles ont un grand contenu en information (c'est presque toujours l'inverse : les fractales ont toutes une assez faible complexité de Kolmogorov), mais plus vraisemblablement parce qu'elles contiennent beaucoup de calculs. Cependant « être profond (au sens de Bennett) » n'est pas équivalent à « être beau » ; personne ne peut dire qu'une blockchain est belle ; pour notre œil, sa profondeur n'est pas directement perceptible. Une théorie computationnelle de l'esthétique a à rendre compte de cela. Elle reste à élaborer.