Marco de 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 pausas en protocolos deterministas reales. En general, en situaciones sin fallos, se mejoró la latencia de Bullshark en un 40% y en situaciones con fallos se mejoró en un 80%.

Shoal es un marco que mejora cualquier protocolo de consenso basado en Narwhal ( como DAG-Rider, Tusk, Bullshark ) a través de canalización y reputación del líder. La canalización reduce la latencia de ordenación del DAG al introducir un punto de anclaje en cada ronda, 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 que Shoal aproveche la construcción de DAG asincrónica para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal ofrezca una propiedad que llamamos respuesta universal, que contiene la respuesta optimista que generalmente se necesita.

Esta tecnología es muy simple, implica ejecutar múltiples instancias del protocolo subyacente una tras otra en orden. 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 redes de blockchain, las personas han estado enfocadas 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 primeras versiones de Diem, solo logró 3500 TPS, muy por debajo del objetivo de más de 100k TPS.

El reciente avance proviene del reconocimiento de que la propagación de datos es el principal cuello de botella basado en el protocolo 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 y propone una arquitectura en la que todos los validadores propagan datos simultáneamente, mientras que el componente de consenso solo ordena una cantidad reducida de metadatos. El documento de Narwhal reportó un rendimiento de 160,000 TPS.

Se presentó anteriormente Quorum Store - Narwhal, que implementa la separación de la propagación de datos y el consenso, así como 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 los cambios de vista de 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, a medida que aumenta el rendimiento, el líder de Hotstuff/Jolteon sigue estando limitado.

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

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

Antecedentes de DAG-BFT

Cada vértice en el DAG de Narwhal está asociado con un número de ronda. Para entrar en la ronda r, el 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 propiedad clave de DAG no es ambigua: si dos nodos de validación tienen el mismo vértice v en su vista local de DAG, entonces tienen la misma historia causal de v.

Secuencia completa

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 basados en Narwhal existentes tienen la siguiente estructura:

1. Punto de anclaje programado: cada ciertas rondas habrá un líder predefinido, el vértice del líder se llama punto de anclaje;

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

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

La clave para satisfacer la seguridad es asegurar que en el paso 2, todos los nodos de verificación honestos creen una lista de anclajes ordenados, de modo que todas las listas compartan el mismo prefijo. En Shoal, se hacen las siguientes observaciones sobre todos los protocolos mencionados anteriormente:

Todos los validadores están de acuerdo con el primer punto de anclaje ordenado.

Bullshark retraso

La latencia de Bullshark depende del número de rondas entre los puntos de anclaje ordenados en el DAG. Aunque la parte más práctica de Bullshark tiene mejor latencia en versiones de sincronización que en versiones asincrónicas, aún está lejos de ser óptima.

Pregunta 1: Retardo promedio de bloques. En Bullshark, cada ronda par tiene un punto de anclaje, y cada ronda impar se interpreta como una votación. En casos comunes, se requieren dos rondas de DAG para ordenar los puntos de anclaje; sin embargo, los puntos en la historia causal del ancla requieren más rondas para esperar que los puntos de anclaje sean ordenados. En casos comunes, los puntos en las rondas impares requieren tres rondas, mientras que los puntos no anclados en las rondas pares requieren cuatro rondas.

Pregunta 2: Retraso en casos de falla, el análisis de retraso anterior se aplica a situaciones sin fallas, por otro lado, si un líder de ronda no logra transmitir lo suficientemente rápido el ancla, no se puede ordenar el ancla ( y, por lo tanto, se omite ), por lo que todos los vértices no ordenados de las rondas anteriores deben esperar a que se ordene el siguiente ancla. Esto reduce significativamente el rendimiento de la red de replicación geográfica, especialmente porque se utiliza un tiempo de espera de Bullshark para esperar al líder.

Marco de Shoal

Shoal resolvió estos dos problemas de retraso, mejorando Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de un sistema de tuberías, permitiendo que haya un punto de anclaje en cada ronda y reduciendo el retraso de todos los vértices no anclados en el DAG a tres rondas. Shoal también introdujo un mecanismo de reputación de líderes de cero costo 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, la reputación de la línea de producción y de los líderes 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 en la idea del ancla en Bullshark (. Aunque las discrepancias en la identidad del líder no violan la seguridad de estos protocolos, en Bullshark podría llevar a un orden completamente diferente, lo que plantea el núcleo del problema, es decir, que la selección dinámica y determinista del ancla de la ronda es necesaria para resolver el consenso, y los validadores deben alcanzar un consenso sobre la historia ordenada para seleccionar los futuros anclajes.

Como evidencia de la dificultad del problema, la implementación de Bullshark, incluida la que actualmente se encuentra 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(

Acuerdo

A pesar de los desafíos mencionados, la solución se encuentra oculta detrás de la simplicidad.

En Shoal, se basa en la capacidad de realizar cálculos locales sobre el DAG y se logra la capacidad de almacenar y reinterpretar la información de rondas anteriores. Con la visión central de que todos los validadores acuerdan el primer ancla ordenada, Shoal combina en secuencia múltiples instancias de Bullshark para su procesamiento en línea, lo que hace 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 mapea los turnos a los líderes. Shoal ejecuta instancias de Bullshark una tras otra, de modo que para cada instancia, el ancla es determinada previamente por el mapeo F. Cada instancia ordena un ancla, lo que activa el cambio a la siguiente instancia.

Al principio, Shoal lanzó la primera instancia de Bullshark en la primera ronda del 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 concluyente 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 inicia una nueva instancia en la segunda ronda, que tiene su propio punto de anclaje, el cual es ordenado por esa instancia, y luego, otra nueva instancia ordena el punto de anclaje 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 período de clasificación de Bullshark, la latencia aumenta al omitir puntos de anclaje. En este caso, la técnica de canalización no puede ayudar, ya que no se puede iniciar una nueva instancia antes de que se ordenen los puntos de anclaje de la instancia anterior. Shoal asegura que es poco probable que se elija al líder correspondiente para manejar los puntos de anclaje perdidos en el futuro, asignando un puntaje a cada nodo de validación según el historial de actividad reciente de cada nodo de validación mediante un mecanismo de reputación. Los validadores que respondan y participen 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 fallar, 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 puntos, inclinándose hacia los líderes con puntuaciones más altas. Para que los validadores lleguen a un consenso sobre el nuevo mapeo, deberían alcanzar un consenso sobre los puntos, logrando así un acuerdo en la historia utilizada para derivar los puntos.

En Shoal, las líneas de producció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 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-1baf540693f376d93cb18ef3193593cc.webp(

No hay más tiempo de espera

El tiempo de espera desempeña 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 puede aumentar significativamente la latencia, ya que es muy importante configurarlos adecuadamente y a menudo requieren ajustes dinámicos, dado que depende en gran medida del entorno ) red (. Antes de pasar al siguiente líder, el protocolo