Bullshark: El motor de consenso DAG parcialmente síncrono

Tusk mostró que el DAG de Narwhal basta para ordenar transacciones incluso en asincronía, eligiendo líderes a posteriori con una moneda aleatoria compartida. [2] El precio es que el líder solo se conoce cuando la moneda se revela, y la confirmación depende de que esa elección aleatoria tenga suerte.

Bullshark, de Spiegelman, Giridharan, Sonnino y Kokoris-Kogias, se pregunta qué se puede ganar si, además de sobrevivir a la asincronía, el protocolo aprovecha los periodos en que la red se porta bien. [1] Este capítulo recorre su versión parcialmente síncrona: anclas fijadas de antemano, votos que son simples aristas del DAG y una regla de commit sorprendentemente barata. También mira de frente su punto débil, que es el mismo que motivó a Shoal: cuando el ancla es lenta, todos esperan.

De Tusk a Bullshark: qué cambia al asumir sincronía parcial

El modelo de sincronía parcial de Dwork, Lynch y Stockmeyer supone que la red puede comportarse de forma arbitraria hasta un instante desconocido, el GST, y que a partir de ahí los mensajes llegan dentro de una cota. [4] En ese modelo la safety debe valer siempre, pero basta con que la liveness se cumpla después del GST. [4]

Tusk no necesita esa hipótesis: su moneda aleatoria le da liveness probabilística aun sin GST. [2] Bullshark parte de la misma estructura y busca un camino rápido para los periodos síncronos, sin el mecanismo de cambio de vista que caracteriza a los protocolos tipo PBFT o HotStuff. [1] La idea es que el DAG ya contiene toda la información que un cambio de vista transportaría: quién vio qué y en qué ronda.

El paper presenta un protocolo completo que mezcla un camino rápido con un respaldo asíncrono, y también describe una versión independiente solo para sincronía parcial, que es la que se evalúa contra Narwhal-HotStuff y Tusk. [1] Esa versión es la protagonista de este capítulo.

El DAG de Narwhal como sustrato de votos

Narwhal organiza la difusión en rondas. En cada ronda, cada validador publica un vértice con lotes de transacciones y referencias a al menos $2f + 1$ vértices certificados de la ronda anterior, con $n = 3f + 1$ validadores. [2] El certificado garantiza disponibilidad: un vértice certificado puede recuperarse aunque su autor deje de responder. [2]

Para Bullshark, ese grafo es más que un mempool. Cada validador interpreta localmente su copia del DAG y decide el orden sin intercambiar mensajes de consenso adicionales; los autores lo llaman sobrecarga de comunicación nula. [1] Dos validadores correctos pueden tener DAGs locales distintos en un instante dado, porque los vértices llegan en órdenes distintos, pero si ambos tienen un mismo vértice certificado, tienen exactamente la misma historia causal de ese vértice. [2]

Figura 1

Rondas del DAG leídas como votos sobre un ancla

Fuentes:

[2]

Cómo leer esta figura

Cuatro validadores A, B, C y D con un vértice por ronda en las rondas r, r + 1 y r + 2. Cada vértice de una ronda tiene aristas hacia tres vértices de la ronda anterior. El vértice de A en la ronda r recibe aristas desde los vértices de A, B y D en la ronda r + 1.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Anclas predefinidas y la regla de commit con f + 1 votos

En la versión parcialmente síncrona, una ronda de cada dos tiene un ancla predefinida: un validador concreto, conocido por todos de antemano, cuyo vértice en esa ronda es el candidato a confirmarse. [1] La ronda que sigue a cada ronda de ancla funciona como ronda de votación.

La regla es la siguiente. Sea $A_r$ el vértice ancla de la ronda $r$. Un vértice de la ronda $r + 1$ vota por $A_r$ si tiene una arista hacia él. Un validador confirma $A_r$ en cuanto su DAG local contiene al menos $f + 1$ vértices de la ronda $r + 1$ que votan por $A_r$. [1]

¿Por qué basta $f + 1$ y no $2f + 1$? La clave está en que cada vértice de la ronda $r + 2$ referencia $2f + 1$ vértices de la ronda $r + 1$. [2] Como $(f + 1) + (2f + 1) = 3f + 2 > n$, cualquier vértice de la ronda $r + 2$ referencia al menos uno de los votantes, y por tanto tiene un camino hasta $A_r$. [1] Desde ahí, todo vértice de rondas posteriores, incluida la próxima ancla de cualquier validador, contiene a $A_r$ en su historia causal. No hace falta una supermayoría de votos: hace falta que el voto sea imposible de esquivar en el futuro.

Fíjate en la diferencia con los protocolos basados en líder, donde cada fase reúne votos firmados explícitos sobre una propuesta. En Bullshark, el umbral de $2f + 1$ ya lo paga Narwhal al construir cada ronda; la regla de commit solo tiene que apoyarse en esa estructura. [1] En el caso favorable, un ancla se confirma en dos rondas del DAG. [1]

Ordenar la historia causal sin perder anclas

Confirmar un ancla no basta: hay que convertir el DAG en una secuencia. Cuando un validador confirma $A_r$, mira hacia atrás las anclas de rondas anteriores que todavía no ha ordenado. Si existe un camino desde $A_r$ hasta una ancla anterior $A_s$, esa ancla se ordena antes que $A_r$, y el proceso se repite desde $A_s$ hasta llegar a la última ancla ya ordenada. [1]

Esto resuelve el caso incómodo: un validador puede no haber visto los $f + 1$ votos de $A_s$ que otro sí vio. Por el lema anterior, si alguien confirmó $A_s$, cualquier ancla posterior tiene un camino hasta ella, así que todos la recuperan al confirmar la siguiente. [1] Las anclas sin camino desde la siguiente confirmada se saltan, y como la decisión depende solo de la historia causal compartida, todas las réplicas correctas saltan las mismas.

Una vez fijada la secuencia de anclas, cada una entrega su historia causal todavía no ordenada siguiendo una regla determinista común. [1] Por eso la propiedad de Narwhal sobre historias causales idénticas importa tanto: dos réplicas con la misma ancla producen el mismo bloque de transacciones. [2] Ojo con una consecuencia: solo el ancla goza de la latencia de dos rondas. Los demás vértices esperan a quedar dentro de la historia causal de alguna ancla confirmada, de modo que su latencia es mayor, un punto que Shoal señala explícitamente. [3]

Versión con fallback asíncrono frente a versión parcialmente síncrona

El protocolo completo de Bullshark agrupa las rondas en olas y combina dos tipos de líderes: anclas predefinidas para el camino rápido y un líder de respaldo elegido con una moneda aleatoria compartida, al estilo de Tusk. [1] [2] Cada validador decide, según lo que observó en la ola anterior, si sus vértices votan en modo rápido o en modo de respaldo, y los dos modos no pueden confirmar líderes incompatibles. [1] El resultado conserva la liveness en asincronía y aprovecha la sincronía cuando existe.

La versión parcialmente síncrona elimina el respaldo aleatorio. [1] A cambio, necesita algo que garantice que, tras el GST, las anclas correctas reciban sus votos. Ese algo son los timeouts: un validador no avanza de la ronda de ancla sin haber recibido el vértice del ancla o sin que expire un temporizador, y en la ronda de votación espera los votos del ancla o un timeout. [1] Sin esa espera, un validador rápido podría construir su vértice antes de ver el ancla y dejarla sin votos.

Es un intercambio clásico de la sincronía parcial: la safety no depende de los tiempos, pero la liveness sí, y los temporizadores son la forma de convertir la cota posterior al GST en progreso. [4]

Por qué los timeouts sobre anclas duelen con validadores lentos

Los timeouts no son gratis. Si el validador al que le toca ser ancla está caído, todos los demás esperan el temporizador completo antes de avanzar, y esa ronda no confirma nada. [3] Si el ancla no está caída sino solo lenta, el problema es más sutil: puede llegar tarde para reunir sus $f + 1$ votos, y entonces se salta y la confirmación espera a la siguiente ancla, dos rondas después. [1]

Spiegelman, Arun, Gelashvili y Li analizan este efecto en Shoal. Señalan que Bullshark depende de timeouts para su liveness y que, en presencia de fallas, esas esperas dominan la latencia; además, que solo las anclas se confirman en el camino corto. [3] Su propuesta combina tres ideas sobre el mismo DAG: canalizar las instancias para tener un ancla en cada ronda, usar reputación de líder para preferir validadores que responden a tiempo y evitar los timeouts en la mayoría de los casos, una propiedad que llaman prevalent responsiveness. [3]

La lección para quien diseña o opera un comité es concreta. Un protocolo con anclas predefinidas es tan rápido como el ancla de la ronda: el calendario fijo que elimina la moneda aleatoria también impide esquivar a un validador lento. Ajustar el timeout no resuelve el dilema, porque uno corto salta anclas correctas pero lentas y uno largo congela la red cuando el ancla está caída; es la misma tensión que discute por qué no usar timeouts fijos.

Siguiente lectura

Para ver dónde encaja Bullshark entre las demás propuestas DAG-BFT y las variantes de HotStuff, continúa con HotStuff-2 y la frontera DAG-BFT. Si quieres repasar el sustrato sobre el que corre todo esto, vuelve a Narwhal como mempool DAG.