# Prova de treball

Un Sistema de prova de treball o Sistema "POW" (de l'anglès Proof-Of-Work system), és un sistema que, per evitar comportaments indesitjats (per exemple atacs de denegació de servei o spam), requereix que el client del servei realitzi algun tipus de treball que tingui cert cost i que és verificat fàcilment en la part del servidor. Normalment el treball consisteix a realitzar un còmput en l'ordinador del client.
La característica clau de l'estratègia és la seva asimetria: El treball ha de ser moderadament difícil (però factible) pel costat del client, però fàcil de verificar pel costat del servidor.

## Variants de sistemes POW

Existeixen dues classes de protocols per als sistemes POW:
* Els protocols de desafiament-resposta assumeixen un enllaç interactiu directe entre el client i el servidor. El servidor tria un desafiament, per exemple un element d'un conjunt amb una propietat específica; després el client troba una resposta apropiada en el conjunt, la qual és enviada de tornada al servidor, que procedeix a verificar-la. Com el desafiament és triat al moment pel servidor, la seva dificultat pot ser adaptada segons la càrrega actual del servei. El treball per part del client està fitat i la seva variància és baixa.
* Els protocols de solució-verificació no assumeixen un enllaç com en el cas anterior: a causa d'això el desafiament deu ser acte-imposat abans que el client pugui buscar una solució, i el servidor deu verificar punt el desafiament triat com la solució oposada. La majoria dels casos corresponen a procediments iteratius probabilístics no fitats amb alta variància, com Hashcash.
Més encara, les funcions utilitzades pels diferents protocols poden ser de 2 tipus:
* CPU-bound, on el còmput s'executa a la velocitat del processador, que canvia visiblement en el temps seguint la llei de Moore, i també de servidors dedicats a dispositius portàtils.
* Memory-bound on la velocitat de còmput depèn de la velocitat d'accés a la memòria principal (que al seu torn pot estar limitada per latència o amplada de banda insuficient), la qual s'@esperar sigui menys sensitiva a les evolucions de maquinari.
Finalment, alguns sistemes POW ofereixen còmputs de drecera que permeten a participants que coneixen algun secret, típicament una clau privada, accedir al servei generant treball mínim. La idea és que, per exemple, un amo d'una llista de correus pugui enviar missatges a tots els inscrits sense incórrer en un alt cost. Si aquesta característica és o no desitjable depèn de l'escenari en què s'usi el sistema POW.

## Exemple de sistemes
### Hashcash

Hashcash és un mètode que agrega un string a l'encapçalat d'un correu electrònic que prova que l'emissor va dedicar una mica de temps per calcular aquest string. La idea és que com l'emissor li va dedicar temps a calcular el string i enviar el correu, és improbable que aquest sigui spam. D'altra banda el receptor pot, amb un cost computacional gairebé nul, verificar que el string és vàlid.

### Sistema RPOW

Precursors de Bitcoin i basats en Hashcash, un sistema RPOW difereix d'un sistema POW normal en què després que un servidor rep una prova de treball ("moneda POW") d'un client, aquest pot canviar aquesta moneda ja gastada per una altra que no ho estigui, que pot ser utilitzada per accedir a un altre servidor que també requereixi el lliurament d'una prova de treball. D'aquesta manera el servidor s'estalvia el cost de fer el treball requerit, usant en canvi el treball que aquest ha rebut pels seus serveis. L'altre servidor al seu torn també pot canviar la prova de treball rebuda per una altra que pugui usar.

### Bitcoin

Bitcoin utilitza un sistema de prova de treball per a la creació de noves unitats monetàries i per verificar la validesa de les transaccions. En aquest cas, el sistema de prova de treball permet la transferència de valor de manera directa entre els participants d'una transacció sense necessitat de dependre de cap organització central de confiança, ja sigui bancs o qualsevol altra entitat financera.

## Elecció de l'algorisme de prova de treball

Amb l'experiència d'ús dels algorisme de prova de treball, especialment en Bitcoin, s'ha argumentat que l'algorisme triat seria millor si complís certes restriccions:
* Resistència enfront de tecnologies ASIC. En Bitcoin l'especialització del procés de minat, per fer-lo rendible, està provocant que el poder per crear blocs s'estigui centralitzant en aquells que emplean economies d'escala per competir i inverteix en tecnologies ASIC. Això provoca la centralització del poder de producció de blocs en entitats externes. Per aquest inconvenient si es vol usar algorismes de prova de treball és bé que siguin resistents a la tecnologia ASIC.
* Prova de treball útil de l'anglès Proof-Of-Useful-Work. En Bitcoin la quantitat de treball computacional que avui dia es gasta en el procés de mineria és extraordinari. S'estima que s'han gastat diversos centenars de megawatts. Per això es planteja usar algorismes de consens per prova de treball de tal forma que el treball que es realitzi es pugui aprofitar per obtenir algun benefici. Per exemple l'algorisme de consens de Primecoin (busquen nombres primers amb certes característiques) i de Permacoin (basat en emmagatzematge distribuït d'informació donant lloc a l'anomenada prova d'emmagatzematge de l'anglès proof-of-storage o prova de recuperació de l'anglès proof-of-retrievability).

## Vegeu també

* Monero (criptomoneda)

## Referències

* ↑ Lowenthal, Thomas. «Bitcoin: inside the encryted, peer-to-peer digital currency» (en anglès). ArsTechnica.com, 06-08-2011. [Consulta: 3 octubre 2020].
* ↑ Peck, Morgen E. «Bitcoin: The Crytoanarchists' Answer to Cash» (en anglès). IEEE.org, 30-05-2012. [Consulta: 3 octubre 2020].
* ↑ Narayanan, Arvind; Bonneau, Joseph; Felten, Edward; Miller, Andrew; Goldfeder, Steven. «Bitcoin and Cryptocurrency Technologies», 25-08-2015. Arxivat de l'original el 07-08-2017. [Consulta: 3 octubre 2020].

## Enllaços externs

* Hashcash (Inglés)
* Sistema de Finney (Inglés)
* Bit gold. Descriu un sistema monetari complet (including generation, storage, assay, and transfer) basat en funcions POW, i el problema de l'arquitectura de màquines generat per l'ús d'aquestes funcions. (Inglés)
* ↑ Adam Back. HashCash Popular proof-of-work system. First announce in March 1997.
* ↑ 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.
* ↑ 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.
* ↑ Ben Laurie and Richard Clayton. proof-of-work proves not to work. In WEIS 04, May 2004.
* ↑ Fabien Coelho. Exponential memory-bound functions for proof of work protocols. Cryptology ePrint Archive, Report 2005/356.
* ↑ Debin Liu and L Jean Camp. Proof of Work can Work. In Fifth Workshop on the Economics of Information Security, June 2006.