A verifiable delay function (VDF) is a function whose evaluation requires running a given number of sequential steps, yet the result can be efficiently verified.
Take long time from computing x—— y
but short time to verify
cannot speed up
The basic idea of IVC is that at every incremental step of the computation, a prover can produce a proof that a certain state is indeed the current state of the computation. This proof is updated after every step of the computation to produce a new proof. Importantly, the complexity of each proof in proof size and verification cost is bounded by poly(λ) for any sub-exponential length computation. Additionally the complexity of updating the proof is independent of the total length of the computation.
VDF
