Les laboratoires Aptos ont résolu deux problèmes ouverts importants dans DAG BFT, réduisant considérablement la latence et, pour la première fois, éliminant le besoin de pauses dans les protocoles pratiques déterministes. Dans l'ensemble, cela améliore la latence de Bullshark de 40 % en cas de non-échec et de 80 % en cas de défaut.
Shoal est un cadre qui améliore tout protocole de consensus basé sur Narwhal (par exemple, DAG-Rider, Tusk, Bullshark) grâce à la canalisation et à la réputation de leader. Le pipeline réduit la latence de commande DAG en introduisant une ancre par tour, et la réputation du leader améliore encore la latence en garantissant que les ancres sont associées aux validateurs les plus rapides. De plus, la réputation de leader permet à Shoal de tirer parti de la construction DAG asynchrone pour éliminer les délais d'attente dans tous les scénarios. Cela permet à Shoal de fournir une propriété que nous avons nommée Universal Response, qui contient la réponse optimiste généralement requise.
Notre technique est très simple, elle consiste à exécuter plusieurs instances du protocole sous-jacent de manière séquentielle les unes après les autres. Ainsi, lorsqu'il est instancié avec Bullshark, nous obtenons un groupe de "requins" qui font une course de relais.
Motivation
Dans la poursuite de hautes performances dans les réseaux blockchain, l'accent a été mis en permanence sur la réduction de la complexité des communications. Cependant, cette approche n'a pas entraîné une augmentation significative du débit. Par exemple, l'implémentation de Hotstuff dans une première version de Diem n'a atteint que 3500 TPS, bien en deçà de notre objectif d'atteindre 100k+ TPS.
Cependant, les percées récentes découlent de la prise de conscience que la propagation des données est le principal goulot d'étranglement des protocoles basés sur les leaders et qu'elle peut bénéficier de la parallélisation. Le système Narwhal sépare la propagation des données de la logique de consensus de base et propose une architecture où tous les validateurs propagent les données simultanément, tandis que les composants de consensus ne commandent qu'une plus petite quantité de métadonnées. Le journal Narwhal rapporte un débit de 160 000 TPS.
Dans un article précédent, nous avons présenté Quorum Store. Notre implémentation Narwhal dissocie la propagation des données du consensus, et comment nous l'utilisons pour étendre notre protocole de consensus actuel, Jolteon. Jolteon est un protocole basé sur un leader qui combine le chemin rapide linéaire de Tendermint avec des changements de vue de style PBFT pour réduire la latence de Hotstuff de 33 %. Cependant, il est clair qu'un protocole de consensus basé sur un leader ne peut pas exploiter pleinement le potentiel de débit du narval. Malgré la séparation de la propagation des données du consensus, les leaders de Hotstuff/Jolteon sont toujours limités à mesure que le débit augmente.
Par conséquent, nous avons décidé de déployer Bullshark, un protocole de consensus sans surcharge de communication, au-dessus de Narwhal DAG. Malheureusement, la structure DAG qui prend en charge le débit élevé de Bullshark s'accompagne d'une pénalité de latence de 50 % par rapport à Jolteon.
Dans cet article, nous décrivons comment Shoal a réussi à réduire considérablement la latence de Bullshark.
Contexte DAG-BFT
Commençons par comprendre le contexte pertinent de cet article. Pour une description détaillée du narval et du bullshark, veuillez vous référer au message DAG rencontre BFT.
Chaque sommet d'un Narwhal DAG est associé à un nombre rond. Pour entrer dans le tour r, un vérificateur doit d'abord obtenir nf sommets appartenant au tour r-1. Chaque vérificateur peut diffuser un sommet par tour, et chaque sommet fait référence à au moins nf sommets du tour précédent. En raison de l'asynchronisme du réseau, différents validateurs peuvent observer différentes vues locales du DAG à tout moment. Voici une illustration d'une vue partielle possible :
Figure 1 : L'historique causal des sommets identifiés par le nœud 2 de validation du tour 2 est surligné en vert
Une propriété clé des DAG n'est pas l'ambiguïté : deux validateurs ont exactement le même historique causal de v s'ils ont le même sommet v dans leur vue locale du DAG.
Commande totale
Il est possible de s'entendre sur l'ordre total de tous les sommets d'un DAG sans surcharge de communication supplémentaire. À cette fin, les validateurs de DAG-Rider, Tusk et Bullshark interprètent la structure du DAG comme un protocole de consensus, où les sommets représentent les propositions et les arêtes représentent les votes.
Bien que la logique d'intersection de groupe diffère sur la structure DAG, tous les protocoles de consensus existants basés sur Narwhal ont la structure suivante :
Ancres prédéterminées, il y aura un leader prédéterminé tous les quelques tours (par exemple, deux tours dans Bullshark), et les sommets du leader sont appelés ancres ;
En commandant les ancres, le vérificateur décide indépendamment mais de manière déterministe quelles ancres commander et quelles ancres ignorer ;
Ordonner les histoires causales, où les validateurs traitent leur liste ordonnée d'ancres une par une, et pour chaque ancre, trient tous les sommets précédemment non ordonnés dans son histoire causale selon certaines règles déterministes.
Figure 2 : Illustration d'une vue partielle possible d'un DAG dans le protocole Bullshark. Dans cet exemple, les ancres rouges et jaunes sont triées, tandis que le vert (pas dans le DAG) est ignoré. Par conséquent, pour ordonner le DAG, les validateurs ordonnent de manière déterministe les historiques causaux des ancres rouges en premier, suivis des ancres jaunes.
La clé pour satisfaire la sécurité est de s'assurer qu'à l'étape (2) ci-dessus, tous les validateurs honnêtes créent une liste ordonnée d'ancres de sorte que toutes les listes partagent le même préfixe. Chez Shoal, nous faisons les observations suivantes pour tous les protocoles ci-dessus :
** Tous les validateurs s'accordent sur la première ancre commandée. **
Latence Bullshark
La latence de Bullshark dépend du nombre de tours entre les ancres ordonnées dans le DAG. Bien que la version partiellement synchrone la plus utile de Bullshark ait une meilleure latence que la version asynchrone, elle est loin d'être optimale.
Problème 1 : Latence moyenne des blocs. Dans Bullshark, chaque tour pair a une ancre et les sommets de chaque tour impair sont interprétés comme des votes. En règle générale, il faut deux tours du DAG pour commander des ancres, cependant, les sommets de l'historique causal d'une ancre prennent beaucoup plus de tours pour attendre qu'une ancre soit commandée. Dans le cas courant, les sommets dans les tours impairs nécessitent trois tours, tandis que les sommets non ancrés dans les tours pairs nécessitent quatre tours (voir Figure 3).
Figure 3 : Dans le cas courant, les ancres du tour i+1 doivent être triées pendant deux tours. Les sommets du tour i sont triés simultanément, leur latence est donc de trois tours. Cependant, les sommets du tour i+1 doivent attendre que la prochaine ancre soit triée (celle du tour i+3), donc leur délai de tri est de quatre tours.
Problème 2 : Latence du cas d'échec, l'analyse de latence ci-dessus s'applique au cas sans échec, d'autre part, si le leader d'un tour ne parvient pas à diffuser les ancres assez rapidement, les ancres ne peuvent pas être commandées (et sont donc ignorées), donc Tous les sommets non triés dans les tours précédents doivent attendre que la prochaine ancre soit triée. Cela peut réduire considérablement les performances d'un réseau géo-répliqué, d'autant plus que Bullshark utilise des délais d'attente en attente du leader.
Cadre de banc
Shoal résout ces deux problèmes de latence en améliorant Bullshark (ou tout autre protocole BFT basé sur Narwhal) en pipelinant, en permettant une ancre à chaque tour et en réduisant la latence de tous les sommets non ancrés dans le DAG à trois tours. Shoal introduit également un mécanisme de réputation de leader sans frais généraux dans le DAG, qui biaise la sélection en faveur des leaders rapides.
défi
Dans le contexte des protocoles DAG, le pipelining et la réputation du leader sont considérés comme des problèmes difficiles pour les raisons suivantes :
Le pipelining précédent tente de modifier la logique de base de Bullshark, mais cela semble intrinsèquement impossible
Leader Reputation, introduite dans DiemBFT et formalisée dans Carousel, est l'idée de sélectionner dynamiquement les futurs leaders (ancres dans Bullshark) en fonction des performances passées des validateurs. Alors que le désaccord sur l'identité du leader ne viole pas la sécurité dans ces protocoles, dans Bullshark, cela peut conduire à un ordre complètement différent, qui va au cœur de la question, à savoir que la sélection dynamique et déterministe des ancres de roue est la clé pour résoudre le consensus requis. , tandis que les validateurs doivent se mettre d'accord sur un historique ordonné pour sélectionner les futures ancres.
Comme preuve de la difficulté du problème, nous notons que l'implémentation de Bullshark, y compris l'implémentation actuelle en production, ne prend pas en charge ces fonctionnalités.
accord
Malgré les défis susmentionnés, il s'avère que les solutions, comme le dit le proverbe, se cachent derrière la simplicité.
Dans Shoal, nous nous appuyons sur la capacité d'effectuer des calculs locaux sur le DAG et implémentons la capacité de conserver et de réinterpréter les informations des cycles précédents. Avec l'idée de base que tous les validateurs s'accordent sur la première ancre ordonnée, Shoal les canalise en composant plusieurs instances de Bullshark en séquence de telle sorte que (1) la première ancre ordonnée est le point de commutation pour les instances, et (2) L'histoire causale du Les ancres sont utilisées pour calculer la réputation du leader.
Canalisation
Semblable à Bullshark, les validateurs s'accordent a priori sur les ancres potentielles, c'est-à-dire qu'il existe un mappage connu F: R -> V mappage des tours aux leaders. Shoal exécute les instances de Bullshark les unes après les autres de sorte que pour chaque instance l'ancre est prédéterminée par la carte F. Chaque instance commande une ancre, qui déclenche un passage à l'instance suivante.
Initialement, Shoal lance la première instance de Bullshark au premier tour du DAG et l'exécute jusqu'à ce que la première ancre commandée soit identifiée, disons au tour r. Tous les validateurs sont d'accord sur cette ancre. Par conséquent, tous les validateurs peuvent s'accorder de manière déterministe pour réinterpréter le DAG à partir du tour r+1. Shoal commence juste une nouvelle instance de Bullshark au round r+1.
Dans le meilleur des cas, cela permet à Shoal de commander une ancre à chaque tour. Les ancres du premier tour sont triées par première instance. Ensuite, Shoal démarre une nouvelle instance au deuxième tour, qui a elle-même une ancre commandée par l'instance, puis une autre nouvelle instance commande les ancres au troisième tour, et le processus se poursuit. Veuillez consulter l'illustration ci-dessous :
Figure 4 : Les sommets correspondant aux leaders déterminés par F sont marqués d'une couronne. La première instance de Bullshark interprète d'abord le DAG avec les ancres aux tours 1, 3 et 5. Bullshark détermine les ancres au tour 1 (en coche verte marque) est le premier à être trié en première instance. (Notez que dans le cas général, cette ancre peut être ignorée, tandis que d'autres ancres seront triées en premier.) Ensuite, le reste de la première instance est ignoré, et une nouvelle instance de Bullshark commence à partir du tour 2, les points d'ancrage sont marqués aux tours 2 et 4.
Réputation de chef
Augmentation de la latence lors du saut des ancres lors du tri Bullshark. Dans ce cas, la technique Pipelining est impuissante car une nouvelle instance ne peut être démarrée tant que l'instance précédente n'a pas commandé une ancre. Shoal garantit que le leader approprié est moins susceptible d'être élu à l'avenir pour faire face à une ancre perdue en utilisant un mécanisme de réputation pour attribuer à chaque validateur un score basé sur son historique d'activité récente. Un validateur qui répond et participe au protocole se verra attribuer un score élevé, sinon, un validateur se verra attribuer un score faible car il peut planter, être lent ou être malveillant.
L'idée est de recalculer de manière déterministe la cartographie prédéfinie F des tours aux leaders à chaque mise à jour du score, en favorisant les leaders avec des scores plus élevés. Pour que les validateurs s'accordent sur le nouveau mappage, ils doivent s'accorder sur le score et donc sur l'historique utilisé pour dériver le score.
Dans Shoal, le pipelining et la réputation de leadership peuvent être combinés naturellement car ils utilisent tous deux la même technique de base consistant à réinterpréter le DAG après s'être mis d'accord sur la première ancre ordonnée.
En fait, la seule différence est qu'après avoir trié les ancres au tour r, le validateur n'a plus qu'à calculer une nouvelle cartographie F' à partir du tour r+1 en se basant sur l'historique causal des ancres ordonnées au tour r . Ensuite, le validateur exécute une nouvelle instance de Bullshark à partir du tour r+1 en utilisant la fonction de sélection d'ancre mise à jour F'. Voir l'image ci-dessous :
Figure 5. Les sommets correspondant aux leaders identifiés par F sont marqués de couronnes transparentes. La première instance de Bullshark commande une ancre au tour 1, marquée d'une coche verte, puis calcule une nouvelle cartographie F' basée sur les informations de l'historique causal de l'ancre. Les chefs déterminés par F' sont marqués par des couronnes colorées.
Plus de délais d'attente
Les délais d'attente jouent un rôle crucial dans toutes les implémentations BFT déterministes partiellement synchrones basées sur le leader. Cependant, la complexité qu'ils introduisent augmente la quantité d'états internes qui doivent être gérés et observés, ce qui complique le processus de débogage et nécessite davantage de techniques d'observabilité.
Les délais d'expiration peuvent également augmenter considérablement la latence, car il est important de les configurer de manière appropriée et doivent généralement être ajustés de manière dynamique, car ils dépendent fortement de l'environnement (réseau). Le protocole paie au chef fautif la pénalité de délai d'attente complète avant de passer au chef suivant. Par conséquent, le paramètre de délai d'attente ne peut pas être trop conservateur, mais si le délai d'attente est trop court, le protocole peut ignorer les bons leaders. Par exemple, nous avons observé qu'en cas de charge élevée, les dirigeants de Jolteon/Hotstuff étaient dépassés et les délais d'attente expiraient avant qu'ils ne puissent pousser la progression.
Malheureusement, les protocoles basés sur le leader tels que Hotstuff et Jolteon nécessitent intrinsèquement des délais d'attente pour garantir que le protocole peut progresser à chaque fois que le leader échoue. Sans délai d'attente, même un leader écrasé pourrait arrêter le protocole pour toujours. En raison de l'incapacité à faire la distinction entre un leader défectueux et un leader lent pendant l'asynchronisme, les délais d'attente peuvent amener les validateurs à voir les changements sur tous les leaders sans vivacité consensuelle.
Dans Bullshark, les délais d'attente sont utilisés dans la construction du DAG pour s'assurer que pendant la synchronisation, un leader honnête ajoute des ancres au DAG assez rapidement pour qu'elles soient commandées.
Nous observons que la construction DAG fournit une "horloge" pour estimer la vitesse du réseau. En l'absence de pauses, les rondes continuent de progresser tant que nf validateurs honnêtes continuent d'ajouter des sommets au DAG. Bien que Bullshark puisse ne pas être en mesure de trier à la vitesse du réseau (en raison de leaders problématiques), le DAG continue de croître à la vitesse du réseau malgré certains problèmes de leader ou le réseau étant asynchrone. Finalement, lorsqu'un leader sans faute diffuse des ancres assez rapidement, toute l'histoire causale des ancres sera commandée.
Dans notre évaluation, nous avons comparé Bullshark avec et sans timeout dans les cas suivants :
Leader rapide, c'est-à-dire au moins plus rapide que les autres validateurs. Dans ce cas, les deux méthodes fournissent la même latence car les ancres sont ordonnées et les délais d'attente ne sont pas utilisés.
Faux leader, dans ce cas Bullshark sans pauses offre une meilleure latence car les validateurs sauteront immédiatement ses ancres, tandis que les validateurs avec des pauses attendront leur arrivée avant de continuer Expect.
Leader lent, c'est le seul cas où Bullshark a de meilleures performances de timeout. En effet, sans pause, l'ancre peut être ignorée car le leader ne peut pas la diffuser assez rapidement, alors qu'avec une pause, les validateurs attendront l'ancre.
Chez Shoal, éviter les temps morts et la réputation de leadership vont de pair. L'attente répétée d'un leader lent augmente la latence, et le mécanisme de réputation du leader empêche les validateurs lents d'être élus en tant que leaders. De cette façon, le système utilise des nœuds de validation rapides pour fonctionner à la vitesse du réseau dans tous les scénarios du monde réel.
Notez que le résultat d'impossibilité FLP montre qu'aucun protocole de consensus déterministe ne peut éviter les délais d'attente. Shoal ne peut pas contourner ce résultat car il existe un calendrier théorique d'événements contradictoires qui empêcherait toutes les ancres d'être commandées. Au lieu de cela, Shoal revient à un délai d'attente après un nombre configurable de sauts d'ancre consécutifs. En pratique, cela est extrêmement peu probable.
Réponse générale
L'article Hotstuff a popularisé le concept de réponse optimiste, qui, bien qu'il ne soit pas formellement défini, signifie intuitivement que le protocole peut fonctionner à la vitesse du réseau dans de bonnes conditions, y compris un leader rapide et un réseau synchrone.
Shoal offre une propriété encore meilleure, que nous appelons Universal Response. Plus précisément, contrairement à Hotstuff, Shoal continue de fonctionner à la vitesse du réseau même si le leader échoue pendant un nombre configurable de tours consécutifs ou de cycles asynchrones par lesquels le réseau passe. Voir une comparaison plus détaillée dans le tableau ci-dessous.
Notez que la réactivité universelle offre des garanties de progrès strictement meilleures pendant les périodes asynchrones et lorsque le leader échoue. Lors de la synchronisation avec un leader lent, ces propriétés ne sont pas comparables car elles dépendent de la lenteur du leader. Cependant, étant donné la réputation du leader, les leaders lents devraient rarement apparaître dans Shoal.
Évaluer
Nous avons implémenté Bullshark et Shoal en plus de notre implémentation Narwhal Quorum Store. Une comparaison détaillée entre Shoal, Bullshark et Jolteon peut être trouvée dans la section d'évaluation du document Shoal, où nous fournissons quelques faits saillants.
Tout d'abord, pour démontrer la puissance de la construction DAG asynchrone, nous comparons Bullshark avec et sans pauses. L'article complet de Bullshark suppose un réseau asynchrone, mais fournit un mode de chemin rapide, nécessitant ainsi des pauses pendant tous les tours. Nous appelons cette version la Vanilla Bullshark. Nous observons que pour les versions hypothétiques de réseaux partiellement synchrones indépendants, aucune pause dans les tours de scrutin n'est requise. Nous appelons cette version Vanilla Bullshark sans délai de vote sans délai de vote, Baseline Bullshark est la version sans aucun délai.
Le graphique ci-dessous compare l'impact des délais d'attente sur la latence de Bullshark avec et sans échecs. Apparemment, Baseline Bullshark (pas de délai d'attente) fonctionne mieux en cas d'échec. Sans échec, Baseline Bullshark est comparable à Vanilla Bullshark sans suspension de vote. En effet, comme mentionné précédemment, sans mécanisme de réputation du leader, les délais d'attente peuvent avoir un avantage dans les situations où le leader est bon mais lent.
Figure 6. : Impact des délais d'attente sur la latence de Bullshark sans échecs (à gauche) et avec échecs (à droite), avec 50 validateurs en cas d'échec
Ensuite, nous instancions Shoal à l'aide de Baseline Bullshark (pas de délai) et démontrons les améliorations de la latence du pipelining et du mécanisme de réputation du leader avec et sans échec, et pour être complet, nous le comparons également avec Jolteon avec et sans échec.
La figure 7 ci-dessous montre le cas sans échec, et bien que le pipelining et la réputation du leader puissent réduire la latence individuellement, leur combinaison permet d'obtenir la meilleure latence.
Quant à Jolteon, il ne peut pas évoluer à plus de 20 validateurs, et même s'il s'exécute sur Quorum Store, il ne peut atteindre qu'environ la moitié du débit de Bullshark/Shoal, ce qui supprime le goulot d'étranglement de la propagation des données.
Les résultats montrent que Shoal améliore considérablement la latence de Bullshark. Quant à Jolteon, il est important de noter que même si nous n'avons mesuré que la latence de consensus. Étant donné que Jolteon ne peut pas s'exécuter de manière native sur un DAG, il nécessite une latence supplémentaire pour découpler la propagation des données, ce que nous n'avons pas mesuré. Par conséquent, sous une charge élevée, Shoal devrait correspondre à la latence de bout en bout de Jolteon.
Figure 7 : Débit et latence sans défaillance, Shoal PL et Shaol LR ne prennent en charge que le pipelining et la réputation de leader, respectivement.
La figure 8 ci-dessous montre un cas d'échec avec 50 validateurs, où le mécanisme de réputation du leader améliore considérablement la latence en réduisant la probabilité qu'un validateur défaillant soit élu en tant que leader. Notez qu'avec 16 échecs sur 50, la latence de Shoal était inférieure de 65 % à celle de Baseline Bullshark.
Voir l'original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Explication du framework 4D Shoal : comment réduire la latence de Bullshark sur Aptos ?
Original : Laboratoires Aptos
Compilation : Aptos Global
Aperçu
Les laboratoires Aptos ont résolu deux problèmes ouverts importants dans DAG BFT, réduisant considérablement la latence et, pour la première fois, éliminant le besoin de pauses dans les protocoles pratiques déterministes. Dans l'ensemble, cela améliore la latence de Bullshark de 40 % en cas de non-échec et de 80 % en cas de défaut.
Shoal est un cadre qui améliore tout protocole de consensus basé sur Narwhal (par exemple, DAG-Rider, Tusk, Bullshark) grâce à la canalisation et à la réputation de leader. Le pipeline réduit la latence de commande DAG en introduisant une ancre par tour, et la réputation du leader améliore encore la latence en garantissant que les ancres sont associées aux validateurs les plus rapides. De plus, la réputation de leader permet à Shoal de tirer parti de la construction DAG asynchrone pour éliminer les délais d'attente dans tous les scénarios. Cela permet à Shoal de fournir une propriété que nous avons nommée Universal Response, qui contient la réponse optimiste généralement requise.
Notre technique est très simple, elle consiste à exécuter plusieurs instances du protocole sous-jacent de manière séquentielle les unes après les autres. Ainsi, lorsqu'il est instancié avec Bullshark, nous obtenons un groupe de "requins" qui font une course de relais.
Motivation
Dans la poursuite de hautes performances dans les réseaux blockchain, l'accent a été mis en permanence sur la réduction de la complexité des communications. Cependant, cette approche n'a pas entraîné une augmentation significative du débit. Par exemple, l'implémentation de Hotstuff dans une première version de Diem n'a atteint que 3500 TPS, bien en deçà de notre objectif d'atteindre 100k+ TPS.
Cependant, les percées récentes découlent de la prise de conscience que la propagation des données est le principal goulot d'étranglement des protocoles basés sur les leaders et qu'elle peut bénéficier de la parallélisation. Le système Narwhal sépare la propagation des données de la logique de consensus de base et propose une architecture où tous les validateurs propagent les données simultanément, tandis que les composants de consensus ne commandent qu'une plus petite quantité de métadonnées. Le journal Narwhal rapporte un débit de 160 000 TPS.
Dans un article précédent, nous avons présenté Quorum Store. Notre implémentation Narwhal dissocie la propagation des données du consensus, et comment nous l'utilisons pour étendre notre protocole de consensus actuel, Jolteon. Jolteon est un protocole basé sur un leader qui combine le chemin rapide linéaire de Tendermint avec des changements de vue de style PBFT pour réduire la latence de Hotstuff de 33 %. Cependant, il est clair qu'un protocole de consensus basé sur un leader ne peut pas exploiter pleinement le potentiel de débit du narval. Malgré la séparation de la propagation des données du consensus, les leaders de Hotstuff/Jolteon sont toujours limités à mesure que le débit augmente.
Par conséquent, nous avons décidé de déployer Bullshark, un protocole de consensus sans surcharge de communication, au-dessus de Narwhal DAG. Malheureusement, la structure DAG qui prend en charge le débit élevé de Bullshark s'accompagne d'une pénalité de latence de 50 % par rapport à Jolteon.
Dans cet article, nous décrivons comment Shoal a réussi à réduire considérablement la latence de Bullshark.
Contexte DAG-BFT
Commençons par comprendre le contexte pertinent de cet article. Pour une description détaillée du narval et du bullshark, veuillez vous référer au message DAG rencontre BFT.
Chaque sommet d'un Narwhal DAG est associé à un nombre rond. Pour entrer dans le tour r, un vérificateur doit d'abord obtenir nf sommets appartenant au tour r-1. Chaque vérificateur peut diffuser un sommet par tour, et chaque sommet fait référence à au moins nf sommets du tour précédent. En raison de l'asynchronisme du réseau, différents validateurs peuvent observer différentes vues locales du DAG à tout moment. Voici une illustration d'une vue partielle possible :
Figure 1 : L'historique causal des sommets identifiés par le nœud 2 de validation du tour 2 est surligné en vert
Une propriété clé des DAG n'est pas l'ambiguïté : deux validateurs ont exactement le même historique causal de v s'ils ont le même sommet v dans leur vue locale du DAG.
Commande totale
Il est possible de s'entendre sur l'ordre total de tous les sommets d'un DAG sans surcharge de communication supplémentaire. À cette fin, les validateurs de DAG-Rider, Tusk et Bullshark interprètent la structure du DAG comme un protocole de consensus, où les sommets représentent les propositions et les arêtes représentent les votes.
Bien que la logique d'intersection de groupe diffère sur la structure DAG, tous les protocoles de consensus existants basés sur Narwhal ont la structure suivante :
Ancres prédéterminées, il y aura un leader prédéterminé tous les quelques tours (par exemple, deux tours dans Bullshark), et les sommets du leader sont appelés ancres ;
En commandant les ancres, le vérificateur décide indépendamment mais de manière déterministe quelles ancres commander et quelles ancres ignorer ;
Ordonner les histoires causales, où les validateurs traitent leur liste ordonnée d'ancres une par une, et pour chaque ancre, trient tous les sommets précédemment non ordonnés dans son histoire causale selon certaines règles déterministes.
Figure 2 : Illustration d'une vue partielle possible d'un DAG dans le protocole Bullshark. Dans cet exemple, les ancres rouges et jaunes sont triées, tandis que le vert (pas dans le DAG) est ignoré. Par conséquent, pour ordonner le DAG, les validateurs ordonnent de manière déterministe les historiques causaux des ancres rouges en premier, suivis des ancres jaunes.
La clé pour satisfaire la sécurité est de s'assurer qu'à l'étape (2) ci-dessus, tous les validateurs honnêtes créent une liste ordonnée d'ancres de sorte que toutes les listes partagent le même préfixe. Chez Shoal, nous faisons les observations suivantes pour tous les protocoles ci-dessus :
** Tous les validateurs s'accordent sur la première ancre commandée. **
Latence Bullshark
La latence de Bullshark dépend du nombre de tours entre les ancres ordonnées dans le DAG. Bien que la version partiellement synchrone la plus utile de Bullshark ait une meilleure latence que la version asynchrone, elle est loin d'être optimale.
Problème 1 : Latence moyenne des blocs. Dans Bullshark, chaque tour pair a une ancre et les sommets de chaque tour impair sont interprétés comme des votes. En règle générale, il faut deux tours du DAG pour commander des ancres, cependant, les sommets de l'historique causal d'une ancre prennent beaucoup plus de tours pour attendre qu'une ancre soit commandée. Dans le cas courant, les sommets dans les tours impairs nécessitent trois tours, tandis que les sommets non ancrés dans les tours pairs nécessitent quatre tours (voir Figure 3).
Figure 3 : Dans le cas courant, les ancres du tour i+1 doivent être triées pendant deux tours. Les sommets du tour i sont triés simultanément, leur latence est donc de trois tours. Cependant, les sommets du tour i+1 doivent attendre que la prochaine ancre soit triée (celle du tour i+3), donc leur délai de tri est de quatre tours.
Problème 2 : Latence du cas d'échec, l'analyse de latence ci-dessus s'applique au cas sans échec, d'autre part, si le leader d'un tour ne parvient pas à diffuser les ancres assez rapidement, les ancres ne peuvent pas être commandées (et sont donc ignorées), donc Tous les sommets non triés dans les tours précédents doivent attendre que la prochaine ancre soit triée. Cela peut réduire considérablement les performances d'un réseau géo-répliqué, d'autant plus que Bullshark utilise des délais d'attente en attente du leader.
Cadre de banc
Shoal résout ces deux problèmes de latence en améliorant Bullshark (ou tout autre protocole BFT basé sur Narwhal) en pipelinant, en permettant une ancre à chaque tour et en réduisant la latence de tous les sommets non ancrés dans le DAG à trois tours. Shoal introduit également un mécanisme de réputation de leader sans frais généraux dans le DAG, qui biaise la sélection en faveur des leaders rapides.
défi
Dans le contexte des protocoles DAG, le pipelining et la réputation du leader sont considérés comme des problèmes difficiles pour les raisons suivantes :
Le pipelining précédent tente de modifier la logique de base de Bullshark, mais cela semble intrinsèquement impossible
Leader Reputation, introduite dans DiemBFT et formalisée dans Carousel, est l'idée de sélectionner dynamiquement les futurs leaders (ancres dans Bullshark) en fonction des performances passées des validateurs. Alors que le désaccord sur l'identité du leader ne viole pas la sécurité dans ces protocoles, dans Bullshark, cela peut conduire à un ordre complètement différent, qui va au cœur de la question, à savoir que la sélection dynamique et déterministe des ancres de roue est la clé pour résoudre le consensus requis. , tandis que les validateurs doivent se mettre d'accord sur un historique ordonné pour sélectionner les futures ancres.
Comme preuve de la difficulté du problème, nous notons que l'implémentation de Bullshark, y compris l'implémentation actuelle en production, ne prend pas en charge ces fonctionnalités.
accord
Malgré les défis susmentionnés, il s'avère que les solutions, comme le dit le proverbe, se cachent derrière la simplicité.
Dans Shoal, nous nous appuyons sur la capacité d'effectuer des calculs locaux sur le DAG et implémentons la capacité de conserver et de réinterpréter les informations des cycles précédents. Avec l'idée de base que tous les validateurs s'accordent sur la première ancre ordonnée, Shoal les canalise en composant plusieurs instances de Bullshark en séquence de telle sorte que (1) la première ancre ordonnée est le point de commutation pour les instances, et (2) L'histoire causale du Les ancres sont utilisées pour calculer la réputation du leader.
Canalisation
Semblable à Bullshark, les validateurs s'accordent a priori sur les ancres potentielles, c'est-à-dire qu'il existe un mappage connu F: R -> V mappage des tours aux leaders. Shoal exécute les instances de Bullshark les unes après les autres de sorte que pour chaque instance l'ancre est prédéterminée par la carte F. Chaque instance commande une ancre, qui déclenche un passage à l'instance suivante.
Initialement, Shoal lance la première instance de Bullshark au premier tour du DAG et l'exécute jusqu'à ce que la première ancre commandée soit identifiée, disons au tour r. Tous les validateurs sont d'accord sur cette ancre. Par conséquent, tous les validateurs peuvent s'accorder de manière déterministe pour réinterpréter le DAG à partir du tour r+1. Shoal commence juste une nouvelle instance de Bullshark au round r+1.
Dans le meilleur des cas, cela permet à Shoal de commander une ancre à chaque tour. Les ancres du premier tour sont triées par première instance. Ensuite, Shoal démarre une nouvelle instance au deuxième tour, qui a elle-même une ancre commandée par l'instance, puis une autre nouvelle instance commande les ancres au troisième tour, et le processus se poursuit. Veuillez consulter l'illustration ci-dessous :
Figure 4 : Les sommets correspondant aux leaders déterminés par F sont marqués d'une couronne. La première instance de Bullshark interprète d'abord le DAG avec les ancres aux tours 1, 3 et 5. Bullshark détermine les ancres au tour 1 (en coche verte marque) est le premier à être trié en première instance. (Notez que dans le cas général, cette ancre peut être ignorée, tandis que d'autres ancres seront triées en premier.) Ensuite, le reste de la première instance est ignoré, et une nouvelle instance de Bullshark commence à partir du tour 2, les points d'ancrage sont marqués aux tours 2 et 4.
Réputation de chef
Augmentation de la latence lors du saut des ancres lors du tri Bullshark. Dans ce cas, la technique Pipelining est impuissante car une nouvelle instance ne peut être démarrée tant que l'instance précédente n'a pas commandé une ancre. Shoal garantit que le leader approprié est moins susceptible d'être élu à l'avenir pour faire face à une ancre perdue en utilisant un mécanisme de réputation pour attribuer à chaque validateur un score basé sur son historique d'activité récente. Un validateur qui répond et participe au protocole se verra attribuer un score élevé, sinon, un validateur se verra attribuer un score faible car il peut planter, être lent ou être malveillant.
L'idée est de recalculer de manière déterministe la cartographie prédéfinie F des tours aux leaders à chaque mise à jour du score, en favorisant les leaders avec des scores plus élevés. Pour que les validateurs s'accordent sur le nouveau mappage, ils doivent s'accorder sur le score et donc sur l'historique utilisé pour dériver le score.
Dans Shoal, le pipelining et la réputation de leadership peuvent être combinés naturellement car ils utilisent tous deux la même technique de base consistant à réinterpréter le DAG après s'être mis d'accord sur la première ancre ordonnée.
En fait, la seule différence est qu'après avoir trié les ancres au tour r, le validateur n'a plus qu'à calculer une nouvelle cartographie F' à partir du tour r+1 en se basant sur l'historique causal des ancres ordonnées au tour r . Ensuite, le validateur exécute une nouvelle instance de Bullshark à partir du tour r+1 en utilisant la fonction de sélection d'ancre mise à jour F'. Voir l'image ci-dessous :
Figure 5. Les sommets correspondant aux leaders identifiés par F sont marqués de couronnes transparentes. La première instance de Bullshark commande une ancre au tour 1, marquée d'une coche verte, puis calcule une nouvelle cartographie F' basée sur les informations de l'historique causal de l'ancre. Les chefs déterminés par F' sont marqués par des couronnes colorées.
Plus de délais d'attente
Les délais d'attente jouent un rôle crucial dans toutes les implémentations BFT déterministes partiellement synchrones basées sur le leader. Cependant, la complexité qu'ils introduisent augmente la quantité d'états internes qui doivent être gérés et observés, ce qui complique le processus de débogage et nécessite davantage de techniques d'observabilité.
Les délais d'expiration peuvent également augmenter considérablement la latence, car il est important de les configurer de manière appropriée et doivent généralement être ajustés de manière dynamique, car ils dépendent fortement de l'environnement (réseau). Le protocole paie au chef fautif la pénalité de délai d'attente complète avant de passer au chef suivant. Par conséquent, le paramètre de délai d'attente ne peut pas être trop conservateur, mais si le délai d'attente est trop court, le protocole peut ignorer les bons leaders. Par exemple, nous avons observé qu'en cas de charge élevée, les dirigeants de Jolteon/Hotstuff étaient dépassés et les délais d'attente expiraient avant qu'ils ne puissent pousser la progression.
Malheureusement, les protocoles basés sur le leader tels que Hotstuff et Jolteon nécessitent intrinsèquement des délais d'attente pour garantir que le protocole peut progresser à chaque fois que le leader échoue. Sans délai d'attente, même un leader écrasé pourrait arrêter le protocole pour toujours. En raison de l'incapacité à faire la distinction entre un leader défectueux et un leader lent pendant l'asynchronisme, les délais d'attente peuvent amener les validateurs à voir les changements sur tous les leaders sans vivacité consensuelle.
Dans Bullshark, les délais d'attente sont utilisés dans la construction du DAG pour s'assurer que pendant la synchronisation, un leader honnête ajoute des ancres au DAG assez rapidement pour qu'elles soient commandées.
Nous observons que la construction DAG fournit une "horloge" pour estimer la vitesse du réseau. En l'absence de pauses, les rondes continuent de progresser tant que nf validateurs honnêtes continuent d'ajouter des sommets au DAG. Bien que Bullshark puisse ne pas être en mesure de trier à la vitesse du réseau (en raison de leaders problématiques), le DAG continue de croître à la vitesse du réseau malgré certains problèmes de leader ou le réseau étant asynchrone. Finalement, lorsqu'un leader sans faute diffuse des ancres assez rapidement, toute l'histoire causale des ancres sera commandée.
Dans notre évaluation, nous avons comparé Bullshark avec et sans timeout dans les cas suivants :
Leader rapide, c'est-à-dire au moins plus rapide que les autres validateurs. Dans ce cas, les deux méthodes fournissent la même latence car les ancres sont ordonnées et les délais d'attente ne sont pas utilisés.
Faux leader, dans ce cas Bullshark sans pauses offre une meilleure latence car les validateurs sauteront immédiatement ses ancres, tandis que les validateurs avec des pauses attendront leur arrivée avant de continuer Expect.
Leader lent, c'est le seul cas où Bullshark a de meilleures performances de timeout. En effet, sans pause, l'ancre peut être ignorée car le leader ne peut pas la diffuser assez rapidement, alors qu'avec une pause, les validateurs attendront l'ancre.
Chez Shoal, éviter les temps morts et la réputation de leadership vont de pair. L'attente répétée d'un leader lent augmente la latence, et le mécanisme de réputation du leader empêche les validateurs lents d'être élus en tant que leaders. De cette façon, le système utilise des nœuds de validation rapides pour fonctionner à la vitesse du réseau dans tous les scénarios du monde réel.
Notez que le résultat d'impossibilité FLP montre qu'aucun protocole de consensus déterministe ne peut éviter les délais d'attente. Shoal ne peut pas contourner ce résultat car il existe un calendrier théorique d'événements contradictoires qui empêcherait toutes les ancres d'être commandées. Au lieu de cela, Shoal revient à un délai d'attente après un nombre configurable de sauts d'ancre consécutifs. En pratique, cela est extrêmement peu probable.
Réponse générale
L'article Hotstuff a popularisé le concept de réponse optimiste, qui, bien qu'il ne soit pas formellement défini, signifie intuitivement que le protocole peut fonctionner à la vitesse du réseau dans de bonnes conditions, y compris un leader rapide et un réseau synchrone.
Shoal offre une propriété encore meilleure, que nous appelons Universal Response. Plus précisément, contrairement à Hotstuff, Shoal continue de fonctionner à la vitesse du réseau même si le leader échoue pendant un nombre configurable de tours consécutifs ou de cycles asynchrones par lesquels le réseau passe. Voir une comparaison plus détaillée dans le tableau ci-dessous.
Notez que la réactivité universelle offre des garanties de progrès strictement meilleures pendant les périodes asynchrones et lorsque le leader échoue. Lors de la synchronisation avec un leader lent, ces propriétés ne sont pas comparables car elles dépendent de la lenteur du leader. Cependant, étant donné la réputation du leader, les leaders lents devraient rarement apparaître dans Shoal.
Évaluer
Nous avons implémenté Bullshark et Shoal en plus de notre implémentation Narwhal Quorum Store. Une comparaison détaillée entre Shoal, Bullshark et Jolteon peut être trouvée dans la section d'évaluation du document Shoal, où nous fournissons quelques faits saillants.
Tout d'abord, pour démontrer la puissance de la construction DAG asynchrone, nous comparons Bullshark avec et sans pauses. L'article complet de Bullshark suppose un réseau asynchrone, mais fournit un mode de chemin rapide, nécessitant ainsi des pauses pendant tous les tours. Nous appelons cette version la Vanilla Bullshark. Nous observons que pour les versions hypothétiques de réseaux partiellement synchrones indépendants, aucune pause dans les tours de scrutin n'est requise. Nous appelons cette version Vanilla Bullshark sans délai de vote sans délai de vote, Baseline Bullshark est la version sans aucun délai.
Le graphique ci-dessous compare l'impact des délais d'attente sur la latence de Bullshark avec et sans échecs. Apparemment, Baseline Bullshark (pas de délai d'attente) fonctionne mieux en cas d'échec. Sans échec, Baseline Bullshark est comparable à Vanilla Bullshark sans suspension de vote. En effet, comme mentionné précédemment, sans mécanisme de réputation du leader, les délais d'attente peuvent avoir un avantage dans les situations où le leader est bon mais lent.
Figure 6. : Impact des délais d'attente sur la latence de Bullshark sans échecs (à gauche) et avec échecs (à droite), avec 50 validateurs en cas d'échec
Ensuite, nous instancions Shoal à l'aide de Baseline Bullshark (pas de délai) et démontrons les améliorations de la latence du pipelining et du mécanisme de réputation du leader avec et sans échec, et pour être complet, nous le comparons également avec Jolteon avec et sans échec.
La figure 7 ci-dessous montre le cas sans échec, et bien que le pipelining et la réputation du leader puissent réduire la latence individuellement, leur combinaison permet d'obtenir la meilleure latence.
Quant à Jolteon, il ne peut pas évoluer à plus de 20 validateurs, et même s'il s'exécute sur Quorum Store, il ne peut atteindre qu'environ la moitié du débit de Bullshark/Shoal, ce qui supprime le goulot d'étranglement de la propagation des données.
Les résultats montrent que Shoal améliore considérablement la latence de Bullshark. Quant à Jolteon, il est important de noter que même si nous n'avons mesuré que la latence de consensus. Étant donné que Jolteon ne peut pas s'exécuter de manière native sur un DAG, il nécessite une latence supplémentaire pour découpler la propagation des données, ce que nous n'avons pas mesuré. Par conséquent, sous une charge élevée, Shoal devrait correspondre à la latence de bout en bout de Jolteon.
Figure 7 : Débit et latence sans défaillance, Shoal PL et Shaol LR ne prennent en charge que le pipelining et la réputation de leader, respectivement.
La figure 8 ci-dessous montre un cas d'échec avec 50 validateurs, où le mécanisme de réputation du leader améliore considérablement la latence en réduisant la probabilité qu'un validateur défaillant soit élu en tant que leader. Notez qu'avec 16 échecs sur 50, la latence de Shoal était inférieure de 65 % à celle de Baseline Bullshark.