Explication du cadre Shoal : comment réduire la latence de Bullshark sur Aptos

Aperçu

Aptos labs a résolu deux problèmes ouverts importants dans le DAG BFT, réduisant considérablement la latence et éliminant pour la première fois le besoin de pauses dans les protocoles déterministes réels. Dans l'ensemble, la latence de Bullshark a été améliorée de 40 % en cas de fonctionnement normal et de 80 % en cas de défaillance.

Shoal est un cadre qui améliore tout protocole de consensus basé sur Narwhal ( comme DAG-Rider, Tusk, Bullshark ) grâce à une pipeline et à la réputation des leaders. La pipeline réduit la latence de tri DAG en introduisant un point d'ancrage à chaque ronde, et la réputation des leaders améliore encore le problème de 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 d'utiliser des constructions DAG asynchrones pour éliminer les délais dans tous les scénarios. Cela permet à Shoal de fournir ce que nous appelons des propriétés de réponse universelle, qui contiennent des réponses optimistes généralement nécessaires.

Cette technologie est très simple, impliquant l'exécution séquentielle de plusieurs instances du protocole sous-jacent. Ainsi, lorsque nous l'instancions avec Bullshark, nous obtenons un groupe de "requins" participant à une course de relais.

Motivation

Dans la quête d'une haute performance des réseaux blockchain, les gens se sont toujours concentrés sur la réduction de la complexité de communication. Cependant, cette approche n'a pas conduit à une augmentation significative du débit. Par exemple, le Hotstuff implémenté dans les premières versions de Diem n'a réalisé que 3500 TPS, bien en dessous de notre objectif de 100k+ TPS.

La récente percée provient de la reconnaissance que la propagation des données est le principal goulot d'étranglement des protocoles de leadership et peut bénéficier de la parallélisation. Le système Narwhal dissocie la propagation des données de la logique de consensus de base, proposant une architecture où tous les validateurs propagent les données simultanément, tandis que le composant de consensus ne commande qu'une petite quantité de métadonnées. Le document Narwhal rapporte un débit atteignant 160 000 TPS.

Nous avons précédemment présenté Quorum Store, notre implémentation Narwhal qui sépare la propagation des données et le consensus, ainsi que comment l'utiliser pour étendre le protocole de consensus actuel Jolteon. Jolteon est un protocole basé sur un leader, combinant le chemin rapide linéaire de Tendermint et les changements de vue de style PBFT, permettant de réduire la latence de Hotstuff de 33 %. Cependant, les protocoles de consensus basés sur un leader ne peuvent manifestement pas tirer pleinement parti du potentiel de débit de Narwhal. Bien que la séparation de la propagation des données et du consensus soit réalisée, avec l'augmentation du débit, le leader de Hotstuff/Jolteon reste limité.

Nous avons donc décidé de déployer Bullshark, un protocole de consensus sans coût de communication, sur le Narwhal DAG. Malheureusement, par rapport à Jolteon, la structure DAG qui prend en charge le haut débit de Bullshark entraîne un coût de latence de 50 %.

Cet article présente comment Shoal réduit considérablement la latence de Bullshark.

Contexte DAG-BFT

Dans le Narwhal DAG, chaque sommet est associé à un tour. Pour entrer dans le tour r, un validateur doit d'abord obtenir n-f sommets appartenant au 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'asynchronisme du réseau, différents validateurs peuvent observer à tout moment des vues locales différentes du DAG.

Une caractéristique clé du DAG est qu'elle est non ambiguë : 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.

Préface

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

Bien que la logique d'intersection des groupes sur la structure DAG soit différente, tous les protocoles de consensus basés sur Narwhal existants partagent la structure suivante :

1. Point d'ancrage prévu : toutes les quelques rondes (, comme dans Bullshark où deux rondes ) ont un leader prédéterminé, le sommet du leader 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 commander et lesquels sauter.

3. Historique de causalité ordonné : les validateurs traitent un par un une liste d'ancrages ordonnée, et pour chaque ancrage, ils trient tous les sommets précédemment désordonnés dans son historique de causalité selon certaines règles déterministes.

La clé pour garantir la sécurité est de s'assurer qu'à l'étape (2), tous les nœuds de validation honnêtes créent une liste de points d'ancrage ordonnée, et que toutes les listes partagent le même préfixe. Dans Shoal, nous faisons les observations suivantes sur tous les protocoles mentionnés ci-dessus :

Tous les validateurs ont convenu du 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 la version synchronisée de Bullshark soit plus pratique et ait une meilleure latence que la version asynchrone, elle est loin d'être optimale.

Question 1 : latence moyenne des blocs. Dans Bullshark, chaque round pair a un point d'ancrage, et les sommets des rounds impairs sont interprétés comme des votes. Dans des cas courants, il faut deux tours du DAG pour commander des points d'ancrage, cependant, les sommets dans l'historique causal de l'ancre nécessitent plus de tours pour attendre que l'ancre soit triée. Dans des cas courants, 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.

Problème 2 : latence des cas de panne. L'analyse de latence ci-dessus s'applique aux situations sans panne ; d'autre part, si le leader d'un tour ne parvient pas à diffuser les points d'ancrage suffisamment rapidement, il est impossible de trier les points d'ancrage (, donc ils sont sautés ), et tous les sommets non triés des tours précédents doivent attendre que le prochain point d'ancrage soit trié. Cela réduit considérablement les performances du réseau de réplication géographique, d'autant plus que Bullshark utilise un délai pour attendre le leader.

Cadre Shoal

Shoal a résolu ces deux problèmes de latence en renforçant Bullshark( ou tout autre protocole BFT basé sur Narwhal) par le biais de pipelines, permettant ainsi d'avoir un point d'ancrage à chaque tour et réduisant la latence de tous les sommets non ancrés dans le DAG à trois tours. Shoal a également introduit dans le DAG un mécanisme de réputation de leader à zéro coût, ce qui favorise le choix des leaders rapides.

Défi

Dans le contexte du protocole DAG, la réputation des pipelines et des leaders est considérée comme un problème difficile, pour les raisons suivantes:

1. Les chaînes de production précédentes ont essayé de modifier la logique centrale de Bullshark, mais cela semble en essence impossible.

2. La réputation du leader introduite dans DiemBFT et officialisée dans Carousel, est l'idée de sélectionner dynamiquement les futurs leaders en fonction des performances passées des validateurs dans ( Bullshark, les ancres de ). Bien que l'existence de divergences sur l'identité du leader ne contredise pas la sécurité de ces protocoles, dans Bullshark, cela peut conduire à un classement complètement différent, ce qui soulève le cœur du problème, à savoir que le choix dynamique et déterministe des ancres de rotation est nécessaire pour résoudre le consensus, et que les validateurs doivent parvenir à un accord sur l'historique ordonné pour choisir les futures ancres.

En tant que preuve de la difficulté du problème, nous notons que l'implémentation de Bullshark, y compris celle actuellement en production, ne prend pas en charge ces fonctionnalités.

Protocole

Malgré les défis mentionnés ci-dessus, la solution se cache dans la simplicité.

Dans Shoal, nous comptons sur la capacité d'effectuer des calculs locaux sur le DAG et avons réalisé la capacité de sauvegarder et de réinterpréter les informations des tours précédents. Avec la compréhension fondamentale que tous les validateurs s'accordent sur le premier point d'ancrage ordonné, Shoal combine séquentiellement plusieurs instances de Bullshark pour les traiter en pipeline, faisant de ( le premier point d'ancrage ordonné qui est le point de basculement des instances, ainsi que ) l'historique causale du point d'ancrage utilisé pour calculer la réputation des leaders.

Chaîne de production

V qui associe les tours aux leaders. Shoal exécute un à un des exemples de Bullshark, de sorte que pour chaque exemple, l'ancre est préalablement déterminée par le mappage F. Chaque exemple commande une ancre, ce qui déclenche le passage au prochain exemple.

Au départ, Shoal a lancé le premier instance de Bullshark lors du premier tour du DAG et l'a fait fonctionner jusqu'à ce que le premier point d'ancrage ordonné soit déterminé, par exemple au tour r. Tous les validateurs ont convenu de ce point d'ancrage. Par conséquent, tous les validateurs peuvent convenir de manière certaine de réinterpréter le DAG à partir du tour r+1. Shoal a simplement lancé une nouvelle instance de Bullshark au tour r+1.

Dans le meilleur des cas, cela permet à Shoal de commander une ancre à chaque tour. Les points d'ancrage de la première ronde sont triés par le premier exemple. Ensuite, Shoal commence un nouvel exemple au début de la deuxième ronde, qui a elle-même un point d'ancrage, cette ancre étant triée par cet exemple, puis un autre nouvel exemple commande un point d'ancrage lors de la troisième ronde, et le processus continue.

Réputation des leaders

Lorsqu'un point d'ancrage est sauté pendant le tri Bullshark, la latence augmente. Dans ce cas, la technologie de pipeline ne peut rien faire, car il est impossible de lancer une nouvelle instance avant que le point d'ancrage de l'instance précédente ne soit commandé. Shoal s'assure qu'il est peu probable que les leaders correspondants soient choisis à l'avenir pour traiter les points d'ancrage manquants en attribuant un score à chaque nœud de validation en fonction de l'historique de ses activités récentes grâce à un mécanisme de réputation. Les validateurs qui répondent et participent au protocole obtiendront un score élevé, sinon, les nœuds de validation se verront attribuer un score bas, car ils pourraient s'écraser, être lents ou malveillants.

Son principe est de recalculer de manière déterministe le mappage prédéfini F du tour au leader à chaque mise à jour du score, en faveur des leaders ayant un score plus élevé. Pour que les validateurs parviennent à un consensus sur le nouveau mappage, ils doivent parvenir à un consensus sur le score, atteignant ainsi un consensus sur l'histoire utilisée pour dériver le score.

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

En fait, la seule différence est qu'après avoir trié les points d'ancrage lors de la rème ronde, les validateurs n'ont qu'à calculer le nouveau mappage F' à partir de la r+1ème ronde en se basant sur l'historique causal des points d'ancrage ordonnés de la rème ronde. Ensuite, les nœuds de validation exécutent une nouvelle instance de Bullshark à partir de la r+1ème ronde en utilisant la fonction de sélection de points d'ancrage mise à jour F'.

Plus de temps d'attente

Le délai joue un rôle crucial dans toutes les implémentations BFT synchrones 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 complique le processus de débogage et nécessite davantage de techniques d'observabilité.

Le dépassement de délai augmentera également significativement la latence, car il est très important de les configurer correctement et qu'il est souvent nécessaire de les ajuster dynamiquement, car cela dépend fortement de l'environnement ( réseau ). Avant de passer au leader suivant, le protocole paiera la pénalité de latence complète pour le leader défaillant. Par conséquent, les paramètres de délai ne doivent pas être trop conservateurs, mais si le temps de délai est trop court, le protocole pourrait sauter de bons leaders. Par exemple, nous avons observé que, en cas de forte charge, les leaders dans Jolteon/Hotstuff étaient surchargés et que le délai avait expiré avant qu'ils n'avancent.

Malheureusement, les protocoles basés sur le leader ( tels que Hotstuff et Jolteon ) nécessitent essentiellement une latence pour garantir que le protocole progresse à chaque fois qu'un leader échoue. Sans latence, même un leader en échec peut