Análise do quadro Shoal: redução significativa da latência do Bullshark na Aptos

Aptos Labs recentemente resolveu dois problemas críticos no DAG BFT, Gota significativamente a latência, e pela primeira vez eliminou a necessidade de timeouts em protocolos de tempo real determinísticos. No geral, em condições sem falhas, a latência do Bullshark melhorou 40%, e em caso de falhas melhorou 80%.

Shoal é uma estrutura que melhora o protocolo de consenso baseado em Narwhal ( através de um mecanismo de pipeline e reputação do líder, como DAG-Rider, Tusk, Bullshark ). O pipeline reduz a latência de ordenação do 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 Shoal utilize a construção de DAG assíncrona para eliminar timeouts em todos os cenários. Isso confere ao Shoal uma responsividade universal, incluindo a responsividade otimista geralmente necessária.

A tecnologia é muito simples, envolvendo a execução sequencial de várias instâncias do protocolo subjacente. Usar a instância Bullshark é equivalente a um grupo de "tubarões" participando de uma corrida de revezamento.

Contexto e Motivação

Na busca por um alto desempenho da rede blockchain, a Gota da complexidade de comunicação sempre foi um foco de atenção. No entanto, esse método não trouxe um aumento significativo na taxa de transferência. Por exemplo, o Hotstuff implementado no início do Diem alcançou apenas 3500 TPS, muito abaixo da meta de mais de 100.000 TPS.

A recente quebra decorre da percepção de que a propagação de dados é o principal gargalo baseado em protocolos de liderança, 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, e o componente de consenso apenas ordena uma pequena quantidade de metadados. O artigo do Narwhal reporta uma taxa de transferência de até 160.000 TPS.

Aptos anteriormente apresentou o Quorum Store, que é a implementação Narwhal, separando a propagação de dados do consenso, para escalar o atual protocolo de consenso Jolteon. Jolteon combina o caminho rápido linear do Tendermint com mudanças de visão no estilo PBFT, podendo reduzir a latência do Hotstuff em 33%. No entanto, os protocolos de consenso baseados em líderes não conseguem aproveitar plenamente o potencial de throughput do Narwhal.

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

O framework Shoal visa reduzir significativamente a latência do Bullshark.

Contexto DAG-BFT

Em um Narwhal DAG, cada vértice está associado a uma rodada. Ao entrar na rodada r, o validador deve primeiro obter n-f vértices da 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 das principais propriedades do DAG é a não ambiguidade: se dois nós de validação têm o mesmo vértice v na visão local do DAG, então eles têm exatamente a mesma história causal de v.

Sequência geral

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

Todos os protocolos de consenso baseados em Narwhal têm a seguinte estrutura:

1. Ponto de ancoragem: a cada algumas rodadas há um líder previamente determinado, cujo pico é chamado de ponto de ancoragem.

2. Pontos de Ancoragem de Ordenação: os validadores determinam de forma independente, mas determinística, quais pontos de ancoragem ordenar e quais ignorar.

3. História causal ordenada: os validadores processam sequencialmente a lista de âncoras ordenadas, ordenando os vértices desordenados anteriores na história causal de cada âncora.

A chave da segurança é garantir que, no passo (2), todas as listas de pontos de ancoragem ordenadas criadas por nós validadores honestos compartilhem o mesmo prefixo. Shoal observou: todos os validadores concordaram com o primeiro ponto de ancoragem ordenado.

Bullshark latência

A latência do Bullshark depende do número de voltas entre os pontos âncora ordenados no DAG. Embora algumas versões de sincronização parcial do Bullshark tenham uma latência melhor do que as versões assíncronas, ainda estão longe do ideal.

Existem dois problemas principais:

1. Latência média de bloco: Em situações comuns, os vértices de ponto ímpar precisam de três rodadas, enquanto os vértices de ponto par não âncora precisam de quatro rodadas para serem ordenados.

2. Situação de falha de latência: Se um líder em determinada rodada não conseguir transmitir a âncora a tempo, resultando em a âncora não poder ser classificada e ser ignorada, os vértices não classificados das rodadas anteriores devem esperar pela classificação da próxima âncora. Isso reduz significativamente o desempenho da rede de replicação geográfica.

Estrutura Shoal

Shoal através de uma linha de montagem melhora Bullshark( ou qualquer protocolo BFT baseado em Narwhal), permitindo que haja um ponto de âncora em cada rodada, reduzindo a latência de todos os vértices não âncora no DAG para três rodadas. Shoal também introduz um mecanismo de reputação de líder sem custo no DAG, favorecendo a escolha de 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:

1. As tentativas anteriores de modificar a lógica central do Bullshark parecem ser essencialmente impossíveis.

2. A reputação do líder é introduzida no DiemBFT e formalizada no Carousel, selecionando dinamicamente futuros líderes com base no desempenho passado dos validadores ( âncora no Bullshark ). Embora a divergência de identidade do líder não viole a segurança, pode levar a uma ordenação completamente diferente no Bullshark.

Esses desafios resultaram no fato de que as implementações do Bullshark no ambiente de produção atual não suportam esses recursos.

protocolo

Shoal depende da capacidade de executar cálculos locais sobre DAG, permitindo a preservação e reinterpretacao das informações das rodadas anteriores. Com base na percepção de que todos os validadores concordam com o primeiro ponto âncora ordenado, Shoal combina sequencialmente múltiplas instâncias de Bullshark para processamento em pipeline, permitindo que:

1. O primeiro ponto âncora ordenado é o ponto de mudança da instância.
2. A história causal do ponto de âncora é usada para calcular a reputação dos líderes

linha de produção

V que mapeia as rodadas para os líderes. O Shoal executa instâncias do Bullshark em sequência, onde cada ponto de ancoragem de cada instância é previamente determinado pelo mapeamento F. Cada instância ordena um ponto de ancoragem, desencadeando a mudança para a próxima instância.

Shoal foi inicialmente lançado no primeiro estágio do DAG com a primeira instância do Bullshark, funcionando até a determinação do primeiro ponto âncora ordenado (, assumindo na rodada r ). Todos os validadores concordaram com esse ponto âncora, portanto, podem concordar de forma determinística em reinterpretar o DAG a partir da rodada r+1. Shoal inicia uma nova instância do Bullshark na rodada r+1.

Em um cenário ideal, isso permite que o Shoal classifique um ponto de ancoragem por rodada. O primeiro ponto de ancoragem é classificado pela primeira instância, e então o Shoal inicia uma nova instância na segunda rodada, classificando o ponto de ancoragem dessa rodada, e assim por diante.

Reputação do líder

Quando o processo de classificação Bullshark ignora os pontos de âncora, a latência aumenta. Nesse caso, a tecnologia de pipeline não pode ajudar, pois não é possível iniciar uma nova instância antes da classificação do ponto de âncora da instância anterior. O Shoal atribui uma pontuação a cada nó de validação através de um mecanismo de reputação, garantindo que líderes lentos correspondentes sejam escolhidos com menor probabilidade no futuro, com base no histórico de atividades recentes. Os validadores que respondem e participam do protocolo recebem altas pontuações, enquanto os que não o fazem recebem baixas pontuações.

Sempre que a pontuação é atualizada, recalcula-se de forma determinística o mapeamento predefinido F de rodadas para líderes, favorecendo líderes de alta pontuação. Para que os validadores entrem em consenso sobre o novo mapeamento, eles precisam entrar em consenso sobre a pontuação, alcançando assim consenso sobre a história utilizada para derivar a pontuação.

No Shoal, a linha de montagem e a reputação de liderança se combinam naturalmente, pois ambas usam a mesma tecnologia central: reinterpretar o DAG após chegar a um consenso sobre o primeiro ponto de ancoragem ordenado.

A única diferença é que, após a ordenação dos pontos de ancoragem da r-ésima rodada, o validador calcula um novo mapeamento F' a partir da r+1-ésima rodada, apenas com base na história causal dos pontos de ancoragem ordenados da r-ésima rodada. Em seguida, o nó validador começa a usar a função de seleção de pontos de ancoragem atualizada F' para executar uma nova instância Bullshark a partir da r+1-ésima rodada.

Eliminar latência

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, aumentando a complexidade da depuração e exigindo mais técnicas de observabilidade.

O tempo limite também aumenta significativamente a latência, pois é importante configurar adequadamente o tempo limite, que geralmente requer ajustes dinâmicos e depende fortemente do ambiente ( rede ). Antes de mudar para o próximo líder, o protocolo aplicará uma penalização completa pela latência do líder com falha. Portanto, a configuração do tempo limite não pode ser excessivamente conservadora, mas se for muito curta, o protocolo pode ignorar bons líderes.

Infelizmente, os protocolos baseados em líderes ( como Hotstuff e Jolteon) essencialmente requerem Gota, para garantir que o protocolo avance sempre que um líder falhar. Sem Gota, mesmo um líder que falhou pode parar o protocolo para sempre. Como não é possível distinguir entre líderes com falhas e lentos durante o período assíncrono, Gota pode levar os nós de validação a rotacionar todos os líderes sem atividade de consenso.

No Bullshark, o tempo limite é usado para a construção do DAG, para garantir que durante a sincronização os líderes honestos adicionem pontos âncora ao DAG rapidamente para que possam ser ordenados.

A Shoal observou que a construção do DAG fornece um "relógio" para estimar a velocidade da rede. Na ausência de pausas, enquanto n-f validadores honestos continuarem a adicionar vértices ao DAG, as rodadas continuarão a avançar. Embora o Bullshark possa não conseguir classificar ( a velocidade da rede devido a problemas de liderança ), o DAG ainda cresce à velocidade da rede, apesar de alguns líderes terem problemas ou a rede estar assíncrona. No final, quando líderes sem falhas transmitirem âncoras rapidamente o suficiente, toda a história causal das âncoras será classificada.

Em Shoal, evitar timeouts está intimamente relacionado à reputação do líder. Esperar repetidamente por líderes lentos aumentará a latência, e o mecanismo de reputação do líder exclui validadores lentos de serem escolhidos como líderes. Desta forma, o sistema utiliza nós de validação rápidos para operar a velocidade da rede em todos os cenários do mundo real.

É importante notar que o resultado de impossibilidade do FLP indica que não há um protocolo de consenso determinístico que possa evitar a latência. O Shoal não pode contornar esse resultado, pois existe um cronograma de eventos adversos teóricos que pode impedir que todas as âncoras sejam ordenadas. Em vez disso, após um número configurável de âncoras puladas continuamente, o Shoal retornará à latência. Na prática, essa situação é extremamente improvável de ocorrer.

resposta universal

O artigo Hotstuff popularizou o conceito de resposta otimista, embora não tenha sido formalmente definido, mas intuitivamente significa que o protocolo pode operar a velocidade da rede sob boas condições ( com líderes rápidos e redes sincronizadas ).

Shoal oferece propriedades melhores, chamadas de responsividade universal. Especificamente, em comparação com o Hotstuff, mesmo que o líder falhe em um número contínuo de rodadas configuráveis ou a rede experimente períodos assíncronos, Shoal continuará a operar na velocidade da rede.

A responsividade geral oferece garantias de progresso significativamente melhores durante períodos assíncronos e quando o líder falha. Durante a sincronização com líderes lentos, essas propriedades não são comparáveis, pois dependem de quão lento o líder é. No entanto, tendo em conta a reputação do líder, líderes lentos em Shoal devem aparecer raramente.

Avaliação

Aptos implementou Bullshark e Shoal sobre o Quorum Store no Narwhal. Abaixo estão alguns destaques da avaliação:

Primeiro, para a apresentação