Quadro Shoal: Como reduzir a latência do Bullshark na Aptos?

Resumo

Aptos labs resolveu dois importantes problemas abertos no DAG BFT, reduzindo drasticamente a latência e eliminando pela primeira vez a necessidade de pausas em protocolos práticos determinísticos. No total, 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 e Bullshark ), através de pipelines e da reputação dos líderes. O pipeline reduz a latência de ordenação do DAG ao introduzir um ponto âncora a cada rodada, enquanto a reputação dos líderes 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 dos líderes permite que o Shoal utilize a construção de DAG assíncrona 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.

Esta tecnologia é muito simples, envolve executar múltiplas instâncias do protocolo subjacente uma após a outra em sequência. Assim, quando instanciamos com o Bullshark, obtemos um grupo de "tubarões" que estão numa corrida de revezamento.

Motivação

Na busca por alto desempenho em redes de blockchain, as pessoas têm se concentrado em reduzir a 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 atingiu apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.

A recente descoberta deriva do reconhecimento de que a propagação de dados é o principal gargalo baseado nos protocolos dos líderes e que pode beneficiar da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central e propõe uma arquitetura onde todos os validadores propagam dados simultaneamente, enquanto o componente de consenso apenas ordena uma quantidade reduzida de metadados. O artigo do Narwhal relatou uma taxa de transferência de 160.000 TPS.

Anteriormente, foi apresentada a Quorum Store - Narwhal, que implementa a separação entre a propagação de dados e o consenso, assim como a forma de utilizá-la para escalar o atual protocolo de consenso Jolteon. Jolteon é um protocolo baseado em líder, que combina o caminho rápido linear do Tendermint e a mudança de vista no 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. Apesar de separar a propagação de dados do consenso, à medida que o throughput aumenta, os líderes do Hotstuff/Jolteon ainda enfrentam limitações.

Portanto, foi decidido implementar o Bullshark em cima do Narwhal DAG, um protocolo de consenso sem custos 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 conseguiu reduzir significativamente a latência do Bullshark.

Contexto 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 a qualquer momento.

Uma das propriedades chave do DAG não é ambígua: se dois nós de validação tiverem o mesmo vértice v em suas visões locais do DAG, então eles têm exatamente a mesma história causal de v.

Totalidade

É possível alcançar consenso sobre a ordem total dos vértices em um 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 em Narwhal existentes têm a seguinte estrutura:

1. Ponto de ancoragem: a cada algumas rodadas haverá um líder predeterminado, e o pico do líder é chamado de ponto de ancoragem;

2. Ponto de ancoragem ordenado: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem encomendar e quais pular;

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

A chave para garantir a segurança é assegurar que, na etapa 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, as seguintes observações são feitas sobre todos os protocolos mencionados acima:

Todos os validadores concordam com o primeiro ponto de ancoragem ordenado.

Bullshark atraso

A latência do Bullshark depende do número de voltas entre os âncoras ordenadas no DAG. Embora a versão de sincronização parcial do Bullshark seja mais prática e tenha melhor latência do que a versão assíncrona, ainda assim está longe de ser a ideal.

Pergunta 1: Atraso médio de bloco. No Bullshark, cada rodada par tem um ponto de ancoragem, enquanto os vértices da rodada ímpar são interpretados como votos. Na maioria dos casos, 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. Nos casos 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: Atraso de casos de falha, a análise de atraso acima se aplica a situações sem falha. Por outro lado, se o líder de uma rodada não conseguir transmitir rapidamente o ponto de âncora, não será possível ordenar o ponto de âncora (, portanto, ele será ignorado ). Assim, todos os vértices não ordenados nas rodadas anteriores devem aguardar que o próximo ponto de âncora seja ordenado. Isso diminuirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o tempo limite do Bullshark é utilizado para aguardar o líder.

Estrutura Shoal

Shoal resolveu esses dois problemas de latência, aumentando o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de um pipeline, permitindo que haja um ponto de ancoragem 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 parecia, na essência, impossível.

2. A reputação dos líderes é introduzida no DiemBFT e formalizada no Carousel, sendo escolhidos dinamicamente os futuros líderes com base no desempenho passado dos validadores, a ideia dos âncoras no Bullshark (. Embora a divergência na identidade dos líderes não comprometa a segurança desses protocolos, no Bullshark, isso pode levar a uma ordenação completamente diferente, o que levanta o cerne da questão, ou seja, que a escolha dinâmica e determinística das âncoras do ciclo é necessária para resolver o consenso, e os validadores precisam chegar a um acordo sobre a história ordenada para escolher as futuras âncoras.

Como evidência da dificuldade do problema, a implementação do Bullshark, incluindo a implementação atualmente 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 por trás do simples.

No Shoal, aproveitando a capacidade de realizar cálculos locais sobre o DAG, foi implementada 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 âncora ordenado, o Shoal combina sequencialmente várias instâncias de Bullshark para processá-las em pipeline, tornando ) o primeiro ponto de âncora ordenado o ponto de mudança das instâncias, e ( a história causal do ponto de âncora utilizada para calcular a reputação do líder.

Linha de Montagem

V que mapeia as rodadas para os líderes. Shoal executa uma instância do Bullshark de cada vez, de modo que para cada instância, o âncora é previamente determinado pelo mapeamento F. Cada instância encomenda um âncora, o que desencadeia a mudança 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 âncora ordenado, como na rodada r. Todos os validadores concordam com esse ponto âncora. Assim, todos os validadores podem concordar de maneira definitiva 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 encomende uma âncora em cada rodada. A primeira âncora é ordenada de acordo com a primeira instância. Em seguida, o Shoal inicia uma nova instância na segunda rodada, que tem sua própria âncora, ordenada por essa instância, e então, outra nova instância encomenda uma â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 o período de ordenação do Bullshark, pular pontos âncora aumenta a latência. Nesse caso, a tecnologia de pipeline não pode ajudar, pois não é possível iniciar uma nova instância antes de encomendar o ponto âncora anterior. O Shoal garante que é improvável que os líderes correspondentes sejam escolhidos para lidar com pontos â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 uma alta pontuação; caso contrário, os nós de validação serão atribuídos uma pontuação baixa, pois podem estar em colapso, lentos ou agindo de má-fé.

A ideia é recalcular de forma determinística o mapeamento predefinido F do turno ao líder sempre que a pontuação for atualizada, favorecendo 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, a linha de montagem 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 consenso no primeiro ponto de ancoragem ordenado.

Na verdade, a única diferença é que, após classificar os âncoras 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 âncoras ordenados na r-ésima rodada. Em seguida, os nós validadores começam a usar a função de seleção de âncoras atualizada F' para executar uma nova instância do Bullshark a partir da (r+1)-ésima rodada.

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

Sem 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 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