Aptos labs ha resuelto dos importantes problemas abiertos en DAG BFT, reduciendo en gran medida la latencia y, por primera vez, eliminando la necesidad de pausas en los protocolos prácticos deterministas. En general, esto mejora la latencia de Bullshark en un 40 % en el caso sin fallas y en un 80 % en el caso de fallas.
Shoal es un marco que mejora cualquier protocolo de consenso basado en Narwhal (por ejemplo, DAG-Rider, Tusk, Bullshark) a través de canalización y reputación de líder. La canalización reduce la latencia de pedidos de DAG mediante la introducción de un ancla por ronda, y la reputación del líder mejora aún más la latencia al garantizar que las anclas estén asociadas con los validadores más rápidos. Además, la reputación de líder permite que Shoal aproveche la construcción DAG asincrónica para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal proporcione una propiedad que llamamos Respuesta universal, que contiene la Respuesta optimista que generalmente se requiere.
Nuestra técnica es muy simple, implica ejecutar varias instancias del protocolo subyacente secuencialmente, una tras otra. Entonces, cuando se crea una instancia con Bullshark, obtenemos un grupo de "tiburones" que están haciendo una carrera de relevos.
Motivación
En la búsqueda de un alto rendimiento en las redes de cadena de bloques, ha habido un enfoque constante en la reducción de la complejidad de la comunicación. Sin embargo, este enfoque no resultó en un aumento significativo en el rendimiento. Por ejemplo, la implementación de Hotstuff en una versión anterior de Diem solo logró 3500 TPS, muy por debajo de nuestro objetivo de lograr más de 100k TPS.
Sin embargo, los avances recientes se derivan de la comprensión de que la propagación de datos es el principal cuello de botella de los protocolos basados en 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 los componentes de consenso solo solicitan una cantidad menor de metadatos. El papel Narwhal informa un rendimiento de 160.000 TPS.
En un artículo anterior, presentamos Quorum Store. Nuestra implementación de Narwhal desvincula la propagación de datos del consenso y cómo usamos esto para extender nuestro protocolo de consenso actual, Jolteon. Jolteon es un protocolo basado en líder que combina la ruta rápida lineal de Tendermint con cambios de vista de estilo PBFT para reducir la latencia de Hotstuff en un 33 %. Sin embargo, está claro que un protocolo de consenso basado en líderes no puede explotar completamente el potencial de rendimiento de Narwhal. A pesar de separar la propagación de datos del consenso, los líderes de Hotstuff/Jolteon todavía están limitados a medida que aumenta el rendimiento.
Por lo tanto, decidimos implementar Bullshark, un protocolo de consenso sin sobrecarga de comunicación, además de Narwhal DAG. Desafortunadamente, la estructura DAG que admite el alto rendimiento de Bullshark viene con una penalización de latencia del 50 % en comparación con Jolteon.
En esta publicación, describimos cómo Shoal logró una reducción drástica en la latencia de Bullshark.
Antecedentes DAG-BFT
Comencemos por comprender los antecedentes relevantes de este artículo. Para obtener una descripción detallada de Narwhal y Bullshark, consulte la publicación DAG Meets BFT.
Cada vértice en un Narwhal DAG está asociado con un número redondo. Para ingresar a la ronda r, un verificador primero debe obtener nf vértices pertenecientes a la ronda r-1. Cada verificador puede transmitir un vértice por ronda, y cada vértice se refiere a al menos nf vértices en la ronda anterior. Debido a la asincronía de la red, diferentes validadores pueden observar diferentes vistas locales del DAG en cualquier momento. Aquí hay una ilustración de una posible vista parcial:
Figura 1: La historia causal de los vértices identificados por el nodo 2 de validación de la ronda 2 está resaltada en verde
Una propiedad clave de los DAG no es la ambigüedad: dos validadores tienen exactamente el mismo historial causal de v si tienen el mismo vértice v en su vista local del DAG.
Orden total
Es posible acordar el orden total de todos los vértices en un DAG sin sobrecarga de comunicación adicional. Con este fin, 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 difiere en la estructura DAG, todos los protocolos de consenso basados en Narwhal existentes tienen la siguiente estructura:
Anclas predeterminadas, habrá un líder predeterminado cada pocas rondas (por ejemplo, dos rondas en Bullshark), y los vértices del líder se llaman anclas;
ordenar anclas, el verificador decide de forma independiente pero determinista qué anclas pedir y qué anclas omitir;
Ordenar historias causales, donde los validadores procesan su lista ordenada de anclas una por una, y para cada ancla, ordenan todos los vértices previamente desordenados en su historia causal por alguna regla determinista.
Figura 2: Ilustración de una posible vista parcial de un DAG en el protocolo Bullshark. En este ejemplo, se ordenan los anclajes rojo y amarillo, mientras que se omite el verde (no en el DAG). Por lo tanto, para ordenar el DAG, los validadores ordenan de forma determinista las historias causales de las anclas rojas primero, seguidas de las anclas amarillas.
La clave para satisfacer la seguridad es asegurarse de que en el paso (2) anterior, todos los validadores honestos creen una lista ordenada de anclas de modo que todas las listas compartan el mismo prefijo. En Shoal, hacemos las siguientes observaciones para todos los protocolos anteriores:
** Todos los validadores están de acuerdo con el primer ancla ordenada. **
Latencia del tiburón toro
La latencia de Bullshark depende del número de rondas entre anclas ordenadas en el DAG. Si bien la versión parcialmente síncrona más útil de Bullshark tiene una mejor latencia que la versión asíncrona, está lejos de ser óptima.
Problema 1: latencia de bloque promedio. En Bullshark, cada ronda par tiene un ancla, y los vértices de cada ronda impar se interpretan como votos. Por lo general, se necesitan dos rondas del DAG para ordenar anclas, sin embargo, los vértices en la historia causal de un ancla necesitan muchas más rondas para esperar a que se ordene un ancla. En el caso común, los vértices en rondas impares requieren tres rondas, mientras que los vértices que no son ancla en rondas pares requieren cuatro rondas (consulte la Figura 3).
Figura 3: En el caso común, los anclajes en la ronda i+1 deben clasificarse en dos rondas. Los vértices en la ronda i se ordenan simultáneamente, por lo que su latencia es de tres rondas. Sin embargo, los vértices en la ronda i+1 tienen que esperar a que se ordene el siguiente ancla (la de la ronda i+3), por lo que su retraso en la ordenación es de cuatro rondas.
Problema 2: Latencia del caso de falla, el análisis de latencia anterior se aplica al caso de no falla, por otro lado, si el líder de una ronda no transmite los anclajes lo suficientemente rápido, los anclajes no se pueden ordenar (y por lo tanto se omiten), por lo que todos los vértices no clasificados en rondas anteriores deben esperar a que se clasifique el siguiente ancla. Esto puede reducir significativamente el rendimiento de una red replicada geográficamente, especialmente porque Bullshark usa tiempos de espera para el líder.
Estructura del bajío
Shoal resuelve estos dos problemas de latencia al mejorar Bullshark (o cualquier otro protocolo BFT basado en Narwhal) mediante canalización, lo que permite un ancla en cada ronda y reduce la latencia de todos los vértices que no son ancla en el DAG a tres rondas. Shoal también introduce un mecanismo de reputación de líder sin gastos generales en el DAG, que sesga la selección a favor de los líderes rápidos.
desafío
En el contexto de los protocolos DAG, la canalización y la reputación del líder se consideran problemas difíciles por las siguientes razones:
La canalización anterior intenta modificar la lógica central de Bullshark, pero esto parece intrínsecamente imposible
Leader Reputation, introducido en DiemBFT y formalizado en Carousel, es la idea de seleccionar dinámicamente futuros líderes (anclas en Bullshark) en función del desempeño pasado de los validadores. Si bien el desacuerdo sobre la identidad del líder no viola la seguridad en estos protocolos, en Bullshark puede conducir a un orden completamente diferente, lo que llega al meollo de la cuestión, que es que la selección dinámica y determinista de los anclajes de las ruedas es la clave para resolver el consenso requerido. , mientras que los validadores deben acordar un historial ordenado para seleccionar futuras anclas.
Como prueba de la dificultad del problema, observamos que la implementación de Bullshark, incluida la implementación actual en producción, no admite estas características.
acuerdo
A pesar de los desafíos antes mencionados, resulta que las soluciones, como dice el refrán, están detrás de la simplicidad.
En Shoal, confiamos en la capacidad de realizar cálculos locales en el DAG e implementamos la capacidad de conservar y reinterpretar información de rondas anteriores. Con la idea central de que todos los validadores están de acuerdo con el primer anclaje ordenado, Shoal los canaliza al componer múltiples instancias de Bullshark en secuencia de modo que (1) el primer anclaje ordenado sea el punto de cambio para las instancias y (2) la historia causal del anclas se utiliza para calcular la reputación del líder.
Canalización
De manera similar a Bullshark, los validadores acuerdan a priori sobre los anclajes potenciales, es decir, existe un mapeo conocido F: R -> V rondas de mapeo a líderes. Shoal ejecuta instancias de Bullshark una tras otra de modo que para cada instancia el ancla está predeterminada por el mapa F. Cada instancia ordena un ancla, que desencadena un cambio a la siguiente instancia.
Inicialmente, Shoal lanza la primera instancia de Bullshark en la primera ronda del DAG y la ejecuta hasta que se identifica el primer ancla ordenada, digamos en la ronda r. Todos los validadores están de acuerdo con este ancla. Por lo tanto, todos los validadores pueden aceptar de manera determinista reinterpretar el DAG a partir de la ronda r+1. Shoal acaba de iniciar una nueva instancia de Bullshark en la ronda r+1.
En el mejor de los casos, esto le permite a Shoal pedir un ancla en cada ronda. Los anclajes de la primera ronda se ordenan por primera instancia. Luego, Shoal inicia una nueva instancia en la segunda ronda, que a su vez tiene un ancla ordenada por la instancia, luego otra nueva instancia ordena las anclas en la tercera ronda y el proceso continúa. Por favor, vea la ilustración a continuación:
Figura 4: Los vértices correspondientes a los líderes determinados por F están marcados con una corona. La primera instancia de Bullshark primero interpreta el DAG con los anclajes en las rondas 1, 3 y 5. Bullshark determina los anclajes en la ronda 1 (en marca de verificación verde mark) es el primero en ser ordenado en primera instancia. (Tenga en cuenta que, en el caso general, este ancla se puede omitir, mientras que otras anclas se ordenarán primero). Luego, el resto de la primera instancia se ignora y una nueva instancia de Bullshark comienza desde la ronda 2, los puntos de anclaje se marcan en las rondas 2 y 4.
Reputación de líder
Mayor latencia al omitir anclas durante la clasificación de Bullshark. En este caso, la técnica Pipelining es impotente porque no se puede iniciar una nueva instancia hasta que la instancia anterior haya ordenado un ancla. Shoal asegura que es menos probable que se elija al líder apropiado en el futuro para lidiar con un ancla perdida mediante el uso de un mecanismo de reputación para asignar a cada validador una puntuación basada en su historial de actividad reciente. A un validador que responda y participe en el protocolo se le otorgará una puntuación alta; de lo contrario, a un validador se le asignará una puntuación baja porque puede fallar, ser lento o ser malicioso.
La idea es volver a calcular de manera determinista el mapeo predefinido F de rondas a líderes en cada actualización de puntaje, favoreciendo a los líderes con puntajes más altos. Para que los validadores estén de acuerdo con el nuevo mapeo, deben estar de acuerdo con el puntaje y, por lo tanto, con el historial utilizado para obtener el puntaje.
En Shoal, la canalización y la reputación de liderazgo se pueden combinar naturalmente porque ambos usan la misma técnica central de reinterpretar un DAG después de acordar un ancla ordenada por primera vez.
De hecho, la única diferencia es que, después de ordenar los anclajes en la ronda r, el validador solo necesita calcular un nuevo mapeo F' de la ronda r+1 basado en la historia causal de los anclajes ordenados en la ronda r. Luego, el validador ejecuta una nueva instancia de Bullshark a partir de la ronda r+1 utilizando la función de selección de anclaje actualizada F'. Vea la imagen a continuación:
Figura 5. Los vértices correspondientes a los líderes identificados por F están marcados con coronas transparentes. La primera instancia de Bullshark ordena un ancla en la ronda 1, marcada con una marca de verificación verde, y luego calcula una nueva asignación F' basada en la información del historial causal del ancla. Los líderes determinados por F' están marcados con coronas de colores.
No más tiempos de espera
Los tiempos de espera juegan un papel crucial en todas las implementaciones de BFT parcialmente síncronas deterministas basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estado interno que debe administrarse y observarse, lo que complica el proceso de depuración y requiere más técnicas de observación.
Los tiempos de espera también pueden aumentar significativamente la latencia, ya que es importante configurarlos adecuadamente y, por lo general, deben ajustarse dinámicamente, ya que depende en gran medida del entorno (red). El protocolo paga al líder defectuoso la penalización por demora de tiempo de espera completa antes de pasar al siguiente líder. 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 buenos líderes. Por ejemplo, observamos que bajo mucha carga, los líderes en Jolteon/Hotstuff se vieron abrumados y los tiempos de espera expiraron antes de que pudieran impulsar el progreso.
Desafortunadamente, los protocolos basados en líderes, como Hotstuff y Jolteon, requieren inherentemente tiempos de espera para garantizar que el protocolo pueda progresar cada vez que el líder falla. Sin un tiempo de espera, incluso un líder estrellado podría detener el protocolo para siempre. Debido a la incapacidad de distinguir entre un líder defectuoso y un líder lento durante la sincronización, los tiempos de espera pueden hacer que los validadores vean cambios en todos los líderes sin un consenso vivo.
En Bullshark, los tiempos de espera se utilizan en la construcción de DAG para garantizar que, durante la sincronización, un líder honesto agregue anclas al DAG lo suficientemente rápido como para que se ordenen.
Observamos que la construcción DAG proporciona un "reloj" para estimar la velocidad de la red. En ausencia de pausas, las rondas continúan progresando siempre que los validadores honestos continúen agregando vértices al DAG. Si bien es posible que Bullshark no pueda ordenar a la velocidad de la red (debido a problemas con los líderes), el DAG aún crece a la velocidad de la red a pesar de algunos problemas con los líderes o que la red sea asíncrona. Eventualmente, cuando un líder libre de fallas difunda las anclas lo suficientemente rápido, se ordenará toda la historia causal de las anclas.
En nuestra evaluación, comparamos Bullshark con y sin tiempo de espera en los siguientes casos:
Líder rápido, es decir, al menos más rápido que otros validadores. En este caso, ambos métodos proporcionan la misma latencia porque se ordenan los anclajes y no se utilizan tiempos de espera.
Falso líder, en este caso Bullshark sin pausas proporciona una mejor latencia ya que los validadores saltarán inmediatamente sus anclas, mientras que los validadores con pausas esperarán su llegada antes de continuar Expect.
Líder lento, este es el único caso en el que Bullshark tiene un mejor rendimiento de tiempo de espera. Esto se debe a que, sin una pausa, el ancla puede omitirse porque el líder no puede transmitirla lo suficientemente rápido, mientras que con una pausa, los validadores esperarán al ancla.
En Shoal, evitar los tiempos muertos y la reputación de liderazgo van de la mano. Esperar repetidamente a un líder lento aumenta la latencia, y el mecanismo de reputación del líder impide que los validadores lentos sean elegidos como líderes. De esta forma, el sistema utiliza nodos de validación rápida para ejecutarse a la velocidad de la red en todos los escenarios del mundo real.
Tenga en cuenta que el resultado de imposibilidad de FLP muestra que ningún protocolo de consenso determinista puede evitar los tiempos de espera. Shoal no puede eludir este resultado porque existe un programa teórico de eventos adversarios que evitaría que se comanden todas las anclas. En su lugar, Shoal recurre a un tiempo de espera después de un número configurable de saltos de anclaje consecutivos. En la práctica, esto es extremadamente improbable que suceda.
Respuesta general
El artículo de Hotstuff popularizó el concepto de respuesta optimista que, aunque no se define formalmente, intuitivamente significa que el protocolo puede ejecutarse a la velocidad de la red en buenas condiciones, incluido un líder rápido y una red síncrona.
Shoal proporciona una propiedad aún mejor, que llamamos Respuesta universal. Específicamente, a diferencia de Hotstuff, Shoal continúa funcionando a la velocidad de la red incluso si el líder falla durante una cantidad configurable de rondas consecutivas o ciclos asíncronos por los que pasa la red. Vea una comparación más detallada en la siguiente tabla.
Tenga en cuenta que la capacidad de respuesta universal proporciona garantías de progreso estrictamente mejores durante los períodos asincrónicos y cuando el líder falla. Durante la sincronización con un líder lento, estas propiedades no son comparables porque depende de qué tan lento sea el líder. Sin embargo, dada la reputación del líder, los líderes lentos rara vez deberían aparecer en Shoal.
Evaluar
Implementamos Bullshark y Shoal además de nuestra implementación Narwhal Quorum Store. Puede encontrar una comparación detallada entre Shoal, Bullshark y Jolteon en la sección de evaluación del documento de Shoal, donde proporcionamos algunos aspectos destacados.
Primero, para demostrar el poder de la construcción DAG asincrónica, comparamos Bullshark con y sin pausas. El documento Bullshark completo asume una red asíncrona, pero proporciona un modo de ruta rápida, por lo que requiere pausas durante todas las rondas. A esta versión la llamamos Vanilla Bullshark. Observamos que para versiones hipotéticas de redes independientes parcialmente síncronas, no se requieren pausas en las rondas de votación. Llamamos a esta versión Vanilla Bullshark sin tiempo de espera de votación sin tiempo de espera de votación, Baseline Bullshark es la versión sin ningún tiempo de espera.
El siguiente gráfico compara el impacto de los tiempos de espera en la latencia de Bullshark con y sin fallas. Aparentemente, Baseline Bullshark (sin tiempo de espera) funciona mejor en caso de falla. Sin fallas, Baseline Bullshark es comparable a Vanilla Bullshark sin suspensión de votos. Esto se debe a que, como se mencionó anteriormente, sin un mecanismo de reputación de líder, los tiempos de espera pueden tener una ventaja en situaciones en las que el líder es bueno pero lento.
Figura 6.: Impacto de los tiempos de espera en la latencia de Bullshark sin fallas (izquierda) y con fallas (derecha), con 50 validadores en el caso de falla
A continuación, creamos una instancia de Shoal usando Baseline Bullshark (sin tiempo de espera) y demostramos las mejoras de latencia de canalización y el mecanismo de reputación de líder con y sin fallas, y para completarlo también lo comparamos con Jolteon con y sin fallas.
La Figura 7 a continuación muestra el caso sin fallas, y aunque tanto la canalización como la reputación de líder pueden reducir la latencia individualmente, combinarlos da como resultado la mejor latencia.
En cuanto a Jolteon, no puede escalar a más de 20 validadores, e incluso si se ejecuta en Quorum Store, solo puede lograr aproximadamente la mitad del rendimiento de Bullshark/Shoal, lo que elimina el cuello de botella de propagación de datos.
Los resultados muestran que Shoal mejora en gran medida la latencia de Bullshark. En cuanto a Jolteon, es importante tener en cuenta que aunque solo medimos la latencia de consenso. Dado que Jolteon no puede ejecutarse de forma nativa sobre un DAG, requiere una latencia adicional para desacoplar la propagación de datos, que no medimos. Por lo tanto, bajo una carga alta, Shoal debería coincidir con la latencia de extremo a extremo de Jolteon.
Figura 7: rendimiento y latencia sin fallas, Shoal PL y Shaol LR solo admiten canalización y reputación de líder, respectivamente.
La Figura 8 a continuación muestra un caso de falla con 50 validadores, donde el mecanismo de reputación de líder mejora significativamente la latencia al reducir la probabilidad de que un validador fallido sea elegido como líder. Tenga en cuenta que, con 16 fallas de 50, la latencia de Shoal fue un 65 % más baja que la de Baseline Bullshark.
Ver originales
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
4D Shoal Framework explicado: ¿Cómo reducir la latencia de Bullshark en Aptos?
Original: Laboratorios Aptos
Compilación: Aptos Global
Descripción general
Aptos labs ha resuelto dos importantes problemas abiertos en DAG BFT, reduciendo en gran medida la latencia y, por primera vez, eliminando la necesidad de pausas en los protocolos prácticos deterministas. En general, esto mejora la latencia de Bullshark en un 40 % en el caso sin fallas y en un 80 % en el caso de fallas.
Shoal es un marco que mejora cualquier protocolo de consenso basado en Narwhal (por ejemplo, DAG-Rider, Tusk, Bullshark) a través de canalización y reputación de líder. La canalización reduce la latencia de pedidos de DAG mediante la introducción de un ancla por ronda, y la reputación del líder mejora aún más la latencia al garantizar que las anclas estén asociadas con los validadores más rápidos. Además, la reputación de líder permite que Shoal aproveche la construcción DAG asincrónica para eliminar los tiempos de espera en todos los escenarios. Esto permite que Shoal proporcione una propiedad que llamamos Respuesta universal, que contiene la Respuesta optimista que generalmente se requiere.
Nuestra técnica es muy simple, implica ejecutar varias instancias del protocolo subyacente secuencialmente, una tras otra. Entonces, cuando se crea una instancia con Bullshark, obtenemos un grupo de "tiburones" que están haciendo una carrera de relevos.
Motivación
En la búsqueda de un alto rendimiento en las redes de cadena de bloques, ha habido un enfoque constante en la reducción de la complejidad de la comunicación. Sin embargo, este enfoque no resultó en un aumento significativo en el rendimiento. Por ejemplo, la implementación de Hotstuff en una versión anterior de Diem solo logró 3500 TPS, muy por debajo de nuestro objetivo de lograr más de 100k TPS.
Sin embargo, los avances recientes se derivan de la comprensión de que la propagación de datos es el principal cuello de botella de los protocolos basados en 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 los componentes de consenso solo solicitan una cantidad menor de metadatos. El papel Narwhal informa un rendimiento de 160.000 TPS.
En un artículo anterior, presentamos Quorum Store. Nuestra implementación de Narwhal desvincula la propagación de datos del consenso y cómo usamos esto para extender nuestro protocolo de consenso actual, Jolteon. Jolteon es un protocolo basado en líder que combina la ruta rápida lineal de Tendermint con cambios de vista de estilo PBFT para reducir la latencia de Hotstuff en un 33 %. Sin embargo, está claro que un protocolo de consenso basado en líderes no puede explotar completamente el potencial de rendimiento de Narwhal. A pesar de separar la propagación de datos del consenso, los líderes de Hotstuff/Jolteon todavía están limitados a medida que aumenta el rendimiento.
Por lo tanto, decidimos implementar Bullshark, un protocolo de consenso sin sobrecarga de comunicación, además de Narwhal DAG. Desafortunadamente, la estructura DAG que admite el alto rendimiento de Bullshark viene con una penalización de latencia del 50 % en comparación con Jolteon.
En esta publicación, describimos cómo Shoal logró una reducción drástica en la latencia de Bullshark.
Antecedentes DAG-BFT
Comencemos por comprender los antecedentes relevantes de este artículo. Para obtener una descripción detallada de Narwhal y Bullshark, consulte la publicación DAG Meets BFT.
Cada vértice en un Narwhal DAG está asociado con un número redondo. Para ingresar a la ronda r, un verificador primero debe obtener nf vértices pertenecientes a la ronda r-1. Cada verificador puede transmitir un vértice por ronda, y cada vértice se refiere a al menos nf vértices en la ronda anterior. Debido a la asincronía de la red, diferentes validadores pueden observar diferentes vistas locales del DAG en cualquier momento. Aquí hay una ilustración de una posible vista parcial:
Figura 1: La historia causal de los vértices identificados por el nodo 2 de validación de la ronda 2 está resaltada en verde
Una propiedad clave de los DAG no es la ambigüedad: dos validadores tienen exactamente el mismo historial causal de v si tienen el mismo vértice v en su vista local del DAG.
Orden total
Es posible acordar el orden total de todos los vértices en un DAG sin sobrecarga de comunicación adicional. Con este fin, 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 difiere en la estructura DAG, todos los protocolos de consenso basados en Narwhal existentes tienen la siguiente estructura:
Anclas predeterminadas, habrá un líder predeterminado cada pocas rondas (por ejemplo, dos rondas en Bullshark), y los vértices del líder se llaman anclas;
ordenar anclas, el verificador decide de forma independiente pero determinista qué anclas pedir y qué anclas omitir;
Ordenar historias causales, donde los validadores procesan su lista ordenada de anclas una por una, y para cada ancla, ordenan todos los vértices previamente desordenados en su historia causal por alguna regla determinista.
Figura 2: Ilustración de una posible vista parcial de un DAG en el protocolo Bullshark. En este ejemplo, se ordenan los anclajes rojo y amarillo, mientras que se omite el verde (no en el DAG). Por lo tanto, para ordenar el DAG, los validadores ordenan de forma determinista las historias causales de las anclas rojas primero, seguidas de las anclas amarillas.
La clave para satisfacer la seguridad es asegurarse de que en el paso (2) anterior, todos los validadores honestos creen una lista ordenada de anclas de modo que todas las listas compartan el mismo prefijo. En Shoal, hacemos las siguientes observaciones para todos los protocolos anteriores:
** Todos los validadores están de acuerdo con el primer ancla ordenada. **
Latencia del tiburón toro
La latencia de Bullshark depende del número de rondas entre anclas ordenadas en el DAG. Si bien la versión parcialmente síncrona más útil de Bullshark tiene una mejor latencia que la versión asíncrona, está lejos de ser óptima.
Problema 1: latencia de bloque promedio. En Bullshark, cada ronda par tiene un ancla, y los vértices de cada ronda impar se interpretan como votos. Por lo general, se necesitan dos rondas del DAG para ordenar anclas, sin embargo, los vértices en la historia causal de un ancla necesitan muchas más rondas para esperar a que se ordene un ancla. En el caso común, los vértices en rondas impares requieren tres rondas, mientras que los vértices que no son ancla en rondas pares requieren cuatro rondas (consulte la Figura 3).
Figura 3: En el caso común, los anclajes en la ronda i+1 deben clasificarse en dos rondas. Los vértices en la ronda i se ordenan simultáneamente, por lo que su latencia es de tres rondas. Sin embargo, los vértices en la ronda i+1 tienen que esperar a que se ordene el siguiente ancla (la de la ronda i+3), por lo que su retraso en la ordenación es de cuatro rondas.
Problema 2: Latencia del caso de falla, el análisis de latencia anterior se aplica al caso de no falla, por otro lado, si el líder de una ronda no transmite los anclajes lo suficientemente rápido, los anclajes no se pueden ordenar (y por lo tanto se omiten), por lo que todos los vértices no clasificados en rondas anteriores deben esperar a que se clasifique el siguiente ancla. Esto puede reducir significativamente el rendimiento de una red replicada geográficamente, especialmente porque Bullshark usa tiempos de espera para el líder.
Estructura del bajío
Shoal resuelve estos dos problemas de latencia al mejorar Bullshark (o cualquier otro protocolo BFT basado en Narwhal) mediante canalización, lo que permite un ancla en cada ronda y reduce la latencia de todos los vértices que no son ancla en el DAG a tres rondas. Shoal también introduce un mecanismo de reputación de líder sin gastos generales en el DAG, que sesga la selección a favor de los líderes rápidos.
desafío
En el contexto de los protocolos DAG, la canalización y la reputación del líder se consideran problemas difíciles por las siguientes razones:
La canalización anterior intenta modificar la lógica central de Bullshark, pero esto parece intrínsecamente imposible
Leader Reputation, introducido en DiemBFT y formalizado en Carousel, es la idea de seleccionar dinámicamente futuros líderes (anclas en Bullshark) en función del desempeño pasado de los validadores. Si bien el desacuerdo sobre la identidad del líder no viola la seguridad en estos protocolos, en Bullshark puede conducir a un orden completamente diferente, lo que llega al meollo de la cuestión, que es que la selección dinámica y determinista de los anclajes de las ruedas es la clave para resolver el consenso requerido. , mientras que los validadores deben acordar un historial ordenado para seleccionar futuras anclas.
Como prueba de la dificultad del problema, observamos que la implementación de Bullshark, incluida la implementación actual en producción, no admite estas características.
acuerdo
A pesar de los desafíos antes mencionados, resulta que las soluciones, como dice el refrán, están detrás de la simplicidad.
En Shoal, confiamos en la capacidad de realizar cálculos locales en el DAG e implementamos la capacidad de conservar y reinterpretar información de rondas anteriores. Con la idea central de que todos los validadores están de acuerdo con el primer anclaje ordenado, Shoal los canaliza al componer múltiples instancias de Bullshark en secuencia de modo que (1) el primer anclaje ordenado sea el punto de cambio para las instancias y (2) la historia causal del anclas se utiliza para calcular la reputación del líder.
Canalización
De manera similar a Bullshark, los validadores acuerdan a priori sobre los anclajes potenciales, es decir, existe un mapeo conocido F: R -> V rondas de mapeo a líderes. Shoal ejecuta instancias de Bullshark una tras otra de modo que para cada instancia el ancla está predeterminada por el mapa F. Cada instancia ordena un ancla, que desencadena un cambio a la siguiente instancia.
Inicialmente, Shoal lanza la primera instancia de Bullshark en la primera ronda del DAG y la ejecuta hasta que se identifica el primer ancla ordenada, digamos en la ronda r. Todos los validadores están de acuerdo con este ancla. Por lo tanto, todos los validadores pueden aceptar de manera determinista reinterpretar el DAG a partir de la ronda r+1. Shoal acaba de iniciar una nueva instancia de Bullshark en la ronda r+1.
En el mejor de los casos, esto le permite a Shoal pedir un ancla en cada ronda. Los anclajes de la primera ronda se ordenan por primera instancia. Luego, Shoal inicia una nueva instancia en la segunda ronda, que a su vez tiene un ancla ordenada por la instancia, luego otra nueva instancia ordena las anclas en la tercera ronda y el proceso continúa. Por favor, vea la ilustración a continuación:
Figura 4: Los vértices correspondientes a los líderes determinados por F están marcados con una corona. La primera instancia de Bullshark primero interpreta el DAG con los anclajes en las rondas 1, 3 y 5. Bullshark determina los anclajes en la ronda 1 (en marca de verificación verde mark) es el primero en ser ordenado en primera instancia. (Tenga en cuenta que, en el caso general, este ancla se puede omitir, mientras que otras anclas se ordenarán primero). Luego, el resto de la primera instancia se ignora y una nueva instancia de Bullshark comienza desde la ronda 2, los puntos de anclaje se marcan en las rondas 2 y 4.
Reputación de líder
Mayor latencia al omitir anclas durante la clasificación de Bullshark. En este caso, la técnica Pipelining es impotente porque no se puede iniciar una nueva instancia hasta que la instancia anterior haya ordenado un ancla. Shoal asegura que es menos probable que se elija al líder apropiado en el futuro para lidiar con un ancla perdida mediante el uso de un mecanismo de reputación para asignar a cada validador una puntuación basada en su historial de actividad reciente. A un validador que responda y participe en el protocolo se le otorgará una puntuación alta; de lo contrario, a un validador se le asignará una puntuación baja porque puede fallar, ser lento o ser malicioso.
La idea es volver a calcular de manera determinista el mapeo predefinido F de rondas a líderes en cada actualización de puntaje, favoreciendo a los líderes con puntajes más altos. Para que los validadores estén de acuerdo con el nuevo mapeo, deben estar de acuerdo con el puntaje y, por lo tanto, con el historial utilizado para obtener el puntaje.
En Shoal, la canalización y la reputación de liderazgo se pueden combinar naturalmente porque ambos usan la misma técnica central de reinterpretar un DAG después de acordar un ancla ordenada por primera vez.
De hecho, la única diferencia es que, después de ordenar los anclajes en la ronda r, el validador solo necesita calcular un nuevo mapeo F' de la ronda r+1 basado en la historia causal de los anclajes ordenados en la ronda r. Luego, el validador ejecuta una nueva instancia de Bullshark a partir de la ronda r+1 utilizando la función de selección de anclaje actualizada F'. Vea la imagen a continuación:
Figura 5. Los vértices correspondientes a los líderes identificados por F están marcados con coronas transparentes. La primera instancia de Bullshark ordena un ancla en la ronda 1, marcada con una marca de verificación verde, y luego calcula una nueva asignación F' basada en la información del historial causal del ancla. Los líderes determinados por F' están marcados con coronas de colores.
No más tiempos de espera
Los tiempos de espera juegan un papel crucial en todas las implementaciones de BFT parcialmente síncronas deterministas basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estado interno que debe administrarse y observarse, lo que complica el proceso de depuración y requiere más técnicas de observación.
Los tiempos de espera también pueden aumentar significativamente la latencia, ya que es importante configurarlos adecuadamente y, por lo general, deben ajustarse dinámicamente, ya que depende en gran medida del entorno (red). El protocolo paga al líder defectuoso la penalización por demora de tiempo de espera completa antes de pasar al siguiente líder. 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 buenos líderes. Por ejemplo, observamos que bajo mucha carga, los líderes en Jolteon/Hotstuff se vieron abrumados y los tiempos de espera expiraron antes de que pudieran impulsar el progreso.
Desafortunadamente, los protocolos basados en líderes, como Hotstuff y Jolteon, requieren inherentemente tiempos de espera para garantizar que el protocolo pueda progresar cada vez que el líder falla. Sin un tiempo de espera, incluso un líder estrellado podría detener el protocolo para siempre. Debido a la incapacidad de distinguir entre un líder defectuoso y un líder lento durante la sincronización, los tiempos de espera pueden hacer que los validadores vean cambios en todos los líderes sin un consenso vivo.
En Bullshark, los tiempos de espera se utilizan en la construcción de DAG para garantizar que, durante la sincronización, un líder honesto agregue anclas al DAG lo suficientemente rápido como para que se ordenen.
Observamos que la construcción DAG proporciona un "reloj" para estimar la velocidad de la red. En ausencia de pausas, las rondas continúan progresando siempre que los validadores honestos continúen agregando vértices al DAG. Si bien es posible que Bullshark no pueda ordenar a la velocidad de la red (debido a problemas con los líderes), el DAG aún crece a la velocidad de la red a pesar de algunos problemas con los líderes o que la red sea asíncrona. Eventualmente, cuando un líder libre de fallas difunda las anclas lo suficientemente rápido, se ordenará toda la historia causal de las anclas.
En nuestra evaluación, comparamos Bullshark con y sin tiempo de espera en los siguientes casos:
Líder rápido, es decir, al menos más rápido que otros validadores. En este caso, ambos métodos proporcionan la misma latencia porque se ordenan los anclajes y no se utilizan tiempos de espera.
Falso líder, en este caso Bullshark sin pausas proporciona una mejor latencia ya que los validadores saltarán inmediatamente sus anclas, mientras que los validadores con pausas esperarán su llegada antes de continuar Expect.
Líder lento, este es el único caso en el que Bullshark tiene un mejor rendimiento de tiempo de espera. Esto se debe a que, sin una pausa, el ancla puede omitirse porque el líder no puede transmitirla lo suficientemente rápido, mientras que con una pausa, los validadores esperarán al ancla.
En Shoal, evitar los tiempos muertos y la reputación de liderazgo van de la mano. Esperar repetidamente a un líder lento aumenta la latencia, y el mecanismo de reputación del líder impide que los validadores lentos sean elegidos como líderes. De esta forma, el sistema utiliza nodos de validación rápida para ejecutarse a la velocidad de la red en todos los escenarios del mundo real.
Tenga en cuenta que el resultado de imposibilidad de FLP muestra que ningún protocolo de consenso determinista puede evitar los tiempos de espera. Shoal no puede eludir este resultado porque existe un programa teórico de eventos adversarios que evitaría que se comanden todas las anclas. En su lugar, Shoal recurre a un tiempo de espera después de un número configurable de saltos de anclaje consecutivos. En la práctica, esto es extremadamente improbable que suceda.
Respuesta general
El artículo de Hotstuff popularizó el concepto de respuesta optimista que, aunque no se define formalmente, intuitivamente significa que el protocolo puede ejecutarse a la velocidad de la red en buenas condiciones, incluido un líder rápido y una red síncrona.
Shoal proporciona una propiedad aún mejor, que llamamos Respuesta universal. Específicamente, a diferencia de Hotstuff, Shoal continúa funcionando a la velocidad de la red incluso si el líder falla durante una cantidad configurable de rondas consecutivas o ciclos asíncronos por los que pasa la red. Vea una comparación más detallada en la siguiente tabla.
Tenga en cuenta que la capacidad de respuesta universal proporciona garantías de progreso estrictamente mejores durante los períodos asincrónicos y cuando el líder falla. Durante la sincronización con un líder lento, estas propiedades no son comparables porque depende de qué tan lento sea el líder. Sin embargo, dada la reputación del líder, los líderes lentos rara vez deberían aparecer en Shoal.
Evaluar
Implementamos Bullshark y Shoal además de nuestra implementación Narwhal Quorum Store. Puede encontrar una comparación detallada entre Shoal, Bullshark y Jolteon en la sección de evaluación del documento de Shoal, donde proporcionamos algunos aspectos destacados.
Primero, para demostrar el poder de la construcción DAG asincrónica, comparamos Bullshark con y sin pausas. El documento Bullshark completo asume una red asíncrona, pero proporciona un modo de ruta rápida, por lo que requiere pausas durante todas las rondas. A esta versión la llamamos Vanilla Bullshark. Observamos que para versiones hipotéticas de redes independientes parcialmente síncronas, no se requieren pausas en las rondas de votación. Llamamos a esta versión Vanilla Bullshark sin tiempo de espera de votación sin tiempo de espera de votación, Baseline Bullshark es la versión sin ningún tiempo de espera.
El siguiente gráfico compara el impacto de los tiempos de espera en la latencia de Bullshark con y sin fallas. Aparentemente, Baseline Bullshark (sin tiempo de espera) funciona mejor en caso de falla. Sin fallas, Baseline Bullshark es comparable a Vanilla Bullshark sin suspensión de votos. Esto se debe a que, como se mencionó anteriormente, sin un mecanismo de reputación de líder, los tiempos de espera pueden tener una ventaja en situaciones en las que el líder es bueno pero lento.
Figura 6.: Impacto de los tiempos de espera en la latencia de Bullshark sin fallas (izquierda) y con fallas (derecha), con 50 validadores en el caso de falla
A continuación, creamos una instancia de Shoal usando Baseline Bullshark (sin tiempo de espera) y demostramos las mejoras de latencia de canalización y el mecanismo de reputación de líder con y sin fallas, y para completarlo también lo comparamos con Jolteon con y sin fallas.
La Figura 7 a continuación muestra el caso sin fallas, y aunque tanto la canalización como la reputación de líder pueden reducir la latencia individualmente, combinarlos da como resultado la mejor latencia.
En cuanto a Jolteon, no puede escalar a más de 20 validadores, e incluso si se ejecuta en Quorum Store, solo puede lograr aproximadamente la mitad del rendimiento de Bullshark/Shoal, lo que elimina el cuello de botella de propagación de datos.
Los resultados muestran que Shoal mejora en gran medida la latencia de Bullshark. En cuanto a Jolteon, es importante tener en cuenta que aunque solo medimos la latencia de consenso. Dado que Jolteon no puede ejecutarse de forma nativa sobre un DAG, requiere una latencia adicional para desacoplar la propagación de datos, que no medimos. Por lo tanto, bajo una carga alta, Shoal debería coincidir con la latencia de extremo a extremo de Jolteon.
Figura 7: rendimiento y latencia sin fallas, Shoal PL y Shaol LR solo admiten canalización y reputación de líder, respectivamente.
La Figura 8 a continuación muestra un caso de falla con 50 validadores, donde el mecanismo de reputación de líder mejora significativamente la latencia al reducir la probabilidad de que un validador fallido sea elegido como líder. Tenga en cuenta que, con 16 fallas de 50, la latencia de Shoal fue un 65 % más baja que la de Baseline Bullshark.