Marco Shoal: cómo Soltar la latencia de Bullshark de Aptos

Aptos Labs ha resuelto dos importantes problemas abiertos en el DAG BFT, lo que ha permitido Soltar la latencia de manera significativa y ha eliminado por primera vez la necesidad de tiempos de espera en el protocolo práctico determinista. En general, en condiciones sin fallos, se ha mejorado la latencia de Bullshark en un 40%, y en condiciones con fallos, se ha mejorado en un 80%.

Shoal es un marco que mejora cualquier protocolo de consenso basado en Narwhal (, como DAG-Rider, Tusk, Bullshark ), a través del procesamiento en línea y el mecanismo de reputación del líder. La línea de producción reduce la latencia de ordenamiento de 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 el nodo de validación más rápido. Además, la reputación del líder permite que Shoal aproveche la construcción de DAG asíncrono para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal ofrezca la propiedad que llamamos respuesta universal, que incluye la respuesta optimista que generalmente se requiere.

Nuestra 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 perseguir un alto rendimiento en redes blockchain, las personas han estado enfocándose en Soltar 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 de nuestro objetivo de más de 100,000 TPS.

Pero el reciente avance proviene de la comprensión de que la propagación de datos es el principal cuello de botella basado en el protocolo de líderes, y que se puede beneficiar 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 pequeña cantidad de metadatos. El documento de Narwhal reportó un rendimiento de 160,000 TPS.

En artículos anteriores, presentamos Quorum Store. Nuestra implementación de Narwhal separa la propagación de datos del consenso, y cómo lo utilizamos 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 al estilo PBFT, lo que puede Soltar 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, los líderes de Hotstuff/Jolteon siguen estando limitados.

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

Este artículo presentará cómo Shoal logra Soltar significativamente la latencia de Bullshark.

fondo DAG-BFT

Primero, entendamos un poco el contexto. Para una descripción detallada de Narwhal y Bullshark, consulte el artículo DAG meets BFT.

Cada vértice en el DAG de Narwhal está asociado con una ronda. Para entrar en la ronda r, un validador debe primero obtener n-f vértices que pertenecen a la ronda r-1. Cada validador puede transmitir 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 que no es ambiguo: si dos nodos de verificación tienen el mismo vértice v en su vista local de DAG, entonces tienen exactamente la misma historia causal de v.

secuencia completa

Se puede alcanzar un consenso sobre el orden total de todos los vértices en el DAG sin gastos 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 los bordes 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 reservado: cada pocas rondas (, como en dos rondas en Bullshark ), habrá un líder predeterminado, el vértice del líder se llama punto de anclaje;

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

3. ordenando la historia causal: los validadores procesan uno por uno la lista de anclajes ordenados, y para cada anclaje, ordenan todos los vértices desordenados anteriores 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 validación honestos creen una lista de anclajes ordenados, de modo que todas las listas compartan el mismo prefijo. En Shoal, hacemos las siguientes observaciones sobre todos los protocolos anteriores:

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

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 de Bullshark es más práctica y tiene mejor latencia que la versión asincrónica, aún está lejos de ser la óptima.

Pregunta 1: latencia promedio de bloque. En Bullshark, cada ronda par tiene un ancla, y cada vértice de ronda impar se interpreta como un voto. En situaciones comunes, se requieren dos rondas de DAG para ordenar anclas; sin embargo, los vértices en la historia causal del ancla requieren más rondas para esperar que el ancla sea ordenada. En situaciones comunes, los vértices en la ronda impar necesitan tres rondas, mientras que los vértices que no son anclas en la ronda par 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 el anclaje, no se puede ordenar el anclaje ( y por lo tanto se salta ), por lo que todos los vértices no ordenados de las primeras rondas deben esperar a que se ordene el siguiente anclaje. Esto disminuirá significativamente el rendimiento de la red de replicación geográfica, especialmente porque el tiempo de espera de Bullshark se utiliza para esperar al líder.

Marco de Shoal

Shoal resolvió estos dos problemas de latencia, mejorando Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de un pipeline, permitiendo tener un ancla 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 se incline hacia líderes rápidos.

desafío

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

1. Las anteriores líneas de procesamiento 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 futuros líderes según el desempeño pasado de los validadores en la idea de anclar 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 anclajes de manera dinámica y determinística 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 que actualmente está en el entorno de producción, no soporta estas características.

) protocolo

A pesar de los desafíos mencionados, como dice el refrán, la solución se encuentra oculta en la simplicidad.

En Shoal, dependemos de la capacidad de realizar cálculos locales en el DAG y hemos logrado conservar y reinterpretar la información de las 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 procesarlas en cadena, haciendo que ### el primer ancla ordenada sea el punto de conmutación de las instancias, así como ( la historia causal del ancla se utilice para calcular la reputación del líder.

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

) procesamiento en línea

V que mapea las rondas a los líderes. Shoal ejecuta instancias de Bullshark una tras otra, de modo que para cada instancia, el ancla está predefinido por el mapeo F. Cada instancia ordena un ancla, lo que activa el cambio a la siguiente instancia.

Al principio, Shoal inició la primera instancia de Bullshark en la primera ronda de DAG y la ejecutó hasta determinar 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 inició 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, 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.

reputación de líder

Durante la clasificación de Bullshark, al omitir un ancla, la latencia aumentará. En este caso, la técnica de procesamiento en línea no puede hacer nada, ya que no se puede iniciar una nueva instancia antes de que se ordene el ancla de la instancia anterior. Shoal asegura que sea poco probable que se elija al líder correspondiente para manejar los anclajes 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 el uso de 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 podrían fallar, ser lentos o actuar mal.

Su concepto es recalcular de manera determinista el mapeo predefinido F desde la ronda hasta el líder cada vez que se actualiza la puntuación, favoreciendo al líder con puntajes más altos. Para que los validadores lleguen a un consenso sobre el nuevo mapeo, deben alcanzar un consenso sobre la puntuación, logrando así un acuerdo sobre 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 consiste en 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 usando la función de selección de puntos de anclaje actualizada F' a partir de la ronda r+1.

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, requieren ajustes dinámicos, ya que dependen en gran medida del entorno ( red ). Antes de pasar al siguiente líder, el protocolo pagará una penalización completa por el tiempo de espera del líder con fallas. 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 saltarse a buenos líderes. Por ejemplo, hemos observado que, en condiciones de alta carga, Jolt.