Marco Shoal: Optimización de la latencia del consenso Bullshark en Aptos

Aptos Labs ha resuelto recientemente dos importantes problemas abiertos en DAG BFT, reduciendo significativamente la latencia y eliminando por primera vez la necesidad de tiempos de espera en protocolos deterministas reales. En general, ha mejorado la latencia de Bullshark en un 40% en condiciones sin fallos y en un 80% en condiciones de fallo.

Shoal es un marco que mejora el protocolo de consenso basado en Narwhal ( mediante un procesamiento en línea y un mecanismo de reputación del líder, como DAG-Rider, Tusk y Bullshark ). La línea de producción introduce un punto de anclaje en cada ronda para reducir la latencia de ordenación del DAG, y la reputación del líder mejora aún más el problema de latencia al asegurar que el punto de anclaje esté asociado con los nodos de validación más rápidos. Además, la reputación del líder permite a Shoal aprovechar la construcción de DAG asincrónica para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal ofrezca características de respuesta universal, que incluyen las respuestas optimistas que normalmente se requieren.

La tecnología de Shoal es relativamente simple, ya que se ejecutan múltiples instancias del protocolo subyacente una tras otra. Al instanciar Bullshark, se forma un grupo de "tiburones" que realizan una carrera de relevos.

Contexto y motivación

En la búsqueda de un alto rendimiento en las redes de blockchain, la reducción de la complejidad de la comunicación ha sido un enfoque clave. Sin embargo, este método no ha llevado a un aumento significativo en el rendimiento. Por ejemplo, Hotstuff implementado en las primeras versiones de Diem solo alcanzó 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 consenso de los líderes, y que 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 donde todos los validadores propagan datos simultáneamente, mientras que el componente de consenso solo ordena una pequeña cantidad de metadatos. El documento de Narwhal informa de un rendimiento de 160,000 TPS.

Aptos presentó anteriormente Quorum Store, que es la implementación de Narwhal, separando 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 el camino rápido lineal de Tendermint y los cambios de vista al estilo PBFT, lo que puede reducir la latencia de Hotstuff en un 33%. Sin embargo, es evidente que los protocolos de consenso basados en líderes no pueden aprovechar plenamente el potencial de rendimiento de Narwhal. A pesar de separar la propagación de datos del consenso, con el aumento del rendimiento, el líder de Hotstuff/Jolteon sigue estando limitado.

Por lo tanto, Aptos decidió implementar Bullshark sobre el DAG Narwhal, un protocolo de consenso sin costo de comunicación. Desafortunadamente, en comparación con Jolteon, la estructura DAG que soporta el alto rendimiento de Bullshark conlleva un costo de latencia del 50%.

Fondo DAG-BFT

Cada vértice en el DAG de Narwhal está asociado a un número de 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 del DAG es la no ambigüedad: si dos nodos de verificación tienen el mismo vértice v en su vista local del DAG, entonces tienen la misma historia causal de v.

Prólogo

Se puede llegar a un consenso sobre el orden total de todos los vértices en el DAG sin costos adicionales de comunicación. 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 existentes basados en Narwhal tienen la siguiente estructura:

1. Punto de anclaje programado: cada pocas rondas (, por ejemplo, en Bullshark, cada dos rondas ) habrá un líder preestablecido, y el vértice del líder se denomina punto de anclaje.

2. Puntos de anclaje ordenados: los validadores deciden de manera independiente pero determinista cuáles puntos de anclaje ordenar y cuáles omitir.

3. Historia causal ordenada: los validadores procesan uno tras otro una lista de puntos de anclaje ordenados, para cada punto de anclaje, ordenan todos los vértices desordenados anteriores en su historia causal mediante reglas deterministas.

La clave para garantizar la seguridad es asegurar que en el paso 2, todos los nodos de validación honestos creen una lista de puntos de anclaje ordenada, de modo que todos los listados compartan el mismo prefijo. En Shoal, se hacen las siguientes observaciones sobre todos los protocolos mencionados anteriormente: todos los validadores están de acuerdo en el primer punto de anclaje ordenado.

Bullshark latencia

La latencia de Bullshark depende de la cantidad de rondas entre los puntos de anclaje ordenados en el DAG. Aunque la versión sincronizada más práctica de Bullshark tiene mejor latencia que la versión asincrónica, todavía está lejos de ser la óptima.

Principalmente hay dos problemas:

1. Latencia promedio de bloque: en Bullshark, cada ronda par tiene un ancla, 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 anclajes, sin embargo, los vértices en la historia causal de los anclajes requieren más rondas para esperar que los anclajes sean ordenados. En situaciones comunes, los vértices en rondas impares requieren tres rondas, mientras que los vértices no anclados en rondas pares requieren cuatro rondas.

2. Casos de fallo de latencia: si un líder en una ronda no logra transmitir lo suficientemente rápido el ancla, no se puede ordenar el ancla (, por lo que se salta ). Todos los vértices no ordenados de las rondas anteriores deben esperar a que se ordene el siguiente ancla. Esto puede 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 mejora el procesamiento de Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de una línea de producción, 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 introduce un mecanismo de reputación de líder de costo cero en el DAG, lo que hace que la selección se incline hacia líderes rápidos.

Desafío

En el contexto del protocolo DAG, el procesamiento en pipeline y la reputación del líder se consideran problemas difíciles, por las siguientes razones:

1. Los intentos anteriores de procesar la línea de producción para modificar la lógica central de Bullshark parecen ser fundamentalmente imposibles.

2. La reputación del líder se introduce en DiemBFT y se formaliza en Carousel, basándose en el rendimiento pasado de los validadores para seleccionar dinámicamente a los futuros líderes. La idea de anclar en Bullshark es (. Aunque las discrepancias en la identidad del líder no violan la seguridad de estos protocolos, en Bullshark, podrían llevar a un orden completamente diferente. Esto plantea el núcleo del problema, ya que seleccionar anclajes de rueda de manera dinámica y determinista es necesario para resolver el consenso, y los validadores necesitan llegar a un acuerdo sobre la historia ordenada para elegir los futuros anclajes.

Protocolo

A pesar de los desafíos mencionados, la solución se encuentra en la simplicidad. En Shoal, se aprovecha la capacidad de realizar cálculos locales sobre un DAG, logrando así la habilidad de almacenar y reinterpretar la información de las rondas anteriores. Con la visión central de que todos los validadores están de acuerdo en el primer punto de anclaje ordenado, Shoal combina en secuencia múltiples instancias de Bullshark para un procesamiento en pipeline, lo que permite:

1. El primer punto de anclaje ordenado es el punto de cambio de la instancia.
2. La historia causal del ancla se utiliza para calcular la reputación de los líderes.

) procesamiento en línea

V que asigna rondas a líderes. Shoal ejecuta instancias de Bullshark una tras otra, de modo que para cada instancia, el ancla es previamente determinado por el mapeo F. Cada instancia ordena un ancla, lo que desencadena el cambio a la siguiente instancia.

Inicialmente, Shoal lanzó la primera instancia de Bullshark en la primera ronda del DAG y la ejecutó hasta que se determinó el primer ancla ordenada, como en la ronda r. Todos los validadores acordaron este ancla. 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. Los puntos de anclaje de la primera ronda se ordenan según la primera instancia. Luego, Shoal comienza una nueva instancia en la segunda ronda, que tiene su propio punto de anclaje, y ese ancla se ordena por esa instancia, luego, otra nueva instancia ordena el punto de anclaje en la tercera ronda, y luego 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-0b0928cb6240e994c1514c75e080a4b2.webp(

) reputación del líder

Durante el período de ordenación de Bullshark, al omitir puntos de anclaje, la latencia aumentará. En este caso, la técnica de procesamiento en línea no puede ayudar, ya que no se puede iniciar una nueva instancia antes de que se ordene el punto de anclaje de la instancia anterior. Shoal garantiza que sea poco probable elegir a los líderes correspondientes para manejar los puntos de anclaje perdidos en el futuro, asignando una puntuación a cada nodo de validación en función del historial de actividad reciente de cada nodo de validación mediante el uso de un mecanismo de reputación. Los validadores que responden y participan en el protocolo recibirán una puntuación alta; de lo contrario, los nodos de validación recibirán una puntuación baja, ya que pueden colapsar, ser lentos o actuar maliciosamente.

Su concepto es recalcular de manera determinista el mapeo predefinido F desde la ronda hasta el líder cada vez que se actualizan los puntajes, favoreciendo a los líderes con puntajes más altos. Para que los validadores lleguen a un consenso sobre el nuevo mapeo, deben llegar a un acuerdo sobre los puntajes, logrando así un consenso sobre la historia utilizada para derivar los puntajes.

En Shoal, el procesamiento en línea y la reputación de liderazgo pueden combinarse de forma natural, ya que ambos utilizan la misma tecnología central, es decir, reinterpretar el DAG después de alcanzar el consenso sobre el primer ancla ordenada.

De hecho, la única diferencia es que, después de ordenar los puntos de anclaje 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 puntos de anclaje ordenados en la ronda r. Luego, los nodos de validación comienzan a ejecutar una nueva instancia de Bullshark utilizando la función de selección de puntos de anclaje 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-859e732e16c3eee0e2c93422474debc2.webp(

) No es necesario un tiempo de espera

El tiempo de espera juega un papel crucial en todas las implementaciones BFT determinísticas basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estados internos que deben 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, se requiere un ajuste dinámico, ya que depende en gran medida del entorno ### red (. Antes de pasar al siguiente líder, el protocolo pagará la penalización completa por la latencia del tiempo de espera para el líder con fallos. Por lo tanto, la configuración del tiempo de espera no puede ser demasiado conservadora, pero si el tiempo de espera es demasiado corto, el protocolo puede omitir a buenos líderes.

Desafortunadamente, los protocolos basados en líderes ) como Hotstuff y Jolteon ( requieren esencialmente un tiempo de espera para asegurar que el protocolo pueda avanzar cada vez que un líder falla. Sin un tiempo de espera, incluso un líder fallido podría detener el protocolo para siempre. Dado que no se puede distinguir entre un líder fallido y un líder lento durante el período asíncrono, los tiempos de espera pueden hacer que los nodos de validación vean cambios en todos los líderes sin actividad de consenso.

En Bullshark, el tiempo de espera se utiliza para la construcción de DAG, para asegurar que durante la sincronización, los líderes honestos añadan puntos de anclaje al DA.