Quais os impactos da computação quântica para o Bitcoin e altcoins?

Embora distante da realidade, a computação quântica representa sim uma ameaça as criptomoedas, mas não se preocupe, temos tempo! Entenda o porquê.

Figura 1 — D-Wave — computador quântico de 2000 qbits

Disclaimer do autor: Antes de tudo, eu sinto que devo alertá-lo para que não acredite em nenhuma palavra do que está escrito aqui. Verifique. Não sou especialista em nada, muito menos em criptografia ou física. Me identifico como um “estudante amador de criptografia”. As opiniões aqui emitidas são baseadas em diversas conversas que tive com professores da área de criptografia (estes sim especialistas) e leitura pessoal. Por favor, não interprete isto como “hate ao Bitcoin”. Eu adoro o protocolo. Gostaria apenas de levantar algumas questões (algumas não tenho exatamente a resposta) e contribuir com algo. Faço questão de escrever isto porque, na Internet, algumas pessoas tendem a interpretar as coisas de forma equivocada. Adoraria ler a sua opinião. Você pode deixar um comentário na caixa de comentários deste post. O intuito deste post é alertar para a ameaça que está por vir. Temos muito tempo até os computadores quânticos se tornarem uma ameaça. Mas precisamos nos preparar. É sério.

Aos especialistas: alerto que este “artigo” está escrito em uma linguagem mais natural (diferente do que estou acostumado a usar na academia) e por vezes, vou utilizar termos mais simples e ter explicações rasas sobre assuntos de grande complexidade.

Se você não tem paciência para ler, você pode assistir ao meu vídeo:

https://www.youtube.com/watch?v=5C-1NzFUL5A

1 — O que é computação quântica? (Introdução ao tema)

Resumidamente, a computação quântica [1] é uma nova forma de computação. Entenda o “computação” como “cálculo”. Cálculo quântico. Nos computadores convencionais, o portador da informação é o elétron, nossos computadores são, portanto, eletrônicos. Temos ainda um sistema binário, isto é, de dois estados, 0 ou 1, sendo que na maioria das vezes estes estados representam “ausência” e “presença” de energia (podendo ser também o contrário). No sistema binário a matemática é um pouco diferente de um sistema decimal que estamos acostumados, pelo facto de estarmos trabalhando com conjuntos finitos [2]. Uma multiplicação ou soma no sistema binário é bastante diferente de uma soma ou multiplicação utilizando outros conjuntos numéricos (como os inteiros). Há diversas outras operações, funções matemáticas por assim dizer (NOT, AND, OR, XOR, NOR, NAND [3]), com teoremas matemáticos diferentes do que estamos acostumados com a matemática convencional. Essa é a computação binária [4] da qual muitos de nós estamos familiarizados.

Figura 2 — Na computação convencional, representamos os dados por meio de bits, que podem assumir estado 0 ou 1.

De forma análoga, a computação quântica possui um portador, que pode ser um fóton, um elétron, etc. Entretanto, ao invés de utilizar a tensão que as partículas exercem num meio, a computação quântica utiliza dos efeitos quânticos das partículas (daí o nome computação quântica), para obter vantagem no cálculo. Como sabemos desde o século passado, desde o advento da mecânica quântica [5], área da física que estuda os efeitos quânticos, as partículas podem ter propriedades estranhas às propriedades clássicas que estamos acostumados. Como o emaranhamento quântico [6], superposição quântica [7], teleporte quântico [8], tunelamento quântico [9] entre outros efeitos.

Figura 3 — Na computação quântica, utilizamos qbits para representar dados. Qbits estão em superposição de 0 e 1. Os qbits colapsam quando são medidos ou quando sofrem decoerência quântica.

Um dos principais efeitos utilizados na computação quântica, mas não o único, é a superposição quântica, que permite que uma partícula esteja em dois (ou mais) estados simultâneos até que ela seja medida. Este efeito é bastante explorado, pois permite guardar mais de um estado em um qbit (quantum bit) [10]. Ao invés de termos os estados 0 ou 1, e aqui alerto que a conjunção “ou” é extremamente importante para o entendimento da computação quântica, podemos ter 0 e 1 e “indefinido” e outros estados, salvos no mesmo qbit, simultâneamente. O emaranhamento quântico é outro efeito bastante explorado, pois permite saber o estado de uma outra partícula que está emaranhada a primeira, sem precisar medir esta segunda partícula. Além de possibilitar a “computação” quântica (no sentido de cálculo), a mecânica quântica permite transmissões quânticas, que são instantâneas [11a][11b]. Sim, transmissões acima da velocidade da luz. Isto é apenas uma amostra dos princípios de mecânica quântica aplicados a computação.

Figura 4 — Qbits

Um dos efeitos práticos da computação quântica é que um circuito quântico pode calcular todas as suas configurações ao mesmo tempo. Por exemplo, enquanto na computação convencional um computador provido de um contador de 4 bits (que conta números de 0 até 15) precisaria passar por todos os estados, o computador quântico conta todos estes estados simultâneamente. Outra implicação importante é que, neste caso, cada qbit adicionado aumenta o poder de cálculo exponencialmente. O computador quântico é capaz de contar de 0 a 15 em apenas uma ronda de computação com seus 4 qbits. Se este computador quântico tiver 20 qbits, ele pode armazenar não somente 16 estados, mas 1.048.576 estados. Adicionamos apenas mais um qbit e vemos o poder de computação dobrar, indo para 2.097.152 estados. Um computador convencional precisaria passar por cada um destes estados por vez. Um computador quântico já faz isso em uma única vez.

Figura 5 — Um computador quântico é capaz de computar muitos estados simultâneos.

Naturalmente, uma computação diferente, possui “operadores” diferentes. Pois estamos aqui tratando de uma “matemática diferente”. Ao contrário da computação clássica, os computadores quânticos utilizam de portas lógicas quânticas [12–13]. E enquanto os estados dos computadores clássicos são estáveis, pois já dominamos a eletrônica há anos, os estados quânticos são instáveis. Isto é, suscetíveis a decoerência quântica [14]. Computadores quânticos exigem resfriamento próximo ao zero absoluto, momento em que alguns elementos químicos, como Nióbio, se tornam supercondutores. Exigem também câmaras de vácuo e uma série de aparatos sofisticados. É uma ciência ainda em desenvolvimento, mas que possibilitará a otimização de diversos cálculos matemáticos. Em conjunto com a eletrônica, spintrônica [15], fotônica [16], computação neuromórfica [17–19], computação biológica [20–23] e outros tipos de computação, estes avanços levarão o desenvolvimento tecnológico a patamares inimagináveis.

1.1 — Tipos de computação quântica

Figura 6 — Tipos de computadores quânticos

Como visto na imagem acima, há basicamente três tipos de computadores quânticos. O computador capaz de causar algum impacto nas criptomoedas é o famoso “quântico universal”. Este computador é extremamente difícil de ser construído, visto que tem de manter a coerência quântica das partículas. Eu nem sei como começar a explicar o desafio científico de se construir um computador quântico desta natureza. Mas é maior do que você pode imaginar. Para ser construído, necessitaria de diversas câmaras de vácuo, muitos litros de nitrogênio líquido e a fabricação de chips sofisticados. Mas não somente isto, o local onde o computador quântico fica é “especial”. Com um imenso bloco de concreto embaixo (para aliviar vibrações), um anulador de ondas eletromagnéticas (tal qual os que existem em aceleradores de partículas e laboratórios com microscópios por transmissão de elétrons), uma série de aparatos sofisticados e pessoas com grau de PhD para operá-lo. Mesmo com todo desafio científico e tecnológico, acredito que este computador será construído em até duas décadas, no máximo.

Este computador é capaz de resolver problemas criptográficos, como a fatoração de números primos (importante para a criptografia RSA [24]) e o problema do logarítimo discreto para curvas elípticas [25][26] em pouco espaço de tempo.

1.2 — Algoritmos quânticos

Um mito a respeito da computação quântica é o que ela resolverá todos os problemas de maneira muito mais rápida que computadores normais. Isto não é verdade. Há problemas impossíveis de serem resolvidos, há problemas que não são resolvidos por computadores quânticos e também aqueles que são piores de se resolver em computadores quânticos ou que seriam melhor executados em um computador normal (até por uma questão de custo). Os computadores quânticos exigem algoritmos quânticos, que explorem os efeitos como a superposição quântica para acelerar os cálculos. Existem poucos algoritmos quânticos e o advento da computação quântica traz a necessidade da criação de software específico para estas máquinas. E escrever algoritmos quânticos não é como escrever algoritmos clássicos. É coisa de gênio. Exige muito domínio matemático. Por isto temos poucos algoritmos quânticos.

Dentre os algoritmos mais conhecidos estão: O Algoritmo de Shor [27], o Algoritmo de Grover [28], o Contador Quântico (explicado anteriormente), A Transformada de Fourier Quântica [29] entre outros [30–36].

2 — Pontos de fragilidade no Bitcoin e nas demais criptomoedas

De maneira geral, há dois pontos de fragilidade nas criptomoedas, são eles: assinatura e consenso (mineração inclusa).

Figura 7 — Bitcoin

2.1- Assinatura

O Bitcoin utiliza para assinatura das transações a criptografia de curvas elípticas [26], conhecidas como “ECCs”. Este tipo de criptografia possui chaves muito menores, porém com a mesma segurança de chaves grandes de outros tipos de algoritmos assimétricos, como RSA. O Bitcoin utiliza uma curva matemática conhecida como secp256k1 [37a][37b]. O “SEC” no nome, vem de Standards for Efficient Cryptography [38]. O Bitcoin utiliza ainda chaves de 2²⁵⁶ bits [39], isto é, um número com 77 casas decimais.

Conforme eu expliquei aqui, é impossível quebrar uma chave de Bitcoin utilizando computação convencional.

115792089237316195423570985008687907853269984665640564039457584007913129639936
Este é o total de possibilidades de chaves do Bitcoin. Grande, não?
Figura 8 — A curva matemática secp256k1 no conjunto dos reais [40].

Mesmo que seja impossível fazer um ataque de força bruta na criptografia de curvas elípticas [40] com computadores convencionais, é possível atacá-las por meio do Algoritmo de Shor modificado para curvas elípticas. Também conhecido como “O Algoritmo de Shor para Curvas Elípticas” [41]. Este tipo de ataque quebraria (supostamente) com a segurança do ECDSA [42], que é o algoritmo utilizado no Bitcoin para realização de assinaturas. Como consequência, alguém que tenha um computador quântico poderia facilmente forjar assinaturas de Bitcoin e mover os fundos de outrem. Será?

Figura 9 — Com o advento da computação quântica, vários algoritmos clássicos deixarão de ser seguros, dando lugar a criptografia pós quântica.

Felizmente, acredito que esta é a maneira mais improvável do Bitcoin ser atacado. Por três motivos. Primeiro: Resolver o problema do logarítimo discreto para curvas elípticas exige uma certa quantidade de qbits. No caso de chaves de 256 bits, são necessários exatos 1560 qbits [43][62]. Manter tantos estados quânticos coerentes é um desafio grande. Lembra do desafio científico? Pois é. A computação quântica é a ciência de controlar o estado quântico de partículas para realizar computação (cálculos). Yeap. Estou falando de controlar o estado de fótons e elétrons individualmente, sem que entrem e decoerência quântica. E se o desafio é grande para apenas um elétron, imagine controlar 1560 destes elétrons.

Figura 10 — O algoritmo assimétrico RSA terá que ser abandonado com o advento da computação quântica.

A título de exemplo, para quebrar um RSA de 2048 bits, seria necessário capturar 2.1⁰⁹ íons, o que exigira 23x23 câmaras de vácuo ocupando uma área de 103.5 x 103.5m² [45a]. Segundo Lekitsch et al, quebrar o RSA 2048 custaria 110 dias, ao passo em que quebrar um RSA 1024 demoraria apenas 14. Entretanto, os autores do artigo afirmam que com otimizações no código e com correção de erros, isto poderia diminuir em uma ordem de grandeza, utilizando o mesmo equipamento [45a]. É muito provável que as técnicas existentes hoje avancem de forma significativa nos anos seguintes, seguindo a famosa e já conhecida Lei de Moore. Falando de forma leiga, você se lembra da tecnologia que tínhamos no ano 2000? E no ano de 2008? Agora, tente imaginar o cenário daqui a 10 ou 20 anos e, não subestime a capacidade humana de fazer coisas fodas.

Embora D-Wave 2000 [45a] afirme ter 2000 qbits, este computador não representa ameaça, pois não é um computador quântico universal e sim da classe dos quantum annealing [45b]. Resumidamente, ele não serve para quebrar criptografia e sim para outros tipos de cálculos. Ufa.

Figura 11 — Resolver o problema do logarítmo discreto para curvas elípticas com uma chave de 256 bits, exige um computador quântico universal de 1560 qbits.

Segundo: o Bitcoin é resistente a computação quântica na assinatura se os endereços não forem reutilizados. Isto se deve a forma como os endereços de Bitcoin são constituídos. A chave pública é protegida por uma função, que leva um hash. Como a chave pública está “hasheada”, o computador quântico não tem como atacar a chave pública a fim de se obter a chave privada. A chave pública do Bitcoin só se torna de facto pública para rede, isto é, registrada no Blockchain, quando o detentor da chave privada faz uma transação.

Figura 12 — A maneira como os endereços de Bitcoin são criados esconde a chave pública. Endereços de Bitcoin não são a chave pública. Você é foda Satoshi Nakamoto.

Uma maneira de se impedir que os computadores quânticos ataquem o Bitcoin é evitando a reutilização de endereços. Sempre que se for mover os fundos de uma carteira, deve-se mover os fundos restantes para outra carteira. Por exemplo, suponha que eu tenha 10 Bitcoins em uma carteira e precise enviar 1 Bitcoin para Marcos. Para se proteger de um computador quântico, devo mover os outros 9 Bitcoins restantes para uma outra carteira em minha posse. Ou ainda, criar dois outputs com dois scripts diferentes. Mas há uma maneira melhor…

Terceiro: Lamport Signatures. Com o advento da computação quântica, os criptólogos estão preocupados em criar algoritmos mais resistentes, a chamada “criptografia pós quântica” [46], isto é, algoritmos criptográficos resistentes aos ataques que computadores quânticos podem fazer. O assunto assusta tanto os criptólogos que um concurso do NIST está sendo realizado no momento em que escrevo este artigo [47].

A boa notícia é que o SegWit [48] permite que um novo tipo de algoritmo seja utilizado para assinatura das transações. Trata-se das Lamport Signatures [49a-49e], um algoritmo que, ao contrário da criptografia de curvas elípticas, é resistente a computação quântica.

Portanto, neste ponto (assinatura), eu creio que a ameaça seja pequena ou inexistente.

2.2 Mineração

Mineração [50] é o processo responsável pelo consenso do Bitcoin, pela validação das transações e pela criação de novos Bitcoins. Assumindo que você leitor já está familiarizado com este conceito, vamos adentrar um pouco mais e entender como a computação quântica afeta o Bitcoin.

De forma simplória, os mineradores estão tentando encontrar um número (nonce) que satisfaça o seguinte:

SHA-256(SHA-256(Informações do bloco + nonce) < Target

Sendo:

  1. SHA-256 [51]: Um dos algoritmos de hash utilizados no Bitcoin. Tudo que você precisa saber neste momento é que a função hash recebe uma entrada (pode ser algo bem pequeno ou muito grande) e “cospe” um número. Este número possui um tamanho fixo e pode conter “0"s na frente.
  2. “Informações do bloco”: Tamanho do bloco, cabeçalho, transações, quantidade de transações, timestamp, dificuldade e outros dados…
  3. Nonce [52]= Um número arbitrário. Uma das únicas coisas que podem ser alteradas no intuito de minerar (satisfazer a fórmula que definimos acima)
  4. Target [53]= Um número que representa a “dificuldade” da mineração. Quanto menor este número, mais difícil é minerar.

Resumidamente, a mineração é o processo onde tentamos “chutar” um número (Nonce), colocando este número em conjunto com outras informações (informações do bloco), posteriormente estes dados passam por duas vezes por uma função hash, que “cospe” um número com quantidade de algarismos fixo. Depois temos que torcer para este número final seja menor que outro número, o já citado “target”. A mineração é um processo onde chutamos um número em uma função e torcemos para este número ser menor que outro número. Se você não entendeu, vou dar outro exemplo.

Figura 13 — Estrutura típica de um bloco [54]

A mineração consiste basicamente em um sorteio onde o ticket é o nonce. Você pode fazer quantas apostas quiser (tentativas de nonce) desde que tenha poder computacional para isto, pois é uma loteria extremamente difícil de acertar. É importante que você tenha bastante poder computacional, pois quanto mais poder computacional, maiores são as suas chances de encontrar um nonce válido antes do restante da rede e resgatar o seu prêmio de 12.5 Bitcoins, fazendo com que as transações sejam “processadas” pela rede. Mineração é um grande sorteio mundial que acontece a cada 10 minutos. Você pode apostar a quantidade de vezes que quiser, mas precisa de poder computacional para isto.

Figura 14 — O blockchain

2.2 O contador quântico e o algoritmo de Grover — Combinação mortal?

Nota: Eu não estou totalmente certo destas informações. Escrevo este texto principalmente para que alguém verifique e analise se isto faz sentido ou não. Adoraria que alguém encontrasse um erro no meu raciocínio. Pois esta é a parte que mais me preocupa (mineração).

No primeiro capítulo deste texto vimos que utilizando os efeitos de superposição quântica é possível contar números de maneira muito mais rápida. É neste ponto onde, possivelmente, está a fragilidade do Bitcoin, pelo simples motivo do algoritmo de mineração, o Proof-of-Work [55] especificamente, ser um ato de contar e testar números ou simplesmente testar números, já que os números podem ser testados com uma sequência aleatória ou pseudoaleatória (Você pode apostar com tickets 1,2,3,4,5… ou escolher números aleatórios).

Figura 15 — Computadores quânticos são extremamente rápidos em buscar itens em uma lista.

Além de serem bons em contar, computadores quânticos podem, em teoria, buscar itens em uma lista de maneira muito mais rápida que um computador normal. É sabido que o Algoritmo de Grover reduz a complexidade de certos algoritmos em O(√n), o que significa dizer, em termos leigos, que um algoritmo AES, com “complexidade de 128 bits”, seria resolvido tal qual como um AES com chave de 64 bits (supondo que existisse este algoritmo com este tamanho de chave). Computadores quânticos são bons em resolver caixas pretas. Da mesma forma, o algoritmo SHA-256 utilizado no Bitcoin, que é uma função de hash, teria a sua complexidade diminuída pela raiz quadrada, o que torna o problema exponencialmente mais fácil de ser resolvido.

Figura 16 — Computadores quânticos reduzem a complexidade de certos algoritmos pela raiz quadrada.

Segundo o professor da UNICAMP, Dr. Serguei Popov, no seu artigo “The Tangle” (whitepaper da IOTA [56]), um minerador usando computação clássica, testa em média 2⁶⁸ nonces até encontrar um hash satisfatório que valide um bloco (como mostrado na equação anteriormente). Entretanto, um computador quântico poderia, em teoria, executar esta função com a raiz quadrada das operações, diminuindo o problema de 2⁶⁸ para √2⁶⁸ =>2³⁴ com uso do Algoritmo de Grover. O que torna a mineração por computadores quânticos cerca de 17 bilhões de vezes mais eficiente do que a mineração clássica. Aqui está o cálculo de onde o professor Popov tirou este número gigante.

Figura 17 — Trecho do whitepaper da IOTA. O artigo do professor Popov me inspirou a escrever este texto tentando explicar de uma maneira mais simplória.

3 E agora?

3.1 Monopólio da computação quântica?

Com uma mineração 17 bilhões de vezes mais eficiente, as placas de vídeo ou ASICs não teriam chances para resolver o problema na mineração antes do computador quântico e portanto, os computadores quânticos (ou “O computador quântico”, caso exista apenas um nesta altura) teria o monopólio sobre a mineração, podendo até mesmo, fazer um ataque de 51%. Até que, depois de 2016 blocos [57] a dificuldade do Bitcoin seria reajustada e a mineração por computação quântica também ficaria complicada (pois até então a dificuldade estava ajustada para placas de vídeo) e o computador quântico iria minerar o bloco nos mesmos 10 minutos que uma placa de vídeo minera hoje. Se os detentores do computador quântico desistirem da ideia, demoraria duas semanas até que as placas de vídeo pudessem voltar a ativa.

Acredito que a esta altura, não existirão muitas empresas com computadores quânticos (tudo tem que começar com uma, acredito que é difícil duas empresas criarem o computador quântico na mesma semana). Isto seria o fim da mineração por placas de vídeo e tornaria o consenso totalmente centralizado na mão da primeira empresa que conseguir fabricar um computador quântico.

Porém, tudo parece muito teórico e utópico, não é mesmo? Qual o incentivo que uma empresa poderia ter para exercer este ataque?

3.2 Incentivos pessoais, financeiros e políticos

Embora não tenha sido minha intenção dar uma resposta do porquê alguém atacaria o Bitcoin, se isto é economicamente viável ou não, achei melhor fazê-lo. Mas tenha em mente que estou apenas teorizando se o ataque é possível ou não. Como ficará claro no texto, é um ataque extremamente custoso. Mas que pode ser feito.

Pesquisadores geralmente querem escrever o seu nome na história. Muitas vezes, eles renunciam de tudo, até mesmo de ganhar dinheiro. Mas não renunciam de serem citados nos seus trabalhos. Acredito que um dos maiores incentivos para alguém exercer um ataque com um computador quântico ao Bitcoin seria este, o de “escrever o nome na história”. Com toda certeza que o primeiro criptólogo, matemático ou pesquisador que fizer um ataque desta natureza será lembrado por gerações. Mas isto pode parecer um incentivo pequeno para você e venho aqui lembrar que existem outros incentivos além destes.

3.2.1 O cálculo com papel de pão.

Como este artigo pretende ser escrito de uma maneira simples, me limitei a fazer um cálculo que um estudante do Ensino Médio seja capaz de entender.

Para nosso cálculo, vamos levar em conta alguns fatores:

  1. Suponha que os computadores quânticos só sujam em 2028, 10 anos após eu ter escrito este textão.
  2. Suponha que o Bitcoin permaneça na casa dos $6500 dólares, o que particularmente acredito ser bem difícil, mas é a cotação da data em que estou escrevendo este artigo.

(UPDATE: Bitcoin a $6.300, preferi deixar o cálculo com $6500)

3. Suponha que o computador quântico daqui uma década, custe 10 milhões de dólares, o mesmo preço de um D-Wave 2000 [58](leve em conta a Lei de Moore).

Em 2018 o Bitcoin tem uma recompensa de 12.5 Bitcoins por bloco. Em 2022 essa recompensa cairá para 6.25, em 2026 para 3.12 e permanecerá em 3.12 em 2028, pois os halvings só acontecem de 4 em 4 anos. Logo, o Bitcoin terá uma recompensa aproximada de 3 Bitcoins por bloco (vamos arredondar, pois estamos fazendo um cálculo em papel de pão né).

3 Bitcoins * $6.500 = $19.500 por bloco.

Entretanto, acredito que dado a grande vantagem da computação quântica, haveria um monopólio da mineração, e o computador quântico poderia em teoria, minerar 2016 blocos sozinho, em menos de duas semanas.

2016 blocos * 3 Bitcoins * $6.500 dólares = $39.312.000

Em menos de duas semanas, o computador quântico obteve um ROI. de 4x o seu valor. E poderia, se os detentores dele quiserem, continuar minerando. Isto parece um incentivo grande o suficiente para construir um computador quântico?

3.3 Quão distantes estamos dos computadores quânticos?

Segundo certas estimativas, de 10 até 20 anos [59]. Note que estas estimativas preveem apenas o surgimento de um computador quântico universal, que é algo extremamente sofisticado (Particularmente, acredito que computadores quânticos nunca ficarão baratos o suficiente para se tornarem computadores pessoais devido a complexidade de serem criados e operados, mas este não é o ponto. Só é necessário UM computador para atacar o Bitcoin).

Deixarei aqui uma lista com empresas que estão investindo em pesquisa em computação quântica [60]. Particularmente acredito que o Bitcoin ajudará a computação quântica. Assim como a indústria de ASICs e placas de vídeo se desenvolveu devido ao Bitcoin, o mesmo acontecerá com a computação quântica. Em outras palavras, o Bitcoin pode se tornar um agente financiador da próxima geração de computadores.

3.4 Impactos em outras moedas

3.4.1 Nano

Como observado, o Bitcoin, no protocolo atual é vulnerável no algoritmo de mineração e resistente na assinatura (se as chaves não forem reutilizadas). Na criptomoeda Nano ocorre o contrário. A assinatura é totalmente vulnerável devido ao fato da chave pública estar exposta no próprio endereço. Isto é, o que vem depois de “xrb_” é uma chave pública. O mesmo não ocorre no Bitcoin devido a maneira como os endereços são criados. Um computador quântico precisa apenas da chave pública para efetuar um Ataque de Shor.

Ao contrário do Bitcoin, a criptomoeda Nano não possui mineração. Portanto, não há este vetor de ataque. A Nano é resistente a computação quântica no PoW, pois um PoW pequeno não é vantajoso usar um computador quântico, como veremos a seguir.

Status: Vulnerável na assinatura, segura no PoW.

3.4.2 IOTA

Iota é uma moeda resistente a computação quântica. De forma resumida, temos um algoritmo de assinatura baseado em hash, o W-OTS [61](Winternitz type one-time signature scheme), que é um tipo de algorimo “quantum-proof” ou da classe dos “pós-quânticos”. O algoritmo força o usuário a não reutilizar os endereços e a criar um endereço novo a cada transação, o que torna o algoritmo mais seguro ainda a computadores quânticos. Entretanto devo aqui fazer um alerta, este tipo algoritmo particular não foi testado com todo rigor que outros algoritmos já consolidados. É um algoritmo que alguns criptólogos definiriam como “exótico”. Particularmente, eu não gosto disto. Também penso que forçar os usuários a criarem um novo endereço a cada transação induz ao erro. Tenho muitos casos de amigos que perderam Iotas por que não sabiam que transferir duas vezes ou mais do mesmo endereço, “revela” a chave privada (A cada nova transação feita a partir da mesma chave torna o trabalho de descobrir a chave privada exponencialmente mais fácil). Mas sim. Iota é resistente a computação quântica [63]e não tem mineração.

Status: Resistente na assinatura e no PoW. Porém possui um algoritmo “exótico”.

3.4.3 Ethereum

Endereços Ethereum são hashs da chave pública como no Bitcoin. Ethereum usa PoW/PoS no consenso. Ethereum pode usar Lamport Signatures [64] no futuro. Quantum safe! [65] Por mais estúpidos que alguns projetos de ICOs possam ser, também entram no bolo.

Status: Tão seguro quanto o Bitcoin na assinatura. Consenso híbrido de PoW/PoS.

3.4.4 Cardano

Cardano usa PoS e seu roadmap [66] menciona “lattice based cryptography” [67](veja a Figura 9). O roadmap diz que essa funcionalidade está 50% implementada (no momento em que escrevo este textão). “Quase” quantum safe. Estão quase lá.

Status: Consenso PoS (Sai pra lá Grover!). Assinatura com “Lattice based Cryptography” em desenvolvimento. Segura no consenso. “50%” segura na assinatura.

3.5 Possíveis soluções

Dado a fragilidade do Bitcoin na mineração, o protocolo terá que mudar um dia. De fato, a mineração é o que o Bitcoin trouxe de novo. Os algoritmos de criptografia assimétrica já existiam antes do Bitcoin, algoritmos de consenso também. O feito genial de Satoshi Nakamoto, na minha humilde opinião, foi criar a mineração (PoW) e no protocolo de um algoritmo de consenso, uma “política monetária” impossível de ser alterada e que ao mesmo tempo, distribui Bitcoins aleatoriamente pelo mundo, ao mesmo tempo em que recompensa eficiência. A mineração é algo novo na história da computação. E é natural que ela não seja perfeita. Devido a este fato, muitos outros algoritmos de mineração e consenso surgiram. Uma possível saída mais rápida para o Bitcoin é a alteração do consenso e da mineração para um sistema Proof-of-Stake ou PoW/PoS híbrido como fez Ethereum. Entretanto, como alguém mais “purista”, esta alteração não me agrada muito.

3.5.1 “Mini blocos”

A vulnerabilidade do Bitcoin perante a computação quântica se deve a complexidade do Proof-of-work. Quanto mais complexo, mais vantagem o computador quântico obtêm perante a computação comum. E… ao contrário do senso comum, “mais dificuldade” não significa “mais segurança”. Mais dificuldade apenas torna o gasto de energia maior, exigindo mais hardware, mais recurso ao mesmo tempo que torna o consenso mais centralizado em grandes mineradoras. Em outras palavras, reduzir a complexidade do Proof-of-work é um requisito sine qua non para tornar o Bitcoin (com o protocolo atual) resistente a computação quântica. Reduzir o PoW ou alterar totalmente o consenso para PoS ou algo semelhante. Porém, a “dificuldade” de se resolver o PoW não pode ser muito pequena. Ela precisa ter um custo. Uma “dificuldade” pequena permite ataques de spam. O Bitcoin fornece um mecanismo natural de “desincentivo de spam”, que são as taxas de transação. O mesmo não ocorre em criptomoedas sem taxas (como Nano, Iota e transações com LN) que frequentemente sofrem de spam.

Acredito que há muitas maneiras de resolver isto. Como entusiasta de Bitcoin que sou, procurei pensar em como eu resolveria isto sem alterar o consenso para PoS. Ao mesmo tempo, penso em maneiras apropriadas de escrever este texto sem parecer arrogante ou sem ofender a “criptoreligião” de alguém. Isto não precisa ser resolvido “da minha maneira”, também não quero que me considerem como “dono da verdade”, mas adoraria uma resposta a este texto mostrando que estou errado (com argumentos). Se e quando isto acontecer, adicionarei uma nota complementar a este texto. Por favor, se você notou um erro no meu raciocínio, escreva uma resposta, é um favor que você me faz me corrigindo, pois assim aprendo mais. O problema da computação quântica é algo que tem me deixado preocupado quanto o futuro do Bitcoin. Acredito que seja um problema que nós, entusiastas de Bitcoin, teremos que resolver em qualquer momento entre 2018 e 2028.

A solução que pensei foi um sistema de “mini blocos”. Isto é, blocos mais constantes e com PoW reduzido. Algo parecido com o que acontece com a LISK, que tem blocos de 10 segundos [68]. Ao invés de um bloco a cada 10 minutos, 1 bloco por minuto (ou algo semelhante), com PoW bem menor do que o utilizado atualmente. Um PoW que placas de vídeo consigam fazer em segundos. Isto tira a vantagem da computação quântica perante as placas de vídeo e ASICs e, adicionalmente, melhora o consenso do Bitcoin. Computadores comuns poderão participar do consenso novamente, ajudando a descentralizar a rede. O tempo de confirmação diminuirá e como cada “mini bloco” poderá ter 1Mb, 512KB (ou outro valor arbitrário), aumentará a quantidade de transações da rede, diminuindo o gargalo. A recompensa permanecerá a mesma, entretanto, ela será dividida para os “mini blocos”. Ao invés de 12.5 Bitcoins para 1 bloco, teremos algo como 1.25 Bitcoins para 1 mini bloco ou coisa parecida, mantendo a quantidade de Bitcoins emitida a mesma que Satoshi planejou.

Bem, isto não precisa ser resolvido da minha maneira. É apenas um exercício de imaginação. Meu ponto aqui é que o consenso do Bitcoin precisará ser alterado visando proteger de ataques quânticos. Como resolver isto? Eu não sei. Por isto escrevi este texto. Para encontrar alguém que saiba. De qualquer forma, acredito que este tipo de solução só pode ser feita com um hardfork, dado que o algoritmo de consenso precisará ser alterado.

4. Conclusão

O Bitcoin já é resistente a computação quântica na assinatura, entretanto, o algoritmo de mineração no protocolo atual torna vantajosa a utilização de computadores quânticos, o que poderá tornar a rede mais centralizada com 1, 2, 3 computadores quânticos minerando todos os Bitcoins e destruindo o consenso ou tornando o consenso extremamente centralizado, o que vai contra a filosofia do Bitcoin de descentralização. Entretanto, o Bitcoin pode prover o incentivo nece$$ário para o desenvolvimento da próxima era da computação.

A computação quântica se tornará realidade e com ela virá uma nova era para criptografia, a criptografia pós quântica. Nós, cypherpunks, temos duas opções: Ignorar a ameaça que está por vir ou utilizar a ameaça como um incentivo e tornar o protocolo ainda mais seguro.

Uma nova era da computação se iniciará. Mudanças de paradigmas de computação são eventos extremamente raros. Tivemos a “Era da computação digital”, com Alan Turing, a “Era da computação pessoal”, com Steve Jobs e Steve Wozniak, a Era da Internet das Coisas, com Mark Weiser e em breve cypherpunks, teremos a Era da computação quântica. Eu não sei quem escreverá o seu nome na história desta vez, mas os impactos do que está por vir irão alterar para sempre nossas vidas.

A criptografia pós quântica, comunicações quânticas e o poder de processamento de dados advindo da computação quântica irá diminuir a interferência estatal nas comunicações ao mesmo tempo em que melhora nossas vidas. Mas, para isto, é preciso preparar o terreno. Criptografia é uma munição e estamos em guerra. Uma guerra silenciosa. Você pode discordar de mim, mas não pode negar a importância da criptografia para as guerras. Não é uma guerra com armas para conquistar território físico. É uma guerra monetária para alcançar a liberdade e manter algo que chamo de “propriedade digital” ou “propriedade artificial”. Algo que Timothy C. May [69] chamava de “cyberespaço” [70]. Podemos usar criptografia para alcançar a liberdade financeira e tecnológica que tanto queremos, ou permitir que as agências de segurança façam uso do poderio tecnológico da computação quântica e acabe com o consenso do Bitcoin. Em verdade, estou preparando um outro texto onde irei expor uma ameaça mais grave do que a computação quântica. Os algoritmos criptográficos usados na maioria das criptomoedas são feitos por agências governamentais. E, na minha humilde opinião, isto é muito grave.

Temos em torno de 10 anos para tornar o Bitcoin mais seguro. Tempo não é desculpa.

Tic tac…

Agradecimentos a Pedro Xavier pela revisão deste texto.

5. Referências:

[1]https://pt.wikipedia.org/wiki/Computa%C3%A7%C3%A3o_qu%C3%A2ntica
[1b]https://pt.wikibooks.org/wiki/Breve_introdu%C3%A7%C3%A3o_%C3%A0_computa%C3%A7%C3%A3o_qu%C3%A2ntica
[2]https://pt.wikipedia.org/wiki/Corpo_finito
[3]https://pt.stackoverflow.com/questions/63215/o-que-s%C3%A3o-os-operadores-l%C3%B3gicos-e-como-funciona-as-opera%C3%A7%C3%B5es-bit-a-bit-na-lingua
[4]https://pt.wikipedia.org/wiki/Sistema_de_numera%C3%A7%C3%A3o_bin%C3%A1rio
[5]https://pt.wikipedia.org/wiki/Mec%C3%A2nica_qu%C3%A2ntica
[6]https://pt.wikipedia.org/wiki/Entrela%C3%A7amento_qu%C3%A2ntico
[7]https://pt.wikipedia.org/wiki/Sobreposi%C3%A7%C3%A3o_qu%C3%A2ntica
[8]https://pt.wikipedia.org/wiki/Teletransporte_qu%C3%A2ntico
[9]https://pt.wikipedia.org/wiki/Tunelamento_qu%C3%A2ntico
[10]https://en.wikipedia.org/wiki/Qubit
[11a]http://www.inovacaotecnologica.com.br/noticias/noticia.php?artigo=informacao-transferida-acima-velocidade-luz&id=010110150327
[11b]http://www.inovacaotecnologica.com.br/noticias/noticia.php?artigo=acao-fantasmagorica-distancia-mais-rapida-luz&id=010130130402#.Wy3JQVKJLIW
[11c]Bounding the speed of “spooky action at a distance”
Juan Yin, Yuan Cao, Hai-Lin Yong, Ji-Gang Ren, Hao Liang, Sheng-Kai Liao, Fei Zhou, Chang Liu, Yu-Ping Wu, Ge-Sheng Pan, Qiang Zhang, Cheng-Zhi Peng, Jian-Wei Pan
[12]M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000
[13]https://en.wikipedia.org/wiki/Quantum_logic_gate
[14]https://pt.wikipedia.org/wiki/Decoer%C3%AAncia_qu%C3%A2ntica
[15]https://pt.wikipedia.org/wiki/Spintr%C3%B4nica
[16]https://pt.wikipedia.org/wiki/Fot%C3%B4nica
[17]http://www.inovacaotecnologica.com.br/noticias/noticia.php?artigo=computacao-neuromorfica-vai-deixar-computacao-quantica-tras&id=010150180125#.Wy1h_oonbIU
[18]https://pt.wikipedia.org/wiki/Engenharia_neurom%C3%B3rfica
[19]https://jornal.usp.br/tecnologia/sistemas-de-computacao-baseados-no-cerebro-humano-ja-sao-realidade/
[20]https://motherboard.vice.com/en_us/article/d7ypqw/komiku-neuron-computer-agabi
[21]http://www2.uol.com.br/sciam/reportagens/computadores_de_dna_ganham_vida.html
[22]https://www1.folha.uol.com.br/tec/2016/03/1747400-o-homem-que-constroi-computadores-com-neuronios-vivos.shtml
[23]https://pt.wikipedia.org/wiki/Computador_de_DNA
[24]https://en.wikipedia.org/wiki/RSA_(cryptosystem)
[25]https://www.gta.ufrj.br/grad/06_2/renan/OProblemadoLogaritmoDiscretoemCurvasElpt.html
[26]https://pt.wikipedia.org/wiki/Criptografia_de_curva_el%C3%ADptica
[26b]https://en.wikipedia.org/wiki/Elliptic_curve_cryptography
[27]https://en.wikipedia.org/wiki/Shor%27s_algorithm
[28]https://en.wikipedia.org/wiki/Grover%27s_algorithm
[29]https://en.wikipedia.org/wiki/Quantum_Fourier_transform
[30]https://en.wikipedia.org/wiki/Quantum_walk
[31]https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm
[32]https://en.wikipedia.org/wiki/Quantum_counting_algorithm
[33]https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
[34]https://en.wikipedia.org/wiki/Aharonov%E2%80%93Jones%E2%80%93Landau_algorithm
[35]https://en.wikipedia.org/wiki/BHT_algorithm
[36]https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
[37a]https://en.bitcoin.it/wiki/Secp256k1
[37b]https://en.bitcoinwiki.org/wiki/Secp256k1
[38]http://www.secg.org/sec2-v2.pdf
[39]https://en.bitcoin.it/wiki/Private_key
[40]https://en.wikipedia.org/wiki/Elliptic_curve
[40b]https://en.bitcoin.it/wiki/File:Secp256k1.png
[41] https://arxiv.org/abs/quant-ph/0301141
[41b]https://dl.acm.org/citation.cfm?id=2011531
[42a]https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[42b]https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[43]https://arxiv.org/pdf/quant-ph/0301141.pdf
[44]http://advances.sciencemag.org/content/3/2/e1601540.full
[44b]http://sci-hub.tw/http://advances.sciencemag.org/content/3/2/e1601540.full
[45a]https://www.dwavesys.com/sites/default/files/D-Wave%202000Q%20Tech%20Collateral_0117F.pdf
[45b]https://www.theverge.com/circuitbreaker/2017/1/25/14390182/d-wave-q2000-quantum-computer-price-release-date
[46]https://en.wikipedia.org/wiki/Post-quantum_cryptography
[47]https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions
[48a]https://en.bitcoin.it/wiki/Segregated_Witness
[48b]https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
[48c]https://en.wikipedia.org/wiki/SegWit
[49a]https://en.wikipedia.org/wiki/Lamport_signature
[49b]http://cryptography.wikia.com/wiki/Lamport_signature
[49c]https://crypto.stackexchange.com/questions/42655/why-dont-crypto-currencies-use-the-lamport-signature-scheme
[49d]http://www.bitcoinnotbombs.com/bitcoin-vs-the-nsas-quantum-computer/
[49e]https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/
[50]https://en.bitcoin.it/wiki/Mining
[51a]https://pt.wikipedia.org/wiki/SHA-2
[51b]https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
[52a]https://en.bitcoin.it/wiki/Nonce
[52b]https://pt.wikipedia.org/wiki/Nonce
[52c]https://en.wikipedia.org/wiki/Cryptographic_nonce
[53]https://en.bitcoin.it/wiki/Target
[54]https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch10.asciidoc#block_header_structure_ch10
[55a]https://en.bitcoin.it/wiki/Proof_of_work
[55b]https://livecoins.com.br/proof-of-work-blockchain-bitcoin/
[55c]https://en.wikipedia.org/wiki/Proof-of-work_system
[55d]https://pt.wikipedia.org/wiki/Prova_de_trabalho
[56]http://www.iota.org/IOTA_Whitepaper.pdf
[57]https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin
[58]https://www.dwavesys.com/press-releases/d-wave-systems-previews-2000-qubit-quantum-system
[59]https://arxiv.org/abs/1710.10377
[60]https://en.wikipedia.org/wiki/List_of_companies_involved_in_quantum_computing_or_communication
[IBM]https://www.ibm.com/blogs/research/2017/11/the-future-is-quantum/
[Google]https://www.technologyreview.com/s/609035/google-reveals-blueprint-for-quantum-supremacy/
[61]https://eprint.iacr.org/2017/965.pdf
[62]https://crypto.stackexchange.com/questions/35137/how-many-qubits-are-required-to-break-rsa-2048-or-4096-with-a-universal-quantum
[63]https://hackernoon.com/why-bitcoin-fears-quantum-computers-and-iota-doesnt-697da531a11b
[64]https://www.youtube.com/watch?v=fbEtivJIfIU
[65]https://www.reddit.com/r/ethereum/comments/50cy0e/ethereum_quantum_resistant/
[66]https://cardanoroadmap.com/
[67]https://iohk.io/research/library/#ITK3N99B
[68]https://lisk.io/documentation/lisk-protocol/blocks
[69]https://www.activism.net/cypherpunk/crypto-anarchy.html
[70]https://nakamotoinstitute.org/crypto-glossary/

Ver também

1 — https://en.bitcoin.it/wiki/Difficulty
2 — https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
3 — https://github.com/bitcoin/bips
4 — http://inovacaotecnologica.com.br/noticias/noticia.php?artigo=brasileiro-cria-novo-design-radical-computador-quantico&id=010150170908#.Wt_gcn8h3IV
5 — http://fortune.com/2018/01/06/breaking-bitcoin-cybersaturday/
6 — https://www.esat.kuleuven.be/cosic/elliptic-curves-are-quantum-dead-long-live-elliptic-curves/
7 —https://www.coindesk.com/quantum-computers-private-keys/
8 — https://crypto.stackexchange.com/questions/35384/quantum-vs-regular-computing-time-to-break-ecc?rq=1
9 — https://security.stackexchange.com/questions/34940/is-ecdsa-breakable-by-quantum-computers
10 — https://crypto.stackexchange.com/questions/436/now-that-quantum-computers-have-been-out-for-a-while-has-rsa-been-cracked