Marco Shoal: cómo reducir la latencia de Bullshark en Aptos

Resumen

Aptos labs resolvió dos importantes problemas abiertos en DAG BFT, reduciendo significativamente la latencia y eliminando por primera vez la necesidad de tiempos de espera en un protocolo práctico determinista. En general, en condiciones sin fallos, la latencia de Bullshark mejoró un 40%, y en condiciones de fallo mejoró un 80%.

Shoal es un marco que mejora el protocolo de consenso basado en Narwhal ( a través de pipelines y la reputación de los líderes, como DAG-Rider, Tusk, Bullshark ). La pipeline reduce la latencia de ordenamiento DAG al introducir puntos de anclaje en cada ronda, y la reputación del líder mejora aún más la latencia al asegurar que los puntos de anclaje estén asociados con los nodos de validación más rápidos. Además, la reputación del líder permite que Shoal aproveche la construcción de DAG asíncrona para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal ofrezca lo que llamamos la propiedad de respuesta universal, que incluye la respuesta optimista que generalmente se requiere.

Nuestra tecnología es muy sencilla, involucra múltiples instancias de protocolos subyacentes que se ejecutan en secuencia. Por lo tanto, cuando se instancia con Bullshark, obtenemos un grupo de "tiburones" que están en una carrera de relevos.

Motivación

Al buscar un alto rendimiento en las redes de blockchain, la gente ha estado enfocándose en reducir la complejidad de la comunicación. Sin embargo, este enfoque no ha llevado a un aumento significativo en el rendimiento. Por ejemplo, Hotstuff implementado en las versiones tempranas de Diem solo logró 3500 TPS, muy por debajo del objetivo de 100k+ TPS.

El reciente avance se debe a la comprensión de que la propagación de datos es el principal cuello de botella basado en el protocolo de los líderes, y puede beneficiarse de la paralelización. El sistema Narwhal separa la propagación de datos de la lógica de consenso central, proponiendo una arquitectura en la que todos los validadores propagan datos simultáneamente, mientras que el componente de consenso solo ordena una cantidad menor de metadatos. El documento de Narwhal reporta una capacidad de 160,000 TPS.

Antes presentamos Quorum Store, es decir, cómo nuestra implementación de Narwhal separa la propagación de datos del consenso, y cómo usarlo para escalar el protocolo de consenso actual Jolteon. Jolteon es un protocolo basado en líderes que combina la ruta rápida lineal de Tendermint y el cambio de vista al estilo PBFT, lo que puede reducir la latencia de Hotstuff en un 33%. Sin embargo, los protocolos de consenso basados en líderes no pueden aprovechar plenamente el potencial de rendimiento de Narwhal. A pesar de que se separa la propagación de datos del consenso, a medida que aumenta el rendimiento, el líder de Hotstuff/Jolteon sigue estando limitado.

Por lo tanto, decidimos desplegar Bullshark sobre Narwhal DAG, un protocolo de consenso sin costo de comunicación. Desafortunadamente, la estructura DAG que soporta el alto rendimiento de Bullshark conlleva un costo de latencia del 50%.

Este artículo presenta cómo Shoal reduce significativamente la latencia de Bullshark.

Fondo de DAG-BFT

Cada vértice en el DAG de Narwhal está asociado con una ronda. Para ingresar a la ronda r, un validador debe primero obtener n-f vértices que pertenecen a la ronda r-1. Cada validador puede difundir un vértice por ronda, y cada vértice debe referenciar al menos n-f vértices de la ronda anterior. Debido a la asincronía de la red, diferentes validadores pueden observar diferentes vistas locales del DAG en cualquier momento.

Una de las propiedades clave de DAG es la no ambigüedad: si dos nodos de validación tienen el mismo vértice v en la vista local de DAG, entonces tienen la misma historia causal de v.

Permutación total

Se puede lograr un consenso sobre el orden total de todos los vértices en el DAG sin costos de comunicación adicionales. Para ello, los validadores en DAG-Rider, Tusk y Bullshark interpretan la estructura del DAG como un protocolo de consenso, donde los vértices representan propuestas y las aristas representan votos.

Aunque la lógica de intersección de grupos en la estructura DAG es diferente, todos los protocolos de consenso basados en Narwhal existentes tienen la siguiente estructura:

1. Punto de anclaje programado: cada pocas rondas (, como en dos rondas de Bullshark ), hay un líder previamente determinado, el vértice del líder se llama punto de anclaje;

2. Puntos de anclaje de ordenación: los validadores deciden de manera independiente pero determinista qué puntos de anclaje ordenar y cuáles omitir;

3. historial de causalidad ordenada: los validadores procesan uno tras otro la lista de puntos de anclaje ordenados, y para cada punto de anclaje, ordenan todos los vértices anteriores no ordenados en su historial de causalidad mediante algunas reglas deterministas.

La clave para satisfacer la seguridad es asegurar que en el paso (2), todos los nodos de verificación honestos compartan la misma prefijo en la lista de anclajes ordenados que crean. En Shoal, hacemos las siguientes observaciones sobre todos los protocolos mencionados anteriormente:

Todos los validadores acuerdan el primer ancla ordenada.

Bullshark latencia

La latencia de Bullshark depende del número de rondas entre los puntos de anclaje ordenados en el DAG. Aunque la versión sincronizada más práctica de Bullshark tiene una mejor latencia que la versión asíncrona, aún está lejos de ser óptima.

Pregunta 1: Latencia media de bloques. En Bullshark, cada ronda par tiene un punto de anclaje y cada vértice de la ronda impar se interpreta como un voto. En situaciones comunes, se requieren dos rondas de DAG para ordenar los puntos de anclaje; sin embargo, los vértices en la historia causal de los puntos de anclaje requieren más rondas para esperar que los puntos de anclaje sean ordenados. En situaciones comunes, los vértices en rondas impares necesitan tres rondas, mientras que los vértices no anclados en rondas pares necesitan cuatro rondas.

Pregunta 2: latencia de casos de fallo, el análisis de latencia anterior se aplica a situaciones sin fallos, por otro lado, si el líder de una ronda no logra transmitir lo suficientemente rápido los puntos de anclaje, no se puede ordenar los puntos de anclaje (, por lo tanto se omiten ), por lo tanto todos los vértices no ordenados en las primeras rondas deben esperar a que se ordene el siguiente punto de anclaje. Esto reducirá significativamente el rendimiento de la red de replicación geográfica, especialmente porque Bullshark utiliza un tiempo de espera para esperar al líder.

Marco Shoal

Shoal resolvió estos dos problemas de latencia, mejorando Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de un procesamiento en paralelo, permitiendo que haya un punto de anclaje en cada ronda y reduciendo la latencia de todos los vértices no ancla en el DAG a tres rondas. Shoal también introdujo un mecanismo de reputación de líderes sin costo en el DAG, lo que hace que la selección favorezca a los líderes rápidos.

Desafío

En el contexto del protocolo DAG, la reputación de la línea de producción y del líder se considera un problema difícil, por las siguientes razones:

1. Las líneas de producción anteriores intentaron modificar la lógica central de Bullshark, pero esto parece ser esencialmente imposible.

2. La reputación del líder se introduce en DiemBFT y se formaliza en Carousel, seleccionando dinámicamente a los futuros líderes según el rendimiento pasado de los validadores, la idea de anclaje en Bullshark (. Aunque las discrepancias en la identidad del líder no violan la seguridad de estos protocolos, en Bullshark, pueden llevar a un orden completamente diferente, lo que plantea el núcleo del problema: seleccionar anclas de manera dinámica y determinista es necesario para resolver el consenso, y los validadores deben llegar a un acuerdo sobre la historia ordenada para seleccionar futuros anclajes.

Como evidencia de la dificultad del problema, notamos que la implementación de Bullshark, incluida la implementación actual en el entorno de producción, no admite estas características.

![Explicación detallada del marco Shoal: ¿cómo reducir la latencia de Bullshark en Aptos?])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(

Protocolo

A pesar de los desafíos mencionados, la solución se oculta en la simplicidad.

En Shoal, nos basamos en la capacidad de realizar cálculos locales sobre el DAG y hemos logrado la capacidad de guardar y reinterpretar la información de las primeras rondas. Con la visión fundamental de que todos los validadores acuerdan el primer ancla ordenada, Shoal combina secuencialmente múltiples instancias de Bullshark para procesarlas en paralelo, haciendo que ) el primer ancla ordenada sea el punto de cambio de las instancias, así como ( la historia causal del ancla se utiliza para calcular la reputación del líder.

Línea de producción

V que asigna rondas a líderes. Shoal ejecuta instancias de Bullshark una tras otra, de modo que para cada instancia, el punto de anclaje está predeterminado por el mapeo F. Cada instancia ordena un punto de anclaje, lo que desencadena el cambio a la siguiente instancia.

Al principio, Shoal lanzó la primera instancia de Bullshark en la primera ronda de DAG y la ejecutó hasta que se determinó el primer punto de anclaje ordenado, como en la ronda r. Todos los validadores estuvieron de acuerdo con este punto de anclaje. Por lo tanto, todos los validadores pueden acordar de manera confiable reinterpretar el DAG a partir de la ronda r+1. Shoal simplemente lanzó una nueva instancia de Bullshark en la ronda r+1.

En el mejor de los casos, esto permite que Shoal ordene un ancla en cada ronda. El ancla de la primera ronda se ordena según la primera instancia. Luego, Shoal comienza una nueva instancia en la segunda ronda, la cual tiene su propio ancla, que se ordena por esa instancia, y luego, otra nueva instancia ordena el ancla en la tercera ronda, y el proceso continúa.

![Explicación detallada del marco Shoal: ¿cómo reducir la latencia de Bullshark en Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Reputación del líder

Durante el salto de puntos de anclaje en la clasificación de Bullshark, la latencia aumentará. En este caso, la técnica de canalización es ineficaz, ya que no se puede iniciar una nueva instancia antes de que se clasifique el punto de anclaje de la instancia anterior. Shoal asegura que es menos probable que se elija al líder correspondiente para manejar los puntos de anclaje perdidos en el futuro, asignando una puntuación a cada nodo de validación según el historial de actividad reciente de cada nodo de validación a través de un mecanismo de reputación. Los validadores que respondan y participen en el protocolo recibirán altas puntuaciones; de lo contrario, a los nodos de validación se les asignarán bajas puntuaciones, ya que pueden fallar, ser lentos o actuar de manera maliciosa.

Su concepto es recalcular de manera determinista el mapeo predefinido F desde el turno hasta el líder cada vez que se actualiza la puntuación, favoreciendo a los líderes con puntuaciones más altas. Para que los validadores lleguen a un consenso sobre el nuevo mapeo, deben alcanzar un consenso sobre la puntuación, logrando así un acuerdo en la historia utilizada para derivar la puntuación.

En Shoal, la canalización y la reputación de liderazgo pueden combinarse de manera natural, ya que ambas utilizan la misma tecnología central, que es reinterpretar el DAG después de alcanzar un consenso sobre el primer ancla ordenada.

De hecho, la única diferencia es que, después de ordenar los anclajes en la ronda r, los validadores solo necesitan calcular un nuevo mapeo F' a partir de la ronda r+1, basándose en la historia causal de los anclajes ordenados en la ronda r. Luego, los nodos de validación inician una nueva instancia de Bullshark utilizando la función de selección de anclajes actualizada F' a partir de la ronda r+1.

![Explicación detallada del marco Shoal: ¿Cómo reducir la latencia de Bullshark en Aptos?])https://img-cdn.gateio.im/webp-social/moments-1baf540693f376d93cb18ef3193593cc.webp(

No hay más tiempo de espera

El tiempo de espera juega un papel crucial en todas las implementaciones BFT deterministas basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estados internos que necesitan ser gestionados y observados, lo que incrementa la complejidad del proceso de depuración y requiere más técnicas de observabilidad.

El tiempo de espera también aumentará significativamente la latencia, ya que es muy importante configurarlos adecuadamente y, a menudo, necesitan ajustes dinámicos, ya que dependen en gran medida del entorno ) red (. Antes de pasar al siguiente líder, el protocolo pagará la penalización completa por la latencia de tiempo de espera al líder defectuoso. Por lo tanto,