### Simple Verifiable Delay Functions

Krzysztof Pietrzak

##### 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 $(N,x,T,y)$ satisfies $y=x^{2^T}\pmod N$ where the prover doesn't know the factorization of $N$ and its running time is dominated by solving the puzzle, that is, compute $x^{2^T}$, 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 a key ingredient. For typical parameters ($T\le 2^{40},N=2048$), our proofs are of size around $10KB$, verification cost around three RSA exponentiations and computing the proof is $8000$ times faster than solving the puzzle even without any parallelism.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MINOR revision.10th Innovations in Theoretical Computer Science (ITCS) 2019
DOI
10.4230/LIPIcs.ITCS.2019.60
Keywords
Verifiable Delay FunctionRSA
Contact author(s)
pietrzak @ ist ac at
History
2019-04-30: last of 3 revisions
See all versions
Short URL
https://ia.cr/2018/627

CC BY

BibTeX

@misc{cryptoeprint:2018/627,
author = {Krzysztof Pietrzak},
title = {Simple Verifiable Delay Functions},
howpublished = {Cryptology ePrint Archive, Paper 2018/627},
year = {2018},
doi = {10.4230/LIPIcs.ITCS.2019.60},
note = {\url{https://eprint.iacr.org/2018/627}},
url = {https://eprint.iacr.org/2018/627}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.