Prueba de trabajo

La prueba de trabajo ( prueba de trabajo en inglés  , POW, PoW ) es el principio de protección de los sistemas de red contra el abuso de los servicios (por ejemplo, de los ataques DoS o la organización de correos no deseados ), basado en la necesidad de realizar un trabajo bastante largo en el lado del cliente (encontrar la solución del problema), cuyo resultado se verifica fácil y rápidamente en el lado del servidor (ver función unidireccional ). La característica principal de los cálculos utilizados es la asimetría de los costos de tiempo: son significativos para encontrar una solución y muy pequeños para la verificación [1] . Dichos esquemas también se conocen como rompecabezas del cliente , rompecabezas computacional o función de fijación de precios de la CPU .

Este método de protección no debe confundirse con los captchas , que ofrecen tareas que son fáciles para una persona, pero difíciles o completamente irresolubles para una computadora. La prueba de trabajo se centra inicialmente en encontrar una solución utilizando un algoritmo previamente conocido en un tiempo finito, pero se requiere un número relativamente pequeño de operaciones para verificar la solución resultante [1] . Las tecnologías POW han recibido la mayor distribución y desarrollo en los sistemas de criptomonedas.

Historia

El requisito de la prueba de trabajo se presentó por primera vez en el artículo "Precio mediante el procesamiento o la lucha contra el correo basura" [1] en 1993. Los autores propusieron la siguiente idea: para acceder a un recurso compartido, el usuario debe calcular alguna función, que es muy compleja y requiere muchos recursos, pero puede resolverse en un tiempo razonable. Calcular una función en el lado del cliente debería ser mucho más difícil que verificar el resultado en el lado del servidor. Uno de los requisitos obligatorios para una función es su no amortización: si se encuentran varias soluciones, el tiempo se requerirá en proporción a su número. Según los autores, tales cálculos adicionales no crean obstáculos para enviar varias cartas ordinarias desde la computadora de un usuario común, pero la necesidad de cálculos constantes hace que el envío de spam requiera muchos recursos. De acuerdo con estimaciones independientes, tales sistemas en realidad conducen a una limitación significativa en la cantidad de cartas que se pueden enviar por día desde una computadora [2] .

En 1997, Adam Back lanzó el proyecto Hashcash , dedicado a la protección contra spam. La tarea se formuló de la siguiente manera: "Encuentre un valor x tal que el hash SHA(x) contenga N bits cero iniciales".

En 1999, aparece el término prueba de trabajo  : se utilizó en el artículo "Proofs of Work and Bread Pudding Protocols" (autores: Markus Jacobsson y Ari Jewels) en la revista Communications and Multimedia Security [3] .

El 16 de agosto de 2004, Hal Finney , en su carta al foro cypherpunk , propuso utilizar pruebas de trabajo reutilizables ( RPOW  , RPoW ) para organizar la moneda electrónica [4] .

Satoshi Nakamoto pronto propuso la criptomoneda bitcoin , donde se utiliza la prueba de trabajo para complicar enormemente el doble gasto . Se propuso encontrar el hash de un bloque de información utilizando la función SHA-256 con la selección de parámetros para que el resultado tenga un número dado de bits altos de cero. Posteriormente, en otras criptomonedas (por ejemplo , Litecoin ), en lugar de SHA-256, se comenzó a utilizar KDF , como scrypt , bcrypt , PBKDF2 y otras [5] .

Ejemplos de funciones aplicables

Lista de las funciones más comunes utilizadas en los sistemas de prueba de trabajo:

• Hashing de inversión parcial . La aplicación más conocida es el sistema Hashcash [6] , que utiliza hashing de inversión parcial cuando se envía por correo electrónico. Para calcular el encabezado de una letra, se requieren alrededor de 252 cálculos hash, que deben volver a calcularse para cada nueva letra. Al mismo tiempo, la verificación de la exactitud del código calculado es rápida: se usa un solo cálculo SHA-1 con una etiqueta preparada previamente [7] [8] [9] .
• Funciones basadas en árboles de Merkle [10] . El ejemplo más famoso de esta variante se puede encontrar en el sistema Bitcoin , donde se utiliza el hashing multinivel como prueba de trabajo: el hash del bloque anterior se convierte en un elemento del siguiente. Por lo tanto, no hay forma de cambiar un bloque sin cambiar los valores hash en todos los bloques posteriores. Al mismo tiempo, la comprobación de la integridad de toda la cadena se limita a un único cálculo de los hash del bloque actual y del anterior. Un hash se reconoce como verdadero solo si el valor de cualquier característica de la suma hash satisface el criterio seleccionado, por ejemplo, en bitcoin: el número de ceros a la izquierda de la suma hash es mayor o igual que el valor de un parámetro especial que determina la dificultad de minado requerida en el momento para mantener la velocidad prevista de aparición de nuevos bloques. Para buscar una suma hash de este tipo, se requiere volver a calcularla varias veces con la enumeración de valores arbitrarios del parámetro nonce [11] .
• Residuo cuadrático módulo un número primo grande [12]
• Firma del protocolo Fiat - Shamira [12]
• Función basada en el protocolo Diffie-Hellman [13]
• Función de límite de memoria ( en:Función de límite de memoria ) [14]
• hash de cuco [15]

Vulnerabilidades potenciales y ataques a los sistemas de información basados ​​en POW

Los expertos continúan debatiendo si la protección POW es lo suficientemente efectiva contra los ataques DoS y el spam [16] [17] .

Ataque 51%

Bitcoin , como muchas otras criptomonedas, puede estar potencialmente sujeta a un "ataque del 51%": si un atacante controla más de la mitad de toda la potencia informática de la red, entonces tiene la oportunidad de confirmar solo sus propios bloques, mientras ignora a los demás. . Esto no solo le permite recibir todas las criptomonedas emitidas al mismo tiempo, sino también bloquear todas o las transacciones seleccionadas, lo que potencialmente puede conducir a la "desaparición" de las cuentas de la criptomoneda recibida de aquellas transacciones que no serán incluidas en el nueva versión de la cadena de bloques [11] .

Doble gasto

El doble gasto (doble gasto) es la transferencia repetida de los mismos activos. Este ataque se divide en varios subtipos.

• Ataque de carrera .  _ _ El atacante realiza la transacción X, pagando la compra de bienes, mientras que simultáneamente transfiere el mismo dinero a su otra cuenta con la transacción Y. Si el vendedor no esperó la confirmación de la transacción y envió los bienes, entonces corrió un gran riesgo. , ya que existe un 50% de posibilidades de que la transacción Y pueda entrar en la cadena real, y esta probabilidad aumenta si el atacante selecciona a propósito los nodos de la red para realizar tal o cual operación [18] .

• El ataque de Finney es el siguiente: el atacante intenta encontrar un bloque que contenga su transacción Y. Sin embargo, una vez que encuentra el bloque, el atacante envía la transacción X, luego de lo cual compra los bienes. El vendedor espera la confirmación de la transacción X y envía la mercancía. Si en este momento aparece un bloque con la transacción Y, entonces se crea una situación de bifurcación en la que los mineros deben elegir uno de los dos bloques para continuar la cadena de bloques. Al concentrar una gran cantidad de recursos informáticos en manos de un atacante, puede aumentar significativamente la probabilidad de elegir un bloque con la operación Y. Por lo tanto, no se garantiza que una transacción confirmada sea válida [19] .

Minería egoísta

En la minería egoísta, el objetivo del atacante  es controlar la red, a pesar de que tiene recursos informáticos con una capacidad total inferior al 50%. Esto se logra por el hecho de que el atacante afirma que su grupo es más rentable para la minería que otros grupos, lo que atrae a mineros externos. El atacante publica bloques de tal manera que se desperdician los recursos informáticos de otros mineros y grupos. El curso aproximado del algoritmo es el siguiente:

1. El grupo extrae en secreto su cadena privada de todos.
2. Si el grupo encuentra un nuevo bloque para su cadena privada, entonces:
   1. Si la cadena original se bifurca, el atacante publica su bloque, por lo que su cadena se vuelve más larga y se vuelve verdadera, y la cadena de mineros honestos se descarta.
   2. Si aún no hay bifurcación, entonces el grupo continúa minando en secreto su cadena privada, aumentando su liderazgo.
3. Si la cadena pública encuentra un bloque para la cadena pública, entonces:
   1. Si la cadena pública está por delante de la secreta, el grupo del atacante descarta sus bloques no publicados y comienza a extraer del nuevo bloque público.
   2. Si las cadenas son iguales, entonces el grupo del atacante publica todos sus bloques, yendo así al hueco de su cadena.
   3. Si la cadena pública está algunos (N) bloques detrás de la cadena privada, entonces el grupo publica un bloque más (N+1), que aísla un nuevo bloque honesto.

En casi todos los resultados, los mineros honestos son los perdedores, obligándolos a unirse al grupo criminal [20] .

Críticas a los sistemas de información basados ​​en POW

Quienes se oponen al enfoque POW, además de una serie de posibles problemas de seguridad , destacan las siguientes desventajas:

• La probabilidad de creación exitosa del próximo bloque por parte del minero es directamente proporcional a la potencia de cómputo que tiene, lo que conduce a un aumento constante en la cantidad y calidad de los equipos para cada miembro de la red. Por lo tanto, la minería con algoritmos POW requiere una cantidad extremadamente grande de electricidad. Por lo tanto, el enfoque POW no es la mejor solución en términos de eficiencia energética [21] [22] .
• Los resultados de la computación de funciones hash no son necesarios en ninguna parte, excepto en la propia red. Desde el advenimiento de la tecnología, la comunidad ha estado tratando de idear una forma de dirigir todos los recursos informáticos de la red para resolver algún problema matemático o industrial útil, pero esto no se ha implementado en su forma pura [23] .

Los intentos de deshacerse de las deficiencias de POW han llevado a la aparición de POS ( prueba de participación en inglés  , prueba de participación) y numerosas opciones híbridas.

Ejemplos de tecnologías híbridas

Se pueden encontrar ejemplos de esquemas híbridos que combinan las ideas de POS y POW en muchas criptomonedas. En ellos, la cadena de bloques se compone de bloques de ambos tipos, lo que dificulta la tarea de reescribir los historiales de transacciones, ya que los bloques POW sirven como puntos de control, dada la complejidad total del trabajo en toda la cadena. Por lo general, en dichos algoritmos, los bloques POW sirven como indicadores de trabajo real, lo que brinda una garantía adicional de confiabilidad para los comerciantes cuando trabajan con transacciones. Los bloques POW se pueden usar para emitir moneda, y los bloques POS se pueden considerar como ingresos potenciales del depósito [24] .

Prueba de actividad

Un prototipo de algoritmo que aún no se ha implementado, que consiste en que los titulares ingresan al proceso general solo después de que los participantes de POW hayan realizado algún trabajo, lo que reduce las posibilidades de un ataque del 51%, ya que el propietario mayoritario no podrá controlar únicamente la creación de nuevos bloques [25] .

Cómo funciona el algoritmo:

1. El minero POW busca un hash de la dificultad adecuada.
2. El hash encontrado se envía a la red, sin ser un bloque, sino solo el primer paso, una especie de plantilla necesaria para su creación.
3. Un hash que consta de 256 bits pseudoaleatorios se interpreta como N números, a cada uno de los cuales se le asigna un satoshi.
4. Se establece una relación uno a uno entre cada satoshi y la clave pública de su propietario actual.
5. Tan pronto como todos los N propietarios pongan sus firmas en este bloque, la salida es un bloque completo.
6. Si uno de los titulares no está disponible o no participa en la minería, el resto de los mineros continúan generando plantillas con diferentes combinaciones de candidatos a titulares.
7. En algún momento, el bloque requerido se firmará el número requerido de veces. La recompensa del bloque se distribuye entre el minero POW y todos los titulares de N.

Prueba de quemado

El dinero se envía a una dirección que es un hash de un número aleatorio, se garantiza que no se puede gastar desde esta dirección, ya que la probabilidad de recoger las llaves de la misma tiende a cero. A cambio, el minero tiene la oportunidad permanente de encontrar un bloque PoB y recibir una recompensa por ello. La minería en este caso está organizada de tal manera que las posibilidades de éxito dependen de la cantidad de monedas quemadas. Por analogía, la quema es como un depósito de POS no reembolsable o una inversión en hardware virtual para la minería POW. Desde un punto de vista económico, este algoritmo es más adecuado para las últimas etapas del desarrollo de las criptomonedas, cuando ya se ha generado la mayor parte de la oferta monetaria [26] .

Prueba de capacidad

El algoritmo de prueba de capacidad (o prueba de espacio ) es el siguiente: para la minería, es necesario asignar una cantidad significativa de memoria en la computadora, después de lo cual se crea una gran cantidad de grandes bloques de datos a partir de la clave pública y números aleatorios. por hashing repetido . En cada bloque de datos, obtenemos un índice del último encabezado, después de lo cual seleccionamos una pequeña parte del bloque con este índice, un fragmento .  Cuanta más memoria se asigna, más fragmentos obtenemos. Se debe cumplir la condición de que el hash del fragmento y el último encabezado deben ser menores que el objetivo. Por lo tanto, cada megabyte de memoria se utiliza como un análogo de un boleto de lotería y aumenta las posibilidades de éxito en la minería [27] .

Prueba de investigación

El algoritmo de prueba de investigación fue desarrollado por el proyecto GridCoin para dirigir el poder de cómputo de las redes PoW para resolver problemas científicos en la plataforma BOINC . La prueba de investigación utiliza simultáneamente la prueba de trabajo para recompensar a los participantes por los cálculos completados y la prueba de participación para alentar la participación a largo plazo en el proyecto [28] .

Ineficiencia energética

Los sistemas basados ​​en POW son extremadamente intensivos en recursos.

• En 2013, la potencia informática total gastada en POW en la red Bitcoin superó 256 veces las 500 supercomputadoras más poderosas del mundo combinadas ese año [29] .
• En 2017, se necesitaba un promedio de 163 kWh de energía para completar una transacción en el sistema Bitcoin . Con esta cantidad de energía es posible cubrir por completo las necesidades de una familia de tres personas que vive en una casa pequeña de un piso durante cinco días y medio. La minería de criptomonedas en las redes Bitcoin y Ethereum tomó un total de más energía que la que consumió toda la población de Siria [21] [22] .

Véase también

• captcha
• Bitmensaje
• Criptosistema de clave pública
• función unidireccional

Notas

1. ↑ 1 2 3 Precios a través del procesamiento o la lucha contra el correo no deseado Archivado el 12 de diciembre de 2017 en Wayback Machine (1993  )
2. ↑ "Proof-of-Work" Proves Not to Work Archivado el 20 de enero de 2017 en Wayback Machine , 2004 "Si tratamos de hacer que sea antieconómico enviar spam, entonces debemos restringir a los remitentes a 1750 mensajes por día".
3. ↑ Pruebas de trabajo y protocolos de budín de pan Archivado el 26 de julio de 2017 en Wayback Machine (1999  )
4. ↑ RPOW - Pruebas de trabajo reutilizables Archivado el 5 de octubre de 2017 en Wayback Machine (2004  )
5. ↑ La prueba de trabajo en criptomonedas: breve historia. Parte 1 Archivado el 5 de septiembre de 2017 en Wayback Machine (2015  )
6. ↑ Hashcash - Una contramedida de denegación de servicio (2002  )
7. ↑ Atrás, Adam HashCash . Consultado el 25 de junio de 2022. Archivado desde el original el 29 de septiembre de 2017.  (indefinido) Popular sistema de prueba de trabajo. Primer anuncio en marzo de 1997.
8. ↑ Gabber, Eran; Jakobsson, Markus; Matías, Yossi; Mayer, Alain J. Frenar el correo electrónico no deseado a través de la clasificación segura  (neopr.)  // Criptografía financiera. - 1998. - S. 198-213 .
9. ↑ Wang, Xiao Feng; Reiter, Michael. Defensa contra ataques de denegación de servicio con subastas de rompecabezas  //  Simposio IEEE sobre seguridad y privacidad '03: revista. - 2003. - Mayo.
10. ↑ Coelho, Fabien Un (casi) protocolo de prueba de trabajo de verificación de solución de esfuerzo constante basado en árboles de Merkle . Archivo ePrint de criptología, Informe . Consultado el 29 de octubre de 2017. Archivado desde el original el 26 de agosto de 2016. (indefinido)
11. ↑ 1 2 Bitcoin: A Peer-to-Peer Electronic Cash System Archivado el 20 de marzo de 2014 en Wayback Machine . 
12. ↑ 1 2 Dwork, Cynthia; Naor, Moni Fijación de precios mediante el procesamiento o la lucha contra el correo no deseado, avances en criptología  //  CRYPTO'92: Apuntes de conferencias sobre informática n. 740: diario. - Springer, 1993. - P. 139-147 .
13. ↑ Aguas, Brent; Juels, Ari; Halderman, John A.; FeltenEdward W.Nuevas técnicas de subcontratación de rompecabezas de clientes para resistencia DoS  (neopr.)  // 11ª Conferencia ACM sobre seguridad informática y de comunicaciones. — 2004.
14. ↑ Dwork, Cynthia; Goldberg, Andrés; Naor, MoniSobre funciones vinculadas a la memoria para combatir el spam  (neopr.)  // Avances en criptología: CRYPTO 2003. - Springer, 2003. - Vol. 2729 . - S. 426-444 .
15. ↑ Trompo, John. Ciclo del cuco; una prueba de trabajo teórica de grafos ligada a la memoria  //  Criptografía financiera y seguridad de datos: BITCOIN 2015: revista. - Springer, 2015. - Pág. 49-62 .
16. ↑ Laurie, Ben; Clayton, Ricardo. La prueba de trabajo demuestra que no funciona  (neopr.)  // WEIS 04. - 2004. - mayo.
17. ↑ Liu, Debin; Campamento, L. Jean. Prueba de Trabajo puede funcionar  (neopr.)  // Quinto Taller de Economía de la Seguridad de la Información. - 2006. - Junio.
18. ↑ Ataques en el mundo de las criptomonedas Archivado el 19 de septiembre de 2016 en Wayback Machine . 
19. ↑ Análisis del doble gasto basado en hashrate. Archivado el 4 de septiembre de 2017 en Wayback Machine (2012  ).
20. ↑ Ataques en el mundo de las criptomonedas Archivado el 19 de septiembre de 2016 en Wayback Machine (2015  )
21. ↑ 1 2 Índice de consumo de energía de Bitcoin Archivado el 25 de enero de 2022 en Wayback Machine . 
22. ↑ 1 2 Índice de consumo de energía de Ethereum (beta) Archivado el 11 de octubre de 2017 en Wayback Machine . 
23. ↑ La prueba de trabajo en criptomonedas: breve historia. Parte 2 Archivado el 14 de marzo de 2016 en Wayback Machine . 
24. ↑ Alternativas para la prueba de trabajo, Parte 2 Archivado el 4 de marzo de 2016 en Wayback Machine (2015  )
25. ↑ Prueba de actividad: extensión de la prueba de trabajo de Bitcoin a través de la prueba de participación . Archivado el 17 de octubre de 2017 en Wayback Machine . 
26. ↑ Una criptomoneda punto a punto con prueba de grabación "Minería sin hardware potente" Archivado el 10 de octubre de 2017 en Wayback Machine (2014  )
27. ↑ Proofs of Space: When Space is of the Essence Archivado el 5 de noviembre de 2017 en Wayback Machine . 
28. ↑ Prueba de investigación - Gridcoin  . wiki.gridcoin.us. Consultado el 4 de septiembre de 2018. Archivado desde el original el 4 de septiembre de 2018.
29. ↑ ¡El poder informático global de Bitcoin ahora es 256 veces más rápido que las 500 supercomputadoras principales, combinadas! Archivado el 8 de junio de 2017 en Wayback Machine (2013  )