A Aptos labs resolveu dois importantes problemas em aberto no DAG BFT, reduzindo bastante a latência e, pela primeira vez, eliminando a necessidade de pausas em protocolos práticos determinísticos. No geral, isso melhora a latência do Bullshark em 40% no caso sem falha e 80% no caso com falha.
Shoal é uma estrutura que aprimora qualquer protocolo de consenso baseado em Narwhal (por exemplo, DAG-Rider, Tusk, Bullshark) por meio de pipelining e reputação de líder. O pipeline reduz a latência de pedidos de DAG introduzindo uma âncora por rodada, e a reputação do líder melhora ainda mais a latência ao garantir que as âncoras sejam associadas aos validadores mais rápidos. Além disso, a reputação de líder permite que a Shoal aproveite a construção DAG assíncrona para eliminar tempos limite em todos os cenários. Isso permite que o Shoal forneça uma propriedade que chamamos de Universal Response, que contém a Optimistic Response que geralmente é necessária.
Nossa técnica é muito simples, envolve a execução de várias instâncias do protocolo subjacente sequencialmente, uma após a outra. Assim, quando instanciado com Bullshark, obtemos um grupo de "tubarões" que estão fazendo uma corrida de revezamento.
Motivação
Na busca pelo alto desempenho nas redes blockchain, tem havido um foco constante na redução da complexidade da comunicação. No entanto, esta abordagem não resultou em um aumento significativo no rendimento. Por exemplo, a implementação do Hotstuff em uma versão inicial do Diem atingiu apenas 3500 TPS, muito abaixo de nossa meta de atingir 100k+ TPS.
No entanto, avanços recentes decorrem da percepção de que a propagação de dados é o principal gargalo dos protocolos baseados em líderes e que pode se beneficiar da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central e propõe uma arquitetura em que todos os validadores propagam dados simultaneamente, enquanto os componentes de consenso solicitam apenas uma quantidade menor de metadados. O jornal Narwhal relata um rendimento de 160.000 TPS.
Em um artigo anterior, apresentamos o Quorum Store. Nossa implementação Narwhal separa a propagação de dados do consenso e como usamos isso para estender nosso protocolo de consenso atual, Jolteon. Jolteon é um protocolo baseado em líder que combina o caminho rápido linear do Tendermint com alterações de visualização no estilo PBFT para reduzir a latência do Hotstuff em 33%. No entanto, está claro que um protocolo de consenso baseado em líder não pode explorar totalmente o potencial de rendimento do Narwhal. Apesar de separar a propagação de dados do consenso, os líderes do Hotstuff/Jolteon ainda são limitados à medida que a taxa de transferência aumenta.
Portanto, decidimos implantar o Bullshark, um protocolo de consenso com sobrecarga de comunicação zero, sobre o Narwhal DAG. Infelizmente, a estrutura DAG que suporta o alto rendimento do Bullshark vem com uma penalidade de latência de 50% em comparação com o Jolteon.
Neste post, descrevemos como o Shoal conseguiu uma redução drástica na latência do Bullshark.
Plano de fundo DAG-BFT
Vamos começar entendendo o contexto relevante deste artigo. Para uma descrição detalhada de Narwhal e Bullshark, consulte o post DAG Meets BFT.
Cada vértice em um Narwhal DAG está associado a um número redondo. Para entrar na rodada r, um verificador deve primeiro obter nf vértices pertencentes à rodada r-1. Cada verificador pode transmitir um vértice por rodada, e cada vértice refere-se a pelo menos nf vértices na rodada anterior. Devido à assincronia da rede, diferentes validadores podem observar diferentes visualizações locais do DAG a qualquer momento. Aqui está uma ilustração de uma possível visão parcial:
Figura 1: O histórico causal dos vértices identificados pelo nó de validação 2 da rodada 2 são destacados em verde
Uma propriedade chave dos DAGs não é a ambiguidade: dois validadores têm exatamente o mesmo histórico causal de v se tiverem o mesmo vértice v em sua visão local do DAG.
Ordem total
É possível concordar com a ordem total de todos os vértices em um DAG sem sobrecarga de comunicação adicional. 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 do grupo seja diferente na estrutura DAG, todos os protocolos de consenso baseados em Narwhal existentes têm a seguinte estrutura:
Âncoras predeterminadas, haverá um líder pré-determinado a cada poucas rodadas (por exemplo, duas rodadas no Bullshark), e os vértices do líder são chamados de âncoras;
Ordenando as âncoras, o verificador decide de forma independente, mas deterministicamente, quais âncoras pedir e quais pular;
Ordenar histórias causais, onde os validadores processam sua lista ordenada de âncoras uma a uma e, para cada âncora, classificam todos os vértices não ordenados anteriormente em sua história causal por alguma regra determinística.
Figura 2: Ilustração de uma possível visualização parcial de um DAG no protocolo Bullshark. Neste exemplo, as âncoras vermelhas e amarelas são classificadas, enquanto as verdes (não no DAG) são ignoradas. Portanto, para ordenar o DAG, os validadores ordenam de forma determinística primeiro as histórias causais das âncoras vermelhas, seguidas pelas âncoras amarelas.
A chave para satisfazer a segurança é garantir que na etapa (2) acima, todos os validadores honestos criem uma lista ordenada de âncoras de modo que todas as listas compartilhem o mesmo prefixo. Na Shoal, fazemos as seguintes observações para todos os protocolos acima:
** Todos os validadores concordam com a primeira âncora ordenada. **
Latência Bullshark
A latência do Bullshark depende do número de rodadas entre as âncoras ordenadas no DAG. Embora a versão parcialmente síncrona mais útil do Bullshark tenha melhor latência do que a versão assíncrona, ela está longe de ser ideal.
Problema 1: Latência média do bloco. No Bullshark, cada rodada par tem uma âncora e os vértices de cada rodada ímpar são interpretados como votos. Normalmente, são necessárias duas rodadas do DAG para ordenar as âncoras, no entanto, os vértices no histórico causal de uma âncora levam muito mais rodadas para esperar que uma âncora seja ordenada. No caso comum, os vértices em rodadas ímpares requerem três rodadas, enquanto os vértices não-âncora em rodadas pares requerem quatro rodadas (consulte a Figura 3).
Figura 3: No caso comum, as âncoras na rodada i+1 precisam ser classificadas por duas rodadas. Os vértices na rodada i são classificados simultaneamente, então sua latência é de três rodadas. No entanto, os vértices na rodada i+1 precisam esperar que a próxima âncora seja classificada (a da rodada i+3), portanto, o atraso na classificação é de quatro rodadas.
Problema 2: Latência do caso de falha, a análise de latência acima se aplica ao caso sem falha, por outro lado, se o líder de uma rodada falhar em transmitir âncoras rápido o suficiente, as âncoras não podem ser solicitadas (e, portanto, são ignoradas), portanto, todas os vértices não classificados nas rodadas anteriores devem aguardar a classificação da próxima âncora. Isso pode reduzir significativamente o desempenho de uma rede replicada geograficamente, especialmente porque o Bullshark usa tempos limite de espera pelo líder.
Shoal Framework
O Shoal resolve esses dois problemas de latência aprimorando o Bullshark (ou qualquer outro protocolo BFT baseado em Narwhal) por canalização, permitindo uma âncora em cada rodada e reduzindo a latência de todos os vértices não âncora no DAG para três rodadas. A Shoal também introduz um mecanismo de reputação de líder de sobrecarga zero no DAG, que influencia a seleção em favor de líderes rápidos.
desafio
No contexto dos protocolos DAG, o pipelining e a reputação do líder são considerados problemas difíceis pelos seguintes motivos:
O pipelining anterior tenta modificar a lógica central do Bullshark, mas isso parece inerentemente impossível
Leader Reputation, introduzido no DiemBFT e formalizado no Carousel, é a ideia de selecionar dinamicamente os futuros líderes (âncoras no Bullshark) com base no desempenho passado dos validadores. Embora o desacordo sobre a identidade do líder não viole a segurança nesses protocolos, no Bullshark pode levar a uma ordenação completamente diferente, que chega ao cerne da questão, que é que a seleção dinâmica e determinística de âncoras de roda é a chave para resolver o consenso necessário , enquanto os validadores precisam concordar com um histórico ordenado para selecionar futuras âncoras.
Como evidência da dificuldade do problema, notamos que a implementação do Bullshark, incluindo a implementação atual em produção, não suporta esses recursos.
protocolo
Apesar dos desafios mencionados, verifica-se que as soluções, como diz o ditado, estão por trás da simplicidade.
No Shoal, contamos com a capacidade de realizar cálculos locais no DAG e implementamos a capacidade de preservar e reinterpretar informações de rodadas anteriores. Com o insight central de que todos os validadores concordam com a primeira âncora em ordem, Shoal canaliza várias instâncias do Bullshark compondo-as sequencialmente de modo que (1) a primeira âncora em ordem seja o ponto de comutação para as instâncias e (2) o causal o histórico das âncoras é usado para calcular a reputação do líder.
Canalização
Semelhante ao Bullshark, os validadores concordam a priori sobre possíveis âncoras, ou seja, existe um mapeamento conhecido F: R -> V rodadas de mapeamento para os líderes. Shoal executa instâncias de Bullshark uma após a outra, de modo que, para cada instância, a âncora seja predeterminada pelo mapa F. Cada instância solicita uma âncora, que aciona uma mudança para a próxima instância.
Inicialmente, Shoal lança a primeira instância de Bullshark na primeira rodada do DAG e a executa até que a primeira âncora ordenada seja identificada, digamos na rodada r. Todos os validadores concordam com esta âncora. Portanto, todos os validadores podem concordar deterministicamente em reinterpretar o DAG a partir da rodada r+1. Shoal apenas inicia uma nova instância de Bullshark na rodada r+1.
Na melhor das hipóteses, isso permite que Shoal peça uma âncora a cada rodada. As âncoras para a primeira rodada são classificadas pela primeira instância. Então, Shoal inicia uma nova instância na segunda rodada, que por sua vez tem uma âncora ordenada pela instância, então outra nova instância ordena as âncoras na terceira rodada, e o processo continua. Por favor, veja a ilustração abaixo:
Figura 4: Os vértices correspondentes aos líderes determinados por F são marcados com uma coroa. A primeira instância do Bullshark primeiro interpreta o DAG com as âncoras nas rodadas 1, 3 e 5. Bullshark determina as âncoras na rodada 1 (em marca de seleção verde mark) é o primeiro a ser classificado na primeira instância. (Observe que, no caso geral, essa âncora pode ser ignorada, enquanto algumas outras âncoras serão classificadas primeiro.) Em seguida, o restante da primeira instância é ignorado e uma nova instância de Bullshark começa na rodada 2, os pontos de âncora são marcados nas rodadas 2 e 4.
Reputação do líder
Maior latência ao pular âncoras durante a classificação do Bullshark. Nesse caso, a técnica de Pipelining é impotente porque uma nova instância não pode ser iniciada até que a instância anterior tenha solicitado uma âncora. Shoal garante que o líder apropriado seja menos provável de ser eleito no futuro para lidar com uma âncora perdida usando um mecanismo de reputação para atribuir a cada validador uma pontuação com base em seu histórico de atividade recente. Um validador que responder e participar do protocolo receberá uma pontuação alta, caso contrário, um validador receberá uma pontuação baixa porque pode travar, ser lento ou ser malicioso.
A ideia é recalcular de forma determinística o mapeamento pré-definido F das rodadas para os líderes a cada atualização de pontuação, favorecendo os líderes com pontuações mais altas. Para que os validadores concordem com o novo mapeamento, eles devem concordar com a pontuação e, portanto, com o histórico usado para derivar a pontuação.
No Shoal, pipelining e reputação de liderança podem ser combinados naturalmente porque ambos usam a mesma técnica central de reinterpretar o DAG depois de concordar com a primeira âncora ordenada.
De fato, a única diferença é que, após ordenar as âncoras na rodada r, o validador só precisa calcular um novo mapeamento F' da rodada r+1 com base no histórico causal das âncoras ordenadas na rodada r . Em seguida, o validador executa uma nova instância de Bullshark a partir da rodada r+1 usando a função de seleção de âncora atualizada F'. Veja a imagem abaixo:
Figura 5. Os vértices correspondentes aos líderes identificados por F são marcados com coroas transparentes. A primeira instância de Bullshark ordena uma âncora na rodada 1, marcada com uma marca de seleção verde e, em seguida, calcula um novo mapeamento F' com base nas informações do histórico causal da âncora. Líderes determinados por F' são marcados por coroas coloridas.
Não há mais tempos limite
Os tempos limite desempenham um papel crucial em todas as implementações BFT parcialmente síncronas determinísticas baseadas em líder. No entanto, a complexidade que eles introduzem aumenta a quantidade de estado interno que precisa ser gerenciado e observado, o que complica o processo de depuração e requer mais técnicas de observabilidade.
Os tempos limite também podem aumentar significativamente a latência, pois é importante configurá-los adequadamente e geralmente precisam ser ajustados dinamicamente, pois são altamente dependentes do ambiente (rede). O protocolo paga ao líder defeituoso a penalidade de tempo limite total antes de passar para o próximo líder. Portanto, a configuração de timeout não pode ser muito conservadora, mas se o timeout for muito curto, o protocolo pode pular bons líderes. Por exemplo, observamos que, sob alta carga, os líderes em Jolteon/Hotstuff ficaram sobrecarregados e os tempos limite expiraram antes que pudessem avançar no progresso.
Infelizmente, os protocolos baseados em líder, como Hotstuff e Jolteon, exigem inerentemente tempos limite para garantir que o protocolo possa progredir sempre que o líder falhar. Sem um tempo limite, até mesmo um líder com falha poderia interromper o protocolo para sempre. Devido à incapacidade de distinguir entre um líder defeituoso e um líder lento durante a assíncrona, os tempos limite podem fazer com que os validadores vejam alterações em todos os líderes sem consenso.
No Bullshark, os tempos limite são usados na construção do DAG para garantir que, durante a sincronização, um líder honesto adicione âncoras ao DAG rápido o suficiente para que sejam ordenados.
Observamos que a construção do DAG fornece um "relógio" para estimar a velocidade da rede. Na ausência de pausas, as rodadas continuam a progredir enquanto nf validadores honestos continuarem a adicionar vértices ao DAG. Embora o Bullshark possa não ser capaz de classificar na velocidade da rede (devido a líderes problemáticos), o DAG ainda cresce na velocidade da rede, apesar de alguns problemas de líder ou da rede ser assíncrona. Eventualmente, quando um líder livre de falhas transmite âncoras com rapidez suficiente, toda a história causal das âncoras será ordenada.
Em nossa avaliação, comparamos o Bullshark com e sem timeout nos seguintes casos:
Líder rápido, ou seja, pelo menos mais rápido que outros validadores. Nesse caso, ambos os métodos fornecem a mesma latência porque as âncoras são ordenadas e os tempos limite não são usados.
Falso líder, neste caso o Bullshark sem pausas fornece melhor latência, pois os validadores pularão imediatamente suas âncoras, enquanto os validadores com pausas aguardarão sua chegada antes de continuar o Expect.
Líder lento, este é o único caso em que o Bullshark tem melhor desempenho de timeout. Isso ocorre porque, sem uma pausa, a âncora pode ser ignorada porque o líder não pode transmiti-la rápido o suficiente, enquanto com uma pausa, os validadores aguardarão a âncora.
Na Shoal, evitar tempos limite e reputação de liderança andam de mãos dadas. Esperar repetidamente por um líder lento aumenta a latência, e o mecanismo de reputação do líder impede que validadores lentos sejam eleitos como líderes. Dessa forma, o sistema utiliza nós de validação rápida para executar na velocidade da rede em todos os cenários do mundo real.
Observe que o resultado da impossibilidade de FLP mostra que nenhum protocolo de consenso determinístico pode evitar timeouts. Shoal não pode contornar esse resultado porque existe um cronograma teórico de eventos adversários que impediria que todas as âncoras fossem comandadas. Em vez disso, Shoal volta a um tempo limite após um número configurável de saltos de âncora consecutivos. Na prática, é extremamente improvável que isso aconteça.
Resposta Geral
O artigo Hotstuff popularizou o conceito de resposta otimista, que, embora não seja formalmente definido, intuitivamente significa que o protocolo pode ser executado na velocidade da rede sob boas condições, incluindo um líder rápido e uma rede síncrona.
O Shoal fornece uma propriedade ainda melhor, que chamamos de Universal Response. Especificamente, em contraste com Hotstuff, Shoal continua a rodar na velocidade da rede mesmo se o líder falhar por um número configurável de rodadas consecutivas ou ciclos assíncronos pelos quais a rede passa. Veja uma comparação mais detalhada na tabela abaixo.
Observe que a capacidade de resposta universal fornece garantias de progresso estritamente melhores durante períodos assíncronos e quando o líder falha. Durante a sincronização com um líder lento, essas propriedades não são comparáveis porque dependem da lentidão do líder. No entanto, dada a reputação do líder, líderes lentos raramente devem aparecer em Shoal.
Avalie
Implementamos Bullshark e Shoal em cima de nossa loja Quorum de implementação Narwhal. Uma comparação detalhada entre Shoal, Bullshark e Jolteon pode ser encontrada na seção de avaliação do artigo do Shoal, onde fornecemos alguns destaques.
Primeiro, para demonstrar o poder da construção DAG assíncrona, comparamos o Bullshark com e sem pausas. O papel Bullshark completo assume uma rede assíncrona, mas fornece um modo de caminho rápido, exigindo pausas durante todas as rodadas. Chamamos esta versão de Vanilla Bullshark. Observamos que para versões hipotéticas de redes parcialmente síncronas independentes, não são necessárias pausas nas rodadas de votação. Chamamos essa versão de Vanilla Bullshark sem tempo limite de votação sem tempo limite de votação, Baseline Bullshark é a versão sem tempo limite.
O gráfico abaixo compara o impacto dos tempos limite na latência do Bullshark com e sem falhas. Aparentemente, o Baseline Bullshark (sem tempo limite) funciona melhor em caso de falha. Sem falhas, o Baseline Bullshark é comparável ao Vanilla Bullshark sem suspensão de votação. Isso ocorre porque, conforme mencionado anteriormente, sem um mecanismo de reputação do líder, os tempos limite podem ter uma vantagem em situações em que o líder é bom, mas lento.
Figura 6.: Impacto dos timeouts na latência do Bullshark sem falhas (esquerda) e com falhas (direita), com 50 validadores no caso de falha
Em seguida, instanciamos o Shoal usando o Baseline Bullshark (sem timeout) e demonstramos as melhorias de latência do pipelining e do mecanismo de reputação do líder com e sem falha e, para completar, também o comparamos com o Jolteon com e sem comparação de falha.
A Figura 7 abaixo mostra o caso sem falha e, embora o pipeline e a reputação do líder possam reduzir a latência individualmente, combiná-los resulta na melhor latência.
Quanto ao Jolteon, ele não pode ser dimensionado para mais de 20 validadores e, mesmo que seja executado no Quorum Store, pode atingir apenas cerca de metade da taxa de transferência do Bullshark/Shoal, o que remove o gargalo da propagação de dados.
Os resultados mostram que o Shoal melhora muito a latência do Bullshark. Quanto ao Jolteon, é importante observar que, embora tenhamos medido apenas a latência de consenso. Como o Jolteon não pode ser executado nativamente em cima de um DAG, ele requer latência adicional para desacoplar a propagação de dados, que não medimos. Portanto, sob alta carga, o Shoal deve corresponder à latência de ponta a ponta do Jolteon.
Figura 7: Taxa de transferência e latência sem falhas, Shoal PL e Shaol LR suportam apenas pipelining e reputação de líder, respectivamente.
A Figura 8 abaixo mostra um caso de falha com 50 validadores, onde o mecanismo de reputação do líder melhora significativamente a latência ao reduzir a probabilidade de um validador com falha ser eleito como líder. Observe que com 16 falhas em 50, a latência de Shoal foi 65% menor do que a linha de base Bullshark.
Ver original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Explicação do 4D Shoal Framework: Como reduzir a latência do Bullshark no Aptos?
Original: Aptos Labs
Compilação: Aptos Global
Visão geral
A Aptos labs resolveu dois importantes problemas em aberto no DAG BFT, reduzindo bastante a latência e, pela primeira vez, eliminando a necessidade de pausas em protocolos práticos determinísticos. No geral, isso melhora a latência do Bullshark em 40% no caso sem falha e 80% no caso com falha.
Shoal é uma estrutura que aprimora qualquer protocolo de consenso baseado em Narwhal (por exemplo, DAG-Rider, Tusk, Bullshark) por meio de pipelining e reputação de líder. O pipeline reduz a latência de pedidos de DAG introduzindo uma âncora por rodada, e a reputação do líder melhora ainda mais a latência ao garantir que as âncoras sejam associadas aos validadores mais rápidos. Além disso, a reputação de líder permite que a Shoal aproveite a construção DAG assíncrona para eliminar tempos limite em todos os cenários. Isso permite que o Shoal forneça uma propriedade que chamamos de Universal Response, que contém a Optimistic Response que geralmente é necessária.
Nossa técnica é muito simples, envolve a execução de várias instâncias do protocolo subjacente sequencialmente, uma após a outra. Assim, quando instanciado com Bullshark, obtemos um grupo de "tubarões" que estão fazendo uma corrida de revezamento.
Motivação
Na busca pelo alto desempenho nas redes blockchain, tem havido um foco constante na redução da complexidade da comunicação. No entanto, esta abordagem não resultou em um aumento significativo no rendimento. Por exemplo, a implementação do Hotstuff em uma versão inicial do Diem atingiu apenas 3500 TPS, muito abaixo de nossa meta de atingir 100k+ TPS.
No entanto, avanços recentes decorrem da percepção de que a propagação de dados é o principal gargalo dos protocolos baseados em líderes e que pode se beneficiar da paralelização. O sistema Narwhal separa a propagação de dados da lógica de consenso central e propõe uma arquitetura em que todos os validadores propagam dados simultaneamente, enquanto os componentes de consenso solicitam apenas uma quantidade menor de metadados. O jornal Narwhal relata um rendimento de 160.000 TPS.
Em um artigo anterior, apresentamos o Quorum Store. Nossa implementação Narwhal separa a propagação de dados do consenso e como usamos isso para estender nosso protocolo de consenso atual, Jolteon. Jolteon é um protocolo baseado em líder que combina o caminho rápido linear do Tendermint com alterações de visualização no estilo PBFT para reduzir a latência do Hotstuff em 33%. No entanto, está claro que um protocolo de consenso baseado em líder não pode explorar totalmente o potencial de rendimento do Narwhal. Apesar de separar a propagação de dados do consenso, os líderes do Hotstuff/Jolteon ainda são limitados à medida que a taxa de transferência aumenta.
Portanto, decidimos implantar o Bullshark, um protocolo de consenso com sobrecarga de comunicação zero, sobre o Narwhal DAG. Infelizmente, a estrutura DAG que suporta o alto rendimento do Bullshark vem com uma penalidade de latência de 50% em comparação com o Jolteon.
Neste post, descrevemos como o Shoal conseguiu uma redução drástica na latência do Bullshark.
Plano de fundo DAG-BFT
Vamos começar entendendo o contexto relevante deste artigo. Para uma descrição detalhada de Narwhal e Bullshark, consulte o post DAG Meets BFT.
Cada vértice em um Narwhal DAG está associado a um número redondo. Para entrar na rodada r, um verificador deve primeiro obter nf vértices pertencentes à rodada r-1. Cada verificador pode transmitir um vértice por rodada, e cada vértice refere-se a pelo menos nf vértices na rodada anterior. Devido à assincronia da rede, diferentes validadores podem observar diferentes visualizações locais do DAG a qualquer momento. Aqui está uma ilustração de uma possível visão parcial:
Figura 1: O histórico causal dos vértices identificados pelo nó de validação 2 da rodada 2 são destacados em verde
Uma propriedade chave dos DAGs não é a ambiguidade: dois validadores têm exatamente o mesmo histórico causal de v se tiverem o mesmo vértice v em sua visão local do DAG.
Ordem total
É possível concordar com a ordem total de todos os vértices em um DAG sem sobrecarga de comunicação adicional. 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 do grupo seja diferente na estrutura DAG, todos os protocolos de consenso baseados em Narwhal existentes têm a seguinte estrutura:
Âncoras predeterminadas, haverá um líder pré-determinado a cada poucas rodadas (por exemplo, duas rodadas no Bullshark), e os vértices do líder são chamados de âncoras;
Ordenando as âncoras, o verificador decide de forma independente, mas deterministicamente, quais âncoras pedir e quais pular;
Ordenar histórias causais, onde os validadores processam sua lista ordenada de âncoras uma a uma e, para cada âncora, classificam todos os vértices não ordenados anteriormente em sua história causal por alguma regra determinística.
Figura 2: Ilustração de uma possível visualização parcial de um DAG no protocolo Bullshark. Neste exemplo, as âncoras vermelhas e amarelas são classificadas, enquanto as verdes (não no DAG) são ignoradas. Portanto, para ordenar o DAG, os validadores ordenam de forma determinística primeiro as histórias causais das âncoras vermelhas, seguidas pelas âncoras amarelas.
A chave para satisfazer a segurança é garantir que na etapa (2) acima, todos os validadores honestos criem uma lista ordenada de âncoras de modo que todas as listas compartilhem o mesmo prefixo. Na Shoal, fazemos as seguintes observações para todos os protocolos acima:
** Todos os validadores concordam com a primeira âncora ordenada. **
Latência Bullshark
A latência do Bullshark depende do número de rodadas entre as âncoras ordenadas no DAG. Embora a versão parcialmente síncrona mais útil do Bullshark tenha melhor latência do que a versão assíncrona, ela está longe de ser ideal.
Problema 1: Latência média do bloco. No Bullshark, cada rodada par tem uma âncora e os vértices de cada rodada ímpar são interpretados como votos. Normalmente, são necessárias duas rodadas do DAG para ordenar as âncoras, no entanto, os vértices no histórico causal de uma âncora levam muito mais rodadas para esperar que uma âncora seja ordenada. No caso comum, os vértices em rodadas ímpares requerem três rodadas, enquanto os vértices não-âncora em rodadas pares requerem quatro rodadas (consulte a Figura 3).
Figura 3: No caso comum, as âncoras na rodada i+1 precisam ser classificadas por duas rodadas. Os vértices na rodada i são classificados simultaneamente, então sua latência é de três rodadas. No entanto, os vértices na rodada i+1 precisam esperar que a próxima âncora seja classificada (a da rodada i+3), portanto, o atraso na classificação é de quatro rodadas.
Problema 2: Latência do caso de falha, a análise de latência acima se aplica ao caso sem falha, por outro lado, se o líder de uma rodada falhar em transmitir âncoras rápido o suficiente, as âncoras não podem ser solicitadas (e, portanto, são ignoradas), portanto, todas os vértices não classificados nas rodadas anteriores devem aguardar a classificação da próxima âncora. Isso pode reduzir significativamente o desempenho de uma rede replicada geograficamente, especialmente porque o Bullshark usa tempos limite de espera pelo líder.
Shoal Framework
O Shoal resolve esses dois problemas de latência aprimorando o Bullshark (ou qualquer outro protocolo BFT baseado em Narwhal) por canalização, permitindo uma âncora em cada rodada e reduzindo a latência de todos os vértices não âncora no DAG para três rodadas. A Shoal também introduz um mecanismo de reputação de líder de sobrecarga zero no DAG, que influencia a seleção em favor de líderes rápidos.
desafio
No contexto dos protocolos DAG, o pipelining e a reputação do líder são considerados problemas difíceis pelos seguintes motivos:
O pipelining anterior tenta modificar a lógica central do Bullshark, mas isso parece inerentemente impossível
Leader Reputation, introduzido no DiemBFT e formalizado no Carousel, é a ideia de selecionar dinamicamente os futuros líderes (âncoras no Bullshark) com base no desempenho passado dos validadores. Embora o desacordo sobre a identidade do líder não viole a segurança nesses protocolos, no Bullshark pode levar a uma ordenação completamente diferente, que chega ao cerne da questão, que é que a seleção dinâmica e determinística de âncoras de roda é a chave para resolver o consenso necessário , enquanto os validadores precisam concordar com um histórico ordenado para selecionar futuras âncoras.
Como evidência da dificuldade do problema, notamos que a implementação do Bullshark, incluindo a implementação atual em produção, não suporta esses recursos.
protocolo
Apesar dos desafios mencionados, verifica-se que as soluções, como diz o ditado, estão por trás da simplicidade.
No Shoal, contamos com a capacidade de realizar cálculos locais no DAG e implementamos a capacidade de preservar e reinterpretar informações de rodadas anteriores. Com o insight central de que todos os validadores concordam com a primeira âncora em ordem, Shoal canaliza várias instâncias do Bullshark compondo-as sequencialmente de modo que (1) a primeira âncora em ordem seja o ponto de comutação para as instâncias e (2) o causal o histórico das âncoras é usado para calcular a reputação do líder.
Canalização
Semelhante ao Bullshark, os validadores concordam a priori sobre possíveis âncoras, ou seja, existe um mapeamento conhecido F: R -> V rodadas de mapeamento para os líderes. Shoal executa instâncias de Bullshark uma após a outra, de modo que, para cada instância, a âncora seja predeterminada pelo mapa F. Cada instância solicita uma âncora, que aciona uma mudança para a próxima instância.
Inicialmente, Shoal lança a primeira instância de Bullshark na primeira rodada do DAG e a executa até que a primeira âncora ordenada seja identificada, digamos na rodada r. Todos os validadores concordam com esta âncora. Portanto, todos os validadores podem concordar deterministicamente em reinterpretar o DAG a partir da rodada r+1. Shoal apenas inicia uma nova instância de Bullshark na rodada r+1.
Na melhor das hipóteses, isso permite que Shoal peça uma âncora a cada rodada. As âncoras para a primeira rodada são classificadas pela primeira instância. Então, Shoal inicia uma nova instância na segunda rodada, que por sua vez tem uma âncora ordenada pela instância, então outra nova instância ordena as âncoras na terceira rodada, e o processo continua. Por favor, veja a ilustração abaixo:
Figura 4: Os vértices correspondentes aos líderes determinados por F são marcados com uma coroa. A primeira instância do Bullshark primeiro interpreta o DAG com as âncoras nas rodadas 1, 3 e 5. Bullshark determina as âncoras na rodada 1 (em marca de seleção verde mark) é o primeiro a ser classificado na primeira instância. (Observe que, no caso geral, essa âncora pode ser ignorada, enquanto algumas outras âncoras serão classificadas primeiro.) Em seguida, o restante da primeira instância é ignorado e uma nova instância de Bullshark começa na rodada 2, os pontos de âncora são marcados nas rodadas 2 e 4.
Reputação do líder
Maior latência ao pular âncoras durante a classificação do Bullshark. Nesse caso, a técnica de Pipelining é impotente porque uma nova instância não pode ser iniciada até que a instância anterior tenha solicitado uma âncora. Shoal garante que o líder apropriado seja menos provável de ser eleito no futuro para lidar com uma âncora perdida usando um mecanismo de reputação para atribuir a cada validador uma pontuação com base em seu histórico de atividade recente. Um validador que responder e participar do protocolo receberá uma pontuação alta, caso contrário, um validador receberá uma pontuação baixa porque pode travar, ser lento ou ser malicioso.
A ideia é recalcular de forma determinística o mapeamento pré-definido F das rodadas para os líderes a cada atualização de pontuação, favorecendo os líderes com pontuações mais altas. Para que os validadores concordem com o novo mapeamento, eles devem concordar com a pontuação e, portanto, com o histórico usado para derivar a pontuação.
No Shoal, pipelining e reputação de liderança podem ser combinados naturalmente porque ambos usam a mesma técnica central de reinterpretar o DAG depois de concordar com a primeira âncora ordenada.
De fato, a única diferença é que, após ordenar as âncoras na rodada r, o validador só precisa calcular um novo mapeamento F' da rodada r+1 com base no histórico causal das âncoras ordenadas na rodada r . Em seguida, o validador executa uma nova instância de Bullshark a partir da rodada r+1 usando a função de seleção de âncora atualizada F'. Veja a imagem abaixo:
Figura 5. Os vértices correspondentes aos líderes identificados por F são marcados com coroas transparentes. A primeira instância de Bullshark ordena uma âncora na rodada 1, marcada com uma marca de seleção verde e, em seguida, calcula um novo mapeamento F' com base nas informações do histórico causal da âncora. Líderes determinados por F' são marcados por coroas coloridas.
Não há mais tempos limite
Os tempos limite desempenham um papel crucial em todas as implementações BFT parcialmente síncronas determinísticas baseadas em líder. No entanto, a complexidade que eles introduzem aumenta a quantidade de estado interno que precisa ser gerenciado e observado, o que complica o processo de depuração e requer mais técnicas de observabilidade.
Os tempos limite também podem aumentar significativamente a latência, pois é importante configurá-los adequadamente e geralmente precisam ser ajustados dinamicamente, pois são altamente dependentes do ambiente (rede). O protocolo paga ao líder defeituoso a penalidade de tempo limite total antes de passar para o próximo líder. Portanto, a configuração de timeout não pode ser muito conservadora, mas se o timeout for muito curto, o protocolo pode pular bons líderes. Por exemplo, observamos que, sob alta carga, os líderes em Jolteon/Hotstuff ficaram sobrecarregados e os tempos limite expiraram antes que pudessem avançar no progresso.
Infelizmente, os protocolos baseados em líder, como Hotstuff e Jolteon, exigem inerentemente tempos limite para garantir que o protocolo possa progredir sempre que o líder falhar. Sem um tempo limite, até mesmo um líder com falha poderia interromper o protocolo para sempre. Devido à incapacidade de distinguir entre um líder defeituoso e um líder lento durante a assíncrona, os tempos limite podem fazer com que os validadores vejam alterações em todos os líderes sem consenso.
No Bullshark, os tempos limite são usados na construção do DAG para garantir que, durante a sincronização, um líder honesto adicione âncoras ao DAG rápido o suficiente para que sejam ordenados.
Observamos que a construção do DAG fornece um "relógio" para estimar a velocidade da rede. Na ausência de pausas, as rodadas continuam a progredir enquanto nf validadores honestos continuarem a adicionar vértices ao DAG. Embora o Bullshark possa não ser capaz de classificar na velocidade da rede (devido a líderes problemáticos), o DAG ainda cresce na velocidade da rede, apesar de alguns problemas de líder ou da rede ser assíncrona. Eventualmente, quando um líder livre de falhas transmite âncoras com rapidez suficiente, toda a história causal das âncoras será ordenada.
Em nossa avaliação, comparamos o Bullshark com e sem timeout nos seguintes casos:
Líder rápido, ou seja, pelo menos mais rápido que outros validadores. Nesse caso, ambos os métodos fornecem a mesma latência porque as âncoras são ordenadas e os tempos limite não são usados.
Falso líder, neste caso o Bullshark sem pausas fornece melhor latência, pois os validadores pularão imediatamente suas âncoras, enquanto os validadores com pausas aguardarão sua chegada antes de continuar o Expect.
Líder lento, este é o único caso em que o Bullshark tem melhor desempenho de timeout. Isso ocorre porque, sem uma pausa, a âncora pode ser ignorada porque o líder não pode transmiti-la rápido o suficiente, enquanto com uma pausa, os validadores aguardarão a âncora.
Na Shoal, evitar tempos limite e reputação de liderança andam de mãos dadas. Esperar repetidamente por um líder lento aumenta a latência, e o mecanismo de reputação do líder impede que validadores lentos sejam eleitos como líderes. Dessa forma, o sistema utiliza nós de validação rápida para executar na velocidade da rede em todos os cenários do mundo real.
Observe que o resultado da impossibilidade de FLP mostra que nenhum protocolo de consenso determinístico pode evitar timeouts. Shoal não pode contornar esse resultado porque existe um cronograma teórico de eventos adversários que impediria que todas as âncoras fossem comandadas. Em vez disso, Shoal volta a um tempo limite após um número configurável de saltos de âncora consecutivos. Na prática, é extremamente improvável que isso aconteça.
Resposta Geral
O artigo Hotstuff popularizou o conceito de resposta otimista, que, embora não seja formalmente definido, intuitivamente significa que o protocolo pode ser executado na velocidade da rede sob boas condições, incluindo um líder rápido e uma rede síncrona.
O Shoal fornece uma propriedade ainda melhor, que chamamos de Universal Response. Especificamente, em contraste com Hotstuff, Shoal continua a rodar na velocidade da rede mesmo se o líder falhar por um número configurável de rodadas consecutivas ou ciclos assíncronos pelos quais a rede passa. Veja uma comparação mais detalhada na tabela abaixo.
Observe que a capacidade de resposta universal fornece garantias de progresso estritamente melhores durante períodos assíncronos e quando o líder falha. Durante a sincronização com um líder lento, essas propriedades não são comparáveis porque dependem da lentidão do líder. No entanto, dada a reputação do líder, líderes lentos raramente devem aparecer em Shoal.
Avalie
Implementamos Bullshark e Shoal em cima de nossa loja Quorum de implementação Narwhal. Uma comparação detalhada entre Shoal, Bullshark e Jolteon pode ser encontrada na seção de avaliação do artigo do Shoal, onde fornecemos alguns destaques.
Primeiro, para demonstrar o poder da construção DAG assíncrona, comparamos o Bullshark com e sem pausas. O papel Bullshark completo assume uma rede assíncrona, mas fornece um modo de caminho rápido, exigindo pausas durante todas as rodadas. Chamamos esta versão de Vanilla Bullshark. Observamos que para versões hipotéticas de redes parcialmente síncronas independentes, não são necessárias pausas nas rodadas de votação. Chamamos essa versão de Vanilla Bullshark sem tempo limite de votação sem tempo limite de votação, Baseline Bullshark é a versão sem tempo limite.
O gráfico abaixo compara o impacto dos tempos limite na latência do Bullshark com e sem falhas. Aparentemente, o Baseline Bullshark (sem tempo limite) funciona melhor em caso de falha. Sem falhas, o Baseline Bullshark é comparável ao Vanilla Bullshark sem suspensão de votação. Isso ocorre porque, conforme mencionado anteriormente, sem um mecanismo de reputação do líder, os tempos limite podem ter uma vantagem em situações em que o líder é bom, mas lento.
Figura 6.: Impacto dos timeouts na latência do Bullshark sem falhas (esquerda) e com falhas (direita), com 50 validadores no caso de falha
Em seguida, instanciamos o Shoal usando o Baseline Bullshark (sem timeout) e demonstramos as melhorias de latência do pipelining e do mecanismo de reputação do líder com e sem falha e, para completar, também o comparamos com o Jolteon com e sem comparação de falha.
A Figura 7 abaixo mostra o caso sem falha e, embora o pipeline e a reputação do líder possam reduzir a latência individualmente, combiná-los resulta na melhor latência.
Quanto ao Jolteon, ele não pode ser dimensionado para mais de 20 validadores e, mesmo que seja executado no Quorum Store, pode atingir apenas cerca de metade da taxa de transferência do Bullshark/Shoal, o que remove o gargalo da propagação de dados.
Os resultados mostram que o Shoal melhora muito a latência do Bullshark. Quanto ao Jolteon, é importante observar que, embora tenhamos medido apenas a latência de consenso. Como o Jolteon não pode ser executado nativamente em cima de um DAG, ele requer latência adicional para desacoplar a propagação de dados, que não medimos. Portanto, sob alta carga, o Shoal deve corresponder à latência de ponta a ponta do Jolteon.
Figura 7: Taxa de transferência e latência sem falhas, Shoal PL e Shaol LR suportam apenas pipelining e reputação de líder, respectivamente.
A Figura 8 abaixo mostra um caso de falha com 50 validadores, onde o mecanismo de reputação do líder melhora significativamente a latência ao reduzir a probabilidade de um validador com falha ser eleito como líder. Observe que com 16 falhas em 50, a latência de Shoal foi 65% menor do que a linha de base Bullshark.