Paper 2018/194

Proofs of Catalytic Space

Krzysztof Pietrzak


Proofs of space (PoS) [DFKP15] 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. The first contribution of this paper is a security proof for the PoS from [DFKP15] 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 introduce and construct proofs of catalytic space (PoCS), which are defined like classical PoS, but most of the space required by the prover can at the same time be used to store useful data. Our first construction has almost no overhead (i.e., the useful data is almost as large as the dedicated space), whereas our second construction has a slightly larger overhead, but allows for efficient updates of the data. Our constructions are extensions of the [DFKP15] PoS, and our tight proof for the PoS extends (non-trivially) to the PoCS. As our last contribution we construct a proof of replication (PoR), coming up with such an object has recently been stated as an open problem in the Filecoin paper. Also this construction (and its proof) are extensions of the [DFKP15] PoS.

Available format(s)
Publication info
Preprint. MINOR revision.
Proofs of SpaceProofs of ReplicationPebbling
Contact author(s)
krzpie @ gmail com
2018-02-22: received
Short URL
Creative Commons Attribution


      author = {Krzysztof Pietrzak},
      title = {Proofs of Catalytic Space},
      howpublished = {Cryptology ePrint Archive, Paper 2018/194},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.