Prueba de trabajo

La prueba de trabajo (también escrita como prueba-de-trabajo y abreviada PoW ) es una forma de prueba criptográfica en la que una parte (el probador ) demuestra a otras (los verificadores ) que se ha gastado una cierta cantidad de un esfuerzo computacional específico. ^{[ 1 ]} Los verificadores pueden posteriormente confirmar este gasto con un esfuerzo mínimo por su parte. El concepto fue propuesto por primera vez por Moni Naor y Cynthia Dwork en 1993 como una forma de disuadir los ataques de denegación de servicio y otros abusos de servicio como el spam en una red al requerir cierto trabajo de un solicitante de servicio, generalmente significa tiempo de procesamiento por parte de una computadora. Ampliando el trabajo de Cynthia Dwork y Moni Naor, Adam Back describió formalmente un sistema de prueba de trabajo llamado Hashcash como protección contra el spam de correo electrónico en 1997. El término "prueba de trabajo" fue acuñado y formalizado por primera vez en un artículo de 1999 por Markus Jakobsson y Ari Juels . ^{[ 2 ] [ 3 ]} El concepto fue adaptado a los tokens digitales por Hal Finney en 2004 a través de la idea de "prueba de trabajo reutilizable" utilizando el algoritmo de hash seguro de 160 bits 1 (SHA-1). ^{[ 4 ]}

La prueba de trabajo fue popularizada posteriormente por Bitcoin como base para el consenso en una red descentralizada sin permisos, en la que los mineros compiten para añadir bloques y minar nueva moneda, con una probabilidad de éxito proporcional al esfuerzo computacional invertido. La prueba de trabajo (PoW) y la prueba de participación (PoS ) siguen siendo los dos mecanismos de disuasión Sybil más conocidos . En el contexto de las criptomonedas, son los mecanismos más comunes. ^{[ 5 ]}

Una característica clave de los esquemas de prueba de trabajo es su asimetría: el trabajo —el cálculo— debe ser moderadamente difícil (pero factible) para el probador o solicitante, pero fácil de comprobar para el verificador o proveedor de servicios. Esta idea también se conoce como función de coste de CPU, rompecabezas del cliente , rompecabezas computacional o función de precios de CPU. Otra característica común son las estructuras de incentivos integradas que recompensan la asignación de capacidad computacional a la red con valor en forma de criptomoneda. ^{[ 6 ] [ 7 ]}

The purpose of proof-of-work algorithms is not proving that certain work was carried out or that a computational puzzle was "solved", but deterring manipulation of data by establishing large energy and hardware-control requirements to be able to do so.^[6] Proof-of-work systems have been criticized by some environmentalists who argue that it generates externalities that are not reflected in market electricity prices which do not compensate for the economic and social benefits.^[8] The interruptible load characteristics of proof-of-work mining provide demand-response services and support the integration of variable renewable energy under certain market and grid conditions.^[9]

The concept of Proof of Work (PoW) has its roots in early research on combating spam and preventing denial-of-service attacks. One of the earliest implementations of PoW was Hashcash, created by British cryptographer Adam Back in 1997.^[10] It was designed as an anti-spam mechanism that required email senders to perform a small computational task, effectively proving that they expended resources (in the form of CPU time) before sending an email. This task was trivial for legitimate users but would impose a significant cost on spammers attempting to send bulk messages.

Hashcash's system was based on the concept of finding a hash value that met certain criteria, a task that required computational effort and thus served as a "proof of work." The idea was that by making it computationally expensive to send large volumes of email, spamming would be reduced.

One popular system, used in Hashcash, uses partial hash inversions to prove that computation was done, as a goodwill token to send an e-mail. For instance, the following header represents about 2⁵² hash computations to send a message to calvin@comics.net on January 19, 2038:

X-Hashcash: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE

It is verified with a single computation by checking that the SHA-1 hash of the stamp (omit the header name X-Hashcash: including the colon and any amount of whitespace following it up to the digit '1') begins with 52 binary zeros, that is 13 hexadecimal zeros:

0000000000000756af69e2ffbdb930261873cd71

Si los sistemas PoW pueden realmente resolver un problema particular de denegación de servicio, como el problema del spam, es objeto de debate; ^{[ 11 ] [ 12 ]} el sistema debe hacer que el envío de correos electrónicos no deseados sea intrusivamente improductivo para el remitente, pero tampoco debe impedir que los usuarios legítimos envíen sus mensajes. En otras palabras, un usuario genuino no debería encontrar ninguna dificultad al enviar un correo electrónico, pero un remitente de spam tendría que gastar una cantidad considerable de potencia de cálculo para enviar muchos correos electrónicos a la vez. Los sistemas de prueba de trabajo están siendo utilizados por otros sistemas criptográficos más complejos, como Bitcoin, que utiliza un sistema similar a Hashcash. ^{[ 11 ]}

La prueba de trabajo remonta sus orígenes teóricos a los primeros esfuerzos por combatir el abuso digital, evolucionando significativamente con el tiempo para abordar la seguridad, la accesibilidad y aplicaciones más amplias que su propósito inicial contra el spam. La idea surgió por primera vez en 1993 como un elemento disuasorio para el correo basura, pero fue el documento técnico de Satoshi Nakamoto de 2008, "Bitcoin: un sistema de efectivo electrónico entre pares" ^{[ 13 ],} el que consolidó el potencial de la prueba de trabajo como piedra angular de las redes blockchain. Este desarrollo refleja la creciente demanda de sistemas seguros y descentralizados.

La primera aparición de la prueba de trabajo se remonta a 1993, cuando Cynthia Dwork y Moni Naor propusieron un sistema para frenar el correo basura exigiendo a los remitentes la realización de tareas computacionalmente exigentes. En su artículo «Pricing via Processing or Combatting Junk Mail» ^{[ 14 ],} describieron métodos como el cálculo de raíces cuadradas modulares, diseñados para ser difíciles de resolver pero sencillos de verificar, estableciendo así un principio fundamental de la asimetría de la prueba de trabajo. Esta asimetría es crucial para la eficacia de la prueba de trabajo, ya que garantiza que tareas como el envío de spam resulten costosas para los atacantes, mientras que la verificación siga siendo eficiente para los usuarios legítimos.

Este fundamento conceptual encontró aplicación práctica en 1997 con Hashcash de Adam Back , un sistema que requería que los remitentes calcularan una inversión parcial del algoritmo SHA-1 , produciendo un hash con un número determinado de ceros iniciales. Descrito en el artículo de Back "Hashcash: una contramedida contra la denegación de servicio" ^{[ 15 ]} , Hashcash impuso un coste computacional para disuadir el spam, al tiempo que permitía a los destinatarios confirmar el trabajo sin esfuerzo, sentando así una base fundamental para las posteriores implementaciones de prueba de trabajo en criptografía y tecnología blockchain.

Bitcoin, lanzado en 2009 por Satoshi Nakamoto, marcó un punto de inflexión al adaptar la prueba de trabajo de Hashcash a las criptomonedas. El documento técnico de Bitcoin de Nakamoto describió un sistema que utiliza el algoritmo SHA-256 , donde los mineros compiten para resolver acertijos criptográficos y agregar bloques a la cadena de bloques, obteniendo recompensas en el proceso. A diferencia de las pruebas estáticas de Hashcash, el algoritmo de prueba de trabajo de Bitcoin ajusta dinámicamente su dificultad en función del tiempo promedio empleado para minar un bloque en la época anterior, lo que garantiza un tiempo de bloque constante de aproximadamente 10 minutos, creando una cadena a prueba de manipulaciones. Esta innovación transformó la prueba de trabajo, pasando de ser un elemento disuasorio independiente a un mecanismo de consenso para una red descentralizada, priorizando los incentivos financieros sobre el esfuerzo computacional.

Inicialmente minado con CPU estándar , Bitcoin experimentó una rápida transición a las GPU , luego a las FPGA y finalmente a los ASIC , que superaron con creces al hardware general en la resolución de los rompecabezas SHA-256.

Para abordar la creciente dependencia de Bitcoin de hardware especializado, Litecoin cambió la función hash de Hashcash de SHA-256 a Scrypt . Desarrollado por Colin Percival y detallado en la especificación técnica "The scrypt Password-Based Key Derivation Function" ^{[ 16 ],} Scrypt fue diseñado como un algoritmo que consume mucha memoria, requiriendo una cantidad moderada de RAM para su cálculo. El objetivo de Litecoin de hacer que la minería fuera más accesible para usuarios con hardware de propósito general no duró mucho, ya que la minería siguió una migración similar desde las CPU a través de las GPU y FPGA hasta los ASIC.

Existen dos clases de protocolos de prueba de trabajo.

• Los protocolos de desafío-respuesta presuponen una conexión interactiva directa entre el solicitante (cliente) y el proveedor (servidor). El proveedor elige un desafío, por ejemplo, un elemento de un conjunto con una propiedad; el solicitante busca la respuesta correspondiente en el conjunto, la cual se envía de vuelta y es verificada por el proveedor. Dado que el proveedor elige el desafío en el momento, su dificultad puede adaptarse a su carga de trabajo actual. El trabajo del solicitante puede limitarse si el protocolo de desafío-respuesta cuenta con una solución conocida (elegida por el proveedor) o si se sabe que existe dentro de un espacio de búsqueda delimitado.

• Los protocolos de verificación de soluciones no presuponen tal vínculo: por lo tanto, el problema debe ser autoimpuesto antes de que el solicitante busque una solución, y el proveedor debe verificar tanto la elección del problema como la solución encontrada. La mayoría de estos esquemas son procedimientos iterativos probabilísticos ilimitados, como Hashcash.

Los protocolos de solución conocida tienden a tener una varianza ligeramente menor que los protocolos probabilísticos no acotados, ya que la varianza de una distribución rectangular es menor que la de una distribución de Poisson (con la misma media). Una técnica genérica para reducir la varianza consiste en utilizar múltiples subdesafíos independientes, puesto que el promedio de varias muestras tendrá una varianza menor.

También existen funciones de coste fijo, como el rompecabezas del bloqueo temporal.

Además, las funciones subyacentes utilizadas por estos esquemas pueden ser:

• Limitado por la CPU, donde el cálculo se ejecuta a la velocidad del procesador, que varía enormemente en el tiempo , así como desde servidores de gama alta hasta dispositivos portátiles de gama baja. ^{[ 17 ]}
• Limitado por la memoria ^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]} donde la velocidad de cálculo está limitada por los accesos a la memoria principal (ya sea latencia o ancho de banda), cuyo rendimiento se espera que sea menos sensible a la evolución del hardware.
• Dependiente de la red ^{[ 22 ]} si el cliente debe realizar pocos cálculos, pero debe recopilar algunos tokens de servidores remotos antes de consultar al proveedor de servicios final. En este sentido, el trabajo no lo realiza realmente el solicitante, pero aun así se producen retrasos debido a la latencia para obtener los tokens necesarios.

Finalmente, algunos sistemas de prueba de trabajo (PoW) ofrecen cálculos abreviados que permiten a los participantes que conocen un secreto, normalmente una clave privada, generar pruebas de trabajo de bajo costo. La idea es que los administradores de listas de correo pueden generar sellos para cada destinatario sin incurrir en un alto costo. La conveniencia de esta función depende del escenario de uso.

Aquí hay una lista de funciones de prueba de trabajo conocidas:

• Raíz cuadrada entera módulo un primo grande ^{[ 3 ]}
• Debilitar las firmas Fiat-Shamir ^{[ 3 ]}
• Firma de Ong–Schnorr–Shamir rota por Pollard ^{[ 3 ]}
• Inversión parcial de hash ^{[ 23 ] [ 24 ] [ 2 ]} Este artículo formaliza la idea de una prueba de trabajo e introduce "la idea dependiente de un protocolo de pudín de pan ", un sistema de "prueba de trabajo reutilizable" (RPoW). ^{[ 25 ]}
• Secuencias hash ^{[ 26 ]}
• Rompecabezas ^{[ 27 ]}
• Rompecabezas basado en Diffie-Hellman ^{[ 28 ]}
• Moderado ^{[ 18 ]}
• Mbound ^{[ 19 ]}
• Hokkaidō ^{[ 20 ]}
• Ciclo del cuco ^{[ 21 ]}
• Árbol Merkle basado ^{[ 29 ]}
• Protocolo de rompecabezas para visitas guiadas ^{[ 22 ]}
• coincidencia parcial de una función hash

En la conferencia IACR Crypto 2022, los investigadores presentaron un artículo que describe Ofelimos, un protocolo blockchain con un mecanismo de consenso basado en la "prueba de trabajo útil" (PoUW). En lugar de que los mineros consuman energía resolviendo rompecabezas complejos, pero esencialmente inútiles, para validar transacciones, Ofelimos logra el consenso al tiempo que proporciona un solucionador de problemas de optimización descentralizado . El protocolo se basa en la Búsqueda Local Doblemente Paralela (DPLS), un algoritmo de búsqueda local que se utiliza como componente PoUW. El artículo presenta un ejemplo que implementa una variante de WalkSAT , un algoritmo de búsqueda local para resolver problemas booleanos. ^{[ 30 ]}

La prueba de trabajo optimizable (OPoW) es una variante de la prueba de trabajo en la que los algoritmos de prueba de trabajo se pueden optimizar sin causar inestabilidad ni centralización en la red. A diferencia de la PoW estándar , donde los mineros compiten para resolver problemas criptográficos arbitrarios, y de los sistemas PoUW , que dirigen el esfuerzo computacional hacia problemas del mundo real, OPoW integra múltiples desafíos de prueba de trabajo —extraídos de problemas de la ciencia computacional como la satisfacibilidad booleana , el enrutamiento de vehículos con capacidad limitada y el problema de la mochila— y los vincula mediante un cálculo de influencia que distribuye las recompensas por bloque proporcionalmente. El mecanismo incentiva a dos categorías de participantes: mineros que calculan soluciones y son recompensados ​​por adoptar los algoritmos más eficientes, y colaboradores de algoritmos que desarrollan y envían algoritmos mejorados y obtienen recompensas en función de su adopción por parte de los mineros. Al desacoplar la resolución de problemas computacionales de la creación de bloques, OPoW permite encontrar muchas soluciones por bloque, creando de hecho un mercado sintético para algoritmos. ^{[ 31 ] [ 32 ]}

En 2009, la red Bitcoin se puso en línea. Bitcoin es una moneda digital de prueba de trabajo que, al igual que RPoW de Finney, también se basa en la prueba de trabajo de Hashcash. Sin embargo, en Bitcoin, la protección contra el doble gasto la proporciona un protocolo P2P descentralizado para el seguimiento de las transferencias de monedas, en lugar de la función de computación confiable de hardware utilizada por RPoW. Bitcoin tiene mayor confiabilidad porque está protegido por computación. Los bitcoins se "minan" utilizando la función de prueba de trabajo de Hashcash por mineros individuales y son verificados por los nodos descentralizados en la red Bitcoin P2P. La dificultad se ajusta periódicamente para mantener el tiempo de bloque alrededor de un tiempo objetivo ^{[ 33 ] .}

consumo de energía

Desde la creación de Bitcoin, la prueba de trabajo ha sido el diseño predominante de las criptomonedas peer-to-peer . Diversos estudios han estimado el consumo energético total de la minería de criptomonedas. ^{[ 35 ]} El mecanismo PoW requiere una gran cantidad de recursos informáticos, que consumen una cantidad significativa de electricidad. Estimaciones de 2018 de la Universidad de Cambridge equiparan el consumo energético de Bitcoin al de Suiza . ^{[ 5 ]}

Los mineros compiten para resolver desafíos criptográficos en la cadena de bloques de Bitcoin, y sus soluciones deben ser acordadas por todos los nodos y alcanzar el consenso. Posteriormente, las soluciones se utilizan para validar transacciones, añadir bloques y generar nuevos bitcoins. Los mineros son recompensados ​​por resolver estos desafíos y añadir nuevos bloques con éxito. Sin embargo, el proceso de minería al estilo Bitcoin consume mucha energía, ya que la prueba de trabajo se basa en un mecanismo de lotería. El trabajo computacional subyacente no tiene otro propósito que proporcionar seguridad a la red, que ofrece acceso abierto y debe funcionar en condiciones adversas. Los mineros deben usar mucha energía para añadir un nuevo bloque con una transacción a la cadena de bloques. La energía utilizada en esta competencia es lo que fundamentalmente le da a Bitcoin su nivel de seguridad y resistencia a los ataques. Además, los mineros deben invertir en hardware informático que requiere grandes espacios como coste fijo. ^{[ 47 ]}

En enero de 2022, el vicepresidente de la Autoridad Europea de Valores y Mercados, Erik Thedéen, pidió a la UE que prohibiera el modelo de prueba de trabajo en favor del modelo de prueba de participación debido a sus menores emisiones de energía. ^{[ 48 ]}

En noviembre de 2022, el estado de Nueva York promulgó una moratoria de dos años sobre la minería de criptomonedas que no utilice exclusivamente energía renovable como fuente de energía. Las empresas mineras existentes podrán continuar minando sin utilizar energía renovable, pero no se les permitirá expandirse ni renovar sus permisos con el estado. No se permitirá que ninguna empresa minera nueva que no utilice exclusivamente energía renovable comience a minar. ^{[ 49 ]}

• Bitcoin
• Mensaje de Bit
• Criptomoneda
• Prueba de autoridad
• Prueba de quemadura
• Prueba de personalidad jurídica
• Prueba del espacio
• Prueba de participación
• Prueba del tiempo transcurrido
• Consenso (informática)

• ^ En la mayoría de los sistemas Unix esto se puede verificar conecho -n 1:52:380119:calvin@comics.net:::9B760005E92F0DAE | openssl sha1