La prueba de trabajo ( PoW ) es una forma de prueba criptográfica de conocimiento cero en la que una parte (el probador ) demuestra a los demás (los verificadores ) que se ha gastado una cierta cantidad de un esfuerzo computacional específico. Posteriormente, los verificadores pueden confirmar este gasto con un esfuerzo mínimo de su parte. El concepto fue inventado por Cynthia Dwork y Moni Naor en 1993 como una forma de disuadir los ataques de denegación de servicio y otros abusos del servicio como el spam.en una red al requerir algo de trabajo por parte de un solicitante de servicio, lo que generalmente significa tiempo de procesamiento por parte de una computadora. 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. [1] [2] La prueba de trabajo fue más tarde popularizada por Bitcoin como base para el consenso en cadenas de bloques y criptomonedas sin permiso , en las que los mineros compiten para agregar bloques y acuñar nueva moneda, cada minero experimentando una probabilidad de éxito proporcional a su esfuerzo computacional invertido. PoW y PoS ( prueba de participación ) son los dos mecanismos de disuasión de Sybil más conocidos . En el contexto de las criptomonedas son los mecanismos más habituales. [3]
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) por parte del probador o solicitante, pero fácil de verificar para el verificador o proveedor de servicios. Esta idea también se conoce como función de costo de CPU, rompecabezas de cliente , rompecabezas computacional o función de precio de CPU. Otra característica común son las estructuras de incentivos incorporadas que recompensan la asignación de capacidad computacional a la red con valor en forma de dinero .
El propósito de los algoritmos de prueba de trabajo no es probar que se llevó a cabo cierto trabajo o que se "resolvió" un rompecabezas computacional, sino disuadir la manipulación de datos a través de la solución específica de establecer grandes requisitos de energía y control de hardware para la capacidad de hazlo.
Fondo
Un sistema popular, utilizado en Hashcash , utiliza inversiones hash parciales para demostrar que se realizó el cálculo, como un token de buena voluntad para enviar un correo electrónico . Por ejemplo, el siguiente encabezado representa aproximadamente 2 52 cálculos hash para enviar un mensaje [email protected]
el 19 de enero de 2038:
X-Hashcash: 1: 52: 380119: [email protected] ::: 9B760005E92F0DAE
Se verifica con un solo cálculo comprobando que el hash SHA-1 del sello (omita el nombre del encabezado, X-Hashcash:
incluidos los dos puntos y cualquier cantidad de espacio en blanco que lo siga hasta el dígito '1') comience con 52 ceros binarios, es decir 13 ceros hexadecimales: [1]
0000000000000756af69e2ffbdb930261873cd71
Si los sistemas PoW realmente pueden resolver un problema particular de denegación de servicio, como el problema del spam, está sujeto a debate; [4] [5] el sistema debe hacer que el envío de correos electrónicos no deseados sea molestamente improductivo para el emisor de correo no deseado, 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 correo no deseado tendría que gastar una cantidad considerable de potencia informática 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. [4]
Variantes
Hay dos clases de protocolos de prueba de trabajo.
- Los protocolos de desafío-respuesta asumen un vínculo interactivo directo entre el solicitante (cliente) y el proveedor (servidor). El proveedor elige un desafío, digamos un artículo en un conjunto con una propiedad, el solicitante encuentra la respuesta relevante en el conjunto, que es devuelta y verificada por el proveedor. Dado que el proveedor elige el desafío en el lugar, su dificultad se puede adaptar a su carga actual. El trabajo del lado del solicitante puede estar limitado si el protocolo de desafío-respuesta tiene una solución conocida (elegida por el proveedor), o se sabe que existe dentro de un espacio de búsqueda limitado.
- Los protocolos de verificación de solución no asumen tal vínculo: como resultado, 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 ilimitados porque la varianza de una distribución rectangular es menor que la varianza de una distribución de Poisson (con la misma media). [ se necesita más explicación ] Una técnica genérica para reducir la varianza es utilizar múltiples sub-desafíos independientes, ya que el promedio de múltiples muestras tendrá una varianza más baja.
También hay funciones de costo fijo como el rompecabezas de bloqueo de tiempo.
Además, las funciones subyacentes utilizadas por estos esquemas pueden ser:
- Vinculado a la CPU donde el cálculo se ejecuta a la velocidad del procesador, que varía mucho en el tiempo , así como desde un servidor de gama alta hasta dispositivos portátiles de gama baja. [6]
- Límite de memoria [7] [8] [9] [10] donde la velocidad de cálculo está limitada por los accesos a la memoria principal (latencia o ancho de banda), cuyo rendimiento se espera que sea menos sensible a la evolución del hardware.
- Vinculado a la red [11] 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 es realmente realizado por el solicitante, pero de todos modos se produce un retraso debido a la latencia para obtener los tokens requeridos.
Por último, algunos sistemas PoW ofrecen cálculos de acceso directo que permiten a los participantes que conocen un secreto, generalmente una clave privada, generar PoW baratos. La razón es que los titulares de listas de correo pueden generar sellos para cada destinatario sin incurrir en un alto costo. Si tal característica es deseable depende del escenario de uso.
Lista de funciones de prueba de trabajo
Aquí hay una lista de funciones conocidas de prueba de trabajo:
- Raíz cuadrada entera módulo un primo grande [2] [ dudoso ]
- Debilitar las firmas de Fiat-Shamir [2]
- Pollard rompió la firma de Ong-Schnorr-Shamir [2]
- Inversión parcial de hash [12] [13] [1] 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) . [14]
- Secuencias hash [15]
- Rompecabezas [16]
- Rompecabezas basado en Diffie-Hellman [17]
- Moderado [7]
- Mbound [8]
- Hokkaido [9]
- Ciclo del cuco [10]
- Merkle: a base de árbol [18]
- Protocolo de rompecabezas de visitas guiadas [11]
Prueba de trabajo reutilizable
El científico informático Hal Finney se basó en la idea de la prueba de trabajo y dio como resultado un sistema que explotaba la prueba de trabajo reutilizable (RPoW). [19] La idea de hacer que las pruebas de trabajo sean reutilizables para algún propósito práctico ya se había establecido en 1999. [1] El propósito de Finney para RPoW era como dinero simbólico . Así como se cree que el valor de una moneda de oro está respaldado por el valor del oro en bruto necesario para fabricarlo, el valor de una ficha RPoW está garantizado por el valor de los recursos del mundo real necesarios para 'acuñar' una ficha PoW. En la versión de Finney de RPoW, el token de PoW es una pieza de Hashcash .
Un sitio web puede exigir un token de PoW a cambio de un servicio. Exigir un token de PoW a los usuarios inhibiría el uso frívolo o excesivo del servicio, ahorrando los recursos subyacentes del servicio, como ancho de banda a Internet , computación, espacio en disco, electricidad y gastos administrativos.
El sistema RPoW de Finney se diferenciaba de un sistema PoW en que permitía el intercambio aleatorio de tokens sin repetir el trabajo necesario para generarlos. Después de que alguien había "gastado" un token de PoW en un sitio web, el operador del sitio web podía intercambiar ese token de PoW "gastado" por un token de RPoW nuevo no gastado, que luego podría gastarse en algún sitio web de terceros equipado de manera similar para aceptar tokens de RPoW. Esto ahorraría los recursos necesarios para 'acuñar' un token de PoW. La propiedad anti-falsificación del token RPoW estaba garantizada por atestación remota . El servidor RPoW que intercambia un token PoW o RPoW usado por uno nuevo de igual valor utiliza una atestación remota para permitir que cualquier parte interesada verifique qué software se está ejecutando en el servidor RPoW. Dado que el código fuente del software RPoW de Finney se publicó (bajo una licencia similar a BSD ), cualquier programador con conocimientos suficientes podría, inspeccionando el código, verificar que el software (y, por extensión, el servidor RPoW) nunca emitió un nuevo token excepto a cambio de una ficha gastada de igual valor.
Hasta 2009, el sistema de Finney fue el único sistema RPoW que se implementó; nunca vio un uso económicamente significativo.
RPoW está protegido por las claves privadas almacenadas en el hardware del módulo de plataforma confiable (TPM) y los fabricantes que tienen claves privadas de TPM. Robar la clave de un fabricante de TPM u obtener la clave examinando el chip TPM en sí subvertiría esa garantía.
Prueba de trabajo tipo Bitcoin
En 2009, la red Bitcoin se puso en línea. Bitcoin es una prueba de trabajo criptomoneda que, al igual RPoW de Finney, también se basa en la Hashcash PoW. Pero en Bitcoin, la protección contra el doble gasto la proporciona un protocolo P2P descentralizado para rastrear transferencias de monedas, en lugar de la función informática confiable de hardware utilizada por RPoW. Bitcoin tiene una mayor confiabilidad porque está protegido por computación. Los mineros individuales "extraen" los bitcoins mediante la función de prueba de trabajo de Hashcash y los verifican los nodos descentralizados de la red bitcoin P2P.
La dificultad se ajusta periódicamente para mantener el tiempo de bloqueo alrededor de un tiempo objetivo.
Consumo de energía
Desde la creación de Bitcoin, la prueba de trabajo ha sido el diseño predominante de la criptomoneda peer-to-peer. Los estudios han estimado el consumo total de energía de la minería de criptomonedas. [21] El mecanismo PoW requiere una gran cantidad de recursos informáticos, que consumen una cantidad significativa de electricidad. El consumo total de energía de Bitcoin es equivalente al de un país pequeño. [3] Se descubrió que este consumo de energía causa grandes cantidades de emisiones de carbono, lo que interfiere con los compromisos internacionales contemporáneos de mitigación del cambio climático . Según un estudio de 2021, se puede esperar que la minería de Bitcoin solo dentro de China supere pronto las emisiones anuales totales de países europeos como Italia . [22] [23]
Modificación del historial
Cada bloque que se agrega a la cadena de bloques, comenzando con el bloque que contiene una transacción determinada, se denomina confirmación de esa transacción. Idealmente, los comerciantes y servicios que reciben el pago en la criptomoneda deben esperar a que se distribuya al menos una confirmación a través de la red, antes de asumir que el pago se realizó. Cuantas más confirmaciones espere el comerciante, más difícil será para un atacante revertir con éxito la transacción en una cadena de bloques, a menos que el atacante controle más de la mitad de la potencia total de la red, en cuyo caso se denomina ataque del 51% . [24]
ASIC y grupos de minería
Dentro de la comunidad de Bitcoin, hay grupos que trabajan juntos en grupos de minería . [25] Algunos mineros utilizan circuitos integrados de aplicaciones específicas (ASIC) para PoW. [26] Esta tendencia hacia grupos de minería y ASIC especializados ha hecho que la minería de algunas criptomonedas sea económicamente inviable para la mayoría de los jugadores sin acceso a los últimos ASIC, fuentes cercanas de energía económica u otras ventajas especiales. [27]
Algunos PoW afirman ser resistentes a ASIC, es decir, que limitan la ganancia de eficiencia que un ASIC puede tener sobre el hardware básico, como una GPU, por debajo de un orden de magnitud. La resistencia ASIC tiene la ventaja de mantener la minería económicamente viable en hardware básico, pero también contribuye al riesgo correspondiente de que un atacante pueda alquilar brevemente el acceso a una gran cantidad de poder de procesamiento de productos básicos no especializado para lanzar un ataque del 51% contra una criptomoneda. [28]
Ver también
- Bitcoin
- Bitmessage
- Criptomoneda
- Prueba de autoridad
- Prueba de quemadura
- Prueba de personalidad
- Prueba de espacio
- Prueba de participación
- Prueba de tiempo transcurrido
- Consenso (informática)
Notas
- ^ En la mayoría de los sistemas Unix, esto se puede verificar con
echo -n 1:52:380119:[email protected]:::9B760005E92F0DAE | openssl sha1
Referencias
- ^ a b c Jakobsson, Markus; Juels, Ari (1999). "Pruebas de trabajo y protocolos de budín de pan" . Redes de información seguras: comunicaciones y seguridad multimedia . Editores académicos de Kluwer: 258–272. doi : 10.1007 / 978-0-387-35568-9_18 .
- ^ a b c d Dwork, Cynthia ; Naor, Moni (1993). "Fijación de precios a través del procesamiento, o la lucha contra el correo basura, avances en criptología" . CRYPTO'92: Lecture Notes in Computer Science No. 740 . Springer: 139-147. doi : 10.1007 / 3-540-48071-4_10 .
- ^ a b "Criptomonedas y blockchain" (PDF) . Parlamento Europeo . Julio de 2018 . Consultado el 29 de octubre de 2020 .
las dos más conocidas, y en el contexto de las criptomonedas también las más utilizadas
- ^ a b Laurie, Ben; Clayton, Richard (mayo de 2004). "Prueba de trabajo demuestra que no funciona". Taller sobre economía de la seguridad de la información 2004 .
- ^ Liu, Debin; Camp, L. Jean (junio de 2006). "Prueba de trabajo puede funcionar - Quinto taller sobre la economía de la seguridad de la información" .
- ^ ¿Qué tan poderosa era la computadora Apollo 11? , una comparación específica que muestra cómo diferentes clases de dispositivos tienen diferente potencia de procesamiento.
- ^ a b Abadi, Martín ; Burrows, Mike; Manasse, Mark; Wobber, Ted (2005). "Funciones moderadamente difíciles, limitadas a la memoria" . 5 (2): 299–327. Cite journal requiere
|journal=
( ayuda ) - ^ a b Dwork, Cynthia ; Goldberg, Andrew ; Naor, Moni (2003). "Sobre las funciones ligadas a la memoria para combatir el spam" . Avances en criptología: CRYPTO 2003 . Apuntes de conferencias en Ciencias de la Computación. Saltador. 2729 : 426–444. doi : 10.1007 / 978-3-540-45146-4_25 . ISBN 978-3-540-40674-7.
- ^ a b Coelho, Fabien (2005). "Funciones exponenciales vinculadas a la memoria para los protocolos de prueba de trabajo" . Archivo ePrint de criptología, informe .
- ^ a b Tromp, John (2015). "Ciclo del cuco; una prueba de trabajo teórica de gráficos limitada a la memoria" (PDF) . Criptografía financiera y seguridad de datos: BITCOIN 2015 . Apuntes de conferencias en Ciencias de la Computación. Saltador. 8976 : 49–62. doi : 10.1007 / 978-3-662-48051-9_4 . ISBN 978-3-662-48050-2.
- ^ a b Abliz, Mehmud; Znati, Taieb (diciembre de 2009). "Un rompecabezas de visita guiada para la prevención de la denegación de servicio". Actas de la Conferencia Anual de Aplicaciones de Seguridad Informática (ACSAC) 2009 . Honolulu, HI: 279–288. CiteSeerX 10.1.1.597.6304 . doi : 10.1109 / ACSAC.2009.33 . ISBN 978-1-4244-5327-6. S2CID 14434713 .
- ^ Atrás, Adam. "HashCash" .Un sistema PoW popular. Anunciado por primera vez en marzo de 1997.
- ^ Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. (1998). "Frenar el correo electrónico no deseado mediante una clasificación segura" (PDF) . Criptografía financiera : 198–213.
- ^ Wang, Xiao-Feng; Reiter, Michael (mayo de 2003). "Defensa contra ataques de denegación de servicio con subastas de rompecabezas" (PDF) . Simposio IEEE sobre seguridad y privacidad '03 .
- ^ Franklin, Matthew K .; Malkhi, Dahlia (1997). "Medición auditable con seguridad ligera" . Criptografía financiera '97 . Apuntes de conferencias en Ciencias de la Computación. 1318 : 151–160 . doi : 10.1007 / 3-540-63594-7_75 . ISBN 978-3-540-63594-9. Versión actualizada el 4 de mayo de 1998.
- ^ Juels, Ari; Brainard, John (1999). "Rompecabezas del cliente: una defensa criptográfica contra ataques de agotamiento de la conexión". NDSS 99 .
- ^ Waters, Brent; Juels, Ari; Halderman, John A .; Felten, Edward W. (2004). "Nuevas técnicas de outsourcing de rompecabezas de clientes para la resistencia al DoS" (PDF) . XI Conferencia ACM sobre Seguridad Informática y Comunicaciones .
- ^ Coelho, Fabien (2007). "Un protocolo de prueba de trabajo de verificación de solución de (casi) esfuerzo constante basado en árboles de Merkle" . Archivo ePrint de criptología, informe .
- ^ "Pruebas de trabajo reutilizables" . Archivado desde el original el 22 de diciembre de 2007.
- ^ "Índice de consumo de electricidad de Cambridge Bitcoin (CBECI)" . www.cbeci.org . Consultado el 20 de febrero de 2020 .
- ^ "Índice de consumo de electricidad de Cambridge Bitcoin" . Centro de Cambridge para las finanzas alternativas . Consultado el 30 de septiembre de 2020 .
- ^ Lu, Donna. "Las emisiones mineras de Bitcoin en China alcanzarán los 130 millones de toneladas en 2024" . Nuevo científico . Consultado el 9 de mayo de 2021 .
- ^ Jiang, Shangrong; Li, Yuze; Lu, Quanying; Hong, Yongmiao; Guan, Dabo; Xiong, Yu; Wang, Shouyang (6 de abril de 2021). "Evaluaciones de políticas para los flujos de emisión de carbono y la sostenibilidad de la operación de la cadena de bloques de Bitcoin en China" . Comunicaciones de la naturaleza . 12 (1): 1938. Bibcode : 2021NatCo..12.1938J . doi : 10.1038 / s41467-021-22256-3 . ISSN 2041-1723 . PMC 8024295 . PMID 33824331 . Disponible bajo CC BY 4.0 .
- ^ Michael J. Casey; Paul Vigna (16 de junio de 2014). "Correcciones a corto plazo para evitar un" ataque del 51% " " . Money Beat . Wall Street Journal . Consultado el 30 de junio de 2014 .
- ^ Descripción general de los grupos de minería de Bitcoin en blockchain.info
- ^ ¿Qué es un minero ASIC en digitaltrends.com?
- ^ Vorick, David (13 de mayo de 2018). "El estado de la minería de criptomonedas" .
- ^ Savva Shanaev, Arina Shuraeva, Mikhail Vasenin y Maksim Kuznetsov (2019). "Valor de la criptomoneda y ataques del 51%: evidencia de estudios de eventos" . La Revista de Inversiones Alternativas . 22 (3): 65–77. doi : 10.3905 / jai.2019.1.081 . S2CID 211422987 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
enlaces externos
- El sistema de Finney en Wayback Machine (archivado el 22 de diciembre de 2007)
- un poco de oro Un poco de oro . Describe un sistema monetario completo (que incluye generación, almacenamiento, análisis y transferencia) basado en funciones de prueba de trabajo y el problema de arquitectura de la máquina que surge con el uso de estas funciones.