Corte localizado
Consenso BFT desde cero: réplicas, quórums y fallas bizantinas
Qué problema resuelve la tolerancia a fallas bizantinas, por qué aparece n ≥ 3f + 1 y cómo separar safety de liveness antes de leer HotStuff.
Varias máquinas que se comportan como una
En State Machine Replication todas las réplicas correctas aplican las mismas operaciones en el mismo orden. El reto de BFT es lograrlo aunque una parte del grupo mienta, se caiga, se atrase o intente sabotear el orden acordado.
Crash no es bizantino
Un nodo con crash fault simplemente calla. Un nodo bizantino puede proponer dos bloques en la misma vista, votar distinto ante grupos distintos o retrasar mensajes a propósito. Tolerar ese comportamiento arbitrario exige firmas, quórums y reglas de voto verificables.
- Crash: el nodo deja de responder o reinicia.
- Bizantino: el nodo puede actuar de forma arbitraria, incluso con equivocation.
La aritmética mínima: n ≥ 3f + 1
Para tolerar f réplicas bizantinas se necesitan al menos 3f + 1 réplicas y quórums de 2f + 1. Dos quórums se cruzan en al menos f + 1 réplicas, así que la intersección contiene siempre una réplica correcta: ahí vive la seguridad. La liveness, en cambio, depende de supuestos de sincronía parcial.
Referencias
[1]
Castro and Liskov, Practical Byzantine Fault Tolerance (OSDI 1999)Primer sistema BFT práctico: replicación de máquina de estados con 3f + 1 réplicas.
[2]
Dwork, Lynch and Stockmeyer, Consensus in the Presence of Partial Synchrony (JACM 1988)Origen de los límites de quórum y del modelo de sincronía parcial.
[3]
Yin et al., HotStuff: BFT Consensus in the Lens of Blockchain (2019)El protocolo al que conduce la serie: cambio de líder lineal y respuesta optimista.