How Can I Get You To Do a Difficult Piece of Maths …
And Check You Have Complete It, Without Actually Computing It? Meet Verifiable Delay Functions
Let’s say I want you to do some work, and you show me the result. But, I don’t want to actually do the work, but still, check it. With this, we can use a difficult mathematical calculation that must be done in a certain way, and where there are no shortcuts. One way is to compute:
and where we need to compute g times g time g … for 2^T times. There is no shortcut with parallel processing. We then need to find a way for Peggy (the prover) to prove her work, and Victor (the verifier) to check the work in a simple way.
Verifiable Delay Function (VDF)
For this we can use a Verifiable Delay Function (VDF) where we can prove that a given amount of work has been done by Peggy. Victor can then send the Peggy a proof value, and for her to compute a result which verifies the work has been done, without Victor needing to do the work.
VDFs were first proposed by Dan Bohen et al [4], but it was Pietrzak [1] and Wesolowski [2] who then proposed the repeated squaring function to define the workload. In this article, we will implement the Wesolowski method:
