Tusk: Consenso asíncrono y aleatorizado sin timeouts en el camino feliz

Narwhal resolvió la difusión: los datos circulan como batches certificados y el DAG registra qué estaba disponible y en qué orden causal. Pero un DAG no es todavía un libro contable. Falta decidir un orden total que todas las réplicas honestas reproduzcan idéntico. [1]

El paper de Danezis, Kokoris-Kogias, Sonnino y Spiegelman ofrece dos respuestas. Una es Narwhal-HotStuff, que pone un consenso con líder y pacemaker encima del DAG. La otra es Tusk: un protocolo asíncrono que no envía ningún mensaje propio, sino que cada réplica interpreta localmente el DAG con ayuda de una moneda aleatoria compartida. [1]

Para entender por qué eso importa, primero hay que mirar qué se pierde cuando el progreso depende de un reloj. Si necesitas el contexto del DAG, vuelve a Narwhal: mempool DAG para HotStuff.

Qué cuesta depender de timeouts

HotStuff está diseñado para sincronía parcial: garantiza safety siempre, pero su liveness depende de que, después de GST, un líder correcto reciba los votos a tiempo. El componente que vigila eso es el pacemaker, que usa timeouts para abandonar una vista cuyo líder no progresa. [3] El modelo está explicado en sincronía parcial y quórums BFT.

Los timeouts son una apuesta sobre la red:

• si el plazo es corto, un líder honesto pero lento se sustituye antes de terminar, y la vista $v$ se pierde;
• si el plazo es largo, un líder caído o malicioso congela el progreso durante todo ese intervalo;
• si un adversario controla los retrasos, puede apuntar al líder conocido de la siguiente vista y hacer que sus mensajes lleguen siempre tarde.

El último punto es el más incómodo. En un protocolo con rotación predecible, el atacante sabe a quién retrasar. No necesita romper la criptografía; le basta con manipular el calendario de la red.

¿Por qué no prescindir del reloj sin más? Por FLP: ningún protocolo determinista puede garantizar consenso en un sistema completamente asíncrono si incluso un proceso puede fallar por crash. [2] La salida estándar es la aleatorización. Tusk renuncia al determinismo en la elección del líder y, a cambio, obtiene progreso sin ninguna suposición temporal. [1]

Olas: elegir al líder después de construir el DAG

Tusk agrupa las rondas del DAG de Narwhal en olas (waves). En la primera ronda de una ola, cada validador produce su vértice como siempre. En la ronda siguiente, los nuevos vértices referencian $2f+1$ certificados de la ronda anterior, como exige Narwhal, y esas referencias funcionan como votos implícitos. En la ronda que cierra la ola, los validadores aportan su parte de la moneda aleatoria compartida. [1]

Cuando la moneda se revela, todos calculan el mismo líder para la ola $w$:

$\ell_w = \operatorname{coin}(w) \bmod n.$

El vértice que ese validador produjo en la primera ronda de la ola es el candidato a comprometerse. La clave es el orden temporal: el líder se conoce después de que el DAG de la ola ya existe. Un adversario que controla los retrasos de la red no sabe qué vértice proteger o castigar mientras las rondas se construyen. Cuando lo sabe, las referencias ya están fijadas. [1]

La moneda debe cumplir dos propiedades: ser impredecible hasta que suficientes validadores aportan su parte, y no poder sesgarse por $f$ validadores bizantinos. Una construcción habitual usa firmas de umbral sobre el número de ola, de modo que el valor resultante es único y verificable. [1]

Regla de commit y orden retroactivo

Una vez conocido el líder, cada réplica mira su copia local del DAG. Si al menos $f+1$ vértices de la segunda ronda de la ola referencian el vértice del líder, la réplica lo compromete. Si no, no hace nada: no hay timeout, no hay cambio de vista, simplemente se pasa a la ola siguiente. [1]

¿Por qué $f+1$ basta? Por intersección de quórums. Cualquier vértice de la ronda posterior referencia $2f+1$ vértices de la segunda ronda. Como hay $3f+1$ validadores, un conjunto de $f+1$ votantes y uno de $2f+1$ referencias comparten al menos un vértice. Por lo tanto, todo vértice de rondas futuras tiene un camino hacia el líder comprometido.

Esa propiedad resuelve el caso difícil: réplicas distintas pueden ver el DAG en momentos distintos. Una réplica puede comprometer el líder de la ola $w$ mientras otra todavía no ve suficientes votos. Cuando esta segunda réplica comprometa un líder posterior, recorre hacia atrás los líderes de olas anteriores que son alcanzables por caminos del DAG y los ordena primero. El líder de $w$ será alcanzable por la propiedad anterior, así que ambas réplicas terminan con la misma secuencia. [1]

Finalmente, para cada líder en esa secuencia, la réplica toma su historia causal todavía no ordenada y la recorre con una regla determinista común. Como Narwhal certifica cada vértice con $2f+1$ firmas, un validador bizantino no puede mostrar vértices distintos a réplicas distintas para la misma ronda, y todas recorren el mismo grafo. [1]

Cero mensajes extra: dónde está realmente el costo

La afirmación de que Tusk tiene costo de comunicación cero para el orden es literal: no existen mensajes de propuesta, voto ni cambio de vista propios de Tusk. Las referencias que actúan como votos ya forman parte de los vértices que Narwhal construye de todos modos. [1]

Eso no significa que el orden sea gratuito. El costo se desplaza a tres lugares:

• Latencia en rondas. Un líder solo puede comprometerse cuando la ola termina y la moneda se revela, de modo que la latencia de commit se mide en varias rondas del DAG, no en un par de intercambios.
• Mala suerte con la moneda. Si la moneda elige a un validador lento o bizantino cuyo vértice no reunió soporte, esa ola no compromete nada y el sistema espera a la siguiente.
• Trabajo local. Cada réplica recorre el DAG para contar referencias y ordenar historias causales; es cómputo y memoria, no red.

Límites de Tusk y lo que vino después

Asíncrono no significa inmune a la red. Si los mensajes tardan, las rondas tardan, y el commit con ellas. Lo que Tusk garantiza es que ningún patrón de retrasos puede detener el progreso indefinidamente ni romper safety. [1]

Cuando la red es estable, esa robustez tiene un precio visible: un protocolo parcialmente síncrono puede comprometer en menos rondas porque no espera a que una moneda revele al líder. Bullshark ataca exactamente ese hueco. Mantiene el DAG de Narwhal y añade un camino rápido para periodos de sincronía, conservando un comportamiento asíncrono como respaldo. [4]

La comparación honesta con HotStuff sobre Narwhal tampoco es una escalera. Narwhal-HotStuff aprovecha el mismo mempool y puede tener baja latencia cuando los líderes son honestos y la red coopera, pero hereda la dependencia del pacemaker. [1] [3] Tusk elimina esa dependencia a cambio de latencia en el caso común. Elegir entre ambos es elegir qué falla te preocupa más: un adversario de red sofisticado o algunas rondas de latencia adicional en un día tranquilo.

Siguiente lectura: de Tusk a los motores DAG de producción

El siguiente paso natural son los motores DAG-BFT que parten de esta idea, empezando por Bullshark. [4] Para situar Tusk dentro del panorama completo, revisa el mapa de frontera HotStuff-2 y DAG-BFT y el mapa de blockchain y consenso, que muestra qué capítulos ya están publicados.