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)