Advertisement
Published in:
2019 | OriginalPaper | Chapter
Tight Proofs of Space and Replication
Author : Ben Fisch
Published in: Advances in Cryptology – EUROCRYPT 2019
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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\) the construction can be tuned such that no adversary can pass verification using less than \((1-\epsilon ) 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 ))\). The proof size is \(O(d/\epsilon )\). The degree d depends on the depth robust graphs, which are only required to maintain \(\varOmega (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.