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 $(λ, D)$ → $pk , vk$ : Takes the security parameter λ and outputs the prover key $pk$ and a verification key $vk$
PoS.Prove $(pk, D, c, d)$ → $π$ : Takes the prover key, the data $D$ and some random challenge $c$ issued by a verifier V, and a time period $d$ and outputs a proof π
PoS.Verify $(vk, c, d, π)$ → {0, 1} : Takes the verifier key, the challenge $c$ , a time period $d$ 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 $id$ string $id ∈ \{0, 1\}$ Both the prover and the verifier output state strings $σ_p, σ_v$ , respectively.

Execution Phase

Both parties receive the $id$ and their corresponding state $σ_p$ or $σ_v$ from the initialization phase.

The verifier sends a challenge and receives a succinct response after a time $t$ 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):

$\alpha$ = cost ratio between a computation unit and a storage unit (this value may change over time)

Properties/ Considerations

💡

Coming soon..

On this page

Delegated Storage
Guarantees for the data
Unsatisfactory solutions
Naive attempt
PoS Scheme
Algorithms
PoS Protocol
Initialization Phase
Execution Phase
Security in the Cost Model
Real-worlds costs
Properties/ Considerations