Protocol Labs: Verifiable Randomness and ZKPs

Transcript

Good morning GMGM. Thank you everybody here for taking choosing [music] to spend your time at our third inaugural noon randomness and zero knowledge proofs. Um so today we'll cover what is randomness and why it's a bit tricky when it comes up you know in zks. So first things first what is randomness? Uh so if you open you know dictionary randomness is the quality of being random. Thank you.

Okay. Granted they refine it a tiny bit. The quality of being random happening done or chosen by chance rather than according to a plan. That doesn't really sound like the randomness we're used to in computer sciences, right? Um you can find other definitions like the Oxford language one that says it's the quality or state of lacking a pattern or principle of organization unpredictability and this one is more you know is closer to what we mean uh when we're talking about randomness in computer sciences that word unpredictability in particular will come up later and is quite important. Um, so now I can ask you all,

you know, is these random? Well, if you look at it and you squint a little bit, you'll be like, nah, Elan, this is not random. No way. And then you look at the second one and you're like, that looks random, you know, could be random, feels random, and then you look at the next one and you're like, nah, not random neither. The next one also again looks random but actually if you look at the exadimal representation that doesn't look random anymore right?

1 2 3 4 5 6 7 8 so ish. And then the last one definitely doesn't look random right and yet all of these things all of these bit strings have the same probability of happening at random in a random draw of that size. uh here I think we got like 37 character displayed or displayed or something. Um the chance of getting any of these five values is the exact same uh for all of them. Um so we do have a sense a notion I guess of randomness as human beings and um that has actually been like properly defined uh through

the colograph complexity. Uh so cograph complexity basically tells you something will look random if you struggle to compress it and it makes a lot of sense if you think about it. The ones that did not look random you could describe them uh you know with fewer sentences like with without saying all the numbers whereas the one that were properly random you would have to spell them out you know bit by bit to actually convey uh the final value. Um but so let's come back to the initial question. Okay, what is randomness? Um, well, it turns out there are flavors of randomness. Um, there are different kinds of randomness.

Uh, if you're generating a secret key to all all of your bitcoins or ethereums or whatsoever, you want to use secret randomness, something that is private that only you know, right? That is probably generated on a device you trust, maybe hardware wallet, maybe your own computer, something like that, right? Um, however, if you're running a lottery and somebody's going to tell you who's winning, you don't really want to trust them. Maybe they pick the number so that their friends is winning. So you in the case of public randomness when you know for casinos, lotteryies, a lot of unchained smart contract thingies, you kind of don't want to trust anybody

and you would like to see the public randomness being properly random. Um, in the real world, what they do is they pick the numbers, you know, using bowls uh in a in a big jar on TV to prove you're not cheating in the lotteryies. Uh, it's a bit trickier when it comes, you know, when we're trying to do it on chain. And that's when the notion of verifiable randomness comes in. So, uh, remember the title of my talk, right? Public verifiable randomness. Um, so public randomness is real cool because we can do lotteryies, casinos, that kind of stuff. But since you don't want to trust anybody, you really want the public auditability of it to be a thing.

And that's when verifiable randomness comes in and is basically a way of verifying that some random value has been properly generated. Properly generated means it's unpredictable and unbiased. usually uh how does that work? Well, using cool complex cryptography. We'll see some later. Um and why do we even need uh randomness? Well, turns out we need randomness for a lot of stuff. Uh so I mentioned lotteryies already in general for sorts when you want to pick people at random or something like that. Um jury selection, leader election, that kind of stuff. Um you kind of want randomness. So it's unbiased and

unpredictable. Uh same for lots of protocols in cryptography, right? Uh for signature schemes, you need nonses. Uh for gossiping, you want to randomly choose the peers you'll be gossiping to so that it disseminates uniformly in the network and so on and so on. Even for stuff like medical trials, you kind of want uh randomness. And people have actually shown recently that if you just take bad randomness for simulations, uh your simulation won't be that good. So you actually need really good randomness to do good simulation of real world stuff like physics and so on. Anyho, other reasons to want public verifiable

randomness. When a random investigation targets two people that are closely related, people will be like that doesn't look random, right? Um another reason uh consensus algorithm is leader election typically to choose who's going to mine the next block or who's going to choose the next transactions. Everybody does it in a different way. So for example, Filecoin has a leader election that uses a random beacon I'll be talking about a bit later the end whereas Ethereum has a random beacon called Randow that allows a committee of 128 nodes in the Etherum network to choose the next random value for um for leader elections.

Um so I mentioned earlier we wanted unpredictability and bias resistance uh when it comes to randomness and is quite important. Um and the question is why do we need them? So unpredictability probably is obvious so that people cannot cheat. If I'm able to predict who's going to win the lottery, what what's the winning number for example or something like that? I could tell my friends and they could cheat. Uh nobody wants that. Um same if you're um in the FCIN network and you don't want to waste resources, you could turn off your com your your you know um storage provider uh machine until you know you'll be elected and will need to do some work.

So you could not be available, not participate in the network until you need to prove you're actually participating and that would be cheating as well. Um why unbiased? Um so this one is a bit trickier. I mentioned earlier that biased Montgomery simulations can can lead to like bad outcomes in simulations of physics and stuff like that. In general, for cryptographic purposes, a small nons bias can lead to complete uh key recovery. So when you're signing a transaction on Ethereum or Bitcoin, you'll be using the ECDSA signature scheme. The ECDSA signature scheme uh is very very sensitive to bias in the nons. It's been shown that having

less than one bit of bias, so only maybe every three signatures is slightly biased or something like that can actually lead to key recovery. Uh which is pretty crazy. And um ECDSA is very close to signatures. So it is the same for all shnore like signatures. EDSA, EDDDSA, all of them are very sensitive to bias. Um, and it actually happened. Uh, so people have lost bitcoins because their nonsies were not properly random. Uh, and that was a long time ago. You'll tell me 2013, right? Well, guess what?

It kept happening. Uh, people have been generating signatures with slight bias in the randomness they were using, which led to private key recovery. Uh so that paper by uh Jacim and Nadia showed actually that all the addresses on chain that were vulnerable to nonbias were actually already empty. Um so it's unclear who's you know emptied them but there's definitely people watching for bias on chain. So be careful with bias. Um maybe you're wondering what do I mean when I'm talking about bias. So a very obvious uh bias and I'm sorry this is not noir code and this is not restlike uh um I love go so that's some go code

is when you try to generate a random integer let's say you want a random integer smaller than 107 um so you could pick a random bite this is very easy to do in most languages you have a run read or something like that in all languages that allows you to read a single random bite It's usually coming from sold on your machine or from you know your CPU. Um even though some are biased sometimes but you would read a a bite right and you'd think oh do I make it smaller than 107? Well I can just reduce it modulo 107 right and it will be smaller than 107.

Nope. This will actually bias your value in a very noticeable way. And that's the bi the kind of bias we're talking to when about when we do that because 256 uh possible values for one bite do not map perfectly to 107 meaning you have 2 * 107 in 256 plus 42 possible values and these 42 possible values will mean you will be a much heavier uh start of your uh you know distribution here and this is not great and that can lead to lost bitcoins and so on and so on. So we usually want to avoid that. Um a way to avoid that is

to actually do rejection sampling or using very large values before doing a modular rejection. Um there is a blog post I've written about it like seven years ago online. You can check it out. Uh it's a thing. Anyway, that was all for secret or local randomness on your machine when you're, you know, reading from your PRNG one bite and trying to get a value out of it. How does it work? You know, in the decentralized case, other well, uh, a very old idea for public randomness was to create these so-called randomness beacons. Uh, you can think of it like a lighthouse, you know, that has a light on the on the

top. uh these beacons would be like emitting randomness every now and then uh for anybody to use whenever they want and that ID is actually um yeah due to Michael Rabin in 1993 so it's been around for a while you know uh and turns out till six years ago uh there weren't much many options out there to do that one option was to trust NIS which is running a random beacon except people usually don't want any single trusted party especially not NIST because NIST uh is the standardization body in the US has been known to actually try and bias randomness in cryptographic schemes in the past. Uh look up uh the dual ECDRBG

scandal out uh online and you'll see that they they were nasty you know like really trying to bias randomness there. Um so what happened is that six years ago uh with cloudflare etherum foundations and a couple of other people uh we launched a duran network called the legal entropy that is meant to be just you know there to provide public verifiable randomness for anybody to use and that thing has been ticking since then flawlessly and is actually providing the randomness used by filecoin for leader election and so the different properties are all the nice ones we might want to have for something like public randomness except it's decentralized. So it's unpredictable,

it's bias resistant and it's very feable. And that last word is super important because that's where it becomes interesting for us. So anybody can grab randomness online from Duran. It's there. It's free. It's a public good. And the entropy itself uh is actually coming from all the organizations running these dur. mentioned Cloudflare is one of them. So for example, Cloudflare is using the wall of lava lamps to seed the randomness used in the end to guarantee nobody can predict the next number stuff like that. Um so I mentioned that verifiability property multiple times now and that's because random public randomness is cool

but we don't want to trust anybody. You know, we're not in a hey trust me bro here is a random number kind of case. we're in a hey show me you know the deeds what's going on here and Duran is achieving that through um signature verification using pairings and I'm sorry you'll be asking me now hey you've been talking for 20 minutes where the zk you're like we're at right um well turns out that first things first I need to explain what is a pairing and all the signature verification using pairings block. Um so a pairing is a billinear function from two groups G1 and G2 onto

a target group GT. Um typically um G2 is like an extension field of G1 of degree 2 and G2 will be an extension fields of degree 12 of G1 as well. Uh the problem here is that these fields are typically big. So I mentioned G2 is an extension field of degree 2 of G1. So typically G1 is 254 bits or 381 uh bit field sizes meaning the 12 extension is ginormous and that is not great to do in ZK right. Um so signature verification using pairings is fairly easy. Um, you take a signature pi. Uh,

you take the message you want to verify, you sign it by just multiplying the message with your secret and producing the pairing um and producing that value out there saying, hey, that's my signature. The discrete logarithm problem uh guarantees us it's difficult to go from that multiplication back to the initial value s that is your secret and when you want to verify you take the public key which is simply your secrets time the generator of the curve g1 so sg1 here is your public key and magically if you compute the pairing of g1 the generator

on g1 together with the signature path I you got the pairing of G1 and S times the message which which is equal by billinearity to S times the pairing of G1 and M. Now if you do the same computation using the public key and the message without knowing the secret key this time um you compute the pairing of the public key s time g1 together with the message m and that pairing s g1 uh of with m is actually byarity again equal to the same value s time the pairing of g1 and m. So we have basically two very different ways of computing the same value. Uh one time we

need you know in in both cases we need to know the secret key to generate the the signatures pi and the public key. But as a as a receiver of the signature pi I can verify everything works just using the public key very easily. Um and that's exactly how dire works actually at each epoch uh it will tick you know like a clock and it will take the wrong number it's currently at. uh we'll map it to the elliptic curve we're using and we'll sign that using a threshold signature scheme so that the wall network participates and it cannot be uh biased nor predicted before the time has come. Um and then this final signature is aggregated using lrange interpolation

which is all right and gives you give us a signature pi that's just like classical threshold signatures not really the topic today. Um and so now let's come back to z case right what do we do to get randomness in noir uh well you don't generate randomness right you don't have a standard library function that tells hey random get number give me a random number that doesn't exist are inherently deterministic right um so one way that people typically do it is by using a commit reveal scheme where you would commit to some value ahead of time and then reveal it after a while or maybe if you're two people, one of them would commit to a value, the other it

would be like a multihop protocol. It's a bit annoying, not always great. But you have ways to verify that, you know, the committed value is really the one that has been revealed at the at the really matches the one that has been revealed at the end yada yada by just reashing it in ZK. That would work. It's not very practical. Um instead if you use something like dearand and verifiable randomness what you could do is you could take three public values. These are all public values. So you don't need to care too much about the private side of things here. Um and you can verify that the signature is valid and then you know because of the way signature schemes work that it could not

be predicted and could not be biased because a signature in a secure signature scheme is always uniformly distributed in the space of all possible signatures. And so what you do next to verify the randomness is just verify the signature you got from the network and then ash that value so that you get something that maps to uh to bits. Uh because I mentioned the space of possible signatures uh which is on an elliptic curve. So you you can't use that directly as bits. You need to map it to the possible bit strings you might want to use. Um and that you know works well uh works also in EVM works for most ca for for most decentralized stuff out

there because it's all public values very easy to do right well I mentioned the base fields of the curves we're typically using for pairings is very large uh so having to do arithmetic on 381 bit field elements is not quick and Um you might know you know recently uh in Noir we got the big integer library that was the noir bigam library that was added and provides um support for such large field arithmetic and so it is nowadays possible to do pairing verification in noir somewhat uh easily. So if you look it up there are

uh libraries out there to do pairing uh in noir. I mean look at these circuit sizes right this is not the fastest things out there but it's doable it works you could do it um so yeah now I guess it's time for trying to think about other solutions to do verifiable randomness in no so uh what do we do to make it faster better and so on way of doing that would be to use application specific curves in which you can embed the in which the like curve you use for your ZK system embeds the um curve we use for the different signatures. So this has been done for example for the

ZK time lock project by Timothy U or is trying to do time lock encryption using the same technology as Durand and in ZK prove that what has been encrypted is really um you know something you're interested in. Um anyway that allows you to have good performances. Uh another way of doing it is to switch to curves like BLS 12 377 on which Dcash they've been doing a lot of work and that one can be embedded into the another curve called BW67 761 and that means your arithmetic gets faster because you're you know basically a subset of the

of the curve you're working with for your ZK system but these are not great because they require changes to the existing durand uh you know protocol. Um so it could be doable but it's not great. And so in in the meantime we have no choice but to do native arithmetic in in 381 bit fields. Um so I guess my plea for you no more folks. I don't know if there are any no devs in the in the room but uh yeah there is a cool BN254 field library in Noah already except it's very limited right now. It'd be really cool to see that library being extended to support more curves maybe like pls 12 381 and also provide convenient

functions like ash to curve and uh pairing verification uh directly you know in the language could be also added as a blackbox function. I guess this is all operating on public values anyway. So um yeah and so thank you very much. I think we still have like three four minutes for questions. If you're curious about the project, uh you can to dire.lo or check out our GitHub. So Duran has been running as a public good uh for the past six years will keep running. So um you can use it for your public verifiable randomness needs next time you do a lottery. For example, it was used last year for uh doing a raffle for

defcon connect defcon tickets in Thailand onchain on a a chain. Um um but yeah, basically I hope you learned something today about um randomness and decentralized verifiable randomness and um I'll be around if you want to talk to me about threshold signatures or yeah that kind of tech. Awesome. Um any questions? Yeah.

Uh I'm not sure I understood the question was based on arbitum. >> Oh yeah, definitely. Um so in EVM land it's fairly easy to verify BN254 pairings. there is a pre-ompile for it and since the pectra upgrade of Ethereum there is also pre-ompiles for BLS 1281 and so we have code on GitHub to verify uh in solidity in EVM land uh signatures produced by DN uh and if you check the blog I think the last blo blog post was

about exactly that uh using the new pre-ompiles um and yeah so for EVM stuff it's very easy to verify for other blockchains like SUI for example or Aptos they also have some convenient functions to do BLS uh in M so that works well too so yeah it's fairly like trust chain compatible on that side on that front yeah >> all right thank you very >> [applause]