La blockchain est encore jeune, mais quelques applications sont déjà opérationnelles : traçabilité des aliments, sécurisation des transactions commerciales, désintermédiation dans la publicité, indemnisation par un assureur, digitalisation des titres financiers, possession d’objets dans le cadre d’un jeu vidéo… Mais quels sont les principes fondamentaux de la blockchain ? Un sujet d’actualité, celui des crypto-monnaies, domaine fondateur du concept, est l’occasion d’une belle investigation mathématique.
Le Bitcoin, dont la capitalisation s’élève à 120 milliards de dollars, est la crypto-monnaie la plus connue. Certaines entreprises de commerce électronique acceptent déjà le paiement en Bitcoins. Facebook, à travers son projet de crypto-monnaie Libra (finalement mis à mal par les autorités publiques), cherche à fluidifier les échanges commerciaux B2B (« business to business » : activités d’une entreprise visant une clientèle d’entreprises) ou B2C (« business to customer » : activités d’une entreprise visant directement le consommateur) à l’échelle mondiale, à accroître le nombre des acteurs dans ces domaines et donc à générer de nouveaux besoins publicitaires qui augmenteront ses revenus. Du coup, les crypto-monnaies suscitent une opposition des régulateurs, Banques centrales ou États.
Quelques principes de cryptographie
La blockchain n’existerait pas sans la cryptographie, l’art de rendre confidentielles des données et, surtout, de les authentifier. Deux primitives, des algorithmes de bas niveau, sont essentielles : le hashing (hachage) et la signature.
Le hachage calcule, à partir d’une donnée fournie en entrée, une empreinte numérique servant à identifier rapidement la donnée initiale, au même titre qu’une signature sert à identifier une personne. Le standard ISO SHA (pour Secure Hash Algorithm) transforme un bloc de quelques kilo-octets en un hash de 256 bits d’une façon imprévisible et non inversible. Il est impossible de retrouver le message initial à partir du hash. Il s’agit d’une impossibilité pratique car il suffirait en fait d’essayer toutes les combinaisons pour le retrouver, mais cela nécessiterait un temps de calcul monstrueux. Le hashing peut s’appliquer sur un grand volume de données en les décomposant en blocs et en chaînant les calculs (le calcul du hash du bloc i + 1 incorporant le résultat du calcul sur le bloc i).
La signature, elle, s’appuie sur des notions mathématiques telles que l’arithmétique modulaire. En sécurité informatique, ce concept date de quarante ans, avec l’invention du schéma RSA (du nom de ses inventeurs, Ronald Rivest, Adi Shamir et Leonard Adleman). Il est utilisé universellement sur Internet, selon les protocoles SSL ou TLS. Le RSA suit le principe de la signature manuscrite : capacité de contrefaçon limitée, vérification aisée. En informatique, on parle de bi-clé. L’une, privée et ne devant être divulguée à personne, sert à calculer la signature d’un message ou bloc de données quelconque, préalablement hashé. L’autre, publique, pouvant être communiquée à tout le monde, permet de vérifier la signature du message ou bloc de données.
Ces algorithmes se basent sur des fonctions difficilement inversibles. Ainsi, si N est un nombre premier de l’ordre de 2128 (qui compte trente-neuf chiffres en écriture décimale), l’entier C étant connu, calculer le reste r de la division euclidienne de Cu par N est « facile » (quelques millisecondes sur un PC), mais calculer u à partir du seul reste r est difficile et incomparablement plus long. C’est le problème du logarithme discret. RSA se base sur des fonctions d’un autre type, mais elles procurent le même genre d’asymétrie.
Cryptiques courbes elliptiques
Le principe se transpose aujourd’hui sur l’ensemble des points des courbes elliptiques, ces courbes algébriques satisfaisant une équation du type y2 = x3 + bx + c, où x et y appartiennent à un corps fini. Les points de cette équation peuvent être dotés d’une loi de groupe abélien fini. Ils sont complétés par un point fictif à l’infini, qui joue le rôle de l’élément neutre. Si P et Q sont deux points de la courbe, la droite passant par P et Q (ou, si P et Q sont confondus, la tangente en P) coupe la courbe en un nouveau point. Ceci permet de définir une « addition » (notée +). En répétant μ fois cette opération, on peut définir le multiple R d’un point P. Calculer R à partir de μ et de P est facile : la complexité est polynomiale. Calculer μ à partir de R et de P est très difficile : la complexité est exponentielle. On retrouve ainsi l’asymétrie du logarithme discret, utilisable pour un schéma de signature.
Des clients font entre eux des transactions à travers le monde. On s’intéressera ici au paiement : A paye un montant m, libellé dans l’unité du système considéré, à un client B. Nous vivons dans un contexte global, avec des acteurs multiples et autonomes. On ne se base pas sur l’autorité d’une entité unique, comme le réseau des cartes bancaires VISA ou MasterCard ; on doit au contraire accepter des intervenants multiples, appelés nœuds, qui travaillent de concert en s’échangeant des données, suivant des règles, donc des protocoles, bien établis. Et ce, sans que l’on puisse être sûr que ces règles soient toujours suivies à la lettre, que ce soit intentionnellement (tricherie) ou non (pannes dans les systèmes, erreurs dans les échanges…). Donc les crypto-monnaies doivent être tolérantes aux fautes, c’est-à-dire être capables de détecter et de corriger les fautes. Autrement dit, elles doivent établir un consensus* sur les traitements.
Les clients envoient leurs transactions vers des nœuds qui, par des techniques peer to peer (« bouche à oreille viral »), les propagent à d’autres nœuds. Un flux de transactions à traiter se constitue ainsi. Bien sûr, si A paye à B la somme de m unités, il faut que A soit d’accord et qu’il dispose au moins de m unités. La signature de A est nécessaire. Chaque client doit avoir une bi-clé qui lui est propre, et un identifiant unique qui est un hash de sa clé publique mais qui ne révèle pas son identité réelle. Ainsi, pour vérifier que B a bien reçu m de A, il suffit de vérifier que A a signé un ensemble de données comprenant m, l’identité de B et le lien avec la transaction qui a crédité A d’au moins le montant m. Ce travail de vérification est fait par les nœuds lorsqu’ils reçoivent les transactions.
Les machines à états permettent de décrire les systèmes séquentiels.
Une représentation du type machine à états est utilisée (voir le schéma). La machine évolue périodiquement d’un état à un autre grâce au traitement du groupe de transactions, le bloc.
Une gigantesque base de données distribuée aux quatre coins du monde est mise à jour continuellement par le flux des transactions. Toutes les crypto-monnaies fonctionnent de cette façon ! Bitcoin se base sur les blocs de transaction qu’il mémorise depuis son démarrage en 2009. Libra se base sur les états. Etherum, un concurrent de Bitcoin, exploite les deux approches.
Bitcoin : comment ça marche
Le schéma en page suivante présente un extrait de la blockchain avec des blocs (consécutifs ou non), i, j, k… où i < j < k… Chaque transaction affecte des gains à des dépenses : X paye 8 unités à A, puis Y paye 3 unités à A. A possède au total 11 unités et va ainsi pouvoir payer 9 unités à B en en gardant 2 pour lui. Il y a donc ici deux bénéficiaires. Toutes les dix minutes environ, un nouveau bloc est ajouté, contenant les nouvelles transactions, et c’est cet ensemble qui est appelé blockchain ou chaîne de blocs. La blockchain est donc un fichier partagé, accessible en lecture à quiconque.
Pour ce qui est de l’écriture dans ce fichier, on compte quatre points critiques : comment valider les nouvelles transactions (et empêcher les doubles dépenses, par exemple empêcher A d’utiliser deux fois le gain de 3 unités provenant de Y) ? comment garantir l’intégrité de ce qui a déjà été validé (et empêcher Y d’effacer YA3 pour faire oublier sa dépense) ? comment répartir les rôles de façon à ce que n’apparaisse pas une « autorité de fait », se chargeant seule de toutes les vérifications ? comment enfin, si la plupart des participants sont honnêtes, parvenir au résultat que le système est sûr et donc que toute faute est détectée et rendue inopérante ?
Les réponses se trouvent dans les processus de contrôle, par les nœuds, des transactions du nouveau bloc, et de minage, permettant de constituer une preuve de travail (proof of work), sorte de sceau démontrant que le bloc a été dûment vérifié et joint à la chaîne de blocs, garantissant son intégrité. Ce sceau est en fait le hash d’un ensemble de données : hash du bloc précédent, hash du bloc courant et nonce.
Le nonce est un nombre choisi de façon à ce que le sceau ait n bits de poids fort (les n bits « les plus à gauche ») à zéro. Les propriétés de la fonction de hashing font que ces n bits ont un caractère aléatoire, la probabilité de tomber sur n zéros étant 2–n.
En d’autres termes, la recherche du nonce nécessite en moyenne 2n–1 calculs. Actuellement, n vaut 70, et, comme 270 est « proche » de 1021, mille milliards de milliards de calculs sont à faire. Le terme de « minage » convient bien à ce processus hautement répétitif ! Le nombre de bits pour n est d’ailleurs adapté automatiquement, tous les cent blocs, de façon à maintenir le rythme moyen d’un nouveau bloc toutes les dix minutes. Ce processus nécessite une grande puissance de calcul.
Le premier nœud qui termine le processus ajoute un nouveau bloc à la chaîne et est rémunéré. Un nœud qui veut tricher, par exemple créer une double dépense à son avantage, doit réussir à rajouter à la chaîne un bloc litigieux, mais ceci provoquera la création d’une nouvelle branche de la chaîne par les nœuds honnêtes, évitant ce bloc. Avec l’hypothèse que les nœuds honnêtes ont plus de la moitié de la puissance de calcul totale, cette branche croîtra plus vite que la branche litigieuse. Les actions litigeuses sont ainsi rendues inopérantes.
Libra : un processus basé sur les états
Dans l’état i – 1 apparaissent les positions des comptes des différents clients au temps
i – 1. Pour établir un consensus sur l’état i, on fait voter les nœuds sur le nouvel état résultant du traitement des transactions du bloc i. Parmi les N nœuds (N = 4 ici), l’un est leader, les autres sont valideurs.
Pour chaque période i, trois phases apparaissent :
• Bi : le leader constitue un bloc de transactions, les traite et calcule le hash du nouvel état, et envoie aux autres nœuds le bloc et le hash ;
• Vi : les valideurs traitent le bloc reçu et envoient au leader leur accord signé s’ils trouvent le même hash que le leader ;
• Ci : établissement du consensus. Vote sur la base d’un quorum de signatures obtenues des valideurs : le leader agrège les signatures du quorum, ce qui constitue avec le hash de l’état un sceau du nouvel état, et les nœuds en déduisent qui est le leader suivant.
La crypto-monnaie Libra prévoit le cas de problèmes de transmissions entre nœuds (erreurs, délais), ainsi que les comportements malhonnêtes. Soit f le nombre de nœuds fautifs ( f < N). Il y a donc h = N – f nœuds honnêtes. Si q est la taille du quorum et si q > f , il contiendra toujours au moins un nœud honnête. Si q ≤ h, le système ne peut pas être bloqué si les malhonnêtes se taisent, puisqu’il y a suffisamment d’honnêtes. Suite à des erreurs, deux quorums différents pourraient apparaître, mais, si q > f + h / 2, il y aura forcément au moins un nœud honnête en commun, donc impossibilité de deux quorums. Ces contraintes aboutissent à N > 3f . Autrement dit, on s’arrangera pour que le nombre N des nœuds soit au moins le triple de la pire estimation du total des erreurs et fraudes. Les points critiques vus pour Bitcoin sont donc ici résolus, un état de Libra précisant la balance des comptes de chaque utilisateur.
* Le succès médiatique du mot blockchain peut, dans le cas de certaines applications, mener à son utilisation quelque peu abusive. C’est le cas quand n'apparaît pas un besoin de consensus du fait de l'existence dans ces applications d'un unique acteur naturel jouant le rôle d'autorité. Dans ce cas, il s'agit plutôt d'une simple base de donnée distribuée.
Jean-Claude Pailles est membre de EESTEL, une association d’experts européens de haut niveau en systèmes de transactions numériques.
Lire la suite