Proof of space – New Directions

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)$ = storing a file of size $N'< N$ for d time + computation to regenerate and pass the audit with probability larger that $1-2^{-\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 efficiency: $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

1. Reducing d:
1. This will result in reducing $T_{dec}(N)$, $T_{init}(N)$
2. Improve execution efficiency $T_{init}(N)$/$RC(N',d)$
1. while lowering the cost of $T_{init}(N)$
2. optimal value is when $T_{init}(N)= RC(N’,d)$
3. today’s ratio $T_{init}(N)/R(N’,d)$ = 13.75
4. we want to reduce this ratio
5. 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)$
3. 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