Authors

Luca IreneMatteo Campanelli

Creator

Irene

Created

Feb 13, 2023 1:18 PM

### 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 $D$. More precisely in a PoS protocol we have two main sub-protocols:

*Initialization*(ie, setup phase): on public input $N(size)$ and $D (data)$, a*replica*$R$ of size $N$ is created, which is a an encoded version of the data. The replica is stored by the prover, while a commitment to $R$ and $D$ is publicly available*.- We call
**$T_{init}(N)$**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: $t$, $d$
- $t$ = time between challenge and response (on-chain communication)
- $d$ = 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**$SC(N,d)$**= storing a file of size N for d time; - (
**regeneration cost**) The cost of the malicious is**$RC(N',d, \lambda)$** - We can set lambda = 80 and ignore this param in the following discussion;
- Limit: $RC(N',d) ≤ T_{init}(N)$ (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:***$RC(N',d) >> SC(N,d)$****for any****$N'< N$**- Note: we may weaken this and consider$N' < (1-\epsilon )*N$ ($\epsilon$ is called spacegap and today in Filecoin $\epsilon = 0.2$)
- Let $RC = min_{N'} ({RC(N’,d)})$ (the min represents the lower bound of any strategies for the malicious prover)
- We call
*security margin*the ration**$sm = RC / SC(N,d) >> 1$** - 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**$T_{dec}(N)$****;**- Decoding
**:**$T_{dec} / T_{int}$ - Note that $T_{dec} / T_{int} = 1$ is easy (see the “PoS + XOR data” construction), while having $T_{dec} / T_{int} < 1$ opens the door to the “SealStack Attack” (ie, use the replica as data for the next proof of useful space initialisation);
- Limit: $T_{dec} ≥ min(RC(N’,d’))$ (same as before)
**(new!!!**)*Execution Efficiency EE:*- $EE = T_{int} / RC$
- Limit: since $RC ≤ T_{int}$, $EE ≥ 1$ (the lower the better! Why? see later, direction 2)
- Today we have $EE = 13.75$
- 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 $T_{dec}(N)$,
**$T_{init}(N)$** - Improve execution efficiency $T_{init}(N)$/$RC(N',d)$
- while lowering the cost of $T_{init}(N)$
- optimal value is when $T_{init}(N)= RC(N’,d)$
- today’s ratio $T_{init}(N)/R(N’,d)$ = 13.75
- we want to reduce this ratio
- The recomputing time for the attacker is dependent on the amount of data deleted, $R(N’,d)$. What fraction of data do we consider to compute $RC(N’,d)$
- 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