Qu’est-ce que le protocole de consensus HotStuff et comment fonctionne-t-il ?

Qu’est-ce que le protocole de consensus HotStuff ?

HotStuff est un protocole de consensus BFT qui permet à un groupe fixe de validateurs de se mettre d’accord sur un ordre définitif unique de transactions ou d’autres instructions, même si une partie de ce groupe commet des erreurs ou envoie volontairement des messages trompeurs.

BFT signifie Byzantine Fault Tolerance. Cela signifie que le protocole résiste à des validateurs qui tombent en panne, ne répondent pas, mentent ou envoient des messages différents à différents participants. HotStuff fait en sorte que les validateurs qui fonctionnent correctement suivent malgré tout la même version de la blockchain ou du registre partagé.

HotStuff fonctionne avec un groupe de validateurs connu. Le protocole ne détermine donc pas lui-même qui peut devenir validateur, comment le staking est organisé, ni comment un réseau crypto ouvert sélectionne les participants. Ces règles se situent en dehors de HotStuff. Le protocole se concentre sur la question suivante : comment ce groupe de validateurs atteint-il un accord de manière sécurisée ?

Le modèle initial part d’un groupe de validateurs comptant n = 3f + 1 participants. Ici, n est le nombre total de validateurs et f est le nombre maximal de validateurs pouvant se comporter de manière erronée ou malveillante. En d’autres termes : tant que moins d’un tiers des validateurs est non fiable, le système continue de fonctionner correctement.
Avec 4 validateurs, au maximum 1 peut être non fiable. Les 3 autres validateurs peuvent alors encore prendre ensemble une décision sûre. Avec 7 validateurs, au maximum 2 validateurs peuvent être non fiables. Pour qu’une décision soit valide, au moins 5 validateurs doivent être d’accord. HotStuff utilise pour cela un quorum certificate, souvent abrégé en QC. Un QC est une preuve cryptographique compacte indiquant qu’un nombre suffisant de validateurs a voté pour la même proposition. Un quorum est la quantité minimale de soutien nécessaire pour prendre une décision. Dans le modèle initial, ce quorum correspond à n − f, soit 2f + 1, votes.

Avec 4 validateurs, cela représente 3 votes. Avec 7 validateurs, cela représente 5 votes. Ce seuil élevé empêche un petit groupe de validateurs non fiables de faire approuver, à lui seul, un bloc conflictuel.

HotStuff est conçu pour un réseau partiellement synchrone. Cela signifie que les messages peuvent être fortement retardés temporairement, mais que le réseau doit finir par redevenir suffisamment stable pour livrer les messages à temps. La sécurité reste garantie, même pendant de grands retards. En revanche, la progression, comme la finalisation de nouveaux blocs, n’est garantie que lorsque le réseau est suffisamment stable.

À retenir

• HotStuff est un protocole de consensus BFT pour un groupe fixe de validateurs.
• Les validateurs fixent ensemble un ordre unique de transactions ou d’instructions.
• Un quorum certificate prouve cryptographiquement qu’un nombre suffisant de validateurs soutient la même proposition.
• Le modèle initial tolère moins d’un tiers de validateurs byzantins.
• HotStuff conserve la sécurité en cas de retards réseau, mais nécessite un réseau stable pour assurer la progression.

Comment fonctionne le protocole de consensus HotStuff ?

HotStuff fonctionne en rondes successives au cours desquelles un leader temporaire coordonne une proposition et les validateurs votent à son sujet. Une telle ronde s’appelle une view. Le leader n’est pas un producteur de blocs permanent, mais n’a qu’un rôle de coordination durant cette view spécifique.

Dans la variante originale Basic HotStuff, trois phases de vote sont nécessaires avant qu’une décision devienne définitive : prepare, pre-commit et commit. Chaque phase apporte aux validateurs une certitude supplémentaire qu’aucune proposition conflictuelle ne peut être finalisée.

Une forme pratique ultérieure, Chained HotStuff, fait se chevaucher ces phases sur des blocs successifs. Ainsi, un nouveau bloc peut en même temps fournir une preuve de la progression de blocs antérieurs. Les règles de base relatives aux votes, aux quorums et à la sécurité demeurent identiques.

Quel rôle jouent les validateurs et le leader ?

Les validateurs vérifient si la proposition du leader est sûre avant de voter. Ils examinent notamment si la proposition s’appuie sur les bons blocs précédents et si elle respecte les règles de sécurité du protocole. Si c’est le cas, ils envoient un vote signé numériquement au leader.

Le leader collecte les votes. Dès qu’il dispose d’un nombre suffisant de votes, il les regroupe en un seul QC. Au lieu de transmettre constamment tous les votes individuels, le leader peut donc diffuser une preuve compacte indiquant qu’un quorum a approuvé.

Les validateurs utilisent également un lock, c’est-à-dire un verrouillage. Un lock est une règle qui empêche un validateur de soutenir ultérieurement, sans raison, une branche conflictuelle. En règle générale, un validateur ne vote que pour une proposition qui étend sa branche verrouillée. Une exception est possible lorsqu’un QC issu d’une view plus élevée démontre, selon les règles de sécurité, qu’une suite est sûre.

Lorsqu’une view ne progresse pas, par exemple parce que le leader est hors ligne, les validateurs basculent vers une nouvelle view. Ils envoient alors un message new-view au leader suivant. Ce message contient leur prepareQC le plus élevé connu, c’est-à-dire la preuve la plus solide dont ils disposent à cet instant.

Le nouveau leader choisit le QC reçu le plus élevé comme highQC. C’est le point de départ d’une nouvelle proposition sûre. Une rotation connue à l’avance peut déterminer qui est le prochain leader. Un pacemaker, un mécanisme basé sur des time-outs, garantit que les validateurs n’attendent pas indéfiniment un leader non fonctionnel.

Comment se déroule le processus de consensus ?

Dans Basic HotStuff, la prise de décision se déroule étape par étape via trois phases de vote. La description suivante montre comment une proposition passe du début jusqu’à une décision définitive.

1. Le nouveau leader collecte des informations. Lors d’un changement de view, le nouveau leader reçoit des messages new-view provenant d’un quorum de validateurs. Le leader choisit le QC le plus élevé qui y figure. Cela évite que le leader ne fasse une proposition qui entre en conflit avec un bloc antérieur déjà poursuivi de manière sûre.

2. Le leader fait une proposition. Le leader construit un nouveau bloc sur la branche justifiée par le highQC et l’envoie à tous les validateurs. La proposition contient donc également la preuve expliquant pourquoi il s’agit de la suite sûre.

3. Les validateurs vérifient et votent dans la phase prepare. Chaque validateur vérifie que le bloc respecte les règles de sécurité. Si la proposition les respecte, le validateur renvoie un vote prepare au leader.

4. Le leader forme des preuves pour prepare et pre-commit. Après 2f + 1 votes prepare, le leader crée un prepareQC et le diffuse pour la phase pre-commit. Ensuite, les validateurs collectent à nouveau des votes. Avec encore 2f + 1 votes, le leader forme un precommitQC.

5. Les validateurs verrouillent et valident (commit) la proposition. Les validateurs établissent un lock sur la base du precommitQC et votent dans la phase commit. Le leader regroupe ensuite 2f + 1 votes commit en un commitQC. Un message decide ultérieur rend la proposition exécutable et définitive.

Exemple : Supposons qu’un groupe soit composé de 4 validateurs. Un leader propose un bloc. Au moins 3 validateurs doivent voter dans chaque phase requise avant que le leader puisse former un QC. Un validateur défectueux ne peut donc pas forcer le processus à rendre définitif un autre bloc.

Chained HotStuff rend cette méthode plus efficace en combinant les phases de différents blocs. Selon la three-chain commit rule, le bloc le plus ancien d’une série devient définitif lorsque trois blocs consécutifs sont reliés entre eux, selon les règles du protocole, via des QCs valides. Cette chaîne fournit la preuve de commit pour le plus ancien bloc pertinent.

Comment HotStuff gère-t-il les fautes byzantines ?

HotStuff limite l’impact des fautes byzantines en combinant un seuil de vote élevé, des votes signés, des locks et des règles claires de changement de view. Un validateur byzantin est un validateur qui se comporte de manière imprévisible ou malveillante, par exemple en mentant, en ne répondant pas ou en envoyant différentes propositions à différents validateurs.

La limite de fautes est inférieure à un tiers des validateurs dans un groupe non pondéré. Avec n = 3f + 1 participants, au maximum f validateurs peuvent être byzantins. Un QC exige 2f + 1 votes, ce qui équivaut à n − f.

La conséquence importante est que deux quorums se chevauchent toujours. Avec 7 validateurs, par exemple, 5 votes sont nécessaires pour un QC. Deux groupes de 5 votes doivent avoir au minimum 3 validateurs en commun. Comme au plus 2 validateurs peuvent être byzantins, ce chevauchement contient toujours au moins un validateur correct.

Un validateur correct ne vote pas deux fois pour des propositions conflictuelles dans la même phase et la même view. Ainsi, deux QCs conflictuels pour la même phase et la même view ne peuvent pas apparaître. Les locks et la règle safeNode, c’est-à-dire la vérification qu’une nouvelle proposition s’appuie de manière sûre sur des preuves connues, garantissent en outre que les validateurs ne basculent pas ensuite sans raison vers une branche conflictuelle.

Cela protège la safety. Ici, safety signifie que deux blocs conflictuels ne peuvent pas être rendus définitifs tous les deux par des validateurs fonctionnant correctement. En cas d’incertitude, le réseau préfère attendre plutôt que de rendre définitives deux histoires différentes.

La liveness concerne la progression : la capacité à rendre définitifs de nouveaux blocs. HotStuff ne promet pas cette progression pendant une partition réseau prolongée ou des retards importants persistants. Dès que le réseau redevient suffisamment stable et qu’un leader correct dirige la même view suffisamment longtemps, les validateurs peuvent à nouveau former des quorums et continuer.

Dans des variantes proof-of-stake, cette limite est souvent exprimée en poids de vote plutôt qu’en simple nombre de validateurs. Dans ce cas, chaque validateur n’a pas le même poids. Les garanties de sécurité et de progression ne s’appliquent que tant que moins d’un tiers du poids de vote pertinent est byzantin.

À quoi sert le protocole de consensus HotStuff ?

HotStuff est utilisé pour permettre à un groupe de serveurs ou de validateurs d’enregistrer un ordre définitif unique d’instructions. On appelle cela la state machine replication : plusieurs ordinateurs exécutent les mêmes instructions dans le même ordre, afin de conserver le même résultat et le même registre partagé.

Dans une blockchain, cette tâche peut consister à ordonner et à finaliser des blocs contenant des transactions. Une fois que les validateurs ont fixé l’ordre, d’autres composants du réseau peuvent exécuter les transactions et mettre à jour le registre. HotStuff détermine donc principalement l’ordre et la finalité des décisions.

DiemBFT était une famille de consensus basée sur HotStuff pour l’historique blockchain Diem. Cette famille de protocoles ordonnait et finalisait les transactions au sein d’un groupe de validateurs configurable.

Aptos utilise AptosBFT, un protocole de consensus BFT basé sur Jolteon. Le protocole fonctionne avec un pouvoir de vote pondéré par la stake et peut appliquer une sélection de leaders basée sur la réputation, où le comportement et les performances des validateurs influencent le choix des leaders. Dans ce cadre, le poids de vote des validateurs peut varier en fonction de la stake.

Flow utilise la famille de consensus HotStuff et a migré en janvier 2023 vers Jolteon. Jolteon est une variante optimisée de HotStuff. Ces systèmes n’emploient donc pas nécessairement la spécification HotStuff originale exactement telle qu’elle a été conçue ; des détails comme la sélection des leaders et le traitement peuvent différer.

Quels sont les avantages de HotStuff ?

HotStuff a pour avantage majeur d’organiser plus efficacement la communication entre validateurs que des protocoles où chacun doit communiquer en permanence avec tous les autres validateurs.

• Preuves compactes : le leader regroupe les votes des validateurs avec des threshold signatures en un seul QC. Les threshold signatures sont des signatures numériques agrégées qui prouvent qu’un nombre suffisant de validateurs a voté. Ainsi, un validateur n’a pas besoin de recevoir systématiquement tous les votes individuels pour vérifier le quorum.

• Communication linéaire avec un leader correct : dans le modèle initial, la charge de communication et d’authentification par leader correct augmente approximativement avec le nombre de validateurs, au lieu d’augmenter beaucoup plus rapidement. Cela ne dit pas automatiquement combien de transactions une blockchain complète peut traiter, car l’exécution, le stockage, le matériel et la propagation des transactions peuvent aussi constituer des facteurs limitants.

• Changements de leader plus efficaces : HotStuff est conçu pour nécessiter moins de communication que PBFT même en cas de défaillance d’un leader. C’est important lorsqu’un leader tombe en panne ou ne diffuse pas de proposition exploitable.

• Pipelining dans Chained HotStuff : de nouvelles propositions peuvent contribuer à la finalisation de blocs antérieurs. Ainsi, le réseau n’a pas besoin de terminer entièrement chaque phase de manière isolée avant de commencer une proposition suivante.

• Finalité déterministe : un bloc commité est définitif dans le cadre des hypothèses de sécurité. La finalité déterministe signifie que des validateurs fonctionnant correctement ne pourront pas accepter plus tard comme définitif un bloc conflictuel.

HotStuff présente en outre une optimistic responsiveness. Une fois le réseau redevenu stable, un leader correct n’a pas besoin d’attendre systématiquement un délai maximal de réseau prédéfini si les messages nécessaires ont déjà été reçus plus tôt. Cela peut améliorer la progression dans des conditions réseau favorables.

Quelles sont les limites de HotStuff ?

HotStuff n’offre pas une protection illimitée ni une progression garantie dans toutes les circonstances. Son fonctionnement dépend d’hypothèses claires concernant les validateurs, la communication réseau et l’implémentation choisie.

• Limites de tolérance aux fautes : l’analyse formelle de sécurité s’applique lorsque moins d’un tiers des validateurs, ou du poids de vote, est byzantin. Au-delà, les garanties de sécurité et de progression sortent du modèle.

• Aucune progression en cas de partition persistante : la safety reste assurée malgré des retards réseau illimités, mais HotStuff ne rend pas de nouveaux blocs définitivement validés tant que le réseau reste durablement divisé ou instable.

• Dépendance au leader : un leader défaillant, en panne ou injoignable peut faire échouer une view. Le pacemaker et la rotation des leaders aident finalement le réseau à se rétablir lorsque l’hypothèse de synchronie redevient valable, mais ils entraînent d’abord des retards supplémentaires.

• Groupe fixe de validateurs comme point de départ : le protocole original part d’un groupe de validateurs connu, authentifié, et de threshold signatures. HotStuff ne détermine pas lui-même comment un réseau ouvert choisit les validateurs, répartit la stake ou sanctionne les comportements économiques malveillants.

• Plusieurs phases pour la finalité : Basic HotStuff nécessite trois phases de vote avant qu’une proposition soit définitive. Chained HotStuff augmente le débit grâce au pipelining, mais le temps jusqu’à la finalité des premiers blocs et le comportement lors des changements de leader restent dépendants des retards réseau, des time-outs et de l’implémentation.

Le leader réduit donc la quantité de communication entre participants, mais devient aussi un point de coordination temporaire important. Ce leader doit collecter les votes du quorum à temps et diffuser de nouvelles preuves.

Comment HotStuff se compare-t-il à d’autres protocoles de consensus ?

HotStuff appartient à la famille des protocoles BFT basés sur un leader, mais se distingue par la manière dont il organise les votes, les quorums et les changements de leader. Il n’existe pas de hiérarchie directe : les protocoles font des choix différents concernant les groupes de validateurs, les conditions réseau et la finalité.

Par rapport à PBFT, HotStuff est conçu pour réduire la communication lors de la progression normale et lors d’un changement de view. Dans la comparaison initiale, la complexité des authentificateurs de HotStuff, en présence d’un leader correct et lors d’une défaillance de leader, croît linéairement avec le nombre de validateurs. Dans la même comparaison, cette charge augmente plus rapidement avec PBFT. La complexité des authentificateurs concerne spécifiquement la quantité d’informations d’authentification à traiter dans le protocole, et non directement les transactions par seconde ou la latence pour les utilisateurs.

Tendermint et Casper partagent avec HotStuff l’approche BFT avec des leaders temporaires, des quorums et la finalité. Dans la comparaison initiale, les variantes Tendermint et Casper de l’époque avaient une charge de communication plus élevée. Des optimisations techniques, telles que les threshold signatures, peuvent modifier ces coûts dans des implémentations spécifiques.

HotStuff diffère nettement du consensus de Nakamoto, comme Bitcoin. HotStuff fonctionne avec un groupe de validateurs connu et peut finaliser de manière déterministe des décisions commitées tant que la limite de fautes n’est pas dépassée. Bitcoin utilise un modèle permissionless de proof-of-work où les participants peuvent se joindre librement et où la finalité est probabiliste. Cela signifie que la probabilité d’annulation diminue à mesure que davantage de blocs suivent, au lieu qu’un instant donné confère une finalité absolue dans les règles du protocole.

Par rapport aux protocoles BFT totalement asynchrones, HotStuff choisit la synchronie partielle. Le protocole peut ainsi progresser de manière réactive lorsque le réseau se stabilise, mais ne promet pas de liveness pendant une partition réseau persistante.

Des variantes ultérieures s’appuient sur les idées de HotStuff. DiemBFTv4 adapte l’approche avec un commit en régime permanent en deux étapes, tandis que Flow utilise Jolteon comme variante optimisée de HotStuff. De tels dérivés peuvent présenter des propriétés différentes de celles du protocole original.

En résumé

HotStuff est un protocole de consensus BFT qui aide un groupe fixe de validateurs à enregistrer de manière sûre un ordre unique de transactions ou d’instructions. Le leader temporaire collecte les votes, tandis que les quorum certificates démontrent qu’un nombre suffisant de validateurs a vérifié et soutenu la même proposition.

La combinaison de seuils de vote élevés, de signatures numériques, de locks et de changements de view empêche un petit groupe de validateurs byzantins de rendre définitifs deux blocs conflictuels. HotStuff reste ainsi sûr pendant de grands retards réseau, mais ne peut garantir la progression que lorsque le réseau redevient suffisamment stable et qu’un leader correct reste actif.

Le regroupement efficace des votes et la possibilité de pipelining font de HotStuff une base importante pour des variantes BFT modernes. En parallèle, il demeure essentiel de comprendre que HotStuff n’est pas un modèle de consensus entièrement ouvert ni un système économique : la sélection des validateurs, la stake et les incitations sont définies par la blockchain ou l’implémentation qui l’entoure.