Consenso BFT desde cero: réplicas, quórums y fallas bizantinas

Antes de HotStuff hay una idea menos glamorosa y más importante: varias máquinas deben comportarse como una sola, incluso si algunas mienten, se caen, se atrasan o intentan sabotear la película. [3]

Ese es el terreno de Byzantine Fault Tolerance. Si vienes de APIs, bases de datos o cloud, piensa en BFT como una disciplina para responder esta pregunta:

¿Cómo hago que un grupo de nodos acuerde el mismo historial aunque una parte del grupo sea arbitraria?

El problema: una sola máquina imaginaria

En State Machine Replication las réplicas ejecutan las mismas operaciones en el mismo orden. Si el log dice:

1. crear cuenta,
2. transferir 10,
3. cerrar lote,

entonces todas las réplicas correctas deben aplicar exactamente esa secuencia. Si una ve transferir antes de crear cuenta, ya no tenemos sistema distribuido: tenemos novela experimental.

PBFT hizo famosa esta idea en un sistema práctico para tolerar fallas bizantinas. [1] HotStuff hereda esa ambición, pero simplifica el cambio de líder y reduce el costo de comunicación en el camino feliz. [3]

Crash no es bizantino

Un nodo con crash fault se apaga, se congela o deja de responder. Molesto, sí. Pero relativamente fácil de razonar: el nodo calla.

Un nodo bizantino puede:

• proponer dos bloques distintos en la misma vista;
• votar una cosa a un grupo y otra al resto;
• perder su lock "por accidente";
• atrasar mensajes para forzar cambios de líder.

La aritmética mínima: n >= 3f + 1

La regla clásica de BFT autenticado es: [2]

Si quieres tolerar f réplicas bizantinas, necesitas al menos 3f + 1 réplicas totales. Para finalizar algo normalmente buscas un quórum de:

El detalle sabroso está en la intersección: dos quórums de 2f + 1 dentro de 3f + 1 réplicas se cruzan en al menos f + 1 nodos. Como solo f pueden ser bizantinos, esa intersección contiene al menos una réplica correcta. Ahí vive la seguridad. [2]

Figura 1

Intersección de quórums BFT

Fuentes:[2]

📖 Cómo leer esta figura (Detalle explicativo)

Los dos círculos representan quórums de 2f + 1 dentro de un universo de 3f + 1 réplicas. Su intersección mínima contiene f + 1 miembros; como a lo sumo f son bizantinos, al menos uno es correcto. Ese miembro común impide certificar dos afirmaciones incompatibles si conserva la regla de voto.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en pestaña nueva

Safety y liveness: no los mezcles

Safety significa que no pasan cosas malas: dos réplicas correctas no finalizan historiales incompatibles.

Liveness significa que eventualmente pasan cosas buenas: si la red se porta lo suficiente y hay líderes correctos, el sistema sigue avanzando. [2]

La intuición importante:

• safety debe aguantar incluso con retrasos y líderes malos;
• liveness necesita condiciones de red y mecanismos de cambio de líder;
• en HotStuff, los certificados ayudan a que ambas propiedades no se peleen.

Qué debes llevarte

Si recuerdas una sola cosa, que sea esta:

Profundización conceptual

Modelo mental: acuerdo sobre historial, no sobre verdad

Un protocolo BFT no intenta descubrir "la verdad" del mundo exterior. Esa parte queda en clientes, aplicaciones, oráculos, firmas de usuario, reglas de negocio y validaciones locales. El protocolo intenta algo más específico: que las réplicas correctas acuerden el mismo historial ordenado. Si dos operaciones compiten por la misma posición del log, el consenso no pregunta cuál se ve más simpática; pregunta cuál puede ser respaldada por suficiente evidencia bajo el modelo de fallas.

Esa distinción parece académica, pero salva muchas confusiones. Una blockchain no es segura porque todos los validadores sean buenos, sino porque el sistema limita cuánto daño puede hacer una minoría arbitraria. Si el log final dice A, B, C, todas las réplicas correctas deben terminar con un prefijo compatible con A, B, C. Puede haber retrasos, vistas fallidas y líderes torpes; lo que no puede haber es una réplica correcta finalizando A, B, C y otra finalizando A, X, C en la misma altura. Ahí se rompe la película.

La palabra práctica para recordar es prefijo. Dos réplicas correctas pueden estar en momentos distintos, pero sus historias finalizadas deben poder alinearse como prefijos de una misma historia. Si una va más adelante, la otra debería poder alcanzarla sin borrar una decisión finalizada. [1]

Invariante: una decisión finalizada no debe tener gemela incompatible

El invariante base de BFT es sencillo de decir y difícil de preservar: una vez que un valor queda decidido para una posición, ningún valor incompatible debe decidirse para esa misma posición. En protocolos concretos, ese invariante se implementa con reglas de voto, locks, certificados, vistas y restricciones sobre qué propuestas son seguras de extender.

La aritmética 3f + 1 no es decoración. Si dos certificados requieren 2f + 1 votos, esos dos conjuntos se intersectan en al menos f + 1 réplicas. Como a lo sumo f son bizantinas, al menos una réplica correcta está en la intersección. Esa réplica correcta es el puente de memoria entre el pasado y el futuro: no debería firmar dos historias incompatibles si el protocolo le exige mantener su lock, verificar la evidencia y rechazar propuestas inseguras.

Más adelante HotStuff empaqueta esta idea en QCs y highQC. Por ahora basta con verlo así: el sistema no confía en "mayoría" de forma ingenua; confía en que dos mayorías BFT no pueden ser totalmente independientes. [3]

Escenario adversarial: el líder que cuenta dos cuentos

Imagina un líder bizantino que propone el bloque B a la mitad de la red y el bloque B' a la otra mitad. Además, retrasa mensajes para que cada grupo crea que el otro está caído. Si el protocolo aceptara mayoría simple, el líder podría fabricar dos mundos paralelos: uno donde B parece ganador y otro donde B' parece ganador.

En BFT, la pregunta es: ¿puede conseguir dos certificados válidos? Para lograrlo necesitaría dos quórums de 2f + 1. Pero esos quórums se cruzan en al menos una réplica correcta. Esa réplica correcta vería la incompatibilidad o quedaría bloqueada por una regla de voto anterior. Si firma ambos lados, el invariante se pierde; por eso los protocolos dedican tanta ingeniería a definir cuándo se puede votar, cuándo se puede desbloquear y qué evidencia debe traer el nuevo líder.

Esta es la razón por la que los papers parecen obsesionados con mensajes firmados. La firma no es solo autenticación; es memoria verificable. Un nodo bizantino puede mentir, pero no debería poder negar fácilmente que firmó una propuesta contradictoria.

Cómo leer el paper desde aquí

Cuando abras PBFT, DLS u HotStuff, no empieces por memorizar cada mensaje. Primero busca cuatro piezas:

1. Modelo: cuántas réplicas hay, cuántas pueden fallar, si las firmas existen y qué se asume de la red.
2. Regla de seguridad: qué evita que dos valores incompatibles sean decididos.
3. Regla de progreso: bajo qué condiciones eventualmente se decide algo.
4. Cambio de líder: qué evidencia viaja cuando el líder falla o miente.

En PBFT, presta atención a prepared, committed-local y view-change. [1] En HotStuff, mira QC, highQC y la regla de cadena. [3] Si un paper afirma "linear communication" o "responsiveness", no lo leas como magia de marketing: pregunta en qué camino, bajo qué líder y después de qué supuesto de red. Esa pequeña disciplina evita tragarse benchmarks con moño.

Siguiente lectura

Continúa con sincronía parcial, quórums y la aritmética BFT. Ahí se formaliza cuándo puede progresar el protocolo, por qué aparecen 3f + 1 réplicas y cómo la intersección de quórums sostiene safety.