Proof-of-work

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Un sistema proof-of-work (POW) o protocollo proof-of-work, o funzione proof-of-work è una misura economica per scoraggiare attacchi denial of service (negazione di servizio) e altri abusi di servizio, come spam sulla rete, imponendo alcuni lavori dal richiedente del servizio, di solito intendendo tempo di elaborazione di un computer. Una caratteristica chiave di questi schemi è la loro asimmetria: il lavoro deve essere moderatamente complesso (ma fattibile) dal lato richiedente ma facile da controllare per il fornitore del servizio (service provider). Questa idea è anche conosciuta come funzione di costo della CPU, client puzzle, puzzle computazione o funzione di pricing della CPU.

Un sistema famoso, usato anche nella creazione di moneta Bitcoin è l'hashcash, che usa inversioni di hash parziali per verificare che il lavoro sia fatto, come token di buona volontà da inviare via e-mail. La seguente intestazione (header) rappresenta i calcoli di circa 252 hash per inviare un messaggio a calvin@comics.net il 19 gennaio 2038:

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

È verificabile con un singolo calcolo controllando l'hash SHA-1 dello timbro (omette la porzione "X-Hashcash:") cominciando con 52 zeri binari, che corrispondono a 13 zeri esadecimali: 0000000000000756af69e2ffbdb930261873cd71.

È ancora oggetto di dibattito se i sistemi POW siano in grado di risolvere particolari casi di denial of service, come nel caso del problema spam.

I sistemi Proof-of-work sono usati come primitive da altri più complessi sistemi crittografici come quello che usa Bitcoin, un sistema simile a Hashcash.

Varianti[modifica | modifica wikitesto]

  • Challenge response (Risposta di sfida): i protocolli di questo tipo prendono un collegamento interattivo diretto tra il richiedente (client) ed il fornitore (server).
Proof of Work challenge response.svg
  • Solution-verification (Soluzione-Verifica): questi protocolli non hanno un collegamento: il problema è autoimposto prima che una soluzione venga richiesta dal richiedente, ed il fornitore deve controllare che sia la scelta del problema che la soluzione trovata. La maggior parte di tali schemi sono procedure iterative probabilistiche illimitate come Hashcash.
Proof of Work solution verification.svg

Elenco di funzioni proof of work[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ a b c Cynthia Dwork e Moni Naor, Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology (ps), in CRYPTO’92: Lecture Notes in Computer Science No. 740, Springer, 1993, pp. 139–147.
  2. ^ Adam Back, HashCash, su hashcash.org. Popular proof-of-work system. First announce in March 1997.
  3. ^ Eran Gabber, Markus Jakobsson, Yossi Matias e Alain J. Mayer, Curbing junk e-mail via secure classification, in Financial Cryptography, 1998, pp. 198–213.
  4. ^ Markus Jakobsson e Ari Juels, Proofs of Work and Bread Pudding Protocols, in Communications and Multimedia Security, Kluwer Academic Publishers, 1999, pp. 258–272. This paper formalizes the idea of a proof of work (POW) and introduces "the dependent idea of a bread pudding protocol", a "re-usable proof of work" (RPOW) system.
  5. ^ Xiao-Feng Wang e Michael Reiter, Defending against denial-of-service attacks with puzzle auctions (PDF), in IEEE Symposium on Security and Privacy '03, maggio 2003.
  6. ^ Matthew K. Franklin e Dahlia Malkhi, Auditable metering with lightweight security, in Financial Cryptography '97, 1997. Updated version May 4, 1998.
  7. ^ Ari Juels e John Brainard, Client puzzles: A cryptographic defense against connection depletion attacks, in NDSS 99, 1999.
  8. ^ Brent Waters, Ari Juels, John A. Halderman e Edward W. Felten, New client puzzle outsourcing techniques for DoS resistance, in 11th ACM Conference on Computer and Communications Security, 2004.
  9. ^ Martín Abadi, Mike Burrows, Mark Manasse e Ted Wobber, Moderately hard, memory-bound functions, in ACM Trans. Inter. Tech., vol. 5, nº 2, 2005, pp. 299–327.
  10. ^ Cynthia Dwork, Andrew Goldberg e Moni Naor, On memory-bound functions for fighting spam, in Advances in Cryptology: CRYPTO 2003, vol. 2729, Springer, 2003, pp. 426–444.
  11. ^ Fabien Coelho, 2005/356 Exponential memory-bound functions for proof of work protocols, su Cryptology ePrint Archive, Report.
  12. ^ Fabien Coelho, An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees, su Cryptology ePrint Archive, Report.
  13. ^ Mehmud Abliz e Taieb Znati, A Guided Tour Puzzle for Denial of Service Prevention, in Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009, Honolulu, HI, dicembre 2009, pp. 279–288.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  • (EN) Finney's system, su web.archive.org.
  • (EN) Bit gold. Describes a complete money system (including generation, storage, assay, and transfer) based on proof of work functions and the machine architecture problem raised by the use of these functions.