Recorte localizado
Consenso BFT do zero: réplicas, quóruns e falhas bizantinas
Que problema a tolerância a falhas bizantinas resolve, por que surge n ≥ 3f + 1 e como separar safety de liveness antes de ler HotStuff.
Várias máquinas que se comportam como uma
Em State Machine Replication todas as réplicas corretas aplicam as mesmas operações na mesma ordem. O desafio do BFT é conseguir isso mesmo quando parte do grupo mente, cai, atrasa ou tenta sabotar a ordem acordada.
Crash não é bizantino
Um nó com crash fault simplesmente silencia. Um nó bizantino pode propor dois blocos na mesma visão, votar de forma diferente para grupos diferentes ou atrasar mensagens de propósito. Tolerar esse comportamento arbitrário exige assinaturas, quóruns e regras de voto verificáveis.
- Crash: o nó deixa de responder ou reinicia.
- Bizantino: o nó pode agir de forma arbitrária, inclusive com equivocation.
A aritmética mínima: n ≥ 3f + 1
Para tolerar f réplicas bizantinas são necessárias ao menos 3f + 1 réplicas e quóruns de 2f + 1. Dois quóruns se cruzam em pelo menos f + 1 réplicas, então a interseção sempre contém uma réplica correta: é ali que vive a segurança. A liveness, por outro lado, depende de hipóteses de sincronia parcial.
Referências
[1]
Castro and Liskov, Practical Byzantine Fault Tolerance (OSDI 1999)Primeiro sistema BFT prático: replicação de máquina de estados com 3f + 1 réplicas.
[2]
Dwork, Lynch and Stockmeyer, Consensus in the Presence of Partial Synchrony (JACM 1988)Origem dos limites de quórum e do modelo de sincronia parcial.
[3]
Yin et al., HotStuff: BFT Consensus in the Lens of Blockchain (2019)O protocolo ao qual a série conduz: troca de líder linear e responsividade otimista.