Comment fonctionne la Proof Of Work et pourquoi s'en débarasser?

23 October 2017

Un peu partout, on parle de Proof Of Work et de Proof Of Stake. Et il est difficile de parler de plateformes comme Bitcoin ou Ethereum sans parler de “minage”.

Mais à quoi correspond exactement la Proof Of Work? Comment fonctionne-t-elle? Et plus encore: pourquoi certains projets essaient de s’en débarasser?

La nécessité des Proof Of

Dans l’architecture d’une plateforme de Consensus Distribué, on retrouve:

  • des structures de blockchain pour éviter la falsification des données
  • des protocoles peer-to-peer pour échanger ces données dans un réseau publique décentralisé
  • des algorithmes de Proof Of (Proof Of Work, Proof Of Stake) pour que chaque membre du réseau puisse proposer, choisir et diffuser les nouveaux états du système.

Sans Proof Of Work, le Bitcoin n’aurait pas vu le jour:

Les membres du réseau proposeraient de nouveaux blocks ad nauseum et le système tournerait en rond sans trouver de consensus sur UN nouveau block.

Twitch Plays Pokemon Twitch Plays Pokemon: Tous les participants peuvent proposer un mouvement pour le personnage. Les participants ont des objectifs contradictoires, le personnage tourne en rond.

La Proof Of Work permet à chaque membre du réseau de recevoir de nouveaux block et de choisir quoi en faire, soit:

  • le garder et le diffuser
  • l’ignorer

J’ai décrit précédemment la nécessité des Proof Of. Ici, on va creuser sur le fonctionnement d’UN de ces algorithmes: la Preuve de Travail / Proof Of Work.

Une solution pour choisir un nouveau block: Temporiser leur création

Une règle simple pour éviter d’inonder le système de blocks et pour sélectionner facilement les nouveaux blocks serait de ralentir la création de chaque nouveau block.

Mais le temps est une notion trop fragile dans un système distribué, plus encore dans un système public où les utilisateurs peuvent tricher.

Si on veut temporiser la production des blocks, on le fait par la force, c’est ce que fait la Proof Of Work.

Un Casse-Tête Mathématique pour enfants de 8 ans:

Je vous propose un jeu tout simple qui va nous permettre de comprendre la suite:

Je choisis un chiffre au hasard entre 1 et 10. Vous devez trouver ce chiffre.

— Hum, est-ce que c’est 4? Non. — 8? Non. — 7? Oui, Gagné!

Il vous faut quelques tentatives pour trouver ce chiffre. En moyenne, on a une chance sur dix de tomber sur le chiffre du premier coup. Puis une chance sur neuf, etc.

Vous pourriez tenter 1, 2, 3, 4, … Ou 9, 8, 7, 6, …. Il n’y a pas de stratégie idéale car je chois le chiffre au hasard. Vous n’avez pas d’information hormis Succès / Échec.

C’est un jeu dans lequel trouver la solution prend un peu de temps. Mais il est facile de la valider

Continuons: Un deuxième joueur vous rejoint. Vous vous mettez d’accord pour que l’un fasse les nombres pairs et l’autre les nombres impairs. Vous avez maintenant une chance sur cinq de trouver la solution du premier coup. Puis une chance sur quatre, etc. Vous allez deux fois plus vite.

De mon coté, je peux changer les contraintes du jeu:

Je vais choisir un chiffre entre 1 et 20.

Les probabilités sont de nouveau de 1/10 pour trouver le chiffre du premier coup.

On peut “redimensionner” notre problème à loisir pour l’adapter aux participants.

Par contre, il nous faut un maître du jeu qui connaisse la solution. C’est une entité centrale qui rend jeu inutilisable sur la Blockchain! Dans la suite, on va décentraliser le jeu: chaque participant va travailler sur sa propre instance.

PoW: Un Casse-Tête Mathématique Décentralisé

De retour dans un système de Blockchain. Les participants peuvent envoyer des paquets de données sous la forme de block. Un participant veut proposer un nouveau block:

ALICE SEND 1 BITCOIN TO BOB

Il calcule le hash de ce block. C’est une empreinte cryptographique unique:

SHA384("ALICE SEND...") = 3796601003deefd3662a8e...

Ce résultat est déterministe. Mais il se comporte comme de l’aléatoire: le seul moyen de savoir à quoi il ressemble c’est de le calculer. On ne peut pas exploiter de relations entre deux résultats.

On retrouve l’aléatoire de notre casse-tête précédent!

On va ajouter une contrainte sur cette empreinte:

Je veux qu’elle commence par 0

Mon exemple est en hexadécimal: on a une chance sur seize de tomber sur un hash qui commence par 0. Par exemple:

ALICE SEND 1 BITCOIN TO BOB
NONCE=39
SHA384('ALICE SEND...NONCE=39') = 01c2c2e0e499a841e623e...

Ce Nonce, c’est le champ “poubelle” qui va nous permettre de générer des empreintes différentes sans changer le sens de notre block.

Lorsque de nouveaux participants rejoignent le réseau et commencent à calculer des hash et proposer des blocks, on va augmenter la difficulté. On impose qu’il ressemble à 00 puis 000, etc. Changer la difficulté revient à changer le temps que le réseau met pour résoudre le problème. Comme dans le premier jeu.

Chaque membre du réseau calcule la difficulté localement. Mais pour qu’un block soit diffusé sur le réseau, il doit respecter les contraintes choisies par la majorité. Même pour les participants hostiles.

On retrouve toutes les propriétés de notre jeu initial, sous un format décentralisé.

Asymétrie

Rechercher le Nonce c’est “Miner”!

Chaque participant qui décide de miner va accepter des transactions, les accumuler dans un block puis calculer des Hashs. Le mineur génère un Nonce, calcule le hash de son block, génère un nouveau Nonce, calcule le nouveau hash,…

Parfois, il tombe sur une pépite: un hash qui respecte les contraintes du réseau. Il va transférer ce block au reste du réseau.

Trouver un Nonce nécessite de calculer de nombreux hash, des milliers, des millions ou plus. Mais vérifier un block ne demande qu’un seul calcul.

Cette asymétrie permet de temporiser la chaine malgré les participants hostiles: il suffit d’un calcul assez peu coûteux pour qu’un participant accepte de diffuser un block. Ou le rejette.

Gaspillage

On ralentit la proposition des blocks par la force: un nouveau block demande beaucoup d’énergie.

À chaque nouveau Mineur, la difficulté du réseau augmente un peu. On a donc des millions de machines en course pour calculer des hashs qui ne servent à rien: on n’en garde qu’un seul.

L’analogie du minage tient toujours: la Proof Of Work c’est la centrale à charbon de l’écosystème de Blockchain.

Cependant, ce n’est pas le point le plus critique envers la PoW: une infrastructure “classique” consomme et gaspille beaucoup d’énergie. Il faut sécuriser des bâtiments, écrire des logiciels de sécurité, etc.

Re-Centralisation

Finalement, on peut voir la limitation principale de cette méthode: Plus vous mettez d’énergie dans la blockchain plus vous avez de pouvoir sur le système.

Les membres sont encouragés à miner de nouveaux block. Mais on utilise la Puissance de calcul comme équivalent pour le droit de vote (proposer des blocks). Les membres qui investissent le plus dans le système ont le plus de potentiel pour en déjouer ses mécaniques.

Finalement

On a vu comment fonctionne la proof of work: c’est un jeu mathématique qui repose sur des fonctions pseudo-aléatoires. Elle peut temporiser tous les participants du réseau pour que chaque block fasse consensus avant le suivant.

Cependant, on voit aussi clairement que la Proof Of Work induit un gaspillage assez affolant d’énergie. Et pire: il re-centralize le “cerveau” du consensus vers les membres les plus massifs. Voilà la raison du développement d’alternatives comme la Proof Of Stake.


Laurent Senta

I wrote software for large distributed systems, web applications, and even robots. These days I focus on making developers, creators, and humans more productive through IPDX.co.