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 délais dans un protocole pratique déterministe. Dans l'ensemble, en cas de fonctionnement sans défaut, la latence de Bullshark a été améliorée de 40 %, et en cas de défaillance, elle a été améliorée de 80 %.

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 ). Les pipelines réduisent la latence de tri DAG en introduisant des points d'ancrage à chaque tour, tandis que 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 d'exploiter la construction de DAG asynchrone pour éliminer les délais dans tous les scénarios. Cela permet à Shoal d'offrir ce que nous appelons l'attribut de réponse universelle, qui contient la réponse optimiste généralement requise.

Notre technologie est très simple, impliquant plusieurs instances des protocoles sous-jacents exécutées en séquence. Ainsi, lorsque nous instancions avec Bullshark, nous obtenons un groupe de "requins" participant à une course de relais.

Motivation

Dans la recherche de hautes performances pour les 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, le 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.

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

Auparavant, nous avons introduit Quorum Store, c'est-à-dire comment notre implémentation Narwhal sépare la diffusion des données et le consensus, et 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 le changement 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 pas tirer pleinement parti du potentiel de débit de Narwhal. Bien que la diffusion des données soit séparée du consensus, à mesure que le débit augmente, le leader de Hotstuff/Jolteon reste limité.

Ainsi, nous avons décidé de déployer Bullshark, un protocole de consensus sans frais de communication, sur le DAG Narwhal. Malheureusement, la structure DAG qui soutient 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

Chaque sommet dans le DAG Narwhal est associé à un tour. Pour entrer dans le tour r, un validateurs 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 à 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 exactement la même histoire causale de v.

Permutation totale

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 : tous les quelques tours ( comme dans Bullshark, il y a un leader prédéterminé tous les deux tours ), 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 trier et lesquels sauter ;

3. tri de l'historique causale : les validateurs traitent un par un la liste des points d'ancrage ordonnés, pour chaque point d'ancrage, en triant tous les sommets précédemment non ordonnés dans son historique causale selon certaines règles déterministes.

La clé pour garantir 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. Dans Shoal, nous faisons les observations suivantes sur tous les protocoles susmentionnés:

Tous les validateurs conviennent 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 avec 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 un point d'ancrage, et chaque sommet du tour impair est interprété comme un vote. Dans les cas courants, deux tours de DAG sont nécessaires pour trier les points d'ancrage, cependant, les sommets dans l'historique causale des points d'ancrage nécessitent plus de tours pour attendre que les points d'ancrage soient triés. Dans les 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 défaillance. L'analyse de latence ci-dessus s'applique aux cas sans défaillance. D'autre part, si le leader d'un tour ne parvient pas à diffuser suffisamment rapidement le point d'ancrage, il ne sera pas possible de trier le point d'ancrage (, ce qui sera donc ignoré ). 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 réduit considérablement les performances du réseau de réplication géographique, surtout parce que Bullshark utilise des délais 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 sans coût dans le DAG, 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 anciennes chaînes de production ont tenté de modifier la logique principale de Bullshark, mais cela semble essentiellement impossible.

2. La réputation des leaders est introduite dans DiemBFT et formalisée dans Carousel, en sélectionnant dynamiquement les futurs leaders selon les performances passées des validateurs, l'idée étant de faire des points d'ancrage dans Bullshark (. Bien que des divergences sur l'identité des leaders ne compromettent pas la sécurité de ces protocoles, dans Bullshark, cela peut entraîner un classement complètement différent, ce qui soulève la question centrale : il est nécessaire de sélectionner dynamiquement et de manière déterministe les ancres de rotation pour résoudre le consensus, et les validateurs doivent parvenir à un consensus sur l'historique ordonné pour choisir les futurs points d'ancrage.

En tant que preuve de la difficulté des problèmes, nous avons remarqué que l'implémentation de Bullshark, y compris l'implémentation actuelle dans l'environnement de production, ne prend pas en charge ces fonctionnalités.

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

Protocole

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

Dans Shoal, nous nous appuyons sur la capacité d'exécuter des calculs locaux sur le DAG et avons mis en œuvre la capacité de conserver et de réinterpréter les informations des premiers tours. Grâce à la perception centrale selon laquelle 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 en sorte que ) le premier point d'ancrage ordonné soit le point de basculement des instances, ainsi que ( l'historique causal des points d'ancrage utilisé pour calculer la réputation des leaders.

Chaîne de production

Comme Bullshark, les validateurs parviennent a priori à un consensus sur les points d'ancrage potentiels, c'est-à-dire qu'il existe un mappage connu F : R -\u003e V qui associe les tours aux leaders. Shoal exécute une instance de Bullshark à la fois, de sorte que pour chaque instance, le point d'ancrage est prédéfini par le mappage F. Chaque instance trie un point d'ancrage, ce qui déclenche le passage à l'instance suivante.

Au départ, Shoal a lancé la première instance de Bullshark lors du premier tour de 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 trier un point d'ancrage à chaque tour. Le point d'ancrage du premier tour est trié par la première instance. Ensuite, Shoal commence une nouvelle instance au deuxième tour, qui a elle-même un point d'ancrage, ce point d'ancrage étant trié par cette instance, puis une autre nouvelle instance trie le point d'ancrage au troisième tour, et le processus se poursuit.

![Interprétation détaillée du cadre Shoal : comment réduire la latence de Bullshark sur Aptos ?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Réputation des dirigeants

Lors du saut de points d'ancrage pendant le tri Bullshark, la latence augmente. Dans ce cas, la technique de pipeline est impuissante, car il n'est pas possible de démarrer une nouvelle instance avant le tri du point d'ancrage de l'instance précédente. Shoal assure qu'il est peu probable que le leader correspondant soit choisi à l'avenir pour traiter les points d'ancrage manquants en attribuant un score à chaque nœud de validation en fonction de l'historique de l'activité récente de chaque nœud de validation 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 faible, car ils peuvent être en panne, lents ou malveillants.

Son principe est de recalculer de manière déterministe la cartographie prédéfinie F du tour au leader à chaque mise à jour du score, en faveur des leaders ayant des scores plus élevés. Afin que les validateurs parviennent à un consensus sur la nouvelle cartographie, ils doivent parvenir à un consensus sur le score, afin d'atteindre 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 convenu du 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-ème ronde, le validateur n'a qu'à calculer un nouveau mappage F' à partir de la r+1-ème ronde en se basant sur l'historique causale des points d'ancrage ordonnés de la r-ème ronde. Ensuite, le nœud de validation commence à exécuter 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'.

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

Plus de délais

Le dépassement de délai joue un rôle crucial 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 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 nécessite souvent des ajustements dynamiques, car cela dépend fortement de l'environnement ) réseau (. Avant de passer au leader suivant, le protocole paie la pénalité de dépassement de délai complète pour le leader défaillant. Par conséquent,