Um olhar técnico sobre o algoritmo do Consenso da Libra

O Facebook divulgou sua nova criptomoeda de baixa volatilidade, a Libra, alimentada por uma plataforma de contrato inteligente projetada para ser “segura, escalável e confiável”.

Libra Blockchain usa um sistema de replicação de máquina de estado robusto e eficiente chamado LibraBFT [1], que é o foco desta análise técnica. Discutimos suas propriedades e comparamos com outros protocolos consensuais de Tolerância a Falhas Bizantinas (BFT) com propriedades similares.

Consenso clássico e Nakamoto

O consenso é um processo usado para alcançar um acordo sobre um único valor de dados entre processos ou sistemas distribuídos. Os processos que participam do consenso podem confiar ou não uns nos outros e, ainda assim, poderão chegar a um acordo sobre um único valor de dados. Existem duas classes de algoritmos de consenso.

Algoritmos estilo Nakamoto – Esta classe de algoritmos de consenso, popularizada pelo Bitcoin, elege um líder aleatoriamente através de um quebra-cabeça criptográfico e o líder propõe um bloco de transações junto com uma prova de trabalho (PoW) para todos os outros processos na rede. A decisão da maioria é representada pela cadeia mais longa, que tem o maior esforço de prova de trabalho investido nela. Se a maioria for controlada por processos honestos, a cadeia honesta crescerá mais rápido e ultrapassará qualquer cadeia concorrente.
Algoritmos de consenso clássico – Nesta classe de algoritmos, os processos participantes chegam ao consenso usando várias rodadas de trocas de mensagens com votos e provas de segurança. A maioria dos processos deve concordar com os votos e as provas de segurança, a fim de alcançar um consenso.

Algoritmos de consenso clássicos satisfazem as seguintes propriedades gerais.

Validade – Se um processo correto p transmite uma mensagem m, então p eventualmente entrega m.

Acordo – Se uma mensagem m é entregue por algum processo correto, então m é finalmente entregue por cada processo correto.

Integridade – Nenhum processo correto entrega a mesma mensagem mais de uma vez; Além disso, se um processo correto entregar uma mensagem m, se o remetente p de m estiver correto, então m foi anteriormente transmitido por p.

Pedido total – Para mensagens m1 e m2, suponha que p e q sejam dois processos corretos que entregam m1 e m2. Então p entrega m1 antes de m2 se, e somente se, q entregar m1 antes de m2.

Falhas bizantinas

Quando uma rede de processos diferentes participa de um processo de consenso, ocorrem falhas. Por exemplo, os processos podem falhar, experimentar falhas de energia e de rede ou simplesmente não conseguir progredir porque estão presos em um determinado estado. Estes geralmente são classificados como falhas de travamento. Por outro lado, alguns processos podem intencionalmente agir maliciosamente para orientar o consenso em seu benefício. Essas falhas são chamadas de Falhas Bizantinas. Algoritmos de consenso que toleram Falhas Bizantinas são chamados de algoritmos de Tolerância a Falhas Bizantinas (BFT – Byzantine Fault Tolerant). Os algoritmos de consenso da BFT também são capazes de lidar com falhas de colisão automaticamente.

Redes autorizadas e sem permissão

A rede de processos que participam do processo de consenso pode ser configurada em configurações autorizadas ou sem permissão.

Rede autorizada – Em uma rede autorizada, a identidade e a contagem de processos na rede são conhecidas por todos os processos. Assim, um processo pode confiar nas mensagens originadas de outro processo na mesma rede. Embora os processos possam sair e ingressar na rede à vontade, suas identidades devem ser conhecidas a priori para todos os processos na rede.
Rede sem permissão – Em uma rede sem permissão, nem as identidades do processo nem suas contagens são conhecidas por outros processos. Assim, quando um novo processo se une à rede, ele deve fornecer alguma forma de prova de trabalho para provar sua associação a outros processos.

O Libra Blockchain será configurado como uma rede de permissão no lançamento com um conjunto conhecido de processos chamados Validadores. Isso significa que todos os validadores da rede Libra conhecem as identidades uns dos outros.

LibraBFT, HotStuff, pBFT e Tendermint

O LibraBFT pertence à classe de algoritmos de consenso clássicos do BFT. Ele é baseado em outro algoritmo de consenso chamado HotStuff [2], que, por sua vez, empresta parte de sua lógica de consenso de outro algoritmo clássico de BFT chamado Tolerância de Falha Bizantina Prática, pBFT [3].

Tolerância a falhas bizantinas práticas

O pBFT usa um modelo de sistema, que assume um sistema distribuído assíncrono onde os processos são conectados por uma rede. A rede pode falhar ao entregar mensagens, atrasá-las, duplicá-las ou entregá-las fora de ordem. Se N é o número total de processos na rede e f é o número de processos defeituosos (incluindo Bizantinos), então pBFT requer:

N ≥ 3f + 1

processos para fornecer tolerância contra falhas bizantinas.

O algoritmo de consenso pBFT faz progressos em várias rodadas, onde cada rodada realiza acordo em algum estágio no processo de consenso. A figura 1 ilustra os ciclos de consenso de pBFT, que prosseguem como segue.

Um cliente C envia uma solicitação para chamar uma operação de serviço para o processo primário 0. Esse é o líder dessa rodada de consenso.
Os multicasts primários enviam a solicitação para outros processos, 1, 2 e 3. Esses processos são chamados de réplicas.
As réplicas executam a solicitação e enviam uma resposta ao cliente.
O cliente aguarda respostas f+1 de réplicas diferentes com o mesmo resultado; este é o resultado da operação.

O protocolo progride e garante a vitalidade, se o líder não falhar. No caso de falhas do líder, um protocolo de mudança de exibição é acionado após um tempo limite para evitar que as réplicas esperem para sempre as mensagens do líder. Em uma rede assíncrona distribuída geograficamente, as falhas de líder podem ser mais comuns do que se pode imaginar, portanto, os acionadores de mudança de exibição também podem ser comuns. Assim, a complexidade de execução do pBFT com mudanças de visão é O(n3) onde n é o número de processos na rede.

O protocolo fornece segurança se todas as réplicas sem falhas computarem o mesmo resultado. Isso significa que os processos (N-f) devem calcular o mesmo resultado e enviar os resultados para o cliente para garantir a segurança.

Hotstuff

O algoritmo de consenso HotStuff tenta abordar a complexidade O(n3) do pBFT. A propriedade de atividade requer que réplicas sem falhas (N-f) executem comandos de forma idêntica e produzam a mesma resposta para cada comando. Como é comum, com o modelo de comunicação parcialmente síncrono, por meio do qual uma transmissão de mensagem bound— ∆ — on conhecida se mantém após algum tempo de estabilização global desconhecida (GST). Neste modelo, N ≥ 3f + 1 é necessário para que réplicas sem falhas concordem com os mesmos comandos na mesma ordem, e o progresso pode ser assegurado deterministicamente somente após o GST, como discutimos anteriormente com mudanças de visão. O HotStuff melhora o pBFT com as duas propriedades adicionais a seguir.

Alteração da visualização linear – Após a GST, qualquer líder correto, uma vez designado, envia apenas autenticadores O(n) para conduzir uma decisão de consenso. Isso inclui o caso em que um líder é substituído. Consequentemente, os custos de comunicação para chegar ao consenso após GST são autenticadores O(n2) no pior caso de falhas de líder em cascata.
Capacidade de resposta otimista – Depois do GST, qualquer líder correto, uma vez designado, precisa esperar apenas pelas primeiras respostas (N-f) para garantir que possa criar uma proposta que fará progressos. Isso inclui o caso em que um líder é substituído.

A Tabela 1 abaixo mostra as melhorias resultantes na complexidade da mensagem. Com o líder correto, a complexidade melhorou de O(n2) para O(n). Com a falha do líder e o protocolo de mudança de exibição resultante, a complexidade melhorou de O(n3) para O(n).

Tabela 1 – Comparação das complexidades de mensagens de alguns algoritmos clássicos de consenso de BFT

Em pBFT, cada rodada do consenso realiza um trabalho semelhante (como coletar votos de réplicas etc.), que o HotStuff otimiza encadeando Certificados de Quorum (QC), conforme mostrado na fig. 2. Com isso, as rodadas de consenso podem ser encadeadas, melhorando assim a vivacidade. Mudanças de visualização k requer k+2 rodadas de comunicação ao invés de 2*k.

O HotStuff também implementa um mecanismo chamado Pacemaker (ou Marcapasso em inglês), que garante a vivacidade após o GST. Marcapasso a) sincroniza todas as réplicas corretas e um líder único em uma altura comum por um período de tempo suficientemente longo. Ele escolhe o líder único, de modo que as réplicas corretas sincronizadas progridem com o líder escolhido. Esse mecanismo dissocia a vivacidade do protocolo, o que, por sua vez, o dissocia da segurança.

LibraBFT

LibraBFT melhora o HotStuff com uma especificação detalhada e implementação do mecanismo do Marcapasso discutido acima. Ele também vem com uma análise de vivacidade que consiste em limites concretos ao compromisso de transação. Além desses aprimoramentos, o LibraBFT é essencialmente HotStuff e faz as mesmas suposições sobre o modelo do sistema com uma rede parcialmente síncrona.

Nos processos LibraBFT são chamados Validators e eles fazem progressos em rodadas, cada um tendo um validador designado chamado líder. Os líderes são responsáveis por propor novos blocos e obter votos assinados pelos validadores em suas propostas. LibraBFT segue o modelo de HotStuff Acorrentado descrito na fig. 2, que funciona da seguinte maneira:

Uma rodada é uma fase de comunicação com um único líder designado, e as propostas do líder são organizadas em uma cadeia usando hashes criptográficos.
Durante uma rodada, o líder propõe um bloco que estende a cadeia mais longa que conhece.
Se a proposta for válida e oportuna, cada nó honesto assinará e enviará um voto de volta ao líder.
Depois que o líder recebeu votos suficiente para chegar ao quórum, ele agrega os votos em um Certificado de Quorum (QC) que estende a mesma cadeia novamente.
O QC é transmitido para todos os nós.
Se o líder não conseguir montar um QC, os participantes terão o tempo limite e passarão para a próxima rodada.
Eventualmente, blocos e QCs suficientes estenderão a cadeia de maneira oportuna e um bloco corresponderá à regra de confirmação do protocolo.
Quando isso acontece, a cadeia de blocos não confirmados até o bloco correspondente é confirmada.

O processo de consenso acima pode ser comparado com outro algoritmo de consenso BFT clássico popular, Tendermint [4], que é ilustrado na fig. 3.

Fig. 3 – Processo de consenso de mendigo

Assim como o LibraBFT, o Tendermint procede em várias rodadas – pré-voto, pré-commit e commit – e coleta as assinaturas do Validador para cada rodada, similar aos QCs no LibraBFT. A principal diferença entre os dois algoritmos é que em Tendermint cada rodada tem um timeout e os Validators aguardam mesmo que terminem a rodada mais cedo, enquanto no LibraBFT, uma vez que a rede é síncrona, a velocidade do protocolo é baseada na latência da rede, desde que o líder esteja correto.

A qualificação destacada acima é importante. O protocolo termina sem ter que esperar por um tempo limite, somente se o líder estiver correto. Se o líder falhar, o protocolo de mudança de visão é acionado após GST e enquanto a mudança de visão é linear e é otimizada quando comparada a pBFT, ela pode não ter um desempenho melhor do que a implementação de Tendermint.

Implicações práticas do LibraBFT

A Libra Blockchain é lançada como uma rede autorizada. Os validadores fundadores incluem empresas como Uber, Visa, MasterCard, PayPal etc. Os membros fundadores são obrigados a cumprir as diretrizes rígidas para fazer parte do conjunto inicial do Validador. Por exemplo, os fundos de hedge criptográficos tinham que ter um AUM acima de US$ 1 bilhão, enquanto os custodiantes focados em ativos digitais precisavam armazenar pelo menos US$ 100 milhões. As empresas não-criptográficas precisam ter uma capitalização de mercado de mais de US$ 1 bilhão ou ostentar balanços de clientes que equivalem a mais de US$ 500 milhões. Com tais requisitos rigorosos em vigor, pode-se assumir que os validadores serão mais provavelmente executados em data centers com redes privadas ou altamente confiáveis conectando-os. Eles provavelmente são tolerantes a falhas, semelhantes à configuração necessária para executar o Cosmos Validators (que executa o algoritmo de consenso Tendermint). Então, praticamente falando, o HotStuff Acorrentado provavelmente será o único design importante que melhora a vivacidade do protocolo. Todos os outros aprimoramentos de design podem ser menos úteis na implantação prática descrita acima. Por outro lado, se for assumido que a rede não é confiável, as suposições feitas sobre a exatidão dos líderes para finalização rápida podem, de fato, falhar, resultando no pior desempenho possível.