O Problema dos Generais e Consenso Distribuído
[Transcrição do vídeo abaixo]
Pessoal, aqui é Daniel Scocco do canal criptos.com.br e hoje eu vou falar sobre dois problemas: o primeiro chamado o problema dos dois Generais e o segundo dos Generais Bizantinos, que é uma generalização do primeiro problema que a gente vai discutir. Eles ilustram o desafio que é você chegar a um consenso em uma rede ou um sistema com pontos dispersos, como é o caso de uma criptomoeda como o Bitcoin. Você tem os nós dispersos, trabalhando independentemente uns dos outros e eles precisam chegar a um consenso, por exemplo, da ordem das transações ou quais transações são válidas ou não.
Então vamos lá: o primeiro problema é o chamado dos dois Generais. O problema é o seguinte você tem o General 1 e o General 2, que são da mesma tropa e eles estão querendo conquistar, invadir o castelo C. O problema em questão é que se eles atacarem não simultaneamente, eles não vão ter sucesso. O Castelo é forte, então se o Castelo tiver que lidar com as tropas de um General sozinho, ele vai devastar essas tropas, enquanto que, se eles conseguirem atacar exatamente no mesmo momento, cada um do seu lado, aí sim eles conseguem conquistar o castelo.
Como eles fazem, porém, para sincronizar esse ataque? Obviamente tem que existir alguma forma de comunicação e o problema parte da premissa que a comunicação vai ser através de mensageiros. Então o General 1 tem que enviar o mensageiro com alguma mensagem para o General 2, e o General 2 responde, com o problema que nesse meio de campo, obviamente existem tropas inimigas, espiões e etc, que podem capturar esse mensageiro.
Curiosamente não existe solução para esse problema. Isso já foi provado. Nem é tão difícil assim de se provar. Porque o único jeito para sincronizar com 100 % de certeza seria o General 1 de fato mandar uma mensagem para o General 2 falando: “Vamos atacar tal hora” e o General 2 mandar uma confirmação: “Ok, recebi e iremos então atacar nesse horário como combinado”.
O problema é assim: a hora que o General 1 mandar essa mensagem, ele vai ficar esperando a resposta. Enquanto ele não receber resposta, ele não sabe se está confirmado ou não o ataque. Na hora que o General 2 mandar a confirmação, por sua vez ele vai ficar também esperando a confirmação da confirmação, porque ele não sabe se esta confirmação dele chegou no General 1 ou se ela foi interceptada e não chegou. Caso ela tenha sido interceptada e o General 2 atacar no horário que tinha sido combinado, pode ser que o General 1 não ataque, porque ele não recebeu confirmação nenhuma, e aí o General 2 vai acabar levando suas tropas à morte. E mesmo se o General 1 receber a confirmação e enviar confirmação, aí por sua vez agora ele vai ficar esperando a confirmação da confirmação da confirmação e assim sucessivamente, até o infinito. Então, esse problema aqui, com 100% de segurança, não tem como eles realizarem essa comunicação aí e terem 100% de certeza que vão os dois atacarem ao mesmo tempo.
Visto que não existe uma solução com 100% de segurança, que o ataque vai ser realizado no mesmo tempo, o jeito na prática, a gente tem que usar alguma estratégia, algum protocolo que maximize a probabilidade de sucesso. Por exemplo, eles poderiam combinar que às 10 horas o General 1 iria enviar uma mensagem com o horário de ataque para o General 2. Daí esse acordo desse horário já seria feito, a priori, antes deles se posicionarem e, caso o General 2 de fato receba essa mensagem, ele não faz nada e aí eles vão atacar no horário combinado. Por outro lado, se ele não receber essa mensagem, ou seja, se ela for interceptada, o protocolo já pré acordado diz que o General 2 tem que fazer, por exemplo, 10 tentativas. Deve enviar até 10 mensageiros sucessivamente para o General 1 para avisar que ele não recebeu a mensagem, então eles tem que reiniciar o protocolo para restabelecer o horário. Então o General 1 envia a mensagem e espera.
Vamos supor que demore, sei lá, um minuto, simplificando um minuto para fazer a travessia. Ele vai esperar 10 minutos. Se, em 10 minutos não chegar nenhum mensageiro, das duas uma: ou com grande probabilidade o General 2 recebeu a primeira mensagem, então eles podem realizar o ataque no horário combinado, ou com pouca possibilidade, com pouca probabilidade, os 10 mensageiros que o General 2 enviou, todos foram capturados. Mas daí, se aconteceu isso, não tem o que fazer. Eles têm que arriscar e realizar o ataque no horário combinado e seja o que Deus quiser.
O segundo problema dos chamados Generais Bizantinos nada mais é do que uma generalização do primeiro. Agora a gente tem N Generais então não são mais 2. Geralmente o problema apresenta um Comandante que vai passar as ordens para os outros Generais e eles precisam chegar a um consenso de qual ação tomar. E a gente pode simplificar dizendo que eles têm basicamente duas ações: a ação de atacar e a ação de bater em retirada. E eles precisam tomar essa decisão ao mesmo tempo, e de modo coordenado. Então a primeira complicação de generalização é que agora tem N Generais e a segunda é que um General, ele pode ser traidor e passar para frente uma ordem errada. Por exemplo, o Comandante pode passar aqui uma ordem de atacar para o General G3 e ele poderia passar para frente, para o General 2, a ordem de retirada. Então como você resolve esse problema de chegar num consenso, né? E é provado que se as mensagens que foram trocadas forem mensagens orais, por exemplo, este Comandante aqui vai mandar um mensageiro para o General 3, e esse mensageiro verbalmente vai estar falando qual é a ordem. Basta que um terço dos Generais sejam traidores e você já consegue fazer o sistema fracassar. Então vamos supor que a gente estivesse falando de um sistema com três, um Comandante e 2 Generais, 3 elementos bastaria que este aqui fosse um traidor e eles não iriam conseguir chegar num consenso, ter 100% de segurança no qual seria a ordem a ser executada.
