Paper 2018/654

Proofs of Replicated Storage Without Timing Assumptions

Ivan Damgård, Chaya Ganesh, and Claudio Orlandi

Abstract

In this paper we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin. In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file $m$ on $n$ different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the server is indeed reserving the space necessary to store $n$ copies of the file, the user will not accept the proof. While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions i.e., the user must reject the proof if the prover does not reply within a certain time-bound. In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.

Note: comparison with related work, clarified instantiation of oracle

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
replicated storageproof of replicationencodings
Contact author(s)
ivan @ cs au dk
chaya ganesh @ gmail com
orlandi @ cs au dk
History
2019-06-29: last of 3 revisions
2018-07-06: received
See all versions
Short URL
https://ia.cr/2018/654
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/654,
      author = {Ivan Damgård and Chaya Ganesh and Claudio Orlandi},
      title = {Proofs of Replicated Storage Without Timing Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/654},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/654}},
      url = {https://eprint.iacr.org/2018/654}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.