Getting started
Constructions
Useful resources
Delegated Storage
Storage-as-a-Service solutions provide data storage and retrieval service for users willing to outsource their files. However, after outsourcing, the data owner has no physical control over the data.
Guarantees for the data
Protocols that guarantee the data storage are called Proofs-of-Storage and they come in different flavours.
Proofs-of-Storage schemes such as Provable Data Possession (PDP) and Proof-of-Retrievability (PoR) schemes allow a user (the verifier V) who outsources data D to a server (the prover P) to repeatedly check if the server is still storing D.
The user can verify the integrity of the data outsourced to a server in a very efficient way, more efficiently than downloading the data. The prover generates probabilistic proofs of possession by sampling a random set of blocks and transmits a small constant amount of data in a challenge/response protocol with the user.
Unsatisfactory solutions
These proofs solve partially the problem of untrusted delegated storage of data. However, PDP/PoR protocols certify data integrity and availability only at the time a valid proof is processed. Between two proofs, there is nothing that can be guaranteed about the permanent storage or availability of the outsourced data.
Naive attempt
A way to guarantee continuous data availability is by performing frequent checks over time. However, this requires that users (the verifiers) are online when sending sequential challenges to the storage server and the communication and computation costs for these verifiers increases with the number of queries.
PoS Scheme
Proof of Space (PoS) is a protocol that enables a prover to demonstrate continuous storage of outsourced data in a (publicly) verifiable way.
Algorithms
- PoS.Setup → : Takes the security parameter λ and outputs the prover key and a verification key
- PoS.Prove → : Takes the prover key, the data and some random challenge issued by a verifier V, and a time period and outputs a proof π
- PoS.Verify→ {0, 1} : Takes the verifier key, the challenge , a time period and the proof π and outputs accept or reject.
PoS Protocol
The setup algorithm is run in a trusted manner and the parameters are available to the Prover and the Verifier who run an interactive protocol:
Initialization Phase
Both parties receive as input an string Both the prover and the verifier output state strings , respectively.
Execution Phase
Both parties receive the and their corresponding state or from the initialization phase.
The verifier sends a challenge and receives a succinct response after a time specified by the verifier. At the end of this phase, the verifier either accepts or rejects.
The execution phase can be repeated multiple times without rerunning the initialization phase. This is critical, since the initialization phase is expensive in computation, while the execution phase is energy-efficient.
Security in the Cost Model
We consider two different resources for the prover:
- computation: a CPU unit required when executing some tasks
- storage (over time): a space unit that is “reserved” for a unit of time
Storage as well as computation are directly convertible to cost.
Real-worlds costs
In the following, we will consider rational adversaries, that chose their strategy based on cost consumption, in order to minimize their cost.
To measure the total cost incurred by a prover, regardless of the type of resource we introduce a ratio between computation units and storage units (in terms of real-worlds prices):
= cost ratio between a computation unit and a storage unit (this value may change over time)