Computação Quântica e o Bitcoin

Como um computador quântico poderia atacar os algoritmos do Bitcoin? Qual a probabilidade disso acontecer? Quais as maneiras de mitigar esse risco?

"IBM Q" by Pierre Metivier is licensed under CC BY 2.0

A computação quântica foi idealizada há poucas décadas, nos anos 80 e 90. Na época em que o Satoshi estava construindo o Bitcoin, ainda não havia nenhum computador quântico de uso prático, apenas aparelhos experimentais em laboratórios de pesquisa. Tampouco havia qualquer certeza de que esse tipo de computador pudesse realmente existir algum dia. No entanto, quinze anos mais tarde, essa área vem avançando a passos enormes, crescendo exponencialmente. Apesar da forte arrancada, ainda não existe nenhum computador capaz de oferecer qualquer risco à criptografia digital.

Qubits

Os computadores quânticos se diferem dos computadores clássicos, pois usam propriedades da física quântica para realizar muitos cálculos mas com pouco trabalho. Os computadores digitais usam bits para registar a menor quantidade de informação digital possível: ou 0 ou 1. Já os quânticos usam qubits, partículas com superposição de estados quânticos que são capazes de registrar tanto 0 quanto 1, ao mesmo tempo!

Um PC comum consegue fazer bilhões de operações matemáticas por segundo. Para fazer mil vezes mais operações no mesmo tempo, seria necessário utilizar mil vezes mais PCs (crescimento linear). O ganho de escala dos computadores quânticos acontece quando se aumenta apenas os qubits do dispositivo. Grosso modo, para obter esse ganho da ordem de mil vezes, bastaria aumentar em dez os qubits de um computador quântico, em vez de adquirir mil novas unidades. Aumentando vinte qubits o ganho seria da ordem de milhões de vezes (crescimento exponencial). Seria como se um computador quântico conseguisse fazer todas as contas possíveis em uma só tacada — que poderia até ser meio lenta, mas ainda assim seria uma só.

Algoritmos de ataques quânticos

Os dois principais algoritmos criptográficos usados no Bitcoin são o ECDSA, usado nas assinaturas, e o SHA-256, usado na mineração e em diversas outras partes.

No caso do ECDSA, com o uso do algoritmo de Shor, capaz de fatorar números grandes, fica possível descobrir a chave privada à partir da chave pública. Existem milhões de BTC em UTXOs cuja chave pública está exposta, como por exemplo todos os 1M BTC do Satoshi. Todos eles poderiam ser roubados nesse tipo de ataque. Os demais, que usam endereços nunca reutilizados, estão um pouco mais seguros, pois a chave pública só é exposta na hora da movimentação.

No caso do SHA-256, com o algoritmo de Grover, capaz de fazer buscas mais rapidamente, fica mais fácil encontrar o bloco na mineração, em proporção quadrática (√N).

No entanto, ambos algoritmos exigem computadores quânticos com "qubits limpos", ou "lógicos", da ordem de milhares deles.

Atualmente ainda estamos na fase dos "qubits sujos", ou "físicos". Estes não servem pra quebrar criptografia, apenas resolvem alguns problemas de física quântica, que computadores clássicos tem dificuldade pra resolver. As melhores técnicas conhecidas preveem que, talvez, com milhões de qubits sujos seja possível executar os algoritmos acima. O computador quântico mais potente em 2024 tem pouco mais de mil qubits sujos. Com os saltos tecnológicos, o setor já espera que em alguns anos, talvez 10, talvez 30, já existam computadores com poder suficiente pra quebrar a criptografia digital. Uma empresas promete 10 qubits limpos ainda neste ano e 100 em 2026. Ainda insuficiente, mas bem próximo de um ataque efetivo, embora seja uma promessa um tanto quanto esperançosa.

Quantum annealing

Os algoritmos descritos acima são usados em computadores quânticos ditos “modelos universais”, que possuem funcionamento de portas lógicas quânticas análogas às portas lógicas dos computadores digitais. Mas existe também um outro modelo de computação quântica chamado quantum annealing, que é usado para resolver problemas de otimização combinatória. A empresa D-Wave fabrica esse tipo de máquina e já vende, por milhões de dólares, um equipamento com 5 mil qubits físicos. Também existe a possibilidade de alugar tempo dessas máquinas por alguns milhares de dólares a hora.

Em 2024, pesquisadores poloneses usaram esse computador para quebrar chaves pequenas de RSA (29 bits), e ECDSA (4 bits). O tamanho considerado seguro para chaves desses algoritmos são 2048 e 256, respectivamente.

Roadmap do Bitcoin

Não existe, por enquanto, nenhum empenho para mudar o algoritmo de assinatura do Bitcoin, o ECDSA, para algum outro que seja seguro contra ataques quânticos. O mais perto disso seria o uso do operador OP_CAT, cuja reativação vem sendo discutida há uns anos. Endereços (UTXOs) seguros contra esses ataques seriam bem mais caros de usar, pois geralmente essa criptografia exige dezenas ou centenas mais dados que as tradicionais. As transações seriam bem maiores e mais caras. Como os blocos tem tamanho limitado, não seria possível que todo mundo movesse suas moedas para um UTXO seguro ao mesmo tempo.

As moedas paradas, há muitos anos, com chave pública exposta ficariam totalmente vulneráveis e não há meios de protegê-las contra roubos (4M BTC segundo estimativa). Uma solução possível, mas enormemente polêmica, seria bloqueá-las pra sempre. Talvez fosse mais prudente não agir contra o roubo, pois não implicaria, necessariamente, em prejuízo aos demais bitcoinheiros.

Para o algoritmo de mineração, o SHA-256, já existe o ajuste de dificuldade para mitigar o risco de mineração muito rápida. Quando os ASICs surgiram, houve um aumento muito grande na geração de novos blocos mas logo a rede se ajustou ao "novo normal". Também existe a possibilidade de algum softfork que exigisse alguma prova-de-trabalho adicional, resistente à computação quântica, caso necessário.

No entanto, esse algoritmo também é usado em diversas outras partes do sistema. Caso seja definitivamente quebrado, seria muito difícil substituí-lo. Como último recurso, talvez o sistema possa ser corrigido com um hardfork, uma modificação drástica e obrigatória. Todos teriam que atualizar seus programas e usar essa nova versão à prova de ataques quânticos.

Sistemas centralizados

Alguns acreditam que outros sistemas, como os bancários e estatais, poderiam ser mais prejudicados e oferecer maiores ganhos para esse tipo de atacante. No entanto, justamente por serem centralizados, tem a vantagem de poderem ser modificados a qualquer momento. Por isso, podem ser atualizados muito mais rapidamente que o Bitcoin, que não costuma aceitar atualizações drásticas ou apressadas. Recentemente os profissionais de segurança da informação já recomendam que sejam usados algoritmos de criptografia pós-quânticos, imunes à esses ataques. Aos poucos esses sistemas estão sendo atualizados.

Disclaimer

Como o objetivo é apenas resumir os riscos dessa possível ameaça ao Bitcoin, o texto possui simplificações e erros grosseiros. O autor mal entende de computação, que dirá quântica!

Ainda está longe de ser uma ameaça.