{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T08:58:48Z","timestamp":1771232328075,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662479995","type":"print"},{"value":"9783662480007","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48000-7_29","type":"book-chapter","created":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T02:27:46Z","timestamp":1438309666000},"page":"585-605","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":212,"title":["Proofs of Space"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Dziembowski","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Faust","sequence":"additional","affiliation":[]},{"given":"Vladimir","family":"Kolmogorov","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Pietrzak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,1]]},"reference":[{"key":"29_CR1","unstructured":"Abadi, M., Burrows, M., Wobber, T.: Moderately hard and memory-bound functions. In: NDSS 2003. The Internet Society, February 2003"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Symposium on Theory of Computing, STOC 2015 (2015)","DOI":"10.1145\/2746539.2746622"},{"key":"29_CR3","unstructured":"Anderson, N.: Mining Bitcoins takes power, but is it an \u201cenvironmental disaster\u201d? April 2013. http:\/\/tinyurl.com\/cdh95at"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1007\/978-3-319-10879-7_31","volume-title":"Security and Cryptography for Networks","author":"G Ateniese","year":"2014","unstructured":"Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538\u2013557. Springer, Heidelberg (2014)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Kissner, L., Peterson, Z.N.J., Song, D.: Provable data possession at untrusted stores. In: Ning, P., De Capitani di Vimercati, S., Syverson, P.F. (eds.) ACM CCS 2007, pp. 598\u2013609. ACM Press, October 2007","DOI":"10.1145\/1315245.1315318"},{"key":"29_CR6","unstructured":"Back, A.: Hashcash - a denial of service counter-measure (2002). http:\/\/www.hashcash.org\/papers\/hashcash.pdf"},{"issue":"5","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B Barak","year":"2008","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661\u20131694 (2008)","journal-title":"SIAM J. Comput."},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, pp. 62\u201373. ACM Press, November 1993","DOI":"10.1145\/168588.168596"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: theory and implementation. In: CCSW, pp. 43\u201354 (2009)","DOI":"10.1145\/1655008.1655015"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Kouck\u00fd, M., Loff, B., Speelman, P.: Computing with a full memory: catalytic space. In: Symposium on Theory of Computing, STOC 2014, May 31 - June 03 2014, pp. 857\u2013866, New York, NY, USA (2014)","DOI":"10.1145\/2591796.2591874"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC, pp. 209\u2013218. ACM Press, May 1998","DOI":"10.1145\/276698.276741"},{"key":"29_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11818175_10","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"R Canetti","year":"2006","unstructured":"Canetti, R., Halevi, S., Steiner, M.: Mitigating dictionary attacks on password-protected local storage. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 160\u2013179. Springer, Heidelberg (2006)"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Di Pietro, R., Mancini, L.V., Law, Y.W., Etalle, S., Havinga, P.: Lkhw: a directed diffusion-based secure multicast scheme for wireless sensor networks. In: 2003 Proceedings of the International Conference on Parallel Processing Workshops, pp. 397\u2013406 (2003)","DOI":"10.1109\/ICPPW.2003.1240395"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/3-540-45748-8_24","volume-title":"Peer-to-Peer Systems","author":"JR Douceur","year":"2002","unstructured":"Douceur, J.R.: The sybil attack. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251\u2013260. Springer, Heidelberg (2002)"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-540-45146-4_25","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"C Dwork","year":"2003","unstructured":"Dwork, C., Goldberg, A.V., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426\u2013444. Springer, Heidelberg (2003)"},{"key":"29_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139\u2013147. Springer, Heidelberg (1993)"},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11535218_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"C Dwork","year":"2005","unstructured":"Dwork, C., Naor, M., Wee, H.M.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37\u201354. Springer, Heidelberg (2005)"},{"key":"29_CR18","unstructured":"Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. Cryptology ePrint Archive, Report 2013\/796 (2013). http:\/\/eprint.iacr.org\/2013\/796"},{"key":"29_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-642-22792-9_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S Dziembowski","year":"2011","unstructured":"Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335\u2013353. Springer, Heidelberg (2011)"},{"key":"29_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-19571-6_9","volume-title":"Theory of Cryptography","author":"S Dziembowski","year":"2011","unstructured":"Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125\u2013143. Springer, Heidelberg (2011)"},{"key":"29_CR21","unstructured":"Erd\u00f6s, P., Graham, R.L., Szemer\u00e9di, E.: On sparse graphs with dense long paths. Technical report STAN-CS-75-504, Stanford University, Computer Science Department (1975)"},{"key":"29_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-63594-7_75","volume-title":"Financial Cryptography","author":"KM Franklin","year":"1997","unstructured":"Franklin, K.M., Malkhi, D.: Auditable metering with lightweight security. In: Luby, M., Rolim, J.D.P., Serna, M. (eds.) FC 1997. LNCS, vol. 1318, pp. 151\u2013160. Springer, Heidelberg (1997)"},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th FOCS, pp. 102\u2013115. IEEE Computer Society Press, October 2003","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"29_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-36504-4_9","volume-title":"Financial Cryptography","author":"P Golle","year":"2003","unstructured":"Golle, P., Jarecki, S., Mironov, I.: Cryptographic primitives enforcing communication and storage complexity. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 120\u2013135. Springer, Heidelberg (2003)"},{"issue":"2","key":"29_CR25","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1109\/MSP.2007.28","volume":"5","author":"V Gratzer","year":"2007","unstructured":"Gratzer, V., Naccache, D.: Alien vs. quine. IEEE Secur. Priv. 5(2), 26\u201331 (2007)","journal-title":"IEEE Secur. Priv."},{"key":"29_CR26","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: 48th FOCS, pp.669\u2013679. IEEE Computer Society Press, October 2007","DOI":"10.1109\/FOCS.2007.7"},{"issue":"4","key":"29_CR27","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"ME Hellman","year":"1980","unstructured":"Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401\u2013406 (1980)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"29_CR28","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J Hopcroft","year":"1977","unstructured":"Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. ACM 24(2), 332\u2013337 (1977)","journal-title":"J. ACM"},{"key":"29_CR29","doi-asserted-by":"crossref","unstructured":"Jakobsson, M., Juels, A.: Proofs of work and bread pudding protocols. In: Preneel, B. (ed.) Proceedings of the IFIP Conference on Communications and Multimedia Security, vol. 152, pp. 258\u2013272. Kluwer (1999)","DOI":"10.1007\/978-0-387-35568-9_18"},{"key":"29_CR30","unstructured":"Juels, A., Brainard, J.G.: Client puzzles: a cryptographic countermeasure against connection depletion attacks. In: NDSS 1999. The Internet Society, February 1999"},{"key":"29_CR31","doi-asserted-by":"crossref","unstructured":"Juels, A., Kaliski Jr., B.S.: Pors: proofs of retrievability for large files. In: Ning, P., De Capitani di Vimercati, S., Syverson, P.F. (eds.) ACM CCS 07, pp. 584\u2013597. ACM Press, October 2007","DOI":"10.1145\/1315245.1315317"},{"key":"29_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/978-3-319-10879-7_30","volume-title":"Security and Cryptography for Networks","author":"NP Karvelas","year":"2014","unstructured":"Karvelas, N.P., Kiayias, A.: Efficient proofs of secure erasure. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 520\u2013537. Springer, Heidelberg (2014)"},{"issue":"4","key":"29_CR33","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T Lengauer","year":"1982","unstructured":"Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087\u20131130 (1982)","journal-title":"J. ACM"},{"key":"29_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24638-1_2","volume-title":"Theory of Cryptography","author":"UM Maurer","year":"2004","unstructured":"Maurer, U.M., Renner, R.S., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21\u201339. Springer, Heidelberg (2004)"},{"key":"29_CR35","unstructured":"Merkle, R.C.: Method of providing digital signatures. US Patent 4309569, 5 January 1982"},{"issue":"4","key":"29_CR36","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"key":"29_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-45760-7_11","volume-title":"Topics in Cryptology - CT-RSA 2002","author":"S Micali","year":"2002","unstructured":"Micali, S., Rivest, R.L.: Micropayments revisited. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 149\u2013163. Springer, Heidelberg (2002)"},{"key":"29_CR38","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2009). http:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"29_CR39","unstructured":"Park, S., Pietrzak, K., Alwen, J., Fuchsbauer, G., Gazi, P.: Spacecoin: a cryptocurrency based on proofs of space. Cryptology ePrint Archive, Report 2015\/528 (2015). http:\/\/eprint.iacr.org\/2015\/528"},{"key":"29_CR40","doi-asserted-by":"crossref","unstructured":"Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10(1), 239\u2013251 (1976\u20131977)","DOI":"10.1007\/BF01683275"},{"key":"29_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-15497-3_39","volume-title":"Computer Security \u2013 ESORICS 2010","author":"D Perito","year":"2010","unstructured":"Perito, D., Tsudik, G.: Secure code update for embedded devices via proofs of secure erasure. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 643\u2013662. Springer, Heidelberg (2010)"},{"key":"29_CR42","doi-asserted-by":"crossref","unstructured":"Rivest, R.L., Shamir, A.: Payword and micromint: two simple micropayment schemes. In: CryptoBytes, pp. 69\u201387 (1996)","DOI":"10.1007\/3-540-62494-5_6"},{"key":"29_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11958239_14","volume-title":"Progress in Cryptology - VIETCRYPT 2006","author":"P Rogaway","year":"2006","unstructured":"Rogaway, P.: Formalizing human ignorance. In: Nguy\u00ean, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 211\u2013228. Springer, Heidelberg (2006)"},{"key":"29_CR44","volume-title":"Models of Computation: Exploring the Power of Computing","author":"JE Savage","year":"1997","unstructured":"Savage, J.E.: Models of Computation: Exploring the Power of Computing, 1st edn. Addison-Wesley Longman Publishing Co. Inc., Boston (1997)","edition":"1"},{"key":"29_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"DR Simon","year":"1998","unstructured":"Simon, D.R.: Findings collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"key":"29_CR46","series-title":"Lecture Notes in Computer Science","first-page":"246","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"L Ahn Von","year":"2003","unstructured":"Von Ahn, L., Blum, M., Hopper, N.J., Langford, J.: CAPTCHA: Using hard AI problems for security. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 246\u2013256. Springer, Heidelberg (2003)"},{"key":"29_CR47","doi-asserted-by":"crossref","unstructured":"Waters, B., Juels, A., Halderman, J.A., Felten, E.W.: New client puzzle outsourcing techniques for dos resistance. In: Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, pp. 246\u2013256. ACM, New York (2004)","DOI":"10.1145\/1030083.1030117"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology -- CRYPTO 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48000-7_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T20:40:23Z","timestamp":1748551223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48000-7_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662479995","9783662480007"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48000-7_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"1 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}