Bizâncio, a capital do antigo Império Romano do Oriente, foi uma das cidades mais poderosas e ricas do mundo. No entanto, devido ao seu vasto território, Bizâncio enfrentava frequentemente invasões externas e rebeliões internas. Para defender as suas fronteiras, Bizâncio enviou múltiplos exércitos, cada um comandado por diferentes generais. Alcançar consenso entre esses generais tornou-se um desafio significativo.
O Problema dos generais bizantinos tem uma relação próxima com a blockchain. Uma rede blockchain é uma rede distribuída onde os nós, como os generais bizantinos, devem alcançar consenso sobre transações e dados num ambiente de rede não confiável.

Problema dos dois generais

O Problema dos Dois Generais é um caso especial do Problema dos generais bizantinos. O problema e sua prova de insolubilidade foram propostos pela primeira vez por E.A. Akkoyunlu, K.Ekanadham e R.V. Huber no seu artigo de 1975 “Algumas restrições e compensações no design de comunicações em rede.” Em 1978, Jim Gray formalmente nomeou este problema como o “Problema dos Dois Generais” no seu livro “Notas sobre Sistemas Operacionais de Banco de Dados.” Originalmente, era usado para analisar os problemas de alcançar consenso através da comunicação sobre uma ligação de comunicação não fiável. Atualmente, é comumente usado para ilustrar questões de consistência e consenso em sistemas distribuídos.

Definição do Problema:
Duas armadas do país A, cada uma liderada por um general, estão se preparando para atacar uma armada do país B. A armada do país B está cercada num vale, com as duas armadas de A estacionadas nas colinas de cada lado do vale. No entanto, o único caminho entre as duas armadas de A passa pelo vale. A armada de B é mais forte do que qualquer uma das armadas de A individualmente, mas se ambas as armadas de A atacarem juntas, podem derrotar a armada de B.
Problema: Pode ser elaborado um algoritmo que permita que os dois generais dos exércitos de A concordem com um ataque simultâneo? O algoritmo pode incluir o envio e receção de mensagens.
Solução: O clássico Problema dos Dois Generais é insolúvel. Não há nenhum protocolo que possa garantir que os dois exércitos de A coordenarão com sucesso o seu ataque. No entanto, em sistemas práticos, as questões podem ser abordadas de forma relativamente confiável, como com o mecanismo de "aperto de mão de três vias" no protocolo TCP.

Problema dos generais bizantinos

O Problema dos generais bizantinos foi proposto pela primeira vez por Leslie Lamport, vencedor do Prêmio Turing de 2013, no seu artigo de 1982 “O Problema dos generais bizantinos”. O problema descreve como alcançar consistência em sistemas distribuídos na presença de comportamento malicioso, como a adulteração de mensagens.
Várias armadas do Império Bizantino cercam uma cidade inimiga, cada uma liderada por um general. As armadas bizantinas só podiam comunicar através de mensageiros. Após observar as forças inimigas, os generais bizantinos devem chegar à mesma conclusão: apenas se mais da metade das armadas bizantinas atacarem juntas podem capturar a cidade e alcançar a vitória.

Solução: Se o número de generais (nós) em um sistema bizantino for Z e o número de generais não confiáveis (traidores) for X, então apenas quando Z ≥ 3X + 1 pode um protocolo de Tolerância a Falhas Bizantinas (BFT) garantir a consistência do sistema.
Em sistemas práticos, falhas que causam nós inativos são classificadas como “Falhas de Colisão,” enquanto nós que forjam ou adulteram mensagens são classificados como “Falhas Bizantinas.”

Classificação do Algoritmo de Consenso

Os sistemas de blockchain são um tipo de sistema distribuído, especialmente as cadeias públicas como o Bitcoin e o Ethereum, que consistem em numerosos nós de rede altamente descentralizados e mutuamente desconfiados. O mecanismo de consenso blockchain garante que o sistema blockchain alcance consistentemente a consistência dos dados sem bifurcações.
Com base no tipo de tolerância a falhas, os algoritmos de consenso podem ser classificados em algoritmos de Tolerância a Falhas Não-Byzantina (CFT) e algoritmos de Tolerância a Falhas Bizantinas (BFT).

Algoritmos de Tolerância a Falhas não Bizantinas

Em sistemas distribuídos, os algoritmos de Tolerância a Falhas Não-bizantinas garantem a confiabilidade de todo o sistema distribuído quando os nós enfrentam falhas no sistema ou interrupções não planeadas (falhas não-bizantinas). No entanto, quando os nós maliciosos forjam ou adulteram dados, os algoritmos de Tolerância a Falhas Não-bizantinas não conseguem garantir a confiabilidade do sistema. Esses algoritmos são usados principalmente em sistemas distribuídos empresariais fechados e controlados. Os algoritmos de Tolerância a Falhas Não-bizantinas mais representativos incluem o algoritmo Paxos e o algoritmo Raft.

Algoritmos de Tolerância a Falhas Bizantinas

Os algoritmos de Tolerância a Falhas Bizantinas permitem que um sistema distribuído garanta a fiabilidade, mesmo que os nós sofram qualquer tipo de falha, desde que o número de nós defeituosos não exceda uma certa proporção. Simplificando, desde que o número de nós defeituosos (devido a falhas não bizantinas ou bizantinas) seja inferior a uma certa proporção do total de nós, os algoritmos de Tolerância a Falhas Bizantinas podem garantir a fiabilidade do sistema. Devido à presença de muitos nós de rede desconfiados em sistemas blockchain como Bitcoin e Ethereum, os algoritmos de Tolerância a Falhas Bizantinas são principalmente utilizados em mecanismos de consenso blockchain. Os algoritmos de Tolerância a Falhas Bizantinas mais representativos incluem PBFT (Tolerância a Falhas Bizantinas Prática), PoW (Prova de Trabalho) e PoS (Prova de Participação).