Estrutura Shoal: como Gota a latência do Bullshark do Aptos

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

Shoal é uma estrutura que melhora qualquer protocolo de consenso baseado em Narwhal (, como DAG-Rider, Tusk, Bullshark ), através de processamento em pipeline e um mecanismo de reputação do líder. O pipeline reduz a latência de ordenação do 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 aos nós de validação mais rápidos. Além disso, a reputação do líder permite que o Shoal utilize construções de DAG assíncronas para eliminar timeouts em todos os cenários. Isso permite que o Shoal ofereça uma propriedade que chamamos de resposta universal, que contém a resposta otimista normalmente necessária.

A nossa tecnologia é muito simples, envolve a execução sequencial de várias instâncias do protocolo subjacente. Portanto, quando instanciamos com Bullshark, obtemos um grupo de "tubarões" a participar numa corrida de estafetas.

Motivação

Na busca por alto desempenho em redes de blockchain, as pessoas sempre se concentraram na latência da complexidade da comunicação. 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 alcançou apenas 3500 TPS, muito abaixo da nossa meta de 100.000+ TPS.

Mas a recente quebra se deve à percepção de que a propagação de dados é o principal gargalo baseado no protocolo de líderes e que pode 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 documento do Narwhal reportou uma taxa de transferência de 160.000 TPS.

No artigo anterior, apresentamos o Quorum Store. A nossa implementação do Narwhal separa a propagação de dados do consenso, e como a utilizamos 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 as mudanças de vista ao estilo PBFT, podendo reduzir a latência do Hotstuff em 33%. No entanto, é claro 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 esteja separada do consenso, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda está limitado.

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

Este artigo apresentará como o Shoal consegue Gota significativamente a latência do Bullshark.

fundo DAG-BFT

Vamos primeiro entender o contexto relevante. Para uma descrição detalhada sobre Narwhal e Bullshark, consulte o artigo DAG meets 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 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 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.

sequência completa

É 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 atuais protocolos de consenso baseados no Narwhal possuem a seguinte estrutura:

1. Ponto de âncora reservado: a cada algumas rodadas (, como nas duas rodadas ) do Bullshark, haverá um líder pré-determinado, e o ponto alto do líder é chamado de ponto de âncora;

2. Ponto de ancoragem de ordenação: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem ordenar e quais ignorar;

3. ordenação da história causal: os validadores processam individualmente 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 algumas 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, de modo 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 voltas entre os pontos âncora ordenados no DAG. Embora a versão sincronizada 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: latência média de bloco. No Bullshark, cada rodada par tem um ponto âncora, e o vértice de cada rodada ímpar é interpretado como uma votação. Em situações comuns, são necessárias duas rodadas de DAG para ordenar os pontos âncoras; no entanto, os vértices na história causal do ponto âncora precisam de mais rodadas para esperar que o ponto âncora seja ordenado. Em situações comuns, os vértices na rodada ímpar precisam de três rodadas, enquanto os vértices não âncora na rodada par precisam de quatro rodadas.

Pergunta 2: latência de casos de falha, 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 ancoragem rapidamente o suficiente, não será possível ordenar o ponto de ancoragem (, portanto será ignorado ). Assim, todos os vértices não ordenados nas rodadas anteriores devem aguardar o próximo ponto de ancoragem ser ordenado. Isso reduzirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark usa um tempo limite para aguardar o líder.

Shoal estrutura

Shoal resolveu esses dois problemas de latência, melhorando o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de pipelines, permitindo que houvesse um ponto de âncora em 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, o que faz com que a escolha favoreça líderes rápidos.

desafio

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

1. Tentativas anteriores de processamento em linha de montagem 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 escolher futuros líderes. A ideia dos âncoras no Bullshark ( é que, embora a divergência na identidade do líder não viole a segurança desses protocolos, no Bullshark, isso pode levar a ordenações completamente diferentes. Isso levanta o cerne da questão, que é que a seleção dinâmica e determinística das âncoras de rodada é necessária para resolver o consenso, e os validadores precisam chegar a um consenso sobre a história ordenada para escolher as âncoras futuras.

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 acima, como diz o ditado, a solução está muitas vezes escondida na simplicidade.

No Shoal, confiamos na capacidade de realizar cálculos locais sobre o DAG e implementamos a capacidade de armazenar e reinterpretar 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 ### o primeiro ponto de ancoragem ordenado o ponto de troca das instâncias, bem como ( a história causal do ponto de ancoragem usada para calcular a reputação do líder.

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

) processamento em linha

V que mapeia as rodadas para os líderes. Shoal executa instâncias do Bullshark uma após a outra, de forma que para cada instância, a âncora é previamente determinada pelo mapeamento F. Cada instância encomenda uma âncora, o que desencadeia a transição para a próxima instância.

No início, o Shoal iniciou a primeira instância do Bullshark na primeira rodada do DAG e a executou até determinar o primeiro ponto de âncora ordenado, como na rodada r. Todos os validadores concordaram com este ponto de âncora. 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 cenário, isso permite que o Shoal encomende 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 si só tem um ponto de âncora, que é ordenado por esse instante, e então, outro novo instante 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, a latência aumenta ao pular âncoras. Nesse caso, a técnica de processamento em pipeline não consegue ajudar, pois não é possível iniciar uma nova instância antes de pedir a âncora da instância anterior. O Shoal assegura que é menos provável que líderes correspondentes sejam escolhidos para lidar com âncoras perdidas no futuro, atribuindo uma pontuação a cada nó de validação com base no histórico de atividades recentes de cada nó de validação, através do uso de um mecanismo de reputação. 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 com falhas, lentos ou agindo de má fé.

A sua filosofia é recalcular de forma determinística o mapeamento pré-definido F, que vai do turno ao líder, sempre que a pontuação é atualizada, favorecendo os líderes com pontuações mais altas. Para que os validadores cheguem a um consenso sobre o novo mapeamento, eles devem concordar 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 utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após alcançar um consenso sobre o primeiro ponto âncora ordenado.

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

Não há mais tempo limite.

O tempo limite desempenha um papel crucial em todas as implementações BFT de sincronização determinística baseadas em líder. 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 ( da rede ). Antes de se transferir para o próximo líder, o protocolo pagará a penalização total 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 ignorar bons líderes. Por exemplo, observamos que, em situações de alta carga, Jolt