Prueba de trabajo (algoritmo de consenso distribuido)
Un algoritmo de prueba de trabajo, también conocido por las siglas POW (del inglés Proof-Of-Work), es un protocolo de consenso distribuido para redes distribuidas.[1] Los sistemas que los usan, como Bitcoin, son sistemas de prueba de trabajo
Motivación e historia
David Chaum introdujo en 1983 el concepto de dinero electrónico.[2] En su propuesta había un servidor central fiable que evitaba un posible doble gasto. Para evitar riesgos de privacidad de los individuos producidos por este servidor, y para asegurar la fungibilidad de la moneda, Chaum introduce una firma ciega para evitar enlazar las firmas del servidor central (la cual representa la moneda), aún manteniendo el servidor central para evitar el doble gasto. Este servidor central fue el punto débil del sistema. Es posible distribuir este único punto de fallo reemplazando la firma del servidor central por una firma con umbral. Sin embargo, por temas de auditabilidad, es importante que los firmantes sean distintos y por tanto identificables. Esto todavía deja el sistema vulnerable a fallos ya que los firmantes (fijos e identificados) pueden caer, todos de golpe o uno a uno.
En 1997 apareció Hashcash el primer sistema de prueba de trabajo. La idea fundamental en la que se basa es que los nodos no confiables que intervienen en un sistema deben aportar una prueba de su interés en el sistema. Para ello tienen que demostrar que han dedicado cierta cantidad de recursos (prueba de trabajo). Además el coste de la verificación de dicha prueba tiene que ser reducida.
A partir de la idea aportada por Hashcash van apareciendo nuevos sistemas que intentan aprovechar el concepto de prueba de trabajo para aplicaciones más generales. En 1998 aparece B-Money de Wei Dai y Bit Gold de Nick Szabo. En 2004 aparece Reusable Proof Of Work de Hall Finney. Estos sistemas, con sus puntos débiles, son las primeras aproximaciones a tener un sistema de prueba de trabajo que permitan el intercambio de valor (criptomonedas) y de su experiencia se aprovecha Bitcoin.[3]
En 2009 Satoshi Nakamoto lanzó Bitcoin, la primera implementación ampliamente usada de un sistema de dinero electrónico peer-to-peer que no requiere tener confianza en los pares. En él se reemplaza la firma del servidor central con un mecanismo de firma consensuada, realizada por nodos no confiables a los que se llama mineros, basada en pruebas de trabajo donde los firmantes son incentivados para que actúen cooperativamente y de forma honesta.
El sistema Bitcoin es el primer sistema de firma multipartita de adhesión dinámica o DMMS (del inglés dynamic membership multi-party signature). La firma es realizada por un conjunto de firmantes no confiables, que no tiene tamaño fijo y que no han solicitado ningún tipo de adhesión. La fiabilidad de la firma se basa en la existencia de un grupo independiente de firmantes, cuantos más mejor, dispuestos a vender sus recursos de CPU (realizan una prueba de trabajo) a cambio de una remuneración. Cuantos más recursos de CPU tenga un firmante, más contribución a la firma hace (se dice que la firma está ponderada por el poder computacional).
La remuneración a los firmantes hace que a priori estén dispuestos a tener un comportamiento honesto para conseguir el consenso. Como la contribución a la firma está ponderada por el poder computacional, si un grupo de firmantes tiene alguna motivación para ser deshonestos, tiene que competir computacionalmente con el resto de firmantes que siguen siendo honestos. Por eso cuantos más firmantes haya más difícil será que un grupo deshonesto tenga cierto éxito. Por esta razón se dice que es una solución al Problema de los generales bizantinos.
Ejemplos
Consenso en Bitcoin
El protocolo Bitcoin obliga a los mineros a trabajar (prueba de trabajo) reintentando inútilmente una y otra vez hasta conseguir un número arbitrario para construir un bloque. Bitcoin podría operar perfectamente sin prueba de trabajo, siempre que todos los participantes fueran perfectamente honestos y altruistas. La prueba de trabajo es un método para establecer un consenso entre un número de personas interesadas, ninguna de las cuales está subordinada a otra, y existen incentivos considerables para resistirse a dicho consenso.
Antes de que un bloque nuevo sea generado, puede que haya muchos pagos circulando por la red sin existir respuesta objetiva acerca de qué pagos deberían ser validados. Algunos podrían ser inválidos, así que todos deben ser comprobados. Algunos pueden no incluir una tasa de transacción, así que puede decidir incluir la transacción o ignorarla. Finalmente, podría haber un conjunto de 2 o más pagos que no pueden ser válidos simultáneamente. Por ejemplo, si alguien intenta gastar los mismos bitcoins en dos transacciones que aún no han sido confirmadas, habría que tomar una decisión sobre qué pago permitir.
De este modo, para un conjunto de pagos dado, pueden existir muchos bloques posibles que pueden construirse con ellos, ninguno de los cuales es objetivamente el más correcto. Tampoco habrá necesariamente un acuerdo acerca de qué resultado es preferible, porque los distintos bloques posibles benefician a distintas personas. Primeramente, está el beneficio que surge de generar un bloque en forma de nuevos bitcoins. Esto es necesario porque, si no existiera, habría muy poco incentivo para hacer la contabilidad para empezar. Con esta recompensa, cada minero naturalmente prefiere que el nuevo bloque sea su propuesta, y no la de cualquier otro.
Además puede haber comportamientos malintencionados. Por ejemplo un minero podría negarse a validar las transacciones procedentes de su enemigo, o podría mostrarse más o menos altruista con las tarifas por transacción que aceptará. Podría incluso proponerse estafar a alguien mediante el doble gasto: él mandaría un pago a la víctima a cambio de un bien determinado, pero solo confirmaría otro pago que hace a una cartera de su propiedad y que está en conflicto con el primero; esto invalidaría el primer pago, y acabaría quedándose con un bien por el que no ha pagado.
Para evitar que se hagan manipulaciones interesadas, Bitcoin añade requerimientos extra al protocolo que incrementan enormemente el coste de la deserción. Los bloques se generan aleatoriamente mediante un cálculo muy difícil, que requiere muchos recursos computacionales, y solo se propone un único bloque a la vez. Es anunciado y verificado por la mayoría de otros nodos (lo cual es fácil verificando los hashes). Cuando un bloque ha sido propuesto, los mineros tienen la opción de continuar buscando un bloque alternativo que les sea más favorable, o aceptar la propuesta (dar por verificado) y luego pasar a buscar el siguiente. Alguien que acepta el último bloque propuesto entiende que está siguiendo un proceso de consenso natural y que, si tiene la suerte de generar el siguiente bloque, será probablemente aceptado por las mismas razones que él aceptó el anterior. Por el otro lado, la opción de esperar e intentar encontrar un bloque más favorable para él es muy arriesgada, porque entonces tendría que convencer a un número suficiente de mineros de que podrá establecer un nuevo consenso, para que le sigan.
La regla general es que el primer bloque minado nunca es egoísta, porque nadie puede planear ser el primero en resolverlo. Uno solo puede ser el primero con suerte. Cualquiera que se desmarque de ese bloque levantará sospechas, porque tiene que rechazar una alternativa perfectamente válida y supuestamente altruista, y convencer a los demás de que hagan lo mismo; algo nada fácil de hacer.
La fortaleza de la firma realizada por la red Bitcoin es directamente proporcional al poder computacional total de todos los mineros. Cuanto mayor sea más difícil será (más poder computacional requerirá) cambiar la cadena de consenso.En esto se basa el protocolo de consenso de bitcoin, el cual puede manejar fallos bizantinos.
Si queremos cambiar un bloque de la cadena, cada bloque que viene después de ese bloque tiene que ser rehasheado y rehacer el trabajo. Esto hace que sea esencialmente imposible modificar un bloque.
Referencias
- Distributed Consensus Protocol el 12 de octubre de 2016 en Wayback Machine.. Jonathan Bhaskar. 2015
- Chaum, David (1983). «Blind signatures for untraceable payments». Advances in Cryptology Proceedings of Crypto (en inglés) 82 (3): 199-203.
- Understanding Bitcoin: Cryptography, Engineering and Economics. Pedro Franco. Wiley 2015
- Enabling Blockchain Innovations with Pegged Sidechains. Adam Back et ali. 2014
- Estudio de la red Bitcoin. Andrés Cisneros Campos. Trabajo Final de Master. 2013
- El concepto de la prueba de trabajo. Daniel Krawisz. Traducido por Majalu el 7 de agosto de 2014