Getting started

Introduction

Definitions

Ideas and Theory

Use Case

Constructions

Filecoin PoS

Related Protocols

Open Problems

Useful resources

Documentation

Outreach Talks

References

Proof of Space and Replication

1. Proofs of Space with Maximal Hardness Leonid Reyzin URL: https://eprint.iacr.org/2023/1530
2. stoRNA: Stateless Transparent Proofs of Storage-time. Reyhaneh Rabaninejad, Behzad Abdolmaleki, Giulio Malavolta, Antonis Michalas, Amir Nabizadeh URL: https://eprint.iacr.org/2023/515
3. Proof of storage-time: Efficiently checking continuous data availability. Ateniese, G., Chen, L., Etemad, M., Tang, Q. In: NDSS (2020) URL: https://eprint.iacr.org/2020/840
4. Proofs of Catalytic Space Krzysztof Pietrzak URL: https://eprint.iacr.org/2018/194.pdf
5. Proofs of Replicated Storage Without Timing Assumptions. Ivan Damgård, Chaya Ganesh, Claudio Orlandi In: Advances in Cryptology – CRYPTO 2019 URL: https://eprint.iacr.org/2018/654.pdf
6. Spacemint: A cryptocurrency based on proofs of space. S. Park, A. Kwon, G. Fuchbauer, P. Gazi, J. Alwen, and K. Pietrzak In Proceedings of the 22nd International Conference on Financial Cryptography and Data Security (FC). Springer, 2018. URL: http://fc18.ifca.ai/preproceedings/78.pdf.
7. Poreps: Proofs of space on useful data. B. Fisch. IACR Cryptology ePrint Archive, 2018:678, 2018. URL: https://eprint.iacr.org/2018/678.
8. Tight proofs of space and replication. B. Fisch. IACR Cryptology ePrint Archive, Report 2018/702, 2018. URL: https://eprint.iacr.org/2018/702.
9. Filecoin: A decentralized storage network. Protocol Labs 2017 URL: https://filecoin.io/filecoin.pdf
10. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. H. Abusalah, J. Alwen, B. Cohen, D. Khilko, K. Pietrzak, and L. Reyzin In Advances in Cryptology ASIACRYPT 2017 Proceedings, 2017. URL: https://eprint.iacr.org/2017/893.pdf
11. Proof of Space from Stacked Expanders. Ling Ren, Srinivas Devadas In Advances in Cryptology TCC 2016 URL: https://eprint.iacr.org/2016/333.pdf
12. On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model. J. Alwen, B. Chen, C. Kamath, V. Kolmogorov, K. Pietrzak, S. Tessaro In Advances in Cryptology EUROCRYPT 2016 URL: https://eprint.iacr.org/2016/100.pdf
13. Proofs of space. S. Dziembowski, S. Faust, V. Kolmogorov, and K. Pietrzak. In Advances in Cryptology CRYPTO 2015 Proceedings, 2015. URL: https://www.iacr.org/archive/crypto2015/92160192/92160192.pdf
14. Proofs of Space: When Space is of the Essence. Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi. In Security and Cryptography for Networks SCN 2014. URL: https://eprint.iacr.org/2013/805
15. Provable data possession at untrusted stores. G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, D. Song. In: Proceedings of the 14th ACM CCS 2007 URL: https://eprint.iacr.org/2007/202.pdf

Proof of Retrievability

1. Mirror: Enabling proofs of data replication and retrievability in the cloud. F. Armknecht, L. Barman, J-M. Bohli, and G. O. Karame In USENIX Security Symposium, pages 1051–1068, 2016 URL: https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_armknecht.pdf
2. Dynamic proofs of retrievability via oblivious RAM. David Cash, Alptekin Küpçü, and Daniel Wichs Journal of Cryptology, pages 1–26, 2015. URL: https://eprint.iacr.org/2012/550.pdf
3. Proofs of retrievability via hardness amplification. Yevgeniy Dodis, Salil P. Vadhan, and Daniel Wichs In TCC 2009, volume 5444 of LNCS, March 2009. URL: https://eprint.iacr.org/2009/041.pdf
4. Compact proofs of retrievability. Hovav Shacham and Brent Waters In ASIACRYPT 2008, volume 5350 of LNCS. Springer, 2008. URL: https://eprint.iacr.org/2008/073.pdf
5. Pors: proofs of retrievability for large files. Ari Juels and Burton S. Kaliski Jr In ACM CCS 2007, pages 584–597. ACM Press, October 2007 URL: https://eprint.iacr.org/2007/243
6. Provable data possession at untrusted stores. G. Ateniese, R. C. Burns, R. Curtmola, J. Herring, L. Kissner, Z. N. J. Peterson, D. X. Song In ACM CCS 2007 URL: https://eprint.iacr.org/2007/202.pdf

Proof of Data Possession

1. Scalable and efficient provable data possession. G. Ateniese, R. Di Pietro, L.V. Mancini, and G. Tsudik In SecureComm ACM 2008, pp. 1–10. URL: https://eprint.iacr.org/2008/114.pdf
2. Provable data possession at untrusted stores. G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, D. Song. In: Proceedings of the 14th ACM CCS (2007) URL: https://eprint.iacr.org/2007/202.pdf

Proof of Secure Erasure

1. Efficient Proofs of Secure Erasure. Nikolaos P. Karvelas, Aggelos Kiayias In SCN 2014
2. One-Time Computable Self-erasing Functions. Stefan Dziembowski, Tomasz Kazana, Daniel Wichs: In TCC 2011
3. Secure code update for embedded devices via proofs of secure erasure. Daniele Perito and Gene Tsudik. In ESORICS 2010, volume 6345 of LNCS, pages 643–662. Springer, 2010 URL: https://eprint.iacr.org/2010/217.pdf

Memory-Hard Functions

1. Efficiently Computing Data-Independent Memory-Hard Functions. Joël Alwen, Jeremiah Blocki In CRYPTO 2016
2. High Parallel Complexity Graphs and Memory-Hard Functions. Joël Alwen, Vladimir Serbinenko In STOC 2015
3. Tradeoff Cryptanalysis of Memory-Hard Functions. Alex Biryukov, Dmitry Khovratovich In ASIACRYPT 2015
4. Moderately hard, memory-bound functions. Martin Abadi, Michael Burrows, Mark S. Manasse, Ted Wobber In ACM Trans. Internet Techn (2005)

Time-Space Trade-offs

1. Asymptotically tight bounds on time-space trade-offs in a pebble game. Thomas Lengauer, Robert Endre Tarjan In J. ACM 29 (1982)
2. Time-Space Trade-Offs in a Pebble Game. Wolfgang J. Paul, Robert Endre Tarjan In Acta Informatica 10 (1978)
3. On Time versus Space and Related Problems. John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant In FOCS 1975
4. An Observation on Time-Storage Trade Off. Stephen A. Cook In STOC 1973

Depth Robust Graphs

1. Lower Bounds and Trade-offs in Proof Complexity Susanna de Rezende, PhD thesis URL: manuscript
2. Depth-robust graphs and their cumulative memory complexity J. Alwen, J. Blocki, and K.Pietrzak, In EUROCRYPT 2017 URL: https://eprint.iacr.org/2016/875.pdf
3. On depth-reduction and grates G. Schnitger, In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983) URL: https://ieeexplore.ieee.org/document/4568095
4. Asymptotically tight bounds on time-space trade-offs in a pebble game Thomas Lengauer and Robert E. Tarjan, In STOC 1979 URL: https://dl.acm.org/doi/pdf/10.1145/322344.322354
5. Graph-theoretic arguments in low-level complexity Leslie G. Valiant In MFCS 1977 URL: PDF

• References
• Proof of Space and Replication
• Proof of Retrievability
• Proof of Data Possession
• Proof of Secure Erasure
• Memory-Hard Functions
• Time-Space Trade-offs
• Depth Robust Graphs