Preuve de travail

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un système de validation par preuve de travail (en anglais proof-of-work ou PoW) (ou protocole, ou la fonction) est difficile à produire car il est coûteux en temps et en énergie. C'est une mesure économique et sécuritaire pour dissuader, sur un réseau informatique, des attaques par déni de service et autres abus de service tels que le spam en requérant de la puissance de calcul et de traitement par ordinateur au demandeur de service. Le concept a d'abord été présenté par Cynthia Dwork et Moni Naor dans un article de 1993[1]. Le terme « preuve de travail » ou PoW a été formalisé dans un document de 1999 par Markus Jakobsson et Ari Juels[2].

Une caractéristique de ce système est l'asymétrie du calcul : le travail doit être difficile mais réalisable pour le demandeur, mais facile à vérifier pour un tiers. Cette idée est également définie comme une fonction de coût pour processeur, un protocole de réflexion client (en), un puzzle de calcul ou une fonction de tarification du processeur. Il se distingue d'un CAPTCHA, qui est destiné à un être humain pour résoudre rapidement un problème, au lieu d'un ordinateur.

Contexte[modifier | modifier le code]

Une des premières mise en œuvre de la preuve de travail était le système Hashcash qui cherchait à prévenir le pourriel. Dans ce système, le contenu de chaque email individuel est chiffré, y compris l'adresse du destinataire et la date d'envoi, selon un algorithme qui requiert un certain temps de traitement par l'ordinateur. Il est donc facile d'envoyer un courriel nominativement mais le publipostage (et donc potentiellement le pourriel) requiert une telle quantité de calcul à l'ordinateur qui envoie le message que la mise en œuvre est impossible. Inversement, le destinataire de l'email peut très facilement déchiffrer son contenu.

Exemple[modifier | modifier le code]

Il est demandé à un processeur de réaliser une preuve de travail pour dire "Bonjour, monde!" en utilisant le protocole de cryptage SHA-256 jusqu'à trouver une séquence chiffrée qui commence par 4 zéros. Le processeur devra réalisera en moyenne 4251 tentatives pour générer une séquence chiffrée du protocole SHA-256 codant "Bonjour, monde!".

  • "Bonjour, monde! 0" ⇒ 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
  • "Bonjour, monde! 1" ⇒ e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
  • "Bonjour, monde! 2" ⇒ ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
  • ...
  • ...
  • "Bonjour, monde! 4248" ⇒ 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
  • "Bonjour, monde! 4249" ⇒ c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
  • "Bonjour, monde! 4250" ⇒ 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

4 251 hashs 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 dans le cas de certaines crypto-monnaies comme le Bitcoin[3]

Le décryptage de la séquence chiffrée par le protocole est en revanche très rapide.

Variants[modifier | modifier le code]

Il existe deux protocoles de preuve de travail différents

Protocoles de défi-réponse[modifier | modifier le code]

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 accorde un privilège au demandeur. Dans ce système, la difficulté est adaptée à la charge de travail que reçoit le fournisseur.

Protocole de défi-réponse

Protocoles de vérification de solution[modifier | modifier le code]

Les protocoles de vérification de solution ne supposent pas de lien étroit avec un fournisseur. Dans ce système, le problème est établi par le protocole et lorsque la solution est trouvée, celle-ci est soumise au fournisseur qui peut facilement la vérifier. La plupart de ces protocoles sont des procédures itératives probabilistes non bornées telles que le protocole Hashcash.

Protocole de vérification de solution

Liste d'algorithmes[modifier | modifier le code]

Les systèmes de preuve de travail les plus largement utilisé sont ceux des crypto-monnaies comme par exemple 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 :

Utilisations dans les crypto-monnaies[modifier | modifier le code]

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 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.

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 voir impossible.

Références[modifier | modifier le code]

  1. (en) « Pricing via Processing or Combatting Junk Mail », sur www.wisdom.weizmann.ac.il,‎ (consulté le 23 mars 2016)
  2. « RSA Laboratories - Proofs of Work and Bread Pudding Protocols », sur www.emc.com (consulté le 23 mars 2016)
  3. « Bitcoin Difficulty and Hashrate Chart - BitcoinWisdom », sur bitcoinwisdom.com (consulté le 23 mars 2016)
  4. (en) « Introduction to Hashcash », sur hashcash.org
  5. (en) Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J., « Curbing junk e-mail via secure classification », Financial Cryptography,‎ , p. 198–213
  6. (en) Jakobsson, Markus; Juels, Ari, « Proofs of Work and Bread Pudding Protocols », Communications and Multimedia Security,‎ , p. 258–272
  7. (en) Franklin, Matthew K.; Malkhi, Dahlia, « Auditable metering with lightweight security », Financial Cryptography,‎
  8. (en) Juels, Ari; Brainard, John, « Client puzzles: A cryptographic defense against connection depletion attacks », NDSS,‎
  9. (en) Abadi, Martín; Burrows, Mike; Manasse, Mark; Wobber, Ted, « Moderately hard, memory-bound functions », ACM Trans. Inter. Tech, no 5 (2),‎ , p. 299–327
  10. (en) Dwork, Cynthia; Goldberg, Andrew; Naor, Moni, « On memory-bound functions for fighting spam », Advances in Cryptology, no 2729,‎ , p. 426–444
  11. (en) Coelho, Fabien, « Exponential memory-bound functions for proof of work protocols », Cryptology ePrint Archive, Report,‎ (lire en ligne)
  12. (en) Coelho, Fabien, « An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees », Cryptology ePrint Archive, Report,‎
  13. (en) Tromp, John, « Cuckoo Cycle; a memory bound graph-theoretic proof-of-work », Financial Cryptography and Data Security: BITCOIN 2015,‎ , p. 49–62
  14. (en) Abliz, Mehmud; Znati, Taieb, « A Guided Tour Puzzle for Denial of Service Prevention », Proceedings of the Annual Computer Security Applications Conference (ACSAC),‎ , p. 279–288

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]