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 tiempos de espera en protocolos prácticos deterministas. En general, mejoró la latencia de Bullshark 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 la canalización y la reputación del líder, como DAG-Rider, Tusk, Bullshark ). La canalizació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 la 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 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 la propiedad que llamamos respuesta universal, que contiene la respuesta optimista que normalmente se requiere.
La 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 participando en una carrera de relevos.
Motivación
Al buscar un alto rendimiento en redes blockchain, la gente ha estado enfocada en reducir la complejidad de la comunicación. Sin embargo, este enfoque no ha traído 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.
El último 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 puede beneficiarse de la paralelización. El sistema Narwhal separa la propagación de datos de la lógica de consenso principal, proponiendo 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 reporta una capacidad de 160,000 TPS.
Anteriormente se presentó Quorum Store, es decir, la implementación de Narwhal que separa la propagación de datos del 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 el cambio de vista al 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 completamente 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ó implementar 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 logra reducir significativamente la latencia de Bullshark.
Fondo 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, 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 propiedad clave del DAG no es ambigua: si dos nodos de validación tienen el mismo vértice v en su vista local del DAG, entonces tienen la misma historia causal de v.
Orden total
Se puede alcanzar un consenso sobre el orden total de todos los vértices en el DAG sin costos 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 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:
Punto de anclaje programado: cada pocas rondas habrá un líder predefinido, y el vértice del líder se llama punto de anclaje;
Puntos de anclaje de ordenación: los validadores deciden de manera independiente pero determinista qué puntos de anclaje ordenar y cuáles omitir;
Historia causal ordenada: los validadores procesan uno tras otro su lista de puntos de anclaje ordenados y ordenan todos 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), todos los nodos de validación honestos creen una lista de puntos de anclaje ordenada, de modo que todas las listas compartan el mismo prefijo. En Shoal, se hacen las siguientes observaciones sobre todos los protocolos anteriores:
Todos los validadores acuerdan 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 más práctica de Bullshark tiene mejor latencia que la versión asíncrona, está lejos de ser óptima.
Pregunta 1: Latencia promedio de bloques. En Bullshark, cada ronda par tiene un punto de anclaje, y los vértices de cada ronda impar se interpretan como votos. En situaciones comunes, se requieren dos rondas de DAG para ordenar los puntos de anclaje; sin embargo, los vértices en la historia causal de anclaje requieren más rondas para esperar que el anclaje sea ordenado. En situaciones comunes, los vértices en la ronda impar requieren tres rondas, mientras que los vértices no ancla en la ronda par requieren cuatro rondas.
Pregunta 2: latencia de casos de falla, el análisis de latencia anterior se aplica a situaciones sin fallas, por otro lado, si el líder de una ronda no logra transmitir 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 en las rondas anteriores deben esperar a que se ordene el siguiente ancla. Esto 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 Shoal
Shoal ha mejorado Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de una línea de producción, permitiendo que haya 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 ha introducido un mecanismo de reputación de líder 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 canalización y la reputación del líder se consideran problemas difíciles, por las siguientes razones:
Las líneas de producción anteriores intentaron modificar la lógica central de Bullshark, pero esto parece ser esencialmente imposible.
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, pueden llevar a un orden completamente diferente, lo que plantea el núcleo del problema: seleccionar de manera dinámica y determinista el ancla del ciclo 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, la implementación de Bullshark ( no incluye actualmente las características que se están implementando en el entorno de producción ).
Protocolo
En Shoal, confiamos en la capacidad de realizar cálculos locales sobre el DAG y hemos logrado preservar y reinterpretar la información de rondas anteriores. Con la comprensión central de que todos los validadores acuerdan el primer ancla ordenada, Shoal combina secuencialmente múltiples instancias de Bullshark para procesarlas en pipeline, haciendo 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
Al igual que Bullshark, los validadores llegan a un consenso a priori sobre los puntos de anclaje potenciales, es decir, hay un mapeo conocido F: R -\u003e 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 es predefinido por el mapeo F. Cada instancia ordena un ancla, lo que desencadena el cambio a la siguiente instancia.
Inicialmente, 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 acordaron este punto de anclaje. Por lo tanto, todos los validadores pueden acordar de manera definitiva 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 comienza una nueva instancia en la segunda ronda, que a su vez tiene un punto de anclaje, el cual es ordenado por esa instancia, y luego, otra nueva instancia ordena puntos de anclaje en la tercera ronda, y luego el proceso continúa.
Reputación del líder
Durante el ordenamiento de Bullshark, al omitir un anclaje, la latencia aumenta. En este caso, la técnica de tubería es impotente, ya que no se puede iniciar una nueva instancia antes de que se ordene el anclaje de la instancia anterior. Shoal asegura que es menos probable que se elija al líder correspondiente para manejar los anclajes perdidos en el futuro, asignando una puntuación 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 altas puntuaciones; de lo contrario, los nodos de validación recibirán bajas puntuaciones, ya que pueden colapsar, ser lentos o actuar de manera maliciosa.
Su filosofía consiste en recalcular de manera determinista el mapeo predefinido F desde la ronda hasta el líder 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 consenso sobre la puntuación, logrando así un acuerdo sobre la historia utilizada para derivar las puntuaciones.
En Shoal, las líneas de producción y la reputación de liderazgo pueden combinarse de forma natural, ya que ambas utilizan la misma tecnología central, es decir, 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, el validador solo necesita calcular un nuevo mapeo F' a partir de la historia causal de los puntos de anclaje ordenados en la ronda r, comenzando desde la ronda r+1. 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.
No hay más tiempo de espera
El tiempo de espera juega un papel crucial en todas las implementaciones BFT de sincronización determinista basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estados internos que deben 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 depende altamente del entorno ( red ). Antes de pasar al siguiente líder, el protocolo paga la penalización completa por la latencia de tiempo de espera del líder que falló. 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, observamos
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
El marco Shoal reduce significativamente la latencia del consenso de Bullshark en Aptos, mejorando entre un 40% y un 80%.
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 tiempos de espera en protocolos prácticos deterministas. En general, mejoró la latencia de Bullshark 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 la canalización y la reputación del líder, como DAG-Rider, Tusk, Bullshark ). La canalizació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 la 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 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 la propiedad que llamamos respuesta universal, que contiene la respuesta optimista que normalmente se requiere.
La 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 participando en una carrera de relevos.
Motivación
Al buscar un alto rendimiento en redes blockchain, la gente ha estado enfocada en reducir la complejidad de la comunicación. Sin embargo, este enfoque no ha traído 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.
El último 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 puede beneficiarse de la paralelización. El sistema Narwhal separa la propagación de datos de la lógica de consenso principal, proponiendo 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 reporta una capacidad de 160,000 TPS.
Anteriormente se presentó Quorum Store, es decir, la implementación de Narwhal que separa la propagación de datos del 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 el cambio de vista al 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 completamente 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ó implementar 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 logra reducir significativamente la latencia de Bullshark.
Fondo 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, 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 propiedad clave del DAG no es ambigua: si dos nodos de validación tienen el mismo vértice v en su vista local del DAG, entonces tienen la misma historia causal de v.
Orden total
Se puede alcanzar un consenso sobre el orden total de todos los vértices en el DAG sin costos 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 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:
Punto de anclaje programado: cada pocas rondas habrá un líder predefinido, y el vértice del líder se llama punto de anclaje;
Puntos de anclaje de ordenación: los validadores deciden de manera independiente pero determinista qué puntos de anclaje ordenar y cuáles omitir;
Historia causal ordenada: los validadores procesan uno tras otro su lista de puntos de anclaje ordenados y ordenan todos 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), todos los nodos de validación honestos creen una lista de puntos de anclaje ordenada, de modo que todas las listas compartan el mismo prefijo. En Shoal, se hacen las siguientes observaciones sobre todos los protocolos anteriores:
Todos los validadores acuerdan 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 más práctica de Bullshark tiene mejor latencia que la versión asíncrona, está lejos de ser óptima.
Pregunta 1: Latencia promedio de bloques. En Bullshark, cada ronda par tiene un punto de anclaje, y los vértices de cada ronda impar se interpretan como votos. En situaciones comunes, se requieren dos rondas de DAG para ordenar los puntos de anclaje; sin embargo, los vértices en la historia causal de anclaje requieren más rondas para esperar que el anclaje sea ordenado. En situaciones comunes, los vértices en la ronda impar requieren tres rondas, mientras que los vértices no ancla en la ronda par requieren cuatro rondas.
Pregunta 2: latencia de casos de falla, el análisis de latencia anterior se aplica a situaciones sin fallas, por otro lado, si el líder de una ronda no logra transmitir 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 en las rondas anteriores deben esperar a que se ordene el siguiente ancla. Esto 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 Shoal
Shoal ha mejorado Bullshark( o cualquier otro protocolo BFT basado en Narwhal) a través de una línea de producción, permitiendo que haya 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 ha introducido un mecanismo de reputación de líder 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 canalización y la reputación del líder se consideran problemas difíciles, por las siguientes razones:
Las líneas de producción anteriores intentaron modificar la lógica central de Bullshark, pero esto parece ser esencialmente imposible.
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, pueden llevar a un orden completamente diferente, lo que plantea el núcleo del problema: seleccionar de manera dinámica y determinista el ancla del ciclo 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, la implementación de Bullshark ( no incluye actualmente las características que se están implementando en el entorno de producción ).
Protocolo
En Shoal, confiamos en la capacidad de realizar cálculos locales sobre el DAG y hemos logrado preservar y reinterpretar la información de rondas anteriores. Con la comprensión central de que todos los validadores acuerdan el primer ancla ordenada, Shoal combina secuencialmente múltiples instancias de Bullshark para procesarlas en pipeline, haciendo 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
Al igual que Bullshark, los validadores llegan a un consenso a priori sobre los puntos de anclaje potenciales, es decir, hay un mapeo conocido F: R -\u003e 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 es predefinido por el mapeo F. Cada instancia ordena un ancla, lo que desencadena el cambio a la siguiente instancia.
Inicialmente, 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 acordaron este punto de anclaje. Por lo tanto, todos los validadores pueden acordar de manera definitiva 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 comienza una nueva instancia en la segunda ronda, que a su vez tiene un punto de anclaje, el cual es ordenado por esa instancia, y luego, otra nueva instancia ordena puntos de anclaje en la tercera ronda, y luego el proceso continúa.
Reputación del líder
Durante el ordenamiento de Bullshark, al omitir un anclaje, la latencia aumenta. En este caso, la técnica de tubería es impotente, ya que no se puede iniciar una nueva instancia antes de que se ordene el anclaje de la instancia anterior. Shoal asegura que es menos probable que se elija al líder correspondiente para manejar los anclajes perdidos en el futuro, asignando una puntuación 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 altas puntuaciones; de lo contrario, los nodos de validación recibirán bajas puntuaciones, ya que pueden colapsar, ser lentos o actuar de manera maliciosa.
Su filosofía consiste en recalcular de manera determinista el mapeo predefinido F desde la ronda hasta el líder 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 consenso sobre la puntuación, logrando así un acuerdo sobre la historia utilizada para derivar las puntuaciones.
En Shoal, las líneas de producción y la reputación de liderazgo pueden combinarse de forma natural, ya que ambas utilizan la misma tecnología central, es decir, 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, el validador solo necesita calcular un nuevo mapeo F' a partir de la historia causal de los puntos de anclaje ordenados en la ronda r, comenzando desde la ronda r+1. 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.
No hay más tiempo de espera
El tiempo de espera juega un papel crucial en todas las implementaciones BFT de sincronización determinista basadas en líderes. Sin embargo, la complejidad que introducen aumenta la cantidad de estados internos que deben 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 depende altamente del entorno ( red ). Antes de pasar al siguiente líder, el protocolo paga la penalización completa por la latencia de tiempo de espera del líder que falló. 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, observamos