Problème des généraux byzantins
Cet article est une traduction du mail de Satoshi Nakamoto [1]dans lequel il explique sa solution au problème des généraux byzantins en utilisant la narrative utilisée par Lamport, Shostak et Pease en 1982 [2].
La chaine de preuve de travail est une solution au problème des généraux byzantins. Je vais essayer de reformuler ma solution dans ce contexte.
Un certain nombre de généraux byzantins possèdent chacun un ordinateur et souhaitent attaquer le wifi du roi en utilisant une attaque par brute force. Ils savent déjà que le mot de passe possède un certain nombre de caractères. Une fois les premiers paquets lancés sur le réseau, ils doivent trouver le mot de passe en un temps limité et effacer l’historique sinon ils seront découvert et auront des problèmes. Ils n’ont suffisamment de puissance de calcul pour trouver le mot de passe dans le temps impartie que si une majorité des généraux attaquent simultanément.
Ils accordent peu d’importance à quand l’attaque aura lieu, ils veulent juste être tous d’accord sur la même heure. Il a été décidé que n’importe qui peut annoncer l’heure, et que la première heure entendue serait l’heure à laquelle l’attaque doit être lancée. Le problème est que le réseau n’est pas instantané et si deux généraux annoncent différentes heures d’attaques presque simultanément, certains peuvent entendre l’un en premier et les autres celle du deuxième générale en premier.
Pour résoudre ce problème, ils utilisent une chaîne de preuve de travail. Lorsque chacun des généraux entend un message en premier, ils demandent à leur ordinateur de résoudre un problème de preuve de travail extrêmement difficile qui inclut l’heure d’attaque dans le hash. Cette preuve de travail est tellement difficile qu’il faut en moyenne 10 min pour que l’un d’entre eux trouve une solution. Une fois que l’un des généraux trouve une preuve de travail, il le communique aux autres et tout le monde met à jour sa configuration pour inclure cette nouvelle preuve de travail dans le hash sur lequel il travaille. Si quelqu’un était en train de travailler sur une heure d’attaque différente, il doit la changer pour celle qu’il vient de recevoir parce que cette chaîne de preuve de travail est maintenant la plus longue.
Après deux heures, une heure d’attaque devrait être hashé par une chaîne de 12 preuves de travail. Tous les généraux, juste en vérifiant la difficulté de la chaîne de la preuve de travail, peuvent estimer combien de puissance de calcul parallèle par heure a été dépensé dessus et peuvent constater que cela a dû nécessiter la majorité des ordinateurs afin de créer une aussi longue chaîne dans le temps impartie. Ils doivent tous l’avoir vu puisque la preuve de travail est la preuve qu’ils ont travaillé dessus. Si la puissance de calcul mis en évidence par la preuve de travail est suffisant pour cracker le mot de passe, ils peuvent attaquer à l’heure donnée.
La chaîne de preuve de travail est la solution aux problèmes de synchronisation, de distribution de base de donnée et aux problèmes de vue général que tu* as mentionné.
*Il s’adresse à James A. Donald dans son mail.
Une chose importante à noter c’est qu’on accorde peu d’importance à l’heure de l’attaque ou même si un espion annonce une mauvaise heure. Ici, on s’intéresse surtout à savoir si tout le monde est sur la même longueur d’onde. Il est important que l’attaque soit synchrone. Certaines compagnies l’utilisent comme registre anti-fraude pour assurer la traçabilité de produits mais il n’y a aucune façon de vérifier la validité de la donnée. La solution élaborée par Satoshi Nakamoto ne permet pas d’assurer que la donnée soit juste !
J’insisterais aussi sur l’approche qu’a pris Nakamoto pour son consensus est une approche probabiliste et non déterministe. C’est ici que se trouve la nouveauté de la solution. Il vient par contre avec le désavantage de consommer une certaine quantité d’énergie mais aussi un délai entre chaque bloc. Cela fonctionne pour Bitcoin (et encore… ) mais pas forcément pour d’autres applications.
Merci à Xavier Charpentier pour sa contribution.
