### 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$$.