Mise à jour d'Ethereum : notions fondamentales sur le consensus (2/2)
TechFlow SélectionTechFlow Sélection
Mise à jour d'Ethereum : notions fondamentales sur le consensus (2/2)
Il s'agit d'un ouvrage technique d'autorité sur le protocole de preuve d'enjeu d'Ethereum. Il commence par quelques notions préliminaires, couvrant les bases du consensus, qui ne se limitent pas à Ethereum.
Dédié à des analyses Web3 approfondiesRédaction : Ben Edgington
Traduction : tiao
Cet article constitue la seconde moitié du chapitre « Fondamentaux sur le consensus ». Pour la première partie, voir « Mettre à niveau Ethereum : les fondamentaux du consensus ».
Règle de choix de fourchette (fork choice rule)
Comme nous l’avons vu, pour diverses raisons — latence réseau, interruptions, ordre erroné de réception des messages, comportement malveillant de pairs — les nœuds d’un réseau peuvent finir par avoir des visions différentes de l’état du réseau. À terme, nous souhaitons que chaque nœud correct du réseau parvienne à une vision linéaire et commune de l’historique, et donc à une vue partagée de l’état du système. C’est précisément ce que vise à atteindre la règle de choix de fourchette du protocole.
Lorsqu’elle est appliquée à un arbre de blocs, accompagnée de certains critères décisionnels basés sur la vision locale qu’un nœud a du réseau, la règle de choix de fourchette a pour but de sélectionner, parmi toutes les branches disponibles, celle qui a le plus de chances de devenir la chaîne canonique linéaire finale. Autrement dit, lorsqu’un nœud cherche à converger vers la vue canonique, il choisit la branche la moins susceptible d’être élaguée de l’arbre des blocs.
La règle de choix de fourchette sélectionne implicitement une branche en désignant un bloc situé à son extrémité (appelé bloc tête).
Pour tout nœud correct, le premier critère de toute règle de choix de fourchette est que le bloc choisi doit être valide : il doit respecter les règles du protocole, tout comme tous ses ancêtres. Tout bloc invalide est ignoré, et tout bloc construit par-dessus un bloc invalide devient lui-même invalide.
Étant donné cela, plusieurs exemples différents de règles de choix de fourchette existent.
-
Les protocoles de preuve de travail d’Ethereum et de Bitcoin utilisent la « règle de la chaîne la plus lourde » [4] (parfois appelée « chaîne la plus longue », bien que cela soit légèrement inexact). Le bloc tête est celui qui se trouve au sommet de la chaîne ayant accumulé le plus grand « travail » sous preuve de travail.
-
Dans le protocole Casper FFG de preuve d’enjeu d’Ethereum, la règle de choix de fourchette consiste à « suivre la chaîne contenant le point de contrôle le plus haut justifié », sans jamais revenir sur un bloc déjà finalisé.
-
Dans le protocole LMD GHOST de preuve d’enjeu d’Ethereum, la règle de choix de fourchette est indiquée dans son nom : elle adopte la « sous-arborescence observée la plus gourmande et la plus lourde ». Elle implique de calculer les votes cumulés des validateurs sur un bloc ainsi que sur ses descendants. Elle suit également les mêmes règles que Casper FFG.
Nous expliquerons en détail les deuxième et troisième exemples dans leurs chapitres respectifs.
Vous avez peut-être compris que ces règles de choix de fourchette sont toutes des méthodes permettant d’attribuer une note numérique à chaque bloc. Le bloc gagnant — le bloc tête — est celui qui obtient la note la plus élevée. L’idée sous-jacente est que, lorsque tous les nœuds corrects verront finalement un certain bloc, ils s’accorderont sans ambiguïté sur le fait qu’il s’agit du bloc tête, et choisiront de suivre sa branche, quelle que soit leur vision antérieure du réseau. Ainsi, tous les nœuds corrects finiront par converger vers une vue commune d’une unique chaîne canonique remontant au bloc génèse.
Réorganisations (Reorgs) et retours arrière (reversions)
Lorsqu’un nœud reçoit un nouveau bloc (ou, dans le cas de la preuve d’enjeu, de nouveaux votes sur un bloc), il réévalue la règle de choix de fourchette à la lumière de ces nouvelles informations. Dans le cas le plus courant, le nouveau bloc est un fils du bloc qu’il considérait précédemment comme tête, et devient alors le nouveau bloc tête.
Cependant, parfois, le nouveau bloc peut être un descendant d’un autre bloc dans l’arbre. (Notez que si le nœud ne possède pas encore le bloc parent du nouveau bloc, il doit interroger ses pairs pour l’obtenir, tout comme pour tout autre bloc manquant.)
Dans tous les cas, l’application de la règle de choix de fourchette sur l’arbre mis à jour peut aboutir à un bloc tête appartenant à une branche différente de la précédente. Lorsque cela se produit, le nœud doit effectuer une réorganisation (« reorg », abréviation de « reorganisation »), aussi appelée retour arrière (rollback). Il doit retirer (annuler) les blocs précédemment inclus dans sa chaîne et adopter les blocs situés sur la nouvelle branche du bloc tête.
Dans le schéma ci-dessous, le nœud évalue le bloc F comme étant le bloc tête, donc sa chaîne est composée des blocs A, B, D, E, F. Le nœud connaît le bloc C, mais il n’appartient pas à la vue de sa chaîne actuelle ; C se trouve sur une branche secondaire.
Un certain temps plus tard, le nœud reçoit le bloc G, qui n’est pas construit sur son bloc tête courant F, mais sur la branche du bloc C. Selon les détails de la règle de choix de fourchette, le nœud pourrait continuer à juger F meilleur que G, et ignorer G. Mais dans le scénario présent, supposons que la règle de choix de fourchette indique que G est désormais le meilleur bloc tête.
Les blocs D, E et F ne sont pas des ancêtres de G, ils doivent donc être retirés de la chaîne canonique du nœud. Toutes les transactions ou informations qu’ils contiennent sont annulées, comme s’ils n’avaient jamais été reçus. Le nœud doit revenir complètement à l’état qu’il avait après le traitement du bloc B.
Après ce retour arrière jusqu’au bloc B, le nœud peut ajouter les blocs C et G à sa chaîne et les traiter. Une fois cette opération terminée, la réorganisation de sa chaîne est achevée.
Plus tard, un bloc H pourrait apparaître, construit sur le bloc F. Si la règle de choix de fourchette indique que le nouveau bloc tête doit être H, le nœud effectuera à nouveau une réorganisation, reviendra au bloc B, puis reconstruira les blocs sur la branche H.
Dans les protocoles de preuve de travail et de preuve d’enjeu d’Ethereum, des réorganisations courtes d’un ou deux blocs ne sont pas rares, dues aux délais de propagation des blocs sur le réseau. Sauf attaque contre la chaîne, erreur dans la conception de la règle de choix de fourchette ou bug dans son implémentation cliente, des réorganisations très longues devraient être extrêmement rares.
Sécurité et vivacité
Lorsqu’on discute des mécanismes de consensus, deux concepts importants reviennent fréquemment : la sécurité (safety) et la vivacité (liveness).
Sécurité
De façon informelle, un algorithme est considéré sûr si « rien de mauvais ne se produit » [5].
Des événements néfastes pouvant survenir dans un contexte blockchain incluent le double dépense (double-spend) de cryptomonnaie, ou la finalisation de deux points de contrôle conflictuels.
Un aspect clé de la sécurité dans les systèmes distribués est la « cohérence ». Cela signifie que si nous interrogeons différents nœuds (honnêtes) sur l’état du système à un certain stade — par exemple, le solde d’un compte à une hauteur de bloc donnée — nous devrions toujours obtenir la même réponse, quel que soit le nœud interrogé. Dans un système sécurisé, chaque nœud partage une vision identique et immuable de l’historique de la chaîne.
En pratique, la sécurité signifie que notre système distribué « se comporte comme une instance centralisée, exécutant une opération atomique à la fois » (selon Castro et Liskov). Dans la classification centralisée de Vitalik, un système sécurisé est logiquement centralisé.
Vivacité
De façon informelle, un algorithme possède la vivacité si « quelque chose de bon finit par arriver ».
Dans le contexte blockchain, cela signifie généralement que la chaîne peut toujours ajouter un nouveau bloc ; elle ne reste jamais bloquée, incapable de produire de nouveaux blocs contenant des transactions.
La « disponibilité (availability) » est une autre manière de voir cela. Je souhaite que la chaîne soit disponible, c’est-à-dire que si j’envoie une transaction valide à un nœud honnête, elle sera finalement incluse dans un bloc étendant la chaîne.
Les deux ensemble sont impossibles !
Le théorème CAP est un résultat célèbre de la théorie des systèmes distribués, affirmant qu’aucun système distribué ne peut simultanément offrir (1) la cohérence (consistency), (2) la disponibilité (availability) et (3) la tolérance aux partitions (partition tolerance). La tolérance aux partitions désigne la capacité du système à fonctionner même lorsque les communications entre nœuds sont fiables. Par exemple, une panne réseau peut séparer les nœuds en deux groupes ou plus incapables de communiquer entre eux.
Il est facile d’illustrer le théorème CAP dans le contexte blockchain. Supposons que les services Amazon Web Services (AWS) tombent en panne, de sorte que tous les nœuds hébergés sur AWS puissent communiquer entre eux, mais aucun ne puisse communiquer avec l’extérieur ; ou qu’un pays bloque toutes les connexions entrantes et sortantes, empêchant tout trafic gossip de passer. Ces deux situations divisent les nœuds en deux groupes disjoints, notés A et B.
Supposons qu’un compte connecté au groupe A envoie une transaction. Si les nœuds du groupe A traitent cette transaction, leur état final différera de celui des nœuds du groupe B, qui n’ont pas vu la transaction. En conséquence, nous perdons la cohérence entre tous les nœuds, donc la sécurité. La seule façon d’éviter cela serait que les nœuds du groupe A refusent de traiter la transaction, auquel cas nous perdons la disponibilité, donc la vivacité.
En résumé, le théorème CAP implique que nous ne pouvons pas espérer concevoir un protocole de consensus à la fois sûr et vivant dans toutes les circonstances, car nous sommes contraints de fonctionner sur un réseau non fiable : Internet [6].
Ethereum privilégie la vivacité
Lorsque le réseau fonctionne bien, le protocole de consensus d’Ethereum assure à la fois sécurité et vivacité. Mais en cas de perturbations réseau, il privilégie la vivacité. En cas de partition, les nœuds des deux côtés continueront à produire des blocs. Toutefois, la finalité (finality, propriété liée à la sécurité) ne se produira plus simultanément des deux côtés. Selon la proportion de mise en jeu gérée de chaque côté, soit un seul côté poursuit la finalité, soit aucun des deux côtés ne la poursuit.
Finalement, à moins que la partition ne soit résolue, les deux côtés retrouveront la finalité grâce au mécanisme novateur de pénalité d’inactivité (inactivity leak). Mais cela entraînera aussi une faille de sécurité : chaque chaîne finalisera un historique différent, et les deux chaînes deviendront irrémédiablement indépendantes et inconciliables.
Finalité (Finality)
Nous aborderons largement la notion de finalité dans les prochains chapitres, car il s’agit d’une propriété essentielle de la sécurité de la chaîne.
La finalité signifie que certains blocs ne seront jamais annulés. Lorsqu’un bloc est finalisé, tous les nœuds honnêtes du réseau conviennent qu’il restera à jamais dans l’historique de la chaîne, tout comme tous ses ancêtres. La finalité rend votre paiement pour une pizza irrévocable, comme avec de l’argent liquide. C’est la protection ultime contre le double dépense [7].
Certains protocoles de consensus, comme PBFT classique ou Tendermint, finalisent chaque tour (chaque bloc). Dès qu’un ensemble de transactions est inclus dans la chaîne, tous les nœuds conviennent qu’il y restera à jamais. D’un côté, ces protocoles sont très « sûrs » : une fois qu’une transaction est incluse, elle ne sera jamais annulée. De l’autre, ils sont sensibles aux pannes de vivacité : si les nœuds ne parviennent pas à s’entendre — par exemple, si plus d’un tiers des nœuds sont hors ligne — aucune transaction ne peut être ajoutée, et la chaîne s’arrête.
D’autres protocoles, comme le consensus de Nakamoto utilisé par Bitcoin, n’ont absolument aucun mécanisme de finalité. Il existe toujours une possibilité qu’une chaîne alternative plus lourde apparaisse. Dans ce cas, tous les nœuds honnêtes doivent réorganiser leur chaîne en conséquence, annulant toutes les transactions précédemment traitées. Des heuristiques comme « combien de confirmations a mon bloc ? » ne sont que des approximations de la finalité, sans garantie [8].
La couche de consensus d’Ethereum privilégie la vivacité, mais s’efforce aussi de fournir des garanties de sécurité via la finalité lorsque les conditions le permettent. C’est une tentative d’avoir le meilleur des deux mondes. Comme le défend Vitalik [9] :
Le principe général est de vouloir offrir aux utilisateurs « autant de consensus que possible » : si les nœuds parvenant à un accord représentent > 2/3, alors nous avons un consensus normal. Mais si < 2/3, inutile de tout arrêter : même si la sécurité des nouveaux blocs est temporairement réduite, la chaîne peut continuer à croître. Si une application individuelle n’est pas satisfaite du niveau de sécurité réduit, elle est libre d’ignorer ces blocs jusqu’à leur finalisation.
Sur la couche de consensus d’Ethereum, la finalité est assurée par le mécanisme Casper FFG, que nous examinerons bientôt. Son principe est que tous les validateurs honnêtes s’accordent régulièrement sur les blocs-points de contrôle récents, et ne reviendront jamais dessus. Ces blocs, ainsi que tous leurs ancêtres, sont alors « finalisés » — ils ne changeront jamais, et si vous interrogez n’importe quel nœud honnête du réseau à leur sujet, vous obtiendrez toujours la même réponse.
La finalité d’Ethereum est une « finalité économique ». Théoriquement, le protocole pourrait finaliser deux points de contrôle conflictuels, c’est-à-dire deux visions contradictoires de l’historique de la chaîne. Mais cela ne pourrait se produire qu’au prix d’un coût énorme et quantifiable. Hormis les attaques ou pannes extrêmes, « finalisé » veut dire « finalisé ».
La section sur Casper FFG approfondit le fonctionnement de ce mécanisme de finalité.
Voir aussi
Tout ce à quoi Leslie Lamport participe vaut toujours la peine d’être lu. Son article fondateur de 1982, coécrit avec Shostak et Pease, « The Byzantine Generals Problem », contient de nombreuses idées profondes. Bien que l’algorithme proposé soit aujourd’hui inefficace, cet article constitue une excellente introduction au raisonnement sur les protocoles de consensus en général. Il en va de même pour l’article fondateur de Castro et Liskov en 1999, « Practical Byzantine Fault Tolerance », qui a fortement influencé la conception du protocole Casper FFG d’Ethereum. Toutefois, vous pouvez souhaiter comparer ces méthodes « classiques » à l’élégante simplicité de la preuve de travail décrite par Nakamoto dans le livre blanc de Bitcoin en 2008. Si la preuve de travail a un avantage, c’est bien sa simplicité.
Nous avons mentionné plus haut l’article de Gilbert et Lynch en 2012, « Perspectives on the CAP Theorem ». Cet article explore en profondeur les notions de cohérence et de disponibilité (ou, dans notre contexte, de sécurité et de vivacité), et est très accessible.
En mai 2022, la Beacon Chain d’Ethereum a subi une réorganisation de sept blocs, due à des différences entre les implémentations clientes de la règle de choix de fourchette. Ces divergences étaient connues à l’époque et considérées comme inoffensives. Ce n’était manifestement pas le cas. La description de cet incident par Barnabé Monnot est particulièrement instructive.
L’article de blog de Vitalik, « On Settlement Finality », propose une exploration plus approfondie et nuancée du concept de finalité.
Pour les systèmes que nous construisons, notre idéal est qu’ils soient politiquement décentralisés (pour être permis et résistants à la censure), architecturalement décentralisés (pour être résilients sans point de défaillance unique), mais logiquement centralisés (pour garantir des résultats cohérents). Ces critères influencent fortement la conception de nos protocoles de consensus. Vitalik explore ces questions dans son article « The Meaning of Decentralization ».
Bienvenue dans la communauté officielle TechFlow
Groupe Telegram :https://t.me/TechFlowDaily
Compte Twitter officiel :https://x.com/TechFlowPost
Compte Twitter anglais :https://x.com/BlockFlow_News
@LXDAO_Official
