Le problème de la double dépense et les généraux byzantins

Curiosité

1. Si un fichier numérique peut être copié parfaitement et instantanément, qu’est-ce qui l’empêche d’être utilisé deux fois ?
2. Comment un groupe d’inconnus sans identité commune peut-il s’accorder sur un historique unique, sans chef pour trancher les différends ?
3. Qu’est-ce qui rend un vote dans un réseau ouvert plus précieux que les paroles d’une autre personne ?

Explorer

1. Un jeton numérique n’est qu’un fichier. Contrairement à l’argent liquide, il peut être dupliqué bit pour bit, sans coût ni dégradation. Si Alice envoie dix unités à Bob, elle conserve le fichier original et peut envoyer en même temps ces mêmes dix unités à Charlie. Jusqu’en 2008, tous les systèmes de monnaie numérique fonctionnels dépendaient d’un émetteur de confiance : les systèmes en ligne vérifiaient chaque paiement de manière centralisée, et les systèmes hors ligne ne pouvaient identifier les auteurs de doubles dépenses qu’après coup.
2. Avec le DigiCash de David Chaum, chaque bénéficiaire déposait les pièces à la banque, qui vérifiait chaque numéro de série par rapport à sa liste de pièces déjà dépensées. Les Reusable Proofs of Work de Hal Finney reposaient sur un serveur unique exécutant du code open source sur du matériel sécurisé pour suivre les jetons dépensés. Le b-money de Wei Dai prévoyait des serveurs qui déposaient des cautions et pouvaient être sanctionnés par des amendes en cas de triche, mais il n’a jamais été construit. Chaque conception gardait en son centre une partie de confiance, ou un groupe connu.
3. En 1982, Leslie Lamport, Robert Shostak et Marshall Pease ont formalisé le problème des généraux byzantins dans les ACM Transactions on Programming Languages and Systems. Les généraux qui entourent une ville doivent s’accorder pour attaquer ou se retirer, mais certains généraux sont des traîtres qui envoient des messages contradictoires ; les messagers eux-mêmes sont fiables. Avec des messages non signés, un accord n’est possible que si moins d’un tiers des généraux sont des traîtres (n ≥ 3f+1) ; s’il y a un tiers ou plus de traîtres, aucun protocole ne peut le garantir.
4. Les protocoles classiques de tolérance aux pannes comme PBFT exigent un ensemble de participants connu et fixe. Cela fonctionne pour les registres internes des banques, mais échoue dans les réseaux ouverts où n’importe qui peut entrer. John Douceur a identifié l’attaque Sybil en 2002 : un adversaire peut générer un nombre illimité de fausses identités pour diluer les votes honnêtes ou contrôler les quorums. Dans un réseau pair-à-pair ouvert, l’identité est bon marché et infinie, si bien que tout mécanisme qui compte les identités peut être pris en main par un seul acteur.
5. Le livre blanc de Satoshi Nakamoto s’attaquait directement à ce problème. Son résumé présente bitcoin comme une solution à la double dépense sans tiers de confiance. Au lieu de s’appuyer sur l’identité ou sur la confiance institutionnelle, le système lie chaque bloc à une preuve de travail cumulée. Les votes sont pondérés par le calcul, qu’on ne peut pas multiplier en inventant des identités ; pour réécrire l’historique, un attaquant doit disposer de plus de puissance de calcul que le réseau honnête.
6. Il en résulte une finalité probabiliste. Une transaction n’est jamais définitive au sens mathématique, mais devient de plus en plus sûre à mesure que chaque nouveau bloc prolonge la chaîne. Tant qu’un attaquant contrôle moins de la moitié de la puissance de hachage, la probabilité d’annulation diminue exponentiellement à chaque confirmation. Ce compromis accepte la possibilité théorique d’une annulation pour obtenir une immuabilité pratique sans contrôle central. Ouvrez un explorateur de blocs et observez comment le travail cumulé augmente avec la hauteur des blocs ; c’est ce coût accumulé qui ancre le registre dans la réalité physique.

Faits clés

Exercice neuf, six, trois, un

Vérification des faits

Les dates, les chiffres et les affirmations ont été vérifiés à l’aide des sources publiées listées ci-dessous.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)