Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Verifiable Delay Function, RSA

Original Publication (with minor differences): 10th Innovations in Theoretical Computer Science (ITCS) 2019

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:

[ Cryptology ePrint archive ]