O Problema dos Generais Bizantinos investiga se processos corretos podem concordar com uma decisão quando processos defeituosos agem arbitrariamente e enviam mensagens contraditórias a destinatários diferentes. A formulação de Lamport, Shostak e Pease de 1982 prova o limite inferior de 3m+1 participantes para tolerar m traidores com mensagens orais sem assinaturas e descreve algoritmos recursivos para mensagens orais e assinadas. São resultados sob hipóteses precisas, não um sinônimo de todo consenso em blockchain.
Lamport, Shostak e Pease publicaram a alegoria na ACM TOPLAS em julho de 1982 para explicar consistência interativa em sistemas replicados. Generais separados devem escolher um plano embora traidores enviem versões diferentes. Uma falha bizantina é mais forte que uma parada: o componente pode mentir, equivocar, omitir ou parecer correto apenas para parte do sistema. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
O artigo separa IC1: todos os tenentes leais seguem a mesma ordem, e IC2: se o comandante é leal, seguem a ordem dele. Termos modernos relacionados são acordo ou segurança, validade e terminação ou vivacidade. Garantias só fazem sentido com modelo de rede, autenticação e número máximo de falhas declarados. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Em mensagens orais conhece-se o remetente direto, detecta-se ausência e todos se comunicam, mas um traidor envia valores distintos. OM(m) retransmite recursivamente e aplica maioria determinística. Tolerar m processos bizantinos exige pelo menos 3m+1 participantes, mais de dois terços leais. Três processos não toleram um traidor porque o leal não distingue comandante mentiroso de colega mentiroso. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Assinaturas infalsificáveis revelam equivocações e impedem alterar ordem assinada por leal. O algoritmo retransmite valores assinados inéditos e decide sobre o conjunto coletado. Sob hipóteses ideais admite qualquer número de traidores. Porém assinatura prova origem, não verdade, entrega pontual ou chave não comprometida; Dolev e Strong depois precisaram limites de rodadas. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Garantir progresso depende do tempo. Fischer–Lynch–Paterson mostrou em 1985 que um sistema determinístico totalmente assíncrono de mensagens, mesmo permitindo a parada de um só processo, admite uma execução sem terminar o consenso. FLP não diz que sistemas reais nunca concordam. A vivacidade exige premissas adicionais, como limites temporais posteriores ou um detector de falhas com propriedades definidas, ou mudança para protocolo aleatório. Nomear um líder não basta. Em uma partição longa, um protocolo seguro pode parar de concluir operações. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT de Miguel Castro e Barbara Liskov (1999) aplica acordo bizantino a uma máquina de estados replicada. Na configuração básica n = 3f+1, tolera f réplicas bizantinas. Estar preparado inclui um pre-prepare da réplica primária e 2f mensagens prepare correspondentes; confirmação local exige estar preparado e 2f+1 mensagens commit correspondentes. Interseções de quóruns e regras de mudança de visão impedem confirmações contraditórias. Autenticação, sequências, pontos de controle e mudanças de visão tratam falsificação, repetição, crescimento do registro e líder defeituoso. Membros conhecidos e finalidade determinística diferem de uma rede aberta Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin não executa OM nem PBFT e não conta nós identificados. Proof of Work resistente a Sybils pondera histórias por trabalho acumulado; cada Full Node rejeita sozinho blocos contrários ao consenso e segue a cadeia válida com mais trabalho. Bifurcações temporárias são esperadas. Sob premissas de maioria honesta de trabalho e comunicação, a probabilidade de substituição cai com a profundidade, sem irreversibilidade matemática. Bitcoin Backbone formaliza prefixo comum, crescimento e qualidade sob condições explícitas de trabalho adversário e rede. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Dizer que Bitcoin resolveu o problema oculta mudança de modelo. O acordo clássico começa com grupo fixo de identidades conhecidas e limite f; Bitcoin admite pseudônimos variáveis e recurso escasso externo. Suas garantias ainda exigem hipóteses concretas de entrega. Proof of Work limita Sybils, mas não impede ataques eclipse, censura, mineração egoísta, erros de software ou reorganização por maioria de poder computacional. O modelo de ameaça deve especificar adversário, tempo, membros e finalidade; apenas BFT não basta. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Para ter uma visão mais completa, leia este verbete junto com Nakamoto consensus, Proof of Work, Regras de consenso, Gasto duplo, Bitcoin, Finality.