Estrutura Shoal: otimização da latência do consenso Bullshark no Aptos

Aptos Labs resolveu recentemente dois problemas abertos importantes no DAG BFT, reduzindo significativamente a latência e eliminando pela primeira vez a necessidade de timeouts no protocolo real determinístico. 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, através do processamento em pipeline e do mecanismo de reputação dos líderes, melhora o protocolo de consenso baseado em Narwhal (, como DAG-Rider, Tusk, Bullshark ). O pipeline reduz a latência de ordenação do DAG ao introduzir um ponto de âncora a cada rodada, e a reputação dos líderes melhora ainda mais o problema de latência ao garantir que os pontos de âncora estejam associados aos nós de validação mais rápidos. Além disso, a reputação dos líderes permite que o Shoal utilize a construção de DAGs assíncronos para eliminar os timeouts em todos os cenários. Isso permite que o Shoal ofereça características de resposta universal, incluindo a resposta otimista normalmente necessária.

A tecnologia do Shoal é relativamente simples, consistindo principalmente em executar múltiplas instâncias do protocolo subjacente em sequência, uma após a outra. Quando instanciado com Bullshark, forma-se um grupo de "tubarões" que estão a fazer uma corrida de estafetas.

Contexto e Motivação

Na busca por um alto desempenho na rede de blockchain, a redução da complexidade da comunicação sempre foi um ponto focal. No entanto, essa abordagem não resultou em um aumento significativo na taxa de transferência. Por exemplo, o Hotstuff implementado nas versões iniciais do Diem atingiu apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.

A recente quebra de paradigma resulta do reconhecimento de que a propagação de dados é o principal gargalo baseado em acordos entre líderes, podendo beneficiar-se da paralelização. O sistema Narwhal separa a propagação de dados da lógica central de consenso, 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 capacidade de 160.000 TPS.

Aptos apresentou anteriormente o Quorum Store, que é a implementação do Narwhal, separando a propagação de dados do consenso, e como usá-lo para escalar o protocolo de consenso atual Jolteon. Jolteon é um protocolo baseado em líder que combina o caminho linear rápido do Tendermint e a mudança de visão ao estilo PBFT, reduzindo 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. Apesar de separar a propagação de dados do consenso, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda é limitado.

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

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 momento.

Uma propriedade chave do DAG é a não ambiguidade: se dois nós de validaçã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 baseados no Narwhal existentes têm a seguinte estrutura:

1. Ponto de ancoragem: A cada algumas rodadas (, por exemplo, em Bullshark, a cada duas rodadas ) haverá um líder pré-determinado, o pico do líder é chamado de ponto de ancoragem.

2. Pontos de ancoragem de ordenação: 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 uma lista de âncoras ordenadas um após o outro, ordenando todos os vértices anteriores desordenados em sua história causal para cada âncora, 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 ordenadas, para que todas as listas compartilhem o mesmo prefixo. No Shoal, as seguintes observações são feitas sobre todos os protocolos acima mencionados: todos os validadores concordam com a primeira âncora ordenada.

Bullshark latência

A latência do Bullshark depende do número de voltas entre os pontos de âncora 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, ainda está longe de ser a ideal.

Existem dois problemas principais:

1. Latência média do bloco: No Bullshark, cada rodada par tem um ponto de ancoragem, e o vértice de cada rodada ímpar é interpretado como um voto. Em situações comuns, são necessárias duas rodadas do DAG para classificar o ponto de ancoragem; no entanto, os vértices na história causal do ponto de ancoragem necessitam de mais rodadas para aguardar a classificação do ponto de ancoragem. Em situações comuns, os vértices na rodada ímpar necessitam de três rodadas, enquanto os vértices não ancorados na rodada par necessitam de quatro rodadas.

2. Casos de falha de latência: se um líder de uma rodada não conseguir transmitir rapidamente o ponto de âncora, o ponto de âncora não poderá ser ordenado ( e, portanto, será ignorado ). Todos os vértices não ordenados das rodadas anteriores devem aguardar que o próximo ponto de âncora seja ordenado. Isso reduzirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark utiliza timeouts 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 que haja 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 de custo zero no DAG, fazendo com que a seleção 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, pelas seguintes razões:

1. As tentativas anteriores de processamento em linha de montagem de modificar a lógica central do Bullshark parecem ser, em essência, impossíveis.

2. A reputação dos líderes é introduzida no DiemBFT e formalizada no Carousel, sendo selecionados dinamicamente os futuros líderes com base no desempenho passado dos validadores, a ideia do âncora no Bullshark (. Embora as divergências na identidade dos líderes não violem a segurança destes protocolos, no Bullshark, isso pode levar a ordenações completamente diferentes. Isso leva ao cerne da questão, que a seleção dinâmica e determinística do âncora da rodada é necessária para resolver o consenso, e os validadores precisam concordar sobre o histórico ordenado para escolher os futuros âncoras.

Protocolo

Apesar dos desafios mencionados, a solução está escondida na simplicidade. No Shoal, é aproveitada a capacidade de executar cálculos locais em DAG, permitindo a preservação e reinterpretação das informações das primeiras rodadas. Com a compreensã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, permitindo que:

1. O primeiro ponto de ancoragem ordenado é o ponto de mudança do exemplo.
2. A história causal do ponto de ancoragem é utilizada para calcular a reputação dos líderes

) processamento em pipeline

V que mapeia as rodadas para os líderes. Shoal executa uma instância do Bullshark de cada vez, assim para cada instância, o âncora é previamente determinado pelo mapeamento F. Cada instância ordena um âncora, o que desencadeia a transição para a próxima instância.

Inicialmente, o Shoal iniciou a primeira instância do Bullshark na primeira rodada do DAG e a executou até determinar o primeiro ponto de ancoragem ordenado, como na rodada r. Todos os validadores concordaram com este ponto de ancoragem. Portanto, todos os validadores podem concordar de forma confiável em reinterpretar o DAG a partir da rodada r+1. O Shoal apenas iniciou uma nova instância do Bullshark na rodada r+1.

No melhor dos casos, isso permite que o Shoal ordene um âncora em cada rodada. O ponto de âncora da primeira rodada é ordenado pelo primeiro instante. Em seguida, o Shoal inicia um novo instante na segunda rodada, que por sua vez tem um ponto de âncora, que é ordenado por esse instante, e então, outro novo instante ordena o ponto de â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-0b0928cb6240e994c1514c75e080a4b2.webp(

) Reputação do Líder

Durante a ordenação do Bullshark, quando os pontos de ancoragem são ignorados, a latência aumenta. Nesses casos, a técnica de processamento em pipeline é impotente, pois não é possível iniciar novas instâncias antes que o ponto de ancoragem da instância anterior seja ordenado. O Shoal garante que os líderes correspondentes que lidam com os pontos de ancoragem perdidos sejam menos prováveis de serem escolhidos no futuro, atribuindo uma pontuação a cada nó de validação com base na história da atividade recente de cada nó de validação, usando um mecanismo de reputação. Os validadores que respondem e participam do protocolo receberão pontuações altas; caso contrário, os nós de validação receberão pontuações baixas, pois podem estar em colapso, lentos ou agindo de forma maliciosa.

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

No Shoal, o processamento em pipeline e a liderança de reputação podem se combinar naturalmente, uma vez que ambos utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após alcançar consenso sobre o primeiro ponto âncora ordenado.

Na verdade, a única diferença é que, após a ordenação dos pontos âncora na r-ésima rodada, os validadores apenas precisam 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. Depois, os nós validadores 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-859e732e16c3eee0e2c93422474debc2.webp(

) Não é necessário tempo extra

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 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 aplicará uma penalização completa de latência de tempo de espera ao líder com falhas. Portanto, as configurações de tempo de espera não podem ser muito conservadoras, mas se o tempo de espera for muito curto, o protocolo pode pular bons líderes.

Infelizmente, protocolos baseados em líderes ), como Hotstuff e Jolteon (, essencialmente exigem latência para garantir que o protocolo avance sempre que um líder falhe. Sem latência, até mesmo um líder que falhou pode interromper o protocolo para sempre. Como não é possível distinguir entre um líder com falha e um líder lento durante períodos assíncronos, a latência pode levar os nós de validação a ver mudanças em todos os líderes sem atividade de consenso.

No Bullshark, o tempo limite é utilizado para a construção do DAG, a fim de garantir que durante a sincronização, líderes honestos adicionem pontos de ancoragem ao DA.