14

Considerações iniciais

Estou realizando uma pesquisa sobre Bitcoin e esbarrei no conceito do Problema dos Generais Bizantinos, onde o criador do Bitcoin - Satoshi Nakamoto - escreveu "Bitcoin: A Peer-to-Peer Electronic Cash System". Nesse artigo, ele descreve como tornou possível a existência de uma moeda digital sem depender de uma autoridade central.

Minhas perguntas

  1. Qual é o Problema dos Generais Bizantinos?
  2. Como posso implementar uma solução, preferencialmente em java, para o Problema dos Generais Bizantinos?

Referência:

[Satoshi Nakamoto], Bitcoin: A Peer-to-Peer Electronic Cash System. Disponível em: < https://bitcoin.org/bitcoin.pdf >. Acesso em: 03 Jan. 2018.

6
  • Creio que "implementar o problema" tenha sido um erro de digitação. Um programa é uma solução ao problema. O problema em si ele existe, simplesmente, sem precisar de implementação nem solução. Por exemplo, existe o problema da parada HALT mas não há implementação para ele. Também existe o problema co-NP da primalidade (n é primo?), que você não codifica o problema, mas sua solução Commented 5/01/2018 às 12:19
  • 1
    Aproveitando: esse problema foi descrito formalmente em 1982 por Leslie Lampourt (o "La" em "LaTeX") em um artigo submetido à ACM Commented 5/01/2018 às 12:24
  • 1
    @JeffersonQuesado, realmente pode induzir ao erro! Já editei. Quanto ao problema é bem documentado. Mas não encontrei uma resposta aqui no SOPt. Commented 5/01/2018 às 17:25
  • A pergunta do item 2 é ampla demais. Commented 7/01/2018 às 2:24
  • @VictorStafusa, acredito que não seja. Porque se trata de implementar uma solução de um problema. Exercício comum de construção de Projetos de algoritmos. Mostrar as aplicações dos algoritmos para resolução de diferentes problemas; O que se aplica com o propósito da pergunta. Não é questão de certo ou errado. Mas demostrar uma solução de forma prática. O que pode implicar em um solução de processamento distribuído devido o contexto do problema! Commented 7/01/2018 às 2:40

2 Respostas 2

19
+50

O problema

Como o companheiro prmottajr disse na resposta dele, o problema dos generais bizantinos é permitir que seja tomada uma decisão distribuída (atacar/recuar ou então atacar/aguardar) frente a possibilidade de alguns deles serem traidores e frente a possibilidade de mensagens entre eles se perderem. O tempo para a decisão ser tomada é finito.

É importante que todos os generais não-traidores cheguem a um consenso. Se metade deles decidir atacar e metade decidir recuar, os exércitos que atacarem serão massacrados e os que recuaram não serão numerosos o suficiente para levar a guerra adiante. E esse é o objetivo dos traidores.

Os traidores não apenas votam contra a decisão do grupo, mas o fazem de forma seletiva. Podem ora mandar mensagens verdadeiras, e ora mandar mensagens falsas, e podem escolher quando e para quem mandarão quais mensagens. Os traidores também podem ou não operar em conluio para tentar frustrar o objetivo dos generais leais. Por outro lado, os generais leais sempre obedecem o que eles acreditam ser a decisão da maioria.

Restrições do problema

Há algumas soluções possíveis, dependendo das restrições adotadas. Entretanto, em todas as soluções, todos os generais leais devem ter um mesmo processo/algoritmo e segui-lo de forma rigorosa.

Os generais leais então devem dar o seu voto e comunicá-lo a todos os demais generais. Após um general receber o voto dos demais generais, ele conhece a decisão do grupo. Se a maioria dos generais leais votarem por atacar, então o pequeno número de traidores não será o suficiente para mudar o consenso. Se os generais leais se dividirem mais ou menos meio-a-meio, então provavelmente é porque ambas as alternativas devem ser igualmente boas ou igualmente ruins, e o voto dos traidores apenas trocará seis por meia-dúzia.

Na verdade, isso corresponde a uma classe de problemas vez que há diversas restrições que podem ou não se aplicar dependendo do caso concreto:

  • As mensagens entre os generais podem ser perdidas?

  • As mensagens entre os generais podem ser alteradas no caminho?

  • Quais generais podem se comunicar com quais outros generais?

  • Os remetentes das mensagens podem ser forjados?

  • Há um comandante dentre os generais?

  • Quantos e quais são os traidores?

  • A comunicação entre os generais é síncrona ou assíncrona?

  • O número de generais é fixo?

  • Há limitações quanto ao número de mensagens?

  • Mensagens perdidas ou não enviadas podem ser detectadas?

  • O que fazer quando uma mensagem se perde?

Há casos em que não existe solução. Por exemplo:

  • Se todos os generais forem traidores, não há muito o que fazer e a guerra estará perdida.

  • Se os traidores forem capaz de forjar, interceptar, alterar e/ou destruir quaisquer mensagens a qualquer tempo, mesmo se enviadas entre dois generais leais, então eles efetivamente controlam toda e qualquer comunicação e podem induzir os generais leais a fazer o que eles quiserem.

Também há casos onde a solução é simples e fácil, por exemplo:

  • Se as mensagens entre os generais não podem ser forjadas, interceptadas ou destruídas e há um comandante que é sabidamente leal, então basta o comandante mandar uma mensagem a cada general e os generais leais obedecerão a essa mensagem.

  • Se os traidores puderem ser facilmente identificados, ou alternativamente os generais leais puderem facilmente comprovar a sua lealdade, então basta identificar os traidores e excluí-los.

Mas, há cenários onde a solução é algo bem complicado.

Cenário 1

O primeiro cenário considera que:

  • As mensagens enviadas entre dois generais leais nunca se perdem e nem podem ser interceptadas. Ou seja, todos os mensageiros são confiáveis.

  • O remetente de uma mensagem vinda de um general leal não pode ser forjado/falsificado.

  • A ausência de uma mensagem é detectável (ex: timeout).

  • Todos os generais podem se comunicar com todos os outros generais diretamente.

  • Um dos generais é o comandante, é ele que toma a decisão.

  • O número de generais traidores é menor, mas não igual, a um terço do total de generais.

  • Se o comandante for traidor, ainda assim todos os demais generais chegam a um consenso.

O algoritmo nesse caso é o seguinte:

  • Todos os generais leais devem mandar mensagens para todos os outros, retransmitindo a decisão do comandante.

  • Define-se uma estratégia padrão para o caso de nenhuma mensagem ser recebida dentro de um espaço de tempo razoável (por exemplo: recuar).

  • Todas as mensagens enviadas de um general para o outro devem ter a identificação do remetente.

  • As mensagens recebidas contém a lista ordenada dos generais pelos quais elas passaram antes de chegar ao destinatário. O destinatário a enviará para todos os outros generais que não estejam nessa lista, colocando a si mesmo no final dessa lista de generais por onde a mensagem passou.

  • Cada general segue a decisão do comandante. Em caso de mensagens recebidas com informações conflitantes acerca do que é a decisão do comandante, segue-se aquela que é expressa no maior número de mensagens recebidas.

  • Mensagens de um mesmo remetente recebidas em excesso devem ser ignoradas.

Nesse cenário, vez que o remetente não pode ser forjado, não há como os traidores mandar mensagens se passando por outros generais leais para tentar enganá-los (um traidor pode se passar por outro traidor, mas isso é de pouca serventia para eles).

Também não há meio de uma mensagem enviada por um general leal ser corrompida no caminho a seu destinatário. Também não é muito interessante a um traidor deixar de mandar uma mensagem a algum general leal porque isso iria revelar a esse general leal a sua condição de traidor.

Observe que os traidores podem mentir e fornecer mensagens com listas de generais falsas, fora de ordem e/ou com decisões incorretas.

Nesse caso, as mensagens entre os generais leais efetivamente dizem o seguinte:

De: Comandante
Para: General 1
Eu decidi X.

De: General 1
Para: General 2
O comandante decidiu X.

De: General 2
Para: General 3
Segundo o general 1, o comandante decidiu X.

De: General 3
Para: General 4
Segundo o general 2, o general 1 disse que o comandante decidiu X.

De: General 4
Para: General 5
Segundo o general 3, o general 2 disse que o general 1 disse que o comandante decidiu X.

Isso significa que sendo n o número de generais e m o número máximo de traidores (m = n-1/3, arredondado para baixo), o comandante enviará n-1 mensagens na primeira rodada. Na segunda rodada, cada um dos demais n-1 generais enviará n-2 mensagens aos demais generais. Na terceira rodada, cada general enviará n-3 mensagens aos demais generais (excetuando-se aqueles que já tem o nome na lista de generais da mensagem). Na quarta rodada, cada um enviará n-4 mensagens. E assim sucessivamente, completando n-m-1 rodadas.

Após terem sido coletadas todas as mensagens, cada general observa o que cada outro general enviou e decide qual é a opinião de cada general a respeito do consenso para então entender qual é o consenso.

A prova de que esse algoritmo funciona é bastante complicada. No entanto, ele não é muito aplicável na prática, pois necessita de um número muito grande de mensagens para dar certo e necessita que todos os generais possam se comunicar com todos. Esse não é algo realista quando você tem uma implementação onde há milhões de generais por exemplo. Outro problema é que se o comandante for um traidor, embora os demais generais cheguem a um consenso, isso será de pouca valia vez que qualquer decisão tomada será determinada pelo traidor.

Cenário 2

O principal problema do cenário 1 é que os traidores podem mentir. Isso pode ser resolvido se:

  • As mensagens dos generais leais são assinadas.

  • Não é possível forjar-se assinaturas falsas.

  • Mensagens com assinaturas que não possam ser verificadas ou sem assinatura são descartadas pelos generais leais.

Na prática, essas restrições são facilmente modeladas por um esquema de assinatura digital. Veja mais nessa resposta.

Com esse esquema de assinatura. É possível criar-se mensagens assim:

De: General 4
Para: General 5
Atesto que o que se segue é verdadeiro.

De: General 3
Para: General 4
Atesto que o que se segue é verdadeiro.

De: General 2
Para: General 3
Atesto que o que se segue é verdadeiro.

De: General 1
Para: General 2
Atesto que o que se segue é verdadeiro.

De: Comandante
Para: General 1
Decidi X.

[Assinatura do Comandante]

[Assinatura do General 1]

[Assinatura do General 2]

[Assinatura do General 3]

[Assinatura do General 4]

Nesse esquema, as mensagens são colocadas umas dentro das outras, demonstrando a sequência de generais por onde ela passou e vão acumulando assinaturas. O general 5, quando receber isso, poderá atestar a autenticidade de todas as assinaturas.

Se, por exemplo, o general 3 for um traidor e ele tentar forjar uma mensagem falsa, as assinaturas do comandante, do general 1 e do general 2 não vão ser validadas e ao fazer isso ele rapidamente seria desmascarado.

Se o comandante for um traidor e enviar "Decidi X." para o general 1 e "Decidi Y." para o general 2, quando o general 1 e o general 2 trocarem mensagens, eles perceberão a inconsistência, e vez que as assinaturas não podem ser forjadas, eles vão deduzir que o comandante deu ordens diferentes para diferentes generais e portanto seria um traidor.

Esse esquema, permite ainda reduzir o número de mensagens e elimina a necessidade de todos os generais terem que falar com todos os outros generais, bastando que todos os generais leais consigam se comunicar uns com os outros por caminhos onde as mensagens não passem por nenhum traidor (mas como desconhece-se quem são os traidores, estes também receberão e enviarão mensagens). Ainda assim, isso é algo bem complicado de gerenciar corretamente.

Aplicação do problema

Muitos algoritmos para casos de generais bizantinos necessitam que o número de traidores não chegue a um terço do número total de generais. Existem circunstâncias para as quais basta que o número de traidores não chegue a metade do número de generais.

O problema dos generais bizantinos é na verdade uma família de problemas correlatos e similares, mas que podem ter soluções muito diferentes entre si a depender das condições dos problemas.

No bitcoin, por exemplo, os generais representam os nós que podem fazer transações e cada um deles mantém uma blockchain. O bitcoin usa assinaturas digitais para garantir que mensagens não possam ser forjadas. Em cada transação, o comandante é aquele que a inicia, ou seja, uma pessoa que está a enviar alguma quantia de bitcoins para alguma outra pessoa. A blockchain é um gigantesco livro contábil que armazena o conjunto de transações de todos, e como cada um tem uma cópia, a ideia é que quando uma transação é anunciada, todos as registrem em seus livros contábeis. Os generais leais são aqueles que registram as transações de forma honesta em suas blockchains e enviam mensagens aos demais generais para que eles também o façam.

No caso do bitcoin, os traidores seriam aqueles que tentam forjar transações inexistentes, gastar dinheiro que não têm, criar dinheiro a partir do nada ou manter livros contábeis distintos dos demais. Se houver um suficiente número de traidores agindo em conluio no bitcoin, eles podem impôr aos usuários honestos uma blockchain fraudulenta. Uma das premissas da segurança do bitcoin é que o número de traidores seja suficientemente pequeno.

Várias outras situações são análogas aos problemas dos generais bizantinos:

  • Redes de drones controladas por inteligência artificial.

  • Compartilhamento de arquivos P2P.

  • Sistemas de defesa aérea anti-mísseis.

Na prática, os generais leais representam aqueles usuários e softwares legítimos que visam trabalhar como o esperado de forma honesta para o benefício de todos. Os traidores são aqueles que têm interesses escusos, tais como hackers tentando burlar ou abusar do sistema, softwares falsos ou que foram hackeados, usuários querendo trollar, zoar e atrapalhar. Os traidores podem também ser equipamentos que têm peças defeituosas e não funcionam corretamente ou softwares que têm bugs que estão causando problemas.

Como há muitos cenários nos quais isso pode ser aplicado, e o algoritmo a ser aplicado varia bastante de acordo com as restrições do problema, não dá para se criar uma implementação genérica sem maiores detalhes. Entretanto, mesmo assim alguns existem, inclusive em Java:

Não conheço os pormenores de nenhum deles e de certo devem haver outros projetos para isso por aí. Mas com essa lista, já deve dar para começar.

11

A ideia é conseguir chegar a um consenso sobre alguma ação que deve ser tomada em um ambiente distribuído.

O problema foi ilustrado da seguinte maneira, um grupo de generais precisa chegar a um consenso se vão atacar ou recuar e só podem se comunicar através de mensageiros (sendo que estes podem nunca chegar ou serem capturados). Além disso, alguns dos generais podem ser traidores e mandarem mensagens falsas para atrapalhar a decisão.

Isso nos leva ao seguinte cenário:

  • um grupo de processos (generais) precisa chegar a uma decisão postando mensagens.
  • alguns processos podem estar com falhas (traidores).
  • as mensagens podem ser perdidas (mensageiros capturados por inimigos).
  • a decisão precisa ser tomada em um tempo finito.

Em sistemas assíncronos com possibilidade de falha não há como chegar a uma solução a menos que a falha possa ser identificada (saber que uma máquina caiu por exemplo, o que muitas vezes é difícil porque o ping pode estar desabilitado)

Esse cenário é mais "fácil" no caso dos sensores de um avião em que o sistema pode considerar um sensor como falho caso ele não responda em um tempo limite, mas de qualquer forma um avião poderia ser visto como um sistema síncrono.

Um grupo de slides muito bom pode ser encontrado aqui (incluindo os algoritmos):http://www-di.inf.puc-rio.br/~endler/courses/DA/transp/Consensus.pdf

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .