Definitions

Definitions

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

PoS Steps

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

Initialization Phase

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

Execution Phase

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

The verifier sends a challenge by running PoS.Challenge and receives a succinct response respresp from a prover running PoS.Response(pp,chlg,CR)(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

image

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 tt of the challenge-response communication.

image

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

CryptoNet is a Protocol Labs initiative.