Shoal framework: 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 timeouts em protocolos práticos determinísticos. No geral, em situações sem falhas, a latência do Bullshark melhorou em 40%, e em situações de falha melhorou em 80%.

Shoal é uma estrutura que, através de pipelines e da 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 DAG ao introduzir âncoras a cada rodada, enquanto a reputação do líder melhora ainda mais a latência ao garantir que as âncoras estejam associadas aos nós de validação mais rápidos. Além disso, a reputação do líder permite que o Shoal aproveite a construção de DAG assíncrona para eliminar timeouts em todos os cenários. Isso permite que o Shoal forneça a propriedade que chamamos de resposta universal, que inclui a resposta otimista normalmente necessária.

A nossa tecnologia é muito simples, envolvendo múltiplas instâncias do protocolo subjacente a serem executadas em sequência. Assim, quando instanciamos o Bullshark, obtemos um grupo de "tubarões" que estão a realizar uma corrida de estafetas.

Motivação

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 capacidade de processamento. Por exemplo, o Hotstuff implementado nas versões iniciais do Diem alcançou apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.

Os avanços recentes resultam da percepção de que a disseminação de dados é o principal gargalo baseado nos protocolos dos líderes, e pode beneficiar-se da paralelização. O sistema Narwhal separa a disseminação de dados da lógica de consenso central, propondo uma arquitetura onde todos os validadores disseminam dados ao mesmo tempo, enquanto o componente de consenso apenas ordena uma quantidade reduzida de metadados. O artigo do Narwhal reportou uma taxa de transferência de 160.000 TPS.

Anteriormente, apresentamos o Quorum Store, ou seja, como nossa implementação do Narwhal separa 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 rápido linear do Tendermint e as mudanças de vista no estilo PBFT, podendo reduzir 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. Apesar de separar a propagação de dados do consenso, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda é limitado.

Portanto, decidimos implementar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com zero custo de comunicação. Infelizmente, a estrutura DAG que suporta o alto throughput do Bullshark trouxe um custo de latência de 50%.

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

Background do DAG-BFT

Cada vértice no DAG do Narwhal está associado a uma rodada. Para entrar na rodada r, um 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 vistas locais do DAG em qualquer ponto no tempo.

Uma característica chave do DAG é a não ambiguidade: se dois nós de verificaçã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.

Permutação completa

É possível alcançar um consenso sobre a ordem total de todos os vértices no DAG sem custos de comunicação adicionais. 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 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, o pico do líder é chamado de ponto de ancoragem;

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

3. Ordenação da história causal: os validadores processam uma lista de âncoras ordenadas um a um, e para cada âncora, ordenam todos os vértices anteriormente desordenados em sua história causal de acordo com algumas regras determinísticas.

A chave para garantir a segurança é assegurar que, no passo (2), todos os nós de validação honestos compartilhem a mesma prefixo da lista de âncoras ordenadas criada. 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 a 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 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 aguardar a ordenação dos pontos de ancoragem. 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: 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 os pontos âncora rapidamente o suficiente, não será possível ordenar os pontos âncora (, portanto, serão pulados ), e todos os vértices não ordenados nas primeiras rodadas devem esperar que o próximo ponto âncora seja ordenado. Isso reduzirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o Bullshark usa um tempo limite para esperar pelo líder.

Estrutura Shoal

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 haja 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 seleção favoreça líderes rápidos.

Desafio

No contexto do protocolo DAG, a reputação da linha de produção e do líder é considerada um problema difícil, pelos seguintes motivos:

1. As linhas de montagem anteriores 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 escolhida dinamicamente com base no desempenho passado dos validadores para futuros líderes, a ideia do ponto âncora no Bullshark (. Embora a divergência na identidade do líder não comprometa a segurança desses protocolos, no Bullshark, isso pode levar a ordenações completamente diferentes, o que levanta o cerne da questão: a escolha dinâmica e determinística dos âncoras de rodada é necessária para resolver o consenso, e os validadores precisam chegar a um consenso sobre a história ordenada para escolher os futuros pontos âncora.

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.

![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(

Protocolo

Apesar dos desafios acima mencionados, 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 todos os validadores concordando com a percepção central do primeiro ponto de ancoragem ordenado, o Shoal combina sequencialmente várias instâncias Bullshark para processá-las em pipeline, fazendo com que ) o primeiro ponto de ancoragem ordenado seja o ponto de mudança das instâncias, e ( a história causal do ponto de ancoragem é utilizada para calcular a reputação do líder.

Linha de produção

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

Inicialmente, a Shoal lançou 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 concordam com este ponto de ancoragem. Assim, todos os validadores podem concordar de forma definitiva em reinterpretar o DAG a partir da rodada r+1. A Shoal simplesmente lançou uma nova instância do Bullshark na rodada r+1.

No melhor cenário, isso permite que o Shoal classifique um ponto de ancoragem em cada rodada. O ponto de ancoragem da primeira rodada é classificado pela primeira instância. Em seguida, o Shoal inicia uma nova instância na segunda rodada, que por sua vez tem um ponto de ancoragem, e esse ponto de ancoragem é classificado por essa instância, e então, outra nova instância classifica o ponto de ancoragem 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 ordenação Bullshark, pular pontos de ancoragem aumenta a latência. Nesse caso, a tecnologia de pipeline não pode ajudar, 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 é menos provável que líderes correspondentes sejam escolhidos no futuro para lidar com pontos de ancoragem perdidos, atribuindo uma pontuação a cada nó de validação com base no histórico recente de atividades 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 a baixas pontuações, pois podem falhar, ser lentos ou agir maliciosamente.

A sua filosofia é recalcular de forma determinística o mapeamento pré-definido F de cada rodada ao líder sempre que a pontuação for atualizada, favorecendo os líderes com pontuações mais altas. Para que os validadores cheguem a um consenso sobre o novo mapeamento, 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 da 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 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 executar uma nova instância do Bullshark usando a função de seleção de pontos de ancoragem atualizada F' a partir da r+1-ésima rodada.

![Explicação detalhada do框架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 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 eleva 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 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 penalização completa do tempo limite para o líder com falha. Portanto,