Paper 2019/619

Continuous Verifiable Delay Functions

Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass


We introduce the notion of a \textit{continuous verifiable delay function} (cVDF): a function $g$ which is (a) iteratively sequential---meaning that evaluating the iteration $g^{(t)}$ of $g$ (on a random input) takes time roughly $t$ times the time to evaluate $g$, even with many parallel processors, and (b) (iteratively) verifiable---the output of $g^{(t)}$ can be efficiently verified (in time that is essentially independent of $t$). In other words, the iterated function $g^{(t)}$ is a verifiable delay function (VDF) (Boneh et al., CRYPTO '18), having the property that intermediate steps of the computation (i.e., $g^{(t')}$ for $t'<t$) are publicly and continuously verifiable. We demonstrate that cVDFs have intriguing applications: (a) they can be used to construct \textit{public randomness beacons} that only require an initial random seed (and no further unpredictable sources of randomness), (b) enable \textit{outsourceable VDFs} where any part of the VDF computation can be verifiably outsourced, and (c) have deep complexity-theoretic consequences: in particular, they imply the existence of \textit{depth-robust moderately-hard} Nash equilibrium problem instances, i.e. instances that can be solved in polynomial time yet require a high sequential running time. Our main result is the construction of a cVDF based on the repeated squaring assumption and the soundness of the Fiat-Shamir (FS) heuristic for \textit{constant-round proofs}. We highlight that when viewed as a (plain) VDF, our construction requires a weaker FS assumption than previous ones (earlier constructions require the FS heuristic for either super-logarithmic round proofs, or for arguments).

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
Verifiable delay functionscontinuous verifiabilityrandomness beaconsPPAD hardness
Contact author(s)
nephraim @ cs cornell edu
cfreitag @ cs cornell edu
ilan komargodski @ ntt-research ac il
rafael @ cs cornell edu
2020-08-18: last of 3 revisions
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass},
      title = {Continuous Verifiable Delay Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/619},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.