Shoal: pipelining de anclas y reputación de líderes sobre DAG-BFT

Los protocolos de consenso sobre un DAG separan dos trabajos. Narwhal se encarga de difundir y certificar los datos: en cada ronda cada validador emite un vértice que referencia al menos $n - f$ vértices de la ronda anterior, y el resultado es un grafo dirigido acíclico que todas las réplicas correctas terminan viendo de forma consistente. [3] Encima de ese grafo, un protocolo como Bullshark decide el orden total sin enviar mensajes propios: cada réplica interpreta su copia local del DAG y llega al mismo orden que las demás. [2]

Ese diseño es muy eficiente en throughput, pero deja dos fuentes de latencia que Shoal ataca directamente: no todas las rondas tienen un ancla y, cuando el líder de un ancla está caído o es lento, el protocolo puede quedarse esperando un timeout antes de avanzar. Shoal, propuesto por Spiegelman, Arun, Gelashvili y Li en 2023, es un marco que se coloca por encima de cualquier protocolo DAG-BFT basado en Narwhal y añade dos mecanismos: pipelining y reputación de líderes. [1]

Dónde pierde tiempo Bullshark

En la versión parcialmente síncrona de Bullshark, las rondas pares tienen un líder predefinido cuyo vértice es el ancla de esa ronda, y los vértices de la ronda impar siguiente funcionan como votos: si al menos $f + 1$ vértices de la ronda siguiente referencian al ancla, una réplica la confirma. [2] Al confirmar un ancla, la réplica revisa las anclas anteriores todavía no ordenadas y ordena primero las que tienen un camino hasta la nueva; después ordena de forma determinista la historia causal de cada ancla. [2]

La consecuencia es que un vértice cualquiera, que no es ancla, no queda ordenado por sí mismo: tiene que esperar a que alguna ancla posterior lo incluya en su historia causal y a que esa ancla reciba sus votos. Como solo hay ancla en una de cada dos rondas, los vértices que no son ancla pagan rondas extra de espera respecto de las propias anclas. [1]

El segundo problema aparece con fallas. Para garantizar liveness bajo sincronía parcial, Bullshark hace que las réplicas esperen el ancla de la ronda, o los votos sobre ella, hasta que vence un timeout. [2] Si el líder asignado está caído, cada vez que le toque ser ancla la red entera pierde el tiempo del timeout. Con un calendario de líderes fijo, como un round-robin, un validador caído vuelve a provocar esa espera periódicamente. Por qué un valor fijo de timeout es un compromiso incómodo se discute en Por qué no timeouts fijos.

Pipelining: una instancia nueva en cada ronda

La idea central de Shoal es tratar al protocolo base como una caja negra que se puede reiniciar. Una instancia de Bullshark empieza en cierta ronda del DAG y corre hasta ordenar su primera ancla. En ese momento la instancia termina y comienza otra nueva, que interpreta el mismo DAG a partir de la ronda siguiente a esa ancla. [1] No se crea un DAG nuevo ni se detiene la difusión de Narwhal: solo cambia la forma en que las réplicas leen lo que ya tienen.

Si todo va bien, la primera ancla de cada instancia se ordena en la primera ronda de esa instancia, y la instancia siguiente empieza en la ronda inmediatamente posterior. El efecto es que, en el caso favorable, aparece un ancla en cada ronda en lugar de una cada dos. [1] Para los vértices que no son ancla esto importa mucho: la próxima ancla que puede incluirlos en su historia causal está más cerca, y por eso esperan menos.

El punto delicado es la seguridad del cambio de instancia. Si dos réplicas correctas creyeran que la instancia siguiente empieza en rondas distintas, interpretarían el DAG de forma distinta y podrían ordenar cosas en otro orden. Shoal evita ese riesgo apoyándose en la propiedad que ya garantiza el protocolo base: todas las réplicas correctas ordenan las mismas anclas en el mismo orden. [2] Como la primera ancla ordenada de cada instancia es la misma para todas, también coincide la ronda donde arranca la siguiente, y el cambio de instancia no requiere comunicación. [1]

Reputación de líderes calculada desde la historia causal

Pipelining reduce la espera en el caso favorable, pero no resuelve el líder caído: si el calendario sigue eligiendo a un validador que no responde, su ronda vuelve a costar un timeout. La segunda pieza de Shoal es asignar las anclas según una reputación que favorece a los validadores que han mostrado actividad reciente en el DAG. [1]

La idea de reputación no nace con Shoal. DiemBFT v4, un descendiente de HotStuff diseñado para producción, ya describe un mecanismo de reputación para elegir líderes a partir de información confirmada, de modo que los validadores que no participan dejen de ser seleccionados. [4] El contexto productivo de esa familia se resume en DiemBFT, Jolteon y Ditto en producción.

La dificultad en un DAG es la misma que en un protocolo con líder: todas las réplicas correctas deben estar de acuerdo en quién es el ancla de cada ronda. Si cada réplica puntuara a los validadores con lo que observa localmente, por ejemplo latencias medidas o vértices recibidos tarde, dos réplicas podrían asignar líderes distintos a la misma ronda y romper la interpretación común del DAG. Shoal resuelve ese acuerdo calculando la reputación solo sobre la historia causal que ya fue ordenada, que es idéntica en todas las réplicas correctas. [1]

Aquí es donde las dos mejoras encajan. El momento natural para actualizar el calendario es justamente el cambio de instancia: cuando se ordena la primera ancla de una instancia, cada réplica actualiza las puntuaciones con la nueva historia ordenada y la instancia siguiente arranca con un calendario de anclas que refleja esas puntuaciones. [1] No hace falta un subprotocolo de votación ni mensajes de medición: el DAG ya contiene la evidencia de quién participó, porque los vértices de cada validador y sus referencias quedan registrados en el grafo. Para una explicación de por qué el DAG funciona como un registro de causalidad, ver El DAG como máquina del tiempo.

Timeouts que casi nunca vencen

Shoal no elimina los timeouts del modelo: bajo sincronía parcial siguen siendo la red de seguridad que garantiza liveness. Lo que cambia es cuántas veces llegan a vencer. Los autores llaman a esta propiedad prevalent responsiveness: el protocolo avanza a la velocidad real de la red en casi todos los escenarios, y esperar un timeout queda reservado a casos poco comunes. [1]

El razonamiento es directo. Un validador caído deja de producir vértices, así que deja de aparecer en la historia ordenada y su reputación cae. Tras la siguiente actualización del calendario deja de ser elegido como ancla, y las rondas que antes habrían esperado su timeout pasan a tener un ancla activa que se ordena en cuanto llegan sus votos. [1] El costo de una falla se paga, en esencia, mientras la reputación todavía no la refleja, en lugar de pagarse cada vez que el validador caído vuelve a tocar en un round-robin.

Esto conecta con una tensión clásica que este curso recorre desde HotStuff: los protocolos parcialmente síncronos necesitan timeouts para liveness, pero cada timeout que vence es latencia perdida. Tusk evita los timeouts usando aleatoriedad asíncrona; Shoal se queda en el modelo parcialmente síncrono y reduce la frecuencia con que los timeouts vencen. [3] [1]

Límites y lectura crítica

Conviene leer Shoal con precisión. Primero, no cambia el modelo de fallas ni el tamaño del comité: hereda $n = 3f + 1$, la difusión certificada de Narwhal y las garantías de safety del protocolo base. [2] Segundo, la ganancia del pipelining depende del caso favorable: si la primera ancla de una instancia no se confirma, la instancia necesita más rondas para ordenar una, igual que ocurriría en Bullshark. [1]

Tercero, la reputación reacciona a la historia ya ordenada, así que hay un retardo entre que un validador falla y que el calendario lo refleja. Un validador que alterna entre responder y no responder puede degradar la latencia mientras su puntuación oscila. Cuarto, la cifra concreta de mejora depende del despliegue y de la carga; el paper reporta su propia evaluación sobre un protocolo base concreto, y esas mediciones no deben trasladarse sin más a otro sistema. [1]

Finalmente, Shoal sigue pagando el costo estructural de un DAG certificado: cada vértice pasa por la difusión fiable de Narwhal antes de poder ser referenciado. [3] Reducir ese costo exige otra línea de diseño, la de los DAG sin certificación, que se comenta en HotStuff-2, la frontera DAG-BFT y Twins.

Siguiente lectura

Si quieres repasar cómo se construye el grafo que Shoal reinterpreta, vuelve a Narwhal como mempool DAG. Para comparar con la ruta que evita los timeouts mediante aleatoriedad, lee Tusk: consenso asíncrono sin timeouts, y para el panorama de la frontera DAG-BFT continúa con HotStuff-2, la frontera DAG-BFT y Twins.