Proof-of-work
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 [email protected] il 19 gennaio 2038:
X-Hashcash: 1:52:380119:[email protected]:::9B760005E92F0DAE
È verificabile con un singolo calcolo controllando l'hash SHA-1 del 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.
Dopo diversi anni in cui si è proposto l'utilizzo del protocollo POW sulla rete Tor [1], gli sviluppatori dietro il progetto Tor hanno finalmente deciso di utilizzare un sistema POW per proteggere gli Onion Services dagli attacchi DoS che affliggono la rete[2].
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).
- 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 sia la scelta del problema che la soluzione trovata. La maggior parte di tali schemi sono procedure iterative probabilistiche illimitate come Hashcash.
Elenco di funzioni proof of work
[modifica | modifica wikitesto]- Modulo di radice quadrata di un intero di un grande numero primo[3]
- Weaken Fiat–Shamir signatures[3]
- Ong–Schnorr–Shamir signature broken di Pollard[3]
- Inversione hash parziale[4][5][6][7] come Hashcash
- Sequenze Hash[8]
- Puzzle[9]
- Diffie-Hellman basato su puzzle[10]
- Moderate[11]
- Mbound[12]
- Hokkaido[13]
- Basato sull'Albero di Merkle[14]
- Guided tour puzzle protocol (protocollo puzzle tour guidato)[15]
Note
[modifica | modifica wikitesto]- ^ jessecm, Proof of Work su Tor: si può fare?, su Bitcoin24ORE, 6 aprile 2023. URL consultato il 31 agosto 2023.
- ^ Introducing Proof-of-Work Defense for Onion Services | Tor Project, su blog.torproject.org. URL consultato il 31 agosto 2023.
- ^ 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.
- ^ Adam Back, HashCash, su hashcash.org. Popular proof-of-work system. First announce in March 1997.
- ^ Eran Gabber, Markus Jakobsson, Yossi Matias e Alain J. Mayer, Curbing junk e-mail via secure classification, in Financial Cryptography, 1998, pp. 198–213.
- ^ 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.
- ^ 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. URL consultato il 5 dicembre 2013 (archiviato dall'url originale il 3 marzo 2016).
- ^ Matthew K. Franklin e Dahlia Malkhi, Auditable metering with lightweight security, in Financial Cryptography '97, 1997. Updated version May 4, 1998.
- ^ Ari Juels e John Brainard, Client puzzles: A cryptographic defense against connection depletion attacks, in NDSS 99, 1999.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Fabien Coelho, Exponential memory-bound functions for proof of work protocols, su Cryptology ePrint Archive, Report.
- ^ Fabien Coelho, An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees, su Cryptology ePrint Archive, Report.
- ^ 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 rpow.net. URL consultato il 3 maggio 2019 (archiviato dall'url originale il 22 dicembre 2007).
- (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.
