Cryptology ePrint Archive: Report 2016/035

Rational Proofs of Space-Time

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 ``space-time'' resource (storing data---space---over a period of time). Formally, we define the PoST resource as a trade-off 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, and doesn't require any non-standard assumptions (beyond random oracles).

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

Date: received 13 Jan 2016, last revised 24 May 2017

Contact author: talm at idc ac il

Available format(s): PDF | BibTeX Citation

Note: Updated version with improved results.

Version: 20170524:214826 (All versions of this report)

Short URL: ia.cr/2016/035

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]