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