Paper 2018/627

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.

Metadata
Available format(s)
PDF
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
2018-06-26: received
See all versions
Short URL
https://ia.cr/2018/627
License
Creative Commons Attribution
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.