Rompiendo la regla: ¿Por qué 2 cadenas en HotStuff original permite bifurcaciones?

En la taxonomía de commit y en QC, highQC y la regla de tres cadenas vimos que Chained HotStuff compromete un bloque cuando aparece una cadena de tres QCs consecutivos que lo extiende. [1]

Un ingeniero inquieto podría preguntarse:

Si en la vista $v_1$ logramos $QC_1$ para el bloque $A$ y en la vista $v_2$ logramos $QC_2$ para su hijo $B$, ¿por qué no consideramos $A$ finalizado ya y nos ahorramos una fase?

La pregunta es legítima, y la respuesta tiene dos caras. Si acortamos el commit y dejamos los locks como están, perdemos safety. Si además adelantamos el lock para recuperar safety, perdemos la combinación de cambio de vista lineal y responsividad que justifica HotStuff. Vamos a construir ambos contraejemplos y después ver cómo los protocolos de dos cadenas posteriores pagan esa diferencia con mecanismos adicionales.

El atajo tentador: commit al ver dos QCs

Recordemos las piezas de HotStuff básico. Cada réplica mantiene un highQC, el QC más alto que conoce, y un lockedQC, su memoria de seguridad. Antes de votar, aplica el predicado safeNode: acepta una propuesta si extiende el bloque de su lockedQC (regla de safety) o si el QC que la justifica tiene una vista mayor que la de su lockedQC (regla de liveness). [1]

En la versión encadenada, los tres saltos de la cadena tienen funciones distintas. Cuando una réplica recibe una propuesta cuyo QC certifica a $B$, y $B$ a su vez lleva $QC_1$ sobre $A$, la réplica actualiza su highQC y fija su lock en $QC_1$. Solo cuando aparece un tercer QC consecutivo se compromete $A$. [1]

La regla ingenua cambia una sola línea: comprometer $A$ en el mismo momento en que la réplica fija su lock en $QC_1$, es decir, al ver $QC_2$. Parece inocente porque el lock y el commit ocurren juntos en la réplica que observa la cadena. El problema está en las réplicas que no la observan.

Usaremos un comité de $n = 4$ réplicas, $R_1, R_2, R_3, R_4$, con $f = 1$. El quórum es $n - f = 3$ votos, y $R_4$ es bizantina.

Primera forma de romperlo: el lock llega tarde y safety cae

El ataque explota que, en HotStuff, los votos de una vista se envían al líder de la vista siguiente, que es quien forma el QC. Un líder bizantino puede formar un QC y mostrarlo selectivamente. [1]

Vista 1. $R_1$ propone $A$. $R_1$, $R_2$ y $R_3$ votan, y el siguiente líder forma $QC_1$.

Vista 2. $R_2$ propone $B$, hijo de $A$, justificado con $QC_1$. Las tres réplicas correctas votan y envían sus votos a $R_4$, líder de la vista 3. Al votar, su highQC pasa a ser $QC_1$, pero su lock sigue en la génesis: todavía no vieron un QC sobre $B$.

Vista 3. $R_4$ forma $QC_2$ y se lo muestra solo a $R_3$, dentro de una propuesta que no envía a nadie más. $R_3$ ve la cadena $A$, $B$ con dos QCs consecutivos: fija su lock en $QC_1$ y, bajo la regla ingenua, compromete $A$.

El fork. $R_4$ propone ahora $A'$, que extiende la génesis y no a $A$, justificado con el QC de la génesis. $R_1$ y $R_2$ aplican safeNode: $A'$ extiende el bloque de su lockedQC, que sigue siendo la génesis. Votan. Con el voto de $R_4$ hay tres votos y se forma un QC para $A'$. Si las vistas siguientes certifican un hijo de $A'$, $R_1$ verá dos QCs consecutivos y comprometerá $A'$.

Dos réplicas correctas comprometieron bloques incompatibles. Ninguna regla local se violó; la falla es de diseño. El commit se declaró cuando solo una réplica correcta tenía el lock que debía protegerlo, y una sola réplica no alcanza para impedir un quórum de $n - f$.

Figura 1

Secuencia de ataque y bifurcación en una regla 2-chain no protegida

Fuentes:

[1]

Cómo leer esta figura

El diagrama de árbol muestra dos ramas derivadas de la génesis. La rama superior tiene el bloque A en la vista 1 y B en la vista 2, unidos por QC1; la regla de dos cadenas declara A comprometido. En la vista 3, un líder bizantino propone A' extendiendo la génesis. Las réplicas que nunca vieron QC2 conservan QC1 solo como highQC y su lock no cubre A, de modo que safeNode las deja votar A'. Resultado: A y A' terminan comprometidos en ramas incompatibles.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Segunda forma: bloquear antes y perder el progreso responsivo

La reparación evidente es adelantar el lock: que cada réplica se bloquee en $QC_1$ apenas vota por un bloque que lo transporta, sin esperar a $QC_2$. Así, cuando existe $QC_2$, al menos $n - f$ réplicas, y entre ellas $f + 1$ correctas, ya están bloqueadas en $A$, y la rama conflictiva no reúne quórum. Es esencialmente el diseño de dos fases de Tendermint y Casper. [1]

Safety vuelve, pero aparece otro problema: el lock oculto. Repitamos la escena con el lock adelantado.

Vista 2 con líder bizantino. $R_4$ forma $QC_1$ para $A$, pero envía la propuesta $B$ que lo transporta solo a $R_3$. $R_3$ vota y se bloquea en $QC_1$. $R_1$ y $R_2$ nunca ven $QC_1$.

Vista 3 con líder correcto. $R_1$ recoge mensajes new-view con el highQC de cada réplica. Para ser responsivo, avanza en cuanto tiene $n - f = 3$ mensajes, y los primeros en llegar son los de $R_1$, $R_2$ y $R_4$. Ninguno contiene $QC_1$. $R_1$ propone sobre la génesis.

El bloqueo. $R_3$ rechaza la propuesta: no extiende $A$ y su QC no supera la vista de su lock. Votan $R_1$ y $R_2$; $R_4$ se abstiene. Dos votos no forman QC. El adversario puede repetir el patrón vista tras vista retrasando el mensaje de $R_3$ dentro del límite de la red. [1]

El paper de HotStuff explica que Tendermint y Casper evitan este estancamiento haciendo que el nuevo líder espere el retraso máximo de red conocido antes de proponer, para asegurarse de oír el lock más alto de toda réplica correcta. Funciona y mantiene la comunicación lineal, pero el progreso queda atado a ese límite de red en lugar de a la velocidad real de la red: se pierde la responsividad optimista. [1]

La otra salida es la de PBFT: que el líder pruebe con un expediente cuál es el lock más alto. Es responsiva, pero el cambio de vista deja de ser lineal.

Qué compra exactamente la tercera cadena

HotStuff resuelve el dilema moviendo el lock un escalón hacia atrás y el commit otro escalón más. Una réplica correcta se bloquea en $QC_1$ solo cuando ve $QC_2$. Para que $QC_2$ exista, $n - f$ réplicas votaron por $B$, y al hacerlo guardaron $QC_1$ como highQC. [1]

Esa observación cierra el problema del lock oculto. Si alguna réplica correcta está bloqueada en $QC_1$, al menos $f + 1$ réplicas correctas tienen un highQC igual o superior. Cualquier conjunto de $n - f$ mensajes new-view intersecta a ese grupo en al menos una réplica correcta. El nuevo líder ve siempre un QC tan alto como cualquier lock correcto, y su propuesta pasa la regla de liveness de safeNode. No necesita esperar ni adjuntar expedientes. [1]

El costo es que, al ver $QC_2$, todavía no hay suficientes réplicas bloqueadas para comprometer $A$. Hace falta $QC_3$ sobre el hijo de $B$: prueba que $n - f$ réplicas votaron después de ver $QC_2$ y, por tanto, se bloquearon en $QC_1$. Con eso, el primer contraejemplo desaparece, porque la rama conflictiva necesitaría el voto de alguna de esas réplicas.

$\text{commit}(A) \iff A \leftarrow B \leftarrow C \;\wedge\; QC(A,v),\, QC(B,v+1),\, QC(C,v+2)$

El paper de HotStuff resume este compromiso: la fase adicional es lo que permite tener a la vez cambio de vista lineal y responsividad optimista, mientras que una variante de dos fases debe volver a esperar el retraso máximo de red. [1] La lectura detallada de esas propiedades está en safety, liveness y responsividad en HotStuff.

Cómo recuperan dos cadenas Fast-HotStuff, Jolteon y HotStuff-2

La tercera cadena no es una ley de la naturaleza. Es el precio de un conjunto concreto de objetivos. Los protocolos posteriores comprometen con dos cadenas, pero cada uno agrega una pieza que reemplaza la garantía perdida.

Fast-HotStuff y AggQC. Tras un cambio de vista, el nuevo líder adjunta un AggQC: la agregación de $n - f$ mensajes new-view firmados, cada uno con el highQC de su emisor. Las réplicas comprueban que la propuesta extiende el QC más alto contenido en esa prueba. [2] El líder ya no puede ocultar un QC alto, y una réplica bloqueada puede verificar que su lock no protege un commit. El camino feliz sigue siendo lineal; el costo se concentra en verificar AggQC después de un cambio de vista. Los autores también presentan este diseño como defensa frente a ataques de bifurcación que afectan el rendimiento de HotStuff encadenado. [2] Los detalles están en Fast-HotStuff con AggQC.

Jolteon y el cambio de vista cuadrático. Jolteon compromete con dos cadenas en el camino feliz, con comunicación lineal, y acepta un cambio de vista cuadrático cuando hay timeouts: las réplicas difunden mensajes de timeout con su highQC, y el certificado de timeout resultante permite justificar la propuesta del nuevo líder. [3] Es una apuesta explícita: optimizar el caso común y pagar más solo en el camino infeliz. Su paso a producción se discute en DiemBFT, Jolteon y Ditto.

HotStuff-2 y la espera condicional. Malkhi y Nayak muestran que dos fases bastan para un protocolo lineal y optimistamente responsivo. [4] La idea es no esperar siempre. Si el nuevo líder tiene el certificado de la vista inmediatamente anterior, ese certificado ya es el lock más alto posible y puede proponer de inmediato. Si no lo tiene, espera un intervalo acotado por el retraso de red para recoger los locks de las réplicas correctas antes de proponer. [4] El análisis de esa frontera sigue en HotStuff-2 y la frontera DAG-BFT.

En los tres casos, la información que la tercera cadena garantizaba de forma implícita ahora se obtiene explícitamente: con una prueba agregada, con un certificado de timeout o con una espera condicional.

Siguiente lectura

Continúa con Fast-HotStuff con AggQC y commit de dos cadenas, donde la prueba agregada del cambio de vista se analiza mensaje por mensaje.