Verifiable delay function

A verifiable delay function is a function, fixed by public parameters for a delay , whose value at each input takes parallel time to compute and comes with a proof verified in time ; every adversary running in time finds an input and a verifying output other than its value only with negligible probability, and every adversary that precomputes on the public parameters in time and then runs in parallel time , for a constant , on any polynomial number of processors computes the value at a uniformly random input only with negligible probability. The syntax and the correctness, soundness and -sequentiality definitions below are those of BBBF18.

Syntax

A VDF is a triple of algorithms :

  • , a randomized algorithm running in time that outputs an evaluation key and a verification key ; specifies an efficiently sampleable input space and an output space . may use secret randomness, in which case the scheme needs a trusted setup.
  • , which on input outputs and a possibly empty proof ; it may use randomness to compute but not , and runs in parallel time with processors.
  • , a deterministic algorithm running in total time .

Properties

Correctness

is correct if for all , all , every in the support of and every , if then — BBBF18.

Soundness

Soundness requires that an adversary running in time find an input and an output other than the one computes on it, with a verifying proof, only with negligible probability.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{snd}}_{\mathsf{VDF},T,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp = (\mathit{ek}, \vk) \gets \Setup(1^\secpar, T)$
\State $(x, y, \pi) \gets \calA(1^\secpar, \pp, T)$
\State $(y^*, \pi^*) \gets \Eval(\mathit{ek}, x)$
\Comment{$y^*$ does not depend on $\Eval$'s randomness}
\Return $[\Vrfy(\vk, x, y, \pi) = 1 \wedge y \ne y^*]$
\end{algorithmic}
\end{algorithm}

is sound if for all running in time ,

is negligible — BBBF18.

Sequentiality

The adversary is a pair : precomputes on the public parameters before the input is chosen, and computes the value on a uniform input.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{seq}}_{\mathsf{VDF},T,\calA_0,\calA_1}(\secpar)$}
\begin{algorithmic}
\State $\pp = (\mathit{ek}, \vk) \gets \Setup(1^\secpar, T)$
\State $L \gets \calA_0(1^\secpar, \pp, T)$
\Comment{total time $\poly(T, \secpar)$}
\State $x \getsr \calX$
\State $y_\calA \gets \calA_1(L, \pp, x)$
\Comment{parallel time $\sigma(T)$ on at most $p(T)$ processors}
\State $(y, \pi) \gets \Eval(\mathit{ek}, x)$
\Return $[y_\calA = y]$
\end{algorithmic}
\end{algorithm}

For functions and , is -sequential if for all randomized running in total time and running in parallel time on at most processors,

is negligible — BBBF18. The bound on is necessary because computes in parallel time .

is sequential if, for some with for a constant , it is -sequential for every polynomial and every polynomial delay . MSW20 state sequentiality for parallel time on parallel processors, with as their example — MSW20.

Variations

Weak VDFs

A weak VDF is defined as above except that may use processors — BBBF18.

Other results

  • BBBF18 give the first candidate constructions with an exponential gap between evaluation and verification time — BBBF18.
  • Pietrzak makes the time-lock puzzle of RSW96 publicly verifiable: a statistically sound public-coin interactive protocol proves that satisfies without the prover knowing the factorization of , working in the group of signed quadratic residues for a product of two safe primes, and the Fiat–Shamir transform makes it non-interactive. Sequentiality rests on the assumption that repeated squaring in that group cannot be sped up, a sequential squaring assumption — Pie19.
  • Wesolowski’s VDF is built on groups of unknown order, such as an RSA group or the class group of an imaginary quadratic field; its output and its proof are each a single group element — Wes19. BBF18 prove Wesolowski’s proof of exponentiation sound in groups satisfying the adaptive root assumption, that no efficient adversary that outputs a group element and then receives a random prime can output with , and show that the adaptive root assumption implies the low order assumption, that no efficient adversary outputs an element together with a small positive integer such that — BBF18.
  • No reduction from ROM to VDF: with running time measured in oracle queries and parallel time in rounds of oracle queries, VDFs do not exist relative to a random oracle alone — GRY25, AAK+25.

Participates in

Builds on Verifiable delay function

Produces Verifiable delay function

Barriers