A Proof of (Useful) Space is a protocol that allows a prover to convince a verifier that he has a minimum specified amount of space (ie, used storage) committed to store some data . More precisely in a PoS protocol we have two main sub-protocols:
- Initialization (ie, setup phase): on public input and , a replica of size is created, which is a an encoded version of the data. The replica is stored by the prover, while a commitment to and is publicly available*.
- We call the cost of running the initialization (computation)
- Execution (ie, audit phase): the prover gets challenged and he answer with a proof that can be valid/invalid. Valid means that any verifier is convinced that the prover stores the replica. This phase can be repeated many times.
- We parametrize the audits with two parameters: ,
- = time between challenge and response (on-chain communication)
- = time between two consecutive challenges
We call honest prover one that store the entire replica; while for the analysis we consider a malicious prover trades storage for computation and regenerate on demand to pass the audit phases. In each window of time between 2 audits,
- (honest storage cost) The cost for honest is = storing a file of size N for d time;
- (regeneration cost) The cost of the malicious is = storing a file of size for d time + computation to regenerate and pass the audit with probability larger that .
- We can set lambda = 80 and ignore this param in the following discussion;
- Limit: (if this is not the case, then an adversary is better off re-running initialization rather than regenerating);
We consider a PoS secure when
- Security tradeoff: for any
- Note: we may weaken this and consider ( is called spacegap and today in Filecoin )
- Let (the min represents the lower bound of any strategies for the malicious prover)
- We call security margin the ration
- Ideally the margin is ~10
Other considerations (efficiency):
- Decoding: there is an algorithm to get the data D from the replica R and its cost is ;
- Decoding efficiency:
- Note that is easy (see the “PoS + XOR data” construction), while having opens the door to the “SealStack Attack” (ie, use the replica as data for the next proof of useful space initialisation);
- Limit: (same as before)
- (new!!!) Execution Efficiency EE:
- Limit: since , (the lower the better! Why? see later, direction 2)
- Today we have
- Question by Matteo: Is EE a function of rho and N?
*Having commD and commR publicly available allows for public verifiability.
Goal of future constructions is to reduce T_int, T_dec.
How? We know at least 3 ways: … TODO
- Reducing d:
- This will result in reducing ,
- Improve execution efficiency /
- while lowering the cost of
- optimal value is when
- today’s ratio = 13.75
- we want to reduce this ratio
- The recomputing time for the attacker is dependent on the amount of data deleted, . What fraction of data do we consider to compute
- Same approach as 1, but instead we make the multiple execution steps into a single on-chain interaction (say with VDF or commitments or similar)
- Why approaching this? since it removes/relaxes Reason 1