Definitions

Getting started

Introduction

Definitions

Constructions

Useful resources

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)$ → $pp$ : Takes the security parameter λ and outputs the public parameters $pp$ of the scheme
PoS.Init $(pp, D)$ → $(C_R, R)$ : Takes the parameters, the data $D$ and produces the replica $R$ and a commitment to the replica $C_R$
PoS.Challenge $(pp, C_R)$ → $chlg$ : Takes the parameters, the commitment to the replica and outputs a challenge
PoS.Response $(pp, chlg, C_R)$ → $resp$ : Takes the parameters, the challenge $chlg$ issued by a verifier and the commitment to the replica $C_R$ and answers with $resp$
PoS.Verify $(pp, C_R, chlg, resp)$ → {0, 1} : Takes the parameters, the commitment to the replica $C_R$ , the challenge $chlg$ and the reply $resp$ and outputs accept or reject
PoS.Decode $(pp, R)$ → $D$ : Takes the parameters and the replica and outputs back the data.

PoS Protocol

The setup algorithm PoS.Setup is run in a trusted manner and the parameters $pp$ are available to the Prover and the Verifier who run an interactive protocol:

Initialization Phase

Prover runs PoS.Init $(pp, D)$ → $(C_R, R)$ on the data $D$ .

Execution Phase

Both parties have access to a commitment $C_R$ from the initialization phase.

The verifier sends a challenge by running PoS.Challenge and receives a succinct response $resp$ from a prover running PoS.Response $(pp, chlg, C_R)$ .

At the end of this phase, the verifier runs PoS.Verify and 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.

Decoding Algorithm

Proof of Useful Space requires an algorithm that goes from the replica to the initial data, named decoding algorithm. For this, we also require encoding (the initialization stage producing the replica) to have binding properties.

Security Models

Latency model: A PoS is considered secure if for a prover who does not store the full replica, during the execution phase generating a valid response to the challenge will need a running time superior to the duration $t$ of the challenge-response communication.

Cost model: In this model we assume a rational adversary that chooses the less expensive in terms of costs solution, and that should be storing the entire replica over the expected period of time.

There may exist a successful adversarial strategy that does not require the adversary to store the entire replica over time, but this strategy will be more costly than the honest one, where the adversary dedicates storage in order to answer challenges.

Then, we will not ask a rational prover to show exactly which resource was spent in the execution phase, but just to show they spent some expected amount of resources.

This allows the prover to choose arbitrarily a trade-off between storing the entire replica or recomputing parts of it.

The naive way to is for the prover to discard most of the stored data after the initialization and rerun the initialization in the execution phase.

If the prover prefers to use computation over storage, then that is that the cost of storing the data between the phases is greater than the cost of rerunning the initialization.

By setting parameters correctly, we can ensure that rational provers will prefer to store the replica over computation, and make sure this is the best strategy.

← Previous

Introduction

Ideas and Theory

On this page

PoS Scheme
Algorithms
PoS Protocol
Initialization Phase
Execution Phase
Decoding Algorithm
Security Models