Un Proof-of-work system (o Sistema "POW") es una medida para evitar los ataques de denegación de servicio y otros abusos como el spam en una red requiriendo algún trabajo por parte del cliente del servicio, que usualmente es un cómputo que se hace en el computador del cliente. Una característica clave de estas medidas es su asimetría: el trabajo debe ser moderadamente difícil (pero factible) por el lado del cliente, pero fácil de verificar por el lado del servidor. Uno de los sistemas POW más populares es el Hashcash.^[1]

Si los sistemas POW pueden o no resolver un problema de denegación de servicio en particular, como el problema del spam es un tema de debate:^{[2] [3]} por una parte el sistema debe hacer que el envío de spam sea prohibitivamente caro (en términos del trabajo que debe realizar el computador), pero por otra parte no puede entorpecer a los usuarios legítimos del servicio.

Contenido 1 Variantes de sistemas POW 2 Hashcash 3 Sistema RPOW (Reusable Proof-of-Work System) 4 Referencias 5 Enlaces externos

Variantes de sistemas POW

Existen 2 clases de protocolos para los sistemas POW:

• Los protocolos de desafío-respuesta asumen un enlace interactivo directo entre el cliente y el servidor. El servidor elige un desafío, por ejemplo un elemento de un conjunto con una propiedad específica, luego el cliente encuentra una respuesta apropiada en el conjunto, la cual es enviada de vuelta al servidor, que procede a verificarla. Como el desafío es elegido en el momento por el servidor, su dificultad puede ser adaptada según la carga actual del servicio. El trabajo por parte del cliente está acotado y su varianza es baja.

• Los protocolos de solución-verificación no asumen un enlace como en el caso anterior: debido a esto el desafío debe ser auto-impuesto antes de que el cliente pueda buscar una solución, y el servidor debe verificar tanto el desafío elegido como la solución encontrada. La mayoría de los casos corresponden a procedimientos iterativos probabilísticos no acotados con alta varianza, como Hashcash.

Más aún, las funciones utilizadas por los distintos protocolos pueden ser de 2 tipos:

• CPU-bound, donde el cómputo se ejecuta a la velocidad del procesador, que cambia visiblemente en el tiempo siguiendo la ley de Moore, y también de servidores dedicados a dispositivos portátiles.

• Memory-bound^{[4] [5] [6]} donde la velocidad de cómputo depende de la velocidad de acceso a la memoria principal (que a su vez puede estar limitada por latencia o ancho de banda insuficiente), la cual se espera que sea menos sensitiva a las evoluciones de hardware.

Finalmente, algunos sistemas POW ofrecen cómputos de atajo que permiten a participantes que conocen algún secreto, típicamente una llave privada, acceder al servicio generando trabajo mínimo. La idea es que, por ejemplo, un dueño de una lista de correos pueda enviar mensajes a todos los inscritos sin incurrir en un alto costo. Si esta característica es o no deseable depende del escenario en que se use el sistema POW.

Hashcash

Hashcash es un método para agregar un string al encabezado de un correo electrónico para probar que el emisor dedicó un poco de tiempo para calcular el string. En otras palabras, como el emisor le dedicó tiempo a calcular el string y enviar el correo, es improbable que éste sea spam. El receptor puede, con un costo computacional casi nulo, verificar que el string es válido. La idea es que la única manera de generar un string que sea válido es por fuerza bruta, es decir probando con varios valores hasta encontrar un string válido; mientras que comprobar si un string es válido es fácil.

En teoría, este método evita el spam, puesto que el modelo de negocios de los spammers se basa en la idea de que puedan enviar un gran número de mensajes con un costo bajo por cada uno. Además, los receptores pueden verificar si el emisor dedicó tiempo al cálculo del string, y usar los resultados como ayuda para filtrar los mensajes que reciben.

El Hashcash usa inversiones parciales de hash como prueba de que se hizo trabajo para enviar un correo electrónico. Por ejemplo el encabezado siguiente representa cerca de 2⁴⁰ cómputos de hash para enviar un mensaje a hobbes@comics el 19 de marzo de 2017:

   X-Hashcash: 1:40:170319:hobbes@comics::eb9a45d0eac8b65a:159b56eb15c

Este string es normalmente verificado con una única operación, comprobando que su hash SHA-1 comienza con 40 ceros en notación binaria, o equivalentemente con 10 ceros en notación hexadecimal: 00000000009f0b34697d40bf80d000a3a0646cd9

Sistema RPOW (Reusable Proof-of-Work System)

Un sistema RPOW difiere de un sistema POW normal en que después de que un servidor recibe una prueba de trabajo ("moneda POW") de un cliente, éste puede cambiar esta moneda ya gastada por otra que no lo esté, que puede ser utilizada para acceder a otro servidor que también requiera la entrega de una prueba de trabajo. De esta manera el servidor se ahorra el costo de hacer el trabajo requerido, usando en cambio el trabajo que éste ha recibido por sus servicios. El otro servidor a su vez también puede cambiar la prueba de trabajo recibida por otra que pueda usar.

Estas pruebas de trabajo reusables ("monedas RPOW tokens") tienen propiedades anti-falsificación/anti-inflación garantizadas por una técnica llamada certificación a distancia. En particular, el "servidor RPOW" en donde se pueden cambiar las monedas ya usadas, utiliza esta técnica para permitir que cualquier agente con el suficiente conocimiento e interés pueda verificar qué aplicación está corriendo en el servidor. La idea es que el código fuente de la aplicación esté disponible públicamente, para que cualquier programador con el conocimiento suficiente pueda revisarlo y asegurarse de que la aplicación (y por extensión el servidor RPOW) sólo genera una nueva moneda si recibe una ya gastada, y de que no exista manera de que el operador del servidor pueda modificar el comportamiento de la aplicación.

Actualmente, el sistema creado por Hal Finney es el único sistema que se encuentra implementado, y aún no ha visto un uso significante. La aplicación está implementada en 12.000 líneas de código C.

Referencias

^{[1] [4] [5] [2] [6] [3]}

1. ↑ ^{a b} Adam Back. HashCash Popular proof-of-work system. First announce in March 1997.
2. ↑ ^{a b} Ben Laurie and Richard Clayton. proof-of-work proves not to work. In WEIS 04, May 2004.
3. ↑ ^{a b} Debin Liu and L Jean Camp. Proof of Work can Work. In Fifth Workshop on the Economics of Information Security, June 2006.
4. ↑ ^{a b} Martín Abadi, Mike Burrows, Mark Manasse, and Ted Wobber. Moderately hard, memory-bound functions. In 10th Annual Network and Distributed System Security Symposium (NDSS), San Diego, CA, USA, February 2003. Also in ACM Trans. Inter. Tech., 5(2):299-327, 2005.
5. ↑ ^{a b} Cynthia Dwork, Andrew Goldberg, and Moni Naor. On memory-bound functions for fighting spam. In Advances in Cryptology - CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 426-444. Springer, 2003.
6. ↑ ^{a b} Fabien Coelho. Exponential memory-bound functions for proof of work protocols. Cryptology ePrint Archive, Report 2005/356.

Enlaces externos

• Hashcash (Inglés)
• Sistema de Finney (Inglés)
• Bit gold. Describe un sistema monetario completo (including generation, storage, assay, and transfer) basado en funciones POW, y el problema de la arquitectura de máquinas generado por el uso de estas funciones. (Inglés)