@Anonymous, June 2023
<aside> ➡️ What to expect from this document?
This is a recap of constructions we have considered in the past for proving storage in Filecoin. They are divided in two sections: (1) The first section lists replacements for SDR (ie, replacements for the Proof of Useful Space itself and therefore for the method used to add storage). (2) The second section lists alternative design to winningPoSt and windowPoSt (ie, how and when the storage auditing for the chosen PoUS is conducted).
</aside>
🗣️ Please, be aware that this doc does not describes neither analyses each construction in full details. Links to the relevant documents are provided for this! [Some of these docs may not be public yet, sorry! Ping me if you need access.]
| Security Model | Possible paired PoSt (auditing schedule) | Security analysis completed? | “Fast” (faster than SDR) retrieval ? | |
|---|---|---|---|---|
| ZigZag | latency | |||
| (based on SHA256 latency) | winningPoSt | no (sealstack to solve, bug in the pebbling argument to fix) | yes (asymmetric) | |
| DRG PoRep | latency | |||
| (based on SHA256 latency) | winningPoSt | no (sealstack to solve) | yes (asymmetric) | |
| Small SDR | cost and latency | |||
| (based on SHA256 evaluation) | windowPoSt/ chainPost | yes | yes (symmetric) | |
| NSE | cost | |||
| (based on SHA256 evaluation) | windowPoSt | |||
| (or anything from the cost model category) | yes | yes | ||
| Wide PoRep | latency | |||
| (based on SHA256 latency) | ||||
| winningPost | ||||
| yes | yes-ish | |||
| (no explicit params) |
Here we provide a list of possible replacements for the Stacked-DRG proof of useful space (aka “SDR”). For each construction, we provide (1) a very high level idea of the construction, (2) some comments about possible pros/cons and similarities respect to SDR (eg, security model) and (3) links to relevant documents with more details.
We call a PoS “asymmetric” when the decoding algorithm (from replica back to data) is faster than the encoding algorithm (ie, the algorithm run by the prover/SP to go from data to replica).
Note any asymmetric construction used in the latency model (eg, in combo with winningPoSt) is subject to the following problem:
SealStack Attack: Assume we have a PoRep/PoUS/ with fast unsealing/decoding. The SP runs the sealing process and creates replica R (from data = 0, or any data); The SP runs the sealing process again with data = R and creates replica R'; The SP deletes R and keeps only R'. Every time a post (eg, winning PoSt) is required for R, the SP runs the unsealing algorithm on R' and gets R. If the unsealing algorithm is faster than 30s (block time/response time), then winningPoSt is broken. In other words we must have RetrievalLatency > RegenLatency > ResponseTime (Note: if unsealing algorithm is fast but still as expensive as sealing, then WindowPoSt is still secure and we can use the asymmetric construction in the cost model )
Possible solutions:
- (sub optimal) Use the construction in the cost model with windowPoSt only;
- Maybe use the construction for FIL+ deals (data can not be chosen by the prover);
Construction: It is similar to Stacked-DRGs (SDR) PoUS and presented in the same paper. Respect to SDR, it achieves fast retrieval because the decoding procedure can per run in parallel (ie, all nodes are decoded in parallel). In the paper, it was designed to work in the latency model (so it can work with any PoSt from the next section from the “latency model” category). The latency bound uses SHA256 running time on ASICs
It should be possible to use it in the cost model with similar analysis as the one we did for SDR.
Comments: