Cryptology ePrint Archive: Report 2016/035

Proofs of Space-Time and Rational Proofs of Storage

Tal Moran and Ilan Orlov

Abstract: We introduce a new cryptographic primitive: Proofs of Space-Time (PoSTs) and construct a practical protocol for implementing these proofs. A PoST allows a prover to convince a verifier that she spent a ``spacetime'' resource (storing data---space---over a period of time). Formally, we define the PoST resource as a linear tradeoff between CPU work and space-time (under reasonable cost assumptions, a rational user will prefer to use the lower-cost space-time resource over CPU work).

Compared to a proof-of-work, a PoST requires less energy use, as the ``difficulty'' can be increased by extending the time period over which data is stored without increasing computation costs. Our definition is very similar to ``Proofs of Space'' [ePrint 2013/796, 2013/805] but, unlike the previous definitions, takes into account amortization attacks and storage duration. Moreover, our protocol uses a very different (and simpler) technique, making use of the fact that we explicitly allow a space-time tradeoff.

Category / Keywords: cryptographic protocols / proofs of work, proofs of space, bitcoin, crypto-currency

Date: received 13 Jan 2016

Contact author: talm at idc ac il

Available format(s): PDF | BibTeX Citation

Version: 20160114:152835 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]