## CryptoDB

### Paper: Tight Proofs of Space and Replication

Authors: Ben Fisch DOI: 10.1007/978-3-030-17656-3_12 (login may be required) Search ePrint Search Google We construct a concretely practical proof-of-space (PoS) with arbitrarily tight security based on stacked depth robust graphs and constant-degree expander graphs. A proof-of-space (PoS) is an interactive proof system where a prover demonstrates that it is persistently using space to store information. A PoS is arbitrarily tight if the honest prover uses exactly N space and for any $\epsilon > 0$ϵ>0 the construction can be tuned such that no adversary can pass verification using less than $(1-\epsilon ) N$(1-ϵ)N space. Most notably, the degree of the graphs in our construction are independent of $\epsilon$ϵ, and the number of layers is only $O(\log (1/\epsilon ))$O(log(1/ϵ)). The proof size is $O(d/\epsilon )$O(d/ϵ). The degree d depends on the depth robust graphs, which are only required to maintain $\varOmega (N)$Ω(N) depth in subgraphs on 80% of the nodes. Our tight PoS is also secure against parallel attacks.Tight proofs of space are necessary for proof-of-replication (PoRep), which is a publicly verifiable proof that the prover is dedicating unique resources to storing one or more retrievable replicas of a specified file. Our main PoS construction can be used as a PoRep, but data extraction is as inefficient as replica generation. We present a second variant of our construction called ZigZag PoRep that has fast/parallelizable data extraction compared to replica generation and maintains the same space tightness while only increasing the number of levels by roughly a factor two.
##### BibTeX
@article{eurocrypt-2019-29364,
title={Tight Proofs of Space and Replication},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11477},
pages={324-348},
doi={10.1007/978-3-030-17656-3_12},
author={Ben Fisch},
year=2019
}