Paper 2023/515

stoRNA: Stateless Transparent Proofs of Storage-time

Reyhaneh Rabaninejad, Tampere University
Behzad Abdolmaleki, University of Sheffield
Giulio Malavolta, Max Planck Institute for Security and Privacy
Antonis Michalas, Tampere University, RISE Research Institutes of Sweden
Amir Nabizadeh

Proof of Storage-time (PoSt) is a cryptographic primitive that enables a server to demonstrate non-interactive continuous avail- ability of outsourced data in a publicly verifiable way. This notion was first introduced by Filecoin to secure their Blockchain-based decentral- ized storage marketplace, using expensive SNARKs to compact proofs. Recent work [2] employs the notion of trapdoor delay function to address the problem of compact PoSt without SNARKs. This approach however entails statefulness and non-transparency, while it requires an expensive pre-processing phase by the client. All of the above renders their solution impractical for decentralized storage marketplaces, leaving the stateless trapdoor-free PoSt with reduced setup costs as an open problem. In this work, we present stateless and transparent PoSt constructions using probabilistic sampling and a new Merkle variant commitment. In the process of enabling adjustable prover difficulty, we then propose a multi- prover construction to diminish the CPU work each prover is required to do. Both schemes feature a fast setup phase and logarithmic verification time and bandwidth with the end-to-end setup, prove, and verification costs lower than the existing solutions

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. esorics2023
Contact author(s)
reyhaneh rabbaninejad @ tuni fi
behzad abdolmaleki @ sheffield ac uk
giulio malavolta @ mpi-sp org
antonios michalas @ tuni fi
amirdal @ gmail com
2023-04-10: approved
2023-04-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Reyhaneh Rabaninejad and Behzad Abdolmaleki and Giulio Malavolta and Antonis Michalas and Amir Nabizadeh},
      title = {stoRNA: Stateless Transparent Proofs of Storage-time},
      howpublished = {Cryptology ePrint Archive, Paper 2023/515},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.