Verifiable Delay Functions (VDFs for short) are a fascinating new cryptographic primitive that essentially allow you to do two important things: prove to other people that you spent a certain amount of time running a function, and do it in a way that the person you are proving it to can check quickly. They were introduced very recently by Boneh, Bonneau, Bünz and Fisch in a paper titled 'Verifiable Delay Functions'.
Some basic examples of what you could use this for could be securely running a lottery on a blockchain where you use the output of the VDF of a given block hash to pick the winner, thereby preventing a miner from playing with the hash of the block to try and win the lottery themselves. Another use could be to add a delay to a Proof of Stake consensus algorithm to prevent bad actors from rushing and predicting the randomness to their own benefit. A third (also blockchain-related) use-case could be to implement a 'proof of elapsed time' consensus protocol that doesn't depend on trusted hardware.
More recently, two very clean VDF constructions have emerged, thanks to Pietrzak and Wesolowski. In this article I'm going to give a technical walk-through of the Wesolowski VDF scheme.
The specific VDF being discussed is a fairly simple operation over a finite group of unknown order, which is a group theory phrase for: A set of numbers that has a clear upper limit, but where not every number is easily known. For the purposes of this explainer, we can use the RSA group, doing all multiplications modulo N. (If you care more about the selection of the group, take a look at section 6 of this VDF Survey paper)
With that knowledge, our VDF looks like this (modulo N is implied):
y = x^(2^T)
Where x is the input value, hashed into the group, T is the publicly known delay parameter, used to control how long to delay for, and y is the output.
This is really simple, right?
It works nicely as a delay function because in order to perform any given operation, you need the output of the previous operation, making it serial. There is some room for limited parallelism within the individual multiplications, but it's not much since the width of the numbers involved is fixed.
The reason that we say that `T` is the delay parameter of `x^(2^T)`, as opposed to `2^T` is that this operation actually only takes `T` steps to do since you can just repeatedly square the value, `T` times.
Now, say you computed this. How does someone check it?
This is where the 'verifiable' part of VDF comes from, and is actually the hard part of the whole thing. The verifier could just run the function themselves to check, but that would also take a long time. We want the verifier to be able to check the result quickly. To do this, we need to create a proof.
Note: This proving scheme will be described as an interactive 'game' between the 'prover' (person running the VDF) and the 'verifier' (person checking that you did the VDF properly). It can be adapted to be non-interactive as long as you have some nice public source of randomness.
So, to prove the VDF, the verifier starts by picking a random prime number L, and sending it to the prover. There are some particulars about how this is done, it needs to be a large enough prime, but for now, let's assume it's a random 120bit long prime.
Now, the prover divides 2^T by L to get the quotient q and the remainder r. They then compute x^q, call it pi, and send that, along with their original output y, back to the verifier.
The verifier now computes r = (2^T) mod L, which is pretty fast to do, especially compared to x^(2^T). They then check that the output value y that they were given by the prover is equal to pi^L * x^r. If they line up correctly, then the prover did the math correctly!
But hold up, why does this work?
We are checking the following equality:
y = pi^L * x^r
A few things to remember: When multiplying the same number with different exponents, you add the exponents. When applying an exponent to a number with an exponent, you multiply:
x^4 * x^5 = x^9and(x^4)^5 = x^20
Also remember the equation involving L, q and r: 2^T = q*L + r (dividing 2^T by L gets you the quotient q and remainder r).
Now, looking back at our proof checking equation, let's substitute back in the values for y:
y = pi^L * x^r becomesx^(2^T) = pi^L * x^r
And, if we substitute back in the value for pi:
x^(2^T) = (x^q)^L * x^r
Everything on the right side has the same base, so we can use the exponent combination rules to get to:
x^(2^T) = x^(q*L + r)
And since we know from before that 2^T is equal to q*L + r, both sides are equal, and our proof is validated!
To reply you need to sign in.