# Continuous Verifiable Delay Functions

Ilan Komargodski

Room 116

We introduce the notion of a *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.

In this talk, I will present a construction of a cVDF based on the repeated squaring assumption and the soundness of the Fiat-Shamir (FS) heuristic for constant-round proofs. I will also demonstrate that cVDFs have intriguing applications: (a) they can be used to construct a *public randomness beacon* that only requires an initial random seed (and no further unpredictable sources of randomness), (b) enable *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 *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.

Based on joint work with Naomi Ephraim, Cody Freitag, and Rafael Pass.