Entendendo o básico do Blockchain: o desafio dos generais bizantinos. Parte 1

A tradução do artigo foi preparada especialmente para os alunos do curso “High Load Architect” , que começa este mês.

---

O Blockchain é um sistema descentralizado, composto por várias entidades que agem dependendo de seus incentivos e das informações que possuem.

Sempre que uma nova transação é transmitida pela rede, os nós podem incluir essa transação em uma cópia do razão ou ignorá-la. Quando a maioria dos participantes da rede decide aceitar um determinado estado, é alcançado um consenso.

Um problema fundamental na computação distribuída e nos sistemas multiagentes é obter a confiabilidade geral do sistema na presença de vários processos inoperantes. Freqüentemente, isso exige que os processos coordenem entre si algum valor que será necessário durante o cálculo.

Esses processos são descritos como consenso.

• O que acontece quando um participante decide não seguir as regras e intervir no estado de sua contabilidade?
• O que acontece quando existem muitos participantes na rede, mas não a maioria?

Para um protocolo de consenso ser seguro, ele deve ser tolerante a falhas.

Para começar, falaremos brevemente sobre o problema insolúvel de dois generais. Em seguida, considere o problema dos generais bizantinos e discuta a tolerância a falhas bizantinas em sistemas distribuídos e descentralizados. E no final, vamos falar sobre como tudo isso se relaciona com a tecnologia blockchain.

A tarefa de dois generais

Essa tarefa, publicada pela primeira vez em 1975 e nomeada em 1978, descreve um cenário em que dois generais atacam um inimigo comum. O primeiro general é considerado o líder e o segundo é o seguidor. O exército de cada general sozinho não é suficiente para derrotar o exército inimigo, então eles precisam cooperar e atacar ao mesmo tempo. Este cenário parece simples, mas há uma ressalva:

Para que eles possam se comunicar e chegar a um acordo, o primeiro general deve enviar um mensageiro através do campo do inimigo, ele deve enviar uma mensagem com a hora do início do ataque ao segundo general. No entanto, é provável que o mensageiro seja capturado pelos oponentes e a mensagem não seja entregue. Isso levará ao fato de que o exército do primeiro general continuará o ataque, e o segundo permanecerá no lugar.

Mesmo que a primeira mensagem seja entregue, o segundo general deve confirmar (ACK (reconhecer), observe a semelhança com o handshake de três vias no TCP ) de que ele recebeu a mensagem, para que ele envie o messenger de volta, reproduzindo o cenário anterior em que o messenger pode ser capturado. . Isso flui para intermináveis ​​ACKs e, por causa disso, os generais não conseguem chegar a um acordo.

Não há como garantir a segunda condição, ou seja, que cada general esteja totalmente confiante de que o outro concorda com o plano de ataque. Os dois generais sempre ignoram se o mensageiro alcançou seu companheiro.



Ficou provado que a tarefa de dois generais é insolúvel.

A tarefa dos generais bizantinos

Descrita em 1982 por Lamport, Shostak e Piz, a versão desse problema acabou sendo um destaque. Ela descreve o mesmo cenário, onde, em vez de dois generais, mais generais devem concordar com a hora do ataque. Uma complicação adicional é que um ou mais generais podem ser traidores, ou seja, eles podem mentir sobre suas intenções (por exemplo, o general diz que concorda em atacar às 09:00, mas não).

O paradigma do seguidor-líder descrito na tarefa de dois generais é transformado em uma instalação subordinada-comandante. Para obter consenso aqui, o comandante e cada subordinado devem concordar com a mesma solução (ataque ou retirada).

Tradução de imagens:

A tarefa dos generais bizantinos. O comandante geral deve enviar uma ordem aos seus subordinados n-1, de modo que:

• Todos os generais leais subordinados obedecem a um comando.
• Se o comandante geral é leal, todos os seus subordinados leais obedecem às suas ordens.

Além do segundo ponto, um fato interessante deve ser destacado: se o comandante é um traidor, ainda há consenso. Como resultado, todos os tenentes têm voto majoritário.

O algoritmo de consenso nesse caso é baseado no significado da maioria das decisões que os subordinados veem.

Teorema: Para qualquer m , o algoritmo OM (m) chega a um consenso com mais de 3m generais e um máximo de m traidores.

Isso significa que o algoritmo pode chegar a um consenso enquanto 2/3 dos participantes são honestos. Se os traidores tiverem mais de 1/3, o consenso não será alcançado, os exércitos não poderão coordenar seus ataques e o inimigo vencerá.

Algoritmo OM (0)

1. O comandante envia seu valor para cada um dos subordinados.
2. Cada subordinado usa o valor que ele recebe do comandante ou usa o valor DELAY se ele não receber nenhum valor.

Algoritmo OM (m), m> 0

1. O comandante envia com sua importância a cada um dos subordinados.
2. Para cada i, seja vi o valor que o i-ésimo subordinado recebe do comandante, ou o valor RESET será usado se o subordinado não receber nenhum valor. O i-ésimo subordinado atua como um comandante no algoritmo OM (m-1) e envia um valor para cada um dos n-2 subordinados restantes.
3. Para cada i, desde que ji, seja vj o valor que o i-ésimo subordinado recebeu do j-ésimo subordinado na etapa (2) (usando o algoritmo OM (m-1)) ou use o valor DELAY se não tem nenhum significado. O i-ésimo escravo usa o valor majoritário (v1, ..., vn-1).

Quando m = 0 não há traidores, cada subordinado segue a ordem. Para m> 0, cada escolha final de um subordinado procede da parte predominante da eleição de todos os subordinados.
Será mais claro se você observar a situação do ponto de vista do segundo subordinado - seja C o comandante e L {i} seja o i-ésimo subordinado.



OM (1): O subordinado 3 é um traidor. A situação do ponto de vista do segundo subordinado.

Passos:

1. O comandante envia v a todos os subordinados.
2. L1 envia L2 o valor de v ou L3 envia L2 o valor de x.
3. L2 ← maioria (v, v, x) == v

A decisão final é tomada pela maioria dos votos de L1, L2 e L3 e, como resultado, é alcançado um consenso.

É importante lembrar que o objetivo é que a maioria dos subordinados escolha a mesma solução, em vez de uma solução específica.

Vejamos o caso em que o comandante é um traidor.



OM (1): O comandante é um traidor.

Passos:

1. O comandante envia a L1, L2, L3 os valores de x, y, z, respectivamente;
2. L1 envia o valor de x para os escravos L2, L3 | L2 envia L1, L3 o valor de y | L3 envia L1, L2 o valor de z;
3. L1 ← maioria (x, y, z) | L2 ← mais (x, y, z) | L3 ← maioria (x, y, z)

Todos eles têm o mesmo valor, portanto é alcançado um consenso. Observe que, mesmo que os valores de x, y, z sejam todos diferentes, o valor majoritário (x, y, z) é o mesmo para todos os três subordinados. Se x, y, z são ordens completamente diferentes, podemos assumir que eles agirão de acordo com o plano padrão - RESET.

Para analisar uma abordagem prática de um exemplo mais complexo com 7 generais e 3 traidores, sugiro que você leia este artigo .

Tolerância a falhas bizantinas

A tolerância a falhas bizantinas é uma característica que define um sistema que permite uma classe de falha que pertence à tarefa de generais bizantinos. A falha bizantina é a classe mais complexa de tipos de falha . Ele não implica nenhuma restrição e não faz suposições sobre qual comportamento o nó pode ter (por exemplo, o nó pode gerar dados arbitrários, se apresentando como um participante honesto).

Erros bizantinos são os mais difíceis de corrigir. A tolerância a falhas bizantinas era necessária em sistemas de motores de aeronaves, em usinas nucleares e em praticamente qualquer sistema cujas ações dependem dos resultados de um grande número de sensores. Até a SpaceX vê isso como um requisito potencial para seus sistemas.

O algoritmo mencionado na seção anterior corresponde à tolerância a falhas bizantinas até que o número de traidores exceda um terço de todos os generais. Existem outras opções para facilitar essa tarefa, incluindo o uso de assinaturas digitais ou a introdução de restrições à comunicação entre pares.

Como tudo isso se relaciona com o blockchain?

Blockchain são livros descentralizados que, por definição, não são controlados pela autoridade central. Devido aos valores armazenados neles, os atacantes têm um bom incentivo econômico para tentar iniciar um erro. No entanto, a tolerância a falhas bizantinas e, portanto, a solução do problema geral bizantino para o blockchain são simplesmente necessárias.

Na ausência de tolerância a falhas bizantinas, um par pode transmitir e publicar transações falsas, anulando completamente a confiabilidade do blockchain. Para piorar a situação, não existe uma autoridade central que possa assumir a responsabilidade e reparar os danos.

Quando o Bitcoin foi inventado, um grande avanço foi o uso de evidências da solução probabilística do problema dos Generais Bizantinos. Foi descrito em detalhes por Satoshi Nakamoto neste e - mail .

Conclusão

Neste artigo, examinamos alguns conceitos básicos de consenso em sistemas distribuídos.