### Definitions

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 - 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
**:** - 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.

### Directions

**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