Bitcoin, a ameaça quântica se aproxima

A ameaça quântica não é para amanhã de manhã, mas os avanços recentes sugerem que a comunidade Bitcoin fez bem em iniciar grandes movimentos.

A ameaça Google

Nos perguntávamos em abril se era necessário apagar os bitcoins de Satoshi Nakamoto antes da chegada do computador quântico. Os pesquisadores do Google nos dão uma nova oportunidade para aprofundar um pouco mais o assunto devido a um grande avanço no campo da fatoração quântica.

Quebrar as criptografias clássicas está se mostrando muito mais fácil do que o esperado. Os recursos necessários para quebrar a criptografia RSA-2048 foram reduzidos em 20 vezes. Esse salto é resultado de uma otimização do algoritmo de Shor e de uma melhor correção dos erros relacionados à decoerência quântica.

Agora são necessários um milhão de qubits para quebrar o RSA-2048, contra 20 milhões de qubits anteriormente. Dito isso, o maior processador quântico atualmente possui apenas 1021 qubits (o Condor da IBM). Sabendo que a dificuldade de manter a coerência quântica aumenta exponencialmente com o número de qubits.

Além disso, o computador quântico ainda não consegue fatorar um número tão pequeno quanto 35. Portanto, até prova em contrário, não houve progresso tangível apesar de todos os grandes anúncios sobre o aumento do número de qubits e a melhoria da correção de erros.

De qualquer forma, há ainda muito a considerar. Ainda mais quando empresas como a Apple e Microsoft planejam adotar a criptografia pós-quântica já neste outono.

Aqui está para os curiosos o histórico dos avanços científicos que levaram ao computador quântico:

O Bitcoin está ameaçado?

O avanço do Google diz respeito ao algoritmo de Shor que, aliado ao computador quântico, pode resolver o problema do logaritmo discreto exponencialmente mais rápido do que com computadores clássicos. Em outras palavras, é possível obter uma chave privada a partir de uma chave pública Bitcoin.

Mas embora esse algoritmo possa resolver eficientemente tanto o problema da fatoração (afetando o RSA) quanto o problema do logaritmo discreto (afetando o ECDSA / Bitcoin), o Bitcoin e sua curva elíptica “secp256k1” não são diretamente impactados pelo recente avanço do Google.

O fundador do Pauli Group, porém, alerta que o ECDSA geralmente é mais fácil de quebrar que o RSA, e que não é impossível que a IA consiga otimizar o algoritmo de Shor para quebrar o ECDSA (Bitcoin) com mais facilidade.

A propósito (e isso é importante), note que simplesmente dobrar o tamanho da chave pública (por exemplo, usando uma curva elíptica “secp512k1”) só tornaria a derivação da chave privada duas vezes mais difícil via o algoritmo de Shor. A proteção não seria suficiente.

De acordo com o fabricante de computador quântico IonQ, a curva elíptica “secp32k1” poderia ser quebrada em 2027. Para a “secp256k1” (Bitcoin), seria em 2029. Essas previsões, no entanto, devem ser tomadas com muita cautela.

Felizmente, o NIST está trabalhando na padronização de algoritmos de criptografia pós-quântica. Três candidatos estão em destaque para assinaturas digitais: CRYSTALS-Dilithium, SPHINCS+ e FALCON. Estes algoritmos poderiam teoricamente substituir o ECDSA.

Mas isso não será “de graça”. As assinaturas e as chaves são muito maiores, o que certamente reduzirá o throughput das transações onchain. Criar e verificar as assinaturas também levará muito mais tempo.

Por exemplo, para o CRYSTAL-Dilithium Nível I, uma chave pública representa 1.312 bytes e uma assinatura 2.420 bytes, muito maior do que as assinaturas ECDSA (72 bytes) ou Schnorr (64 bytes) atuais.

[O nível de segurança Level I do NIST oferece segurança equivalente a chaves de 128 bits, e o Level V uma segurança de 256 bits]

Em suma, a solução já existe, mas ainda é preciso escolher o algoritmo adequado. E que cada um migre manualmente para endereços pós-quânticos.

BIP-360 : Pay to Quantum Resistant Hash (P2QRH)

BIP-360, proposto por Hunter Beast, é um “primeiro passo pragmático” (soft fork) introduzindo um novo tipo de UTXO chamado “Pay to Quantum Resistant Hash” (P2QRH), cujos endereços começam com “bc1r”.

Explicação:

Atualmente, uma transação Bitcoin (destruição e criação simultânea de UTXO) ocorre revelando uma chave pública junto com uma assinatura baseada no algoritmo ECDSA.

O BIP-360 propõe que as transações contenham tanto assinaturas ECDSA quanto assinaturas pós-quânticas, de forma semelhante a transações multi-sig. Essa combinação permite ter a solução de respaldo ECDSA caso uma falha seja descoberta no algoritmo pós-quântico escolhido.

Hunter Beast defende o algoritmo FALCON, que tem a vantagem de permitir a agregação de assinaturas. Seu primeiro candidato (SQIsign) foi abandonado devido à sua lentidão.

Como mencionado acima, há um preço a pagar. As chaves públicas e assinaturas pós-quânticas são muito maiores do que uma assinatura Schnorr de 64 bytes.

As assinaturas SLH-DSA (SPHINCS+) podem alcançar 29.000 bytes, ou mais (ou menos) dependendo dos parâmetros escolhidos. Isso significa cerca de 40 vezes menos transações por bloco! As assinaturas FALCON são 20 vezes maiores que as assinaturas Schnorr e 13 vezes maiores que as assinaturas ECDSA.

Outras propostas estão na mesa. Aqui está uma lista delas:

Por exemplo, o BIP “Quantum-Resistant Address Migration Protocol” (QRAMP) proposto por Agustin Cruz. Esse BIP prevê um hard fork. Em outras palavras, os bitcoins que não migrarem para endereços pós-quânticos seriam perdidos para sempre.

Em 2020, a Deloitte estimou que 25% dos bitcoins estão vinculados a tipos antigos de endereços vulneráveis a ataques quânticos.

Como proteger seus bitcoins?

Hoje em dia, as “chaves públicas” não são mais realmente públicas. Elas são codificadas passando por funções de hash resistentes a computadores quânticos, como SHA-256 e RIPEMD-160. O hash resultante é o que chamamos de “endereço Bitcoin”.

No entanto, as chaves públicas precisam ser reveladas no momento das transações. Portanto, elas permanecem vulneráveis durante todo o tempo em que estão no mempool aguardando um minerador adicioná-las a um bloco.

A ameaça termina assim que o bloco se propaga. A menos que você cometa o erro de enviar fundos para o mesmo endereço novamente.

Aqui está o resumo de uma transação para melhor compreensão:

Seu wallet contém um UTXO de 1 BTC. Esse UTXO é público e contém várias informações, como o valor (1 BTC) e um script de bloqueio do tipo P2PKH (Pay-to-Public-Key-Hash).

Agora, imagine que você faça um pagamento de 0,5 BTC. Você fornece sua chave pública e uma assinatura para desbloquear o script a fim de realizar a transação.

Como seu UTXO é de 1 BTC, aqui está o que a transação gera:

-0,5 BTC para o endereço do destinatário.
-0,0001 BTC para o endereço do minerador (taxa de transação).
-0,4999 BTC devolvidos a um NOVO endereço de troco gerado pelo seu wallet.

Cada uma dessas três transações cria um novo UTXO. O troco de 0,4999 BTC está vinculado a um novo endereço Bitcoin (uma nova chave pública), portanto, não está mais vulnerável.

Por outro lado, nunca envie fundos para o endereço original que continha 1 BTC, pois ele é agora conhecido por todos.

Aqui está outro artigo sobre a ameaça quântica: Bitcoin e a ameaça quântica.