Shoal框架:Gota novo plano para a latência do Bullshark em Aptos

Aptos Labs recentemente resolveu dois importantes problemas abertos no DAG BFT, reduzindo significativamente a latência, e pela primeira vez eliminou a necessidade de tempo limite em um protocolo prático determinístico. No total, a latência do Bullshark foi melhorada em 40% em condições sem falhas e em 80% em condições de falha.

Shoal é um framework que melhora o protocolo de consenso baseado em Narwhal ( através do processamento em pipeline e do mecanismo de reputação de líderes, como DAG-Rider, Tusk e Bullshark ). O processamento em pipeline reduz a Gota de ordenação DAG ao introduzir âncoras em cada rodada, enquanto o mecanismo de reputação de líderes melhora ainda mais os problemas de latência, garantindo que as âncoras estejam associadas aos nós de validação mais rápidos. Além disso, a reputação de líderes 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 forneça uma propriedade chamada "resposta universal", que contém a resposta otimista geralmente necessária.

A tecnologia do Shoal é bastante simples, envolvendo a execução de múltiplas instâncias do protocolo subjacente uma após a outra. Assim, quando instanciamos com Bullshark, obtemos um grupo de "tubarões" realizando uma corrida de revezamento.

Contexto

Na busca por alto desempenho em redes de blockchain, as pessoas sempre se preocuparam em reduzir a complexidade da comunicação. No entanto, esse método não resultou em um aumento significativo na latência. Por exemplo, o Hotstuff implementado nas versões iniciais do Diem alcançou apenas 3500 TPS, bem abaixo da nossa meta de 100k+ TPS.

Os recentes avanços resultam do reconhecimento de que a propagação de dados é um dos principais gargalos baseados nos protocolos dos líderes, 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 quantidade reduzida de metadados. O artigo sobre Narwhal reportou uma taxa de transferência de 160.000 TPS.

A nossa implementação do Narwhal Quorum Store separa a propagação de dados do consenso, para escalar o atual protocolo de consenso Jolteon. Jolteon é um protocolo baseado em liderança que combina o caminho rápido linear do Tendermint e a mudança de visão no estilo PBFT, podendo reduzir a latência do Hotstuff em 33%. No entanto, os protocolos de consenso baseados em liderança não conseguem aproveitar plenamente o potencial de throughput do Narwhal. Apesar de separar a propagação de dados do consenso, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda está limitado.

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

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

Contexto do DAG-BFT

Cada vértice no DAG do Narwhal está associado a uma rodada. Para entrar na rodada r, o validador deve primeiro obter n-f vértices pertencentes à 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 não é ambígua: se dois nós de verificação têm o mesmo vértice v em suas visões locais do DAG, então eles têm a mesma história causal de v.

Prefácio

É possível alcançar 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 existentes baseados no Narwhal possuem a seguinte estrutura:

1. Ponto de ancoragem: A cada algumas rodadas, haverá um líder previamente determinado, e o ápice do líder é chamado de ponto de ancoragem.

2. Âncora de ordenação: os validadores determinam de forma independente, mas determinística, quais âncoras ordenar e quais âncoras pular.

3. Ordem da história causal: 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, através de regras determinísticas.

A chave para garantir a segurança é assegurar que, no passo (2), todos os nós de validação honestos criem uma lista de âncoras ordenada, para que todas as listas compartilhem o mesmo prefixo. No Shoal, fazemos as seguintes observações sobre todos os protocolos acima mencionados:

Todos os validadores concordam com o primeiro ponto âncora ordenado.

Bullshark latência

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

Questão 1: Gota 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 situações comuns, 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 esperar que os pontos de ancoragem sejam ordenados. Em situações comuns, os vértices na rodada ímpar precisam de três rodadas, enquanto os vértices não ancorados na rodada par precisam de quatro rodadas.

Questão 2: Gota de casos de falha, a análise de latência acima se aplica a situações sem falhas. Por outro lado, se o líder de uma rodada não conseguir transmitir o ponto de ancoragem rapidamente o suficiente, não será possível ordenar o ponto de ancoragem ( e, portanto, será ignorado ). Assim, todos os vértices não ordenados nas rodadas anteriores devem esperar que o próximo ponto de ancoragem seja ordenado. Isso pode reduzir significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark usa o tempo limite para esperar pelo líder.

Estrutura Shoal

Shoal melhorou o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através do processamento em pipeline, permitindo um ponto de ancoragem em cada rodada e reduzindo a latência de todos os vértices não ancorados no DAG para três rodadas. Shoal também introduziu um mecanismo de reputação de líder sem custo no DAG, o que faz com que a escolha favoreça líderes rápidos.

Desafio

No contexto do protocolo DAG, o processamento em pipeline e a reputação do líder são considerados problemas difíceis, pelos seguintes motivos:

1. O processamento em linha anterior tentou modificar a lógica central do Bullshark, mas isso parecia 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, com a ideia de âncoras no Bullshark (. Embora a divergência na identidade do líder não viole a segurança desses protocolos, no Bullshark, pode levar a ordenações completamente diferentes, o que traz à tona o cerne da questão: escolher âncoras rotativas de forma dinâmica e determinística é necessário para resolver o consenso, e os validadores precisam chegar a um consenso sobre a história ordenada para escolher futuras âncoras.

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

Protocolo

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

No Shoal, confiamos na capacidade de realizar cálculos locais sobre o DAG e implementamos a capacidade de salvar e reinterpretar as informações das rodadas anteriores. Com a percepção fundamental de que todos os validadores concordam com o primeiro ponto âncora ordenado, o Shoal combina sequencialmente várias instâncias de Bullshark para processá-las em pipeline, fazendo com que ) o primeiro ponto âncora ordenado seja o ponto de troca das instâncias, assim como ( a história causal do ponto âncora é utilizada para calcular a reputação dos líderes.

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

Processamento em pipeline

V que mapeia a rodada ao líder. Shoal executa instâncias do Bullshark uma a uma, de modo que para cada instância, o âncora é determinado previamente pelo mapeamento F. Cada instância classifica um âncora, o que desencadeia a mudança 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é identificar o primeiro ponto de ancoragem ordenado, como na rodada r. Todos os validadores concordaram com esse ponto de ancoragem. Assim, todos os validadores podem concordar de forma definitiva 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 um âncora em cada rodada. O ponto de âncora da primeira rodada é classificado de acordo com a primeira instância. Em seguida, o Shoal inicia uma nova instância na segunda rodada, que tem seu próprio ponto de âncora, e essa âncora é classificada por essa instância, e então, outra nova instância classifica o ponto de âncora na terceira rodada, e o processo continua.

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

Reputação dos líderes

Durante o período de ordenação do Bullshark, a latência aumentará ao pular os pontos âncora. Nesse caso, a técnica de processamento em pipeline não pode ajudar, pois não é possível iniciar novas instâncias antes da ordenação do ponto âncora da instância anterior. O Shoal assegura que líderes correspondentes não sejam escolhidos para lidar com pontos âncora perdidos no futuro, atribuindo uma pontuação a cada nó de validação com base no histórico de atividade recente de cada nó, 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 com baixas pontuações, pois podem estar com falhas, lentos ou agindo de má-fé.

A sua filosofia é recalcular de forma determinística a mapeamento pré-definido F de cada turno ao líder, favorecendo os líderes com pontuações mais altas, sempre que a pontuação é atualizada. Para que os validadores cheguem a um consenso sobre o novo mapeamento, eles devem chegar a um consenso sobre a pontuação, assim alcançando um consenso sobre a história utilizada para derivar a pontuação.

No Shoal, o processamento em pipeline e a reputação do líder podem combinar-se naturalmente, uma vez que ambos utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após a concordância sobre o primeiro ponto âncora ordenado.

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

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

Não há 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 introduzem aumenta o número de estados internos que precisam ser geridos e observados, o que eleva a complexidade do processo de depuração e requer mais técnicas de observabilidade.

O tempo de espera também aumentará significativamente a latência, pois é muito importante configurá-los adequadamente e geralmente requer ajustes dinâmicos, uma vez que depende fortemente do ambiente ) rede (. Antes de passar para o próximo líder, o protocolo paga a penalidade total de latência do tempo de espera para o líder com falha. Portanto, as configurações de tempo de espera não podem ser excessivamente conservadoras, mas se o tempo de espera for muito curto, o protocolo pode ultrapassar bons líderes. Por exemplo, observamos que, em situações de alta carga, os líderes em Jolteon/Hotstuff ficam sobrecarregados e o tempo de espera já expirou antes que eles pudessem avançar.

Infelizmente, os protocolos de líder ) como Hotstuff e Jolteon ( necessitam essencialmente de uma Gota, para garantir que sempre que um líder falha, a colaboração.