Análisis del marco Shoal: Soltar significativamente la latencia de Bullshark en Aptos

Aptos Labs recientemente resolvió dos problemas clave en DAG BFT, Soltando significativamente la latencia, y por primera vez eliminó la necesidad de tiempos de espera en un protocolo en tiempo real determinista. En general, en condiciones sin fallos, la latencia de Bullshark mejoró en un 40%, y en condiciones de fallo mejoró en un 80%.

Shoal es un marco que mejora el protocolo de consenso basado en Narwhal ( a través de un mecanismo de línea de producción y reputación de líderes, como DAG-Rider, Tusk, Bullshark ). La línea de producción reduce la latencia de ordenamiento DAG al introducir puntos de anclaje en cada ronda, y la reputación de los líderes 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 de los líderes permite a Shoal aprovechar la construcción DAG asíncrona para eliminar el tiempo de espera en todos los escenarios. Esto le otorga a Shoal una capacidad de respuesta universal, que incluye la respuesta optimista que normalmente se requiere.

La tecnología es muy simple, implica ejecutar múltiples instancias del protocolo subyacente en secuencia. Al instanciar Bullshark, es equivalente a un grupo de "tiburones" corriendo una carrera de relevos.

Antecedentes y Motivación

Al buscar un alto rendimiento en la red de blockchain, Soltar la complejidad de comunicación ha sido un enfoque clave. Sin embargo, este método no ha logrado un aumento significativo en el rendimiento. Por ejemplo, el Hotstuff implementado en el temprano Diem solo alcanzó 3500 TPS, muy por debajo del objetivo de más de 100,000 TPS.

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

Aptos presentó anteriormente Quorum Store, es decir, la implementación de Narwhal, que separa la propagación de datos y el consenso, utilizado para escalar el actual protocolo de consenso Jolteon. Jolteon combina la ruta rápida lineal de Tendermint y el cambio de vista al estilo PBFT, lo que puede Soltar 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.

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

El marco Shoal está diseñado para Soltar significativamente la latencia de Bullshark.

Fondo de DAG-BFT

En el DAG de Narwhal, cada vértice está asociado a una ronda. Al entrar en la ronda r, los validadores deben obtener primero n-f vértices de la ronda r-1. Cada validador puede difundir un vértice por ronda, y cada vértice debe referirse al menos a 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 es la no ambigüedad: si dos nodos de validación tienen el mismo vértice v en su vista local de DAG, entonces tienen exactamente la misma historia causal de v.

Secuencia de orden

Se puede alcanzar 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.

Todos los protocolos de consenso basados en Narwhal tienen la siguiente estructura:

1. Punto de anclaje: cada pocas rondas hay un líder predeterminado, cuyo vértice 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. Historia causal ordenada: los validadores procesan secuencialmente una lista de puntos de anclaje ordenados, clasificando los vértices desordenados anteriores en la historia causal de cada punto de anclaje.

La clave de la seguridad es asegurar que en el paso (2), todas las listas de anclajes ordenados creadas por nodos de validación honestos compartan el mismo prefijo. Shoal observó: todos los validadores acordaron el primer anclaje ordenado.

Bullshark latencia

La latencia de Bullshark depende del número de rondas entre los puntos de anclaje ordenados en el DAG. Aunque algunas versiones sincronizadas de Bullshark tienen una mejor latencia que las versiones asíncronas, aún están lejos de ser óptimas.

Principalmente existen dos problemas:

1. Latencia promedio de bloques: En situaciones comunes, los vértices de la ronda impar necesitan tres rondas, mientras que los vértices no ancla de la ronda par necesitan cuatro rondas para ser ordenados.

2. Situación de latencia de fallos: Si un líder de alguna ronda no logra transmitir a tiempo el punto de anclaje, lo que resulta en que el punto de anclaje no pueda ser ordenado y sea saltado, los vértices no ordenados de las rondas anteriores deben esperar a que el siguiente punto de anclaje sea ordenado. Esto reduce significativamente el rendimiento de la red de replicación geográfica.

Marco de Shoal

Shoal mejora Bullshark( o cualquier protocolo BFT basado en Narwhal) a través de una línea de producción, permitiendo que haya un ancla en cada ronda, 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 sin costo en el DAG, inclinándose a elegir 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:

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 de los líderes se introduce en DiemBFT y se formaliza en Carousel, seleccionando dinámicamente a los futuros líderes según el desempeño pasado de los validadores ( anclajes en Bullshark ). Aunque las divergencias en la identidad del líder no violan la seguridad, pueden dar lugar a un orden completamente diferente en Bullshark.

Estos desafíos han llevado a que las implementaciones de Bullshark en el entorno de producción actual no admitan estas características.

protocolo

Shoal se basa en la capacidad de realizar cálculos locales sobre DAG, logrando la capacidad de almacenar y reinterpretar la información de rondas anteriores. Basado en la percepción de que todos los validadores están de acuerdo con el primer punto de anclaje ordenado, Shoal combina secuencialmente múltiples instancias de Bullshark para su procesamiento en paralelo, 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

Línea de producción

V que mapea las rondas a los líderes. Shoal ejecuta instancias de Bullshark en secuencia, cada ancla de instancia está determinada previamente por el mapeo F. Cada instancia ordena un punto de anclaje, lo que desencadena el cambio a la siguiente instancia.

Shoal inicialmente lanzó la primera instancia de Bullshark en la primera ronda de DAG, funcionando hasta determinar el primer punto de anclaje ordenado ( suponiendo en la ronda r ). Todos los validadores acordaron este punto de anclaje, por lo tanto, pueden acordar de manera determinista reinterpretar el DAG a partir de la ronda r+1. Shoal lanza una nueva instancia de Bullshark en la ronda r+1.

En un escenario ideal, esto permite que Shoal ordene un ancla por ronda. El primer ancla es ordenado por la primera instancia, luego Shoal inicia una nueva instancia en la segunda ronda, ordenando el ancla de esa ronda, y así sucesivamente.

Reputación del líder

Cuando el proceso de ordenación de Bullshark salta puntos de anclaje, la latencia aumenta. En este caso, la técnica de tuberías 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 asigna puntajes a cada nodo de validación a través de un mecanismo de reputación, asegurando que, según el historial de actividades recientes, sea menos probable seleccionar a los líderes lentos correspondientes en el futuro. Los validadores que responden y participan en el protocolo obtienen puntuaciones altas, de lo contrario, se les asignan puntuaciones bajas.

Cada vez que se actualizan los puntajes, se recalcula de manera determinista el mapeo predefinido F de rondas a líderes, favoreciendo a los líderes de puntajes altos. Para que los validadores lleguen a un consenso sobre el nuevo mapeo, necesitan alcanzar un consenso sobre los puntajes, logrando así un consenso en la historia utilizada para derivar los puntajes.

En Shoal, la línea de producción y la reputación de liderazgo se combinan naturalmente, ya que ambas utilizan la misma tecnología central: reinterpretar el DAG después de llegar a un consenso sobre el primer ancla ordenada.

La única diferencia es que, después del anclaje de la ronda r, los validadores calculan el nuevo mapeo F' a partir de la historia causal de los puntos de anclaje ordenados de la ronda r. Luego, los nodos de validación utilizan la función de selección de anclajes actualizada F' para ejecutar una nueva instancia de Bullshark a partir de la ronda r+1.

Eliminar el tiempo de espera

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

El tiempo de espera también aumenta significativamente la latencia, ya que la configuración adecuada del tiempo de espera es importante, generalmente necesita ajustes dinámicos, y depende en gran medida del entorno ( red ). Antes de cambiar al siguiente líder, el protocolo pagará una penalización completa por la latencia del líder fallido. Por lo tanto, la configuración del tiempo de espera no puede ser demasiado conservadora, pero si es demasiado corta, el protocolo puede omitir buenos líderes.

Desafortunadamente, los protocolos basados en líderes ( como Hotstuff y Jolteon ) requieren esencialmente latencia para garantizar que el protocolo avance cada vez que un líder falla. Sin latencia, incluso un líder caído podría detener el protocolo indefinidamente. Dado que durante los períodos asíncronos no se puede distinguir entre líderes fallidos y lentos, la latencia puede llevar a que los nodos de validación roten a todos los líderes sin actividad de consenso.

En Bullshark, el tiempo de espera se utiliza para la construcción del DAG, para asegurar que durante la sincronización los líderes honestos añadan los puntos de anclaje al DAG lo suficientemente rápido para ser ordenados.

Shoal observa que la construcción de DAG proporciona un "reloj" para estimar la velocidad de la red. Sin pausas, mientras n-f validadores honestos sigan añadiendo vértices al DAG, las rondas continuarán avanzando. Aunque Bullshark puede no ser capaz de ordenar a la velocidad de la red ( debido a problemas de liderazgo ), el DAG aún crece a la velocidad de la red, a pesar de que algunos líderes tienen problemas o la red es asíncrona. Al final, cuando los líderes sin fallos transmiten lo suficientemente rápido los anclajes, toda la historia causal de los anclajes será ordenada.

En Shoal, evitar el tiempo de espera está estrechamente relacionado con la reputación del líder. Esperar repetidamente a líderes lentos aumentará la latencia, y el mecanismo de reputación del líder excluye a los validadores lentos de ser seleccionados como líderes. De esta manera, el sistema utiliza nodos de validación rápidos para operar a la velocidad de la red en todos los escenarios reales.

Es importante tener en cuenta que el resultado de imposibilidad de FLP indica que no puede haber un protocolo de consenso determinista que evite la latencia. Shoal no puede eludir este resultado, porque existe una cronología de eventos teóricamente adversos que puede impedir que se ordenen todos los anclajes. En cambio, después de un número configurable de saltos de anclaje, Shoal volverá a la latencia. De hecho, es extremadamente improbable que esto ocurra.

Respuesta General

El documento de Hotstuff popularizó el concepto de respuesta optimista, aunque no se define formalmente, pero intuitivamente significa que el protocolo puede funcionar a velocidad de red bajo condiciones óptimas con un líder rápido y una red sincronizada (.

Shoal ofrece una mejor propiedad, llamada capacidad de respuesta universal. En concreto, en comparación con Hotstuff, Shoal continuará funcionando a la velocidad de la red incluso si el líder falla durante un número configurable de rondas continuas o si la red experimenta períodos asíncronos.

La capacidad de respuesta general proporciona garantías de progreso estrictamente mejores durante períodos asíncronos y en caso de fallos del líder. Durante la sincronización con un líder lento, estas propiedades no son comparables, ya que dependen de cuán lento sea el líder. Sin embargo, dado el prestigio del líder, los líderes lentos en Shoal deberían aparecer raramente.

Evaluación

Aptos implementó Bullshark y Shoal sobre Quorum Store en Narwhal. A continuación se presentan algunos puntos destacados de la evaluación:

Primero, para la actuación