[Pie19] Simple Verifiable Delay Functions

Authors: Krzysztof Pietrzak | Venue: ITCS 2019 | Source

Abstract

We construct a verifable 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 satisfies where the prover doesn’t know the factorization of and its running time is dominated by solving the puzzle, that is, compute , which is conjectured to require 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 a key ingredient. For typical parameters (), our proofs are of size around , verification cost around three RSA exponentiations and computing the proof is times faster than solving the puzzle even without any parallelism.

BibTeX

@Inproceedings{ITCS:Pietrzak19b,
  author = {Krzysztof Pietrzak},
  title = {Simple Verifiable Delay Functions},
  pages = {60:1--60:15},
  editor = {Avrim Blum},
  booktitle = {ITCS 2019: 10th Innovations in Theoretical Computer Science Conference},
  volume = {124},
  address = {San Diego, CA, USA},
  month = {jan~10--12},
  publisher = {Leibniz International Proceedings in Informatics (LIPIcs)},
  year = {2019},
  doi = {10.4230/LIPIcs.ITCS.2019.60},
}