Problema dos Generais Bizantinos

Como o Bitcoin resolve o problema de computadores desonestos em uma rede aberta

O Problema dos Generais Bizantinos (PGB) é um problema fundamental de sistemas distribuídos: como um grupo de participantes, que não confiam uns nos outros e podem incluir traidores, consegue chegar a um acordo sobre uma decisão comum? O Bitcoin oferece uma solução elegantemente prática usando Proof of Work como mecanismo de consenso.

Esta página apresenta o problema clássico, sua relevância para blockchains, e como a abordagem de Satoshi Nakamoto difere das soluções anteriores de tolerância a falhas bizantinas.

Conteúdo

O Problema

Generais desonestos e mensagens não confiáveis

A formulação clássica, proposta por Leslie Lamport, Robert Shostak e Marshall Pease em 1982, descreve o seguinte cenário:

Vários generais do exército bizantino acamparam ao redor de uma cidade inimiga. Eles precisam decidir, por consenso, se atacam ou recuam. Se todos atacarem, vencem. Se todos recuarem, preservam o exército. Mas se alguns atacam e outros recuam, o desastre é certo.

Os generais só podem se comunicar por mensageiros (cartas). Além disso, alguns generais podem ser traidores, enviando mensagens deliberadamente enganosas para sabotar o consenso. O problema é: existe um protocolo que garanta que todos os generais leais cheguem ao mesmo acordo, independentemente do que os traidores façam?

Para que o consenso seja válido, duas condições devem ser satisfeitas:

O resultado de impossibilidade

3 generais, 1 traidor: não há solução

Lamport demonstrou que, com apenas mensagens orais (sem assinaturas criptográficas), não existe protocolo que resolva o problema com 3 generais e 1 traidor. O traidor pode fazer com que os generais leais nunca cheguem a um acordo — um deles acredita que a decisão é "atacar" enquanto o outro acredita que é "recuar".

Com assinaturas criptográficas (mensagens seladas que não podem ser falsificadas), o problema se torna tratável para qualquer número de traidores t, desde que haja pelo menos 2t + 1 generais no total. Mas mesmo essa solução tem limitações práticas em redes abertas e anônimas.

O Algoritmo OM(m)

A solução de Lamport para mensagens orais

Lamport propôs o algoritmo OM(m) (Oral Messages) para resolver o problema quando há m traidores e n ≥ 3m + 1 generais no total. O algoritmo funciona em rodadas:

Ao final, cada tenente coleta todas as ordens que recebeu (diretamente e por retransmissão) e decide pela maioria dos valores. O algoritmo garante que, se n ≥ 3m + 1, todos os tenentes leais chegarão ao mesmo consenso.

O código a seguir implementa uma simulação completa do OM(m) em Ruby, testando três cenários distintos:

# Simulacao completa do algoritmo Byzantine Oral Messages OM(m)
# n = numero total de generais
# t = numero de traidores (n >= 3t + 1)
# comando = "ATACAR" ou "RECUAR"

class General
  attr_reader :id, :leal
  attr_accessor :ordens_recebidas

  def initialize(id, leal: true)
    @id = id
    @leal = leal
    @ordens_recebidas = []
  end

  def traidor?; !@leal end

  def decidir
    return "TRAIDOR (mente)" if traidor?
    return "SEM ORDEM" if @ordens_recebidas.empty?

    atacar = @ordens_recebidas.count("ATACAR")
    recuar = @ordens_recebidas.count("RECUAR")

    if atacar > recuar
      "ATACAR"
    elsif recuar > atacar
      "RECUAR"
    else
      "EMPATE (#{atacar}x cada)"
    end
  end
end

def simular_om(n, traidores, comandante_leal: true, ordem: "ATACAR")
  generais = (1..n).map { |i| General.new(i) }
  traidores.each { |i| generais[i-1].instance_variable_set(:@leal, false) }

  # OM(0): comandante envia ordem a todos
  comandante = generais[0]
  unless comandante.leal
    # Comandante traidor: pode enviar ordens diferentes
    generais[1..].each_with_index do |g, i|
      g.ordens_recebidas << (i.even? ? "ATACAR" : "RECUAR")
    end
  else
    generais[1..].each { |g| g.ordens_recebidas << ordem }
  end

  # OM(1): cada general retransmite o que ouviu
  generais[1..].each do |general|
    next if general.traidor?
    ordem_recebida = general.ordens_recebidas.first
    generais[1..].each do |outro|
      next if outro == general
      outro.ordens_recebidas << ordem_recebida
    end
  end

  gerar_relatorio(generais, comandante, ordem)
end

def gerar_relatorio(generais, comandante, ordem_original)
  saida = []
  saida << "Generais: #{generais.size}, " +
    "Traidores: #{generais.count(&:traidor?)}"
  saida << "Comandante: ##{comandante.id} " +
    "(#{comandante.leal ? "LEAL, ordem: #{ordem_original}" : "TRAIDOR"})"
  saida << ""

  generais[1..].each do |g|
    lealdade = g.leal ? "LEAL" : "TRAIDOR"
    dec = g.decidir
    seta = (g.leal && dec == ordem_original) ? "OK" :
           (g.leal ? "FALHA" : "—")
    saida << "  General ##{g.id} [#{lealdade}] " +
      "ordens=#{g.ordens_recebidas.inspect} " +
      "decide=#{dec} #{seta}"
  end

  saida.join("\n")
end

# Caso 1: n=4, t=1, comandante leal → consenso correto
puts "=== CASO 1: n=4, 1 traidor (General 4) ==="
puts simular_om(4, [4])
puts ""

# Caso 2: n=4, t=1, comandante traidor → consenso entre leais
puts "=== CASO 2: n=4, comandante traidor ==="
puts simular_om(4, [1], comandante_leal: false)
puts ""

# Caso 3: n=3, t=1 → IMPOSSIVEL (consenso falha)
puts "=== CASO 3: n=3, 1 traidor ==="
puts simular_om(3, [3])

Os resultados da simulação mostram três comportamentos distintos:

Caso 1 (n=4, 1 traidor, comandante leal): todos os generais leais decidem por "ATACAR". O traidor (General 4) pode mentir o quanto quiser nas retransmissões, mas a votação por maioria entre 3 ordens recebidas (duas "ATACAR" verdadeiras + uma "RECUAR" mentirosa) ainda produz "ATACAR" por maioria de 2×1. O consenso é correto.

Caso 2 (n=4, comandante é o traidor): o comandante envia "ATACAR" para uns e "RECUAR" para outros. Os tenentes leais trocam mensagens entre si e cada um vê uma divisão 2×2. O resultado é empate — mas todos os leais chegam ao mesmo empate. O consenso é alcançado (todos sabem que o comandante é desonesto), mesmo que a decisão seja "EMPATE".

Caso 3 (n=3, 1 traidor): o cenário clássico de impossibilidade. Com apenas 3 generais e 1 traidor, a condição n ≥ 3m + 1 é violada (3 < 4). O general leal que recebe uma ordem do comandante e outra (diferente) do traidor não tem como saber qual é a verdadeira. O consenso entre leais falha — exatamente como Lamport provou.

Para resolver o caso de 3 generais, são necessárias assinaturas criptográficas (mensagens seladas que não podem ser falsificadas). Com assinaturas, o algoritmo SM(m) (Signed Messages) consegue tolerar qualquer número de traidores, desde que haja pelo menos 2m + 1 generais. Mas mesmo essa solução exige que as identidades e chaves públicas sejam conhecidas de antemão — algo que o Bitcoin não pode assumir.

A impossibilidade com 3 generais e 1 traidor é análoga a um cenário que qualquer operador de nó Bitcoin reconhece: como você sabe que a versão da blockchain que seu nó lhe mostra é a mesma que todos os outros nós veem, se você não pode confiar em todos os pares da rede? A resposta do Bitcoin: você não precisa saber. Você só precisa da cadeia com mais trabalho acumulado.

Soluções Clássicas

BFT antes do Bitcoin

Antes do Bitcoin, as soluções para o Problema dos Generais Bizantinos (BFT) existiam, mas funcionavam em ambientes controlados:

Todas essas abordagens compartilham uma limitação fundamental: identidades conhecidas e controladas. Em uma rede aberta como o Bitcoin, onde qualquer um pode entrar e sair anonimamente, essas soluções falham.

A Solução do Bitcoin

Proof of Work como mecanismo de consenso bizantino

A inovação de Satoshi Nakamoto foi reformular o problema: em vez de tentar fazer todos os participantes concordarem, o Bitcoin exige apenas que a cadeia com mais trabalho acumulado seja aceita como a versão verdadeira dos eventos. Isso transforma o problema de consenso em um problema econômico.

No modelo do Bitcoin, cada "general" é um minerador. A "decisão" é qual bloco (e, portanto, qual conjunto de transações) deve ser o próximo na blockchain. O "voto" de cada general é seu poder computacional. A cadeia mais longa é a decisão final.

A citação de Satoshi (whitepaper, seção 3): "Nós provamos que o esquema é seguro enquanto nós honestos controlam coletivamente mais poder de CPU que qualquer grupo cooperante de nós atacantes." \u2014 Em termos de generais bizantinos: o exército leal precisa ter mais poder computacional que o exército traidor.

Proof of Work como voto

"Um voto por hash, um CPU"

A chave da solução de Satoshi é o Proof of Work (PoW). Cada bloco requer trabalho computacional para ser produzido (encontrar um hash abaixo do alvo). Esse trabalho é caro de produzir, mas barato de verificar.

Para um traidor (general desonesto) impor uma cadeia alternativa, ele precisaria produzir mais trabalho acumulado que todos os generais honestos juntos. Isso equivale a controlar mais de 50% do poder de hash total da rede — algo economicamente proibitivo.

A analogia com os generais bizantinos:

A grande sacada: no modelo de Satoshi, não é necessário que todos concordem ao mesmo tempo. Generais que estão offline (nós desconectados) podem pegar a decisão quando voltarem — basta baixar a cadeia com mais trabalho acumulado. O consenso é assíncrono e eventual.

Proteção contra ataques Sybil

Por que não basta criar mil identidades falsas

Em uma rede sem Proof of Work, um atacante poderia criar milhares de identidades falsas (nós da rede) para simular consenso — isso é um ataque Sybil. Sem uma forma de distinguir identidades legítimas de falsas, o consenso é impossível.

O Proof of Work resolve o ataque Sybil porque o "voto" não é por identidade, mas por trabalho computacional. Criar 10.000 identidades falsas não aumenta em nada seu poder de hash — você ainda precisa gastar energia elétrica e hardware para minerar blocos. O custo de cada voto é real e verificável.

Esta é a razão pela qual blockchains de prova-de-trabalho são chamadas de "permissionless" (sem permissão): qualquer um pode participar sem autorização, porque o próprio trabalho computacional é a credencial de participação.

BFT Clássico vs Bitcoin

Duas abordagens para o mesmo problema fundamental

A principal diferença está no modelo de ameaça:

O custo do PoW (eletricidade, hardware) é o preço pago pela abertura e descentralização. Blockchains permissionadas (como muitas corporativas) usam BFT clássico exatamente para evitar esse custo — mas abrem mão da participação aberta.

Limitações

O que a solução do Bitcoin não resolve

A abordagem de Satoshi para o Problema dos Generais Bizantinos não é uma bala de prata:

Apesar dessas limitações, a solução do Bitcoin para o Problema dos Generais Bizantinos é uma das contribuições mais importantes da ciência da computação do século XXI: pela primeira vez, um sistema aberto e sem confiança permite que estranhos cheguem a um acordo global sobre a ordem dos eventos, sem uma autoridade central.

Recursos