O que significa tolerância a falhas bizantinas?

Sean Blocked Unblock Seguir Seguindo 9 de outubro

Eu tenho tentado entender o que significa Tolerância a Falhas Bizantinas há quase um ano e lentamente descascar as camadas da cebola para entender melhor, mas provavelmente ainda estou a apenas um quarto do caminho. Neste artigo vou tentar explicar o BFT de uma maneira diferente.

Do dicionário

Um dos principais desafios para mim na compreensão do BFT é entender a palavra em si. O que realmente significa Bizantino? O dicionário Oxford define como:

  • Em relação a Bizâncio (agora a Istambul), o Império Bizantino ou a Igreja Ortodoxa Oriental
  • (de um sistema ou situação) Excessivamente complicado
  • Caracterizado por desonestidade ou procedimento inadequado .

Diretamente do bastão, essas definições não facilitam a compreensão do BFT. Vamos para a Wikipedia

Wikipedia

O padrão para qualquer explicação BFT é um time de caras (um general + seu (nos dias em que eram todos homens) exército) querendo atacar um castelo com um punhado de outras equipes e a regra é que eles precisam atacar tudo de uma vez ou não atacar de todo. Qualquer tentativa meio cozida resultará em um fracasso catastrófico e com todos recuando com suas caudas entre as pernas, remontando à antiga Mesopotâmia, no início da antiguidade.

Eu já li isso um milhão de vezes, assisti mais de um milhão de explicações no YouTube, então aqui vai minha tentativa.

Conceitos chave

O conceito-chave é tentar concordar com algo dentro de um grupo de pessoas ou máquinas. Em termos mais técnicos, está tentando chegar a um consenso dentro de uma rede distribuída.

Vamos imaginar um grupo de nós querendo assistir a um filme. Como podemos concordar em qual filme assistir? Em outras palavras, como chegamos ao consenso? Primeiro de tudo, todos nós podemos alternar na sugestão de um filme, podemos desenhar canudos, jogar Jan-Ken-Pon , ter uma corrida, votar ou todo tipo de outras coisas.

No entanto, nesta situação, a restrição é que estamos localizados em diferentes países e só podemos comunicar através de pombos-correio. Isso é para refletir uma rede de computadores em todo o mundo que se comunica via mensagens de rede.

Temos então que imaginar que há algumas pessoas neste grupo que são problemáticas e querem impedir que o consenso seja alcançado. Eles podem mentir, trapacear, conspirar ou até mesmo cometer um erro honesto ao interpretar mal alguma coisa (os Homens são de Marte e as Mulheres são de Vênus). No jargão técnico, chamaríamos essas pessoas ou falhas de computadores na rede.

O objetivo é que o grupo ainda chegue a um acordo, mesmo com um pequeno número de maus atores, então como vamos conseguir isso?

Agradecimentos

Que tal concordarmos que é a vez de Alice escolher um filme esta semana? Ela escolhe Saving Private Ryan e todo mundo tem que votar. Alice diz a todos para enviar um voto de sim ou não de volta através de um pombo-correio. Mas e se a mensagem original for interceptada e substituída pela decisão oposta? E se o pombo-correio perdesse o rumo e nunca chegasse ao seu destino? E se outra pessoa do grupo fosse como Donald Trump e tentasse confundir todo mundo dizendo coisas que simplesmente não fazem sentido?

Alice pode esperar por uma confirmação, mas e se a mesma coisa acontecer? Podemos esperar por uma confirmação da confirmação, mas esta é uma regressão infinita .

Primeiro conceito

Portanto, temos que nos preocupar que alguns de nossos funcionários ou 'computadores' sejam bizantinos, o que significa que eles são desonestos ou usam táticas ilícitas . Este, em essência, é o problema dos generais bizantinos. Como chegar a um consenso quando temos um monte de Donald Trumps no sistema tentando confundir todos?

Segundo conceito

Agora temos que introduzir outra regra. O consenso deve corresponder a pelo menos um dos nossos votos iniciais. Isso significa que se ninguém selecionou sim no começo, então o consenso final não pode ser um sim. Se ninguém selecionou não, então o consenso final não pode ser um não. Isso é adicionado para evitar o problema trivial de forçar programaticamente que todos os computadores votem sim.

A pegada

Tolerância de falha bizantina refere-se às propriedades de um algoritmo de consenso. Os melhores algoritmos são chamados tolerantes a falhas bizantinas assíncronas. Isso significa que um grupo de computadores pode chegar a um acordo, embora existam muitos Donald Trumps como parte da rede.

Os segundos melhores algoritmos são chamados de Tolerantes a Falhas Bizantinas ou, em alguns casos, Tolerantes a Faltas Bizantinas Parcialmente Assíncronas. Isso significa que a rede de computadores pode chegar a um acordo, MAS os computadores honestos podem sempre se comunicar e não há “Donald Trumps” no sistema. Tecnicamente falando, a suposição é de que não existem ataques de Botnets ou DDoS. Todas as mensagens precisam chegar com x segundos também.

Portanto, quando apresentado com um algoritmo, alguma pessoa inteligente será capaz de dizer sim, é BFT, não, não é BFT ou sim, é um BFT ou não, não é um BFT.

Uma rede que está BFT está dizendo que pode resolver o Problema Geral do Bizantino, a menos que haja botnets e um BFT esteja dizendo que a rede pode resolver o Problema Geral do Bizantino, independentemente das botnets. Isto significa que o aBFT é melhor que o BFT.

Quais algoritmos NÃO PODEM alcançar o consenso com os maus atores do sistema?

O RAFT é um algoritmo de consenso, mas NÃO PODE tolerar uma falha em um computador bizantino. ou seja, não é tolerante a falhas bizantinas.

Quais algoritmos ainda podem alcançar consenso com os maus atores do sistema?

  • Algumas das primeiras soluções para falhas bizantinas incluem a família de protocolos de consenso conhecida como Paxos.
  • A Tolerância à Falhas Bizantinas Práticas (PBFT) é outro algoritmo de consenso que é tolerante a falhas bizantinas
  • O Bitcoin usa a prova de trabalho como seu algoritmo para obter consenso da ordem da transação. A prova de trabalho permite que a rede supere as falhas bizantinas.
  • Comprovante de Compromisso, Comprovante de Compromisso Delegado, Prova de Autoridade são todos BFT (pitada de sal requerida aqui).

Quando o consenso é impossível?

Ficou provado no documento original sobre problemas gerais bizantinos por Lamport, Shostak e Pease, que nenhuma solução com menos de 3 m + 1 generais pode lidar com m traitors. Em outras palavras, o consenso é impossível de alcançar se um terço ou mais dos generais são traidores.

Surpresa

Nakamoto disse em um e-mail que a prova de trabalho satisfaz a tolerância a falhas bizantinas ( https://satoshi.nakamotoinstitute.org/emails/cryptography/11/ ). A parte chocante é que isso não acontece e não houve nenhuma prova formal.

Prova de trabalho ou prova de aposta são soluções probabilísticas para tolerância a falhas bizantinas (o que significa que não é garantido 100%). Parte do problema é que esses algoritmos de consenso não mapeiam “muito claramente” todas essas matemáticas na área de algoritmos distribuídos (de onde vem toda essa terminologia).

Leemon Baird explica BFT

Leemon faz um ótimo trabalho explicando BFT no vídeo abaixo.

Referências:

https://medium.com/@alexandratran/uma-introdução-cursória-para-consenso-tolerância-de-busca-antiga-e-consenso-alternativa- 1155a5594f18