Marco de Shoal: ¿Cómo reducir la latencia de Bullshark en Aptos?

Resumen

Aptos labs resolvió dos importantes problemas abiertos en el DAG BFT, reduciendo significativamente la latencia y eliminando por primera vez la necesidad de pausas en el protocolo práctico determinista. En general, la latencia de Bullshark se mejoró 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 ( a través de tuberías y la reputación del líder, como DAG-Rider, Tusk, Bullshark ). La tubería reduce la latencia de ordenamiento de DAG al introducir puntos de anclaje en cada ronda, y la reputación del líder mejora aún más el problema de 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 a Shoal aprovechar la construcción de DAG asíncrona para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal ofrezca propiedades de respuesta universal, que incluyen las respuestas optimistas que normalmente se requieren.

Esta tecnología es muy simple, ya que implica ejecutar múltiples instancias del protocolo subyacente en orden. Por lo tanto, cuando se instancia con Bullshark, se obtiene 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 primeras versiones de Diem solo logró 3500 TPS, muy por debajo del objetivo de 100k+ TPS.

Recientemente, la ruptura provino 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 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, y el componente de consenso solo ordena una pequeña cantidad de metadatos. El documento de Narwhal reporta un rendimiento de 160,000 TPS.

El Quorum Store mencionado anteriormente implementa la separación de la difusión de datos y el consenso para expandir 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, reduciendo 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 separar la difusión de datos del consenso, a medida que aumenta el rendimiento, los líderes de Hotstuff/Jolteon siguen estando limitados.

Por lo tanto, se ha implementado Bullshark sobre Narwhal DAG, 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%.

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

Contexto de DAG-BFT

En el Narwhal DAG, cada vértice está asociado con un número de ronda. Al entrar en la ronda r, los validadores deben primero obtener n-f vértices de 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 no es ambigua: si dos nodos de verificación tienen el mismo vértice v en la vista local de DAG, entonces tienen la misma historia causal de v.

Orden Total

Se puede llegar a un consenso sobre el orden total de todos los vértices en el DAG sin gastos 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 votaciones.

Aunque la lógica de la 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 hay un líder previamente determinado, cuyo vértice se llama punto de anclaje.

2. Puntos de anclaje de orden: los validadores deciden de manera independiente pero determinista qué puntos de anclaje ordenar o saltar.

3. Historia causal ordenada: los validadores procesan uno por uno la lista de puntos de anclaje ordenados, ordenando los vértices desordenados anteriores en la historia causal de cada punto de anclaje.

La clave para satisfacer la seguridad es asegurar que en el paso (2), todas las listas de puntos de anclaje ordenados creadas por nodos de validación honestos compartan el mismo prefijo. En Shoal, hacemos las siguientes observaciones sobre todos estos protocolos:

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

Pregunta 1: Retraso medio de bloques. En Bullshark, cada ronda par tiene un ancla, y el vértice de la ronda impar se interpreta como un voto. En situaciones comunes, se requieren dos rondas de DAG para ordenar el ancla; sin embargo, los vértices en la historia causal del ancla requieren más rondas para que el ancla sea ordenada. Normalmente, los vértices en rondas impares necesitan tres rondas, mientras que los vértices no ancla en rondas pares necesitan cuatro rondas.

Pregunta 2: Retraso en casos de fallos. El análisis de retraso anterior se aplica a situaciones sin fallos; por otro lado, si un líder de ronda no puede transmitir el punto de anclaje lo suficientemente rápido, no se puede ordenar el punto de anclaje (, por lo que se omite ). Todos los vértices no ordenados en las primeras rondas deben esperar a que se ordene el siguiente punto de anclaje. 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 de Shoal

Shoal resolvió estos dos problemas de latencia, mejorando Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de una canalización, permitiendo 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íder de cero costo en el DAG, seleccionando una preferencia hacia líderes rápidos.

Desafío

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

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

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 ( ancla en Bullshark ). Aunque las discrepancias en la identidad del líder no violan la seguridad de estos protocolos, en Bullshark pueden llevar a un ordenamiento completamente diferente, lo que plantea el núcleo del problema: seleccionar anclas de manera dinámica y determinista es necesario para resolver el consenso, los validadores deben llegar a un acuerdo sobre la historia ordenada para seleccionar futuras anclas.

Como evidencia de la dificultad del problema, la implementación de Bullshark ( incluye que las implementaciones en el entorno de producción actual ) no admiten estas características.

Acuerdo

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

En Shoal, dependemos de la capacidad de ejecutar cálculos locales en DAG para lograr la capacidad de almacenar y reinterpretar la información de rondas anteriores. Con la visión fundamental de que todos los validadores están de acuerdo con el primer ancla ordenada, Shoal combina en secuencia múltiples instancias de Bullshark para su procesamiento en línea, haciendo que ( el primer ancla ordenada sea el punto de conmutación de las instancias, ) la historia causal del ancla se utiliza para calcular la reputación del líder.

Línea de producción

V que mapea las rondas a los líderes. Shoal ejecuta instancias de Bullshark una tras otra, donde el ancla de cada instancia está predefinida por el mapeo F. Cada instancia ordena un ancla, 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 funcionó hasta que se determinó el primer ancla ordenada, como en la ronda r. Todos los validadores estuvieron de acuerdo con 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 inicia 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 un punto de anclaje en la tercera ronda, y el proceso continúa.

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 tecnología de canalización no puede hacer nada, ya que no se puede iniciar una nueva instancia antes de que se ordene el punto 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, utilizando un mecanismo de reputación que asigna puntuaciones según el historial de actividad reciente de cada nodo de validación. Los validadores que respondan y participen en el protocolo recibirán altas puntuaciones, de lo contrario, los nodos de validación recibirán bajas puntuaciones, ya que pueden estar caídos, lentos o actuar de manera maliciosa.

Su concepto es recalcular de manera determinista el mapeo predefinido F 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 llegar a un acuerdo sobre la puntuación, logrando así un consenso sobre la historia utilizada para derivar la puntuación.

En Shoal, las líneas de producción y la reputación del liderazgo pueden combinarse naturalmente, ya que ambas utilizan la misma tecnología central, que es reinterpretar el DAG después de llegar a un consenso sobre el primer anclaje ordenado.

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 según la historia causal de los puntos de anclaje ordenados en la ronda r. Luego, los nodos de validación utilizan la función de selección de puntos de anclaje actualizada F' para ejecutar una nueva instancia de Bullshark 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 determinísticas 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.

Los tiempos de espera también aumentarán significativamente la latencia, ya que es muy importante configurarlos adecuadamente, lo que a menudo requiere ajustes dinámicos, ya que depende en gran medida del entorno ( y de la red ). Antes de pasar al siguiente líder, el protocolo pagará una penalización completa por la latencia del tiempo de espera para los líderes defectuosos. Por lo tanto, la configuración de los tiempos de espera no puede ser demasiado conservadora, pero si el tiempo de espera es demasiado corto, el protocolo podría saltarse a buenos líderes. Por ejemplo, hemos observado que, en situaciones de alta carga, los líderes en Jolteon/Hotstuff se ven abrumados y el tiempo de espera ya ha expirado antes de que se logre el progreso.

Desafortunadamente, los protocolos basados en el líder (, como Hotstuff y Jolteon ), esencialmente requieren un tiempo de espera para garantizar que el protocolo avance cada vez que el líder falla. Sin un tiempo de espera, incluso un líder que se ha caído podría detener el protocolo indefinidamente. Dado que durante el período asíncrono no se puede distinguir entre un líder defectuoso y un líder lento, el tiempo de espera puede llevar a 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 del DAG, con el fin de asegurar que durante la sincronización, los líderes honestos añadan puntos de anclaje al DAG rápidamente.