Byzantine Generals Problem

Imagine tropas posicionadas ao redor de uma cidade. Precisam atacar juntas ou recuar juntas; agir separadamente poderia ser desastroso. O comandante envia ordens, mas alguém pode trair o grupo e contar versões diferentes. Como os participantes confiáveis podem acabar agindo da mesma maneira? Não é o relato de uma batalha histórica, mas um experimento mental sobre computadores que precisam manter registros coerentes. Vários servidores, computadores que oferecem um serviço compartilhado, podem, por exemplo, precisar concordar sobre se um pagamento já foi processado. Receber alguma resposta não basta: as respostas precisam sustentar uma decisão comum. [1] [9]

Leslie Lamport, Robert Shostak e Marshall Pease apresentaram a formulação conhecida em julho de 1982, depois do trabalho de 1980 sobre acordo na presença de falhas. O traidor representa um componente cujo comportamento já não podemos prever. Um computador não precisa simplesmente parar. Pode responder corretamente a um vizinho e incorretamente a outro, omitir mensagens ou afirmar que viu outra coisa. Um ataque ou um defeito de software pode causar isso. Falha bizantina descreve o que os demais observam, não a intenção do equipamento. BFT (Byzantine Fault Tolerance), tolerância a falhas bizantinas, é a capacidade de suportar esse comportamento sob condições definidas. [1] [2]

O problema original estabelece duas condições. IC1 exige que todos os subordinados confiáveis aceitem a mesma ordem. IC2 acrescenta que, se o comandante também for confiável, devem aceitar a ordem que ele realmente enviou. Sem a segunda condição, “recuar sempre” pareceria uma solução, mas ignoraria um comandante honesto. Sistemas computacionais distinguem segurança, que impede resultados contraditórios, de vivacidade, que permite chegar a um resultado. Outras regras determinam quais resultados são válidos. Um registro coerente não prova, por si só, que uma afirmação recebida era verdadeira no mundo exterior. [1] [9]

Chamemos o comandante de A e seus subordinados de B e C. C recebe de A a ordem de atacar, mas B diz que o comandante ordenou recuar. B está mentindo ou A enviou ordens diferentes? Sem uma assinatura verificável depois do encaminhamento, C pode não distinguir as situações. B pode enfrentar a mesma incerteza. Obedecer sempre ao comandante permite que um A desonesto os divida; ignorá-lo sempre viola a condição para um comandante honesto. Nesse problema com três participantes e um possível traidor, não existe procedimento sem assinaturas que sempre funcione. Faltam informações que distingam os casos, não computadores mais rápidos. [1] [9]

No modelo clássico sem assinaturas, tolerar m possíveis traidores exige pelo menos n ≥ 3m+1 participantes: quatro para um traidor. Aqui, n é o total de participantes e m, o número máximo de traidores que o sistema deve tolerar. Não basta acrescentar um voto e contar a maioria uma vez. OM(m) faz os participantes retransmitirem o que ouviram e avaliarem as mensagens segundo regras comuns; seu caso básico OM(0) adota o valor do comandante ou um valor padrão combinado. O modelo supõe participantes conhecidos, conexões diretas, entrega correta das mensagens enviadas, identificação do remetente imediato e capacidade de detectar mensagens ausentes. “Sem assinaturas” não significa “sem qualquer autenticação de origem”. Sem essas premissas, o número quatro não garante nada. [1] [9]

Com uma assinatura digital verificável, Digital Signature, B pode mostrar a C o que o comandante realmente assinou. Um programa cria essa assinatura com uma chave privada, um valor numérico secreto. Os demais a verificam com a chave pública correspondente, sem precisar conhecer a privada. Um traidor não pode alterar discretamente a ordem de um participante confiável nem imitar sua assinatura. O algoritmo de mensagens assinadas distribui valores assinados e aplica uma regra comum de escolha. Esse modelo dispensa a exigência anterior de maioria honesta, mas mantém as premissas de assinaturas infalsificáveis, entrega e temporização das rodadas. O trabalho de Dolev e Strong de 1983 aprofunda o número de rodadas necessário. Uma assinatura válida não garante conteúdo verdadeiro nem entrega no prazo, e não prova que a chave privada não tenha sido roubada. Comprova a origem de uma mensagem específica, não a confiabilidade geral do remetente. [1] [3]

Quando um servidor não responde, os demais não sabem se ele parou ou se sua conexão é muito lenta. O resultado FLP, publicado em 1985 por Michael Fischer, Nancy Lynch e Michael Paterson, delimita essa incerteza. Processo significa aqui um programa em execução. Um procedimento determinístico dá o mesmo próximo passo quando o estado e a entrada são iguais; ele não escolhe esse passo ao acaso. Num sistema totalmente assíncrono, sem limite superior conhecido para atrasos, um procedimento determinístico não pode garantir a conclusão do acordo em toda execução admissível se até um único processo puder parar por falha. Isso vale mesmo com entrega confiável e atrasos sem limite definido. Não significa que o acordo nunca aconteça. Sistemas práticos acrescentam premissas de tempo, um detector de falhas adequado ou aleatoriedade. Durante uma divisão da rede, esperar pode ser mais seguro que confirmar resultados incompatíveis. [4] [13] [8]

Miguel Castro e Barbara Liskov descreveram em 1999 o Practical Byzantine Fault Tolerance, PBFT, para um serviço executado em várias réplicas conhecidas. Essas réplicas são cópias do serviço que funcionam em servidores diferentes e processam continuamente as mesmas solicitações. Não são arquivos de backup guardados para uso posterior. A configuração básica n = 3f+1 tolera f réplicas defeituosas. Entre quatro servidores, um pode ser bizantino; dois grupos de três compartilham pelo menos dois servidores, e pelo menos um deles deve ser confiável. Esse conjunto necessário de aprovações é um quórum. Só a interseção não basta: também importam as fases do protocolo e a troca de líder. Mais precisamente, o estado prepared exige a solicitação, uma mensagem pre-prepare e 2f mensagens prepare correspondentes de réplicas distintas que não sejam a primária. A confirmação local requer ainda 2f+1 mensagens commit, podendo incluir a própria. Autenticação, números de sequência e pontos de controle enfrentam falsificações, repetições e crescimento ilimitado do registro. A segurança independe de limites temporais, mas o progresso precisa de condições adicionais sobre os atrasos. [5] [10] [11] [12]

Bitcoin não tem uma lista fechada de servidores definida antecipadamente. Se cada nova conta recebesse um voto, um atacante poderia fabricar uma maioria: isso é um Sybil Attack. Proof of Work vincula a produção de blocos ao trabalho computacional. Um bloco é um lote de transações acrescentado ao histórico compartilhado. Um Full Node, um computador com software que verifica as regras por conta própria, primeiro rejeita blocos inválidos e depois segue a ramificação válida com mais trabalho acumulado. Bitcoin não executa OM nem PBFT; bifurcações temporárias fazem parte de seu funcionamento. Com poder computacional honesto suficiente e comunicação adequada, mais confirmações reduzem o risco de reescrita, mas não criam irreversibilidade absoluta. A pesquisa Bitcoin Backbone examina essas condições: concordância entre históricos, crescimento da cadeia e proporção de blocos que participantes honestos podem produzir. [6] [7]

Diante da frase “a rede alcança consenso”, procure respostas concretas: quem pode participar, o que o atacante controla, quanto tempo as mensagens podem levar e quando uma decisão pode mudar? Nem Proof of Work elimina todos os problemas. Um Eclipse Attack isola um nó de pares honestos, a censura exclui transações e Selfish Mining envolve reter blocos minerados. Também permanecem defeitos de software e a possibilidade de reescrever parte do histórico com força atacante suficiente. Ainda assim, nem a maioria do poder computacional obriga um Full Node funcionando corretamente a aceitar um bloco contrário às suas regras. A história dos generais ensina a examinar as condições do acordo, em vez de confiar no nome de uma tecnologia. [6] [7] [8]