Decentralized Random Number Generation

Transcript

hello and welcome everyone this is the etherium engineering group meetup recording of the rent decentralized random number generation that we did yesterday unfortunately the live stream didn't work so I just thought I'd introduced the topic because the normally introductory piece is missing from the recording so I did the talk and the I've had a lot of people give me some feedback and also provide some helpful links and ideas and they're noted on the one of the early slides I

think I skate over that a bit one other question that was asked that didn't end up on the recording was how does my scheme relate to Justin Drake's scheme so they're covered late in the recording and so Justin's requires less communications so his one is just N squared whereas my one was three N squared however if you were doing unchain verification I've perceived that my scheme may end up using less gas so obviously we need to actually create a POC to really test that out and maybe there's a scheme which is halfway between the two which is both has less

communication and uses less gas so anyway I guess that's something that can be done at a later date so anyway please enjoy the presentation [Music] I'm just gonna wipe that very quickly all right for the record it is simple as random number generation now thank those people down the bottom there or now so why do you want to passionately use this book why would you do et cetera as random number generation if you're going to do say a lottery in fact there's a

really great video that I've seen where in back in the 80s there was a live lottery on TV and by mistake there were people who were cheating the numbers actually came up on the screen before the balls had been dug out you know how they've got the balls another thing you know it's go and then they actually appeared on the screen sitting just you know parts of it of a second before the balls actually popped out of the machine apparently I think it was wet Blatter you know when the guy that was involved in soccer apparently they heated up some of the balls so he put his hand in to pick out the ball to say hey this country has won the rights to host the soccer world cup

and so one of the balls looks Egypt or something along those right so you could just go in and find the correct ball as it were you know in this blind watery so and I've taken those two from some kind gentleman who we've seen it was presenting its death at University so there's those two examples from someone else but what great ideas you know I hear you a you you're doing something public that's supposed to be very random and yeah golly people cheat so you really do want to have try and do something that people can't see do and what other so being like in the blockchain world can be who gets to generate the next block and helps get

those block rewards so improve of work you know it's chosen by who finds the best hash but you know something like proof mistake you've got to have a way of allocating who is actually going to be the miner of the next block or the mentor of the next block so there are a couple of properties that have been really desirable to have when you've got a decentralized random number generator so you want to have it available so in other words you can even if you've got malicious nodes you can successfully complete the algorithm and so you often in our blockchain system to hear about liveliness and safety so this is the equivalent to the liveliness property so we want to say a theory and no matter

what happened to keep on going in fact there's a quote from someone saying even if you have World War 3 and 90% of the nodes are knocked out you still want a theory of to keep on cruising along and so that's why it's going to produce the next block unpredictability means that if you're some partner of some actor in the system there's no way of you understanding what the output will be or could be ahead of time and unbiased is sort of related to that but it's a bit stronger it says there's no way of influencing the output so why that might be useful is mention if imagine if Rob coke and I are going to do a coin flip thing and I said

alright well we'll flip the coin twice and if I if we get two heads then you know something will happen and maybe you know some money will exchange so that that's 25% probability but I could influence the first bit to be say 0 and not 1 then suddenly it's going to 50/50 so here's I'm entering the whole thing thinking 5050 is thinking as 2575 so that's what influencing is all about about directing into the probability of things happening isn't what you'd expect the RF liability is about being able to prove that the random GG generation process was correct and so a third party

can now verify not every algorithm needs to have that public verifiability you could have nodes in a network and as long as all the nodes themselves feel happy with the algorithm then you don't need that public verification scalability so you can have thousands of many participants in the algorithm it's a hazard scale and quantum resistant so if quantum cryptanalysis becomes reality will this algorithm still solid and secure and there's also the idea of the last actor and so the last actor problem is common to many schemes

and so the idea is you have in a dissonance in this game and if you can just sit around and wait for the first n minus one participants to participate then maybe you can do something to either generate an output of your desert in all of your choosing or maybe bias the output in some way or maybe so the last actor is a is the common fall in these algorithms and so something to think through so the first algorithm I'm going to talk about is a very basic and naive xor spear so this is pretty much as simple as you could do it so you have n participants and everyone generates a random number and

then everyone posts their random number and then you use X or X or a mathematical theme so if you have 0 X or 0 you get 0 1 X or 0 you get 1 0 X or 1 you get 1 1 X or 1 you get 0 so the number the numbers are the same you get 0 otherwise you if they're different you get one and so essentially it's a way of combining all of these numbers together to give you the Rend amount so that's a very simple way but if you're an attacker and you're the last actor then what you can do is you can wait everyone else to put in there

values and then you can say well I want this certain desired value and then you can calculate the random number you need to have and if you submit that random number that you will get the desired output so as a last actor you've been able to actually produce the art of your desire so obviously that's not very good so that means that this algorithm actually fails at everything except it is quantum resistance so another simple scheme gives commit reveal and so in the early days of proof of steak this was the scheme that was being

proposed and so the idea is you have been participants and everyone calculates the message digest of their random number they call it C so commitment and then you post your commitments and then once all the commitments have been posted then everyone reveals their random number and then you calculate the random output as the combination of all the input values so if you're an attacker and you're the last actor you watch all of those other one to come by so our zero to R n minus two and then you look at the output and

you say well do I prefer that output value or the output value that then you would have if I put my value you know you've suddenly got a choice and you're the only one with that choice no one else has got that choice because everyone else is already putting their real value so yes if you require one of the participants to participate then you know you could help the algorithm so if you don't want to hope the algorithm by not contributing then what you could do is you could say well look if you don't contribute your random number after committing it

what will find you so you know here about slashing in these algorithm so will slash you you could do that but then what happens if the reward I get is greater than the fine so maybe there's some bet maybe you know we're taught me that fraud kutenai doing something bit and if I could work out if suddenly I'm more likely to get up a million dollars then if I get five twenty thousand dollars or something so you've got to think about what the rewards are versus the fine so it's you know available assuming that you've proceed with the algorithm even as some people who've committed don't reveal and it is unpredictable so you can't actually

predict the output that you can influence it halfway through so it's not so it's unpredictable that not one biased and but it is quantum resistant so the next technique this is actually the ones that is being proposed by in a theory about by clearing foundation for a theory of 2.0 so there's this idea of a hash onion so you can think of in an onion you've got many layers and so in the middle you could have your secret in there and so what you do is you do the hashed of the secret gives you the

output that output is in hash to give another a secondary output and then you have that so you keep on hashing so you can think of commitment 0 is the hash of commitment 1 commitment 1 is the hash of commitment to and then commitment and -1 is the actual hash of the secret so it's by successive hashing is this idea of the of the hash onion and so the idea is that you could post a commitment is to see zero value and then next when you post c1 what you're doing is you know

you've less to abettors a little together by that through the graphic - so you can't you can't you can't change the values sees one that you reveal and because once you reveal see Wow the next time you go to reveal you must reveal situ you can't because there is no way of changing the cryptographic hash so you can you're essentially both walking in that commitment c0 you're walking in a stream of commitment so if you had a million hashes here then you would have a million random variable random million commitment values that are all interlinked biographic ashes

yeah and so observers can check that you have revealed the right values by just doing looking at all right the last time you revealed c0 now you've revealed c1 does the hash of c1 equals C 0 does the hash of c2 equals c1 so you can verify whether someone's done the right thing and so once you've committed to c0 you can't change the sequence so ran down I should that's how you say anyone's allowed to correct me if they want to pronounce it in a different way so this is the mechanism that if you're into is running with and so you have I

validations and you have in the overall group and c0 VI so the initial commitment that each of the validators is put somewhere that everyone can see you know so you could imagine it could be in a smart contract but it's not gonna be it's going to be in some shared store and then what happens is that you've got an initial random number value let's not worry about will we get the initial one from and you say well the H to the minus 1 so essentially give me the preimage of that so in other words where we had if it's c0 a

pre-emerge of c0 and c1 wasn't so you say all this validator VI give me the preimage of what we're up to and then we'll XOR up with the old random number look at the new random number so how I can think about it is the same grants a validator and on the validator so part of revealed up to say c2 and for my validator and he's revealed up to 63 for his validator so I XOR it in and the new random value says right it's over a pretty image of a hash so the preimage

is essentially the value that you're hashing so the image is the actual hashed value and the premium which is the value that you have yep okey-dokey yep so going on with our example so grants up to say so on mine the random number that I produce is such that it chooses grant as the next person or next entity participant to take in the algorithm and so then you reveal your next commitment back and X auditing with the random value and then maybe it that

goes from you to mark and then mark is up to say his first commitment value and then he reveals his second commitment day and so each of us participants have got different commitment values that were opted so we each are rolling back and so this is a way that you've only actually doing one calculation for the whole network rather than you know those other 1/2 of calculations being done all over the place was this one there's only one calculation happening for the whole network and everyone can verify because you could look at the as we unroll this is hatch here and you know and all the commitments to make sure that I haven't

cheated with my commitment grant hasn't read it in the nor as well but what happens if if one of the validators doesn't reveal their commitment value well in that case have a look at those if you're in research articles they're for a big lot of discussions about probabilities of people doing it or not doing it so it has people availability you know I think there is a great incentive for people to to reveal it is unpredictable because I'm going to be

able to work out the output and I'm biased in red here both been in some discussions said that actually there's a way that they're hardened the algorithm and I think yet essentially you've got a step work provided tree in the previous slide to work on exactly why so that's mainly brown how far between regular green and it's verifiable you could verify the numbers and I think it's pretty scalable and it's contour is done so it's actually pretty good so another thing that you've probably heard a lot about verifiable delayed functions and so the idea is that you want to have an

algorithm which you can run serially but you can't run in parallel and the idea is it takes a long time to calculate that only a short time to verify so if you can think of say RSA private key operations and public key operations that's a good example of the same sort of thing it's very quick to be public key slower to duplicate some of us would have been the exact the example of but you know it is it's pretty difficult and slow to do say a square root so wouldn't you have the square root of 49 coming up with seven you might go down the algorithm that's just over to the right

thing and yeah exercises are for later okay it works and so that would give you the square root where as you can imagine multiplying two numbers together gives you a result and that's pretty quick and so you can see you've got an asymmetric timing algorithm and so the goal is that you want to have the calculation versus verified to be a hundred times different and you could even perhaps chain multiple of these the years together as well that's another possibility so the algorithm that's actually been run with is dozen for square root but

it's actually a modular exponentiation sort of thing where you literally exponentiating to the square root of body and so it's your own foundation to actually work with chip manufacturers does the idea is that you want to run this algorithm as quickly as physically possible and so the thought is that if they were they find something hard with it that's pretty good and whatever in commodity chips then even an attacker that invest significantly won't be able to get too much of a speed-up such that it would break the algorithm so that's the general theory and there's the actual algorithm being used using

that paper there and so if you're in foundation of proposing actually to use the two together so so the rand out so you can imagine you've ended up with that possibly bias but pretty rock-solid a random number that were round down and then you put it into a vignette and so the idea is that you have a delay between when you put it in when it comes out so then you're not going to be able to work out the outcome is going to be because it's discipline it's going to take a physical amount of time and so the idea is you can't try and biases because you won't know what with you know if you won't know if you commit or

don't commit because it would be based on the number that produced each time that it's hard to work out ahead of time so it spoke the theory is that it should be Sullivan obviously one of the concerns is that someone will work out a faster algorithm for working up a particular once you have a register Nenshi a shooting group what in thing so the vdf with span down it seems of that it would be available which is good because anyone once they've got that number over and out could run the same algorithm using the vdf chips and in fact you could run it even on your

desktop computer is just going to take a long lot longer problems it would be unpredictable and unbiased and you could verify it and it should be scalable because anyone should be able to run algorithm and quantum resistance you notice it's in a darker shade of green and that's because the actual this modular exponentiation stuff isn't it isn't actually quantum resistant however if you did have a quantum cryptanalysis attack on what that would do is it would all back to the Rando itself oh sorry the secure weakness the security could get will pass tyranny of the R and L algorithm because it's one chained on to

the other so the red the other schemes involve secret sharing essentially and so to understand the secret sharing it's good to the as a starting point things about polynomials so an equation that's one of two it can be defined by three points so this is what 1 plus x squared plus 3x minus 3 any three of these points then we can I score and you know we could even have two

equations and the interesting thing I think about is though that you can add equations so you can add these two equations to give that the third equation but also you could add individual points of view at x equals 1 you could add y equals 1 to y equals 23 if your wife was 24 and 4 x equals 2 you could add label 7:12 is 20 to give locals 29 and so not only did you can you add the equations but for each individual point on the x range you can add the Y values to give you the Y value for the other equation so you know

that's quite powerful so Shamir came up so this is my PS in RSA so he came up with a split secret algorithm where you put in shares and you want to have you want to be able to recreate it using M of n shares and you don't want to reveal any information about the secret if you've got less than n shares to his paper and so the idea is you define an equation which is you know simple to the equations that was just saved big thing is that we do it modular a prime field and peace be you know up to 256

and if x equals zero then all of these Y X of Y will equal a zero so in other words a zero is the y-intercept so where the equation keeps the y-axis and so M is the threshold number of you know the threshold number of shares that you need to recreate the curve and so you randomly generate a zero to am once one and they've got to be in the name to 102 and P minus 1 and then you securely just to keep your shares and then any M of those shares can be used to recreate the equation which can give

you the x equals zero value which is a zero so so that maths can be used in things like this so notice a guy called Feldman who came out of the verifiable secret sharing state and the idea is that you have a generator and then they deal out essentially random public they have a problem random polynomial and then they publish so we had a you know this equation which is very much similar to this Shamir equation and then they publish these valleys fi which is G neatly they are and then secretly they

give out the next values for that equation and so they've published these essentially color commitments to do the coefficients and then what you can do is because you know that you can do the product of F 5x to the I so essentially if you can think it's a way of doing multiplication and addition using its benancio issue anyway so it's a way of publishing values and then you can check that the x value that you've been shared is correct on because you can go and then fit into this equation here so that's a way of verifiably doing the

secret cheering so Harrison came up decided what we could do is we could do a distributive key generation scheme so rather than that then there being one dealer what you can do is every one is a deal so everyone comes up with their own equation everyone shares that commitment equation publicly and then what you can do is yeah each so each party then because they can detect whether a invalid value has been published they can complain if it's invalid and then if enough parties complain then a party is essentially struggle and they're all

part of the qualified list and then each one who's part of the qualified list publishes their y values and then you get Europe you calculate the equations and then for the x equals zero that should be X there the x equals zero value you can then sum all of the Y values and so when you're summing all these Y values so essentially the a zero value for all the equations then that is your random number so everyone's independently created equations and then you're summing up the a0 values everyone's equation and so for persons skin it's available and unpredictable

there are ways of biasing however because there's no commitment scheme as such because you can say whether someone is in the polls that or not even false in that bias by output and then these people edit a commitment scheme and which remove the bias or the possibility of bias so recently another bottom this is not a theorem but the crack called affinity came up with a threshold real a scheme and there's no good there should be a dot just there which is not big display correctly that dot meaning Scott

scalar multiplication so to understand affinity skin you've got to understand DLS signatures and this is for the people who work within consensus here this is a much to bridge version of stuff that you can find in the R&D that channel there's a massive presentation Olivia are presented on this that essentially so finish your public key which is private key times the base point and to calculate a signature in this scheme you go private key times the hash of the message is the signature and then really what you really want to do is you want

to find out it if this equation holds you know essentially so the base point times the signature which is you know the public key times the hash you see on st. that's the base point times the signature equal the top of key times the hatch because the public heat times the hash what that public key was the generator times the privately and then maybe you can say well generator times the private key time time instead a lot of times the passion comes back to back so it seems really simple and the only problem with this with this this lovely simplification that I've done this over the simplification is that you can't

actually do it because you're not allowed to do multiplication of two elliptic curve points but at least nominally it gives you a bit of an idea of how it works so really what's happening is rather elliptic curve and so the public care was the generator times the private key issue their public key and you the hash of the message is actually upon pushed to a point on the curve and then you multiply by the private key that gives you the signal none of the signature and then what you do is you do something called elliptic curve pairing and that helps you map these points to a point on a different plane on a different curve actually and

so this is actually using one of blazes slaves but I think sort of covers of wealth so rather than doing this multiplication which you're not allowed to do you do this other operation which is essentially pairing and you're essentially saying we'll don't do all these signatures match so this is are you doing signature ala aggregation and then using some fancy maths which is summarized as magic and - far from it really but you know it obviously if you're a mathematician talker then you end up with this and so you can do signature aggregation so now that we've got the background

material has how does the definitive scheme actually work so you run the distributed key generation scheme for pls for a threshold scale and then each participant ends up with a private key share and then you generate the public key and you publish it your public key share may be publishing and so you can get together a group of public key by combining T of the public key shares so then you've got your public key and then to sign the value what you're doing is use something you have the random number as the input and then you sign up using your private key and the signatures can

be validated against the public key shares and then you combine these people signature pieces or signature shares into a group signature and so the group signature is the is hashed and that's the random output so the thing to think about here is that the public key shares are public and if you can accumulate from all sorts of different all of the different validators at least T of the signature shares then you can assemble the next random number so what that means is anyone can do it there's no way look because anyone has the power to create the next random number so it seems pretty good but it relies on

there's an availability problem here and so there are some people who are down here on cerium research just and right now as it worked out that 15% of the nodes a rough line then you can stall the actual algorithm so 15% doesn't sound like a really big number to me and you know for a theory we're trying to you know my nuclear war happens and we're still cruising along it doesn't really cut it does have the other properties scale abilities what still green but it's definitely not quantum resistant so I came up this scale everyone should come up with their

own decentralized random number generation so this scheme actually works on the Florida theory blockchain and in fact if within properties I think it's actually about skin so choose a large prime number everyone registers as a participant and so they generate an ephemeral keep it so notice it's not they're actually generating a new key pair that is just going to be used once and I published the public key to the blockchain and then each participant has you know their x value is calculated as their aetherium address model t so you use the if you're

in the dress as a number and then for all participants you know you've got you know generate one of those random codes for the Oceaneer secret sharing style curves where you've got a set of coefficients and you you've got a curve of order m and you calculate the Y values for each of the participants experiments so for each of the other participants you calculate the Y value and then you post the message digest of the wire value which the participants experiments and in participant it doesn't post a wire bailing out the values they drop out of the process and

they get fired and then all participants post an encrypted Y value for each of the X values so you're encrypting against the public key of each of the other participants and then again anyone who doesn't post gets fined and then what you do is you post your decryption key and so you've got the public in there you've posted encrypted values and you've posted commitments to the values and now you're posting your target piece and everyone should be able to decrypt the values and then so anyone can anyone can now decrypt the values and they can create calculate the random value is the sum from 1 to N of the zip

the x equals 0 of values the y intercept what people so if M of the attackers collude then they could decrypt the Y values and they could choose an attack which is which attacker should be called the private key so if you had a consortium of say five or five people and that was in and they could choose to not reveal and you know within the five of us they can choose which combination of us weren't going to reveal and in that way by us the output so we can't change the output completely but we can choose which of us don't reveal and hence bias the output if you had n minus M plus one colluding attackers

then you know they could withhold their keys and in that woman that way stop the algorithm so then it'd be you know I could inviolability problems so hence you like to choose em to be about half ways of half of the participants about 50% so it's really saying well it's good as long as you don't have more than 50% attackers which is probably ok in some situations but I think I think some people have talked well if you're at this you know you want to be sure that everyone you know you could be corrosion and everyone except to use an attacker so maybe for a casino this isn't good enough but most other applications make it is so it's a leaderless is this game

which is good and in the stands attacks up to mmm so I really it's about 50% but its scalability is not too good because you've got to have three times N squared post so communication so that's quite a lot so certainly missing out on the scalability and I think the unbiased maybe I should have had that in a darker green or brown because you know if you've got enough colluding with people you could so just as I was coming out with my skin just and Drake is one of the names that you've probably seen on fuel in the elbow if you're in research

post he came up with a very very simplest game but in many more some ways bill so his skin I can only be used with ECC and so your private key is actually the Weibull zero value so it's actually the widest x equals zero so it's actually the way to send and the public key is the commitment to the private key and you calculate the coefficients but using an algorithm where the hash of the private key and then you do sequential hashing to give you the other values so at all essentially you've based on the

private keys your coefficients and that should be my P as well and then so each party publishes their public key and then they published their encrypted Y values for each the x-bow knees reach the other parties and then they publish their private key and then invalid values can be challenged just like the ice game and then the output is the sum of the private keys that's actually a simple escape there's less to be posted so it's more than in suede skin rather than 3m squared so it's a better state has pretty much the same properties

so golly I've talked about a lot of different schemes and there's been a lot of rat holes of obscure maths and stuff but I think different scenarios probably call for different schemes and yes you could just rush into saying well this one's the best for my scenario I think you've got to look at each of the schemes in detail and work out what your scenario really entails before you go down the track of deploying something are there any questions okay fire

well look I think the idea of doing round ow maybe round out with the video I mean it it seems like a good initial approach because it's solving very similar things so in aetherium you've got proof of state validators and you've also got for the charting you need to work out that well there doesn't make use of working out changing stuff so it sounds like a very similar scheme yeah I think the I went you the definitive thing where you don't have that good availability I think the real problem for a blockchain system because you can imagine you all have people who are trying to bring you down and stop you

the speeds that I've got and Justin Drake that one requires some sort of shared you know knowledge and I guess a lot of little do but you know because it is in the round area someone you've got to put those commitment somewhat you know what what the latest commitment value is so yeah depth at my ah I don't know that there are lips um scalability scalability concerns for the ran down one because all you're really doing this just one entity is doing the operation and it's a really

simple operation that doesn't involve fancy mathematics in one place but completely reproduced by everyone and it's really simple are there any other questions all right well thank you everyone for coming along and have a great day