Cadre Shoal : comment Goutte la latence de Bullshark d'Aptos

Aptos Labs a résolu deux problèmes d'ouverture importants dans le DAG BFT, ce qui a considérablement goutte la latence, et a éliminé pour la première fois la nécessité de délais 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 sans faute et de 80 % en cas de faute.

Shoal est un cadre qui améliore tout protocole de consensus basé sur Narwhal ( comme DAG-Rider, Tusk, Bullshark ) grâce à un traitement par pipeline et un mécanisme de réputation des leaders. Le pipeline réduit la latence de tri DAG en introduisant un point d'ancrage à chaque tour, tandis que la réputation des leaders améliore encore le problème de latence en s'assurant que le point d'ancrage est associé au nœud de validation le plus rapide. De plus, la réputation des leaders 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 ce que nous appelons la propriété de réponse universelle, qui contient généralement la réponse optimiste requise.

Notre technologie est très simple, elle consiste à exécuter plusieurs instances du protocole sous-jacent en séquence, une après l'autre. Ainsi, lorsque nous instancions avec Bullshark, nous obtenons un groupe de "requins" qui participent à une course de relais.

motivation

Lors de la recherche de hautes performances pour les réseaux blockchain, l'accent a toujours été mis sur la Goutte de la complexité de communication. Cependant, cette approche n'a pas conduit à une augmentation significative du débit. Par exemple, Hotstuff, qui a été implémenté dans les premières versions de Diem, n'a réalisé que 3500 TPS, bien en dessous de notre objectif de plus de 100 000 TPS.

Mais 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 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 centrale, proposant une architecture où tous les validateurs propagent simultanément les données, tandis que le composant de consensus ne commande qu'une petite quantité de métadonnées. Le document Narwhal a rapporté un débit de 160 000 TPS.

Dans un article précédent, nous avons présenté Quorum Store. Notre implémentation de Narwhal sépare la propagation des données du consensus, et comment nous l'utilisons 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 le changement de vue de style PBFT, capable de réduire la latence de Hotstuff de 33 %. Cependant, il est clair que les protocoles de consensus basés sur un leader ne peuvent pas tirer pleinement parti du potentiel de débit de Narwhal. Bien que la propagation des données soit séparée du consensus, avec une augmentation du débit, le leader de Hotstuff/Jolteon reste limité.

Ainsi, nous avons décidé de déployer Bullshark sur le Narwhal DAG, qui est un protocole de consensus sans coût de communication. Malheureusement, par rapport à Jolteon, la structure DAG supportant Bullshark avec un haut débit entraîne un coût de latence de 50 %.

Cet article présentera comment Shoal parvient à Goutte la latence de Bullshark.

contexte DAG-BFT

Commençons par comprendre le contexte pertinent. Pour une description détaillée de Narwhal et Bullshark, veuillez consulter l'article DAG meets BFT.

Chaque sommet dans le DAG de Narwhal 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'asynchronicité du réseau, différents validateurs peuvent observer différentes vues locales du DAG à tout moment.

Une caractéristique clé du DAG est qu'elle n'est pas ambiguë : si deux nœuds de validation ont le même sommet v dans leur vue locale du DAG, alors ils ont exactement la même histoire causale de v.

ordre complet

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 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 ont la structure suivante :

1. Point d'ancrage prévu : après quelques tours, (, comme dans deux tours de Bullshark, ), il y aura un leader prédéterminé, le sommet du leader est appelé point d'ancrage;

2. Point d'ancrage de tri : les validateurs décident de manière indépendante mais déterministe de l'ordre des points d'ancrage à inclure et de ceux à sauter ;

3. historique de causalité trié : les validateurs traitent individuellement la liste des points d'ancrage ordonnés et, pour chaque point d'ancrage, trient tous les sommets précédemment non ordonné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 d'ancrage ordonnée, de sorte que toutes les listes partagent le même préfixe. Dans Shoal, nous faisons les observations suivantes sur tous les protocoles susmentionnés :

Tous les validateurs acceptent 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 la version synchronisée la plus pratique 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 ronde paire a un point d'ancrage, et chaque sommet de ronde impaire est interprété comme un vote. Dans les cas courants, il faut deux rondes de DAG pour ordonner les points d'ancrage, cependant, les sommets dans l'histoire causale de l'anchor nécessitent plus de rondes pour attendre que l'anchor soit trié. Dans les cas courants, les sommets de la ronde impaire nécessitent trois rondes, tandis que les sommets non ancrés de la ronde paire nécessitent quatre rondes.

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 suffisamment rapidement le point d'ancrage, il est impossible de trier le point d'ancrage (, ce qui entraîne son omission ). Par conséquent, tous les sommets non triés des tours précédents doivent attendre que le prochain point d'ancrage soit trié. Cela va considérablement Goutte les performances du réseau de réplication géographique, surtout parce que le délai d'attente Bullshark est utilisé 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) grâce à un pipeline, permettant 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 un mécanisme de réputation de leader à coût zéro dans le DAG, ce qui favorise la sélection des leaders rapides.

défi

Dans le contexte du protocole DAG, le pipeline et la réputation du leader sont considérés comme des problèmes difficiles, pour les raisons suivantes :

1. Les tentatives de traitement en ligne de production précédentes de modifier la logique centrale de Bullshark semblaient fondamentalement impossibles.

2. La réputation des leaders introduite dans DiemBFT et officialisée dans Carousel est l'idée de choisir dynamiquement les futurs leaders dans Bullshark en fonction des performances passées des validateurs ( des ancres ). Bien que les divergences sur l'identité des leaders ne violent pas la sécurité de ces protocoles, dans Bullshark, cela pourrait 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 cycle est nécessaire pour résoudre le consensus, et que les validateurs doivent s'accorder sur l'historique ordonné pour choisir les futures ancres.

En tant que preuve de la difficulté des problèmes, 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, comme le dit le proverbe, la solution se cache dans la simplicité.

Dans Shoal, nous comptons sur la capacité d'exécuter des calculs locaux sur le DAG et réalisons la capacité de sauvegarder et de réinterpréter les informations des tours précédents. Grâce à la perception 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, rendant ainsi ( le premier point d'ancrage ordonné comme point de commutation des instances, et ) l'historique causal des points d'ancrage utilisé pour calculer la réputation des leaders.

( traitement en ligne

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

Au départ, Shoal a lancé le premier instance de Bullshark lors du premier tour du DAG et l'a exécuté 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 un ancre à chaque tour. Les points d'ancrage de la première ronde sont triés par le premier instance. Ensuite, Shoal commence une nouvelle instance au début de la deuxième ronde, qui a elle-même un point d'ancrage, ce ancre étant trié par cette instance, puis une autre nouvelle instance commande un point d'ancrage lors de la troisième ronde, puis le processus continue.

![Explication détaillée du cadre Shoal : comment réduire la latence de Bullshark sur Aptos ?])https://img-cdn.gateio.im/webp-social/moments-0b0928cb6240e994c1514c75e080a4b2.webp###

( réputation des leaders

Lorsqu'on saute des points d'ancrage pendant le tri de Bullshark, la latence augmente. Dans ce cas, la technique de traitement par pipeline est impuissante, car un nouvel instance ne peut pas être lancé avant que l'instance précédente ne commande le point d'ancrage. Shoal s'assure qu'il est moins probable que le leader correspondant pour traiter les points d'ancrage manquants soit choisi à l'avenir en attribuant un score à chaque nœud de validation basé sur l'historique récent des activités de chaque nœud de validation grâce à un mécanisme de réputation. Les validateurs qui répondent et participent au protocole recevront un score élevé, sinon, les nœuds de validation se verront attribuer un score bas, car ils peuvent échouer, ê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 des scores plus élevés. Pour que les validateurs parviennent à un consensus sur le nouveau mappage, ils doivent parvenir à un consensus sur les scores, permettant ainsi d'atteindre un consensus sur l'historique utilisé pour dériver les scores.

Dans Shoal, la pipeline 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, le validateur n'a qu'à calculer une nouvelle carte F' à partir de la r+1ème ronde en fonction de l'historique causal des points d'ancrage ordonnés dans la rème ronde. Ensuite, les nœuds de validation commencent à utiliser la fonction de sélection de points d'ancrage mise à jour F' pour exécuter une nouvelle instance de Bullshark à partir de la r+1ème ronde.

![Explication détaillée du cadre Shoal : Comment réduire la latence de Bullshark sur Aptos ?])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp###

( n'a plus de délai

Le dépassement de délai joue un rôle crucial dans toutes les implémentations BFT déterministes basées sur un leader. Cependant, la complexité qu'elles 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'observation.

Le dépassement de délai augmentera également significativement la latence, car il est très important de les configurer correctement et nécessite souvent des ajustements dynamiques, car cela dépend fortement de l'environnement ) réseau ###. Avant de passer au leader suivant, le protocole paiera une pénalité complète de latence pour le leader défaillant. Par conséquent, les réglages de délai ne doivent pas être trop conservateurs, mais si le temps de dépassement est trop court, le protocole peut sauter de bons leaders. Par exemple, nous avons observé que, dans des situations de forte charge, Jolt.