Simple 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 an extremely simple, 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 much 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). Unlike previous constructions, our protocol allows incremental difficulty adjustment, which can gracefully handle increases in the price of storage compared to CPU work. In addition, we show how, in a cryptocurrency context, the parameters of the scheme can be adjusted using a market-based mechanism, similar in spirit to the difficulty adjustment for PoW protocols.

Note: Updated version with simplified protocol and improved results.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
proofs of workproofs of spacebitcoincrypto-currency
Contact author(s)
talm @ idc ac il
History
2019-02-28: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/035

CC BY

BibTeX

@misc{cryptoeprint:2016/035,
author = {Tal Moran and Ilan Orlov},
title = {Simple Proofs of Space-Time and Rational Proofs of Storage},
howpublished = {Cryptology ePrint Archive, Paper 2016/035},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/035}},
url = {https://eprint.iacr.org/2016/035}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.