The Time to Consensus in a Blockchain: Insights into Bitcoin's "6 Blocks Rule''
Dey, Gopalan, Subramanian
We investigate the time to consensus in Nakamoto blockchains. Specifically, we consider two competing growth processes, labeled \emph{honest} and \emph{adversarial}, and determine the time after which the honest process permananetly exceeds the adversarial process. This is done via queueing techniques. The predominant difficulty is that the honest growth process is subject to \emph{random delays}. In a stylized Bitcoin model, we compute the Laplace transform for the time to consensus and verify it via simulation.
academic
Le Temps pour Atteindre le Consensus dans une Blockchain : Perspectives sur la « Règle des 6 Blocs » de Bitcoin
Cet article étudie le problème du temps de consensus dans la blockchain Nakamoto. Plus précisément, les auteurs considèrent deux processus de croissance concurrents (nœuds honnêtes et nœuds adversaires), en utilisant des techniques de théorie des files d'attente pour déterminer le moment où le processus honnête dépasse définitivement le processus adversaire. Le défi principal réside dans le fait que le processus de croissance honnête est soumis à des délais aléatoires. Dans un modèle Bitcoin simplifié, les auteurs calculent la transformée de Laplace du temps de consensus et la valident par simulation.
L'article aborde la question fondamentale suivante : Combien de temps faut-il à un système blockchain pour atteindre le consensus en présence de délais réseau et de nœuds adversaires ? Cette question est directement liée aux fondements théoriques de la célèbre « règle des 6 blocs » de Bitcoin.
Besoins des applications émergentes : Dans les applications blockchain émergentes, notamment dans la gestion des chaînes d'approvisionnement (en particulier pour les produits frais), l'arrivée des blocs est beaucoup plus rapide qu'à Bitcoin, rendant les délais réseau un facteur non trivial
Garanties de sécurité : Tout comme les cartes de crédit offrent une garantie de traitement des transactions en « 3 jours ouvrables », la blockchain doit fournir des garanties de temps de consensus vérifiables
Lacune théorique : Les calculs du livre blanc Bitcoin original contiennent des erreurs et ne tiennent pas compte de l'impact des délais réseau
Travaux de Guo et Ren : Bien qu'utilisant une configuration similaire, ces travaux se limitent aux délais bornés et simplifient le problème au cas de délai zéro, incapables de capturer l'étendue complète du fonctionnement de la blockchain
Analyses traditionnelles : La plupart des recherches se concentrent sur l'« avantage de tête » (basé sur l'état) plutôt que sur l'analyse du consensus basée sur le temps
Modélisation insuffisante des délais : Les travaux existants ne fournissent pas de caractérisation explicite des délais réseau, en particulier dans le cas de délais non bornés
Les auteurs réinterprètent le problème de sécurité de la blockchain du point de vue de l'adversaire : le temps de consensus est compris comme le temps nécessaire pour que l'attaque de l'adversaire échoue dans le pire cas. Cette approche basée sur le temps est mieux adaptée aux modèles non-markoviens.
Les principales contributions de cet article sont :
Modélisation complète pour la première fois : Proposition du premier modèle de temps de consensus blockchain qui considère explicitement à la fois les délais réseau et un adversaire dans le pire cas
Analyse précise de Bitcoin : Pour un modèle Bitcoin simplifié, obtention de la transformée de Laplace exacte de la distribution du temps de consensus et du taux de décroissance de la queue
Résultats théoriques généraux : Pour des modèles plus généraux (applicables aux applications émergentes comme les chaînes d'approvisionnement), caractérisation du dernier temps de passage par le nombre de cycles de files d'attente
Validation numérique : Vérification des résultats théoriques par simulation et estimation conservative de la « règle des 6 blocs »
Nouvelles techniques d'analyse : Transformation du problème en problème de dernier passage pour une marche aléatoire en Z, utilisant les propriétés des files d'attente M/M/1 stables et instables
où ωt ~ Ber(p) est indépendant et identiquement distribué.
Couplage avec la théorie des files d'attente :
Définition Qt := max(At - Ht, -1), par intégration de processus de Poisson, les incréments de Qt peuvent être couplés à une file d'attente M/M/1 :
Transformation du problème de consensus blockchain en problème de dernier passage pour un système de file d'attente avec « serveur non-arrêtable », ce qui est un modèle de file d'attente non-standard.
Estimation conservative : La « règle des 6 blocs » de Bitcoin en pratique exige que l'adversaire soit bien loin de sa valeur critique, ce qui est assez conservateur
Impact des délais : Les délais réseau affectent significativement le temps de consensus, mais l'impact est maîtrisable pour p élevé
Cohérence théorie-pratique : Les prédictions théoriques de la transformée de Laplace sont hautement cohérentes avec les résultats de simulation
Défi central : l'article obtient des résultats à l'échelle de temps des sous-échantillons de cycles de files d'attente, mais ne peut pas convertir explicitement à l'échelle de temps originale
Raisons :
Conditionné au temps de consensus passé, la structure des cycles de files d'attente n'est plus indépendante
Les grands X et grands Y sont positivement corrélés avec les longues périodes d'inactivité et les périodes occupées
Même au sens de l'espérance, on ne peut pas appliquer simplement l'identité de Wald
Fondations mathématiques solides : utilisation complète de la théorie des files d'attente, de la théorie des probabilités et des processus stochastiques
Preuves complètes : chaîne logique claire des hypothèses de base aux théorèmes principaux
Innovation technique : la transformation du problème blockchain en problème de files d'attente est une intuition ingénieuse
Orientation des paramètres : fourniture de justification quantitative pour le choix de la valeur p pour les opérateurs blockchain
Évaluation des risques : l'analyse des probabilités de queue aide à la gestion des risques
Conception d'applications émergentes : fourniture de fondations théoriques pour la conception blockchain des chaînes d'approvisionnement et autres applications émergentes
Cet article est une contribution théorique importante dans le domaine de l'analyse du temps de consensus blockchain. En transformant ingénieusement le problème en un cadre de théorie des files d'attente, les auteurs fournissent pour la première fois une caractérisation précise du temps de consensus de la blockchain Nakamoto sous délais réseau non-triviaux. Pour le modèle Bitcoin simplifié, des expressions explicites de la transformée de Laplace et de la décroissance exponentielle de la queue sont obtenues ; pour le modèle général, des bornes significatives sont fournies par analyse des cycles de files d'attente.
La valeur principale de l'article réside dans : (1) la fourniture de fondations théoriques pour la « règle des 6 blocs », révélant son caractère conservateur ; (2) l'introduction d'une perspective de théorie des files d'attente, ouvrant de nouvelles directions pour l'analyse blockchain ; (3) la prise en compte des délais réseau, plus proche des systèmes réels.
Cependant, l'article présente aussi des limitations évidentes : le problème critique non résolu est la conversion des cycles de files d'attente au temps réel, ce qui limite l'application directe des résultats. De plus, les simplifications du modèle (en particulier la distribution de délai et l'hypothèse d'un bloc unique) peuvent sous-estimer la complexité des systèmes réels.
Les trois directions de travaux futurs (analyse de trajectoires par grandes déviations, conversion d'échelle de temps, extension non-skip-free) possèdent toutes une signification théorique et pratique importante. En particulier, la résolution du problème de conversion d'échelle de temps augmenterait considérablement la valeur pratique des résultats de cet article.
Dans l'ensemble, c'est un article excellent techniquement rigoureux, théoriquement innovant et pratiquement pertinent, fournissant de nouveaux outils théoriques et des perspectives profondes pour l'analyse du consensus blockchain.