El dilema de la responsividad optimista en Tendermint: El precio de esperar al temporizador

En Tendermint visto desde HotStuff estudiamos los locks de Tendermint: cada réplica recuerda el valor y la ronda en que se bloqueó, y solo vota por propuestas compatibles con ese bloqueo o justificadas por evidencia más reciente. [1] Ese mecanismo protege safety, pero crea un problema de liveness cada vez que cambia el líder.

Este artículo trata de ese problema y de las dos maneras de resolverlo. La pregunta es sencilla de formular: ¿cuánto tiene que esperar un líder nuevo antes de proponer? La respuesta separa a Tendermint de HotStuff y explica por qué HotStuff tiene tres fases de votación en lugar de dos.

Qué significa responsividad optimista

HotStuff define la responsividad optimista con precisión: después de GST, un líder correcto, una vez designado, solo necesita esperar las primeras $n - f$ respuestas para garantizar que puede crear una propuesta que hará progresar al protocolo. [2] La palabra "optimista" indica que la garantía aplica en el buen caso, después de la estabilización y con líder correcto; antes de GST nada asegura el progreso.

La diferencia práctica está entre dos magnitudes. $\Delta$ es la cota de retardo que el protocolo usa como supuesto, elegida de forma conservadora para cubrir el peor caso de la red. $\delta$ es el retardo real de los mensajes en una ejecución concreta, que normalmente es mucho menor. Un protocolo responsive avanza a un ritmo proporcional a $\delta$; uno que no lo es paga $\Delta$ en algún paso, aunque todos los mensajes hayan llegado mucho antes. [2]

Ojo con esto: la responsividad no dice que el protocolo sea siempre más rápido en la práctica. Dice que su progreso no está atado a una espera fija calibrada para el peor caso. Cuánto se gana depende de la distancia real entre $\delta$ y $\Delta$ en el despliegue.

El problema del lock oculto

Para entender por qué un líder nuevo podría necesitar esperar, imaginemos el escenario que preocupa a todos los protocolos con locks. En una ronda anterior, alguna réplica correcta se bloqueó en un valor porque vio suficiente evidencia de que podía haberse decidido. Esa réplica, por las reglas de safety, rechazará propuestas incompatibles con su lock que no traigan justificación más reciente. [1]

El líder nuevo recoge mensajes de $n - f$ réplicas. Pero nada garantiza que la réplica bloqueada esté entre ellas: puede ser una de las $f$ que todavía no respondieron. Si el líder propone basándose solo en lo que vio, puede proponer algo que la réplica bloqueada rechaza. Si suficientes réplicas correctas quedan en esa situación, ninguna propuesta reúne el quórum y el protocolo no avanza, aunque la red sea perfectamente estable. [3]

El líder tiene entonces tres opciones: pedir a cada réplica una prueba completa de su estado, como hace PBFT en su cambio de vista; esperar lo suficiente para oír a todas las réplicas correctas; o cambiar el protocolo para que lo que ve entre $n - f$ mensajes siempre baste. [3]

La solución de Tendermint: esperar la cota máxima

Tendermint elige la segunda opción. Su protocolo avanza por rondas con pasos de propuesta, prevote y precommit, usa timeouts que crecen con el número de ronda y difunde mensajes por gossip, de modo que después de GST cada réplica correcta termina recibiendo lo que las demás enviaron. [1] Las réplicas recuerdan no solo su lock, sino también el valor más reciente que vieron respaldado por un quórum de prevotes (validValue), y el proponente de una ronda propone ese valor cuando lo tiene. [1]

Leído desde HotStuff, el efecto es que un líder nuevo debe esperar la cota máxima de retardo antes de proponer: solo así, después de GST, tiene garantizado haber recibido el lock más alto de toda réplica correcta. [2] La ventaja es que el cambio de líder sigue siendo barato en comunicación y que bastan dos fases de votación. El precio es la pérdida de responsividad: esa espera dura $\Delta$ aunque la red entregue todo en $\delta \ll \Delta$. [3]

La solución de HotStuff: una fase más

HotStuff elige la tercera opción. Añade una fase de votación entre la formación del primer certificado y el bloqueo, de modo que una réplica correcta solo se bloquea cuando ya existe un quórum de réplicas que conocen el certificado correspondiente. Como consecuencia, si alguna réplica correcta está bloqueada, cualquier conjunto de $n - f$ mensajes new-view contiene un highQC al menos tan alto como ese lock. [2]

El líder ya no tiene que esperar a nadie en particular: recoge $n - f$ mensajes new-view, extiende el highQC más alto que encuentra y las réplicas bloqueadas lo aceptan, porque la regla safeNode permite votar por una propuesta cuyo QC es más reciente que el lockedQC local. [2] Además, como cada réplica envía un solo QC, el cambio de líder es lineal en comunicación, que era precisamente lo que PBFT no lograba. El análisis de esa regla de commit está en QC, highQC y la regla de tres cadenas.

El costo es visible en el camino feliz: una fase adicional significa un viaje de ida y vuelta más antes de confirmar una decisión. HotStuff cambia latencia de commit en el caso estable por responsividad y linealidad en el cambio de líder. [2] [3]

Figura 1

Cambio de líder: esperar la cota de red o avanzar con el highQC

Fuentes:

[1][2]

Cómo leer esta figura

Dos paneles. A la izquierda, Tendermint: tras la caída del líder, el nuevo líder espera un tiempo Δ y luego propone. A la derecha, HotStuff: tras la caída del líder, el nuevo líder recibe n − f mensajes new-view, toma el highQC más alto y propone al ritmo real de la red δ, sin esperar Δ.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

El compromiso, sin marketing

Visto en conjunto, ninguna de las dos opciones domina a la otra en todos los ejes. Tendermint tiene dos fases y un cambio de líder lineal, pero no es responsive. HotStuff es responsive y lineal, pero confirma con una fase más. PBFT es responsive con dos fases, pero su cambio de vista no es lineal. Malkhi y Nayak organizan precisamente estos protocolos como puntos distintos de un mismo compromiso entre fases, comunicación en el cambio de vista y responsividad. [3]

La historia no terminó con HotStuff. La misma comparación presenta HotStuff-2 como una forma de recuperar las dos fases sin perder la linealidad, pagando la espera solo en las situaciones de cambio de líder en que es estrictamente necesaria. [3] Ese desarrollo se estudia en HotStuff-2 y la frontera DAG-BFT.

Conviene también no idealizar la propiedad. Un estudio reciente sobre protocolos BFT encadenados analiza cómo se comporta la responsividad cuando el retardo de la red varía, y advierte que su beneficio depende del modelo de red y de las condiciones concretas, no es una ventaja universal. [4] La conclusión práctica es medir: la distancia entre $\delta$ y $\Delta$ en el despliegue real decide cuánto vale ahorrar la espera frente a pagar una fase más.

Siguiente lectura

Continúa con Uno, dos y tres chains: la taxonomía de commit, donde el número de fases se traduce en reglas de commit sobre cadenas de certificados.