Estrutura Shoal: Como reduzir a latência do Bullshark na Aptos?

Resumo

Aptos labs resolveu dois importantes problemas abertos no DAG BFT, reduzindo significativamente a latência e eliminando pela primeira vez a necessidade de pausas em protocolos práticos determinísticos. No geral, melhorou a latência do Bullshark em 40% em condições sem falhas e em 80% em condições de falha.

Shoal é uma estrutura que melhora o protocolo de consenso baseado em Narwhal ( através de pipelines e da reputação dos líderes, como DAG-Rider, Tusk, Bullshark ). O pipeline reduz a latência de ordenação do DAG introduzindo âncoras a cada rodada, enquanto a reputação dos líderes melhora ainda mais o problema de latência ao garantir que as âncoras estejam associadas aos nós de validação mais rápidos. Além disso, a reputação dos líderes permite que Shoal utilize a construção assíncrona do DAG para eliminar timeouts em todos os cenários. Isso permite que Shoal forneça a propriedade de resposta universal, incorporando a resposta otimista normalmente necessária.

Esta tecnologia é muito simples, envolvendo a execução em sequência de várias instâncias do protocolo subjacente. Assim, quando instanciado com Bullshark, obtém-se um grupo de "tubarões" em uma corrida de revezamento.

Motivação

Ao buscar alto desempenho em redes de blockchain, as pessoas sempre se concentraram em reduzir a complexidade da comunicação. No entanto, esse método não resultou em um aumento significativo na taxa de transferência. Por exemplo, o Hotstuff implementado nas primeiras versões do Diem alcançou apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.

Recent breakthroughs stem from the recognition that data propagation is the main bottleneck based on leader protocols, which can benefit from parallelization. The Narwhal system separates data propagation from core consensus logic, proposing an architecture where all validators propagate data simultaneously, and the consensus component only orders a small amount of metadata. The Narwhal paper reports a throughput of 160,000 TPS.

A Quorum Store, apresentada anteriormente, implementou a separação entre a propagação de dados e o consenso, para expandir o protocolo de consenso atual Jolteon. Jolteon é um protocolo baseado em líder, que combina o caminho rápido linear do Tendermint e a mudança de visão no estilo PBFT, reduzindo a latência do Hotstuff em 33%. No entanto, os protocolos de consenso baseados em líder não conseguem aproveitar plenamente o potencial de throughput do Narwhal. Embora a separação entre propagação de dados e consenso tenha sido realizada, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda enfrenta limitações.

Assim, foi implementado o Bullshark, um protocolo de consenso sem custos de comunicação, sobre o Narwhal DAG. Infelizmente, em comparação com o Jolteon, a estrutura DAG que suporta o Bullshark com alta taxa de transferência traz um custo de latência de 50%.

Este artigo apresenta como o Shoal reduz significativamente a latência do Bullshark.

Contexto do DAG-BFT

Em cada vértice do Narwhal DAG, está associado ao número de rodadas. Ao entrar na rodada r, os validadores devem primeiro obter n-f vértices da rodada r-1. Cada validador pode transmitir um vértice por rodada, e cada vértice deve referenciar pelo menos n-f vértices da rodada anterior. Devido à assíncronia da rede, diferentes validadores podem observar diferentes visões locais do DAG em qualquer momento.

Uma característica chave do DAG não é ambígua: se dois nós de validação têm o mesmo vértice v na visão local do DAG, então eles têm a mesma história causal de v.

Ordem Total

É possível chegar a um consenso sobre a ordem total de todos os vértices no DAG sem custos adicionais de comunicação. Para isso, os validadores em DAG-Rider, Tusk e Bullshark interpretam a estrutura do DAG como um protocolo de consenso, onde os vértices representam propostas e as arestas representam votos.

Embora a lógica de interseção de grupos na estrutura DAG seja diferente, todos os protocolos de consenso baseados no Narwhal existentes possuem a seguinte estrutura:

1. Ponto de ancoragem: a cada algumas rodadas, há um líder previamente determinado, cujo ápice é chamado de ponto de ancoragem.

2. Ponto de ancoragem da ordem: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem devem ser ordenados ou saltados.

3. História causal ordenada: os validadores processam um a um a lista de âncoras ordenadas, classificando os vértices desordenados anteriores na história causal de cada âncora.

A chave para garantir a segurança é assegurar que, na etapa (2), todas as listas de âncoras ordenadas criadas pelos nós de verificação honestos compartilhem o mesmo prefixo. No Shoal, fazemos as seguintes observações sobre todos esses protocolos:

Todos os validadores concordam com o primeiro ponto de ancoragem ordenado.

Bullshark atraso

A latência do Bullshark depende do número de rodadas entre os pontos âncora ordenados no DAG. Embora a versão de sincronização mais prática do Bullshark tenha uma latência melhor do que a versão assíncrona, ainda está longe de ser a ideal.

Questão 1: Atraso médio de bloco. No Bullshark, cada rodada par tem um ponto de âncora, e o pico da rodada ímpar é interpretado como votação. Em casos comuns, são necessárias duas rodadas do DAG para ordenar os pontos de âncora, no entanto, os picos na história causal do ponto de âncora precisam de mais rodadas para que os pontos de âncora sejam ordenados. Normalmente, os picos na rodada ímpar precisam de três rodadas, enquanto os picos não âncora na rodada par precisam de quatro rodadas.

Pergunta 2: Atraso nos casos de falha. A análise de atraso acima se aplica a situações sem falha; por outro lado, se um líder de rodada não conseguir transmitir os pontos âncora rapidamente o suficiente, os pontos âncora não poderão ser ordenados ( e, portanto, serão pulados ). Todos os vértices não ordenados nas rodadas anteriores devem aguardar que o próximo ponto âncora seja ordenado. Isso diminuirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark utiliza a espera por tempo limite para o líder.

Estrutura Shoal

Shoal resolveu esses dois problemas de latência, aprimorando o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de um pipeline, permitindo que haja âncoras a cada rodada e reduzindo a latência de todos os vértices não âncora no DAG para três rodadas. Shoal também introduziu um mecanismo de reputação de líder sem custo no DAG, com seleção inclinada para líderes rápidos.

Desafio

No contexto do protocolo DAG, o pipeline e a reputação do líder são considerados problemas difíceis, pelas seguintes razões:

1. As tentativas anteriores de modificar a lógica central do Bullshark na linha de produção parecem ser fundamentalmente impossíveis.

2. A reputação dos líderes é introduzida no DiemBFT e formalizada no Carousel, escolhendo dinamicamente os futuros líderes com base no desempenho passado dos validadores ( âncora no Bullshark ). Embora a divergência na identidade dos líderes não viole a segurança desses protocolos, isso pode levar a uma ordenação completamente diferente no Bullshark, o que levanta o núcleo da questão: escolher âncoras de roda de forma dinâmica e determinística é necessário para resolver o consenso, os validadores precisam concordar sobre uma história ordenada para escolher as âncoras futuras.

Como evidência da dificuldade do problema, a implementação do Bullshark ( não suporta essas características, assim como as implementações atualmente em ambiente de produção ).

Acordo

Apesar dos desafios mencionados, a solução está escondida na simplicidade.

No Shoal, dependemos da capacidade de realizar cálculos locais sobre o DAG para preservar e reinterpretar as informações das rodadas anteriores. Com a percepção central de que todos os validadores concordam com o primeiro ponto de ancoragem ordenado, o Shoal combina sequencialmente várias instâncias de Bullshark para processamento em pipeline, tornando ( o primeiro ponto de ancoragem ordenado, e a história causal do ) é utilizada para calcular a reputação do líder.

Linha de Montagem

V que mapeia rodadas para líderes. O Shoal executa instâncias do Bullshark uma a uma, com cada âncora de instância previamente determinada pelo mapeamento F. Cada instância solicita uma âncora, acionando a transição para a próxima instância.

Inicialmente, o Shoal lançou a primeira instância do Bullshark na primeira rodada do DAG e funcionou até que o primeiro ponto de âncora ordenado fosse determinado, como na rodada r. Todos os validadores concordaram com esse ponto de âncora. Assim, todos os validadores podem concordar de forma definitiva em reinterpretar o DAG a partir da rodada r+1. O Shoal apenas inicia uma nova instância do Bullshark na rodada r+1.

No melhor cenário, isso permite que o Shoal encomende um âncora em cada rodada. Os pontos de âncora da primeira rodada são ordenados pelo primeiro exemplo. Em seguida, o Shoal inicia um novo exemplo na segunda rodada, que por si só tem um ponto de âncora, que é ordenado por esse exemplo, e então, outro novo exemplo encomenda um ponto de âncora na terceira rodada, e o processo continua.

Reputação do Líder

Durante o período de ordenação do Bullshark, o atraso aumenta ao pular âncoras. Nesse caso, a tecnologia de pipeline não pode ajudar, pois não é possível iniciar uma nova instância antes que a âncora da instância anterior seja ordenada. O Shoal garante que é menos provável que o líder correspondente seja escolhido para lidar com âncoras perdidas no futuro, atribuindo pontuações com base no histórico de atividade recente de cada nó de validação, utilizando um mecanismo de reputação. Os validadores que respondem e participam do protocolo receberão altas pontuações; caso contrário, os nós de validação receberão pontuações baixas, pois podem estar falhando, lentos ou agindo maliciosamente.

A sua ideia é recalcular de forma determinística a partir do mapeamento pré-definido F, que favorece os líderes com pontuações mais altas, sempre que os pontos são atualizados. Para que os validadores cheguem a um consenso sobre o novo mapeamento, eles devem consensuar sobre a pontuação, alcançando assim um consenso sobre a história utilizada para derivar a pontuação.

No Shoal, a linha de produção e a reputação de liderança podem se combinar naturalmente, uma vez que ambas usam a mesma tecnologia central, que é reinterpretar o DAG após alcançar consenso no primeiro ponto âncora ordenado.

Na verdade, a única diferença é que, após a ordenação dos pontos de ancoragem na r-ésima rodada, o validador só precisa calcular um novo mapeamento F' a partir da r+1-ésima rodada, com base na história causal dos pontos de ancoragem ordenados na r-ésima rodada. Em seguida, os nós de validação começam a usar a função de seleção de pontos de ancoragem atualizada F' para executar uma nova instância do Bullshark a partir da r+1-ésima rodada.

Sem mais tempo limite

O tempo limite desempenha um papel crucial em todas as implementações BFT determinísticas baseadas em líderes. No entanto, a complexidade que elas introduzem aumenta o número de estados internos que precisam ser geridos e observados, o que aumenta a complexidade do processo de depuração e requer mais técnicas de observabilidade.

O tempo limite também aumentará significativamente a latência, pois é muito importante configurá-los adequadamente, geralmente requerendo ajustes dinâmicos, pois depende fortemente do ambiente ( rede ). Antes de passar para o próximo líder, o protocolo pagará a penalidade de latência total do tempo limite para o líder com falha. Portanto, a configuração do tempo limite não pode ser excessivamente conservadora, mas se o tempo limite for muito curto, o protocolo pode pular bons líderes. Por exemplo, observamos que, em condições de alta carga, os líderes em Jolteon/Hotstuff ficam sobrecarregados, e o tempo limite expira antes que o progresso seja feito.

Infelizmente, os protocolos baseados em líderes (, como Hotstuff e Jolteon ), essencialmente precisam de timeouts para garantir que o protocolo avance sempre que um líder falhar. Sem timeouts, mesmo um líder que tenha falhado pode parar o protocolo para sempre. Como não é possível distinguir entre líderes com falha e líderes lentos durante períodos assíncronos, os timeouts podem fazer com que os nós de validação vejam mudanças em todos os líderes sem atividade de consenso.

No Bullshark, o timeout é usado na construção do DAG, para garantir que durante a sincronização, líderes honestos adicionem âncoras ao DAG rapidamente.