---
_id: '2274'
abstract:
- lang: eng
  text: "Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as
    protection to a shared resource. The basic idea is to ask the service requestor
    to dedicate some non-trivial amount of computational work to every request. The
    original applications included prevention of spam and protection against denial
    of service attacks. More recently, PoWs have been used to prevent double spending
    in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an
    alternative concept for PoWs -- so-called proofs of space (PoS), where a service
    requestor must dedicate a significant amount of disk space as opposed to computation.
    We construct secure PoS schemes in the random oracle model, using graphs with
    high "pebbling complexity" and Merkle hash-trees. "
author:
- first_name: Stefan
  full_name: Dziembowski, Stefan
  last_name: Dziembowski
- first_name: Sebastian
  full_name: Faust, Sebastian
  last_name: Faust
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. <i>Proofs of Space</i>.
    IST Austria; 2013.
  apa: Dziembowski, S., Faust, S., Kolmogorov, V., &#38; Pietrzak, K. Z. (2013). <i>Proofs
    of Space</i>. IST Austria.
  chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
    Z Pietrzak. <i>Proofs of Space</i>. IST Austria, 2013.
  ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, <i>Proofs of
    Space</i>. IST Austria, 2013.
  ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space,
    IST Austria,p.
  mla: Dziembowski, Stefan, et al. <i>Proofs of Space</i>. IST Austria, 2013.
  short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space,
    IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-11-28T00:00:00Z
date_updated: 2025-09-23T09:55:25Z
day: '28'
ddc:
- '530'
department:
- _id: VlKo
- _id: KrPi
file:
- access_level: open_access
  checksum: 37b61637b62fc079d9141c59d9f1a94f
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:16:11Z
  date_updated: 2020-07-14T12:45:36Z
  file_id: '5197'
  file_name: IST-2016-671-v1+1_796.pdf
  file_size: 405870
  relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
publist_id: '4670'
pubrep_id: '671'
related_material:
  record:
  - id: '1675'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: Proofs of Space
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...