Getting started

Constructions

Useful resources

PoS is useful in settings where a resource-poor client outsources a large amount of data to a server with a large storage capacity. 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.

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.

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 $t$, the time between challenge and response and $d$ the time between two consecutive challenges.

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.

On this page