Framework Shoal: como reduzir a latência do Bullshark na Aptos
Visão Geral
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 determinísticos. No geral, melhorou a latência do Bullshark em 40% em condições sem falhas e em 80% em condições de falha.
Shoal é um framework que melhora o protocolo de consenso baseado em Narwhal ( através de pipeline e reputação do líder, como o DAG-Rider, Tusk, Bullshark ). O pipeline reduz a latência de ordenação do DAG ao introduzir um ponto âncora a cada rodada, enquanto a reputação do líder melhora ainda mais a latência ao garantir que o ponto âncora esteja associado ao nó de validação mais rápido. Além disso, a reputação do líder permite que Shoal aproveite a construção de DAG assíncrona para eliminar os timeouts em todos os cenários. Isso permite que Shoal ofereça uma propriedade que chamamos de resposta universal, que contém a resposta otimista geralmente necessária.
A tecnologia é muito simples, envolvendo a execução de várias instâncias do protocolo subjacente uma após a outra. Portanto, quando instanciado com Bullshark, obtemos um grupo de "tubarões" que estão em uma corrida de revezamento.
Motivação
Na busca por alto desempenho em redes de blockchain, as pessoas sempre se concentraram na redução 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 meta de 100k+ TPS.
A recente quebra de paradigma origina-se da percepção de que a propagação de dados é o principal gargalo baseado no protocolo dos líderes, podendo beneficiar-se da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central, propondo uma arquitetura em que todos os validadores propagam dados simultaneamente, enquanto o componente de consenso apenas ordena uma quantidade reduzida de metadados. O artigo do Narwhal reporta uma capacidade de 160.000 TPS.
Foi anteriormente apresentada a Quorum Store, que é a implementação do Narwhal que separa a propagação de dados do consenso, e como utilizá-la 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 a mudança de vista ao 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. Embora a propagação de dados e o consenso estejam separados, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda está limitado.
Portanto, decidimos implantar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com zero custo de comunicação. Infelizmente, em comparação com o Jolteon, a estrutura DAG que suporta o Bullshark de alta taxa de transferência traz um custo de latência de 50%.
Este artigo apresenta como a Shoal consegue reduzir significativamente a latência do Bullshark.
Contexto 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 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 característica chave do DAG 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 histórias causais de v completamente idênticas.
Ordem Total
É possível chegar a um consenso sobre a ordem total de todos os vértices no DAG sem custos de comunicação adicionais. 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 protocolos de consenso baseados em Narwhal existentes possuem a seguinte estrutura:
Ponto de ancoragem: A cada algumas rodadas haverá um líder previamente determinado, e o pico do líder é chamado de ponto de ancoragem;
Pontos de ancoragem de ordenação: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem encomendar e quais pular;
História causal ordenada: os validadores processam um a um a sua lista de âncoras ordenadas e ordenam todos os vértices anteriores desordenados na história causal de cada âncora.
A chave para satisfazer a segurança é garantir 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 de âncora ordenado.
Bullshark latência
A latência do Bullshark depende do número de voltas entre os âncoras ordenadas 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.
Questão 1: Latência média de bloco. No Bullshark, cada rodada par tem um ponto âncora, e o vértice da rodada ímpar é interpretado como um voto. Em situações comuns, são necessárias duas rodadas de DAG para ordenar os pontos âncora, 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.
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 rapidamente o ponto âncora, não será possível ordenar o ponto âncora ( e, portanto, será ignorado ), assim, todos os vértices não ordenados das rodadas anteriores devem aguardar o próximo ponto âncora ser ordenado. Isso reduzirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o tempo limite do Bullshark é usado para aguardar o líder.
Estrutura Shoal
A Shoal melhorou o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de pipelines, 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. A 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 pipeline e a reputação do líder são consideradas questões difíceis, pelos seguintes motivos:
As linhas de montagem anteriores tentaram modificar a lógica central do Bullshark, mas isso parece ser essencialmente impossível.
A reputação do líder é introduzida no DiemBFT e formalizada no Carousel, sendo selecionados dinamicamente futuros líderes com base no desempenho passado dos validadores, a ideia do âncora no Bullshark (. Embora a divergência na identidade do líder não viole 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, 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 o futuro âncora.
Como evidência da dificuldade do problema, a implementação do Bullshark ) não suporta essas características, incluindo a implementação atual no ambiente de produção (.
No Shoal, contamos com a capacidade de executar cálculos locais sobre o DAG e implementamos a capacidade de armazenar e reinterpretar as informações das rodadas anteriores. Com todos os validadores concordando com a visão central do primeiro ponto de ancoragem ordenado, o Shoal combina sequencialmente várias instâncias de Bullshark para processá-las em pipeline, tornando )1( o primeiro ponto de ancoragem ordenado o ponto de troca das instâncias, bem como )2( a história causal do ponto de ancoragem usada para calcular a reputação do líder.
Linha de Produção
V que mapeia as rodadas para os líderes. O Shoal executa instâncias do Bullshark uma após a outra, de forma 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.
Inicialmente, 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 concordaram com este ponto âncora. Assim, todos os validadores podem concordar com segurança 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. Os pontos de âncora da primeira rodada são ordenados pelo primeiro instante. Em seguida, o Shoal inicia um novo instante na segunda rodada, que tem um ponto de âncora, que é ordenado por esse instante, e então, outro novo instante encomenda 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-9f789cb669f6fcc244ea7ff7648e48b4.webp(
Reputação do Líder
Durante a ordenação Bullshark, ao pular pontos de ancoragem, a latência aumenta. Nesse caso, a tecnologia de pipeline não pode ajudar, pois uma nova instância não pode ser iniciada até que a instância anterior tenha encomendado os pontos de ancoragem. O Shoal garante que é menos provável que os líderes correspondentes sejam escolhidos para lidar com pontos de ancoragem perdidos 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, usando 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 receberão baixas pontuações, pois podem estar inoperantes, lentos ou agindo de má fé.
A sua filosofia é recalcular de forma determinística o mapeamento pré-definido F 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 alcançar um consenso sobre a pontuação, de modo a alcançar 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, pois ambas usam 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 ordenar os âncoras na r-ésima rodada, os validadores só 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 de validação 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 quadro Shoal: como reduzir a latência do Bullshark no 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 de BFT determinísticas 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 limite também aumentará significativamente a latência, pois é muito importante configurá-los adequadamente e geralmente é necessário ajustá-los dinamicamente, uma vez que depende muito do ambiente ) rede (. Antes de passar para o próximo líder, o protocolo pagará a penalização total do tempo limite para o líder com falha. Portanto, as configurações de tempo limite não podem ser excessivamente conservadoras, mas se o tempo limite for muito curto, o protocolo pode ignorar bons líderes. Por exemplo, observamos
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
O framework Shoal reduz significativamente a latência de consenso do Bullshark na Aptos, melhorando em 40%-80%.
Framework Shoal: como reduzir a latência do Bullshark na Aptos
Visão Geral
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 determinísticos. No geral, melhorou a latência do Bullshark em 40% em condições sem falhas e em 80% em condições de falha.
Shoal é um framework que melhora o protocolo de consenso baseado em Narwhal ( através de pipeline e reputação do líder, como o DAG-Rider, Tusk, Bullshark ). O pipeline reduz a latência de ordenação do DAG ao introduzir um ponto âncora a cada rodada, enquanto a reputação do líder melhora ainda mais a latência ao garantir que o ponto âncora esteja associado ao nó de validação mais rápido. Além disso, a reputação do líder permite que Shoal aproveite a construção de DAG assíncrona para eliminar os timeouts em todos os cenários. Isso permite que Shoal ofereça uma propriedade que chamamos de resposta universal, que contém a resposta otimista geralmente necessária.
A tecnologia é muito simples, envolvendo a execução de várias instâncias do protocolo subjacente uma após a outra. Portanto, quando instanciado com Bullshark, obtemos um grupo de "tubarões" que estão em uma corrida de revezamento.
Motivação
Na busca por alto desempenho em redes de blockchain, as pessoas sempre se concentraram na redução 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 meta de 100k+ TPS.
A recente quebra de paradigma origina-se da percepção de que a propagação de dados é o principal gargalo baseado no protocolo dos líderes, podendo beneficiar-se da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central, propondo uma arquitetura em que todos os validadores propagam dados simultaneamente, enquanto o componente de consenso apenas ordena uma quantidade reduzida de metadados. O artigo do Narwhal reporta uma capacidade de 160.000 TPS.
Foi anteriormente apresentada a Quorum Store, que é a implementação do Narwhal que separa a propagação de dados do consenso, e como utilizá-la 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 a mudança de vista ao 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. Embora a propagação de dados e o consenso estejam separados, à medida que o throughput aumenta, o líder do Hotstuff/Jolteon ainda está limitado.
Portanto, decidimos implantar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com zero custo de comunicação. Infelizmente, em comparação com o Jolteon, a estrutura DAG que suporta o Bullshark de alta taxa de transferência traz um custo de latência de 50%.
Este artigo apresenta como a Shoal consegue reduzir significativamente a latência do Bullshark.
Contexto 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 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 característica chave do DAG 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 histórias causais de v completamente idênticas.
Ordem Total
É possível chegar a um consenso sobre a ordem total de todos os vértices no DAG sem custos de comunicação adicionais. 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 protocolos de consenso baseados em Narwhal existentes possuem a seguinte estrutura:
Ponto de ancoragem: A cada algumas rodadas haverá um líder previamente determinado, e o pico do líder é chamado de ponto de ancoragem;
Pontos de ancoragem de ordenação: os validadores decidem de forma independente, mas determinística, quais pontos de ancoragem encomendar e quais pular;
História causal ordenada: os validadores processam um a um a sua lista de âncoras ordenadas e ordenam todos os vértices anteriores desordenados na história causal de cada âncora.
A chave para satisfazer a segurança é garantir 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 de âncora ordenado.
Bullshark latência
A latência do Bullshark depende do número de voltas entre os âncoras ordenadas 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.
Questão 1: Latência média de bloco. No Bullshark, cada rodada par tem um ponto âncora, e o vértice da rodada ímpar é interpretado como um voto. Em situações comuns, são necessárias duas rodadas de DAG para ordenar os pontos âncora, 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.
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 rapidamente o ponto âncora, não será possível ordenar o ponto âncora ( e, portanto, será ignorado ), assim, todos os vértices não ordenados das rodadas anteriores devem aguardar o próximo ponto âncora ser ordenado. Isso reduzirá significativamente o desempenho da rede de replicação geográfica, especialmente porque o tempo limite do Bullshark é usado para aguardar o líder.
Estrutura Shoal
A Shoal melhorou o Bullshark( ou qualquer outro protocolo BFT baseado em Narwhal) através de pipelines, 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. A 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 pipeline e a reputação do líder são consideradas questões difíceis, pelos seguintes motivos:
As linhas de montagem anteriores tentaram modificar a lógica central do Bullshark, mas isso parece ser essencialmente impossível.
A reputação do líder é introduzida no DiemBFT e formalizada no Carousel, sendo selecionados dinamicamente futuros líderes com base no desempenho passado dos validadores, a ideia do âncora no Bullshark (. Embora a divergência na identidade do líder não viole 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, 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 o futuro âncora.
Como evidência da dificuldade do problema, a implementação do Bullshark ) não suporta essas características, incluindo a implementação atual no ambiente de produção (.
![万字详解Shoal框架：如何减少Aptos上的Bullshark latência？])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(
Protocolo
No Shoal, contamos com a capacidade de executar cálculos locais sobre o DAG e implementamos a capacidade de armazenar e reinterpretar as informações das rodadas anteriores. Com todos os validadores concordando com a visão central do primeiro ponto de ancoragem ordenado, o Shoal combina sequencialmente várias instâncias de Bullshark para processá-las em pipeline, tornando )1( o primeiro ponto de ancoragem ordenado o ponto de troca das instâncias, bem como )2( a história causal do ponto de ancoragem usada para calcular a reputação do líder.
Linha de Produção
V que mapeia as rodadas para os líderes. O Shoal executa instâncias do Bullshark uma após a outra, de forma 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.
Inicialmente, 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 concordaram com este ponto âncora. Assim, todos os validadores podem concordar com segurança 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. Os pontos de âncora da primeira rodada são ordenados pelo primeiro instante. Em seguida, o Shoal inicia um novo instante na segunda rodada, que tem um ponto de âncora, que é ordenado por esse instante, e então, outro novo instante encomenda 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-9f789cb669f6fcc244ea7ff7648e48b4.webp(
Reputação do Líder
Durante a ordenação Bullshark, ao pular pontos de ancoragem, a latência aumenta. Nesse caso, a tecnologia de pipeline não pode ajudar, pois uma nova instância não pode ser iniciada até que a instância anterior tenha encomendado os pontos de ancoragem. O Shoal garante que é menos provável que os líderes correspondentes sejam escolhidos para lidar com pontos de ancoragem perdidos 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, usando 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 receberão baixas pontuações, pois podem estar inoperantes, lentos ou agindo de má fé.
A sua filosofia é recalcular de forma determinística o mapeamento pré-definido F 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 alcançar um consenso sobre a pontuação, de modo a alcançar 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, pois ambas usam 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 ordenar os âncoras na r-ésima rodada, os validadores só 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 de validação 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 quadro Shoal: como reduzir a latência do Bullshark no 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 de BFT determinísticas 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 limite também aumentará significativamente a latência, pois é muito importante configurá-los adequadamente e geralmente é necessário ajustá-los dinamicamente, uma vez que depende muito do ambiente ) rede (. Antes de passar para o próximo líder, o protocolo pagará a penalização total do tempo limite para o líder com falha. Portanto, as configurações de tempo limite não podem ser excessivamente conservadoras, mas se o tempo limite for muito curto, o protocolo pode ignorar bons líderes. Por exemplo, observamos