Estrutura Shoal: 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 pausas em protocolos práticos determinísticos. No geral, em condições sem falhas, a latência do Bullshark foi melhorada em 40%, e em condições de falha, foi melhorada em 80%.
Shoal é uma estrutura que melhora o protocolo de consenso baseado em Narwhal através de pipeline e reputação do líder. 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 Shoal utilize a construção assíncrona de DAG para eliminar timeouts em todos os cenários. Isso permite que Shoal ofereça propriedades de resposta universal, incluindo a resposta otimista que normalmente é necessária.
A tecnologia é muito simples e envolve a execução sequencial de várias instâncias do protocolo subjacente. Quando instanciado com Bullshark, é como um grupo de "tubarões" participando de uma corrida de revezamento.
Motivação
Ao buscar alto desempenho em redes de blockchain, as pessoas sempre se preocuparam 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 na versão inicial do Diem alcançou apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.
Recent breakthroughs stem from the realization that data dissemination is the main bottleneck based on leader protocols and can benefit from parallelization. The Narwhal system separates data dissemination from core consensus logic, proposing an architecture where all validators disseminate data simultaneously, and the consensus component only orders a small amount of metadata. The Narwhal paper reports a throughput of 160,000 TPS.
O Quorum Store apresentado anteriormente separa a propagação de dados do consenso, utilizado para escalar o protocolo de consenso atual Jolteon. Jolteon é um protocolo baseado em líderes, 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, os protocolos de consenso baseados em líderes não conseguem aproveitar plenamente o potencial de throughput do Narwhal.
Portanto, decidiu-se implantar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com zero custo de comunicação. No entanto, a estrutura DAG do Bullshark traz um custo de latência de 50%.
Este artigo apresenta como o Shoal reduz significativamente a latência do Bullshark.
Contexto do DAG-BFT
Em Narwhal DAG, cada vértice está associado a uma rodada. Ao entrar na rodada r, o validador deve 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 momento.
Uma propriedade chave do DAG é que não é ambígua: 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 a mesma história causal de v.
Ordem total
É possível alcançar consenso sobre a ordem total de todos os vértices no DAG sem custos adicionais de comunicação. Os validadores no DAG-Rider, Tusk e Bullshark interpretam a estrutura 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 existentes têm a seguinte estrutura:
Ponto de âncora reservado: a cada algumas rodadas há um líder previamente determinado, o pico do líder é chamado de ponto de âncora.
Ponto 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 por um a lista de âncoras ordenadas, classificando todos os vértices não ordenados anteriores na história causal de cada âncora.
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, todas compartilhando o mesmo prefixo. No Shoal, observamos que todos os validadores concordaram com a primeira âncora ordenada.
Bullshark latência
A latência do Bullshark depende do número de voltas entre os âncoras ordenadas no DAG. Embora algumas versões de sincronização tenham uma latência melhor do que as versões assíncronas, ainda estão longe do ideal.
Existem principalmente duas questões:
Latência média de bloco: em situações comuns, os vértices de pontos ímpares precisam de três rodadas, enquanto os vértices de pontos pares que não são âncoras precisam de quatro rodadas para serem ordenados.
Situação de falha de latência: Se um líder de rodada não conseguir transmitir o ponto âncora a tempo, os vértices não ordenados das rodadas anteriores devem esperar pela ordenação do próximo ponto âncora, o que reduz significativamente o desempenho da rede de replicação geográfica.
Estrutura Shoal
Shoal melhora o Bullshark através de uma linha de produção, permitindo que haja um ponto de ancoragem a cada rodada, reduzindo a latência de todos os vértices não âncoras para três rodadas. Shoal também introduz um mecanismo de reputação de líder sem custo, favorecendo a seleção de líderes rápidos.
Desafio
No protocolo DAG, o pipeline e a reputação do líder são considerados problemas difíceis:
As tentativas anteriores de modificar a lógica central do Bullshark parecem ser essencialmente impossíveis.
A reputação dos líderes pode levar a classificações completamente diferentes, e os validadores precisam chegar a um consenso sobre a história ordenada para escolher os âncoras futuras.
Como evidência da dificuldade do problema, as implementações do Bullshark no ambiente de produção atualmente não suportam essas características.
Protocolo
A Shoal depende da execução de cálculos locais sobre DAG, permitindo a capacidade de armazenar e reinterpretar as informações das rodadas anteriores. Aproveitando a percepção de que todos os validadores concordam com o primeiro ponto de âncora ordenado, a Shoal combina sequencialmente várias instâncias de Bullshark para processamento em pipeline, permitindo que:
O primeiro ponto de ancoragem ordenado é o ponto de transição da instância.
A história causal do ponto de âncora é usada para calcular a reputação dos líderes
linha de produção
Shoal executa instâncias Bullshark uma após a outra, cada instância encomenda uma âncora, acionando a mudança para a próxima instância.
Inicialmente, o Shoal lançou a primeira instância Bullshark na primeira ronda do DAG, funcionando até que o primeiro ponto de ancoragem ordenado ( fosse determinado, como na ronda r ). Todos os validadores concordaram com este ponto de ancoragem, portanto, pode-se concordar de forma definitiva em reinterpretar o DAG a partir da ronda r+1. O Shoal lançou uma nova instância Bullshark na ronda r+1.
Idealmente, isto permite que o Shoal encomende um ponto âncora por ronda.
reputação do líder
Quando o Bullshark salta sobre o ponto de âncora, a latência aumenta. O Shoal atribui pontuações a cada nó de validação através de um mecanismo de reputação, garantindo que é menos provável escolher líderes lentos no futuro.
A cada atualização de pontuação, recalcular de forma determinística o mapeamento F do round para o líder, favorecendo líderes de alta pontuação. Para que os validadores cheguem a um consenso sobre o novo mapeamento, eles devem chegar a um consenso sobre a pontuação.
A linha de produção e a reputação da liderança podem se combinar naturalmente, pois ambas utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após alcançar um consenso sobre o primeiro ponto de âncora ordenado.
sem latência
O tempo limite desempenha um papel crucial na implementação BFT síncrona baseada em líder, mas introduz complexidade e aumenta significativamente a latência.
Shoal observou que a construção do DAG fornece um "relógio" para estimar a velocidade da rede. Contanto que n-f validadores honestos continuem a adicionar vértices ao DAG, as rodadas continuarão a avançar. Eventualmente, quando um líder sem falhas transmitir rapidamente o ponto âncora, toda a história causal do ponto âncora será ordenada.
Evitar atrasos está intimamente relacionado à reputação dos líderes. A espera repetida por líderes lentos aumentará a latência, e o mecanismo de reputação exclui validadores lentos de serem escolhidos como líderes.
resposta geral
Shoal fornece a propriedade de resposta universal, podendo operar em velocidade de rede mesmo na falha do líder ou em situações de rede assíncrona. Isso é superior ao conceito de resposta otimista do Hotstuff.
Avaliação
Implementou o Bullshark e o Shoal, e fez uma comparação com o Jolteon. Principais descobertas:
O Baseline Bullshark sem tempo limite apresenta o melhor desempenho em caso de falha.
O pipeline de Shoal e o mecanismo de reputação dos líderes melhoraram significativamente a latência do Bullshark.
Em 16 das 50 falhas, a latência do Shoal foi 65% menor do que a do Baseline Bullshark.
Jolteon não consegue expandir para mais de 20 nós de validação, com uma capacidade de processamento de cerca de metade da Bullshark/Shoal.
No geral, a Shoal melhorou significativamente a latência do Bullshark, e sob alta carga deve ser capaz de igualar a latência de ponta a ponta do Jolteon.
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 melhora significativamente o desempenho da blockchain Aptos, com uma redução da latência de 40%-80%.
Estrutura Shoal: 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 pausas em protocolos práticos determinísticos. No geral, em condições sem falhas, a latência do Bullshark foi melhorada em 40%, e em condições de falha, foi melhorada em 80%.
Shoal é uma estrutura que melhora o protocolo de consenso baseado em Narwhal através de pipeline e reputação do líder. 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 Shoal utilize a construção assíncrona de DAG para eliminar timeouts em todos os cenários. Isso permite que Shoal ofereça propriedades de resposta universal, incluindo a resposta otimista que normalmente é necessária.
A tecnologia é muito simples e envolve a execução sequencial de várias instâncias do protocolo subjacente. Quando instanciado com Bullshark, é como um grupo de "tubarões" participando de uma corrida de revezamento.
Motivação
Ao buscar alto desempenho em redes de blockchain, as pessoas sempre se preocuparam 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 na versão inicial do Diem alcançou apenas 3500 TPS, muito abaixo da meta de 100k+ TPS.
Recent breakthroughs stem from the realization that data dissemination is the main bottleneck based on leader protocols and can benefit from parallelization. The Narwhal system separates data dissemination from core consensus logic, proposing an architecture where all validators disseminate data simultaneously, and the consensus component only orders a small amount of metadata. The Narwhal paper reports a throughput of 160,000 TPS.
O Quorum Store apresentado anteriormente separa a propagação de dados do consenso, utilizado para escalar o protocolo de consenso atual Jolteon. Jolteon é um protocolo baseado em líderes, 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, os protocolos de consenso baseados em líderes não conseguem aproveitar plenamente o potencial de throughput do Narwhal.
Portanto, decidiu-se implantar o Bullshark sobre o Narwhal DAG, um protocolo de consenso com zero custo de comunicação. No entanto, a estrutura DAG do Bullshark traz um custo de latência de 50%.
Este artigo apresenta como o Shoal reduz significativamente a latência do Bullshark.
Contexto do DAG-BFT
Em Narwhal DAG, cada vértice está associado a uma rodada. Ao entrar na rodada r, o validador deve 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 momento.
Uma propriedade chave do DAG é que não é ambígua: 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 a mesma história causal de v.
Ordem total
É possível alcançar consenso sobre a ordem total de todos os vértices no DAG sem custos adicionais de comunicação. Os validadores no DAG-Rider, Tusk e Bullshark interpretam a estrutura 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 existentes têm a seguinte estrutura:
Ponto de âncora reservado: a cada algumas rodadas há um líder previamente determinado, o pico do líder é chamado de ponto de âncora.
Ponto 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 por um a lista de âncoras ordenadas, classificando todos os vértices não ordenados anteriores na história causal de cada âncora.
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, todas compartilhando o mesmo prefixo. No Shoal, observamos que todos os validadores concordaram com a primeira âncora ordenada.
Bullshark latência
A latência do Bullshark depende do número de voltas entre os âncoras ordenadas no DAG. Embora algumas versões de sincronização tenham uma latência melhor do que as versões assíncronas, ainda estão longe do ideal.
Existem principalmente duas questões:
Latência média de bloco: em situações comuns, os vértices de pontos ímpares precisam de três rodadas, enquanto os vértices de pontos pares que não são âncoras precisam de quatro rodadas para serem ordenados.
Situação de falha de latência: Se um líder de rodada não conseguir transmitir o ponto âncora a tempo, os vértices não ordenados das rodadas anteriores devem esperar pela ordenação do próximo ponto âncora, o que reduz significativamente o desempenho da rede de replicação geográfica.
Estrutura Shoal
Shoal melhora o Bullshark através de uma linha de produção, permitindo que haja um ponto de ancoragem a cada rodada, reduzindo a latência de todos os vértices não âncoras para três rodadas. Shoal também introduz um mecanismo de reputação de líder sem custo, favorecendo a seleção de líderes rápidos.
Desafio
No protocolo DAG, o pipeline e a reputação do líder são considerados problemas difíceis:
As tentativas anteriores de modificar a lógica central do Bullshark parecem ser essencialmente impossíveis.
A reputação dos líderes pode levar a classificações completamente diferentes, e os validadores precisam chegar a um consenso sobre a história ordenada para escolher os âncoras futuras.
Como evidência da dificuldade do problema, as implementações do Bullshark no ambiente de produção atualmente não suportam essas características.
Protocolo
A Shoal depende da execução de cálculos locais sobre DAG, permitindo a capacidade de armazenar e reinterpretar as informações das rodadas anteriores. Aproveitando a percepção de que todos os validadores concordam com o primeiro ponto de âncora ordenado, a Shoal combina sequencialmente várias instâncias de Bullshark para processamento em pipeline, permitindo que:
linha de produção
Shoal executa instâncias Bullshark uma após a outra, cada instância encomenda uma âncora, acionando a mudança para a próxima instância.
Inicialmente, o Shoal lançou a primeira instância Bullshark na primeira ronda do DAG, funcionando até que o primeiro ponto de ancoragem ordenado ( fosse determinado, como na ronda r ). Todos os validadores concordaram com este ponto de ancoragem, portanto, pode-se concordar de forma definitiva em reinterpretar o DAG a partir da ronda r+1. O Shoal lançou uma nova instância Bullshark na ronda r+1.
Idealmente, isto permite que o Shoal encomende um ponto âncora por ronda.
reputação do líder
Quando o Bullshark salta sobre o ponto de âncora, a latência aumenta. O Shoal atribui pontuações a cada nó de validação através de um mecanismo de reputação, garantindo que é menos provável escolher líderes lentos no futuro.
A cada atualização de pontuação, recalcular de forma determinística o mapeamento F do round para o líder, favorecendo líderes de alta pontuação. Para que os validadores cheguem a um consenso sobre o novo mapeamento, eles devem chegar a um consenso sobre a pontuação.
A linha de produção e a reputação da liderança podem se combinar naturalmente, pois ambas utilizam a mesma tecnologia central, ou seja, reinterpretar o DAG após alcançar um consenso sobre o primeiro ponto de âncora ordenado.
sem latência
O tempo limite desempenha um papel crucial na implementação BFT síncrona baseada em líder, mas introduz complexidade e aumenta significativamente a latência.
Shoal observou que a construção do DAG fornece um "relógio" para estimar a velocidade da rede. Contanto que n-f validadores honestos continuem a adicionar vértices ao DAG, as rodadas continuarão a avançar. Eventualmente, quando um líder sem falhas transmitir rapidamente o ponto âncora, toda a história causal do ponto âncora será ordenada.
Evitar atrasos está intimamente relacionado à reputação dos líderes. A espera repetida por líderes lentos aumentará a latência, e o mecanismo de reputação exclui validadores lentos de serem escolhidos como líderes.
resposta geral
Shoal fornece a propriedade de resposta universal, podendo operar em velocidade de rede mesmo na falha do líder ou em situações de rede assíncrona. Isso é superior ao conceito de resposta otimista do Hotstuff.
Avaliação
Implementou o Bullshark e o Shoal, e fez uma comparação com o Jolteon. Principais descobertas:
O Baseline Bullshark sem tempo limite apresenta o melhor desempenho em caso de falha.
O pipeline de Shoal e o mecanismo de reputação dos líderes melhoraram significativamente a latência do Bullshark.
Em 16 das 50 falhas, a latência do Shoal foi 65% menor do que a do Baseline Bullshark.
Jolteon não consegue expandir para mais de 20 nós de validação, com uma capacidade de processamento de cerca de metade da Bullshark/Shoal.
No geral, a Shoal melhorou significativamente a latência do Bullshark, e sob alta carga deve ser capaz de igualar a latência de ponta a ponta do Jolteon.