or How to make things a little slower.

Recently been reading about randomness in ethereum and blockchains generally.

Randomness on blockchains doesn’t exist in ideal form and is hard to find. The use of randomness has various applications like raffles, lotteries, or perhaps an auction model where the initial minimum bid is randomly chosen from a list. On a protocol level, the protocol can also use this randomness to achieve privacy or select a random block producer in the case of proof of stake consensus.

The closest we come to is using chainlink VRFs which, when provided with a seed, generate a random number published on-chain with proof and can be verified using the oracle’s public key and application seed. VRFs have been used in crypto in various applications and at the protocol level in Cardano (Ouroboros) and Polkadot.

Another way to achieve randomness is using Verifiable Delay functions, proposed by Dan Boneh, Joseph Bonneau, Benedikt Bunz and Ben Fisch.

Consider the scenario where you have to run a lottery. While the usual way would be to give everyone tickets and draw from a random set of numbers, we want to run a verifiable lottery so that no one should be able to manipulate the numbers drawn/generated. Randomness beacons are of help here. What is a randomness beacon? Randomness beacons are public sources of randomness which emit random values at constant times. The generated values must be such that they can’t be manipulated and be predictable. How does one go about making them? One way of doing so is to “apply an extractor function to a public entropy source”, basically using a function which can convert highly unpredictable signals into random numbers. The randomness comes because these signals themselves are hard to predict.

For example, think of using the values of 100 stock prices. You can use the closing prices and then hash them to get a random value. A motivated adversary (with enough funds) could manipulate the stock prices of a few stocks, though (let’s assume k). In this scenario, the adversary would read the prices of the stocks it cannot control (100 - k) and then quickly simulate 2^k scenarios based on the outcomes that it can change (i.e. manipulate the stock of the price upwards or downwards). Then this would generate some number which is more favourable to the adversary.

Some outlandish suggestions to improve this could, of course, involve applying extractor functions to the weather or more natural phenomena which are beyond human control. Another way of doing this would be to add a delay function after extraction. In this case, let’s say the market closes at 3:30 pm and adding the delay function makes it so that the random value is generated at 4:30, and the prices are finalized. The adversary would not be able to manipulate or simulate the outcomes of any such strategy.

Simply stopping the clock for an hour and using the extractor function on the prices is not sensible since the adversary will also be able to do it. Hence the nature of the delay function should be so that any adversary, regardless of having access to massive parallel computation, still need to spend at least T time (an hour in our example) to arrive at anything close to what the delay function does.

Verifiable delay functions are cryptographic primitives that have been formalized to act as delay functions with additional properties.

Now let’s take a formal look at this.

VDFs have the following advantages: (from Vitalik’s post on VDFs)

• Relative to RANDAO and similar schemes, they cannot be manipulated.
• Relative to BLS threshold signatures and similar VRFs (verifiable random functions), they do not depend on any specific fraction of nodes to be online and do not require a complicated setup procedure.

Verifiable Delay Functions (VDFs)

A VDF consists of 3 sets of algorithms.

1] Setup (λ, T) - This function takes security parameter λ, and delay parameter T and outputs public parameters pp = (ek, vk), where ek stands for the evaluation key and vk stands for the verification key. The setup function also fixes the range and domain of the VDF. The delay parameter T acts as the time-bound.

2] Eval (pp, x) - This function takes an element x in the domain, outputs a y in the range, and produces a proof π.

3] Verify (pp, x, y, π) - Given x, y and proof π, it verifies that y is the correct output of x.

Another thing to note about the setup stage is that it might need an initial trusted setup.

A VDF should satisfy the following properties:

1] Uniqueness: if verify (pp, x, y, π) = verify (pp, x, y’, π), then y = y’

2] Sequentiality: if A is an algorithm which runs (A, x) < T (the delay parameter), then it can’t distinguish the output from some random number. One of the ways to do this is to have an iterative application of function where in you apply f(f(f(f…..f(x))) t times here. Regardless of parallel computation, you would have to run the function t times to arrive at the result, but in this case, the proof can be slower to generate (and this is also one of the bottlenecks of creating efficient VDFs). This can also be called t-sequentiality.

3] Efficiently verifiable: Once the output is generated, it should be easy and quick to check that it is the correct output.

Simply speaking, what we require from VDFs is:

• The function should be slow to evaluate for both the honest agents and motivated adversaries who have a lot of parallel compute or specialized hardware
• The function should be easily verifiable.

Construction of VDFs

A theoretical model presented in the paper

As spoken about in the sequentiality section, one way would be to apply the function t times, and this can be accomplished through a Hashchain (which is just hashing the input x) and then hashing it again up to T times to get Y.

The way to make a Hashchain verifiable would be to combine it with SNARK or STARKs to generate the proof. The issue with this is that π is incredibly slow to calculate.

One immediate improvement to this procedure is to break down the Hashchain and generate the proof iteratively.

where in you apply the hash function and generate the proof for a few hash applications and then use it to generate the proof after that, so generating the proof while you create the output.

A few optimisations can be made to make it snark optimized, like choosing SNARK-friendly hash functions or replacing the H with a permutation that is slow in the forward direction but fast in the reverse direction.

While treatment of the permutation functions considered is beyond the scope of this blog, permutation polynomials usage for a VDF is still an open question.

You can take a look at this talk for more.

Simple and Efficient VDFs

The papers, “Simple Verifiable Delay Functions” by Pietrzak et al. and Efficient Verifiable Delay Functions by Wesolowski et al. show possible ways VDFs can be constructed.

The only matter they differ in is the way the proof is generated.

(You will need some knowledge of group theory to follow along after this)

An Algebraic Construction

So in this construction, you assume you have a finite cyclic group of unknown order.

The Setup of VDF will be the unknown order group and the hash function, which maps the input X into the group.

The Evaluation will be y = H(x)^(2^T), which in the case of finite groups will belong to G itself, as seen above.

It’s very important that you don’t know the order of the group because if you know the order of the group, let’s say N, the evaluation function reduces to a much simpler:

y = H (x) ^ ( (2 ^ T) / mod N)

which is trivial to solve for smaller order groups.

One thing to note here is that to assure security; you probably need to choose a very large n (around 4000 bits) to make it secure enough that the adversary can’t crack.

The proof for this, called the proof of correct exponentiation, can be seen in the papers and has been arrived at in different ways.

Efficient Verifiable Delay Functions

The motivation for the construction is from Time-lock puzzles by Rivest, Shamir and Wagner, where they use an RSA group to lock the time-lock puzzle for a period of T seconds and arrive at a much similar formula.

The interactive argument/proof for this would look like this:

Interactive proofs, as suggested by their name, require interaction between the prover (Alice) and the verifier (Bob), but this proof gives you an idea of how it can be proved and then converted to a non-interactive proof with the help of the Fiat-Shamir Heuristic.

Assume the function, x^(2^10)

Walking through a small example for convenience, this would look like, as mentioned above, 2^10 = 1024,

• Bob, let’s say, chooses a prime 13
• Alice finds the q and r given e = 13, which turns out to be 1024 = 78 * 13 + 10, so you arrive at q = 78 and r = 10
• Alice sends back proof π = x^q, so you end at x^78
• Bob computes the remainder, r = 10 using e
  • Accept if π^e* x^r = y
  • In our case, this would be (x^78)^13 * x^10 = y
    • This results in x^1014 * x^10 = x^1024, which we started with.

The non-interactive version of the proof iteratively takes the next prime number, which satisfies this proof.

In the case of Simple Verifiable Delay Functions by Pietrzak, the proof is in the form of an interactive iterative protocol and is then similarly converted to its non-interactive form.

NOTE: Something I’ve not covered in this blog and is just as important is the complexity analysis of these protocols (efficiency/ how fast they are), and that’s an important criterion in selecting one construction over the other.

Application of VDFs

VDFs can be used in

• Leader Selection (in Resource Efficient Blockchains) - While a number of blockchains already use VRFs and other techniques to select leaders. VDFs can also select new leaders at regular intervals using a randomness beacon.
• Lotteries
• Randomness Beacons - VDFs can be used to make public sources of entropy (as discussed at the start), like stock market prices, a randomness beacon.
• Computational Timestamps
• VDFs can also be used to provide transaction randomization to in fully private protocols, as told in A note on Privacy in Constant Function Market Makers (which I will cover next).

VDFs are relatively very new cryptographic primitives which have immense application in generating randomness with few assumptions and can also boost privacy and other mechanisms in the crypto space.

The open questions for VDFs are

• to generate a Quantum Resistant VDF.
• Are there other groups of unknown order?

Some Resources

• Verifiable Delay Functions - Original Paper
• Efficient Verifiable Delay Functions - Wesolowski et al
• Simple Verifiable Delay Functions - Pietrzak et al
• A Survey of Two Verifiable Delay Functions (a survey paper of the above two methods)
• Introduction to VDFs Talk by Joseph Bonneau at Protocol Labs
• Verifiable Delay Functions Talk by Ben Fisch at IACR
• Verifiable Delay Functions Talk by Ben Fisch at BPASE 18, Stanford Cyber Initiative
• Verifiable Delay Functions talk by Dan Boneh at Ethereum Foundation
• VDF Research, Maintained by the VDF alliance → To look at work that has happened in various directions since VDFs came out.