# Ethereum 2.0 randomness by Justin Drake (Devcon4)

- Speakers: [Justin Drake](https://streameth.org/speakers/justin-drake)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2019-10-09
- Duration: 33:53
- Topics: blockchain, smart contracts, distributed ledger, Science & Technology
- Watch: https://streameth.org/watch/yt-rUOBPu4W28c
- YouTube: https://www.youtube.com/watch?v=rUOBPu4W28c

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/4/ethereum-20-randomness

Justin Drake talks about the randomness behind Ethereum 2.0 using a Verifiable Delay Function.

Speaker(s): Justin Drake
Skill level: Intermediate
Track: Consensus layer
Keywords: eth2, updates, sharding

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 4 was held in Prague, Czech Republic on Oct 30 - Nov 2, 2018.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

[Music] okay thank you if areum 2.0 randomness using a verifiable delay function so I'm gonna speak about how to build a randomness beacon using a new primitive called the vdf and then I'm going to explain how to build the vdf the cryptography that goes behind it and the hardware the supporting hardware there should be some time for questions at the end the mics are here okay so let's get started with the randomness beacon so we use the randomness to different places we use it at the consensus layer in the beacon chain and basically we're doing secure sampling of validators we have this huge pool of validators each with 32 Eve that could be a hundred thousand or even millions of validators and we're basically sampling what we call leaders and committees and that's part of the the process of fum 2.0 in addition to using it at the consensus layer we can also expose it in the shards at the application layer so through an up code in the film 2.0 you should be able to have totally unbiased able randomness as a core primitive in the virtual machine and so that should be useful for lotteries and gambling and gaming and all sorts of a verifications so what are the goals for the randomness beacon we want it to be unpredictable of course we want it to be unbiased able and it turns out that's much more difficult to do and we also want it to be unstoppable and I'll talk more about that later so there's basically two classical families of randomness beacons there's beacons based on commit reveal for example Randall and these randomness beacons have an attack which is called the last revealer attack so you have an ordered list of participants and then when you're about to use the randomness the last participant can either reveal or not reveal and therefore bias the randomness and then you have approaches such as the the Definity construction which is based on threshold cryptography and these basically require a certain threshold of online participants to create the next random number and so if you don't have enough online participants the randomness beacon stalls and in the case of the affinity that just stops the whole blockchain so to give a bit more context on this last condition one of the design goals of a film 2.0 is to survive world war 3 so we're assuming that 80% of the nodes could go offline and we still want the system to run so let me briefly explain how Randol works because we're going to be building upon it so in R and out you have a random network about 17 minutes and that's a hundred and twenty eight slots each slot is eight seconds basically in the beacon chain and in each slot you have a beacon proposer the beacon proposer is invited to create a block and basically reveal a secret that they've committed to in the past so the first beacon proposer reveals the secret secret which is like local entropy and it contributes to this pool of entropy through the random mix so we have the the next revealer that's mixed in using the XOR sign you know it's okay if some proposals don't show up and don't reveal we just move on and then once we want to use the randomness for example at the very end of the epoch at slot 128 this is where the problems start coming up because the last revealer already knows all the previous actions of the the previous proposals and so they have a choice that can either stay put and not reveal or reveal the secret and effectively they can choose between two random numbers and they'll choose whichever is most favorable to them and that opens the door to various attacks okay so we have this new cryptographic primitive which is very recent just a few months old and it's vdf so the function part of it is very simple just means that you have an input and for every input you have a unique output and if you want you can think of it as a hash function there's a second parameter which is the difficulty so the difficulty specifies the amount of sequential work that needs to be done in order to compute the output so we're talking about inherently sequential computation which takes time and this is whether the delay part of EDF comes in and then we have a second output which is the proof and this is where the verifiable part comes in basically once you've done the computation and you have the output you can also produce a proof and give the proof to others and convince them that the output corresponds to the input immediately without having to do all the sequential work okay so this is the gist of the construction we have two parts we have the random mixing period which is one epoch and that produces a bias of all random mix and then you feed in the random mix into your vdf the vdf is going to take time to compute at least one Airpark of guarantee delay and then on the other side the output is going to be your own bias of all randomness okay so this is briefly the the safety argument why does this produce on bias of all randomness so if you look at one given epoch you will have at least one on this proposer and the reason is because we have a hundred and twenty eight blocks and we have an honesty assumption and the liveness assumption which says that with very high probability we'll have the at least one and if you look at the last on this proposer that will be the point after which everything is predictable by the attacker so the attacker can try and bill the various around our mixes given his local entropy and he can start feeding it into the vdf as soon as possible but the vdf is going to give you a guaranteed delay of one epoch which means that all the outputs you know will be produced after the end of the randall epoch and it will be too late to try and bias the randomness because every action that has been made is now binding the the blockchain has has moved forward okay so in order to get this guaranteed delay we are making a safety assumption which is rooted in the hardware and specifically we want to prevent an attacker even an attacker with a huge budget to be able to build specialized hardware which is significantly faster than what can be done on the commodity hardware so the speed at which you compute the vdf the function is going to depend on the hole that you have and basically we want the good guys to be not too bad relative to the bad guys and in particular we have this Emacs protocol parameter the maximum speed advantage that an attacker can have and for example we can set it to ten and the strategy that the firm foundation is taking is actually to go ahead and build the best ASIC that we can and give it away to the world so that the the the baseline for the commodity hardware is actually pretty good so that we can simultaneously have a very conservative Emacs but at the same time have a reasonably small Emacs okay we also have a live Ness assumption so we need at least one person in the whole world to be running the commodity hardware and the strategy of the film foundation here is basically to build thousands of rigs and give them away to the community for free give them a way to come if in community but also beyond that for example two to two third parties and if at least one of these pieces of hardware stays online then okay so we have the commodity hardware and we have this a max assumption now it's very easy to have a guaranteed delay of one epoch all you need to do is target evaluation period of a max epochs and the attacker will only be able to shrink that down to nothing less than 1 Network and this is the the whole scheme basically so we have part 1 the random mixing process produces bias table entropy this is taken by the vdf evaluators we need at least one in the world to do that they will start the number-crunching that was going to take a bunch of time about three hours and then after three hours pops out the unbiased ball randomness and then we need a 1 a poor conclusion buffer for the randomness to come back on chain and again you know within one network we assuming that there's at least one honest participant and that participant will make sure that it's on on chain and what we do is we basically have a recursive construction so we use the strong randomness the unbiased ball randomness to reseed the next 128 proposes and also another thing that we want is we want a new random number at every epoch you know we want a reasonable reasonably fast generation of these things and so we're going to have parallel randomness beacons and they're going to be staggered in this fashion okay so that's it for the randomness beacon now let's have a look how do we actually go about instantiating vdf so the vdf they tend to be built as a basic building block around and you keep on iterating this round many many many times and so the basic building block that we have is the squaring function so you take a number you multiply it by itself that's it and then you reduce modulo n where n is an unfashionable rsn modulus so no one knows the factorization and and basically you you do multiple squarings you do t-square rings where T is going to be your time parameter and the the output is going to be X to the two to the T okay so let's go through the whole vdf scheme in one slide super simple so the output as I said is going to be X to the 3 to the T mod n and then we want to build the proof so the proof is going to be based on a challenge response scheme where a random challenge will be given to to the person wanting to build the proof and then they will build this proof with as shown and you can make it non interactive with the theorem your scheme and then the verification is just checking this equality so this equality is very fast to check it takes about 1 millisecond on a single call and it's basically two small external incisions and a multiplication so this is the scheme by Benjamin Wesolowski from June 2018 extremely nice but there is one important detail which is how do you generate the modulus we need to have an RSA modulus which no one can factor and so there's various ways to get such a modulus but the the preferred approach that we're looking into is having an RSA ceremony so this is similar to what z cash did with the powers of tau so you have a bunch of participants for example 1,000 participants and they're going to participate in what's called a multi-party computation and you need just one of them to be honest in order for the output which is a 2,000 bit RSA modulus to be unfactored izybelle bye-bye everyone and you know just to speed things up we could have a trustless coordinator in the middle as shown so the team that is working on the multi-party computation is Leggero they're experts in MPC's and they're from a couple universities and this is these are like the parameters of the the ideal multi-party computation that the building so we're looking to have a thousand participants which is much bigger than the Z cache that they only had 88 participants I believe we're looking to produce a modulus of size 2,000 bits its L minus 1 maliciously secured which means that you only need one honest participant to be there one of the things which might be a bit tricky is it's a synchronous thing so everyone needs to be online at the same time to participate the good news is that it's only a one-time thing a one-time setup and it shouldn't last too long it should last about 10 minutes and part of the reason why it's so short is because they got it down to just 20 rounds of communication okay so now the the last piece of the puzzle and the vdf hardware so right now we're working with universities around the world that specialize in hardware implementation of modular multiplication and they have various candidate circuits and some of them are extremely fast and based on the circuits that they've presented this is what we believe we can achieve so we can achieve a latency of 2 nanoseconds per mm bit modular squaring this is extremely extremely fast much faster than what a CPU an FPGA could do we're targeting a fairly advanced process node 16 nanometer from tsmc and the the size of the chip the diarrhea and the power are very reasonable you know 20 square millimeters 7 watts is pretty good and so we'll be taking these Asics and putting them in a rig the each rig would have a max the number of a 6 or maybe about 10 a 6 and that will lead to each machine consuming about 100 watts and the machine hopefully should look something like a Mac Mini that you just plug in the wall and it just works building hardware is expensive you know we're talking tens of millions of dollars especially that we we want to give away the rigs completely for free but I'm very proud to announce that we're making a partnership with pal coins so we've agreed on a 50/50 split on the current ongoing research and if we are going to go through with the whole project then I think that would be the the largest cross blockchain collaboration ever we also you know inviting more other blockchain projects to come in so Gi is working on vdf I know that test sauce is looking to upgrade that randomness they're more than welcome to come in Kedah know could use vdf al-quran' could use vdf the more the merrier we'll have a better ASIC at the end and every participant will have to pay less food for the ASIC so it's it's a win-win and we really encourage collaboration here one of the exciting things that we're looking to do to get the fastest possible circuit that we can is to organize an open-source Hardware competition so anyone who knows how to design a hardware circuit will be invited to design latency optimized multiple modular multiplication circuits and there will be very large cash prizes for the participants we're also doing a research between now and the competition so the competition maybe will happen mid 2019 and so right now we're looking at all the possible ways in which we could squeeze latency to get really good commodity ASIC so if you have expertise and any of these things on the right modular multiplication reduction trees compresses FinFETs please email us and today we just release this website vdf research org where you'll find tens of links maybe 3040 links and you'll be able to dig in more into into the content so just to give a little bit of perspective on on what we're building here what we're looking to build let's compare the vdf with a traditional proof of work so PDFs offer something rather unique which is unbiased world leader election but they're also much less costly than the proof of work so in terms of the energy expenditure it's about ten thousand times less energy than proof of work and in terms of hardware proof of work right now requires about 10 million GPUs for a theorem whereas we need only a few thousand for the vdf and also in terms of protocol subsidies is very expensive you know all the hot loads need to pay a billion dollars of inflation per year to support the proof of work whereas for vdf the incentive would be fairly small about a thousand times less [Applause] okay so this is my conclusion slide and then we can take questions so if we are going to go through with this project and I really hope we do then we'll be basically breaking several world records so would have the first World War three proof unbiased herbal randomness the only construction that we know that has both the unbiased herbal aspect and the strong liveness uses PDFs we will be organizing the largest multi-party computation ever the previous record was with Z cache we would be building the the first open-source ASIC you know open-source Asics haven't really been done before so this is very exciting for me and also as I mentioned we are looking to have the the largest cross blockchain collaboration to actually build this thing as an industry-wide project okay thank you [Applause] [Music] so we have about 10 minutes of questions there's a microphones on both sides thank you for for the dock so a question about the RSA number generation ceremony can you talk a bit more about this and how is like what is the input from each participant and how is the resulting number gonna be bound to to 2048 bits okay so you want to know about the details of the the MPC so this is this is still kind of a bit of open research and somewhat beyond my field of expertise but basically every participant has a random number and then you take the random numbers from every participant and you add them in such a way that no one knows what the what the addition is and then you do by primality testing on the results so basically in a way that no one knows the the details of the secrets you you check that you're basically looking for a number that is the product of two primes and if it's not the product of two primes you do that again and again and again so you do many many rounds until you find a number that is suitable hello thank you for your talk am I right in saying that the problem with Definity that you defined was that it fails if notes go offline right so definitely has a two-thirds honest and online assumption so I made the calculations if if roughly 10 to 15% of the honest nodes go offline and some sort of catastrophic situation or even not so catastrophic situation then the deccan would stall and the whole blockchain would stall okay so I just want to challenge part of that assumption I'm not linked to Definity or anything like that you were asking us to trust three aspects here one that the signing ceremony won't generate toxic waste to that this centralized hardware will be trusted three that there's brand new set of cryptography from this year is the right thing to use rather than just trust that temps and people won't go offline simultaneously right I mean you can pick whatever trade off you want it's true that a pure software don't get to pick it you're picking it know at the end of the day this is a community decision and we're just making a suggestion here there is a trade-off you know you can either have strong liveness and hardware or you can have a pure software solution and and and and no no strong liveness I mean a lot of the infrastructure that we're building for for FM's 2.0 actually all the infrastructure is designed around strong liveness so that is not something that we want to compromise on what is totally possible is actually to just stick with Randall Randall is a is a pure software solution with no hardware but there's actually no loss in having hardware that will upgrade Randall and the reason is that there's two ways that the hardware can fail or the cryptography can fail number one the the RSA modulus is factored for example by by a quantum computer and in which case it would be it would take no time from that attacker to compute the vdf in that case we fall back on the safety of Randall in the case where all the hardware suddenly goes offline oh oh is all hacked at the same time then we instead of having a live list failure we also fall back on Randall for liveness so the vdf is a straight upgrade over Randall yeah so you mentioned about synchronicity for multi-party computation can you expand why your need a synchronous ceremony I don't have a whole question but I think you're asking why why do we need to have a synchronous and see yeah yeah simply because with the state of the art of RSA NPCs we just don't know how to make them a synchronous the the Z cache powers of tau with a synchronous and I believe this is a more the exception than the rule so the current state of the art is a synchronous so we're stuck with that the best we can do is make sure that the the duration of the MPC is as small as possible so that we don't waste people's time what's the fundamental reason for like at a high level yeah again I mean the NPC is going and beyond my my domain of expertise there will be a public paper published soon I believe by by the leave Harrow team and actually that work is based on a paper from crypto 2018 so I can point to you if you if you email me I'll point to you to the paper thank you for your presentation I have a question about the vdf so you are using the VD F which is easy to speed up using Asics right so you your VD f is easily speeded up have you considered you know like doing a competition for a VD f which would be a sick resistant if you like spending twenty million dollars on the asic maybe you can take a million dollars and try to like but differently DFS right so there are different VD f constructions and there's some VD f which are known as protovision swear instead of having an exponential gap between the prover and the verifier you only have a constant gap and one of the teams blockchain teams is called Solana they actually go in that way so they're using repeated shout 256 I believe as the vdf and in order to allow for parallel verification they have these checkpoints and then they use GPUs for the massively parallel verification and the assumption there is that you know Intel is very good at designing sha-256 instructions and what I can tell you is that I'm from the little that I know about the hardware from studying for the last few months I might be actually very surprised if Intel has an optimal implementation like initially I was I was thinking that you know modular multiplication with 4s 2008 modular modification would take maybe 10 or 20 nanoseconds now we got it down to 2 nanoseconds and there's these you know pretty fancy optimizations which I don't expect Intel to do necessarily you know you have a trade-off between latency power area and an Intel is trying to find something reasonable we only want to optimize latency hey Justin um just a quick question about about the vdf so so one of the inputs is a difficulty setting so so can you talk just a little bit about how that's calculated and maybe possibly what the implications are is there an attack vector there possibly could it be manipulated right so the the the a max assumption that I've been talking about we believe we can have it hold for at least five years so for at least five years we won't need anymore Asics and we won't need a difficulty adjustment scheme and once we have the length of the random epoch which is probably going to be something like 17 minutes and we know a Mac so for example MX equals 10 then we just set difficulty to take a hundred and seventy minutes on the commodity hardware so that's all it is in if we want to move to a more long-term solution where we want to have a dynamic difficulty adjustment where for example new hardware enters the market and we want the difficulty to go up organically we would need to have a difficulty adjustment mechanism there it does introduce some complexity so there is some trade-off there I mean I wrote an if research post on the on mitigating the main attack so I'm I would be welcome I'm happy to link it to you just one other question I say say the vdf somehow goes off the line is that um do you do you have a does that change the assumptions do you have a way to account for the fact that now the the randomness is coming from Rando yeah so so in this slide we're basically recursively using the randomness to select the next one down and if the randomness doesn't come on unchain soon enough which should not happen but let's say there's some sort exceptional condition then we just use the the blue dye as opposed to the red dye so we fall back on on ran'tao at the application layer things are actually better so the in the up code you will specify the the epoch and it will return you know I've no randomness like zero zero zero or we will give you the randomness and so you can design your application in such a way that will just retry until it eventually gets to randomness okay thank you hello is there any sort of incentive for the ones that you are interesting with the vdf a6 to maintain that they ensure to ensure that they are honest other than goodwill and that they're probably highly involved in the scene as well right so I guess we'll make sure to widely distribute the a6 and one way to do that is to just give it away for free there will be in protocol incentives so the easiest incentive to to implement is to provide a reward for the block proposer who includes the the randomness and the proof we could also directly incentivize the evaluator by giving them a reward and we do have schemes for that but there's a trade-off between basically introduces complexity and more burden on the beacon chain so I think it's reasonable you know if we have thousands of nodes of EDF rigs distributed around the world you know the foundation will run rigs exchanges will run rigs investors will run rigs and Fuji as well running rigs and we just need one of them to be online I think that's that's not too bad and the the incentivization for the blog proposes that it actually incentivizes sophisticated blog proposals to run a vdf rig themselves and maybe to overclock it just a little bit so that there'll be slightly before everyone else and they'll get the reward thank you one more question so you you suggested that the the vdf rigs would upload or would have their output inside of the block that they propose correct that the the proposers would have their vdf output inside of what they proposed and get rewarded for that because they they were submitted at would that imply that these vdf Asics or rigs are running concurrently with the validators so anyone can be a VDI evaluator you don't have to be collateralized you don't have to be a validator but in the special case where you are a validator and you want to earn a little bit more money and you are sophisticated you can run the hardware in parallel and you can try and and make it run slightly faster and you know make me cool it a bit better you know one of the things that would be cool on this question is if we could have one of the rigs and a satellite around the world you know at least we have this one no that's that's online thank you well I'm out of time I'm so sorry I'm more than happy to speak about this all day long so please come come to me after the talk thank you you