---
_id: '6528'
abstract:
- lang: eng
  text: We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner
    time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically
    sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod
    N) where the prover doesn’t know the factorization of N and its running time is
    dominated by solving the puzzle, that is, compute x2T, which is conjectured to
    require T sequential squarings. To get a VDF we make this protocol non-interactive
    using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia
    blockchain design, which uses a VDF as akey ingredient. For typical parameters
    (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around
    three RSA exponentiations and computing the proof is 8000 times faster than solving
    the puzzle even without any parallelism.
alternative_title:
- LIPIcs
article_number: '60'
article_processing_charge: No
author:
- 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: 'Pietrzak KZ. Simple verifiable delay functions. In: <i>10th Innovations in
    Theoretical Computer Science Conference</i>. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2019. doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2019.60">10.4230/LIPICS.ITCS.2019.60</a>'
  apa: 'Pietrzak, K. Z. (2019). Simple verifiable delay functions. In <i>10th Innovations
    in Theoretical Computer Science Conference</i> (Vol. 124). San Diego, CA, United
    States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ITCS.2019.60">https://doi.org/10.4230/LIPICS.ITCS.2019.60</a>'
  chicago: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In <i>10th
    Innovations in Theoretical Computer Science Conference</i>, Vol. 124. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.ITCS.2019.60">https://doi.org/10.4230/LIPICS.ITCS.2019.60</a>.
  ieee: K. Z. Pietrzak, “Simple verifiable delay functions,” in <i>10th Innovations
    in Theoretical Computer Science Conference</i>, San Diego, CA, United States,
    2019, vol. 124.
  ista: 'Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in
    Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical
    Computer Science, LIPIcs, vol. 124, 60.'
  mla: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” <i>10th Innovations
    in Theoretical Computer Science Conference</i>, vol. 124, 60, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2019, doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2019.60">10.4230/LIPICS.ITCS.2019.60</a>.
  short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
  end_date: 2019-01-12
  location: San Diego, CA, United States
  name: 'ITCS 2019: Innovations in Theoretical Computer Science'
  start_date: 2019-01-10
date_created: 2019-06-06T14:12:36Z
date_published: 2019-01-10T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '10'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.60
ec_funded: 1
file:
- access_level: open_access
  checksum: f0ae1bb161431d9db3dea5ace082bfb5
  content_type: application/pdf
  creator: dernst
  date_created: 2019-06-06T14:22:04Z
  date_updated: 2020-07-14T12:47:33Z
  file_id: '6529'
  file_name: 2019_LIPIcs_Pietrzak.pdf
  file_size: 558770
  relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: '       124'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2018/627
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science Conference
publication_identifier:
  isbn:
  - 978-3-95977-095-8
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Simple verifiable delay functions
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2019'
...
---
_id: '7407'
abstract:
- lang: eng
  text: 'Proofs of space (PoS) [Dziembowski et al., CRYPTO''15] are proof systems
    where a prover can convince a verifier that he "wastes" disk space. PoS were introduced
    as a more ecological and economical replacement for proofs of work which are currently
    used to secure blockchains like Bitcoin. In this work we investigate extensions
    of PoS which allow the prover to embed useful data into the dedicated space, which
    later can be recovered. Our first contribution is a security proof for the original
    PoS from CRYPTO''15 in the random oracle model (the original proof only applied
    to a restricted class of adversaries which can store a subset of the data an honest
    prover would store). When this PoS is instantiated with recent constructions of
    maximally depth robust graphs, our proof implies basically optimal security. As
    a second contribution we show three different extensions of this PoS where useful
    data can be embedded into the space required by the prover. Our security proof
    for the PoS extends (non-trivially) to these constructions. We discuss how some
    of these variants can be used as proofs of catalytic space (PoCS), a notion we
    put forward in this work, and which basically is a PoS where most of the space
    required by the prover can be used to backup useful data. Finally we discuss how
    one of the extensions is a candidate construction for a proof of replication (PoR),
    a proof system recently suggested in the Filecoin whitepaper. '
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- 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: 'Pietrzak KZ. Proofs of catalytic space. In: <i>10th Innovations in Theoretical
    Computer Science  Conference (ITCS 2019)</i>. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2018:59:1-59:25. doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2019.59">10.4230/LIPICS.ITCS.2019.59</a>'
  apa: 'Pietrzak, K. Z. (2018). Proofs of catalytic space. In <i>10th Innovations
    in Theoretical Computer Science  Conference (ITCS 2019)</i> (Vol. 124, p. 59:1-59:25).
    San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPICS.ITCS.2019.59">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>'
  chicago: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In <i>10th Innovations
    in Theoretical Computer Science  Conference (ITCS 2019)</i>, 124:59:1-59:25. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href="https://doi.org/10.4230/LIPICS.ITCS.2019.59">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>.
  ieee: K. Z. Pietrzak, “Proofs of catalytic space,” in <i>10th Innovations in Theoretical
    Computer Science  Conference (ITCS 2019)</i>, San Diego, CA, United States, 2018,
    vol. 124, p. 59:1-59:25.
  ista: 'Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical
    Computer Science  Conference (ITCS 2019). ITCS: Innovations in theoretical Computer
    Science Conference, LIPIcs, vol. 124, 59:1-59:25.'
  mla: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” <i>10th Innovations in
    Theoretical Computer Science  Conference (ITCS 2019)</i>, vol. 124, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2019.59">10.4230/LIPICS.ITCS.2019.59</a>.
  short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science  Conference
    (ITCS 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25.
conference:
  end_date: 2019-01-12
  location: San Diego, CA, United States
  name: 'ITCS: Innovations in theoretical Computer Science Conference'
  start_date: 2019-01-10
date_created: 2020-01-30T09:16:05Z
date_published: 2018-12-31T00:00:00Z
date_updated: 2021-01-12T08:13:26Z
day: '31'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.59
ec_funded: 1
file:
- access_level: open_access
  checksum: 5cebb7f7849a3beda898f697d755dd96
  content_type: application/pdf
  creator: dernst
  date_created: 2020-02-04T08:17:52Z
  date_updated: 2020-07-14T12:47:57Z
  file_id: '7443'
  file_name: 2018_LIPIcs_Pietrzak.pdf
  file_size: 822884
  relation: main_file
file_date_updated: 2020-07-14T12:47:57Z
has_accepted_license: '1'
intvolume: '       124'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2018/194
month: '12'
oa: 1
oa_version: Published Version
page: 59:1-59:25
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)
publication_identifier:
  isbn:
  - 978-3-95977-095-8
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Proofs of catalytic space
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2018'
...