Proof of Useful Space
A Proof of Space (PoS, see for example: eprint 2013/796) is a protocol that allows a prover to convince a verifier that he has a minimum specified amount of space (ie, used storage). More precisely in a PoS protocol we have two main sub-protocols:
- Initialization (ie, setup phase): on public input N, an advice (eg, vector of random data) of size N is created. The advice is stored by the prover, while the verifier does not know the advice (in some protocols, the verifier may know a commitment to the advice).
- Execution (ie, audit phase): the verifier and the prover run a protocol and the verifier outputs reject/accept. Accept means that the verifier is convinced that the prover stores the advice. This phase can be repeated many times.
A PoS is sound if a verifier interacting with a malicious prover who stores a fraction of the advice that has size N’ < N, and runs in at most T steps during the execution phase (regenerates the missing part to answer queries), outputs accept with small probability (ie, soundness error).
The value (N-N’)/N is called the spacegap.
When instantiating a PoS in a real-word protocol, we need to specify what “the malicious prover runs in at most T step” means. Two ways of doing this are:
- Latency model: the verifier accepts only proofs that are produced in less than x seconds after the execution protocol starts because we estimate that T steps correspond to at least to x seconds. In other words, the proved is force to use at least N’ storage;
- Cost model: the prover is allowed to choose among running in T’ > T steps (and using < N’ storage) or using at least N’ storage, however the first strategy always costs more than the second one.
Asymmetric PoRep
In an asymmetrical PoRep there exist a Decoding algorithm that runs faster than the encoding.
In current PoRep the Decoding algorithm is running as slow as the encoding one, so the aim is to improve Decoding in practical protocols.
Nevertheless, this asymmetry may lead to a possible attack from a malicious Prover.
SealStack Attack Illustrated
Every time a Winning PoSt is required for R, the SP runs the unsealing algorithm on R' and gets R. If the unsealing algorithm is faster than Response time, then Adversary is successful in WinningPoSt DecodingLatency > RegenLatency > ResponseTime
(Note: Attack in Latency Model. If unsealing is fast but still as cost expensive as sealing, then WindowPoSt is still secure in the cost model.)
Possible Solutions
1. Resealing each time we perform Execution phase (WinningPoSt)
- Dynamic PoRep: Re-randomizable Replicas - not sure if it mitigates the attack completely
- Changing the underlying data in PoRep costs