Preuve de travail

Un système de validation par preuve de travail (en anglais : proof of work, PoW) est, en informatique, un protocole permettant de repousser, sur un environnement client-serveur, des attaques par déni de service ou d'autres abus de service tels que les spams.

Ce système de preuve de travail est aussi utilisé dans un cadre précis, pour la validation des transactions de la blockchain de certaines crypto-monnaies comme le Bitcoin. Cette vérification par les mineurs de bitcoins est récompensée par l'émission de nouveaux bitcoins au bénéfice des vérificateurs.

Concept

Comme preuve de travail, le serveur requiert du client d'effectuer une petite tâche sous forme d'un calcul par exemple. Le concept a d'abord été envisagé par Cynthia Dwork d'Harvard et Moni Naor de l'Institut Weizmann dans un article de 1993. Le terme « preuve de travail » ou PoW a été formalisé, par la suite, dans un document de 1999 par Markus Jakobsson (en) et Ari Juels.

Une caractéristique essentielle du concept de preuve de travail est l'asymétrie du coût de mise en œuvre. En effet, le travail doit être difficilement réalisable pour l'auteur de la requête (appelé aussi le prouveur), alors qu'il est facilement vérifiable par le serveur (appelé aussi le vérificateur). Cette notion est diversement réalisée dans les applications pratiques : ce peut être un temps minimal d’attente avant d'être servi, un petit problème mathématique à résoudre (en), un puzzle à craquer par calcul ou une taxe demandée au requérant (à l'image d'un timbre fiscal pour un service que rend l’administration). La preuve de travail ne doit pas être confondue avec un CAPTCHA, qui exige d'un être humain de démontrer sa capacité à résoudre rapidement un problème sur lequel un ordinateur « sécherait ».

Contexte

Une des premières mises en œuvre de la preuve de travail est Hashcash qui cherche à prévenir le pourriel. Dans ce système, le contenu de chaque e-mail individuel est chiffré, y compris l'adresse du destinataire et la date d'envoi, selon un algorithme ayant un certain coût d'ordinateur pour l'expéditeur. Envoyer un unique courriel ne coûte presque rien, mais le publipostage (et donc potentiellement le pourriel) requiert une telle quantité de calcul à l'ordinateur qui envoie les messages que sa mise en œuvre est inenvisageable. En revanche, le destinataire de l’e-mail peut très facilement déchiffrer son contenu. L'inconvénient de cette approche est une consommation d'énergie et de temps de processeurs pour l'expéditeur

Exemple

Il est demandé à un processeur de réaliser une preuve de travail consistant à coder une variation de « Bonjour le monde ! » en utilisant la fonction de hachage SHA-256 jusqu'à trouver une empreinte qui débute par quatre zéros. La variation consiste à ajouter un nombre à la fin de la chaîne de caractères. Le processeur devra réaliser 33 681 tentatives pour réussir.

• « Bonjour, monde!0 » ⇒ a9efd73638806846d0495fb92e2deba6e2e1ad5bc453e28e5fdc1334c97c21a8
• « Bonjour, monde!1 » ⇒ f767b47fd98fab25d08bd155c42708b434ac86bfa8d8b95b1457146e86b728e5
• « Bonjour, monde!2 » ⇒ fad41d13e759487a3d70a09c66c3e8ae8e9803f1fadba5411e039c35ac01f8b9
• …
• « Bonjour, monde!33678 » ⇒ c8c15f22d9c2a9ce84f6c8ca5d5943e3bbc2d39758474c3d969c17359e6cf212
• « Bonjour, monde!33679 » ⇒ d109eb920aef296041c7b878eea20f1abc8fb957ea59bdf130d1dcd810722c2a
• « Bonjour, monde!33680 » ⇒ 0000abebe9c6554c85176b8e9f9f3f4ed9b7e8dc856a7b5cb9177bf7b22e1871

Produire 33 681 hachés sur un ordinateur moderne ne représente pas beaucoup de travail (la plupart des ordinateurs peuvent atteindre au moins quatre millions de hachages par seconde) mais il existe aujourd'hui des systèmes de preuve de travail beaucoup plus complexes, qui requièrent des preuves de travail pouvant dépasser, en 2016, 2 milliards de GH/s (gigahachage par seconde, soit 2 milliards de milliards de hachages par seconde) dans le cas de certaines crypto-monnaies comme le Bitcoin.

La vérification de l'empreinte numérique par un ordinateur est en revanche beaucoup plus rapide et moins consommatrice d'électricité.

Variantes

Il existe deux familles de protocoles différents pour fournir une preuve de travail.

Protocoles de défi-réponse

Les protocoles de preuve de travail par défi-réponse supposent un lien direct et interactif entre le demandeur (le client) et le fournisseur (le serveur). Le client demande au fournisseur de choisir un défi requérant un travail. Lorsque la solution est trouvée, le demandeur la renvoie au fournisseur qui la vérifie, la valide et sert la requête. Dans ce système, la difficulté est graduée par rapport à la charge de travail du fournisseur.

Protocole de défi-réponse.

Protocoles de vérification de solution

Dans les protocoles de vérification de solution, le problème n'est pas posé par le serveur, au contraire il fait partie intégrante du protocole et lorsque la solution est trouvée par le client, celle-ci est soumise par le protocole au serveur qui peut facilement la vérifier. La plupart de ces problèmes sont issus de procédures itératives probabilistes non bornées telles que celles du protocole Hashcash.

Protocole de vérification de solution.

Liste de protocoles

Les systèmes de preuve de travail les plus largement utilisés sont ceux des crypto-monnaies comme le protocole SHA256, Scrypt, Ethash, Blake-256, CryptoNight, HEFTY1, Quark, SHA-3, scrypt-jane, scrypt-n, ou des combinaisons de certains d'entre eux.

D'autres systèmes existent aussi, mais ne sont pas utilisés pour les crypto-monnaies :

• Résidu quadratique d'un grand nombre premier
• Protocole d'identification de Fiat-Shamir
• Protocole d'Ong–Schnorr–Shamir
• Inversion partielle de hash
• Séquençage de hash
• Puzzle
• Puzzle basé sur un échange de clés Diffie-Hellman
• Protocole Moderate
• Protocole Mbound
• Protocole Hokkaido
• Arbre de Merkle
• Hashcash utilisant une double itération de la fonction de hachage SHA-256
• Hashcash utilisant la fonction de hachage scrypt
• Momentum birthday collision
• Cycle de Cuckoo
• Protocole de tour guidé en puzzle

Utilisations dans les crypto-monnaies

Processus

Dans les crypto-monnaies utilisant la méthode de validation par preuve de travail pour ajouter un bloc supplémentaire à la chaîne de blocs, chaque mineur du réseau doit réaliser des calculs coûteux en temps et en énergie afin de chiffrer l'ensemble des transactions d'un bloc ainsi que les transactions chiffrées de la chaîne de bloc précédente. Dans la mesure où un bloc est créé à intervalle régulier, la difficulté pour trouver la solution au chiffrement est ajustée en fonction du nombre de participants du réseau à l'instant du calcul (ou suivant le temps de calculs des blocs précédents) mais aussi en fonction du nombre de transactions contenues dans le bloc et la chaîne de bloc précédente.

L'ordinateur ou le groupe d'ordinateurs qui trouvent en premier la solution du chiffrement diffusent le résultat aux autres participants du réseau qui peuvent facilement valider sans requérir de la puissance de calcul. Lorsque la solution est validée, elle est diffusée à l'ensemble du réseau. Le mineur ayant trouvé la solution est récompensé en monnaie nouvelle selon les modalités définies par le protocole de la crypto-monnaie. Dans les blockchains les plus courantes, les mineurs se rassemblent donc en pool de minage pour obtenir une puissance de calcul suffisamment conséquente et obtenir des résultats plus intéressants. Depuis quelques années, en raison de l'augmentation de la valeur des crypto-monnaies et de la difficulté des preuves de travail, des pirates utilisent illégitimement les ordinateurs de leurs victimes pour miner des crypto-monnaie. Ce procédé s'appelle le cryptojacking.

Chaque bloc contient le hachage du bloc précédent, ainsi chaque bloc a une chaîne de blocs qui contiennent tous les deux une grande chaîne de travail. Changer un bloc N (qui n'est possible qu'en faisant un nouveau bloc N+1 contenant le chiffrement de la chaîne de bloc précédente N-1) requiert un travail considérable car il faut recalculer d'abord le chiffrement du bloc N avant de chiffrer le bloc N+1. La falsification est donc difficile voire impossible.

Haute consommation d'électricité

Un inconvénient reste la consommation d'électricité, qui peut être source de consommation d'énergie carbonée, nocive pour l'environnement . Beaucoup^{[Combien ?][source insuffisante]} de crypto actifs à vocation non monétaire n'utilisent pas ou plus la preuve de travail, mais expérimentent d'autres algorithmes de consensus. Ethereum a finalement changé son consensus en preuve d'enjeu en septembre 2022. Ce changement est le premier à être déployé à si grande échelle (sécurisation d'un capital de plus de 150 milliards de dollars mi 2022), et permettra d'apprécier le niveau de sécurisation et de décentralisation de la preuve d'enjeu sur le long terme et à grande échelle.

La Banque des règlements internationaux a critiqué le système des validation par preuve de travail nécessaire à la blockchain, qualifiée de désastre environnemental.

ASIC et mining pools

Dans la communauté bitcoin, il existe des groupes qui travaillent ensemble dans des mining pools. Certains mineurs utilisent des circuits intégrés spécialisés (ASIC) pour la preuve de travail. Cette tendance aux pools de minage^[Quoi ?] et aux ASIC a rendu le minage de certaines crypto-monnaies économiquement impossible pour la plupart des joueurs qui n'ont pas accès aux ASIC les plus récents, à des sources d'énergie à faible coût à proximité, ou à d'autres avantages particuliers.

Certains systèmes de validation par preuve de travail prétendent être résistants aux ASIC, c'est-à-dire qu'ils limitent à un ordre de grandeur inférieur les gains d'efficacité qu'un ASIC peut avoir par rapport à du matériel conventionnel tel qu'un GPU. La résistance aux ASIC présente l'avantage de rendre l'exploitation minière économiquement réalisable sur du matériel conventionnel, mais augmente également le risque associé qu'un attaquant puisse brièvement louer l'accès à une grande quantité de puissance de calcul non spécialisée sur du matériel conventionnel pour lancer une attaque des 51 %.

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Proof of work » (voir la liste des auteurs).

Annexes

Bibliographie

• [Abadi et al. 2005] (en) Martín Abadi, Mike Burrows, Mark Manasse et Ted Wobber, « Moderately hard, memory-bound functions », Transactions on Internet Technology (TOIT), ACM, vol. 5, n^o 2,‎ 2005, p. 299–327 (DOI 10.1145/1064340.1064341).
• [Abliz et Znati 2009] (en) Mehmud Abliz et Taieb Znati, « A Guided Tour Puzzle for Denial of Service Prevention », Annual Computer Security Applications Conference (ACSAC),‎ 2009, p. 279–288.
• [Coelho 2005] (en) Fabien Coelho, « Exponential memory-bound functions for proof of work protocols », Cryptology ePrint Archive, Report,‎ 2005 (lire en ligne).
• [Coelho 2007] (en) Fabien Coelho, « An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees », Africacrypt, Springer-Verlag,‎ juin 2008, p. 80–93.
• [Dwork, Goldberg et Naor 2003] (en) Cynthia Dwork, Andrew Goldberg et Moni Naor, « On memory-bound functions for fighting spam », Crypto, Springer-Verlag, n^o 2729,‎ 2003, p. 426–444.
• [Franklin et Malkhi 1997] (en) Matthew K. Franklin et Dahlia Malkhi, « Auditable metering with lightweight security », Financial Cryptography, Springer-Verlag,‎ 1997, p. 151–160 (DOI 10.1007/3-540-63594-7_75).
• [Gabber et al. 1998] (en) Eran Gabber, Markus Jakobsson, Yossi Matias et Alain J. Mayer, « Curbing junk e-mail via secure classification », Financial Cryptography, Springer-Verlag,‎ 1998, p. 198–213.
• [Jakobsson et Juels 1999] (en) Markus Jakobsson et Ari Juels, « Proofs of Work and Bread Pudding Protocols », Communications and Multimedia Security,‎ 1999, p. 258–272.
• [Juels et Brainard 1999] (en) Ari Juels et John Brainard, « Client puzzles: A cryptographic defense against connection depletion attacks », NDSS,‎ 1999.
• [Tromp 2015] (en) John Tromp, « Cuckoo Cycle; a memory bound graph-theoretic proof-of-work », Financial Cryptography and Data Security : BITCOIN 2015,‎ 2015, p. 49–62.

Articles connexes

• Preuve d'enjeu (Proof-of-stake)
• Crypto-monnaie
• Ethereum crypto-monnaie basée sur une blockchain dont les blocs sont validés par preuve de travail
• IOTA (cryptomonnaie et technologie) crypto-monnaie basée sur un graphe orienté acyclique dont les transsactions sont validées par preuve de travail.

Liens externes

• [Delahave 2014] Jean-Paul Delahaye, « Neutraliser les ordinateurs malveillants… en les faisant travailler. », sur Pour la science, avril 2014
• Qwantic.io - Calcul de la complexité de la PoW suivant la puissance du réseau, octobre 2021