Bitcoin y los computadores cuánticos

Como entusiasta de Bitcoin que soy, la gente de mi alrededor frecuentemente me lanza algunas afirmaciones a modo de reto. Por supuesto el clásico es que es un timo, un esquema piramidal, y esta afirmación suele ir acompañada de risas … Esta afirmación demuestra que o bien no saben qué es un esquema piramidal o bien no entienden Bitcoin (y en algunos casos ninguno de los dos). Otra afirmación muy frecuente es que “los gobiernos lo pararán” porque no les interesa. Esta no es tan absurda, porque es un hecho que al poder no le interesa perder parte del poder, con lo cual intentarán pararlo. No obstante lo que denota la afirmación es que no se han parado a pensar cómo. Cuanto más se piensa, más dificultades se encuentran.
Y de entre los más tecnológicos está la afirmación de que “cuando lleguen los ordenadores cuánticos será posible romper bitcoin” y por tanto no valdrá nada.

Esta afirmación es la que voy a analizar en este artículo.

Para analizar si esto es verdad o no, o , mejor dicho, en qué medida lo es, vamos a ver en primer lugar cómo es una transacción de bitcoin. Una transacción es un conjunto de bytes de información que indica que una cantidad de bitcoins se mueve de una dirección a otra, o, de forma más genérica, de m direcciones origen a n direcciones destino, de forma que el total de bitcoins en las m direcciones de origen es mayor o igual que el total de bitcoins en las n de destino.

¿Cómo se consigue que solo el dueño de los bitcoins de una dirección pueda moverlos?
Esto se consigue mediante criptografía de clave pública, en concreto, en Bitcoin, el sistema usado es el ECDSA (Elliptic Curve Digital Signature Algorithm). En un sistema de clave pública, cada usuario tiene una clave privada que sólo él conoce, kpriv y una clave publica kpub que, como su nombre indica, es pública. Para poder mover los bitcoins de una dirección a otra, es necesario “firmar” el mensaje (la transacción). Y para firmarlo es necesario la clave privada, por tanto, solo el poseedor de esta clave puede moverlos (gastarlos). Por supuesto la firma no desvela la clave privada, y para verificar la firma sólo es necesario la clave pública. (Para una explicación detallada ver (I)).

Con la clave privada hallar la clave pública es inmediato, pero la inversa no es posible. No es posible, en este ámbito, significa que no se conoce ningún algoritmo capaz de calcular la clave privada a partir de la pública salvo la fuerza bruta, es decir, probar con millones de claves privadas al azar y ver si alguna corresponde con la clave pública que tenemos. Como hay del orden de 2 elevado a 256 claves privadas (lo cual es aproximadamente mil millones de veces el número de atomos existentes en la Vía Láctea), ningún ordenador, ni todos los ordenadores del mundo trabajando juntos podrían calcularlo en un tiempo inferior a la edad del universo (13.800 millones de años aproximadamente).

Hasta aquí todo bien, pero… esto es para los ordenadores convencionales, los que todos conocemos, los que trabajan con bits, es decir con 0s y 1s. Pero… ¿qué hay de los ordenadores cuánticos? Hace años que existen y recientemente Google anunció que había conseguido la “supremacía cuántica”. Como ya tenemos ordenadores cuánticos que van a hacer todo mucho más rápido, todo lo anterior no vale y Bitcoin será destruido. ¿No?

¡No tan rápido!

Para empezar, los ordenadores cuánticos no van a hacer todas las tareas más rápido, no son ordenadores “simplemente más rápidos”. Son ordenadores “diferentes”, que harán muchas tareas más lentos que los ordenadors convencionales, pero que algunos problemas que los ordenadores convencionales sólo pueden resolver en tiempo exponencial, podrán resolverlos en tiempo polinomial. Estos ordenadores cuánticos no trabajan con bits sino con qubits.

¿Y qué son los qubits? Los qubits son unidades de información más complejas que los bits. Difíciles de comprender para quien no conoce la mecánica cuántica. Como este artículo no presupone que el lector tiene este conocimiento voy a realizar algunas simplificaciones, a costa, posiblemente, de precisión o exactitud. El objetivo del artículo es proporcionar una idea sobre cómo de real y próxima en el tiempo es la amenaza de los ordenadores cuánticos para Bitcoin y que esta idea sea accesible a la mayor parte de la gente, no sólo a aquellos que conocen la mecánica cuántica.

Habiendo dicho lo anterior, un qubit es una unidad de información que puede estar en infinitos estados, a diferencia de un bit que sólo puede estar en 2 estados.
Al igual que un bit, tiene dos estados básicos: |0 ⟩ y |1⟩. Pero a diferencia de un bit, puede estar en cualquier estado |0 ⟩ + β|1⟩, donde ⍺ y β son números complejos tales que la suma de sus cuadrados es 1.
No queda ahí la cosa, hay más diferencias. Si un bit está en estado 1 y lo “medimos” (leemos), vamos a obtener 1 y si está en estado 0 vamos a obtener 0 (como cualquiera podría esperar). Pues bien, en la mecánica cuántica las cosas no funcionan así. En la mecánica cuántica la medición altera el estado. Y no es “culpa” de que midamos con un aparato muy malo o sin el cuidado suficiente, es “culpa” de la propia esencia del fenómeno cuántico. Así es que un qubit puede estar en infinitos estados pero si medimos o leemos su valor, va a ser |0 ⟩ o |1⟩. No podemos leer el valor ⍺|0 ⟩ + β|1⟩.

Representación gráfica de un qubit

Extraño, sí, pero así es la naturaleza. En principio no parece que estos qubits nos puedan aportar demasiado. Pueden tener muchísimos estados pero sólo podemos leer dos y además, no sabemos qué vamos a leer porque es aleatorio. ¿Para qué podrían servir?. Sí, es aleatorio, pero no equiprobable. Resulta que ⍺ y β son las amplitudes de probabilidad, o dicho de otra manera, el cuadrado de ⍺ es la probabilidad de que si medimos el estado del qubit salga |0 ⟩ y el cuadrado de β es la probabilidad de que si medimos el estado del qubit salga |1⟩.
Como podemos ver, estos qubits son elementos de información muy complejos. Sin profundizar más, ya podemos hacernos una idea de que un ordenador cuántico será radicalmente diferente de un ordenador convencional ya que tiene que tratar con este tipo de elementos de información tan extraños. De hecho, operaciones lógicas, algoritmos, … todo es diferente en la computación cuántica. No sirven las puertas lógicas habituales, los AND, OR, NOT, NAND, XOR… no existen esas puertas lógicas con qubits. En cambio existen muchas otras, muchísimas (infinitas de hecho) posibles puertas lógicas cuánticas. Los algoritmos también son completamente diferentes. Hay que desarrollarlos y no tienen nada que ver con los tradicionales, son algoritmos construidos a partir de estas nuevas puertas cuánticas.

Si no conocéis nada de computación cuántica podréis pensar que esto es rarísimo (lo es) y que probablemente tardaremos muchísimo tiempo en tener algoritmos para poder hacer algo interesante con estas puertas cuánticas tan raras y mucho más para romper la criptografía. Pues no es así para el caso de la criptografía de clave pública.
En el caso que nos ocupa, la amenaza de que Bitcoin será destruido por los ordenadores cuánticos se debe a que ya existe un algoritmo para los ordenadores cuánticos capaz de “romper” el logaritmo discreto de ECDSA, en el que se basa la seguridad de Bitcoin. Y existe desde 1995 (¡13 años antes que la invención de Bitcoin!). Que se pueda calcular el logaritmo discreto de ECDSA significa que dada la clave pública se puede obtener la clave privada con lo cual todo el sistema se vendría abajo. Se trata del famoso algoritmo de Shor. (II)

Así que existen los ordenadores cuánticos y existe el algoritmo que es capaz de calcular el logaritmo discreto de ECDSA en el que se basa Bitcoin. Ya está ¿no?

De nuevo, no tan rápido. ¿Qué significa el anuncio de la supremacía cuántica de Google? ¿Qué ha conseguido?
Ha conseguido resolver en unos segundos un problema que un supercomputador tardaría miles de años. Lo ha conseguido con un computador cuántico de 54 qubits.
Segun las últimas investigaciones (III), sería necesario un ordenador cuántico con más de 2300 qubits ( y más de 128 mil millones de puertas cuánticas Toffoli) para romper ECDSA de 256 bits. Y resulta que construir ordenadores cuánticos con más y más qubits no es nada sencillo. Tomemos un poco de perspectiva histórica:

La idea de la computación cuántica (IV) surgió en 1981 cuando Paul Benioff imaginó un ordenador que trabajaba con algunos de los principios de la mecánica cuántica. También en 1981 Richard P. Feynman dio una charla en el MIT titulada “Simulating physics with computers” (V), donde entre otras ideas, expuso que dado que la esencia de la naturaleza es cuántica, necesitaremos computadores cuánticos para simularla.
Desde 1981 la computación cuántica ha ido avanzando y desarrollándose:

  • En 1985, David Deutsch describió el primer ordenador cuántico universal.
  • En 1995 Peter Shor describió un algoritmo capaz de descomponer números en sus factores primos y resolver también el logaritmo discreto de ECDSA.
  • En 1998 nació la primera máquina de 2 qubits, que fue presentada en la Universidad de Berkeley, California.
  • En 1999 IBM creó la primera máquina de 3 qubits.
  • En 2001 IBM y la Universidad de Stanford ejecutaron por primera vez el algoritmo de Shor. Fue en el primer computador cuántico de 7 qubits. En el experimento se calcularon los factores primos de 15, dando el resultado correcto de 3 y 5.

De ahí a la actualidad han seguido los avances y en el CES de 2019, IBM presentó el IBM Q System One, el primer ordenador cuántico para uso comercial. Alojado en un cubo de vidrio hermético de 2,7 metros de arista, con un total de 20 qubits. En noviembre de 2019 Google anunció la “supremacía cuántica”, dado que han conseguido resolver con su ordenador de 54 qubits un problema que con uno convencional habrían tardado miles de años.

IBM Q SystemOne

Entonces, ¿cuántos años faltan para que los computadores cuánticos puedan romper ECDSA?

Predecir el futuro es algo enormemente complicado principalmente porque como expone Nassim Nicholas Taleb en su libro El cisne negro, no somos capaces de predecir los potencialmente enormes efectos de lo altamente improbable. Llevado al tema que nos ocupa esto significa que no somos capaces de predecir si por ejemplo se puede producir un descubrimiento físico de tal magnitud que haga que nuestra comprensión de la mécanica cuántica avance tanto que construir ordenadores cuánticos de muchísimos qubits sea trivial… o quizás que sea imposible.
Asumiendo que no va a haber cisnes negros en lo referente a la computación cuántica, podemos hacer nuestras predicciones en base a lo que conocemos. Hagamos un resumen de nuestra historia en los avances de la computación cuántica.

Sabemos que de 1981 a 2001, en 20 años, hemos conseguido construir el primer ordenador cuántico capaz de factorizar el número 15 en sus dos factores primos: 3 y 5. Y que en los siguientes 20 años, hemos llegado a 20 qubits en un ordenador cúbico de 2.7m de arista y otro de 54 bits que ha realizado el primer cálculo (sin aplicación práctica) que no pueda realizar un ordenador convencional más rápido. En casi 40 años hemos conseguido fabricar un ordenador cuántico de 54 qubits. Resulta que no es trivial construir computadores con muchos qubits.

Para obtener toda la potencia de cálculo de ellos y por tanto puedan ejecutar los algoritmos que les proporcionan esa ventaja exponencial respecto a los ordenadores convencionales, es muy importante que el sistema de qubits pueda estar en estado de entrelazamiento. El entrelazamiento cuántico es uno de los fenómenos físicos más contraintuitivos de la mecánica cuántica. Un fenómeno que el propio Einstein no consiguió aceptar, pero que se ha podido comprobar experimentalmente. No vamos a ver qué es el entrelazamiento cuántico, pero para nuestro propósito es suficiente con saber que el entrelazamiento es básico para el funcionamiento de los computadores cuánticos. Pues bien, actualmente conseguimos que los qubits estén en este estado unos 100 ms. Es decir, este es el tiempo que tenemos para realizar nuestro cálculo. Cuando se pierde el entrelazamiento (decoherencia cuántica), adiós, no se puede seguir calculando.

Hay diferentes técnicas para la construcción de un sistema de qubits que puedean estar en entrelazamiento, pero la que parece más prometedora (basada en superconductores) requiere que los qubits estén a una temperatura de… ¡15 mili Kelvin!
Para hacernos una idea de qué temperatura es ésta, podemos pensar que es muy posible que el lugar del universo más frío sea actualmente un qubit de alguno de los supercomputadores existenes. Incluso el espacio exterior más alejado de cualquier estrella está a una temperatura superior, 2.7 Kelvin.

Recapitulando: tenemos computadores cuánticos y tenemos el algoritmo necesario (Shor), pero para romper el logaritmo discreto para claves de tamaño de 256 bits (como las de Bitcoin) es necesario un computador con más de 2300 qubits.
Como hemos visto, no es nada sencillo construir computadores con más y más qubits y en 40 años, tenemos actualmente computadores de 54 qubits. El avance tecnológico no tiene por qué ser lineal en el tiempo, desde luego, pero, a priori no parece probable que consigamos construir un computador con más de 2300 qubits en los próximos 10 años. Si lo conseguimos algún día (y éste es un gran “si”), posiblemente sea en mucho más tiempo, 20, 50 o más años.

Conclusión: ¿hay que preocuparse?
En mi opinión, la computación cuántica no supone una amenaza relevante para Bitcoin en la actualidad ya que estamos muy lejos de poder construir un computador cuántico con suficiente número de qubits como para romper ECDSA. No obstante, ésta es únicamente mi opinión personal después de tener en cuenta los hechos que he expuesto anteriormete.
En cualquier caso, si llegara un día en el que la amenaza fuese más cercana, Bitcoin podría ser actualizado y ECDSA sería reemplazado por un esquema de firmas digitales de criptografía cuántica, algo que es posible realizar sin ninguna afectación a la red mediante un Soft Fork (VI).

Referencias.

(I) Anatomy of a Bitcoin transaction https://privatekeys.org/2018/04/17/anatomy-of-a-bitcoin-transaction/
(II) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum computer https://arxiv.org/abs/quant-ph/9508027
(III ) Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms https://arxiv.org/pdf/1706.06752.pdf
(IV) Computación Cuántica https://es.wikipedia.org/wiki/Computación_cuántica
(V) Simulating physics with computers. Richard P. Feynman http://www.wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf
(VI) Soft Fork https://en.bitcoin.it/wiki/Softfork

2 pensamientos en “Bitcoin y los computadores cuánticos

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s