Os computadores Quantum são considerados uma ameaça para o Bitcoin. Dois cientistas fizeram as contas: Os mineiros quânticos têm realmente uma vantagem sobre os mineiros clássicos? E se sim – isto representa uma ameaça para a Bitcoin?
Bitcoin e computadores quânticos: Tivemos este tópico uma ou duas vezes, e na verdade tem assombrado o Bitcoin desde o início.
Os computadores quânticos ameaçam o Bitcoin? Um computador quântico chegará um dia e, através do seu poder computacional superior, esvaziará todas as carteiras e extrairá todas as Bitcoins? Alguns dizem que sim, a longo prazo isto pode acontecer, outros dizem que não, não haverá uma onça de preocupação durante muito tempo.
Já escrevemos sobre computadores quânticos, Bitcoin e o algoritmo de assinatura ECDSA. Hoje analisamos um artigo em que dois professores canadianos de informática analisam se os mineiros quânticos representam um perigo, e em caso afirmativo, que tipo de perigo.
O tema não é trivial, especialmente para leigos matemáticos. Mas como é emocionante para qualquer pessoa interessada em Bitcoin e no futuro da informática, tentarei apresentar o trabalho da forma mais simples possível.
O progresso do Salto
O quadro básico sobre o qual os autores constroem a sua pergunta é a seguinte teoria: Se um mineiro se torna demasiado poderoso, pode ameaçar a rede. Se ele tiver uma maioria absoluta, pode conduzir 51% dos ataques, mas mesmo abaixo disso pode causar danos através de mineração “agressiva” ou “egoísta”.
Agora, e se um mineiro ganha uma vantagem tal através da computação quântica que a sua parte do haxixe cresce desproporcionadamente?
Basicamente, já passámos por tudo isto antes, e é bastante trivial: o progresso tecnológico acelera a exploração mineira. Não acontece de forma gradual, mas muitas vezes por saltos e saltos. A partir de 2011, as placas gráficas deslocaram os principais processadores, a partir de 2013, a Asics deslocou as placas gráficas. Nesses momentos, a eficiência já não aumenta linearmente, mas sim quadraticamente ou exponencialmente. Agora que Ascis parece ter esgotado em grande parte o potencial dos chips clássicos, os computadores quânticos poderiam dar o próximo grande salto.
Em si mesmo, isto não deve constituir um problema. A mecânica teórica do jogo Bitcoin motiva os jogadores racionais a serem honestos e a manterem-se uns aos outros sob controlo. Ainda assim, um salto tecnológico pode ser acidentado, e talvez se torne uma porta de entrada para as potências hostis agirem de forma irracional para prejudicar a Bitcoin.
Por conseguinte, faz sentido saber quando isso pode acontecer. O que tem de acontecer para os computadores quânticos deslocarem os clássicos Asics da mineração Bitcoin?
Procura de bases de dados não seleccionadas
Pode pensar na mineração de bitcoin como mineiros que geram lotes com o seu poder computacional. Geram hashes aleatórios, e se um hash satisfaz certos requisitos muito raros, o mineiro encontra um bloco. Também se poderia chamar-lhe um ataque de força bruta contra a função hash SHA256.
Os dois professores colocaram desta forma: “Os mineiros tentam inverter parcialmente uma função de hash criptográfico”. Esta “inversão parcial de uma função hash” é “equivalente à procura de um item marcado numa lista não ordenada de itens (uma procura não estruturada)”. Parece ser um ponto menor, mas é fundamental para tudo o resto.
Pois não há muito que os computadores quânticos tenham sido comprovadamente capazes de fazer. Uma das poucas tarefas em que os computadores quânticos são conhecidos por superarem os computadores clássicos é a procura de um item em particular numa lista não ordenada.
Um computador clássico, ao pesquisar uma base de dados não classificada – ou um ataque por força bruta – tem de trabalhar através de uma entrada de cada vez. Pode pensar nisto como um ponteiro bidimensional que se move de item para item. Quando tiver visto metade das entradas, a hipótese de aterragem de um hit excede os 50%. Portanto, um computador clássico necessita em média de operações N/2, em que N é o número total de itens possíveis.
Os computadores Quantum têm agora uma vantagem: um qubit pode ser 0 e 1 ao mesmo tempo, razão pela qual uma série de qubits pode representar simultaneamente todas as variantes concebíveis. Pode-se pensar nisso como um ponteiro apontando em N dimensões. Quando as desistências estão nesta “sobreposição”, a solução já está nelas. Está lá.
Mas assim que se mede, destrói-se a solução. Este é o famoso dilema quântico: se medir, força-se o quanta a assumir um certo mas aleatório estado. Assim, o computador quântico conhece a solução, mas numa reviravolta trágica, desvaloriza-a quando se vai buscá-la.
Grover’s algoritmo: quadrado praticamente acelerado
É aqui que entra o algoritmo de Grover. Desenvolvido por Lov Grover em 1996, o algoritmo de Grover é um método de verificação do resultado. Ao combinar diferentes “portões quânticos” – estas são as operações em computadores quânticos – os qubits detectam resultados falsos e suprimem-nos. Com cada repetição – a chamada iteração Grover – a probabilidade de obter o resultado correcto aumenta assim.
Tudo isto é loucamente complicado em detalhe. Mas uma coisa é clara: com o número certo de iterações, o algoritmo Grover pode acelerar dramaticamente tais buscas. Porque para encontrar um item numa lista não classificada, Grover só precisa de tentativas em √n. Portanto, é quase quadraticamente mais rápido.
Dois exemplos: Se houver 4 itens, os computadores clássicos e os computadores quânticos precisam de 2 tentativas. Com 5.198.400 itens, por outro lado, um computador quântico é encontrado após 2280 tentativas, enquanto um computador convencional tem de funcionar mais de dois milhões de vezes.
Especialmente em tarefas com extrema dificuldade ou um N extremamente elevado, como a mineração de bitcoin, esta diferença – a chamada vantagem quântica – é enorme. É um desses saltos que abalam ecossistemas inteiros. Pelo menos em teoria.
A vantagem quântica é o derretimento
Na prática, um mineiro quântico encontra um problema muito específico: ele só consegue encontrar um bloco quando mede o resultado – e assim aborta o processo. Por isso, tem de saber previamente quantas iterações irá realizar.
A questão é delicada. Porque tanto demasiados como poucos têm desvantagens. Mais iterações aumentam a possibilidade de encontrar uma solução correcta – mas também o perigo de outro mineiro ser mais rápido. Menos iterações, por outro lado, reduzem a probabilidade de um resultado válido – e, portanto, a vantagem quântica.
Se um computador quântico tivesse tempo sem fim, poderia explorar toda a vantagem quântica. Mas isto não é possível com a exploração mineira. Tem de encontrar um compromisso entre muito poucas e demasiadas iterações.
Para calcular o compromisso ideal, os investigadores formaram uma cadeia de Markov com os cenários possíveis. Uma cadeia de Markov é uma formulação matemática de sequências de possíveis eventos, geralmente aleatórios ou parcialmente aleatórios. Tal cadeia indica que caminhos através da selva de probabilidades conduzem, em média, aos melhores resultados: qual a configuração do algoritmo Grover seria ideal.
Surpreendentemente, isto seria 16 minutos.
Duas descobertas notáveis
Se um mineiro quântico espera 16 minutos para ler o resultado do algoritmo de Grover, a sua vantagem sobre os mineiros clássicos atinge o máximo em relação às desvantagens que decorrem do longo período de tempo. De acordo com os cientistas, esta vantagem existe independentemente da dificuldade.
O resultado é muito notável porque pode ser transferido para a prática. Aqui podem-se ver duas consequências graves:
Primeiro, o mineiro com tal táctica desqualifica-se de cerca de 80 por cento dos blocos. Porque estes são encontrados em menos de 16 minutos. Ele maximiza as suas hipóteses de sucesso com os restantes 20 por cento. Esta deve ser a máxima potência mineira total que os computadores quânticos podem alcançar sem sacrificar a eficiência.
Em segundo lugar, a maioria das moedas criptográficas têm intervalos mais curtos entre blocos. Dogecoin e Litecoin têm cerca de alguns minutos, Ethereum e Ripple apenas alguns segundos. Os mineiros quânticos têm um nariz ensanguentado com estas correntes de bloqueio porque a vantagem quântica não se aplica aqui. Já são quantum-safe – pelo menos na mineração.
A paralelização dos computadores quânticos também parece ser um beco sem saída. Embora isto seja possível com o algoritmo Grover, só melhora o desempenho por um factor de √m de acordo com os cálculos dos autores. Com os computadores clássicos, o factor é m, ou seja, é quadraticamente maior. Isto torna questionável se os computadores quânticos serão alguma vez relevantes para a mineração.
78 Megahashes
Estes cálculos desactivam consideravelmente o perigo dos computadores quânticos. Mas a questão crucial permanece ainda sem resposta: O que tem de acontecer para que os mineiros quânticos tenham realmente uma vantagem sobre os mineiros clássicos? Em que altura será mais barato encontrar um bloco com um computador quântico – se é que alguma vez o vai fazer?
Dois factores são decisivos para isto: os custos por iteração de grover e a relação entre o número de hashes necessários para um bloco e o número de iterações de grover necessárias. Os autores calculam isto usando o exemplo de um computador quântico actualmente comum com uma “velocidade de porta” de 66,7 megahertz. Os portões são as operações quânticas. Os cientistas calculam que este computador quântico conseguiria 224 iterações de grover por segundo.
Significado? 224 iterações de Grover correspondem a uma taxa de hash de 78 megahashes por segundo. Esta é uma proporção absolutamente microscópica do hashrate Bitcoin, de facto, apenas uma pequena fracção do que a Asics moderna consegue. Seria ridículo cheirar aqui o perigo.
Likely to be more power efficient in the future
But if quantum miners pose no threat – are they are at least more efficient? Então, pode haver, pelo menos gradualmente, uma conversão para a mineração quântica? E em que momento?
Para ser mais eficiente, o custo energético de uma iteração Grover deve ser no máximo 3,49 x 105 vezes o custo de um haxixe clássico. Em comparação com os mineiros clássicos, que têm uma eficiência energética de 10-10 Jules por hash, um computador quântico precisaria de uma eficiência superior a 3,49 x 105 x 10-10, ou cerca de 10 μJ por iteração de Grover. Ou 2240 μJ por segundo.
Isso soa extremamente baixo. Mas os computadores quânticos são muito eficientes do ponto de vista energético. Assim que o sistema é arrefecido para 15 millikalvin, ou seja, perto do zero absoluto, os bits quânticos tornam-se um supercondutor: praticamente não precisam de electricidade e não produzem praticamente nenhum calor. Actualmente, o arrefecimento em relação à potência ainda torna um computador quântico antieconómico. Mas isto é susceptível de mudar à medida que a tecnologia avança.
Assim, em suma, como Bitcoiners, podemos dormir descansados e um pouco mais sábios e sonhar sem terror com um futuro de computadores quânticos.