Continuous Verifiable Delay Functions

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.