**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.

**Category / Keywords: **foundations / Verifiable Delay Function, RSA

**Original Publication**** (with minor differences): **10th Innovations in Theoretical Computer Science (ITCS) 2019
**DOI: **10.4230/LIPIcs.ITCS.2019.60

**Date: **received 22 Jun 2018, last revised 30 Apr 2019

**Contact author: **pietrzak at ist ac at

**Available format(s): **PDF | BibTeX Citation

**Version: **20190430:122513 (All versions of this report)

**Short URL: **ia.cr/2018/627

[ Cryptology ePrint archive ]