What is Proof of Space?
Proof of Space (PoS) is a protocol that allows a prover to efficiently convince a verifier that some data is continuously stored on some minimum amount of space.
PoS is useful in settings where a resource-poor client outsources a large amount of data to a server with a large storage capacity.
Storage-as-a-Service solutions provide such data storage and retrieval service for users willing to outsource their files. However, after outsourcing, the data owner (client) has no physical control over the data.
The main challenge is for a client, who does not keep a copy of the outsource data, to efficiently verify that the server indeed stores all of the client’s data over time.
A PoS is a two-phase protocol consisting in an initialisation phase done once, followed by an execution phase that can be repeated over time.
Part 1: Initialisation
This is a setup phase where the prover “translates” the data D into an encoded form, called replica R.
Both the original data and the replica have same size N.
The replica is stored by the prover, while two commitments to R and to D are made publicly available.
Part 2: Execution
This is an audit phase where the verifier checks that the replica R is continuously stored.
The prover gets challenged and they answer with a proof that can be valid/invalid.
This phase can be repeated many times.
We parametrize the audits in terms of , the time between challenge and response and the time between two consecutive challenges.