El cuello de botella de la doble transmisión: Por qué los líderes saturan tu fibra

HotStuff hizo famosa una idea: un protocolo BFT con líder puede mantener la comunicación lineal en el número de réplicas, incluso durante el cambio de vista, gracias a certificados de quórum compactos. [2] Esa linealidad cuenta mensajes y autenticadores. No cuenta bytes de payload.

Cuando un sistema intenta procesar muchas transacciones por segundo, la pregunta deja de ser cuántos mensajes envía el líder y pasa a ser cuántos bytes tiene que empujar por su interfaz de red. Ahí aparece un límite físico que ninguna optimización de fases elimina: el ancho de banda de salida del líder.

Danezis, Kokoris-Kogias, Sonnino y Spiegelman tomaron ese síntoma como punto de partida de Narwhal: separar la difusión fiable de transacciones del protocolo que decide el orden. [1] Este capítulo explica el problema antes de la solución; la arquitectura completa está en Narwhal: mempool DAG para HotStuff.

Dónde gasta bytes un protocolo con líder

En PBFT, el primario asigna un número de secuencia a la petición del cliente y la difunde junto con el mensaje pre-prepare; las réplicas luego intercambian prepare y commit sobre el digest. [3] En HotStuff, el líder de la vista $v$ propone un bloque que contiene los comandos y las réplicas devuelven votos que se agregan en un QC. [2]

Los dos diseños comparten un patrón: el mensaje del líder es el vehículo del payload. Los votos son pequeños; la propuesta no. Si un bloque transporta varios megabytes, la propuesta domina el tráfico de cada vista.

A eso se suma un mempool que ya difundió las mismas transacciones. Los clientes envían sus transacciones a uno o varios validadores, y estos suelen retransmitirlas por gossip para que cualquier futuro líder pueda incluirlas. Después, el líder reenvía esos mismos bytes dentro del bloque. Esa es la doble transmisión: la red paga dos veces por mover los mismos datos, y la segunda vez todo el costo cae sobre un único nodo. [1]

Ojo con esto: el problema no es que el líder sea lento o malicioso. Un líder perfectamente honesto y bien provisto sigue siendo un embudo, porque la arquitectura le asigna a él solo el trabajo de difusión que podría repartirse entre todos.

Aritmética del enlace de subida

Hagamos el cálculo con números hipotéticos, elegidos para que la cuenta sea fácil y no como medición de ningún sistema real. Tomemos $n = 100$ validadores y una propuesta de $S = 10\ \text{MB}$ de transacciones.

Para que cada réplica reciba la propuesta, el líder debe subir

$E_{\text{líder}} = (n - 1)\cdot S = 99 \times 10\ \text{MB} \approx 1\ \text{GB}.$

Si se quisiera un bloque por segundo, el líder necesitaría sostener cerca de $8\ \text{Gbps}$ de subida dedicados a repetir el mismo contenido. Mientras tanto, cada una de las otras 99 réplicas recibe $S$ y sube únicamente votos de unos cientos de bytes. La capacidad de subida agregada del sistema existe, pero está ociosa.

Figura 1

El cuello de botella de subida del líder en consensos tradicionales

Fuentes:

[1]

Cómo leer esta figura

El diagrama muestra al líder en el centro intentando empujar megabytes de transacciones a 100 réplicas. El canal de subida se satura, provocando demoras en la entrega de la propuesta y disparando timeouts falsos en el Pacemaker.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

La parte interesante aparece al generalizar. Sea $B$ la capacidad de subida del líder. El número de bloques por segundo queda acotado por $B / ((n-1)\,S)$, así que el throughput de payload queda acotado por

$T_{\text{payload}} \le \frac{B}{n-1}.$

El tamaño del bloque desaparece de la cota. Hacer bloques más grandes amortiza la latencia de las fases, pero no compra throughput más allá de ese techo. Y agregar validadores para tolerar más fallas, con $n = 3f + 1$, lo empeora: cada validador nuevo es un destinatario más para el mismo enlace.

Por qué enviar solo hashes no basta

La reacción natural es recortar la propuesta: que el líder envíe solo los digests de 32 bytes de las transacciones y que cada réplica las busque en su propio mempool. Funciona en el caso feliz. Falla en cuanto el líder es bizantino.

Un líder malicioso puede proponer digests de transacciones que nunca difundió. Las réplicas no pueden distinguir de inmediato entre un dato que todavía no les llegó y un dato que no existe en ningún nodo honesto:

• si votan el bloque, el sistema puede comprometer un orden que nadie es capaz de ejecutar;
• si esperan a tener los datos, dependen de pedírselos al mismo líder sospechoso;
• si fijan un plazo y rechazan, un líder honesto con red lenta pierde su propuesta y el sistema vuelve a depender de timeouts.

Este es el problema de disponibilidad de datos: acordar el orden de referencias solo es seguro si alguien garantiza que el contenido referenciado puede recuperarse. [1] Por eso los protocolos clásicos terminan incluyendo el payload en la propuesta: es la forma más simple de que el voto implique tenencia de los datos, y el precio es el cuello de botella de la sección anterior.

Separar disponibilidad de orden: la respuesta de Narwhal

Narwhal convierte la disponibilidad en un objeto verificable antes de que el consenso intervenga. Cada validador ejecuta uno o varios workers que agrupan transacciones en batches y los difunden a los workers de los demás validadores. El proceso primario del validador no transporta los batches: arma un encabezado de ronda con sus digests. [1]

Ese encabezado se convierte en certificado de disponibilidad cuando reúne $2f+1$ firmas de validadores que confirman haber almacenado los datos referenciados. Como a lo sumo $f$ firmantes son bizantinos, al menos $f+1$ validadores honestos guardan el contenido y pueden servirlo después. [1]

Los certificados se organizan por rondas: cada nuevo encabezado referencia $2f+1$ certificados de la ronda anterior. El resultado es un DAG que registra disponibilidad y causalidad a la vez. [1]

Encima de ese DAG, el consenso ordena digests de certificados. En Narwhal-HotStuff, HotStuff propone y certifica referencias compactas en lugar de bloques con megabytes de transacciones; el paper también presenta Tusk, que ordena el DAG sin mensajes adicionales. [1] [2] Bullshark reutiliza el mismo mempool y cambia la regla de ordenamiento. [4]

Volviendo a la aritmética: si todos los validadores difunden sus propios batches, la subida agregada disponible es del orden de $n \cdot B$ en lugar de $B$, y el throughput de payload deja de estar atado a un único enlace. Además, un validador puede agregar workers en máquinas separadas para aumentar su propia capacidad. Esto también es una cota didáctica, no una cifra del paper.

Lo que el desacoplamiento no resuelve

Separar capas mueve el problema; no lo hace desaparecer. Vale la pena nombrar los costos antes de leer los números de cualquier evaluación.

Primero, la difusión sigue costando ancho de banda total: cada batch tiene que llegar a muchos validadores. Lo que cambia es quién paga. En lugar de un emisor que sube todo, cada validador sube lo suyo, y el costo se reparte.

Segundo, aparece estado nuevo que mantener: batches, encabezados, certificados y referencias entre rondas. Un nodo que se atrasa necesita sincronizar el DAG, y el sistema necesita una política de recolección de basura que no borre datos que un rezagado todavía necesita.

Tercero, el consenso no se vuelve trivial. HotStuff sobre Narwhal sigue dependiendo de su pacemaker y de timeouts para el progreso bajo sincronía parcial. [2] Tusk elimina esa dependencia con aleatoriedad, y Bullshark busca menor latencia cuando la red se porta bien. [1] [4]

La trampa está en atribuir todo el salto de rendimiento al protocolo de orden. Cuando se compara un protocolo con líder contra uno sobre Narwhal, gran parte de la diferencia viene de la arquitectura de difusión, no de una regla de commit más ingeniosa.

Siguiente lectura: del embudo al mempool DAG

Continúa con Narwhal: mempool DAG para HotStuff, donde se detalla cómo se forman los certificados y qué ordena finalmente el consenso. Si quieres repasar por qué los QC hacen lineal a HotStuff, vuelve a QC, highQC y la regla de tres cadenas.