Getting started

Constructions

Useful resources

Provable data possession (PDP) allows a storage provider to prove to its clients that their data is intact and available. If a verifier (client) outsources large and incompressible data to the prover, then PDP will achieve the space-hardness goal of PoS. However, this implies communication costs for sending the initial data. On the other hand, the requirement for PoS schemes is to achieve low communication cost. PDP is stronger in another aspect: is allows for arbitrary user data while regular PoS does not necessarily require other than storing random bits.

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.

Similar to PDP, a PoR can be turned into a PoS if the client stores a large and incompressible file.

A Proof of Secure Erasure (PoSE) allows a space restricted prover to convince a verifier that they have erased their memory of some size N. This is useful in settings that require to wipe a remote device.

The idea is related to Proof of Space because of the following observation: Assuming a verifier knows that a prover (a remote device) has exactly N space, then any protocol that forces the prover to use N space can be considered a PoSE.

A memory-hard function (MHF) is a function that requires a lot of memory/space to compute. 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).

Besides being space-hard, a MHF must take short inputs. This is to rule out trivial solutions that only take long and incompressible inputs.

Graph pebbling (also known as pebble games) in the random oracle model is a candidate of MHF.

In a Proof of Replication, a storage provider 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 cannot 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 proof of transient space (PoTS) enables efficient verification of a MHF with sublinear verifier space and time (sublinear in the storage size N).

Seen differently, PoTS is either a PoSE or a MHF with additional efficient verification requirements.

Usually PoTS guarantees that no computationally bounded adversary using less than $γ$N space can convince a verifier with non-negligible probability, where $γ$ can be set close to 1.

PoPS asks that the prover allocates space over time and it is achieved by repeated audits from the verifier.

If the prover is audited only once, PoPS becomes just a PoTS.

If we consider PDP or PoR for arbitrary incompressible random files, those insure that the server to use a lot of persistent space but do not meet the succinctness (short input) requirement since a large amount of data needs to be communicated initially.

Proof of Useful Space (PoS) or what we call simply proof of space combines the PoPS requirements with PDP/PoR functionality, meaning that the prover is asked to use a portion of their disk capacity and to store some client data on it. Since the prover is demonstrating space in the process, it is naturally to consider that this space can be used to store an actual file.