Document Open Access Logo

Proofs of Catalytic Space

Author Krzysztof Pietrzak

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.59.pdf
  • Filesize: 0.78 MB
  • 25 pages

Document Identifiers

Author Details

Krzysztof Pietrzak
  • Institute of Science and Technology Austria, Austria

Funding

  • Pietrzak, Krzysztof: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 682815/TOCNeT).

Cite AsGet BibTex

Krzysztof Pietrzak. Proofs of Catalytic Space. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 59:1-59:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.59

Abstract

Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Proofs of Space
  • Proofs of Replication
  • Blockchains

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Chia Network. https://chia.network/, 2017.
  2. Burstcoin. URL: http://burstcoin.info.
  3. Hamza Abusalah, Joël Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, and Leonid Reyzin. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 357-379. Springer, Heidelberg, December 2017. Google Scholar
  4. Joël Alwen, Jeremiah Blocki, and Ben Harsha. Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 17, pages 1001-1017. ACM Press, October / November 2017. Google Scholar
  5. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Depth-Robust Graphs and Their Cumulative Memory Complexity. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 3-32. Springer, Heidelberg, April / May 2017. Google Scholar
  6. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained Space Complexity. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 99-130. Springer, Heidelberg, April / May 2018. URL: http://dx.doi.org/10.1007/978-3-319-78375-8_4.
  7. Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro. Scrypt Is Maximally Memory-Hard. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 33-62. Springer, Heidelberg, April / May 2017. Google Scholar
  8. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of Useful Work. IACR Cryptology ePrint Archive, 2017:203, 2017. Google Scholar
  9. Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In David B. Shmoys, editor, 46th ACM STOC, pages 857-866. ACM Press, May / June 2014. Google Scholar
  10. Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman. Catalytic Space: Non-determinism and Hierarchy. In STACS, volume 47 of LIPIcs, pages 24:1-24:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  11. Miles Carlsten, Harry A. Kalodner, S. Matthew Weinberg, and Arvind Narayanan. On the Instability of Bitcoin Without the Block Reward. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16, pages 154-167. ACM Press, October 2016. Google Scholar
  12. Phil Daian, Rafael Pass, and Elaine Shi. Snow White: Provably Secure Proofs of Stake. Cryptology ePrint Archive, Report 2016/919, 2016. URL: http://eprint.iacr.org/2016/919.
  13. Anindya De, Luca Trevisan, and Madhur Tulsiani. Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 649-665. Springer, Heidelberg, August 2010. Google Scholar
  14. Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part II, volume 10211 of LNCS, pages 473-495. Springer, Heidelberg, April / May 2017. Google Scholar
  15. Cynthia Dwork, Moni Naor, and Hoeteck Wee. Pebbling and Proofs of Work. In Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 37-54. Springer, Heidelberg, August 2005. Google Scholar
  16. Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of Space. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 585-605. Springer, Heidelberg, August 2015. URL: http://dx.doi.org/10.1007/978-3-662-48000-7_29.
  17. Paul Erdoes, Ronald L. Graham, and Endre Szemeredi. On Sparse Graphs with Dense Long Paths. Technical report, Stanford University, Stanford, CA, USA, 1975. Google Scholar
  18. Ben Fisch. PoReps: Proofs of Space on Useful Data. Cryptology ePrint Archive, Report 2018/678, 2018. URL: https://eprint.iacr.org/2018/678.
  19. Ben Fisch. Tight Proofs of Space and Replication. Cryptology ePrint Archive, Report 2018/702, 2018. URL: https://eprint.iacr.org/2018/702.
  20. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 357-388. Springer, Heidelberg, August 2017. Google Scholar
  21. Eike Kiltz, Krzysztof Pietrzak, and Mario Szegedy. Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 571-588. Springer, Heidelberg, August 2013. URL: http://dx.doi.org/10.1007/978-3-642-40041-4_31.
  22. Sunny King and Scott Nadal. Ppcoin: Peer-to-peer crypto-currency with proof-of-stake. Google Scholar
  23. Protocol Labs. Filecoin: A Decentralized Storage Network. https://filecoin.io/filecoin.pdf, 2017. Google Scholar
  24. Daniel Malinowski and Karol Zebrowski. Disproving the Conjectures from "On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model". In ICITS, volume 10681 of Lecture Notes in Computer Science, pages 26-38. Springer, 2017. Google Scholar
  25. Silvio Micali. ALGORAND: the efficient and democratic ledger. CoRR, abs/1607.01341, 2016. Google Scholar
  26. Andrew Miller, Ari Juels, Elaine Shi, Bryan Parno, and Jonathan Katz. Permacoin: Repurposing Bitcoin Work for Data Preservation. In 2014 IEEE Symposium on Security and Privacy, pages 475-490. IEEE Computer Society Press, May 2014. URL: http://dx.doi.org/10.1109/SP.2014.37.
  27. Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joël Alwen, Georg Fuchsbauer, and Peter Gaži. SpaceMint: A Cryptocurrency Based on Proofs of Space. Cryptology ePrint Archive, Report 2015/528, 2015. URL: https://eprint.iacr.org/2015/528.
  28. Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical systems theory, 10(1):239-251, 1976-1977. Google Scholar
  29. Krzysztof Pietrzak. Proofs of Catalytic Space. Cryptology ePrint Archive, Report 2018/194, 2018. , full version of this paper. URL: https://eprint.iacr.org/2018/194.
  30. Ling Ren and Srinivas Devadas. Proof of Space from Stacked Expanders. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part I, volume 9985 of LNCS, pages 262-285. Springer, Heidelberg, October /Ñovember 2016. URL: http://dx.doi.org/10.1007/978-3-662-53641-4_11.
  31. The NXT Community. Nxt Whitepaper. https://bravenewcoin.com/assets/Whitepapers/NxtWhitepaper-v122-rev4.pdf, July 2014.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact