Getting started

Constructions

Useful resources

PDP allows a storage provider to prove to its clients that their data is intact and available.

In a proof of retrievability, a client can store a file on the server, while storing (a short) verification string locally. In the audit protocol, the client acts as the verifier and the server proves that it possesses the client’s file. The property that the server “possesses” a file is formalized by the existence of an extractor that retrieves the client’s file from any server that makes a client accept in the audit protocol.

Compact proofs of retrievability by Hovav Shacham and Brent Waters [14] gives public verifiability for PoR in the random oracle model. This allows any party to take the role of the verifier in the audit protocol, not just the client who originally stored the file.

A Proof of Secure Erasure (PoSE) allows a space restricted prover to convince a verifier that they have erased their memory of size N.

In a Proof of Replication, a party would like to prove that they are storing multiple redundant copies of a single file. The PoRep definitions combine a PoS and a Proof of Retrievability. Similarly to the PoS cost-model definition, PoReps don’t (and can’t) guarantee that the prover actually stores redundant copies of the data, but instead make it an ε-Nash equilibrium (so a rational prover does not lose much by doing so). The existing constructions of PoReps depend on depth-robust graphs (DRG) for the PoS and on sequential timing assumptions (the prover must respond to a challenge quickly, and the timing assumptions ensure that the prover cannot recompute its data in that time)

A memory-hard function is a function that requires a large amount of memory to evaluate. One of the main motivations for constructing such functions is to construct proofs-of-work that are “ASIC-resistant” (based on the assumption that the large memory requirement would make such chips prohibitively expensive). The known memory-hard functions are still proofs-of-work; the provers must constantly utilize their CPU in order to produce additional proofs. PoS, on the other hand, allow the prover to be offline and idle while still using space-time (since using space resource only requires that storage be filled with data for a period of time).