Welcome to the resource topic for 2018/194
Title:
Proofs of Catalytic Space
Authors: Krzysztof Pietrzak
Abstract: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.
ePrint: https://eprint.iacr.org/2018/194
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .