Rigorous and Generalized Proof of Security of Bitcoin Protocol with Bounded Network Delay

1. Problématique et Contexte

L'article s'attaque à la preuve formelle de la sécurité du protocole Bitcoin dans un modèle de réseau à délai borné ($\Delta$-bounded delay). Bien que la sécurité de Bitcoin ait été étudiée dans des travaux antérieurs (notamment [7] et [8]), l'analyse présente des lacunes critiques :

• Erreur dans les modèles précédents : L'article [7] supposait à tort que la différence entre la longueur de la chaîne de l'adversaire et celle des nœuds honnêtes suivait une marche aléatoire (random walk). Les auteurs de ce papier démontrent par un contre-exemple (Annexe A) que cette hypothèse est fausse car les arrivées de blocs ne sont pas indépendantes de la manière supposée.
• Complexité et manque de généralité : La preuve alternative [8] est jugée trop longue et non intuitive. De plus, les modèles existants ne prenaient pas en compte des variantes avancées comme le « Merged Bitcoin » (fusion de chaînes) où les blocs peuvent avoir des scores différents.
• Objectif : Fournir une preuve rigoureuse, simplifiée et généralisée, valable même lorsque les blocs ont des scores variables et que le réseau subit des délais de transmission jusqu'à $\Delta$.

2. Modèle et Définitions

Les auteurs proposent un modèle mathématique étendu :

• Modèle de réseau : Un modèle à délai borné où l'adversaire peut retarder la transmission des blocs honnêtes jusqu'à un temps $\Delta$. Une fois un bloc transmis à un seul mineur honnête, il ne peut être retardé de plus de $\Delta$ pour les autres.
• Généralisation des scores : Contrairement au Bitcoin standard (où chaque bloc vaut 1), ce modèle autorise des blocs de différents types avec des scores ($c_i$) variables. La règle de sélection de la fourche (fork-choice rule) privilégie la chaîne ayant le score total le plus élevé.
• Taux de croissance :
  • $\lambda_h$ : Taux de croissance du score des blocs honnêtes en cas de délai maximal (fully-delayed).
  • $\lambda_a$ : Taux de croissance du score des blocs de l'adversaire.
• Condition de sécurité : La sécurité est prouvée lorsque $\lambda_a < \lambda_h$.

3. Méthodologie et Approche

L'approche se distingue par trois innovations majeures par rapport aux travaux antérieurs :

A. Introduction des « Intervals de Nakamoto »

Au lieu de se concentrer sur la probabilité qu'un bloc spécifique reste dans la chaîne, les auteurs définissent un intervalle de Nakamoto. Un intervalle de longueur $2q$ est dit « Nakamoto » s'il contient un bloc honnête (appelé bloc de Nakamoto) qui satisfait trois conditions :

1. Loner (Isolé) : Aucun autre bloc honnête n'est miné dans un intervalle temporel proche ($\Delta$ avant et après).
2. Domination passée ($E_1$) : La croissance du score de la chaîne honnête (avec délai) domine celle de l'adversaire pour tous les blocs honnêtes antérieurs.
3. Domination future ($E_2$) : La croissance du score de la chaîne honnête continue de dominer celle de l'adversaire pour tout le futur.

B. Correction de l'erreur de la marche aléatoire

Pour prouver que les événements $E_1$ et $E_2$ se produisent avec une probabilité non nulle, les auteurs rejettent l'approche par marche aléatoire directe. Ils introduisent un processus d'arrivée « percé » (punctured arrival process) :

• Ils simulent un processus où les arrivées de blocs honnêtes sont périodiquement supprimées (sur des intervalles de longueur $\Delta$) pour créer des « gaps » ($\Delta$-gaps).
• Cela permet de découper le processus en segments indépendants et identiquement distribués (i.i.d.), transformant ainsi le problème en une véritable marche aléatoire dont on peut analyser la dérive (drift).
• Ils démontrent que si $\lambda_h > \lambda_a$, il existe une probabilité positive que la croissance du score honnête reste supérieure à celle de l'adversaire sur ces segments percés.

C. Argument de « Bootstrap » (Induction)

La preuve ne se contente pas de montrer qu'un bloc honnête a une chance de survivre. Elle utilise un argument d'induction pour prouver qu'il y a une infinité de tels blocs :

• Ils divisent le temps en segments et montrent que la probabilité qu'un intervalle ne contienne aucun bloc honnête sécurisé décroît exponentiellement avec la longueur de l'intervalle.
• En utilisant le Lemme de Borel-Cantelli, ils concluent que la probabilité qu'il y ait une infinité d'intervalles sans blocs honnêtes est nulle.

4. Résultats Clés

1. Théorème de Sécurité (Théorème 42 & Corollaire 43) :
   Si le taux de croissance du score honnête (avec délai maximal) dépasse celui de l'adversaire ($\lambda_h > \lambda_a$), alors avec une probabilité de 1, la chaîne canonique contiendra une infinité de blocs honnêtes. Cela garantit la sécurité du protocole contre toutes les attaques connues (double dépense privée, selfish mining, etc.).

2. Régime d'In sécurité (Théorème 44) :
   Si $\lambda_a > \lambda_h$, le protocole est insecure. L'adversaire peut exécuter une attaque de minage privé : il mine une chaîne en secret et la révèle dès qu'elle a un score supérieur à la chaîne publique. Grâce à la loi des grands nombres, l'adversaire finira inévitablement par dominer la chaîne avec une probabilité de 100 %.

3. Correction de la littérature :
   L'article réfute formellement l'hypothèse de marche aléatoire utilisée dans [7] et propose une méthode correcte via le processus percé, rendant la preuve rigoureuse.

5. Signification et Impact

• Rigueur Mathématique : Ce papier comble une lacune importante dans la théorie de la sécurité de Bitcoin en corrigeant une erreur fondamentale dans les preuves précédentes concernant la nature stochastique des écarts de longueur de chaîne.
• Généralisation : En permettant des scores de blocs variables, la preuve ouvre la voie à l'analyse de protocoles dérivés comme le Merged Bitcoin (introduit dans un article compagnon), rendant la théorie applicable à des architectures de blockchain plus complexes.
• Robustesse du Modèle : La preuve tient compte des délais réseau réalistes ($\Delta$), confirmant que la sécurité de Bitcoin repose sur le fait que la puissance de minage honnête (ajustée pour les délais) doit dépasser celle de l'adversaire.
• Simplicité Relative : Malgré la complexité du sujet, les auteurs parviennent à simplifier certaines parties de la preuve (notamment via l'argument de bootstrap) par rapport aux travaux antérieurs, rendant l'analyse plus accessible et vérifiable.

En résumé, cet article établit une fondation mathématique solide et généralisée pour la sécurité de Bitcoin, prouvant que tant que les mineurs honnêtes maintiennent un taux de croissance de score supérieur à celui de l'adversaire (même avec des délais de réseau), l'intégrité de la chaîne est garantie avec une probabilité absolue.