Protocolos BFT: PBFT e Tendermint

O Problema dos Generais Bizantinos, formulado por Lamport, Shostak e Pease em 1982, pergunta: um sistema distribuído pode chegar a um consenso quando alguns participantes enviam mensagens contraditórias? O problema recebeu esse nome por causa dos generais bizantinos que precisam coordenar um ataque, mas podem incluir traidores que enviam ordens conflitantes. Um sistema é Tolerante a Falhas Bizantinas (BFT) quando alcança um consenso correto apesar de até f nós maliciosos entre 3f+1 nós no total. BFT é o padrão ouro para o consenso de cadeias de blocos que exige segurança sob condições adversariais.

PBFT (Castro e Liskov, 1999) foi o primeiro protocolo BFT prático, demonstrando que BFT poderia operar com eficiência em sistemas reais. O PBFT opera em visões, ou períodos, cada uma com um primário designado, o líder. A operação normal executa três fases: pré-preparação, na qual o primário transmite a solicitação do cliente e o número de sequência; preparação, na qual as réplicas transmitem sua concordância com a sequência; e confirmação, na qual as réplicas transmitem a confirmação. Uma solicitação é executada quando uma réplica coleta 2f+1 mensagens de confirmação correspondentes. O PBFT fornece segurança e vivacidade desde que menos de 1/3 das réplicas sejam bizantinas.

A principal limitação do PBFT é a complexidade de mensagens O(n^2) por solicitação: cada uma das n réplicas envia mensagens a todas as outras nas fases de preparação e confirmação. Para n=100 réplicas, cada solicitação gera aproximadamente 10.000 mensagens. Isso torna o PBFT impraticável para grandes conjuntos de validadores. A comunidade de pesquisa em BFT passou duas décadas aprimorando esse aspecto: BFT-SMART reduziu os fatores constantes, HotStuff alcançou complexidade linear de mensagens por meio de um modelo de retransmissão pelo líder, e o Tendermint adaptou ideias do PBFT para uso em cadeias de blocos públicas.

Quando se suspeita que o primário do PBFT está com falha, devido a um tempo limite, as réplicas iniciam uma mudança de visão. Cada réplica transmite uma mensagem de mudança de visão contendo seu estado, incluindo os valores preparados da visão anterior. O novo primário coleta 2f+1 mensagens de mudança de visão, constrói uma mensagem de nova visão que comprova que a transição de estado é consistente com os valores confirmados anteriormente e a transmite. As mudanças de visão são dispendiosas, com O(n^3) mensagens, e foram um gargalo prático. Otimizações como o certificado de mudança de visão do PBFT e o design em etapas do HotStuff resolvem esse problema.

O Tendermint (2014, Kwon; em produção no Cosmos desde 2019) adapta o PBFT para ambientes de cadeias de blocos públicas. O Tendermint tem três fases por bloco: proposta, na qual o líder transmite o bloco proposto; pré-voto, na qual os validadores votam na proposta; e pré-confirmação, na qual os validadores votam para confirmar depois de observar 2/3 de pré-votos. Um bloco é confirmado quando um validador coleta 2/3 de votos de pré-confirmação, formando um certificado de quórum. Os validadores se alternam como proponentes em ordem circular, ponderada pela participação. Se uma rodada expirar sem uma confirmação, os validadores avançam para a rodada seguinte com um voto nulo.

O Tendermint fornece segurança forte: um bloco confirmado é final e não pode ser revertido enquanto menos de 1/3 da participação for bizantina. Essa é uma finalização síncrona: não há bifurcações depois da confirmação. A vivacidade exige uma rede parcialmente síncrona: o protocolo avança quando os atrasos das mensagens são limitados, mas não exige sincronia continuamente. O compromisso entre vivacidade e segurança é fundamental: o Tendermint sacrifica a vivacidade, podendo parar quando a rede é particionada, para garantir a segurança, ao contrário de cadeias como o Bitcoin, que sacrificam a segurança, permitindo bifurcações temporárias, em favor da vivacidade.

Um mecanismo fundamental do Tendermint é o bloqueio de votos. Quando um validador envia uma pré-confirmação para um bloco na rodada r, ele fica bloqueado nesse bloco. Nas rodadas seguintes, um validador bloqueado só pode emitir um pré-voto para o bloco em que está bloqueado, ou um voto nulo se receber uma prova de que o bloco não foi confirmado. Isso impede confirmações contraditórias entre rodadas. Um validador só pode desbloquear-se ao receber, em uma rodada posterior, uma prova de 2/3 de pré-votos para um bloco diferente, demonstrando que o bloco original não foi confirmado.

A Comunicação entre Cadeias de Blocos (IBC) do Cosmos depende da finalização instantânea do Tendermint para transferências entre cadeias. Um cliente leve do Tendermint acompanha o conjunto de validadores e a confirmação mais recente, que consiste em um cabeçalho de bloco mais 2/3 de assinaturas de pré-confirmação. Para verificar um pacote da cadeia A, o módulo IBC da cadeia B verifica o certificado de quórum: 2/3 dos validadores da cadeia A assinaram o cabeçalho de bloco relevante. Assim, a segurança do IBC depende da garantia BFT do Tendermint: uma transferência entre cadeias é final assim que o bloco de origem é confirmado.

HotStuff (Yin et al., 2018; base do LibraBFT/DiemBFT do Facebook, atualmente usado pelo Aptos e pelo Sui) alcança complexidade de mensagens O(n) por rodada de consenso usando uma topologia em estrela: todos os validadores enviam votos ao líder, o líder os agrega em uma assinatura de limiar, o QC, certificado de quórum, e transmite o QC. HotStuff usa um design de encadeamento em três fases, no qual as provas de segurança abrangem três QC consecutivos, permitindo o processamento em etapas. A complexidade linear torna o HotStuff prático para 100 a 300 validadores, como implementado no Aptos e no Sui.

As cadeias de blocos empresariais, como Hyperledger Fabric, Besu e Quorum, usam consenso BFT em redes permissionadas nas quais a identidade dos validadores é conhecida. O serviço de ordenação baseado em Raft do Hyperledger Fabric fornece tolerância a falhas de parada (não bizantinas) para consórcios confiáveis. O marco planejado do Fabric para BFT tem como alvo o SMART, uma implementação baseada em biblioteca. O R3 Corda usa um agrupamento de notários com BFT-SMART para impedir gastos duplos. A escolha entre CFT e BFT reflete os pressupostos de confiança: BFT é necessário quando os validadores podem ser adversários, enquanto CFT é suficiente quando eles são apenas não confiáveis.

Entender BFT exige compreender quais ataques ele impede e quais não impede. BFT lida com validadores que emitem mensagens contraditórias para diferentes pares e com validadores que falham ou ficam silenciosos. Ele não lida com ataques Sybil: um invasor que controla 1/3 dos validadores ao criar identidades falsas pode violar a segurança. É por isso que as cadeias BFT públicas usam ponderação por participação na Prova de Participação: adquirir 1/3 da participação custa dinheiro real, oferecendo resistência a ataques Sybil. BFT também pressupõe a entrega eventual de mensagens, ou sincronia parcial: uma partição de rede que dure mais que o tempo limite de vivacidade pode interromper a cadeia.

Qual é a fração máxima de validadores que pode ser bizantina em um protocolo BFT padrão, mantendo a segurança?

Os protocolos BFT garantem o consenso apesar de até 1/3 de validadores maliciosos. O PBFT (1999) provou que BFT era prático, mas tem complexidade de mensagens O(n^2). O Tendermint adapta o PBFT para cadeias de blocos, com finalização instantânea e bloqueio de votos. HotStuff alcança complexidade O(n) por meio de certificados de quórum com assinaturas de limiar e é usado pelo Aptos e pelo Sui. O IBC do Cosmos usa a finalização instantânea do Tendermint para transferências entre cadeias verificadas. As cadeias de blocos empresariais usam BFT-SMART ou Raft, dependendo de serem esperadas falhas bizantinas ou apenas falhas de parada.