La preuve de travail (proof of work)

Le chaînage par hachage rend l'historique détectable en cas d'altération, mais n'empêche pas, à lui seul, un attaquant de recalculer toute la suite des blocs. Pour rendre ce recalcul économiquement infaisable, Bitcoin impose un coût à la création de chaque bloc : la preuve de travail (proof of work).

L'idée : rendre un bloc coûteux à produire

Ajouter un bloc ne doit pas être gratuit. Les participants qui proposent des blocs, les mineurs, doivent résoudre un problème calculatoire difficile mais dont la solution est facile à vérifier.

Le problème : trouver un nombre, le nonce (« number used once »), tel que l'empreinte de l'en-tête du bloc, une fois ce nonce inséré, soit inférieure à une cible — autrement dit qu'elle commence par un certain nombre de zéros.

en-tête = numéro + racine de Merkle + empreinte précédente + nonce

On cherche nonce tel que  H(en-tête) < CIBLE
   c.-à-d.  H(en-tête) commence par (disons) 4 zéros.

nonce = 0      -> H = 9f3a...    (trop grand, raté)
nonce = 1      -> H = c17b...    (raté)
nonce = 2      -> H = 4e88...    (raté)
   ... des milliards d'essais ...
nonce = 726431 -> H = 0000a3d1... (< CIBLE : trouvé !)

Facile à vérifier, difficile à produire

C'est l'asymétrie fondamentale, la même philosophie que la fonction à sens unique :

• Produire la solution : comme l'empreinte est imprévisible (effet d'avalanche), il n'existe aucune méthode plus maligne que d'essayer des milliards de nonces au hasard. Cela demande une énorme puissance de calcul, donc de l'énergie.
• Vérifier la solution : il suffit de calculer une seule empreinte et de constater qu'elle est bien sous la cible. Instantané.

N'importe qui peut donc contrôler en une milliseconde qu'un mineur a réellement fourni le travail — sans refaire ce travail.

La cible et la difficulté

Plus la cible est basse (plus on exige de zéros), plus il faut d'essais en moyenne. Le réseau ajuste automatiquement cette difficulté pour qu'un bloc soit trouvé à intervalle régulier (environ toutes les 10 minutes pour Bitcoin), quelle que soit la puissance totale connectée.

Pourquoi cela protège l'historique

Reprenons l'attaquant qui veut modifier un ancien bloc. Le hachage l'obligeait déjà à recalculer tous les blocs suivants. Avec la preuve de travail, chacun de ces recalculs exige de retrouver un nonce valide, c'est-à-dire de refaire tout le minage.

Falsifier le bloc N  =>  refaire la preuve de travail de N,
                         puis de N+1, N+2, ... jusqu'au sommet
   Pendant ce temps, le réseau honnête continue d'allonger
   la chaîne. L'attaquant doit donc miner PLUS VITE que
   tout le reste du réseau réuni. Économiquement infaisable.

C'est pourquoi on considère qu'un bloc est d'autant plus définitif que de nombreux blocs ont été empilés au-dessus : chacun ajoute une couche de travail à refaire.

En résumé

• La preuve de travail impose aux mineurs de trouver un nonce tel que l'empreinte du bloc soit inférieure à une cible (commence par des zéros).
• Trouver ce nonce demande des milliards d'essais (coûteux en énergie), mais le vérifier est instantané.
• La difficulté est ajustée pour maintenir un rythme de blocs régulier.
• Réécrire l'historique exigerait de refaire tout le travail de tous les blocs suivants, plus vite que le réseau entier : c'est économiquement infaisable.