Desaf¨ªo criptogr¨¢fico: una prueba de trabajo para los mineros de bitcoin

Al aterrizar en la isla, despert¨¦ y vi que mis hermanos Diego y Mar¨ªa segu¨ªan dormidos.

¨D?Que ya hemos llegado!¡ª les espet¨¦. Diego ni se inmut¨®. Mar¨ªa abri¨® un ojo, y me fundi¨® con la mirada. A¨²n est¨¢bamos somnolientos cuando, a la salida del aeropuerto, nos interceptaron dos polic¨ªas.

¨DAcomp¨¢?enme, por favor.¡ª nos dijeron.

Mis padres, m¨¢s despiertos que nosotros, no parec¨ªan preocupados. Los polic¨ªas nos explicaron que en la isla no hab¨ªa monedas de curso legal y tendr¨ªamos que adaptarnos. Solo podr¨ªamos usar ...

Al aterrizar en la isla, despert¨¦ y vi que mis hermanos Diego y Mar¨ªa segu¨ªan dormidos.

¨D?Que ya hemos llegado!¡ª les espet¨¦. Diego ni se inmut¨®. Mar¨ªa abri¨® un ojo, y me fundi¨® con la mirada. A¨²n est¨¢bamos somnolientos cuando, a la salida del aeropuerto, nos interceptaron dos polic¨ªas.

¨DAcomp¨¢?enme, por favor.¡ª nos dijeron.

Mis padres, m¨¢s despiertos que nosotros, no parec¨ªan preocupados. Los polic¨ªas nos explicaron que en la isla no hab¨ªa monedas de curso legal y tendr¨ªamos que adaptarnos. Solo podr¨ªamos usar criptomonedas.

¨D?Eso del bitcoin?¡ª pregunt¨¦.

Asintieron. Nos dieron un folleto explicativo, que pasamos a leer con atenci¨®n. Ah¨ª se describ¨ªa el bitcoin como una moneda digital, un tipo de dinero completamente virtual. Cada bitcoin es un archivo inform¨¢tico que se almacena en una aplicaci¨®n de ¡°monedero digital¡± en un dispositivo, tipo un m¨®vil u ordenador.

Entonces esto no ser¨¢ muy complicado ¡ªdije a mis hermanos¡ª La gente puede enviar bitcoins a su monedero digital, de manera que es sencillo enviar bitcoins a otras personas o comercios. Cada una de las transacciones se registra en una lista p¨²blica llamada cadena de bloques (blockchain, en ingl¨¦s).

Segu¨ª leyendo, sorprendido, que gracias a esto se puede rastrear el historial de Bitcoins para evitar que la gente gaste monedas que no posee, haga copias o deshaga transacciones.

¡ªEl blockchain¡ª me explic¨® mi hermano¡ª es una estructura de datos. Una cadena de bloques, donde cada bloque contiene un conjunto de transacciones. Una especie de libro de contabilidad distribuido que contiene todas las transacciones de forma cronol¨®gica; una red formada por much¨ªsimos ordenadores comparten este libro.

¡ªY tantos ordenadores, ?c¨®mo se ponen de acuerdo?¡ª pregunt¨® mi hermana.

¨DBuena pregunta. A ver qu¨¦ dice el folleto¡ª contest¨¦ yo, ya algo impaciente

Seg¨²n le¨ªmos, cuando alguien quiere hacer una transacci¨®n, digamos comprar algo, env¨ªa la petici¨®n a la red de ordenadores. All¨¢, unos ordenadores especiales llamados mineros, se encargan de ir recogiendo las peticiones (y hacer ciertas comprobaciones, como que tenga suficiente dinero para hacer la compra), y las incorporan a la cadena de bloques.

¡ªPero si hay tantos ordenadores, ?qui¨¦n se encarga de actualizar la cadena esa de bloques?¡ª pregunt¨¦.

Pues se plantea un puzle, que es en realidad hacer un c¨¢lculo muy sencillo con ciertos valores, de modo que el resultado sea un valor que parece elegido al azar. Una versi¨®n simplificada ser¨ªa por ejemplo pedirles calcular, para un primo p y dado un valor x, el cubo de x, y quedarse con el resto de calcular la divisi¨®n entera del cubo de x por p. Esto es, si x = 20 y p =541, el resultado ser¨ªa 426, o si x = 21, con el mismo p, nos saldr¨ªa 64.

¡ª?O sea que solo cambias un n¨²mero y el resultado es completamente diferente?¡ª pregunt¨® Mar¨ªa sorprendida.

¡ªDel todo¡ª observ¨® Diego¡ª Diferente e impredecible si no haces los c¨¢lculos, por eso se llama prueba de trabajo. Venga, os pongo a prueba, a ver qui¨¦n es el que primero que encuentra un valor x que elevado al cubo y dividi¨¦ndolo por 541, proporcione un resto que acabe en cero.

Mi hermana y yo desenfundamos el m¨®vil. A los pocos minutos, ella anunci¨® el resultado con una gran sonrisa.

¡ª?El 36!

Mi hermano y yo comprobamos que estaba en lo cierto. 36 elevado al cubo es 46656, y al dividirlo por 541, el resto es 130.

¡ªY s¨®lo os he pedido que acabe en un cero un 0¡ª continu¨® mi hermano. Imaginaos si el objetivo es que con el mismo procedimiento acabe en dos ceros. ?Lo quer¨¦is intentar?

Nuestros dedos se deslizaban por la pantalla con gran velocidad. En menos de un minuto, yo lo hab¨ªa conseguido

¡ª?El 481!¡ª grit¨¦ a los cuatro vientos. Mi estrategia de comenzar por el 540 e ir disminuyendo no hab¨ªa ido del todo mal.

De nuevo, comprobarlo fue unos pocos segundos, calcularlo, llevo bastante m¨¢s trabajo. Ahora ve¨ªa por qu¨¦ se llamaba prueba de trabajo, pero a¨²n nos faltaba entender c¨®mo la cadena de bloques guardaba el dinero disponible de cada uno. En el folleto hab¨ªa una figura.

Cada rect¨¢ngulo, decidimos, representaba un bloque. En cada uno, parec¨ªan reflejarse tres transacciones; por ejemplo, en el primer bloque interpretamos que D le ha dado a M 5 monedas M y D pagaban a R 3 y 4 monedas respectivamente. La etiqueta B podr¨ªa ser una especie de nombre del bloque y el n¨²mero junto a la etiqueta BA parec¨ªa hacer referencia al bloque anterior.

¡ª?Eyyyy!! ?Os hab¨¦is dado cuenta de que son nuestras iniciales?¡ª dijo mi hermana¡ª Diego, Roger, Mar¨ªa.

¡ªPues s¨ª, quiz¨¢ mucha casualidad¡ª dije.

Como en los ejemplos del folleto el 541 jugaba el papel del divisor p, probamos a dividir 82821 entre 541, y, encantados, vimos que sal¨ªa 48 . Ya sab¨ªamos la relaci¨®n c¨®mo se constru¨ªa la etiqueta BA del segundo bloque, pero ?y B de d¨®nde sal¨ªa?

¡ª?Os hab¨¦is fijado que comienza por 48 y a continuaci¨®n le siguen concatenados los 3 valores de las transacciones?¡ªobserv¨® mi hermana.

¡ªMmmmmmm¡­ pues ahora que lo dices, coincide totalmente¡ª le contest¨¦. Pero, ?c¨®mo se calculan los otros valores? Continuamos leyendo.

Ah¨ª estaba la prueba de trabajo. Jugando con los n¨²meros del folleto encontramos el puzle: hab¨ªa que calcular un n¨²mero cuyos primeros d¨ªgitos fuesen 48421 tal que al elevarlo al cubo y calcular la divisi¨®n entera con 541, los dos ¨²ltimos d¨ªgitos del resto fuesen 00. Y sal¨ªa justo ?4842176!

¨DPues ya estar¨ªa ¡ªsentenci¨® Diego¡ª. El minero que consigue ese valor, lo anuncia; los dem¨¢s mineros (como est¨¢ haciendo Mar¨ªa) comprueban que es correcto y, si est¨¢n de acuerdo, se a?ade el bloque a la cadena.

Fuimos a los polic¨ªas y les explicamos que ya lo hab¨ªamos entendido. La mujer polic¨ªa sonri¨® misteriosa, nos dio un papel y pregunt¨® ?cu¨¢nto dinero ten¨¦is cada uno?

[FE DE ERRORES: La imagen original que aparec¨ªa en este desaf¨ªo ha sido cambiada, ya que inclu¨ªa un error. Esta es la correcta. Agradecemos a nuestro lector Francisco Javier que nos alertara del fallo.]

Conseguimos pasar la prueba, y con ella una peque?a recompensa que gastamos en una pizza, que cost¨®, nada m¨¢s y nada menos que 10.000 bitcoins. Corr¨ªa el a?o 2010. ?Y pensar que en euros esa pizza ha llegado a valer m¨¢s de 500 millones de euros!

?Conseguir¨ªas pasar t¨² tambi¨¦n la prueba?

Los desaf¨ªos criptogr¨¢ficos se publicar¨¢n cada 15 d¨ªas. Los lectores pueden dejar sus soluciones y debatir sobre el problema en los comentarios de esta p¨¢gina, por lo que se recomienda a quien quiera resolverlo por s¨ª mismo no leerlos hasta haber descifrado el enigma. Tambi¨¦n pueden enviar sus respuestas al correo desafioscriptograficos@gmail.com. En cada nuevo desaf¨ªo publicaremos la soluci¨®n del anterior, acompa?ada de un comentario con algunas ideas originales o inspiradoras que hayamos recibido.

Vanesa Daza Fern¨¢ndez es profesora e investigadora del Departament de Tecnologies de la Informaci¨® i les Comunicacions de la Universitat Pompeu Fabra de Barcelona.

SOLUCI?N AL DESAF?O ANTERIOR

La herramienta criptogr¨¢fica que aparece en este reto son los esquemas de compartici¨®n de secretos: c¨®mo repartir un valor secreto s entre diferentes participantes, dando a cada participante Pi un fragmento fi, y de manera que s¨®lo puedan recuperar el secreto a partir de sus fragmentos aquellos subconjuntos de participantes autorizados (que definen lo que se conoce como estructura de acceso).

En las dos primeras reparticiones del secreto (el c¨®digo del candado), los subconjuntos autorizados eran todos aquellos con dos (o m¨¢s) participantes. Es lo que se conoce como estructura de acceso de umbral (en este caso, el valor del umbral es 2). El cript¨®grafo israel¨ª Adi Shamir (la S de RSA) propuso una manera segura de repartir secretos para una estructura de acceso de umbral t: se escoge un polinomio secreto, f(x), de grado t-1 que tenga como t¨¦rmino independiente el secreto s, es decir

f(x) = s + a1¡¤x + a2¡¤x? + a3¡¤x? + ¡­ + at-1¡¤x elevado a t-1

Y se asigna como fragmento de un participante Pi el punto del plano cartesiano (i,f(i)).

El polinomio secreto f(x) tiene t coeficientes desconocidos, s, a1,¡­,at-1. La intuici¨®n (y las matem¨¢ticas) nos dice que para encontrar esos t valores necesitamos saber al menos t datos de ese polinomio, por ejemplo su evaluaci¨®n en t puntos diferentes. Si se tienen menos de t puntos / evaluaciones / fragmentos, cualquier polinomio de grado t-1 es posible, y por tanto el valor secreto s=f(0) queda completamente indeterminado.

En el caso de umbral 2, el polinomio tiene grado 1 y se corresponde a una recta, f(x) = s + a1¡¤x. En el segundo reparto de fragmentos realizado por el Mago del Bosque, tambi¨¦n correspondiente a una recta, tenemos que la recta que pasa por los puntos (1,15) y (2,17) es la recta de ecuaci¨®n y = 2x + 13. Esa recta corta el eje OY en el punto (0,13), por tanto el secreto en ese caso era 13.

En el caso de umbral 3, el polinomio secreto tendr¨¢ grado 2, su gr¨¢fica ser¨¢ una par¨¢bola: f(x) = s + a1 x + a2 x?.

Para recuperar ese polinomio (o par¨¢bola) secreto, hacen falta tres evaluaciones del polinomio, es decir tres fragmentos de tres reinos diferentes, por ejemplo tomaremos los Reinos 1, 2 y 3. Con esa informaci¨®n, plantear¨ªamos un sistema de tres ecuaciones con tres inc¨®gnitas; las inc¨®gnitas son s, a1 y a2:

fragmento (1,22) -> 22 = f(1) = s + a1 ¡¤ 1 + a2 ¡¤ 1?= s + a1 + a2

fragmento (2,29) -> 29 = f(2) = s + a1 ¡¤ 2 + a2 ¡¤ 2?= s + 2 a1 + 4 a2

fragmento (3,32) -> 32 = f(3) = s + a1 ¡¤ 3 + a2 ¡¤ 3?= s + 3 a1 + 9 a2

La soluci¨®n a ese sistema de ecuaciones es s=11, a1=13, a2=-2, es decir que el polinomio secreto era f(x) = 11 + 13¡¤x - 2¡¤x?, y por tanto el secreto que abr¨ªa el candado era s=11.

A partir de ese d¨ªa, como ser¨ªan necesarios t=5 fragmentos (es decir, todos los fragmentos de los cinco reinos) para recuperar el secreto, una posibilidad ser¨ªa usar un polinomio secreto de grado 4. Pero hay otra posibilidad m¨¢s sencilla y eficiente (y que funciona siempre que el umbral t sea igual al n¨²mero total de participantes): dado un secreto s a repartir, el Mago del Bosque simplemente deb¨ªa elegir cuatro fragmentos al azar, por ejemplo f1, f2, f3 y f4, y definir el ¨²ltimo como f5 = s - f1 - f2 - f3 - f4. As¨ª, la suma de los cinco fragmentos dar¨¢ el secreto, pero con 4 o menos fragmentos no se obtendr¨¢ ninguna informaci¨®n sobre el secreto.

Cuando se usan esos esquemas para compartir secretos en la vida real, los secretos y los fragmentos no tienen tama?o libre, sino que por ejemplo se elige el secreto en el conjunto de enteros {0,1,2,3,...,q-1} para un n¨²mero primo q, y se trabaja con operaciones modulares m¨®dulo q, es decir que q equivale a 0, q+3 equivale a 3, etc. As¨ª se consigue que el tama?o de los fragmentos f(i) tambi¨¦n est¨¦ controlado, puesto que pertenecen al mismo conjunto {0,1,2,3,...,q-1} que el secreto repartido.

Muchos de nuestros lectores (como Javier, Ramiro o Joaqu¨ªn) han resuelto r¨¢pidamente este reto¡­asique os planteamos una pregunta adicional: otra opci¨®n que hubiese tenido el Mago del Bosque para hacer realidad el deseo de los Reinos 1, 3 y 4 de que el subconjunto {2,5} no pudiese recuperar el secreto, habr¨ªa sido repartir el secreto para la estructura de acceso que contiene todos los subconjuntos de cardinal 2 excepto el {2,5}. ?Os atrev¨¦is a buscar la manera de repartir el secreto en ese caso?

PS: Tenemos pendiente de resolver tambi¨¦n el desaf¨ªo criptogr¨¢fico musical que nos envi¨® Salva Fuster en los comentarios a uno de estos retos. Ya hemos recibido alguna respuesta en nuestro correo desafioscriptograficos@gmail.com. Os animamos a resolverlo tambi¨¦n. En el pr¨®ximo desaf¨ªo publicaremos la soluci¨®n que nos ha remitido su autor.

Puedes seguir a EL PA?S TECNOLOG?A en Facebook y Twitter o apuntarte aqu¨ª para recibir nuestra newsletter semanal.