Estrutura Shoal: Reduzir significativamente a latência do Bullshark na Aptos

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

Shoal é uma estrutura que aprimora o protocolo de consenso baseado em Narwhal ( através de uma linha de produção e um mecanismo de reputação de líderes, como DAG-Rider, Tusk, Bullshark ). A linha de produção reduz a latência de ordenação de DAG ao introduzir um ponto âncora em cada rodada, e a reputação do líder melhora ainda mais o problema de latência ao garantir que o ponto âncora esteja associado ao nó de validação mais rápido. Além disso, a reputação do líder permite que o Shoal aproveite a construção de DAG assíncrona para eliminar os tempos limite em todos os cenários. Isso permite que o Shoal ofereça propriedades de resposta universal, incluindo a resposta otimista normalmente necessária.

Esta tecnologia é muito simples, envolvendo a execução sequencial de várias instâncias do protocolo subjacente uma após a outra. Assim, quando usamos a instanciação Bullshark, obtemos um grupo de "tubarões" a participar numa corrida de estafetas.

Antecedentes

Na busca por 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 100.000+ TPS.

As recentes quebras surgem da percepção de que a propagação de dados é o principal gargalo baseado no protocolo de liderança, podendo beneficiar-se da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central, propondo uma arquitetura onde todos os validadores propagam dados simultaneamente, enquanto o componente de consenso apenas ordena uma pequena quantidade de metadados. O artigo do Narwhal reportou uma taxa de transferência de 160.000 TPS.

Anteriormente, introduzimos o Quorum Store, ou seja, a nossa implementação Narwhal que separa a propagação de dados do consenso, e como usá-lo para expandir o atual protocolo de consenso Jolteon. Jolteon é um protocolo baseado em líder que combina o caminho rápido linear do Tendermint com a mudança de vista estilo PBFT, podendo reduzir a latência do Hotstuff em 33%. No entanto, é evidente que os protocolos de consenso baseados em líder não conseguem aproveitar plenamente o potencial de throughput do Narwhal. Embora a propagação de dados seja separada do consenso, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda é limitado.

Assim, decidimos implementar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com custo de comunicação zero. Infelizmente, em comparação com o Jolteon, a estrutura DAG que suporta o Bullshark de alta capacidade de processamento tem um custo de latência de 50%.

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

Contexto do DAG-BFT

Cada vértice no DAG do Narwhal está relacionado a uma rodada. Para entrar na rodada r, o validador deve primeiro obter n-f vértices que pertencem à 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 ponto no tempo.

Uma propriedade chave do DAG é que não é ambígua: se dois nós de verificação têm o mesmo vértice v em sua visão local do DAG, então eles têm a mesma história causal de v.

Prefácio

É possível alcançar um consenso sobre a ordem total de todos os vértices no DAG sem custos adicionais de comunicação. Para isso, os validadores no 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 em Narwhal existentes possuem a seguinte estrutura:

1. Ponto de ancoragem: a cada poucas rodadas (, como em duas rodadas ) no Bullshark, há um líder previamente determinado, e o pico do líder é chamado de ponto de ancoragem.

2. Pontos de ancoragem ordenados: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem ordenar e quais pular.

3. História causal ordenada: os validadores processam um por um a lista de âncoras ordenadas, para cada âncora, ordenam todos os vértices anteriores não ordenados em sua história causal de acordo com algumas regras determinísticas.

A chave para garantir a segurança é assegurar que, no passo (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 latência

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

Pergunta 1: latência média de bloco. No Bullshark, cada rodada par tem um ponto de ancoragem, enquanto os vértices da rodada ímpar são interpretados como votos. Em condições normais, são necessárias duas rodadas de DAG para ordenar os pontos de ancoragem; no entanto, os vértices na história causal dos pontos de ancoragem precisam de mais rodadas para que os pontos de ancoragem sejam ordenados. Em condições normais, os vértices na rodada ímpar precisam de três rodadas, enquanto os vértices não âncoras na rodada par precisam de quatro rodadas.

Pergunta 2: Situação de falha latência. A análise de latência acima se aplica a situações sem falha; por outro lado, se o líder de uma rodada não conseguir transmitir o ponto de âncora rapidamente o suficiente, não será possível ordenar esse ponto de âncora (, sendo assim, ele será pulado ). Portanto, todos os vértices não ordenados nas rodadas anteriores devem esperar que o próximo ponto de âncora seja ordenado. Isso pode reduzir significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark usa um tempo limite para esperar pelo líder.

Quadro Shoal

Shoal resolveu esses dois problemas de latência, aprimorando o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de pipelines, permitindo que haja um ponto de ancoragem a cada rodada e reduzindo a latência de todos os vértices não âncoras no DAG para três rodadas. Shoal também introduziu um mecanismo de reputação de líderes sem custo no DAG, o que faz com que a escolha favoreça 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, pelos seguintes motivos:

1. As tentativas anteriores de linha de produção tentaram modificar a lógica central do Bullshark, mas isso parece ser essencialmente impossível.

2. A reputação do líder é introduzida no DiemBFT e formalizada no Carousel, sendo selecionada dinamicamente com base no desempenho passado dos validadores para futuros líderes, a ideia do âncora no Bullshark (. Embora a divergência na identidade do líder não viole a segurança desses protocolos, no Bullshark, ela pode levar a uma ordenação completamente diferente, o que leva ao cerne da questão: a escolha dinâmica e determinística do âncora do ciclo é necessária para resolver o consenso, e os validadores precisam chegar a um consenso sobre a história ordenada para selecionar futuros âncoras.

Como evidência da dificuldade da questão, notamos que a implementação do Bullshark, incluindo a implementação atual em ambiente de produção, não suporta essas características.

![万字详解Shoal框架：如何减少Aptos上的Bullshark latência？])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(

Protocolo

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

No Shoal, dependemos da capacidade de executar cálculos locais no DAG e realizamos a capacidade de salvar 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 processá-las em pipeline, tornando )1( o primeiro ponto de ancoragem ordenado o ponto de troca das instâncias, assim como )2( a história causal do ponto de ancoragem é usada para calcular a reputação dos líderes.

Linha de produção

V que mapeia a rodada ao líder. Shoal executa instâncias do Bullshark uma após a outra, de modo que para cada instância, a âncora é determinada previamente pelo mapeamento F. Cada instância classifica uma âncora, o que desencadeia 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 a executou até que o primeiro ponto âncora ordenado fosse determinado, como na rodada r. Todos os validadores concordaram com esse ponto âncora. Portanto, todos os validadores podem concordar com segurança em reinterpretar o DAG a partir da rodada r+1. O Shoal apenas lançou uma nova instância do Bullshark na rodada r+1.

No melhor cenário, isso permite que o Shoal classifique uma âncora em cada rodada. A âncora da primeira rodada é classificada pela primeira instância. Em seguida, o Shoal inicia uma nova instância na segunda rodada, que por si só tem uma âncora, que é classificada por essa instância, e então, outra nova instância classifica a âncora na terceira rodada, e o processo continua.

![Explicação detalhada do framework Shoal: como reduzir a latência do Bullshark na Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Reputação do Líder

Durante a fase de ordenação do Bullshark, a latência aumenta ao pular pontos de âncora. Nesse caso, a técnica de pipeline é ineficaz, pois não é possível iniciar novas instâncias antes de o ponto de âncora da instância anterior ser ordenado. O Shoal garante que é menos provável que os líderes correspondentes sejam escolhidos no futuro para lidar com pontos de âncora perdidos, atribuindo uma pontuação a cada nó de validação 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 serão atribuídos baixas pontuações, uma vez que podem estar com falhas, lentos ou agindo de forma maliciosa.

A sua filosofia é recalcular de forma determinística o mapeamento pré-definido F do round ao líder a cada atualização de pontuação, com uma preferência por líderes com pontuações mais altas. Para que os validadores possam chegar a um consenso sobre o novo mapeamento, eles devem chegar a um consenso sobre as pontuações, alcançando assim um consenso sobre a história utilizada para derivar as pontuações.

No Shoal, a linha de produção e a reputação de liderança podem se combinar naturalmente, uma vez que ambas utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após alcançar consenso sobre o primeiro ponto de ancoragem ordenado.

Na verdade, a única diferença é que, após classificar os pontos âncora na r-ésima rodada, os validadores precisam apenas calcular um novo mapeamento F' a partir da r+1-ésima rodada, com base na história causal dos pontos âncora 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 âncora atualizada F' para executar uma nova instância do Bullshark a partir da r+1-ésima rodada.

![Explicação detalhada do framework Shoal: como reduzir a latência do Bullshark na Aptos?])https://img-cdn.gateio.im/webp-social/moments-1baf540693f376d93cb18ef3193593cc.webp(

Não há mais tempo de espera

O tempo limite desempenha um papel crucial em todas as implementações BFT determinísticas baseadas em líder. No entanto, a complexidade que 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 exige mais técnicas de observabilidade.

O tempo limite também aumentará significativamente a latência, pois é muito importante configurá-los adequadamente e geralmente requer ajustes dinâmicos, pois depende fortemente do ambiente ) rede (. Antes de transferir para o próximo líder, o protocolo pagará a penalização total da latência do tempo limite para o líder com falha.