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