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 pratiques déterministes. 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 panne.

Shoal est un cadre qui améliore le protocole de consensus basé sur Narwhal ( grâce à des pipelines et à la réputation des leaders, comme DAG-Rider, Tusk, Bullshark ). Le pipeline réduit le délai de tri DAG en introduisant des points d'ancrage à chaque tour, tandis que la réputation des leaders améliore davantage le problème de délai 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'exploiter une construction DAG asynchrone pour éliminer les délais dans tous les scénarios. Cela permet à Shoal de fournir des propriétés de réponse universelles, incluant les réponses optimistes généralement requises.

Cette technologie est très simple, impliquant l'exécution séquentielle de plusieurs instances du protocole sous-jacent. Ainsi, lorsqu'elle est instanciée avec Bullshark, on obtient un groupe de "requins" en relais.

Motivation

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

Récemment, la percée est venue de la compréhension 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 les données simultanément, les composants de consensus n'ordonnant qu'un petit nombre de métadonnées. Le document Narwhal rapporte un débit de 160 000 TPS.

Le Quorum Store présenté précédemment a réalisé une séparation de la diffusion des données et du consensus, afin d'élargir 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, réduisant le délai de Hotstuff de 33%. Cependant, 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 séparation de la diffusion des données et du consensus ait été effectuée, avec l'augmentation du débit, le leader de Hotstuff/Jolteon reste limité.

Ainsi, Bullshark, un protocole de consensus sans coût de communication, a été déployé sur le Narwhal DAG. Malheureusement, par rapport à Jolteon, la structure DAG prenant en charge un haut débit pour Bullshark entraîne un coût de latence de 50 %.

Cet article présente comment Shoal réduit considérablement le délai de Bullshark.

Contexte DAG-BFT

Dans le DAG Narwhal, chaque sommet est associé à un tour. À l'entrée du 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'asynchronisme du réseau, différents validateurs peuvent observer à tout moment des vues locales différentes du DAG.

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

Ordre total

Il est possible d'atteindre un consensus sur l'ordre total de tous les sommets dans un DAG sans frais de communication supplémentaires. Pour cela, les validateurs de 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 dans la structure DAG soit différente, tous les protocoles de consensus existants basés sur Narwhal partagent la structure suivante :

1. Point d'ancrage prévu : chaque quelques tours, il y a un leader prédéfini, 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 commander ou sauter.

3. Histoire causale ordonnée : les validateurs traitent un par un la liste des points d'ancrage ordonnés, en triant les sommets désordonnés précédents dans l'histoire causale de chaque point d'ancrage.

La clé de la sécurité est de s'assurer que dans l'étape (2), toutes les listes d'ancrage ordonnées créées par les nœuds de validation honnêtes partagent le même préfixe. Dans Shoal, nous faisons les observations suivantes sur tous ces protocoles:

Tous les validateurs s'accordent sur le premier point d'ancrage ordonné.

Bullshark retard

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 que la version asynchrone, elle n'est pas optimale.

Question 1 : Délai moyen de bloc. Dans Bullshark, chaque ronde paire a un point d'ancrage, tandis que les sommets des rondes impaires sont interprétés comme des votes. En général, deux rondes de DAG sont nécessaires pour ordonner les points d'ancrage, cependant, les sommets dans l'historique causale des points d'ancrage nécessitent plus de rondes pour que les points d'ancrage soient triés. En général, les sommets des rondes impaires nécessitent trois rondes, tandis que les sommets non ancrés des rondes paires nécessitent quatre rondes.

Problème 2 : Retard des cas de défaillance. L'analyse de retard ci-dessus s'applique en l'absence de défaillance. D'autre part, si un leader d'une rondes ne parvient pas à diffuser suffisamment rapidement le point d'ancrage, il n'est pas possible de trier le point d'ancrage ( et donc il est sauté ). 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, surtout parce que Bullshark utilise un temps d'attente pour le leader.

Cadre Shoal

Shoal a résolu ces deux problèmes de latence, en améliorant Bullshark( ou tout autre protocole BFT basé sur Narwhal) par le biais de pipelines, permettant d'avoir des points d'ancrage à chaque tour et 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 les leaders rapides.

Défi

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

1. Les tentatives précédentes de la chaîne de production de modifier la logique centrale de Bullshark semblent fondamentalement 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 dans l'ancre de Bullshark (. Bien qu'il existe des divergences sur l'identité des leaders qui ne compromettent pas la sécurité de ces protocoles, cela pourrait entraîner un ordre complètement différent dans Bullshark, ce qui soulève le cœur du problème : choisir dynamiquement et de manière déterministe les ancres de roue est nécessaire pour résoudre le consensus, les validateurs doivent parvenir à un accord sur l'historique ordonné pour sélectionner les futurs ancres.

Comme preuve de la difficulté des problèmes, l'implémentation de Bullshark ) n'inclut pas ces fonctionnalités, tout comme les implémentations actuellement en production (.

![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(

Accord

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

Dans Shoal, nous nous appuyons sur la capacité d'effectuer des calculs locaux sur le DAG pour conserver et réinterpréter les informations des tours précédents. Grâce à l'insight fondamental 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, rendant ) le premier point d'ancrage ordonné le point de commutation des instances, ( l'historique causale des points d'ancrage est utilisé pour calculer la réputation des leaders.

Chaîne de montage

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

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

Dans le meilleur des cas, cela permet à Shoal de commander un ancre à chaque tour. Les points d'ancrage du premier tour sont triés par le premier exemple. Ensuite, Shoal commence un nouvel exemple au deuxième tour, qui a lui-même un point d'ancrage, cette ancre étant triée par cet exemple. Puis, un autre nouvel exemple commande un point d'ancrage au troisième tour, et 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-859e732e16c3eee0e2c93422474debc2.webp(

Réputation des leaders

Lorsqu'on saute des points d'ancrage pendant le tri Bullshark, le retard augmente. Dans ce cas, la technique de pipeline est impuissante, car il est impossible de lancer une nouvelle instance avant que l'instance précédente n'ait commandé le point d'ancrage. Shoal garantit qu'il est peu probable que des leaders correspondants soient choisis à l'avenir pour traiter les points d'ancrage manquants en attribuant des scores en fonction de l'historique d'activité récent de chaque nœud de validation à l'aide d'un mécanisme de réputation. Les validateurs qui répondent et participent au protocole obtiendront des scores élevés, sinon, les nœuds de validation se verront attribuer des scores faibles, car ils peuvent échouer, être lents ou agir de manière malveillante.

Le concept est de recalculer de manière déterministe le mappage prédéfini F, qui favorise les leaders avec un meilleur score, à chaque mise à jour de score. Pour que les validateurs parviennent à un consensus sur le nouveau mappage, ils doivent s'accorder sur le score, atteignant ainsi un consensus sur l'historique utilisé pour dériver le score.

Dans Shoal, les pipelines et la réputation des leaders peuvent se combiner naturellement, car ils utilisent tous 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 le tri des points d'ancrage lors de la r-ième ronde, les validateurs n'ont qu'à calculer la nouvelle fonction de mappage F' à partir de la ronde r+1 en se basant sur l'historique causal des points d'ancrage ordonnés de la ronde r. Ensuite, les nœuds de validation utilisent la fonction de sélection de points d'ancrage mise à jour F' pour exécuter une nouvelle instance de Bullshark à partir de la ronde r+1.

![Explication détaillée du cadre Shoal : Comment réduire le délai de Bullshark sur Aptos ?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Plus de délais

Le dépassement de temps joue un rôle crucial dans toutes les implémentations 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 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, ce qui nécessite souvent un ajustement dynamique, car cela dépend fortement de l'environnement ) réseau (. Avant de passer au leader suivant, le protocole paiera la pénalité de délai de dépassement complète pour un leader défaillant. Par conséquent, les paramètres de délai ne doivent pas être trop conservateurs, mais si le temps de dépassement est trop court, le protocole peut ignorer de bons leaders. Par exemple, nous avons observé que, dans des conditions de forte charge, les leaders dans Jolteon/Hotstuff sont submergés, et le délai de dépassement est déjà écoulé avant de pousser les progrès.

Malheureusement, les protocoles basés sur les leaders ) tels que Hotstuff et Jolteon( nécessitent essentiellement des délais d'attente pour garantir que le protocole progresse chaque fois qu'un leader échoue. En l'absence de délai d'attente, même un leader en panne pourrait arrêter le protocole indéfiniment. Comme il est impossible de distinguer un leader défaillant d'un leader lent pendant la période asynchrone, les délais d'attente peuvent amener les nœuds de validation à examiner tous les leaders sans une activité de consensus.

Dans Bullshark, le dépassement de temps est utilisé pour la construction du DAG, afin de garantir qu'un leader honnête ajoute les points d'ancrage au DAG pendant la synchronisation.