Ir para o conteúdo
Financial Context Wiki

Problema dos generais bizantinos: acordo sob mensagens conflitantes

O problema dos generais bizantinos pergunta como participantes honestos podem concordar quando os defeituosos enviam informações conflitantes. Tarefa, canais, autenticação, limite de falhas, cota, algoritmo e implantação devem ser separados.

Atualizado

Material educativo para análise de protocolos. Resolver um modelo de acordo bizantino não comprova que uma rede implantada seja segura, ativa, correta, descentralizada, final ou capaz de proteger ativos.

Resposta direta

O problema dos generais bizantinos pergunta como participantes não defeituosos que se comunicam por mensagens podem tomar uma decisão coerente quando alguns agem arbitrariamente, inclusive enviando afirmações diferentes a destinatários diferentes. A história militar é analogia da consistência interativa em sistemas distribuídos, não fato histórico nem algoritmo específico de consenso de blockchain.

Na formulação de comandante e tenentes, IC1 exige que todos os tenentes leais obedeçam à mesma ordem, enquanto IC2 exige que obedeçam à ordem do comandante quando ele é leal. Acordo sozinho é insuficiente: escolher sempre RETIRADA produz acordo, mas viola uma ordem válida de ATAQUE de um comandante leal.

No modelo de “mensagens orais” do artigo, com no máximo m traidores, há solução apenas quando n>3m, equivalente para participantes inteiros a n>=3m+1. O modelo presume que mensagens enviadas por leais são entregues corretamente, o destinatário conhece o remetente e a ausência esperada pode ser detectada. “Oral” significa que conteúdo não autenticado pode ser falsificado como relato de outro participante; não que um mensageiro desapareça para sempre sem detecção.

O modelo de “mensagens assinadas” acrescenta assinaturas não falsificáveis e verificáveis publicamente, mudando o resultado de resiliência. Não torna verdadeiro o conteúdo, não garante entrega nem término totalmente assíncrono, não protege chaves roubadas nem prova a segurança moderna. O problema bizantino, o dos dois generais ou ataque coordenado, FLP, BFT, prova de trabalho e prova de participação são modelos ou construções relacionados, porém distintos.

Como analisar

  1. Defina a tarefa de acordo. Declare participantes, entradas, saídas e propriedades exatas de acordo, validade e término. Na formulação do comandante, escreva IC1 e IC2 em vez de apenas “alcançar consenso”.
  2. Defina identidades e canais. Informe se mensagens ponto a ponto são autenticadas, entregues, ordenadas, protegidas contra repetição e atribuíveis; se omissão é detectável; e se difusão é primitiva ou envios repetidos.
  3. Defina o tempo. Separe sincronia de atraso limitado, sincronia parcial após instante desconhecido e assincronia total. Não adicione mensageiros desaparecidos a um modelo e preserve teorema de outro.
  4. Defina o orçamento de falhas. Registre participantes totais n, máximo bizantino m, corrupção estática ou adaptativa e se inclui omissão, equivocação, conluio, roubo de chaves ou canais defeituosos.
  5. Rastreie informação recursivamente. Para cada leal, liste afirmações diretas e retransmitidas, caminhos de remetentes, padrões para ausência e desempates determinísticos; compare execuções distinguíveis por duas visões locais.
  6. Confira teorema e algoritmo juntos. Ajuste cotas e suficiência ao modelo oral ou assinado, conectividade e orçamento exatos. Uma desigualdade não é implementação nem prova.
  7. Mapeie para a implantação. Verifique o OM(m), SM(m) ou outro mecanismo, domínios, rodadas, bloqueios, certificados, mudanças de membros, prazos, clientes, finalidade e política de confirmação reais.

A técnica central é a indistinguibilidade. Um participante leal vê apenas mensagens locais; se duas execuções parecem iguais para ele, mas a validade exige decisões diferentes, nenhuma regra determinística acerta sempre. Protocolos adicionam participantes independentes, evidência autenticada, premissas temporais, aleatoriedade ou outra estrutura para distinguir as execuções necessárias ou alterar a garantia.

Exemplos calculados

1. Por que três generais com mensagens orais não toleram um traidor

Considere n=3 e m=1. A condição n>3m torna-se 3>3, falsa. Suponha que o comandante A diga ATTACK a B e RETREAT a C. B não distingue se A é traidor e enviou ordens conflitantes ou se C é traidor e mentiu sobre A; C enfrenta incerteza simétrica.

Qualquer escolha determinística que preserve a ordem de A em execuções nas quais A é leal pode obrigar B e C a decidir diferente quando A é traidor. Retransmitir não cria uma quarta fonte independente, então IC1 e IC2 não podem ser garantidos juntos.

2. Quatro generais com mensagens orais e um traidor

Em OM(1), n=4 e m=1. O comandante envia uma ordem a três tenentes; cada um retransmite o valor aos outros dois; cada leal usa a mesma maioria e padrão. Se o comandante é leal e envia v, um leal vê v, v e um possível x do traidor e escolhe v.

Se o comandante é o único traidor, os três tenentes são leais e retransmitem exatamente o recebido. Assim reconstruem o mesmo conjunto de afirmações do comandante e aplicam a mesma regra. Talvez não recuperem sua “intenção real”, mas satisfazem o acordo.

3. Cota geral das mensagens orais

Com n=7 e m=2, 7>6 vale, então a quantidade satisfaz a condição e a construção recursiva tolera até dois traidores sob as demais premissas. Para n=6, 6>6 é falso. Para n=10 e m=3, 10>9 vale. Passar a desigualdade é necessário; rodadas, retransmissão, maioria, padrões e canais corretos também.

4. O que as assinaturas mudam

Num exemplo com três generais SM(1), o comandante traidor assina ATTACK para B e RETREAT para C. Os tenentes leais encaminham ambas, recebem o mesmo conjunto {ATTACK, RETREAT} e aplicam o mesmo padrão, por exemplo RETREAT. A equivocação do comandante fica atribuída.

As assinaturas impedem falsificar ou alterar sem detecção a ordem de um leal no modelo. Não revelam qual ordem é a “intenção real” do traidor, não garantem entrega pontual nem impedem quem controla chave legítima de assinar ambas.

Riscos e falhas de revisão

Problema e modelo

  • Repetir a alegoria sem condições precisas de acordo, validade e término.
  • Tratar o problema como cerco histórico, algoritmo único ou sinônimo de blockchain.
  • Confundi-lo com os dois generais, centrado em conhecimento comum por canal não confiável.
  • Adicionar perda permanente indetectável e citar teorema oral que a exclui.
  • Aplicar n>3m a todo protocolo autenticado, assíncrono, ponderado, sem permissão ou baseado em recursos.
  • Igualar crash, omissão, equivocação, computação arbitrária, canal defeituoso e chave comprometida.
  • Presumir que participantes equivalem a entidades independentes, stake, poder computacional ou peso de comitê.
  • Omitir a diferença entre comandante leal e traidor na validade.

Algoritmo e implementação

  • Ver apenas a maioria final sem rastrear caminhos recursivos e cada visão local.
  • Usar padrões de ausência, desempates, fotografias de membros ou ordens diferentes entre implementações.
  • Aceitar mensagens sem vincular protocolo, cadeia, tarefa, altura, rodada, valor, remetente e época.
  • Repetir ou combinar mensagens entre execuções, rodadas, bifurcações, redes ou mudanças de membros.
  • Presumir que assinaturas provam verdade, atualidade, contexto de autorização, entrega, disponibilidade ou custódia honesta.
  • Citar OM(m) ou SM(m) sem implementar rodadas, retransmissão, verificação e conectividade exigidas.
  • Testar uma posição de traidor e não comandante, tenente, conluio, omissão e equivocação.

Implantação e interpretação

  • Dizer que um consenso “resolve Bizâncio” sem premissas exatas de segurança, vivacidade e rede.
  • Tratar acordo sobre bytes como prova de execução ou fato externo correto.
  • Ignorar falhas correlacionadas por clientes, operadores, nuvens, chaves ou governança comuns.
  • Creditar depósitos, emitir ativos em bridge ou liquidar ações irreversíveis antes da finalidade necessária.
  • Inferir descentralização, segurança de ativos, verdade jurídica ou valor do token de rótulo de tolerância.

Equívocos comuns

  • O problema é só um ataque de 51%. Trata comportamento arbitrário e conflitante num modelo de acordo; maioria de recursos pertence a protocolos específicos.
  • Uma maioria sempre resolve. No modelo oral clássico, tolerar m traidores exige mais de três vezes esse total de participantes, não só um leal a mais.
  • Assinaturas digitais provam que a mensagem é verdadeira. Autenticam chave e protegem integridade; chave maliciosa ou comprometida assina conteúdo falso ou conflitante.
  • O resultado oral original já cobre entrega não confiável. Inclui premissas explícitas de entrega, identidade e omissão detectável; outros modelos exigem outros resultados.
  • Acordo significa conhecer a realidade. Sem validação separada, nós leais podem concordar com saída inválida ou dado externo incorreto.

Tópicos relacionados

Fontes

Navegação

Pesquisar na wiki...