Distributed Randomness Beacons with Joseph Bonneau | a16z crypto research

Transcript

kicking it off today very happy to introduce Joe Benoit professor at NYU and also a research partner I'm here at a16z crypto many of you probably know Joe primarily as a Fearless semi-professional rock climber but believe it or not he's actually an amazing computer scientist who's done a lot of excellent work over the last decade including has been in this space for a very very long time longer than almost anybody I know on the academic side and today he's going to talk about what I know is one of his favorite topics distributed Randomness beacons so uh great yeah so the goal today is really to give an overview of the whole Space not to talk about any one protocol a lot of this is based on paper that I wrote this to my student I've enjoyed

NYU hopefully attention to an sok a systematization and knowledge paper that was Oakland so two weeks ago actually just one week ago Kevin and I were out of the open conference and Kevin's presented the work this is a much longer presentation going through a few more protocols but I'm going to keep it pretty high level try to keep it pretty much algebra free and at a conceptual level the different design strategies for how you can build a drv uh but you know give a quick background on what a what a drv is because if you haven't seen it before um it's a really old idea that a group of people want to generate a share of random value uh they might not necessarily trust each other so they

want to use some kind of Technology uh classically they would use a physical device to try and generate a Randomness that everybody can see they could use for something like a lottery um but hopefully that nobody can manipulate so dice are a very ancient technology that we still use today all the time variations of dice too it's so old of course you can find mosaics and pictures of people rolling dice there's also this claritarian device that they used in ancient Greece to actually select citizens to be representatives in in the Athenian Parliament and this device is completely forgotten the history of other there's some surviving examples but apparently you

don't even know exactly how it worked we just know that it was used for this purpose so um you know this is ancient technology it will Circle back again to have this engine and Technology it's actually so being used today but this talk of course is about replacing devices like these with some kind of cryptographic protocol um so the cryptographic abstraction that would replace all that technology is called a Randomness Beacon the idea in the abstract the ideal form is some kind of service has periodically publishes random values so in each Epoch the speaker is going to produce some new output that should be totally random unpredictable this should just go on forever so if you want to hold a lottery everybody participating could just say

well uh schedule this Beacon at some specific Epoch in the future and that will be the randomness that determines the lottery so at a high level you want to speak into output uniform Randomness if it doesn't have good uniform Randomness that's actually not really a big problem we know how to fix that cryptographically with a Randomness extractors if we have to um but you know it was a perfect Beacon it would just give us uniform Randomness from the start obviously everybody should have a consensus on what the values are if different people don't agree on what the beacon is outputting it's not very useful for a lottery um we'd like it to Output a lot of Randomness very regularly and it should be secure so attackers

shouldn't be able to predict what's going to be output by the beacon they definitely shouldn't be able to manipulate it and they should be able to block it or take the service down either so those are all kind of high level goals and I'll show you a little bit more detail on how we turn these into cryptographic definitions so uh lotteries with the obvious application they're what motivated the study of drvs and all the physical tools that you know can approximate a beacon but I want to stress there's a lot of other applications especially in the blockchain or webstery space so not just lotteries not just games which require randomness um there's a lot of important security applications like randomized auditing um so this is pretty well understood in

elections but there are a lot of other situations too we'd like to randomly audit something you can use beacons to generate cryptographic parameters randomly for example to choose the coefficients of an elliptic curve um the uh the big application that we'll you know see come up a lot is choosing leaders or choosing committees for some sort of consensus protocol so a lot of consensus protocols in the blockchain space essentially have a beacon running under the hood in some cases that's you know service that you can remove and run by itself or in some cases for example in ethereum the beacon chain exists for the consensus protocol but it will also be made available to application

developers to use if they need Randomness for their application um and then a couple of uh kind of uh more interesting ideas as far as I know haven't actually been deployed yet but are out there what you could use the beacon for one is to randomize transaction ordering as a hedge against mbv so you know you commit to a set of transactions and then based on a future Beacon value you shuffle all the transactions before executing them of course does that prevent all MAV no but it could be a useful uh it could be a useful Hedge but you can also use beacons for uh cryptographic proofs so instead of doing Fiat shimir which gives an attacker

potentially the opportunity to grind over a lot of challenge values you could have uh approver actually commit to the first step of their proof wait a little bit then sample a beacon value and use that as a challenge which would allow you to run various types of proof systems potentially at a much lower security uh much lower secure well more efficient for the same security level than if you're doing csmere and allowing the attacker to potentially grind over challenges um so that's an interesting idea I haven't seen it actually deployed but if we had a really good beacons maybe that's something that people would do more um and the goal I think one of the powerful ideas of the beacon abstraction

is that you could have just one Beacon service that ran and was really high secure and everybody uh trusted and then all of these applications could build on top of one Beacon including lots of different people doing different lotteries for different purposes could all use the same Beacon potentially rather than having to have everybody create their own Beacon which is kind of a pattern that you see with smart contracts today where a lot of different games for example build essentially their own Randomness service or Beacon into into their own application okay so a couple of approximations that have existed before Distributing Randomness we can be the main focus the simplest way to do it obviously is to just have a trust in third party

so nist actually ran a beacon for a while where they produce the output using some apparatus that was in their basement in Maryland and they just signed the result they had a lot of interesting literature about how their Randomness was generated with kind of entangled photons but of course there's no verification in any of this actually happened at the end of the day you're just trusting is to do this so obviously not not something that we'd like to do not an assumption that we'd like to make the one centralized party is behaving correctly um there's physical displays of Randomness uh that should say physical randomness.public Randomness all of these are public Randomness but things like roulette wheels dies and bingo

Wheels um those are still pretty commonly used in state lotteries uh partly because they make really good TV um well at least they make better TV than uh Geographic protocols here um maybe you know that's something we could turn to the production staff and ask how we can make a more interesting to watch but anyway those don't give you any cryptographic verifiability manipulating those is should be something that a good magician is able to do um everybody's seen a magic show where obviously magicians can you know pretend to be choosing a card randomly and they they're choosing a pre-selected car and they know exactly what it is it's always kind of interesting to me that everybody

knows that magicians are able to do that but they think that the uh the rotating wheel on TV when they do Mega Millions is compelling proof that the result was actually randomly chosen there seems to be a mental disconnect between people not realizing that that could be manipulated if the people running it uh weren't trustworthy although of course there's a whole auditing regime backing it up that new gives maybe similar address that magicians don't have to deal with Joe as an encyclopedic knowledge of manipulations and physical Randomness I encourage you to ask them oh yeah there's lots of good there's lots of good stories that have happened that I can chat about um okay and then the last thing which is a little bit closer maybe to a drv or

what we call what we call it in the sfk implicit beacons so I'm using data sources like asset prices prices of large large cap stocks on the stock market blockchain data uh and using that as a source of Randomness so that's actually I think a sensible thing to do we don't really have a good model for either of those sources of what security guarantees it gives you I actually think that's a good uh good project that could be worked on um this is commonly used to uh in in ethereum lots of applications just take uh take the most recent block hash as the source of randomness um so it's a decent idea and it gives

you some Randomness but we don't really have good quantification of it um so I'm not going to talk about that anymore in this talk what I am going to talk about is distributed Randomness beacons uh the goal here is that we have a multi-parting protocol so we have n participants they all contribute some entropy and somehow some output comes out of that which we'll call Omega and this talk Capital Omega um and of course we have to make some assumption about the adversary that the adversary doesn't control all of the participants and we'll see some protocols you know our honest majority and some aren't um but there has to be at least one honest participant to have any hope here um and then a bunch of common kind of

cryptographic assumptions are made crypto basically works the attacker can't break uh you know signatures things like that um probably the more limiting one is that all of the papers that we looked at the literature make a partial synchrony assumptions so nobody has uh really made a random mistake in this designed to work and it's really asynchronous Network um so that's kind of just where the literature is today but so that's the goal and parties are going to come together uh you can phrase the whole thing as an instance of MPC although these are almost all ad hoc NPC I don't know if anybody who's trying to do a trp from generic NPC and we assume uh most of the time that

this is going to happen repeatedly so the same committee maybe maybe some people will come and go and the committee will be slightly Dynamic but usually we want repeated Randomness over time so for the the partial sink grenade so this is going to be like liveness type guarantees after things settle down yeah so yeah I mean if you have totally asynchronous then you would never get like a true liveness guarantee um but uh yeah maybe that's something um okay so uh first example just kind of a warm up um so I'll try to present all the protocols at a very high level uh with these pictures of dogs that my student

Kevin really liked um and we'll see that these are the honest talks we'll see that the dishonest dog in a second um but the first example which is uh you know the the only real human protocol here uh is some version of rock paper scissors um so rock paper scissors is a really simple protocol everybody just submits an entropy contribution uh which we'll call E here and then somehow these are combined the simplest example would be just summing them all up mod K and that being the output which is basically how rock paper scissors works um so this is actually secure if you have one honest participant it's the big caveat that you need perfect synchranean

here so you need everybody to submit their entropy at exactly the same time um so why is that the case if you don't have perfect synchrony if there's any network delay uh the last participant to actually submit their entropy contribution this is the evil dog now they can look at the entropy contributions of the other participants and they can basically choose their contribution that will make the output be whatever they want it to be so they can actually force uh whatever output they want that could be some desirable out but like they actually win the lottery and this is pretty intuitive everybody knows and rock paper scissors you should be able to win every time if you can see what your opponent is

playing before you go um so you know that's why kids in the playground try and approximate perfect synchrony by counting uh you know one two three go and then getting in dispute about if they're supposed to go on three years supposed to go on shoot which comes after three um this should be uh you know should be all warm up here um as a side note one way that you can make this you know less trivially broken rather than just adding everybody's entropy contribution or doing something else that's fully linear in which case the attacker can easily Force whatever output they want um you could hash everybody's contribution and that makes it slightly harder for the attacker to get whatever

they want as an output they have to actually grind over cost of a lot but they can choose the best one in some cases that might actually be okay um for example if the output is like choosing a random committee from a large set the combinatorics might make that uh you know grinding and choosing a committee that is really good for the attacker is actually difficult um and there's also kind of a classic line of research so in the uh in the 80s there were all these papers on coin flipping or Collective coin flipping which is kind of the historical antecedent in the modern I guess idea of a drb um and they almost uh they focused a lot on this question of having a combination

function that wouldn't give too much influence to anyone participants so for example you could take a majority like if you're generating one random bit you could have all the participants contribute around a bit and then output zero or one based on the majority of the bits that were actually submitted and that way even if you're the last participant to go you probably won't actually be able to influence the output at that point um so there's various other kind of tree based constructions that limit how much influence the last contributor actually has but there's also like a normal or bound that the last contributor will have a lot of influence so you know if there's any participants they have to have at least probability

one over n is flipping uh the output if you're just outputting a zero or a one bit so probably more biased and we're really willing to tolerate in practice so this is sort of a deadline of research that I think people aren't thinking about too much anymore that's for like a worst case ordering that people go in right yeah okay so uh moving past rock paper scissors which like I said not very practical um what's actually very close to practical and it's essentially the basis of all the other drbs that I'm going to talk about is the commit reveal which is supposedly also somebody something that people have seen before but you know I'll go through it nevertheless um it's basically just adding one more

phase to the rock paper scissors idea where everybody commits to their entropy contribution before they actually reveal what it is so you have a phase one where everybody commits so your cryptographic commitment function and you have the phase two where everybody reveals what their entropy is of course that commitment function should be hiding so seeing everybody else's commitment doesn't reveal the information about what their entropy contribution is going to do and then you can combine everybody's entropy um so uh this is uh it's actually pretty close um it is it gives you a random output as long as you have at least one honest participant um the only flaw is that if you have

malicious participant who's the last one to reveal so they can see everybody else's entropy contribution in phase two they can then sort of mentally simulate the rest of the protocol and say if I do reveal this is what the output will be and if they don't like it they can just abort or withhold their entity contribution and then the protocol won't finish nobody else will know what their entropy contribution was so they can't compute what the output would have been so this gives them one bit of bias they can basically choose you know keep the current output as it is or force a restart of the protocol and they'll get a new random output and maybe they can do this multiple times or the other participants sort of get tired of them and kick them out or take some other

action um I guess the alternative version is you could have the output be well defined even in the absence of at least one value like you write the sum right you take the sum of whatever you had and so then you'd only be choosing between like two different outcomes right yes you're saying happy well defined even if somebody doesn't contribute um well I mean I guess some protocols kind of do work that way that they can recover from somebody dropping out but you sort of you want everybody's contribution to influence the final result right uh otherwise I guess I'm not totally sure well I'm

just like you write something like that some over the I is the output right right obviously you're saying like it couldn't be the sum over the ones you know about yeah so that still gives bias though yeah but there's two choices at that point right that you're picking between right I see yeah you're not gonna have this like repeated abortion yeah the problem though is that if you have a coalition of malicious participants do you have like a malicious participants to have two Decay choices and right um yeah so they'll they can choose whichever subset to withhold to give the best result okay so uh basically all the other drps I'm going to talk about you can sort of think of all of them as patches to this last reviewer attack and commitment field so

hopefully everybody feels good in the community reveal because everything else will be an extension that tries to fix this last tribular attack um so get to the other protocols I'll just kind of comment on definitions I think one of the key things we found when we were doing the survey is that nobody read on the definitions there aren't standard definitions so we've tried to generalize all the definitions in the literature into kind of a framework that captured everybody's definitions um and we came up with three uh kind of universal properties and all the other a lot of people to find other variations but uh in the end we convinced ourselves that every other property dropped out of these three so the first is unbiased ability if

attackers are in the protocol that can't produce a distinguishable bias so I'll get a little bit more into that definition on the next slide liveness so if attackers are participating they can't prevent the protocol from producing output or produce some sort of null output so the protocol should hopefully produce output even if there are attackers participating um and unpredictability means attackers can't predict any property of the Opera so it could be you know they can't produce the last bit or they can't predict the parity so our definition actually captures this notion that there's no property that they can predict um at least with better probability and randomly guessing yeah um and we make a distinction between uh

intra and predictability so in some protocols attackers might learn early within around so I'll show an example later and some other protocols if attackers are the majority in one round that allows them to predict the next couple of rounds or in some cases You can predict the beacon for the rest of time so we call that inter-end predictability when you can actually predict uh across epox so that's potentially worse although there's a lot more protocols that have this intra and predictability where some of the participants might go in the output slightly earlier than some of the others output smaller values safely relax and it only selects one of 100 they have to change the definition for

unpredictability does it have any Lambda you know security parameter oh yeah so uh you know our the definition still works we basically just say like it can't uh if attackers are in their protocol they can't predict any better than if they weren't in the protocol right so you can always predict with some like if you're predicting the leader rather than people you should always predict one out of that naively right so our definition says you can't do any better you better participating in the product um another note is that I didn't specify how many you know attackers participating in the protocol identify how many notes they actually control and that's because that's going to be different for uh different drbs some try to maintain Security even if the

attacker has an N minus one of their participants under their control some limit the attacker to only having a minority of notes ourselves we all make that clear so as far as unbiasability the way we defined it um which took some work actually to come up with the definition and captured all the different Notions you wanted our notion is that we run the beacon kind of twice in parallel once with all honest participants and one is an infiltrated run that the attacker is able to control some number of participants and again they might be a minus one or it might be some minority coalition um so each of those produces some output and then the attacker gets one of those

two outputs by coin flip and they have to make a guess good job that they actually got um and if they can actually do that with any advantage over one half and we say it's advisable and notice one of the things that's interesting about this definition um is that the attacker can actually have a private biasing strategy so they could bias it in such a way that's undetectable to anybody else without some secret key that the attacker can actually notice which would be that could potentially really interesting attack if you could uh you know bias it in a way of improvably nobody else could detect unless they knew your your secret key okay it makes sense I don't think we're

going to go too much more into definitions of that in this talk I'm happy to chat with you guys offline about some of the more fine points here all right so basically for the rest of this talk I'm going to go through a flow chart of different drv families um all kind of starting with commit reveal like I said which is vulnerable um so the simplest way to patch student reveal is if you have a clear economic model so if you have a clear economic model of what the attacker stands to gain from actually biasing the drb output then you can do a commit reveal punish protocol um so the way that works it looks a lot

like connectivity all except in addition to committing all the participants actually have to put some money on the deposit so notice we have a smart contract in the middle there uh that's capturing everybody's deposit who's participating in the protocol uh and then in the reveal phase uh you get your deposit back when you successfully Reveal Your entropy contribution okay so the two honest participants here get their deposit back uh and this malicious participant who aborted didn't reveal their interview contribution they don't get their deposit back it's captured by this or a contract in this case what happens you know does it get burned or does it goes somewhere else is going to be a similar question

all right so uh what does this really buy you well if you can stay with certainty that the attacker uh you know their utility this is a really simple case imagine you know their utilities zero with probability one minus a p or it's um you know positive value Capital uh what's probability p and that's the probability over an honestly run DRP um so if the attacker is uh trying to manipulate by repeatedly aborting the protocol so they get what they want um you know this is just really trial so they have to do uh one over P minus one runs of the protocol um from that you can directly compute how big everybody's deposit needs to be

so there's such that the attacker is not incentivized to try to manipulate so really nothing fancy going on it's kind of just saying uh you know the attacker has a certain utility and they're not going to attack if the cost of the attack is going to be bigger than that um do they usually then rerun the protocol or try to recover and still calculate an output yeah this is assuming that if anybody Awards you restart the protocol and of course the uh you know the attacker doesn't get the process back in that case so it's expensive for them to keep doing it um so maybe this is okay if you well first you know you have to be sure that you have the economic model right um and maybe this is okay if you have a

very low probability event that the attacker is trying to force um in general this is a really efficient uh you know patch to commit reveal especially if you have a smart contract that's you know they're very good at capturing deposits and not giving them back to have so it's not a surprise that this is how randow worked which is one of the first drbs that was implemented on top of ethereum has been pretty widely used it's efficient and it's very easy you know given a simple economic model to prove that this is actually secure and that the attacker is not incentivized to abort the protocol um the problem two problems really one is that you need to lock up a lot of

capital to make this work and if anybody drops out of the protocol to a honest fault if their network connection goes down or there's the gas war and they're not able to submit uh you know their contribution on the network they'll also lose their deposits so that's a risk um but probably more importantly than that it's hard in practice to really down with the attackers utility is especially if we want to design a beacon that's used for multiple purposes different attackers might have different values than those would all have to sort of be somehow reasoned about in advance which I think is difficult to do with a lot of certainty but you know this is still implemented and this is actually how the ethereum beacon chain works today

um so you know stagers actually get slashed if they um their contribution I mean you could imagine you know put a utility model you could imagine saying that's kind of really the problem of the downstream user right so you can imagine just saying like look here's the beacon we guarantee it up to sort of this value it's up to you the application designer to decide whether that's good enough for you yeah I think the question is and I don't think anyone's really worked this out this is on my future worksite is what happens if multiple lotteries are all being run on the same Peak and the attack of try and manipulate all of them at once um I guess if they're all sort of

independently hashing the result hopefully you'll get some sort of like multiplicative security and the attacker it doesn't benefit from trying to attack them all at once I think that's a difficulty like if you say it's guaranteed up to a million dollars though if multiple people are running million dollar lotteries you know in parallel using the same weekend yeah the hope would be that any one individual from their perspective they don't care that these other people might want once in a while they're losing money in my likelihood of losing money is kind of capped right right that'd be the hope yeah yeah the interesting to think about there I don't think anyone's really tried to formally reason about this Beyond sort of the very basic math that I put on the last slide

in particular I think Miranda was just a blog post I don't even think there's some an academic paper about it it's almost one of those things I think seems too too simple and obvious to believe yeah academic paper so so maybe that says something to chat more about um all right so that's to be reveal punish um so the next step in the flow chart if we're not going to go down to Economic Security route is to ask if we can make an honest majority assumption um and if you can't make an honest majority assumption um then really the only game in town that we know about is to use time-based crypto or delay based crypto which actually leads to really simple

and kind of efficient protocol so notice there's two malicious dogs in office more than the dishonest majority model is there a like impossibility result that time-based crypto is necessary not directly in the case of drvs but there are some generic NPC and possibility results that I can comply this but I don't think some of this you know I think it's I think by implications from what we know about it what's the intuition that like the commit reveal punish doesn't work if you have a like non-honest majority oh it does yeah so um so maybe that wasn't clear

um but uh yeah I was thinking like if you have if you're in the economic world you could also do a delay-based thing where you could do community punish but you know at this point we're out of Economic Security oh I still want a dishonest majority then the only thing that works yeah yeah um okay so uh the simplest example is unicorn uh and it's really really simple it's it's kind of just reveal or contribute there's no commitment at all so all the participants just publish their entropy contribution directly again no commitment you reveal exactly what you're doing um and then you uh combine all these

together and you run them through a delay function so this is uh and then um in modern news this would be a PDF at the time this is proposed the pseudocorn they had kind of a pseudo-bdf called sloth um but the idea is that this delay function is slow to compute um and in the case of a vdf you've got efficient verification kind of as a bonus so why does this work let's say that you have one malicious supports this event and it's the last one to choose their entropy contribution year um they can try to think about you know what would happen if I choose a specific entropy contribution um but actually combining all the other entropy contributions with this you know

possible choice and running it through the delay function they don't have enough time to actually evaluate the delay function before some deadline that protocol imposes that they have to actually publish um so the the benefit um really why the delayed function is powerful is that it ensures that the attacker can't uh they can't compute the result fast enough to actually decide whether or not this is a good choice in fact for any choice that they would try to think about um they can't simulate the rest of the protocol fast enough to choose whether that's a good choice for them or not so again really really simple protocol it's only one phase everybody just

contributes a value you know you collect them all together and run them to do the delay function and that's it um the only real kind of downside of this is that the delay function has to be computed every time so there's a variant that was recently published by me and students the b in this case is me um and uh so we called it biporn because it's kind of a variant of unicorn but with two possibilities um and the idea of bicorn it works more like commit reveal so there is a commit phase followed by a reveal phase and if everybody reveals so if every participant is honest then you

get the result right away there's no delay function but if any number actually is participants or dishonest don't actually you know reveal their committed value then you can still run a delay function and get the result and the the this uses time commitment so that we use a special time commitment it's really ad hoc to this application but the cool thing is that there's a homomorphism in the time commitment so that you can add all the time commitments together and just open once so there's only one delay function no matter how many participants there are um and it also guarantees that in the optimistic case or the pessimistic case

you get the same result every time so there's no benefit to the attacker of forcing the protocol into the pessimistic case all they can do is slow things down but the result will be the same uh in any case and of course they can apply punishments here so you can kind of uh you can combine with some ideas from communicable punish and say you know if the attacker forces the protocol and the pessimistic case they sacrifice the deposit but they can't actually manipulate the randomness they will just slow it down and kind of annoy everybody just to clarify so there's some function not the vdf which Aggregates the C sub I's and gives some random output yeah it's the last time like the lay function was actually giving you the randomness back right whereas here the rant the vdf is just to get those CI just to get the

input yeah the rent the delay function is not really giving you Randomness it's a deterministic function um it's just kind of you know re-randomizing um and that's true in both cases but it is true that the delay function in this case is not exactly a vdf but at core it's also repeated squaring mod n so it's basically the same uh the same geographical slope function but the inputs and outputs are slightly different I mean you could always like basically make it random well I guess it depends if you're comfortable with random local assumptions and that kind of thing yeah but even that I mean it's I guess it depends what you mean by random but it has to be a deterministic function so that everybody gets the same

that's all right I guess like there's no extra uh there's no extra entropy coming in through um through the delay function um I mean I think Brent is saying in the comments uh it's a hash function vdf is the hash function which takes a long time to compute I think that's yeah exactly right um yeah and your construction does it work for any video for is it no yeah so it really only works for repeats wearing a group of unknown order um because it's not it's not generic across PDFs it's kind of building this special time right

um okay so in general for uh no for unicorn and for by corn they're really efficient they allow flexible participation and there's no setups of different group of people can show up in every Epoch uh and they work with a dishonest majority that's probably the most important thing that you only need one honest participant and they always finish um so it's impossible to block these protocols um so they almost have everything that you want but really the only two downsides one is just the Practical requirement that someone has to be around to compute this PDF um and the vdf can slow down that has to take some minimum time by Design so it

slows the protocol down a bit um and there's also this intra Epoch intra-epoc predictability problem if the attacker has a faster VDS uh evaluation circuit than everybody else they can learn their results early and that's kind of just an inherent limitation of these protocols so that again they can't manipulate that they can potentially learn the results before everybody else and that means that if you're an application building on top of this you have to sort of assume the output might be public you'd have to say stop collecting bets or stop allowing people to move in a game or something like that before you actually know what the the outcome is yourself um all right uh so that's the delay

based drbs um and these are on the roadmap um to be added to ethereum with the main root PDF which they've been working on so the goal is to uh at some point add these to the beacon chain I mean again uh it's kind of they're kind of going to do it in combination so they're still going to do a commit reveal punish style thing but then they're going to add they're going to add a DDS on top and the goal is that they still have some economic security argument even if the VDS completely collapses and the attacker can compute it simply somehow okay so uh moving down the flow chart everything else will be in an honest

majority model um the next question is if you have a static participant set so if you have the same participants running uh you know for many many runs um and if you do there's a family of pretty efficient protocols that are what I call pseudo-random drps and the reason is that uh they rely pretty heavily on a setup um the setup is really just some distributed key Generation Um so the output is that there's some shared public key uh it's essentially a secret shared vrf key and all of the participants have one share and you've set it up so that

actually Computing this vrf requires T out of n participants to uh to cooperate um so there's uh distributed setup a dkg this could be centralized too although I don't think that's proposed quite as often um the important thing is that the setup uh itself has to be at drv um so you're basically running sort of one expensive drb to get this key and then you can run an efficient CRV for many rounds after that when I say the setup has to be a drb it should be that no participant can manipulate the actual public key that you get or else they could sort of manipulate to something that they've pre-computed values or something like that so you need to ensure that

uh everybody's contributing entropy to this setup and that it's not easy for any Coalition of malicious participants to manipulate the setup but once you've gotten through that which is usually kind of all the hard work here and I'm not going to get into dkgs because that's basically a whole long talk um but once you have a dkg and you have the shared key um then it's very very easy you have some input in each round that could be as simple as just you know the the round number it could be the drb output from the previous round couple of options but everybody computes a partial signature a partial vrf evaluation and you combine those and the result is

basically a vrs evaluation of that input with the shared public key so the output is deterministic in each round so there's no possibility for bias the argument for that is very straightforward all right it's once you've committed to this key there's no more entropy being contributed in each round so notice that participants here aren't contributing fresh entropy in each round they're just Computing a function of this rounded but um and that kind of makes it obvious that there's no possibility for for bias here um so that's kind of the benefit here there's a bunch of other protocols in this family one of which which is cool a strobe which does uh

kind of uh uses threshold of RSA one of the ends in that long author list is our own not sure which end actually in fact we should put her on this spot and see if you could actually recite every one of those author names this is a very long list um but uh strobe basically does this with uh generating a threshold RSA key between all the participants and the nice thing about strobe is that you can actually run the protocol backwards so if you have a current output you can generate all the passive outputs from that very efficiently which is nice um but I kind of I guess I jumped the more well-known one which is d-rand or is also what dfinity uses which is threshold PLS signatures

so that's uh I'll I'll talk about that more on the next slide but that's kind of the simplest and most efficient way to do it is threshold BLS is really elegant and efficient and there's a couple of other protocols that use Schnur they use kind of a similar thing to BLS that doesn't require a curve of pairings I like that name a lot too because they call it low drb and glow is actually the author acronym um that was they were lucky that their names worked out that way um so on the topic of drand um this is it's actually I think the only cryptographic drb that runs that isn't specifically tied to a blockchain project that I know about

um so uh that's out of date it's obviously uh oh no yeah it's it's 11 out of 18 I think maybe it's not 11. those numbers are out of date because we can see the 18 current well we see 18 logos here which I think are the current participants but anyway so drams it's kind of a project that a bunch of different universities and different crypto projects and a couple of other companies like cloudflare run nodes in um they have a threshold BLS key they compute a new signature every 30 seconds which gives you 256 bits of output

and it's just on the web so I was gonna just show um so they have a kind of a nice web interface with a cool animation it's not like the bits actually come in one after the other they all come at once that's just JavaScript animation but uh you know every 30 seconds it updates um so we should get a new one but anyway so uh it's really nice to have a nice API so you can build applications like blockchain or not blockchain applications on top of this um and uh it's actually been running for a couple years as far as I know it hasn't had any downtime

um so it's been kind of a reliable service um and there's a process to apply if you want to join this and add an extra node um so it's uh it's quite nice and it's again it's very efficient with that threshold BLS so again efficiency is the main goal here it's also like efficient to verify um really the the two main challenges one is generic to any honest majority drb which is that you know if you assume that t honest participants are needed for the uh to get output in a given round um any and minus t participants can actually block output um so you're sort of uh inherently

trading off the number of participants you need you know to actually be honest to make progress versus the seismic Coalition that can kill liveness for you um and you can see uh the parameters that dram shows they sort of favored um and they didn't choose them to be they didn't choose T to be 50 so it's a little bit harder to predict the output and advance than it is to block liveness um which is probably a sensible choice but that's kind of a trade-off that you need to make here um the bigger problem with kind of the simple form is that there's no recovery if there's ever a compromise so if you manage to compromise all of these nodes

in d-rand and see other Keys You can predict every output infinitely far in the future because it's a deterministic protocol at that point um so uh it might be you know prudent in practice to repeat every so often just so that the you know the window from damage is is limited all right so if we don't have a static participant set but you know different participants are coming and going in each round you can ask at least if it's a small person would have said and I'll I'll you know you'll see in a second why it needs to be small um but if you have a relatively small participant set there's this family of commit reveal recovery protocols and

I'll comment here that probably more than half the academic papers are in this family it's not clear that this is really you know the actually the most interesting use case or if it's just the one where there's the most you know different papers to write um but this is kind of the where the bulk of the papers actually work um so really simple commit reveal recover uh works like commit reveal everybody publishes a commitment but they also publish a secret shared version of their actual entropy commitment and its secret shared to all the other participants in the protocol um and they use a tool called pbss publicly verifiable secret sharing so they can prove that they've actually done the secret sharing correctly and

that guarantees that even if they go away and don't open their commitment the rest of the participants an honest majority of the rest of the participants can recover um so if everybody reveals it works just like normal payment reveal but if somebody drops out the honest participants who get together with this extra information that they got in round one they can run this pbss reconstruction function and that will allow them to reconstruct the answer key contribution of whichever nouns dropped out but again obviously there needs to be an honest majority here but they'll get the same result by recovering and missing piece of interview

so that's the idea there's a lot of different versions of this like I said which use kind of special pbss some of them amortize the ppss over multiple rounds to try to get the efficiency better some of them just dispense with the optimistic case completely and say we're just in a secret share our mentioned values and then collectively reconstruct them so there's a lot of remixes of this basic idea um the downside well I should say the the benefit is that this gives you kind of flexible participation with fresh entropy in every round the downside beyond the basic honest majority assumption is that the efficiency is not nearly as good here so these all require inspired communication

to do all of the secret sharing and if you're in the Reconstruction case I guess in the really simple kind of class that commit reveal that causes extra overhead as well so the N squared is really the teller and that's why I said you know this really this family only works if you have a small participants said it's a big participant set that inspires can kill you so if you do have a big participants set and this is the last family to present um then uh the solution here is to do some kind of committee selection before you actually run uh you know this one of these potentially best efficient protocols so in a committee based drb you have a large set here you know some honest some

malicious participants and the first step is that you just sub sample this and get some random committee for the specific round and there's a bunch of different ways to do this you could deterministically pick your committee it could be like public or secret who's on the committee um so I'll show some options on the next slide but somehow you get a committee and hopefully that committee is small enough then you can run either commit review or recover or something that's not quite sufficient maybe if it's running for a lot of epochs you can do some pseudo-random protocol but that would work kind of just as it was on the last Slide the key really is how you sort of randomly sub sample the nodes down for the specific round and

again the way I've drawn it here you know we got lucky we had two honest and one malicious node obviously it would be bad if you selected all three English is not a severe committee for the round they would be able to manipulate that the beacon for that round um so there's a bunch of different ways that you might select the committee the simplest is to just rotate um and they get more and more complicated you know you could see back in your Randomness from the previous rounds or you could do some Private Selection using vrs or even single secret leader election is kind of the most fancy modern way to do it where a lot of the research is happening now in general moving down the slide here we

have better adaptive security so round robin the attacker knows in advance who's going to be on every committee so if they can preemptively corrupt those nodes you know before specific Epoch they can manipulate the epoch they commit the randomness of some Epoch that they care about um whereas with uh you know the private leader election that even an Adaptive attacker doesn't know who to corrupt in advance and then once you have your committee there's a you know like I said there's at least two options for how you actually generate the randomness in a specific epoch so lots and lots of protocols here um not going to go over all these individually

but basically every combination of different strategies for selecting a committee and for you know selecting entropy exists and people I've written papers about so there's been a lot of really great research here um so what this gets you really is that you can have uh you know it can be scalable even if you have large number of participants you don't have to eat that N squared cost over the whole participant set um and you can do this in sort of a modular way so you can sort of drop in and out different strategies for committee selection and then different drvs once the committee actually forms and that allows you to trade off lots of different uh security parameters that you might care about the challenge here is really the

committee selection is an extra risk if you select a corrupt committee that you know you're sort of hosed for that round plus you still need to run a DRP which can uh you know have all the problems that we talked about before um so say this again on my future work but this is where ssle would really help so ssle is a hot hot research topic um that really makes this video based approach better um and we still don't have you know I think we still haven't hit the limits of really good efficient ssod protocols so I think that we're going to have I hope that we're going to have better protocols in a couple years than we have today

um so lots of combinations are possible I mentioned some of these already you can sort of combine the idea of punishment in a lot of these protocols to punish participants to drop out to try to get better efficiency the I mentioned you know modularity for the committee based approaches there's kind of this other question of could you run multiple drbs in parallel just combine the results that's actually a little bit tricky if you do it naively whichever the last protocol to finishes it's you know it basically becomes the last contributor and can negate what the other ones did but you can actually fix this with delay functions so you can have multiple drps run even if they're not guaranteed to finish it at the same time if you have a long enough delay

function you can combine them securely although at that point if you're trusting a delay function uh it's not clear why you wouldn't just use unicorns but this is something that you could do um there's a lot of other practical considerations that I uh that I didn't talk about even just efficiency has a bunch of different dimensions um you know I started talking about different protocols and what the security model is but it's interesting to reason about what happens if the security model breaks so some of them for example if you get uh it's the honest majority assumption fails that just allows predicting sometimes it allows biasing so that might be you might care about how bad things break if

they do break uh as well as this issue of like recovering from some kind of temporary as well so the obvious advertisements if you want to know all the details they're in the paper there's our uh I think this is kind of a tradition with sop talks is that you show unreadable snapshot of the tables sort of justify that there's a lot of detail in the paper that's being left out at the top so the paper is online now read it um I'll see if there's a question in the chat uh oh somebody said what's SFS so Ramset Tia uses vdfs uh yep uh Karma what's ssle so single secret leader election

so it's a way to choose a leader for a round or more generally a committee for around such that the committee is not not immediately known so they can sort of stay private until they need to active and they can prove that they're on the committee so it's a really powerful primitive I think it was introduced in 2021 2020 maybe there's been a lot of papers coming out about it recently I sort of think of it as like imagine magically used vrfs and what exactly one winner yeah or exactly statements yeah um all right so uh I guess a couple of suggestions that came out of this work of areas people

should look at obviously I already beat the Trap of ssle is really powerful so that's a good good research topic um all the definitions in the current drb literature are game based well a lot of papers don't even really have security definitions that just present a protocol but mostly they're game based so there's I think it's a good project to try and have UC definitions or drbs so people haven't really taken that on yet um nobody's really proved adaptive security if most of these protocols there's kind of a missing link to Randomness extractors and I think maybe more importantly we're we haven't really proved fundamental limits uh sort of in each of these five

models for what you can achieve so it's not I don't know if it's proven that the end Square communication is inherent um to the pbss model or if that's just yeah like The Limited every protocol seems to run up against Miriam asks if you know it's inherent that you need some time-based crypto to get around an honest majority assumption that also hasn't really been directly proven so that would be a nice result um the on the engineering side I think you know vdfs are really powerful so getting those out having hardware for them you know as soon as possible as as Graham said she has been using BDS for a couple of years so it's not uh you know I've said before like PDFs and they're

not quantum computers they're not a theoretical object that doesn't exist they exist and uh you know Chia and possibly other projects are using them now but there are some engineering things we can improve like having uh you know really fast Hardware available to honest parties um and on the economic side I mentioned having a security model for implicit beacons based on asset prices or blockchain data would be really nice as well as for the commit reveal punish model um being able to reason about deposits when the attacker sort of has a more complex utility function so mostly people have said you know the attacker gains you with gains utility you with

probability P nobody's really looked at what happens if there's sort of a more complex Suite of options that give different utility to the attacker uh or maybe you have multiple attackers that get different utility and they have to sort of uh you know jointly contribute um and then the last thing I'll say is you know in addition to all the cryptographic research actually getting people to use drvs in the real world so outside is kind of crypto or what three projects it's been a long-term goal of mine for a long time so like I said you know really ancient technology people have used for a long time to generate Randomness for the a lot of the big lotteries today not just Mega

Millions and Powerball but things like the NBA draft or seating the World Cup tournament they're basically still using the ancient technology so they still do ping pong balls on TV for the NBA draft um so I think you know a key challenge would be convincing people outside the crypto space that drbs are actually better than this physical Randomness approach which is hard because it's not very intuitive people think that they can at least understand the ping pong ball model uh much better than that so kind of a long-term goal is that things like the NBA draft will actually be using cryptographic drb in the next who knows 5 10 15 years I actually think it's regressing I watched the draft this

year and it was one person in a private room doing the ping pong experiment and then reporting the results back and uh and the fans don't don't actually buy it so the fans think it's rigged every year no matter what so I tried to say like they have room babies for more convincing things the fans don't seem to believe it but maybe they would come up conspiracy theories with crypto too I mean 31 of the 32 teams lose every every year and so some of them are going to have conspiracy theories yeah um all right so that that's uh those are the slides I have prepared I'm happy to take questions on any of these um I was

what you mentioned about like how you can use this to kind of or do our bees in general to get around like fiatrimir is that something that could then you can avoid like the random Oracle model and like also how that interacts with that you see and stuff is that something people have thought about yeah I'm not sure this might be a question for Justin if this idea has really been formally written up anywhere but I've heard it proposed and it's it's pretty intuitive that if you if you just need a random Challenge and some step if you're interactive boost protocol you know you can generate that using a drb um and replace the action mirror uh yeah I guess it's like usually it comes up more in like modeling and Theory where

people complain if you're like technically saying you're in the UC but yeah so it's maybe not as practical consideration yeah it seems like I mean I guess if you like to have the drb as a black box have a strong assumption that it's not putting Randomness then yeah it seems like it could surrounding a random work I don't know I mean like is anyone really formally written about this Justin like interactive proof protocols with drps it's been mentioned in the introduction of some papers um hasn't actually been deployed to my knowledge it's actually a lot of confusion about that and after people who thought it was deployed when it hasn't been not seen it deployed yeah so people are still using

everything's being run just with Fiat Shamir non-interactive yeah it's in question two of like how much how much efficiency that body if you're doing like a roll-up proof this way right and it you know while it could make the proofs shorter um they're now spread over multiple blocks so that maybe increases some kind of latency and it's trade-offs all over the place you know the beacons might be biasable a bit and any other questions good question about the biased because that's how the bias if you use them for

leader election can you call the cascading effect to kind of slowly yeah I think you can I'm sorry I think some of the some of the proof of stake protocols trying isn't about that I think they usually like because I think like I'll go around there's like withholding attacks right where you you have the winning prf you you don't contribute again I think they sort of rely on the fact that it's hard to grind over committee selections for the next debug and actually go on rear inventory unless they're already really close to inventory so they have a whole uh combinatorial argument for why this doesn't buy the attacker that much but it is like part of their security model

all right thanks again [Applause]