TY - GEN
T1 - Proofs of space
T2 - 9th International Conference on Security and Cryptography for Networks, SCN 2014
AU - Ateniese, Giuseppe
AU - Bonacina, Ilario
AU - Faonio, Antonio
AU - Galesi, Nicola
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPUbound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses. In this paper we put forward a new concept dubbed proof of space. To compute such a proof, the prover must use a specified amount of space, i.e., we are not interested in the number of accesses to the main memory (as in memory-bound proof of work) but rather on the amount of actual memory the prover must employ to compute the proof. We give a complete and detailed algorithmic description of our model. We develop a full theoretical analysis which uses combinatorial tools from Complexity Theory (such as pebbling games) which are essential in studying space lower bounds.
AB - Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPUbound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses. In this paper we put forward a new concept dubbed proof of space. To compute such a proof, the prover must use a specified amount of space, i.e., we are not interested in the number of accesses to the main memory (as in memory-bound proof of work) but rather on the amount of actual memory the prover must employ to compute the proof. We give a complete and detailed algorithmic description of our model. We develop a full theoretical analysis which uses combinatorial tools from Complexity Theory (such as pebbling games) which are essential in studying space lower bounds.
KW - Pebbling Game
KW - Proof of Work
KW - Random Oracle Model
KW - Space Complexity
UR - http://www.scopus.com/inward/record.url?scp=84927645826&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84927645826&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-10879-7_31
DO - 10.1007/978-3-319-10879-7_31
M3 - Conference contribution
AN - SCOPUS:84927645826
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 538
EP - 557
BT - Security and Cryptography for Networks - 9th International Conference, SCN 2014, Proceedings
A2 - Abdalla, Michel
A2 - de Prisco, Roberto
Y2 - 3 September 2014 through 5 September 2014
ER -