On Verifiable Delay Functions - How to Slow Burning the Planet Down (Verifiably)

Update: you can find the Part II of this series here

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 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 encrypt into the future, If you can't remember how RSA works here a quick informal RSA refresher:


RSA Refresher

But what about this RSW paper though? Well now that we master RSA the concept is pretty simple. In order to encrypt something to the future it would be enough to have the exponent e being very very (very very) big. Or as big as needed (it depends how long into the future we want to encrypt). Now it is clear that unless the message sender would know the (secret) factorization of N he needs to go through all the powering sequential steps in order to encrypt the message: From the other end if the factorization of N would be known a shortcut exists: the exponent can be reduced to e mod (phi(N))


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

Clear no? Compute the modular square root is pretty simple but sequential and the running time is logarithmically bigger a p grows. From the other end the verification is immediate. All this comes with a caveat: it turns out that the computation phase is actually parallelizable. So back to square one. At this point all was ready for the VDF idea to be finally formalized (and this happened in the cited seminal paper). But what this VDF is? Well I guess is time to introduce it finally.

VDF stands for Verifiable Delay Function and is (as the name says) a Function that:

Takes T steps to evaluate even with unbounded parallelism
The output can be verified efficiently

And so what? Why all this fuzz? Bear with me another bit an (I hope) all will be clear. It turns out that building a VDF minus any of the property listed in his name is kind of easy (credit to Ben Fish for this analogy, I have seen this in his VDF presentation):

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

From the other handit seemed that build a Function with all the required properties was not a trivial exercise. With a bit of surprise though withing 10 days of the publication of the VDF paper first Benjamin Wesolowski published his Efficient verifiable delay functions paper immediately followed by 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 independently 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 recommend 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 unknown 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 :). (Briefly) 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 contender 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: Verifiable Delay Functions from Supersingular Isogenies and Pairings. 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):

Isogenies VDF

This brings to a BLS's style equality. Curiously 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 typical solution to this problem is to have something called reveal and commit:

Reveal and Commit

In this scenario any (honest) participant to the distributed randomness will generate a random value r and will commit it to a public bullettin board. The final random value is obtained XORing all the values. It is not so hard to spot a fallacy here. Indeed the last participant, 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:


Reveal and Commit +VDF

Indeed it is enough to pipe the outcome of the public bulletin board 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: 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/

https://www.wired.com/story/bitcoin-will-burn-planet-down-how-fast/

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 ceremony 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 ).

Into the symmetry

Search This Blog