Verifiable Delay Functions

Verifiable Delay Functions (VDF) was introduced in 2018 and has become an active research aera in cryptography. VDF has many applications in blockchains, such as randomness beacon, resource-efficient blockchain, computational timestamping, etc. In this chapter, we first give a brief overview of VDF, then study and discuss several existing VDF constructions.

Author(s): phamnhatminh1292001

Introduction to VDF

Verifiable Delay Functions (VDF) were introducted by Boneh et al BBBF18 in 2018. Informally, a VDF is a funtion that requires a specified number of step to compute its output, even with a large number of parallel processor, but the correctness of the output can be quickly verified. While there can be many functions that require a specified of step to compute its output, not all of them are qualified to become VDFs. For example, consider the function $f(X)=\mathsf{SHA256}^t(X)=\mathsf{SHA256}(\mathsf{SHA256}(...(\mathsf{SHA256}(X))...))$. Calculating $f(X)$ require $t$ iterations, even on a parallel computer. However, verification would also require $t$ iterations, thus the function $f(X)$, while VDF verification time must be within $O(poly(\log t))$. VDFs has found it application in many aspects BBBF18. We will highlight some of them later in the Application section.

VDF Algorithms

A VDF consists of three algorithms $(\mathsf{Gen}, \mathsf{Eval}, \mathsf{Verify})$ where:

$(ek,vk) \leftarrow \mathsf{Gen}(1^{\lambda},t)$: This algorithm takes as input as a security parameter $\lambda$, and outputs a public key pair $(ek,vk)$.

$(Y,\pi) \leftarrow \mathsf{Eval}(X,ek,t)$: This algorithm takes an input an evaluation key $sk$, a value $X$ a time parameter $t$ and outputs a value $Y \in \\{0,1\\}^{out(\lambda)}$ and a proof $\pi$.

$b \leftarrow \mathsf{Verify}(vk,X,Y,\pi,t)$: This algorithm takes an input a verification key $vk$, a value $X$, a value $Y$, a proof $\pi$, a time parameter $t$ and outputs a bit $b$ that determines whether $Y=\mathsf{Eval}(X,ek)$. This algorithm run within time $O(poly(\log t))$.

VDF Properties

We require a VDF to have the following security properties:

Correctness: For all parameter $x$,$t$ and $(ek,vk) \leftarrow \mathsf{Gen}(1^{\lambda})$ if $(Y,\pi)=Eval(ek,X,t)$ then $Verify(vk,X,Y,\pi,t)=1$

Soundness: A VDF is sound if every algorithms $A$ can solve the following problem with negligible probability in $\lambda$: Given $ev,vk$ output $X,Y,\pi$ such that $(Y,\pi) \neq Eval(ek,X,t)$ and $Verify(vk,X,Y,\pi,t)=1$.

Sequentiality: A VDF is $t-$sequentiality if for all algorithms $A$ with at most $O(\mathsf{poly}(t))$ parallel processors and runs within time $O(\mathsf{poly}(t))$, the experiment $ExpSeq*{VDF}^{A}(1^\lambda)$ is negilible in $\lambda$, where $ExpSeq*{VDF}^{A}(1^\lambda)$ is described as follows:

$ExpSeq\_{VDF}^{A}(1^\lambda)$:

• $(ek,vk) \leftarrow \mathsf{Gen}(1^{\lambda})$
• $X {\stackrel{\$}{\leftarrow}} \\{0,1\\}^{in(\lambda)}$
• $(Y,\pi) \leftarrow A(X,ek,vk)$
• Return $(Y,\pi)==\mathsf{Eval}(X,ek,t)$

VDF Applications

We present several applications of VDF below:

Randomness Beacon: To see the application of VDF in randomness beacons, we take a look at two examples below: In proof of work blockchains, miners find solutions to computational puzzles and then submits them for monetary rewards. However, there can be more than one solution, and a miner may submit the one that benefits him the most, or refuse to submit if it does not benefit him. Using VDF, then given the deterministic nature of VDF, a miner cannot choose any output other than the VDF output for his goal. Another example is the the RANDAO Ra17 that use "commit-and-reveal" paradigm. In RANDAO, each participant $P_i$ submit the commitment of a random value $s_i$, after each participants reveal $s_i$ and the final output is defined to be $s=\oplus_{i=1}^ns_i.$. The problem is that the last participant may not submit his value if the final output does not benefit him. One approach to solve this problem is to use VDF. After all $s_i$s are revealed, the value $H(s_1,s_2,...,s_n)$ is used as the seed of the VDF and the beacon output is the VDF output LW15. With a sufficient time parameter, the last participant cannot predict the output on time, even if he knows the seed.

Resource efficient Blockchain: Various attempts have been made to develop resource-efficient blockchains to reduce energy consumption. However, resource-efficient mining suffers from nothing-at-stake attack BBBF18. Cohen proposes to combine proof of resources KCMW15 with an incremental verifiable delay function and use the product of proven resources and induced delay as a measure of blockchain quality. This scheme prevents nothing-at-stake attacks by simulating the proof-of-work mining process WXWJWR22. For other applications of VDF, we refer the readers to BBBF18.

A Survey of VDF Constructions

In this section, we study several well known candidates for VDF constructions. These include: the construction of Dwork and Naor DN92, the construction of Pietrzak Pie19 and Wesolowski Wes19, and the isogeny based construction of de Feo et al FMPS19. Then we compare these constructions. Finally, we discuss a possible construction based on incremential verifiable computation BBBF18.

Modular Square Root based Construction

One of the early example of VDF can be found in the paper of Dwork and Naor DN92. Their construction require a prover, to compute $Y=\sqrt(X) \pmod{p}$ for a prime $p$ and input $X$. When $p \equiv 3 \pmod{4}$ we see that $Y=X^{\dfrac{p+1}{4}} \pmod{p}$, and thus computing $Y$ requires $O(\log p)$ computation steps. Verifying only require one multiplication by checking $Y^2 \equiv X \pmod{p}$. The construction is formally described as follow.

$\mathsf{Gen}(1^\lambda)$: The algorithm outputs a $\lambda$ bit prime $p$ where $p \equiv 3 \pmod{4}$.

$\mathsf{Eval}(X)$: Compute $Y=X^{\dfrac{p+1}{4}} \pmod{p}$. The proof $\pi$ is $Y$.

$\mathsf{Verify}(X,Y,\pi)$: Check if $Y^2 \equiv X \pmod{p}$.

This construction, althought very simple, has two problem: First, the time parameter $t$ is only to $\log p$, thus to increase $t$, a very large prime $p$ is required. Second, it is possible to use parallel processors to speed up in field multiplications.

Group of Unknown Order based Constructions

As its name suggests, most constructions follow this direction uses a group $G$ such that $|G|$ is unknown. These constructions require the prover to calculate the value $y=g^{2^t}$ and provide a proof $\pi$ of $y$ that allows efficient verification. Without the knowledge of $|G|$, calculating $y$ requires $O(t)$ steps. There are two candidates for such a group: The RSA group and the Class Group of Imaginary Quadratic Number Field. The RSA group is the group $G=(\mathbb{Z}^\times,.)$ where $N$ is a product of two primes with unknown factorization. Computing the group order of $N$ is as hard as factoring $N$, so $G$ can be seen as a Group of Unknown Order. However, the problem of the RSA group is that we require a trusted party to generate $N$. To avoid trusted setup, we can choose $G$ to be the class group of an imaginary quadratic field. For a large $d \equiv 3 \pmod{4}$, it is assumed that the order of the class group of $\mathbb{Q}(\sqrt{d})$ is hard to compute.

Pietrzak's Construction

Pietrzak Pie19 proposed a VDF based on a Group of Unknown Order. His idea for generating the proof for $y=g^{2^t}$ is to use the identity $z^ry=(g^rz)^{2^{t/2}}$ for any $r$ where $z=g^{2^{t/2}}$. His construction is described below.

$\mathsf{Gen}(1^\lambda)$: The algoritms outputs $pp=(G,H)$, where:

• $G$ is a finite group.
• $H$, a hash function that maps arbitary input length to a bit string.

$\mathsf{Eval}(X,pp,t)$: To generate the proof for $Y=g^{2^t}$, compute $u*{i+1}=u_i^{r_i+2^{t/2^i}}$, where $r_i=H(u_i,t/2^i,v_i,u_i^{2^{t/2^i}})$ and $v_i=u_i^{r_i2^{t/2^i}+2^t}$. The algorithm outputs $(Y,\pi)$=$(g^{2^t},\\{u_1,u_2,...,u_{\log t}\\})$.

$\mathsf{Verify}(X,Y,\pi,pp,t)$: To verify the output, compute $v_i=u_i^{r_i2^{t/2^i}+2^t}$ and check if $v_{\log t}==u\_{\log t}^2$.

Wesolowski's Construction

Independently from Pietrzak, Wesolowski Wes19 also constructed a VDF based on a Group of Unknown Order. Unlike Pietrzak's, Wesolowski's construction has shorter proof size and allows faster verification. However, the proving time is slower, as it require $O(t)$ computation steps compared to $O(\sqrt{t})$ in Pietrzak's construction.

$\mathsf{Gen}(1^\lambda)$: The algoritms outputs $(pk,sk)$=$((G,H_1,H_2),|G|)$ where:

• $G$ is a finite group.

• $H_1$ is a hash function that maps a bit string $X$ to an element $g$ in $G$.

• $H_2$ is a hash function that maps arbitary input length to a bit string. $\mathsf{Eval}(X,sk,t)$: By converting $X$ to an element $g=H_1(X) \in G$, the algorithm outputs $(Y,\pi)$=$(g^{2^t},g^{(2^t-r)/l})$, where $l=H_2(g||Y)$. The trapdoor information makes calculation faster as follow:

• Eval with trapdoor: With the knowledge of $|G|$ as a trapdoor, the value of $Y$ can be computed within $O\log t$ time by calculating $e=2^t \pmod{|G|}$ and $Y=g^e$. Similarly, one can compute $\pi$ quickly by calculating $q=(2^t-r)/l \pmod{|G|}$ and $\pi=g^q$.

• Eval without trapdoor: Without the knowledge of $|G|$, computation of $Y$ and $\pi$ require $O(\lambda t)$ and $O(t\\log t)$ time, respectively.

$\mathsf{Verify}(X,Y,\pi,pk,t)$: To verify the output, simply check if $g^r\pi^l==Y$.

Isogeny based Constructions

In 2019, Luca de Feo et al FMPS19 constructed a VDF based on isogenies of supersingular elliptic curves and pairing. Their construction is motivated by the BLS signature, which uses a bilinear pairing. FMPS19.

For more information about elliptic curves and isogeny graph $G\_{F_q}(l)$, we refer the reader to see the Elliptic Curve chapter I wrote earlier.. Before continuing, we introduce some notations. Let $l$ be a small prime. Let $N$ be a large prime and $p$ be another prime such that $p+1$ is divisible by $N$. For an elliptic curve $E/\mathbf{F}$, define $E[N]=\\{P \in E | N_(P)=O\\}$ where $O$ is the infinity point. The definition and properties of Weil pairing can be found in BLS03. In the construction, the authors consider the pairing $e_N: E[N]\times E'[N] \rightarrow \mu_N$. As the authors stated in their paper, the main important property the pairing is that, for any curves $E$, isogeny $E \rightarrow E'$ and $P \in E[N]$ and $Q \in E'[N]$ we have $e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)$. Now we move to describe the VDF Construction.

$\mathsf{Gen}(1^\lambda,t)$: The algorithm selects a supersingular ellpitic curve $E/ \mathbb{F}$, then choose a direction of the supersingular isogeny graph of degree $l$, then compute the isogeny $\phi E \rightarrow E'$ of degree $l^t$ and its dual isogeny $\hat{\phi}$.

$\mathsf{Eval}(Q)$: For a point $Q \in E'[N]\cap E(\mathbf{F})$, outputs $\hat{\phi(Q)}$.

$\mathsf{Verify}(E,E',P,Q,\phi(P),\hat{\phi(Q)})$: Check that $\hat{\phi(Q)} \in E[N]\cap E(\mathbf{F})$ and $e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)$.

The security of the VDF is based on the assumption that, to compute the isogeny the map $\hat{\phi}$, we are expected to walk $t$ times between some vertices in the isogeny graph $G\_{F_q}(l)$. Currently, there is no efficient algorithm to find shortcut between these vertices of the graph. Finally, while the VDF is isogeny-based, it is not completely quantum secure, due to of the relation $e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)$ of bilinear pairing. Since Shor's algorithm can break the pairing inversion problem FMPS19, it can trivially recover the output $\hat{\phi(Q)}$ from the relation above.

Comparision

Now that we have described several well known VDF constructions, we would like to compare them. The table below compares the evaluation time, proof size and verification time of the VDF we described. Note that the value $P$ in the table denote the number of processors.

Construction	Eval Time	Eval Time (parallel)	Verification Time	Proof Size
Dwork and Naor	$O(t)$	$O(t^{2/3})$	$O(1)$	$O(\lambda)$
Pietrzak	$O(t+\sqrt{t})$	$O(t+\frac{\sqrt{t}}{P})$	$O(\log t)$	$O(\log t)$
Wesolowski	$O(t+\frac{t}{\log t})$	$O(t+\frac{\sqrt{t}}{P \log t})$	$\lambda^4$	$O(\lambda^3)$
Feo et al.	$O(t)$	$O(t)$	$\lambda^4$	$O(\lambda)$

Possible IVC based construction

Apart from the previous well-known constructions, we now discuss another possible direction to construct a VDF is to use Incrementally Verifiable Computation (IVC) BBBF18. The basic idea of IVC is that after each computation step, the prover can produce a proof of the current state. The proof can also be updated after each step to produce a new proof for the corresponding step. The definition and properties of IVC can be found in Pa08. Now, consider a IVC system $(\mathsf{IVC.Setup}, \mathsf{IVC.Prove}, \mathsf{IVC.Verify})$ for a function $f$, it is possible to construct a VDF as follow:

$\mathsf{Gen}(1^\lambda,t)$: Run $(ek,vk) \leftarrow$ $\mathsf{IVC.Gen}(1^\lambda,f,t)$.

$\mathsf{Eval}(X,ek,t)$: Run and output $(Y,\pi)\leftarrow$ $\mathsf{IVC.Prove}(X,ek,t)$.

$\mathsf{Verify}(X,Y,\pi,vk,t)$: Outputs $\mathsf{IVC.Verify}(X,Y,\pi,vk,t)$.

The construction above is rather general. Therefore, it remains a question to choose a suitable IVC system and a function $f$ to make the construction pratical. As suggested by Boneh et al BBBF18 and Ethereum KMT22, there are several candidate functions $f$, for example VeeDo, Sloth++ BBBF18 or Minroot KMT22. Most previous IVCs involves using succinct non-interactive arguments of knowledge (SNARK). For these IVC constructions, at each step the prover has to constructs a SNARK which verifies a SNARK BBBF18. This involves many FFT operations each step, and the SNARK verification circuit can be very expensive. In the recent NOVA KST22 proof system, the prover does not have to compute any FFT, and the recursion overhead is much lower than SNARK based IVCs KST22. It is interesting to see if there will be any IVC based VDF using NOVA.