Analyse du cadre Shoal : Goutte significative de la latence de Bullshark sur Aptos

Aptos Labs a récemment résolu deux problèmes clés dans le DAG BFT, ce qui a considérablement goutte la latence, et a éliminé pour la première fois le besoin de délais dans les protocoles en temps réel déterministes. Dans l'ensemble, dans des conditions sans faute, la latence de Bullshark s'est améliorée de 40 %, et dans des conditions de faute, elle s'est améliorée de 80 %.

Shoal est un cadre qui améliore le protocole de consensus basé sur Narwhal ( grâce à des mécanismes de pipeline et de réputation des leaders, comme DAG-Rider, Tusk, Bullshark ). Le pipeline réduit la latence de tri des DAG en introduisant des points d'ancrage à chaque tour, et la réputation des leaders améliore encore la latence en s'assurant que les points d'ancrage sont associés aux nœuds de validation les plus rapides. De plus, la réputation des leaders permet à Shoal de tirer parti de la construction de DAG asynchrone pour éliminer les délais dans tous les scénarios. Cela confère à Shoal une réactivité universelle, incluant la réactivité optimiste généralement requise.

Cette technologie est très simple, impliquant l'exécution séquentielle de plusieurs instances du protocole sous-jacent. Lors de l'instanciation de Bullshark, cela équivaut à un groupe de "requins" participant à une course de relais.

Contexte et motivation

Dans la quête d'une haute performance des réseaux blockchain, la réduction de la complexité de communication a toujours été un point focal. Cependant, cette approche n'a pas apporté d'améliorations significatives du débit. Par exemple, le Hotstuff implémenté dans le premier Diem n'a atteint que 3500 TPS, bien en dessous de l'objectif de 100 000+ TPS.

La récente percée provient de la prise de conscience que la propagation des données est le principal goulot d'étranglement basé sur le protocole des leaders, et 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, proposant une architecture où tous les validateurs propagent simultanément les données, et le composant de consensus ne classe qu'une petite quantité de métadonnées. Le document sur Narwhal rapporte un débit atteignant 160 000 TPS.

Aptos a précédemment introduit Quorum Store, c'est-à-dire l'implémentation de Narwhal, qui sépare la propagation des données et le consensus, afin d'étendre le protocole de consensus Jolteon actuel. Jolteon combine le chemin rapide linéaire de Tendermint et le changement de vue de style PBFT, ce qui peut réduire la latence de Hotstuff de 33 %. Cependant, les protocoles de consensus basés sur le leader ne peuvent pas exploiter pleinement le potentiel de débit de Narwhal.

Ainsi, Aptos a décidé de déployer Bullshark, un protocole de consensus sans frais de communication, sur le DAG Narwhal. Cependant, par rapport à Jolteon, la structure DAG soutenant Bullshark entraîne un coût de latence de 50 %.

Le cadre Shoal vise à réduire considérablement la latence de Bullshark.

Contexte DAG-BFT

Dans le DAG Narwhal, chaque sommet est associé à un tour. Pour entrer dans le tour r, les validateurs doivent d'abord obtenir n-f sommets du tour r-1. Chaque validateur peut diffuser un sommet par tour, et chaque sommet doit référencer au moins n-f sommets du tour précédent. En raison de l'asynchronicité du réseau, différents validateurs peuvent observer à tout moment des vues locales différentes du DAG.

Une propriété clé du DAG est l'absence d'ambiguïté : si deux nœuds de validation ont le même sommet v dans leur vue locale du DAG, alors ils ont une histoire causale de v complètement identique.

Ordre de tri

Il est possible d'atteindre un consensus sur l'ordre total de tous les sommets dans le DAG sans frais de communication supplémentaires. Pour ce faire, les validateurs dans DAG-Rider, Tusk et Bullshark interprètent la structure DAG comme un protocole de consensus, où les sommets représentent des propositions et les arêtes représentent des votes.

Tous les protocoles de consensus basés sur Narwhal ont la structure suivante :

1. Point d'ancrage prévu : tous les quelques tours, il y a un leader prédéterminé, dont le sommet est appelé point d'ancrage.

2. Points d'ancrage de tri : les validateurs décident de manière indépendante mais déterministe quels points d'ancrage trier et lesquels sauter.

3. Historique causal trié : les validateurs traitent successivement la liste d'ancrage ordonnée, en triant les sommets désordonnés précédents dans l'historique causal de chaque ancrage.

La clé de la sécurité est de s'assurer qu'à l'étape (2), toutes les listes de points d'ancrage ordonnés créées par les nœuds de validation honnêtes partagent le même préfixe. Shoal a observé : tous les validateurs s'accordent sur le premier point d'ancrage ordonné.

Bullshark latence

La latence de Bullshark dépend du nombre de tours entre les points d'ancrage ordonnés dans le DAG. Bien que certaines versions synchronisées de Bullshark aient une latence meilleure que les versions asynchrones, elles restent loin d'être optimales.

Il existe principalement deux problèmes :

1. Latence moyenne des blocs : Dans des conditions normales, les sommets impairs nécessitent trois tours, tandis que les sommets non ancrés pairs nécessitent quatre tours pour être triés.

2. Situation de panne latence : Si un leader d'un tour donné ne parvient pas à diffuser à temps le point d'ancrage, ce qui entraîne le saut du point d'ancrage sans ordre, les sommets non triés des tours précédents doivent attendre le tri du prochain point d'ancrage. Cela Goutte considérablement les performances du réseau de réplication géographique.

Cadre Shoal

Shoal améliore Bullshark( ou tout protocole BFT basé sur Narwhal) via un pipeline, permettant à chaque tour d'avoir un point d'ancrage, 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 coût dans le DAG, favorisant le choix de leaders rapides.

défi

Dans le contexte du protocole DAG, la pipeline et la réputation des leaders sont considérées comme des problèmes difficiles:

1. Les précédentes tentatives de modification de la logique principale de Bullshark dans la chaîne de production semblent en réalité impossibles.

2. La réputation des leaders est introduite dans DiemBFT et formalisée dans Carousel, sélectionnant dynamiquement les futurs leaders en fonction des performances passées des validateurs (Point d'ancrage dans Bullshark ). Bien que les divergences d'identité des leaders ne violent pas la sécurité, elles peuvent conduire à un ordonnancement complètement différent dans Bullshark.

Ces défis ont conduit à ce que les implémentations Bullshark dans l'environnement de production actuel ne prennent pas en charge ces fonctionnalités.

protocole

Shoal s'appuie sur la capacité d'exécuter des calculs locaux sur le DAG, réalisant ainsi la capacité de sauvegarder et de réinterpréter les informations des premiers tours. Basé sur l'insight selon lequel tous les validateurs s'accordent sur le premier point d'ancrage ordonné, Shoal combine séquentiellement plusieurs instances de Bullshark pour un traitement en pipeline, permettant ainsi :

1. Le premier point d'ancrage ordonné est le point de commutation de l'instance.
2. L'histoire causale des points d'ancrage est utilisée pour calculer la réputation des leaders.

chaîne de production

V qui associe les tours aux leaders. Shoal exécute successivement des instances de Bullshark, chaque instance ayant son point d'ancrage déterminé à l'avance par le mappage F. Chaque instance ordonne un point d'ancrage, déclenchant le passage à l'instance suivante.

Shoal a initialement lancé le premier exemple de Bullshark lors du premier tour de DAG, fonctionnant jusqu'à la détermination du premier point d'ancrage ordonné ( supposé au tour r ). Tous les validateurs ont accepté ce point d'ancrage, permettant ainsi de réinterpréter le DAG de manière déterministe à partir du tour r+1. Shoal lance un nouvel exemple de Bullshark au tour r+1.

Idéalement, cela permet à Shoal de trier un point d'ancrage par tour. Le premier point d'ancrage est trié par la première instance, puis Shoal commence une nouvelle instance au début du deuxième tour, triant le point d'ancrage de ce tour, et ainsi de suite.

Réputation des leaders

Lorsque le processus de tri de Bullshark saute des points d'ancrage, la latence augmente. Dans ce cas, la technologie de pipeline est impuissante, car il n'est pas possible de démarrer une nouvelle instance avant que le point d'ancrage de l'instance précédente ne soit trié. Shoal attribue un score à chaque nœud de validation via un mécanisme de réputation, garantissant qu'un leader lent correspondant est moins susceptible d'être choisi à l'avenir en fonction de l'historique des activités récentes. Les validateurs qui répondent et participent au protocole obtiennent un score élevé, sinon un score bas leur est attribué.

À chaque mise à jour des scores, recalculer de manière déterministe le mapping prédéfini F de l'itération au leader, en faveur des leaders à score élevé. Pour que les validateurs parviennent à un consensus sur le nouveau mapping, ils doivent parvenir à un consensus sur les scores, afin de parvenir à un consensus sur l'historique utilisé pour dériver les scores.

Dans Shoal, la chaîne de blocs et la réputation des leaders se combinent naturellement, car elles utilisent toutes deux la même technologie de base : réinterpréter le DAG après avoir atteint un consensus sur le premier point d'ancrage ordonné.

La seule différence est qu'après le point d'ancrage de tri de la r-ième ronde, les validateurs ne calculent la nouvelle cartographie F' qu'à partir de la r+1-ième ronde, en se basant uniquement sur l'historique causal des points d'ancrage ordonnés de la r-ième ronde. Ensuite, les nœuds de validation commencent à utiliser la fonction de sélection de point d'ancrage mise à jour F' pour exécuter la nouvelle instance de Bullshark à partir de la r+1-ième ronde.

Éliminer le dépassement de délai

Le dépassement de délai joue un rôle clé dans toutes les implementations BFT déterministes basées sur un leader. Cependant, la complexité qu'ils introduisent augmente le nombre d'états internes à gérer et à observer, ce qui accroît la complexité du débogage et nécessite davantage de techniques d'observation.

Le dépassement de délai augmente également significativement la latence, car il est important de configurer correctement le délai, qui doit souvent être ajusté dynamiquement, dépendant fortement de l'environnement ( réseau ). Avant de passer au prochain leader, le protocole paiera la pénalité complète du délai pour le leader en panne. Par conséquent, les paramètres de délai ne doivent pas être trop conservateurs, mais s'ils sont trop courts, le protocole pourrait passer à un bon leader.

Malheureusement, les protocoles basés sur les leaders ( tels que Hotstuff et Jolteon) nécessitent essentiellement des Goutte pour s'assurer que le protocole progresse chaque fois qu'un leader échoue. Sans Goutte, même un leader en panne peut potentiellement arrêter le protocole indéfiniment. Étant donné qu'il est impossible de distinguer un leader défaillant d'un leader lent pendant l'asynchrone, les Goutte peuvent entraîner un échange de tous les leaders par les nœuds de validation sans activité de consensus.

Dans Bullshark, le temps d'attente est utilisé pour la construction du DAG, afin de s'assurer que pendant la synchronisation, les leaders honnêtes ajoutent des points d'ancrage au DAG suffisamment rapidement pour le tri.

Shoal a observé que la construction DAG fournit une "horloge" pour estimer la vitesse du réseau. En l'absence de pauses, tant que n-f validateurs honnêtes continuent d'ajouter des sommets au DAG, les tours continueront d'avancer. Bien que Bullshark puisse ne pas être capable de trier ( à la vitesse du réseau en raison de problèmes de leadership ), le DAG continue de croître à la vitesse du réseau, même si certains leaders ont des problèmes ou si le réseau est asynchrone. Finalement, lorsque des leaders sans défaut diffusent suffisamment rapidement des points d'ancrage, l'ensemble de l'histoire causale des points d'ancrage sera trié.

Dans Shoal, éviter les délais est étroitement lié à la réputation des leaders. Attendre de manière répétée des leaders lents augmente la latence, et le mécanisme de réputation des leaders exclut les validateurs lents d'être choisis comme leaders. De cette manière, le système utilise des nœuds de validation rapides pour fonctionner à la vitesse du réseau dans tous les scénarios réels.

Il est important de noter que les résultats d'impossibilité de FLP indiquent qu'aucun protocole de consensus déterministe ne peut éviter les latences. Shoal ne peut pas contourner ce résultat, car il existe un calendrier d'événements théoriquement antagonistes qui peut empêcher tous les ancres d'être ordonnées. En revanche, après un nombre configurable d'ancres sautées, Shoal reviendra à une latence. En pratique, cette situation est extrêmement peu probable.

Réactivité Générale

Le document sur Hotstuff popularise le concept de réponse optimiste, bien qu'il ne soit pas formellement défini, cela signifie intuitivement que le protocole peut fonctionner à la vitesse du réseau sous un bon scénario avec un leader rapide et un réseau synchronisé (.

Shoal offre de meilleures caractéristiques, appelées réactivité universelle. Plus précisément, par rapport à Hotstuff, même si le leader échoue pendant un nombre continu de tours configurables ou si le réseau connaît des périodes asynchrones, Shoal continuera à fonctionner à la vitesse du réseau.

La réactivité générale offre de bien meilleures garanties de progression pendant les périodes asynchrones et en cas de défaillance du leader. Pendant la synchronisation avec un leader lent, ces propriétés ne peuvent pas être comparées, car cela dépend de la lenteur du leader. Cependant, étant donné la réputation du leader, les leaders lents dans Shoal devraient être rares.

Évaluation

Aptos a implémenté Bullshark et Shoal sur Quorum Store grâce à Narwhal. Voici quelques points forts de l'évaluation :

Tout d'abord, pour la performance