In this blog post I am going to talk about some really cool cryptographic research done by Luca De Feo, Simon Masson, Christophe Petit and myself around a relatively new cryptographic construction called

The history of VDF is actually pretty neat indeed it seems that the concept was growing slowly through the years before finally being formalized. This is somehow evident looking at the links in https://vdfresearch.org/ .

VDF were formally introduced by (the legendary) Boneh, Bonneau, Bünz and Fish in a seminal paper less than a year ago (June 2018). The paper contained only some weak form of VDF construction (based on univariate permutation polynomials ) and motivated researchers to continue to look for

*Verifiable Delay Functions*(**VDF**from now on). I know at this point you are thinking that the title of this blog post was yet another clickbait link but I promise that if you bear with me until the end you are not going to be disappointed. If you never heard about VDF fret not I will try to*ELI5*this concept. So fasten your seat belt.The history of VDF is actually pretty neat indeed it seems that the concept was growing slowly through the years before finally being formalized. This is somehow evident looking at the links in https://vdfresearch.org/ .

VDF were formally introduced by (the legendary) Boneh, Bonneau, Bünz and Fish in a seminal paper less than a year ago (June 2018). The paper contained only some weak form of VDF construction (based on univariate permutation polynomials ) and motivated researchers to continue to look for

*theoretically optimal VDF*:We still lack a theoretically optimal VDF, consisting of a simple inherently sequential function requiring low parallelism to compute but yet being very fast (e.g. logarithmic) to invert.

Well it looks that this incentive worked even better than predicted
indeed within 10 days two papers responded to the challenge. Firstly Benjamin Wesolowski then

**Krzysztof Pietrzak***published their respective papers (more on this later) :*
But let's shift down the gear and keep things in order.

## Time lock puzzle

The first construction that might resemble a VDF goes back to the '90s precisely to Rivest, Shamir and Wagner's paper (RSW). This paper is heavily based on the famous RSA construction and introduced the concept of**, If you can't remember how RSA works here a quick informal RSA refresher:**

*encrypt into the future*RSA Refresher |

Time lock puzzle |

##
**Verifiable Delay Functions (VDF)**

Fast forwarding 20 years Joseph Bonneau gave a really inspiring talk about Verifiable lotteries. This concept inspired by the 1981 Rabin's paper about Random Beacon conceived to avoid situation like this:

Rigged(???) lottery |

Bonneau in his talk introduced a concept of

*Verifiable Lotteries*where there is a service that regularly publishes random values which no party can predict and everyone can verify. Back then he did not have an effective construction in his hand but in order for his solution to work he needed that the random extraction to be slow and not parallelizable while the verification should have been immediate. He then displayed some really nice math trick from yet another paper by Dwork and Naor. The trick is as simple as beautiful:

Modular square root |

VDF stands for

**V**erifiable**D**elay**F**unction and is (as the name says) a**Function**that:- Takes
to evaluate even with**T steps****unbounded parallelism** - The output can be
**verified efficiently**

**NOT a Function**: Proof a sequential work achieves this.**NO Delay:**many example in cryptography e.g. Discrete Log**NOT Verifiable:**is obtained chaining a one way function

**Pietrzak**'s Simple Verifiable Delay Functions. Even more surprisingly both papers were based on a similar idea (the

*time lock puzzle*seen above) but solved the problem in two totally different ways! What made the

*time lock puzzle*

**NOT**being a VDF was the lack of efficient verification. And this is what was solved indipendently and differently by Wesolowski and Pietrzak. I am not going to describe these papers here because I can never do a better job then this survey paper or the trail of bits blog post (so I reccomend to read at least one of those two resources in case you want to know more about). The interesting fact is though that none of this two VDFs is clearly better than the other instead each of the one has his own strength and weakness. Recently an hybrid approach has been proposed by Wesolowski Wesolowski/Pietrzak solved this? Well it actually there are two possible solutions. The first one is to perform a

*trusted setup*(ideally via a

*multiparty computation*) and the second is to use

*class groups of imaginary quadratic number fields*. Wait what? While RSA groups are somehow common in cryptography

*class groups of imaginary quadratic number fields*are way less). They are pretty well studied in mathematic though and they were discovered by Gauss (in case you want to dig into it more there is a great blog post by Michael Straka). The tl;dr of why this class groups work in this VDF setting is that taking a negative prime integer being equals to 3 mod 4 gives a group of unkown order so compute the VDF output faster would not be possible. Incidentally enough Boneh, Bünz and Fish reuse the same trick for building efficient Accumulators (to be used in order to save space in a blockchain setup).

## Isogenies VDF

Right. We are finally to the part I am more interested in:

**isogenies VDF**:). (Brifefly) On isogenies first. An isogeny is nothing else that a non-constant algebraic map between elliptic curves, preserving the point at infinity (informally speaking is a way to "travel" from an elliptic curve to another). In the "common" elliptic curve setting we are used to multiply a point to a scalar and land to yet another point in the same curve, In the isogeny based cryptography things are a bit different, again highly informally, you instead start from a curve and end your journey to another curve (after a serious of hops). Isogeny based cryptography started to gain popularity in the last years thanks to a celebrated paper by Jao and De Feo where they built a key exchange protocol (that goes under the name of**SIDH**) based on isogenies. The key fact of SIDH is that it appears to be resistant to quantum computers and his CCA version (SIKE) is a serious contendant for the Post-Quantum Cryptography standardization. But what about VDF ? Well it turns out that we can use isogenies to build a really efficient and elegant VDF. This is what we have shown in our paper:**. In a nutshell we force the prover to perform a long walk between curves (the length of the walk is directly proportional to the time parameter T) and we employ pairings to solve the fast verification (the pairing operation is not tight to the time parameter T):***Verifiable Delay Functions from Supersingular Isogenies and Pairings*Isogenies VDF |

This brings to a BLS's style equality. Curiosly enough the use of pairing will

*invalidate the quantum resistance*brought by isogenies to the VDF. I will cover extensively isogenies VDF in my next blog post but let's spend another couple of words about it. What advantage would it bring over the existing VDFs? The first thing that is not a real advantage but it is evident is that it employs a totally different primitive than the other 2 VDFs. Isogenies is an emergent standard tool in cryptography becoming everyday more popular that lies on top of elliptic curves and algebraic geometry. This is already a good point because it doesn't require people to embark on new study journey and makes code/tooling reusable. The other aspect to take in consideration here is the need of trusted setup. As Wesolowski/Pietrzak's with RSA group the isogenies VDF currently needs a trusted setup but this is not a game over story. Indeed if someone will be able to find an algorithm to generate random supersingular curves in a way that does not reveal their endomorphism ring (and this is not totally unlikely) the requirement of the trusted group will be lost. Last thing I will mention for now (again more details in the next blog post) is that the isogenies VDF is also a natural VRF (this is inherited by being a generalization of the BLS signature). If you want to play with isogenies VDF you can find some Sage code in https://github.com/isogenies-vdf/isogenies-vdf-sage (kudos to Simon Masson).
I will
end up this section with a table that compares the existing VDFs that
comes directly from the paper:

## VDF's applications

So now that we know that a VDF constructions exists what can we do with
that? Good question! Well my hope is that the answer will finally make
you believe the title of this blog post was not so cheese afterall. But lets step back for last time and let's come back to our

*Verified Lotteries***and distributed random generation.****A tipical solution to this problem is to have something called***reveal and commit*:Reveal and Commit |

In this scenario any (honest) partecipant to the distributed randomness will generate a random value r and will commit it to a

*. The final random value is obtained XORing all the values. It is not so hard to spot a fallacy here. Indeed the last partecipant, lets call her Zoe, will have a clear advantage over the other and can indeed cast a value at her own advantage, rigging the output. But at this point VDFs come to the rescue:***public bullettin board**Reveal and Commit +VDF |

Indeed it is enough to pipe the outcome of the

*through a VDF. Assuming the VDF time value is long enough Zoe will not have anymore the time to try to cheat. E.g. if the random beacon will output one random value every hour it is enough to set the VDF time T to 1 hour. In this way Zoe doesn't have control on the output before to commit her contribution. Well you know what? I just described part of the Etherum 2.0 architecture!! Indeed you can reuse this really simple concept to try to replace one of the biggest plagues associated to the blockchains:***public bullettin board****Proof of Work.**It is well known that in order to keep all these blockchains up and running (Bitcoin & co) an incredible amount of electricity is needed:https://www.newsbtc.com/2019/03/14/bitcoins-energy-consumption-equalled-that-of-hungary-in-2018/ |

Can we do any better?

**WE HAVE TO!**

This is what Etherum 2.0 and other blockchains related solution are experimenting with. In the case of Etherum 2.0 they plan to go with some form of Proof of stake + VDF. You can read the full idea here. You can also see Justin Ðrake explaining his full VDF plan in here. In a nutshell while is true that you can't speed up the VDF computation with parallelization it has to be clear how fast you can go with a single operation (modular squaring in the Etherum 2.0 case). For this reason they plan to build some ASICSs as clearly explained in this blog post investing as much as

**15M $ in research**. Etherum 2.0 seems has chosen to go with**Wesolowski's VDF plus RSA groups**(you can also see how they plan to solve the trusted setup with a multiparty cerimony in this video). A totally different choice has been made by Chia Network. In their case they still plan to use VDF but they plan to combine it with Proof of Space and using**Wesolowski's VDF with class groups**! The is an ongoing competition with a 100k price (currently in phase 2) where there is an attempt to speed up as much as possible the class group single operation. But this is just the start. Currently there are several blockchain projects evaluating VDF:VDFs have been known for 8 months only (3 independent papers published in June 2018). Now 10 blockchain projects are looking into them:@ethereum@MineFilecoin@ChiaNetworkInc@SolanaLabs@tezos@cosmos@ThunderProtocol@NearProtocol@poanetwork@InjectiveLabs— Justin Ðrake (@drakefjustin) January 19, 2019

## Conclusions

Well this post became kind of long. I will turn the focus specifically on the isogenies VDF in the next post of the series.## That's all folks! For more Crypto stuff follow me on Twitter.

*Antonio Sanso (reporting on joint work with Luca De Feo, Simon Masson, Christophe Petit ).*

## Comments