[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},
}