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 BFT DAG, 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 sans faille et de 80 % en cas de défaillance.

Shoal est un cadre qui renforce tout protocole de consensus basé sur Narwhal ( tel que DAG-Rider, Tusk, Bullshark ) par le biais de pipelines et de la réputation des leaders. Le pipeline réduit le délai de tri des DAG en introduisant un point d'ancrage à chaque tour, et la réputation des leaders améliore encore 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 des constructions DAG asynchrones pour éliminer les délais dans tous les scénarios. Cela permet à Shoal d'offrir ce que nous appelons des propriétés de réponse universelle, qui contiennent généralement les réponses optimistes nécessaires.

Cette technologie est très simple, elle implique d'exécuter plusieurs instances du protocole sous-jacent l'une après l'autre. Ainsi, lorsqu'elle est instanciée avec Bullshark, nous obtenons un groupe de "requins" en train de faire une course de relais.

Motivation

Lors de la recherche de performances élevées dans les 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, Hotstuff, mis en œuvre 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 réalisation 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 au cœur et propose 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.

Auparavant, nous avons présenté Quorum Store - Narwhal, qui permet de séparer la propagation des données et le consensus, ainsi que la façon de 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 le délai de Hotstuff de 33 %. Cependant, il est clair que les protocoles de consensus basés sur un leader ne peuvent pas pleinement tirer parti du potentiel de débit de Narwhal. Bien que la propagation des données soit séparée du consensus, à mesure que le débit augmente, le leader de Hotstuff/Jolteon reste limité.

Par conséquent, il a été décidé de déployer Bullshark, un protocole de consensus sans frais de communication, sur le DAG de Narwhal. Malheureusement, par rapport à Jolteon, la structure de 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 parvient à réduire considérablement le délai 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 validateurs 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 caractéristique clé du DAG 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 pour 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 ce faire, 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 de groupe sur une 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, il y aura 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 ignorer ;

3. Historique causal trié : les validateurs traitent un par un leur liste d'ancres ordonnées, et pour chaque ancre, ils trient tous les sommets désordonnés précédents dans leur historique causal selon certaines règles déterministes.

La clé de la satisfaction des exigences de 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, les observations suivantes peuvent être faites sur tous les protocoles mentionnés ci-dessus :

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

Bullshark Délai

Le délai 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 présente un meilleur délai que la version asynchrone, elle est loin d'être optimale.

Question 1 : Délai moyen des blocs. Dans Bullshark, chaque cycle pair a un point d'ancrage, et le sommet de chaque cycle impair est interprété comme un vote. Dans les cas courants, il faut deux cycles DAG pour commander les points d'ancrage, cependant, les sommets dans l'historique causale des points d'ancrage nécessitent plus de cycles pour attendre que les points d'ancrage soient triés. Dans les cas courants, les sommets dans les cycles impairs nécessitent trois cycles, tandis que les sommets non ancrés dans les cycles pairs nécessitent quatre cycles.

Problème 2 : Délai dans les cas de panne, l'analyse de délai ci-dessus s'applique aux cas sans panne. D'autre part, si le leader d'un tour ne parvient pas à diffuser les points d'ancrage assez rapidement, il ne sera pas possible de trier les points d'ancrage ( et donc ils seront sautés ). 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 un délai d'attente pour 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 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 nul dans le DAG, ce qui favorise le choix d'un leader rapide.

Défi

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

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

2. La réputation des leaders est introduite dans DiemBFT et formalisée dans Carousel, basée sur la performance passée des validateurs pour sélectionner dynamiquement les futurs leaders dans (Bullshark, l'idée des ancres de ). Bien qu'il n'y ait pas de violation de la sécurité dans ces protocoles en raison de divergences dans l'identité des leaders, dans Bullshark, cela peut entraîner des ordonnancements complètement différents, 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 consensus sur l'historique ordonné pour sélectionner les futures ancres.

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

Accord

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

Dans Shoal, il s'appuie sur la capacité à exécuter des calculs locaux sur le DAG et à sauvegarder et réinterpréter les informations des tours précédents. Grâce à la compréhension 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, ce qui fait que ( le premier point d'ancrage ordonné est le point de basculement des instances, et ) l'historique causal des points d'ancrage est utilisé pour calculer la réputation des leaders.

Ligne de production

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

Au début, Shoal a lancé le premier exemple de Bullshark lors de la première ronde du DAG et l'a exécuté jusqu'à ce que le premier point d'ancrage ordonné soit déterminé, par exemple, lors de la ronde 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 de la ronde r+1. Shoal a simplement lancé un nouvel exemple de Bullshark lors de la ronde r+1.

Dans le meilleur des cas, cela permet à Shoal de commander une ancre à chaque tour. Les points d'ancrage du premier tour sont triés par le premier exemple. Ensuite, Shoal commence un nouvel exemple au début du 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.

Réputation des leaders

Lorsqu'on saute des points d'ancrage pendant le tri Bullshark, le délai augmente. Dans ce cas, la technologie de pipeline est impuissante, car une nouvelle instance ne peut pas être lancée avant que le point d'ancrage de l'instance précédente ne soit commandé. Shoal garantit qu'il est moins probable que les leaders correspondants soient sélectionnés pour traiter les points d'ancrage manquants en attribuant un score à chaque nœud de validation basé sur 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 bas, 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 entre le tour et le leader à chaque mise à jour du score, en faveur des leaders ayant des scores plus élevés. Pour que les validateurs parviennent à un consensus sur la nouvelle cartographie, ils doivent parvenir à un consensus sur le score, atteignant ainsi un consensus sur l'historique utilisé pour dériver le score.

Dans Shoal, la chaîne de production 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 ancres lors de la r-ème ronde, les validateurs n'ont qu'à calculer une nouvelle fonction de mappage F' à partir de la r+1-ème ronde en se basant sur l'histoire causale des ancres ordonnées de la r-ème ronde. Ensuite, les nœuds de validation commencent à utiliser la fonction de sélection d'ancres mise à jour F' pour exécuter une nouvelle instance de Bullshark à partir de la r+1-ème ronde.

Plus de délais

Le dépassement de temps 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 temps augmentera également considérablement la latence, car il est très important de les configurer correctement et qu'elles nécessitent souvent un ajustement dynamique, car cela dépend fortement de l'environnement ( réseau ). Avant de passer au prochain leader, le protocole