El Grafo Dirigido Acíclico (DAG) como una máquina del tiempo inmutable

En Narwhal y Bullshark y en el cuello de botella de la doble transmisión vimos por qué los protocolos modernos separan la difusión de datos del orden. Este artículo mira la estructura que queda en medio: el grafo dirigido acíclico que Narwhal construye ronda a ronda.

La metáfora de la "máquina del tiempo" sirve si se usa con cuidado. El DAG no mide tiempo físico: registra quién había visto qué en el momento de emitir cada vértice. Esa relación de precedencia causal es justo la información que un protocolo de consenso necesita para ordenar, y por eso el orden puede leerse del grafo en lugar de votarse aparte.

La geometría de las rondas

Narwhal organiza el DAG en rondas. En cada ronda, el primary de cada validador emite como máximo un header que contiene digests de batches y referencias a al menos $2f + 1$ certificados de la ronda anterior. [1] Ese header se convierte en vértice del DAG cuando reúne un certificado de $2f + 1$ firmas.

Dos reglas dan forma al grafo. La primera es que un validador correcto firma a lo sumo un header por autor y por ronda, de modo que, aunque un autor bizantino emita dos headers distintos, solo uno de ellos puede certificarse. [1] La segunda es que un validador avanza a la ronda $r + 1$ solo cuando tiene $2f + 1$ certificados de la ronda $r$.

Un ejemplo pequeño ayuda a fijar los números. Con $f = 1$ hay cuatro validadores, A, B, C y D. Cada certificado necesita tres firmas, y cada vértice de la ronda $r + 1$ debe apuntar a por lo menos tres vértices certificados de la ronda $r$. Si D está caído o lento, A, B y C pueden seguir avanzando entre ellos; el DAG sigue creciendo sin D, que más tarde puede ponerse al día descargando los certificados que se formaron mientras tanto.

La primera regla es la intersección de quórums de siempre: dos certificados para el mismo autor y la misma ronda necesitarían dos conjuntos de $2f + 1$ firmas que comparten al menos una réplica correcta, y esa réplica no firma dos veces. La segunda regla impide que un validador corra solo hacia rondas futuras: necesita que una mayoría calificada ya haya terminado la ronda actual.

Figura 1

Estructura de rondas y vínculos causales en un DAG de Narwhal

Fuentes:

[1]

Cómo leer esta figura

El diagrama muestra 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 la ronda r+1 tiene aristas hacia tres vértices de la ronda r, y cada vértice de r+2 hacia tres de r+1, que es 2f + 1 con f = 1.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Historia causal: por qué el pasado queda fijo

Llamemos historia causal de un vértice al conjunto de vértices alcanzables siguiendo sus aristas hacia atrás. Como las referencias son hashes de certificados, la historia causal de un vértice certificado queda determinada por el propio vértice. [1] Cambiar cualquier vértice antiguo cambiaría su hash, y las referencias que ya apuntan a él dejarían de coincidir.

Esto produce la propiedad que motiva la metáfora. Si dos réplicas correctas tienen el mismo vértice certificado $x$, tienen exactamente la misma historia causal de $x$, aunque hayan recibido los vértices en distinto orden y en distintos momentos. El DAG local de cada réplica puede ir más adelante o más atrás, pero lo que está "debajo" de un vértice compartido es idéntico para todas.

También explica por qué el grafo es acíclico sin esfuerzo: toda arista apunta de una ronda a una ronda menor, así que nunca se puede volver al punto de partida. No hace falta un algoritmo especial para detectar ciclos; la numeración de rondas los excluye por construcción.

Narwhal resume las garantías del grafo en propiedades como integridad, disponibilidad de bloques y causalidad: un certificado implica que su historia causal está disponible y que cualquier réplica correcta que lo acepte puede recuperarla. [1]

Del grafo al orden: anclas y commit sin mensajes extra

Que todas las réplicas compartan historias causales no basta para ordenar. Falta elegir qué vértices sirven de puntos de corte. Los protocolos construidos sobre el DAG llaman a esos vértices líderes o anclas, y deciden su commit mirando únicamente la estructura del grafo. [2]

Tusk, el protocolo asíncrono presentado junto a Narwhal, agrupa rondas en olas y usa una moneda aleatoria común para elegir el líder de cada ola después de que el grafo de esa ola ya está construido. [1] Como el líder se revela tarde, el adversario no puede apuntar de antemano contra él. El commit depende de cuántos vértices de la ronda siguiente referencian al líder.

Bullshark conserva la misma interpretación local del DAG y añade un camino rápido para sincronía parcial: hay anclas predefinidas cada dos rondas, y un ancla se compromete cuando al menos $f + 1$ vértices de la ronda siguiente la referencian. [2] El paper destaca que este consenso no envía mensajes propios: los "votos" son las aristas que el DAG ya contiene. [2]

Cuando una réplica compromete un ancla, primero revisa anclas anteriores no comprometidas que sean alcanzables desde ella y las ordena antes. Después ordena la historia causal de cada ancla, aún no entregada, con una regla determinista. [2] Por el lema anterior, dos réplicas que comprometen la misma secuencia de anclas producen la misma secuencia de vértices.

Lo que el DAG no regala

La frase "consenso sin mensajes" necesita su letra pequeña. No hay mensajes adicionales para votar, pero construir el DAG ya cuesta: cada vértice certificado requiere difundir un header y recolectar $2f + 1$ firmas. [1] El consenso es gratis solo porque su costo se pagó al construir el mempool.

Ese costo tiene un efecto en latencia. Certificar cada vértice añade viajes de red antes de que el vértice pueda ser referenciado. Mysticeti explora precisamente la alternativa de construir un DAG sin certificados explícitos por vértice para reducir la latencia de commit. [3] El precio es que las garantías que antes daba el certificado deben recuperarse con otras reglas de commit.

Por último, el DAG no impide que un adversario retrase mensajes. Con anclas predefinidas, un ancla que no llega a tiempo simplemente no se compromete en su ronda, y su contenido se ordena después a través de un ancla posterior si es alcanzable desde ella. [2] La historia queda fija; lo que el protocolo no promete es cuándo se vuelve definitiva.

Siguiente lectura

Para ver cómo la moneda aleatoria de Tusk convierte este grafo en consenso asíncrono, continúa con Tusk: consenso asíncrono sin timeouts. Si quieres repasar por qué $2f + 1$ firmas impiden certificar dos headers en conflicto, vuelve a Quórums en acción.