@inproceedings{6528,
  abstract     = {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.},
  author       = {Pietrzak, Krzysztof Z},
  booktitle    = {10th Innovations in Theoretical Computer Science Conference},
  isbn         = {978-3-95977-095-8},
  issn         = {1868-8969},
  location     = {San Diego, CA, United States},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Simple verifiable delay functions}},
  doi          = {10.4230/LIPICS.ITCS.2019.60},
  volume       = {124},
  year         = {2019},
}

@inproceedings{7407,
  abstract     = {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. },
  author       = {Pietrzak, Krzysztof Z},
  booktitle    = {10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  isbn         = {978-3-95977-095-8},
  issn         = {1868-8969},
  location     = {San Diego, CA, United States},
  pages        = {59:1--59:25},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Proofs of catalytic space}},
  doi          = {10.4230/LIPICS.ITCS.2019.59},
  volume       = {124},
  year         = {2018},
}