Como Pode a Bitcoin Resistir aos Computadores Quânticos? Comparação de Três Esquemas de Assinatura Baseados em Redes

Autor original: Equipa Blockstream

Compilação original: Saoirse, Foresight News

A Blockstream Research publicou um relatório de investigação abrangente sobre assinaturas baseadas em redes para a Bitcoin. Este artigo resume o conteúdo da investigação, as principais conclusões e as recomendações relacionadas. O relatório completo pode ser consultado aqui.

As assinaturas digitais são o mecanismo central para autorizar transações na Bitcoin, e as assinaturas Schnorr e ECDSA atualmente utilizadas para este fim têm um custo extremamente baixo. Em 1994, Shor provou que um computador quântico suficientemente poderoso poderia quebrar ambos os tipos de assinaturas. Embora haja um debate contínuo sobre quando tais máquinas estarão disponíveis, precisamos de desenvolver um plano viável de implementação de assinaturas pós-quânticas antes que o problema realmente chegue.

Os esquemas de assinatura baseados em redes são um candidato popular para substituir as assinaturas existentes. A criptografia baseada em redes tem uma história de investigação de mais de um século, e as suas aplicações criptográficas foram desenvolvidas durante quase três décadas. Na criptografia pós-quântica, as assinaturas baseadas em redes oferecem várias vantagens: o tamanho total das chaves públicas e das assinaturas pode ser tão baixo quanto menos de 1,6 kilobytes, e a sua estrutura algébrica é promissora para suportar multiassinaturas, assinaturas de limiar e provas sucintas no futuro.

Este relatório estuda três esquemas: Dilithium, Falcon e Hawk. Para os leitores não familiarizados com a criptografia baseada em redes, explicamos a lógica de design de cada esquema, fornecemos uma descrição completa do fluxo do algoritmo e analisamo-los em dimensões como segurança, desempenho e implementação prática (por exemplo, derivação de chaves em carteiras). Entre os três, quais os esquemas que podem realmente ser implementados na blockchain da Bitcoin?

Critérios de Avaliação

A Bitcoin tem as suas próprias restrições na seleção do esquema de assinatura, e esta avaliação centra-se em quatro critérios principais:

• Custo na cadeia: Uma das métricas mais importantes é o tamanho total das chaves públicas e das assinaturas. Quando um output é gasto, tanto a chave pública como a assinatura são registadas na cadeia, e os nós completos precisam de descarregar e armazenar cada byte. A sobrecarga de verificação é igualmente crítica: cada assinatura é verificada por todos os nós da rede, e uma verificação lenta sobrecarregaria toda a rede.
• Complexidade de implementação: Se o esquema pode ser implementado de forma segura é crucial. Se o design exigir aritmética de vírgula flutuante ou amostragem gaussiana delicada, um erro de implementação ou um ataque de canal lateral, como a análise de temporização, poderia vazar a chave. Para alcançar uma migração suave, a complexidade de implementação é um fator que não pode ser ignorado.
• Risco de implementação: Ao integrar realmente na Bitcoin, existem vários obstáculos práticos: a escolha da função de hash ao nível do consenso (a maioria dos candidatos usa SHAKE, enquanto a Bitcoin usa SHA-256), a reprodutibilidade dos resultados das assinaturas entre plataformas e se o procedimento de assinatura se adequa às restrições de memória das carteiras de hardware.
• Potencial de desenvolvimento: A grande maioria das carteiras Bitcoin usa o mecanismo hierárquico determinístico BIP-32: a partir de uma única chave pública mestra, um número infinito de chaves públicas filhas pode ser derivado sem acesso à chave privada. Atualmente, nenhum esquema de assinatura pós-quântica padronizado suporta nativamente esta funcionalidade, pelo que estudamos o custo de adicionar esta capacidade; também examinamos várias variantes não padronizadas do esquema que podem oferecer benefícios adicionais.

Que Nível de Segurança Deve Ser Escolhido?

Antes de comparar tamanhos, devemos primeiro determinar o nível de segurança alvo, e esta escolha não é tão simples como parece. O NIST classifica os níveis de segurança de 1 a 5; níveis mais altos proporcionam maior segurança, mas também tamanhos de chave e assinatura maiores.

Acreditamos que a Bitcoin deve adotar pelo menos o nível de segurança 3. Os outputs da Bitcoin podem permanecer não gastos durante décadas, e se os avanços na criptoanálise reduzirem o nível de segurança real do esquema, os ativos ficariam bloqueados por chaves enfraquecidas e expostos a riscos de longo prazo. As suposições baseadas em redes já resistiram a quase três décadas de criptoanálise pública, mais tempo do que a base de investigação quando a Bitcoin adotou as curvas elípticas. No entanto, a estrutura algébrica complexa da criptografia baseada em redes ainda deixa muitas vias para ataques futuros, e não devemos apostar toda a nossa segurança de longo prazo nela.

Os principais produtos mainstream fizeram o mesmo julgamento. O protocolo PQ3 do iMessage da Apple descarta diretamente os parâmetros de rede de nível 1 e usa parâmetros de nível 3 e nível 5 em todo o lado; a Cloudflare usa ML-KEM-768 (nível 3) na sua implementação TLS pós-quântica, afirmando que, embora o nível 1 pareça atualmente seguro, é necessário reservar uma margem de segurança para décadas de criptoanálise futura. O horizonte temporal de segurança da Bitcoin é ainda mais longo do que ambos.

Aumentar o nível de segurança tem um custo. Por exemplo, mover o Dilithium do nível 2 para o nível 3 aumenta o tamanho total em cerca de 1,5 kilobytes. O relatório compara conjuntos de parâmetros em todos os níveis de segurança, permitindo que os leitores ponderem eles próprios os compromissos. O caso do Hawk prova que as considerações conservadoras de segurança não são meramente teóricas.

Análise Detalhada dos Esquemas Candidatos

Dilithium: Um Design Simples

O Dilithium, padronizado pelo NIST como ML-DSA no FIPS 204, migra o paradigma compromisso-desafio-resposta das assinaturas Schnorr para a aritmética de redes modulares.

A sua maior característica é a simplicidade. Todas as operações no Dilithium são operações com inteiros: operações de anel, multiplicação matriz-vetor, hashing e arredondamento. Não há aritmética de vírgula flutuante nem amostragem gaussiana discreta. É mais fácil escrever implementações seguras e de tempo constante. É também o candidato mais amplamente implementado, já integrado no OpenSSL, BoringSSL, AWS-LC e Apple CryptoKit.

O compromisso é um tamanho maior. No nível de segurança 3, o ML-DSA-65 tem uma chave pública de 1952 bytes e uma assinatura de 3309 bytes, totalizando 5261 bytes, cerca de 55 vezes o tamanho total da chave pública/privada mais assinatura nativa da Bitcoin, tornando-o o maior dos três esquemas no mesmo nível de segurança.

Para a Bitcoin, o aspeto mais valioso do Dilithium é que é o único dos três que se aproxima da implementação da derivação de chaves ao estilo BIP-32. A construção de chave re-aleatorizável DilithiumRK pode gerar chaves filhas a partir de chaves-mãe usando apenas informação pública. O relatório analisa três variantes, incluindo a nossa proposta DilithiumRKS, onde a lógica de derivação está inteiramente dentro do software da carteira e a cadeia requer apenas um verificador padrão para processar assinaturas ML-DSA comuns. No entanto, nenhuma das três está pronta para produção: duas variantes requerem modificações no verificador, e o próprio DilithiumRKS carece de uma prova completa de infalsificabilidade; todos os esquemas dependem de uma matriz partilhada em toda a rede, que é formalmente segura sob a suposição Module-LWE, mas vincula a segurança de todas as chaves a uma única instância. Acreditamos que a derivação de chaves públicas baseada no Dilithium é atualmente apenas uma prova de conceito e não pode ser implementada na prática.

Falcon: Um Esquema Compacto

O Falcon, selecionado pelo NIST e padronizado como FN-DSA, é o mais compacto dos três. No nível de segurança 1, o Falcon-512 tem um tamanho combinado de chave pública e assinatura de 1563 bytes; no nível 5, o Falcon-1024 totaliza 3073 bytes. O Falcon-1024, com uma margem de segurança mais elevada, é ainda menor do que o Dilithium de nível 3.

O Falcon adota uma abordagem diferente do Dilithium: um paradigma hash-and-sign baseado em redes NTRU. A chave privada do signatário é uma base curta da rede; a mensagem é transformada num ponto no espaço, e o signatário usa a base curta para encontrar um vetor de rede próximo desse ponto. O ponto e o vetor próximo formam juntos a assinatura; a verificação apenas verifica se o vetor pertence à rede e está suficientemente próximo. O desafio de implementação é encontrar o vetor sem vazar informação sobre a base. Os primeiros esquemas GGH e NTRUSign selecionavam diretamente pontos de rede próximos, vazando alguma informação geométrica com cada assinatura. O Falcon adota a estrutura GPV, amostrando vetores próximos de uma distribuição gaussiana, o que comprovadamente torna o output amostrado independente da base, eliminando o risco de fuga, mas a dificuldade de implementação do amostrador aumenta significativamente.

O amostrador é o ponto fraco de engenharia do Falcon. Opera no domínio de Fourier complexo e requer computação de vírgula flutuante. Diferentes processadores, compiladores e opções de otimização de compilação podem causar resultados de vírgula flutuante inconsistentes. Isto não é apenas um problema de compatibilidade, mas também uma preocupação de segurança: a prova de segurança GPV exige que o signatário nunca produza dois vetores curtos diferentes para o mesmo resumo; se a assinatura se tornar determinística, as diferenças de arredondamento de vírgula flutuante induzidas pela plataforma violariam esta condição. Existe uma solução viável: o Falcon determinístico pode substituir a vírgula flutuante de hardware por emulação de inteiros, produzindo assinaturas idênticas em todas as plataformas. O custo é um abrandamento de aproximadamente 15 vezes na velocidade de assinatura e cerca de 2 vezes na geração de chaves.

É importante notar que a verificação não é afetada: a verificação do Falcon é inteiramente baseada em inteiros, determinística e também a mais rápida entre os candidatos. Esta propriedade assimétrica é muito amigável para a Bitcoin: a assinatura é realizada uma vez pela carteira ao gastar uma transação, enquanto cada assinatura é verificada por todos os nós completos da rede. Um abrandamento de 15 vezes na assinatura é um custo de baixa frequência e, em troca, obtemos reprodutibilidade entre plataformas e aritmética de inteiros, o que consideramos um compromisso razoável. Portanto, a questão da vírgula flutuante é um obstáculo que pode ser resolvido por meios de engenharia, não uma falha fatal.

Dois pontos a notar: devido a restrições estruturais, o Falcon não tem parâmetros de nível 3; é necessário escolher entre o nível 1 ou o nível 5. Com base em considerações de margem de segurança, recomendamos o Falcon-1024. Em segundo lugar, a assinatura consome uma grande quantidade de memória: o amostrador para o conjunto de parâmetros 1024 depende de uma árvore pré-computada, ocupando cerca de 90 kilobytes de memória. As carteiras de hardware podem reconstruir dinamicamente a árvore ramo a ramo, reduzindo o uso de memória para 16 kilobytes, mas o tempo de assinatura duplica. Uma assinatura mais lenta em dispositivos de hardware é um custo real, mas ainda aceitável.

Hawk: Um Esquema Falhado

O Hawk pretendia combinar as vantagens dos outros dois esquemas: as assinaturas Hawk-512 têm apenas 555 bytes, menores do que o Falcon; a assinatura é inteiramente baseada em inteiros, com uma pegada de memória mínima de apenas 6 kilobytes. Foi também o único candidato baseado em redes que permaneceu na terceira ronda da competição adicional de assinaturas do NIST, e o relatório dedica um espaço considerável a este esquema.

O compromisso reside nas suposições de segurança. Não se baseia nos problemas NTRU ou SIS que foram submetidos a décadas de criptoanálise, mas no problema do isomorfismo de redes e na suposição one-more-SVP, ambos com um histórico de investigação relativamente curto.

Pouco antes de o relatório ser finalizado, Straznickas e Weis da Anthropic descobriram uma falha estrutural na construção de rede do Hawk: a dimensão do problema SVP que realmente precisa de ser resolvido para a recuperação da chave é apenas metade do que os designers pretendiam. Os bits de segurança de recuperação de chave dos conjuntos de parâmetros candidatos foram significativamente enfraquecidos. Os investigadores completaram um ataque de recuperação de chave de ponta a ponta no parâmetro de desafio HAWK-256 usado para criptoanálise; mesmo sob ataque, os formalmente propostos HAWK-512 e HAWK-1024 permanecem praticamente inquebráveis. A equipa do Hawk confirmou a validade do ataque e retirou o esquema do processo do NIST; a equipa afirmou que, se a vulnerabilidade fosse corrigida duplicando os parâmetros, a vantagem de tamanho original do Hawk desapareceria completamente.

O relatório mantém a secção do Hawk porque o ataque visa propriedades algébricas de um corpo numérico específico e não nega totalmente o paradigma de design. Se um redesenho pode evitar a vulnerabilidade permanece uma questão em aberto. O incidente do Hawk também valida intuitivamente a nossa insistência em margens de segurança conservadoras: um esquema com excelente tamanho e velocidade, tendo passado por várias rondas de padronização, pode ter o seu nível de segurança estimado drasticamente reduzido por um único artigo.

Tabela Comparativa dos Esquemas

Todos os esquemas na tabela acima (incluindo SPHINCS+) são assinaturas sem estado: o signatário não precisa de registar assinaturas passadas. Assinaturas baseadas em hash com estado, como XMSS, podem alcançar tamanhos de assinatura menores, mas exigem a manutenção do estado da assinatura; consulte o relatório especial sobre assinaturas baseadas em hash para comparação.

Muitos Obstáculos Permanecem para a Implementação

O Falcon carece de um esquema de derivação de chaves utilizável. O único esquema de derivação Falcon ao estilo BIP-32 publicamente disponível re-aleatoriza a base da chave privada, fazendo com que o limite superior da norma da assinatura seja drasticamente aumentado, e as assinaturas na cadeia aumentam para cerca de 23,7 kilobytes. Além disso, os parâmetros do esquema não cumprem as suas próprias condições de segurança, e corrigir esta questão aumentaria ainda mais o tamanho. Atualmente, não existe uma implementação viável de derivação de chaves públicas Falcon, o que é também o problema em aberto mais valioso identificado no relatório.

O padrão Falcon ainda não está finalizado. Embora o NIST tenha selecionado o Falcon, o rascunho do FN-DSA não foi oficialmente divulgado. Só após a conclusão da padronização teremos implementações auditadas, vetores de teste e suporte a nível de hardware. A adoção generalizada pode reduzir o risco e a dificuldade de integração na camada de consenso da Bitcoin. Recomendamos aguardar o lançamento oficial do FN-DSA; até lá, o Falcon permanece num estado de fluxo.

Variante Falcon-WS: Esta variante relaxa os parâmetros internos e depende de amostragem por rejeição para compensação, comprimindo o tamanho total para 1114 bytes no nível 1 e 2387 bytes no nível 5, reduzindo ainda mais o tamanho em comparação com o Falcon original. Esta direção tem valor de investigação, mas não será incluída no padrão oficial e requer mais validação criptoanalítica. A investigação existente encontrou falhas nas provas de infalsificabilidade forte dos seus esquemas derivados (a infalsificabilidade comum não é afetada).

Surgirão melhores esquemas no futuro? Além dos esquemas acima, a família Fiat-Shamir remonta ao BLISS em 2013. O resultado mais recente de Gärtner na CRYPTO 2025, baseado em suposições maduras, tem tamanhos de papel comparáveis ao Falcon. A causa raiz da dificuldade em engenhar esta família reside na segurança da implementação: o BLISS foi quebrado por ataques de canal lateral devido à amostragem gaussiana de tempo não constante; os esquemas subsequentes não resolveram completamente esta questão, e o resultado mais recente também sugere que proteger o passo de amostragem é ainda mais difícil. Até que o problema seja resolvido, tais esquemas são apenas teoricamente atraentes e não adequados para implementação.

Assinaturas baseadas em redes e baseadas em hash podem complementar-se. As assinaturas baseadas em redes podem servir como componentes de esquemas híbridos. Por exemplo, no SHRINCS, o caminho de recuperação sem estado usa atualmente assinaturas SPHINCS+ de vários kilobytes; substituí-las por assinaturas Falcon (ou Falcon-WS) seria menor e mais rápido de verificar, reduzindo significativamente a sobrecarga do caminho de recuperação pouco frequente sem afetar o caminho de uso diário.

Conclusões da Investigação

A classificação dos candidatos baseados em redes é clara: o Hawk retirou-se da competição após o ataque da equipa da Anthropic; o Dilithium tem a menor dificuldade de implementação e é o único esquema com uma base de investigação para derivação de chaves, mas o seu tamanho não é amigável para os custos na cadeia da Bitcoin; o Falcon combina tamanho compacto, verificação rápida e suposições de segurança maduras; a sua principal fraqueza — aritmética de vírgula flutuante no lado da assinatura — já tem uma solução de engenharia viável. Se tivéssemos de escolher hoje um esquema de assinatura baseado em redes para a Bitcoin, escolheríamos o Falcon-1024.

Por agora, a nossa visão é consistente com o relatório sobre assinaturas baseadas em hash: a rota conservadora de curto prazo continua a ser as assinaturas baseadas em hash, com as suposições de segurança mais maduras e o menor risco, adequadas como esquema de transição. Uma vez que o FN-DSA seja oficialmente finalizado, com especificações estáveis, bases de código auditadas e suporte de carteiras de hardware, o Falcon trará melhorias significativas em relação às assinaturas puramente baseadas em hash; uma implementação híbrida também pode ser adotada, permitindo que os dois sistemas de assinatura se complementem.