Resumo Técnico: Digestos que Preservam Distância para Consenso BFT

1. Declaração do Problema

Protocolos de consenso tolerante a falhas bizantinas (BFT), incluindo HotStuff, PBFT e Ethereum 2.0, dependem de hashes resistentes a colisões (por exemplo, SHA-256) para comparar estados de validadores. Embora eficazes para prevenir falsificação, essa abordagem destrói informações de "distância". Se dois validadores concordam em 19 de 20 transações, seus hashes são completamente não relacionados, indistinguíveis de validadores que não compartilham nenhuma transação. Essa limitação impõe três restrições estruturais na literatura BFT:

1. Sincronização de Estado Obrigatória: Validadores devem sincronizar completamente o estado antes de votar, pois hashes não podem medir concordância parcial.
2. Qualidade de Concordância Inmensurável: Protocolos não podem detectar concordância unânime até que todas as rodadas de votação estejam completas, forçando latências fixas de múltiplas rodadas mesmo em condições ideais.
3. Comitês Hierárquicos Grandes: Para garantir segurança em consenso estruturado em árvore, os grupos de folhas devem ser grandes o suficiente (por exemplo, 128 validadores no Ethereum) para satisfazer independentemente o limiar de tolerância bizantina $2N/3$, limitando a profundidade da árvore e a escalabilidade.

2. Metodologia: Digestos que Preservam Distância

O artigo introduz um primitivo chamado Digestos que Preservam Distância para substituir hashes resistentes a colisões na comparação de estados. A construção envolve:

• Vectorização: Cada transação é hashada usando SHA-512. A saída de 64 bytes é dividida em 8 segmentos.
• Mapeamento de Coordenadas: Cada segmento é tratado como um inteiro sem sinal, reduzido módulo 10.000 e dividido por 10.000 para produzir uma coordenada no intervalo $[0, 1)$.
• Soma Comutativa: O digesto de um validador para um conjunto de transações $T$ é a soma vetorial $D(T) = \sum_{tx \in T} v(tx)$ no espaço de 8 dimensões.

Este primitivo possui três propriedades que hashes não possuem:

1. Distância Proporcional: A distância euclidiana entre dois digestos é proporcional ao número de transações diferentes.
2. Resumo Exato: A média ponderada de um grupo de digestos é uma representação exata do estado agregado do grupo, permitindo que um grupo de validadores seja resumido em um único valor compacto (76 bytes) sem perda de informação.
3. Identificação de Diferença de Conjuntos: Quando digestos diferem, uma diferença de filtro de Bloom permite que o agregador identifique exatamente quais transações estão faltando na visão de um validador, permitindo sincronização direcionada sem troca completa de estado.

3. Contribuições Principais e Aplicações

O artigo demonstra três aplicações primárias deste primitivo dentro de um novo protocolo denominado Proxima:

A. Protocolo BFT de Duas Fases (Proxima)

O Proxima opera em duas fases:

• Fase 1 (Filtragem por Distância): Validadores enviam digestos e filtros de Bloom para um agregador. O agregador agrupa validadores dentro de um limiar de distância. Se a variância do grupo estiver próxima de zero (indicando alta concordância), o protocolo emite um certificado de finalidade de rodada única (caminho rápido). Caso contrário, empurra transações faltantes via diferença de Bloom.
• Fase 2 (Comprometimento): Membros do grupo assinam o hash do bloco usando assinaturas BLS. O agregador produz uma assinatura agregada.
• Resultado: Diferentemente do HotStuff, que requer três rodadas independentemente da concordância, o Proxima alcança finalidade de rodada única quando os validadores concordam.

B. Consenso Estruturado em Árvore com Grupos Pequenos

Como a filtragem por distância opera no nível individual em vez de exigir BFT no nível de grupo, o Proxima permite consenso hierárquico com grupos pequenos (por exemplo, 10 validadores).

• Mecanismo: Líderes de folhas filtram validadores bizantinos (que estão longe da referência) e relatam a média ponderada dos validadores honestos.
• Resultado: Isso elimina a necessidade de grandes comitês (128 validadores) para garantir segurança, permitindo árvores mais profundas (5 níveis versus 2–3 níveis) e reduzindo a complexidade de mensagens.

C. Verificação de Consistência entre Shards

Digestos permitem verificação de custo constante entre shards.

• Mecanismo: Shards vizinhos trocam digestos de transações da zona de sobreposição. Se a distância for zero, os estados correspondem. Se não for zero, a diferença de Bloom identifica transações divergentes específicas para resolução.
• Resultado: Isso substitui a coordenação por transação do Commit de Duas Fases (2PC) ou cadeias de recibos, reduzindo a sobrecarga entre shards em 99% em comparação com o 2PC em taxas de propagação de 95%.

4. Resultados e Avaliação

O artigo avalia o Proxima contra HotStuff, PBFT e a estrutura de comitê do Ethereum usando simulações com $N=100.000$ validadores e 30% de falhas bizantinas.

• Complexidade de Mensagens: A Árvore Proxima usa 2,2× menos mensagens que o HotStuff. Esta é uma propriedade estrutural não afetada pelo paralelismo, derivada da execução de duas fases, pré-filtragem de nós bizantinos e roteamento em árvore com resumos compactos.
• Latência:
  • Núcleo Único: O Proxima alcança finalidade de núcleo único em ~0,9 segundos (902 ms) comparado a ~18 segundos para o HotStuff. A estrutura em árvore distribui a agregação BLS, mantendo o processamento do caminho crítico baixo (9,9 ms).
  • Multi-núcleo: Embora a agregação BLS multi-núcleo estreite a lacuna (HotStuff cai para ~940 ms, Proxima Flat para ~220 ms), a árvore mantém uma vantagem no tempo de BLS do caminho crítico porque os nós folha processam muito poucas assinaturas.
• Sobrecarga entre Shards: Em 95% de propagação, a verificação baseada em digestos usa 99% menos mensagens que o 2PC e 95% menos que abordagens baseadas em recibos (NEAR Nightshade).
• Segurança: A segurança é provada independente do agrupamento da Fase 1. Menos de $N/3$ validadores bizantinos não podem causar finalização conflitante. A Fase 1 pode excluir validadores honestos (risco de vivacidade), mas isso é limitado pela desigualdade de Hoeffding para ser negligenciável ($<10^{-9}$ em $N$ prático).

5. Significado e Alegações

O artigo afirma que digestos que preservam distância removem as três restrições fundamentais impostas pelo hashing resistente a colisões no BFT. Ao permitir a medição da qualidade da concordância, o primitivo permite:

1. Caminhos Rápidos Otimistas: Protocolos podem finalizar em uma rodada quando o consenso é alto.
2. Hierarquias Escaláveis: Árvores de consenso podem utilizar grupos pequenos (tamanho 10) e estruturas profundas, pois a segurança é mantida via filtragem por distância em vez de votação por grupo.
3. Sharding Eficiente: A consistência entre shards pode ser verificada a um custo constante por par de shards, escalando com a divergência real em vez do volume total de transações.

Os autores enfatizam que, embora o primitivo seja uma aplicação conhecida de Hashing Sensível à Localização (LSH) em estruturas de dados, sua aplicação a acordo bizantino é nova. A segurança do sistema depende de suposições criptográficas padrão (assinaturas BLS e SHA-512), com o filtro de distância servindo como mecanismo de vivacidade e otimização em vez de mecanismo de segurança. O artigo conclui que essa abordagem oferece uma melhoria geral para qualquer protocolo BFT que compare estados via hashes.