Bitcoin: prueba de trabajo

Un protocolo de prueba de trabajo es una forma eficaz por medio de la que alguien puede probar efectivamente que ha comprometido una cantidad significativa de esfuerzo de cómputo. En los protocolos de prueba de trabajo frecuentemente se trabaja con "puzzles". Y estos puzzles pueden ser, por un lado, el reto a resolver, y, con esto quiero decir que requieren un esfuerzo computacional importante y realmente imposible de evitar. Pero, por otro lado, el resultado de ese esfuerzo puede, de hecho, comprobado de forma simple y puede ser verificado en muchísimo menos tiempo que el que hubo que invertir en ese esfuerzo en el primer paso. ¿De acuerdo? Y hay cantidad de aplicaciones de estos protocolos. Así, por ejemplo, si has oído hablar de Bitcoin, del sistema Bitcoin de pago electrónico, este sistema se basa en un esquema de prueba de trabajo en el contexto de la creación de las que son conocidas como "cadenas de bloques de transacciones". Ahora, aparte de Bitcoin, que es una aplicación relativamente reciente de este tipo de esquemas de prueba de trabajo, estos esquemas se han propuesto en el pasado para otras aplicaciones. Por ejemplo, los esquemas de prueba de trabajo han sido propuestos para hacer cosas como frenar ataques de Denegación de Servicio (ataques DoS). Y aquí la idea es que el solicitante de un determinado servicio debería resolver un problema computacional muy específico, un puzzle de prueba de trabajo, antes de tener acceso a ese servicio. Y la idea aquí es que el esfuerzo computacional necesario es una forma efectiva de retener al solicitante. El servidor, puede, a continuación, comprobar de forma sencilla si el solicitante ha llevado a cabo el trabajo requerido, y sólo si ese trabajo se ha realizado, el servidor dará respuesta a la demanda de servicio. La aplicación original para este tipo de protocolos de prueba de trabajo, el primer sitio en que los he visto propuestos, es en el contexto de intentar detener el spam de correos electrónicos. Y, espero, todos sabemos lo que es el spam de correos electrónicos: son mensajes que no quieres en tu carpeta de entrada (inbox) y que habitualmente llegan a ti sin que los hayas solicitado. Y la idea aquí es que un protocolo de prueba de trabajo puede vincularse a un mensaje de correo en concreto. Y esto es, conceptualmente, como pegar un sello de correos a un mensaje, sólo que, en vez de pagar por el sello utilizando dinero, debes pagar por ese sello "gastando" ciclos de CPU. Así, para un emisor legítimo, que únicamente está enviando un pequeño número de mensajes, este tipo de protocolos de prueba de trabajo no supondrá demasiado. Sólo conllevará un mínimo retraso, ya que sólo es ejecutado en un número muy pequeño de ocasiones. Es un pequeño impedimento, pero no es nada que no sea razonable. Sin embargo para un "spammer", que intentaría enviar muchísimos mensajes -quizás cientos de miles, o millones de mensajes- probablemente sería prohibitivamente caro gastar repetidamente un número de ciclos de CPU por cada mensaje y cada receptor al que se ese mensaje fuera a ser enviado. Espero que esto te haya proporcionado una idea de algunas de las aplicaciones de los protocolos de prueba de trabajo. A continuación voy a profundizar en cómo funcionan en la práctica. Así, en primer lugar, la forma en que me gusta pensar en estos protocolos es como si trabajaran en torno a un "cadena reto". Y voy a llamar a esta cadena-reto, la etiquetaremos con la letra "c". Así, "c" viene a ser un tipo de "cadena reto". Y lo que una persona comprometida en el protocolo hará, el "trabajador", intentará, básicamente, tratará de volver con la pertinente prueba de que está vinculado a esa "cadena reto". Esto viene a ser una respuesta (solución) del reto. Esta respuesta tiene una relación con el reto basada en una propiedad matemática muy específica. Y como puedes haber advertido, quizás cuando hablaba sobre la "cadena reto", por ejemplo en el contexto del spam, esta cadena reto podría ser, de hecho, un mensaje de correo electrónico. Esto es, va a ser algo muy específicamente asociado a la tarea en curso. Ahora lo que el "probador" hará es venir con una "cadena respuesta", y vamos a llamar a la cadena respuesta "r". De hecho, vamos a usar el término "p" para ella dado que podemos pensar en ella como una "prueba", una prueba o una respuesta. Y la idea aquí es que el probador vendrá con esta prueba o "cadena respuesta", y tiene que venir con una cadena tal que, cuando concatenas el reto y la respuesta, y las tomas juntas, y les aplicas una función hash criptográfica, digamos que utilizamos una función criptográfica como SHA-256, o alguna del mismo tipo, si cojo la cadena reto y la cadena prueba y concateno ambas y aplico la función hash criptográfica, aplico esas transformaciones matemáticas que representa la aplicación de la función hash criptográfica, quiero que la cadena respuesta cumpla que la salida de esa función hash cumplirá una propiedad muy particular. El prefijo de la salida, un primer conjunto largo de bits, serán todos ceros. Así, digamos que los primeros 40 bits, o los primeros 30 bits, o algún otro número de bits, serán ceros. Y el resto de los bits pueden tomar cualquier valor, sin ninguna restricción. Obviamente, lo que estás tratando de hacer aquí es encontrar una "cadena prueba" que tenga una relación con la cadena reto. Y esa relación se manifiesta en relación al uso de una función hash concreta (ej. SHA-256) y realmente cumple, o considera, que el output de la función hash se obtiene a partir de la concatenación de la cadena prueba (p) con la cadena reto (c). Y si tienes una buena función hash criptográfica, entonces la única forma conocida para encontrar este tipo de cadena de prueba es, efectivamente, probar con un montón de posibilidades diferentes, utilizar la "fuerza bruta", intentando muchas pruebas diferentes hasta que encuentres una que funciona. Ahora si tú, pongamos por ejemplo, necesitas encontrar una salida que comience por unos 40 ceros consecutivos, esto podría requerirte dos elevado a cuarenta pasos, dos elevado a cuarenta ejecuciones de la función hash. Tendrías que probar dos a la cuarenta diferentes cadenas, y una de ellas funcionaría (sería la solución) si lo intentas con todas esas cadenas. Esto te exige, de hecho, que lo intentes alrededor de 2 a la 40 para obtener la solución, esto es -aproximadamente, un billón (10 elevado a la 12) de intentos. Así, si lo intentas con un billón de cadenas y obtienes el hash de cada una de ellas, tú probablemente encontrarías una cadena cuyos primeros 40 bits fueran ceros. Eso sí, algunas veces lo conseguirías con muchos menos intentos. Otras veces te podría costar un poco más (de un billón). Tu podrías ser muy afortunado. Tú podrías tener muy mala suerte. Pero en media, te vendría a costar un billón de intentos encontrar una cadena cuyos primeros 40 bits fueran igual a cero. Esto es algo que no es sencillo, pero es algo que no está fuera de lo posible. Ahora, para entender porque es realmente difícil resolver este tipo de esquemas de prueba de trabajo más eficientemente que realizando una aproximación basada en la "fuerza bruta", creo que sería útil recordar que la salida de una función hash criptográfica es, prácticamente, aleatoria. De hecho, es como si cada bit de la salida se obtuviera lanzando una serie de monedas. Así, en esta especie de lanzamiento de moneda, si sale cara, has obtenido un cero, y, si sale cruz, puedes pensar en ello como si hubieras obtenido un uno. De forma que lo que realmente estás haciendo es decir, si lanzo 40 monedas, ¿cuál es la probabilidad de que obtenga 40 "caras" de forma consecutiva? Evidentemente, esa probabilidad es muy pequeña pero no está fuera del reino de lo posible. Si lanzas cuarenta monedas alrededor de un billón de veces, de hecho sería esperable que vieras una vez en que las 40 monedas cayeran de cara, de entre ese billón de intentos. Ahora, una propiedad interesante de estos esquemas de prueba de trabajo es que pueden ser calibrados hacia arriba o hacia abajo. Así, digamos, por ejemplo, que quieres exigir aún más esfuerzo para lograr una cadena de prueba correcta. Digamos que quieres incrementar el trabajo que debe ser probado aquí. Lo que podrías hacer, en ese caso, es, simplemente, incrementar el requerimiento del número de ceros con que debe comenzar la cadena. Así, cada vez que aumentes en un cero adicional, estarás doblando la necesidad media de esfuerzo de computo. Y eso es así ya que, efectivamente, estás requiriendo que una moneda más caiga de cara y eso conlleva duplicar el número de monedas lanzadas. Así, si tengo 41 monedas que lanzar y pido que salgan 41 caras, esto exigiría prácticamente el doble de esfuerzo que si sólo pidiese 40 caras. Y, de la misma forma, cada vez que retiras un cero de los requisitos, esto reducirá el esfuerzo computacional necesario a la mitad de lo que era anteriormente. Así, por ejemplo, si sólo requiriese que los primeros 39 bits fuesen cero, esto requeriría alrededor de la mitad de lanzamientos de moneda de los requeridos para que sean 40 ceros. Ahora, lo bueno es que una vez que tienes una solución, digamos que alguien lo ha intentado un billón de veces y, finalmente, viene con una cadena de prueba que funciona, es muy sencillo comprobar que esa cadena de prueba es, realmente, una prueba de trabajo correcta Todo lo que tienes que hacer es juntar la cadena reto con la cadena de prueba y obtener el hash del conjunto. Por ejemplo, si alguien propone esta cadena, llamémosla p', lo único que tienes que hacer es juntar el reto (c) y p', dárselo como entrada a la función hash y ver si los primeros 40 bits son todos ceros. Todo lo que tienes que hacer es aplicar la función hash una única vez a la concatenación de c y p', y puedes comprobar si la salida obtenida cumple el requisito de comenzar por el número de ceros establecido. Y, si ves que la salida tiene el número requerido de ceros, entonces puedes considerar válida la prueba de trabajo, ya que sabes que debe haberle tomado a alguien mucho tiempo, un montón de intentos, conseguir o venir con la cadena p', tal que la concatenación de c y p' dé ese número de ceros como consecuencia de aplicar esta función hash criptográfica. Como puedes ver, estos esquemas son, a la vez, bastante sencillos y bastante ingeniosos. Realmente consiguen que haya que obtener una cadena de prueba que tiene una relación matemática, muy específica con la cadena reto original. Espero que este vídeo te permita hacerte una idea del mecanismo y de cómo funciona esta prueba de trabajo.