Adaptivity and Asynchrony in Distributed Key Generation with Sarah Meiklejohn | a16z crypto research

Transcript

all right welcome everyone uh to this afternoons a16z crypto research seminar we're continuing with the reunion theme uh today we've got Sarah Michael John who is always uh also a faculty fellow with us last summer great to great to have you back um she's a professor at UCL and also a senior researcher at Google and she'll tell us about additivity and asynchrony and distributed key generation Tim um and yeah thanks I'll I'm very happy to be to be really excited to be talking um it's very new well it's not very new work we worked on it for years actually as you'll find out in the talk but um these slides are very new I finished them at like 5 45 this morning um so it's going to be an exciting talk

hopefully but also kind of like who knows how it's gonna go so please do interrupt with questions um you know I don't even know how long it's going to take or anything so yeah um jump in anytime please um we'll we'll see how it goes together so yeah the main sort of application that this is all driving towards is distributed key generation um I'll spend a lot of the time talking about verifiable secret sharing which as you'll find out is a very important ingredient in distributed key Generation Um But first you know what what is distributed key generation so um the idea is that we want a set of participants to interact together in some way and in this process generate a

uh a public key and the idea is that any uh some subset of the participants here should be able to do some action um that the holder of the kind of secret key corresponding to that public key could do so like decrypt something sign something but the idea is that none of them know the pub the secret key themselves they all just know shares of the secret key okay so the kind of classical use case is what I just described so we have end parties uh and we want that some T of those parties have to collaborate have to work together to again do the action of someone who knows the secret key like decrypt something assign some message Etc so for these kind of really

classical use cases right and this was kind of how I think dkg was introduced you know like oh and in a company you know you don't want to send out some message you know unless you know some multiple employees have seen it or with servers right you want them to kind of like do things together without any one server learning everything on it on its own um and so for these kind of classical use cases we really expect to run the dkg only once right we're going to like set up our servers and we're going to run the dkg and then they can do all their threshold stuff after the fact so we don't really like care if the dkg is efficient right it can be like very slow very clunky it just doesn't matter

because we're only going to do it once anyway so in more sort of like modern applications of a dkg um this does start to matter right so one of the examples is using a dkg um for a random Beacon right so the the idea here is We Run The dkg we generate uh the threshold public key so that's the public key that like T of the participants would have to work together to do something with we then have t of the parties um produce a unique threshold signature also sometimes called like a verifiable unpredictable function and then the idea is that you can hash the unique signature and this produces Randomness and this Randomness is like all the good things you would

want it to be ready like unbiasable unpredictable and so this is like this is a nice source of Randomness and so this is kind of an idea like I would say happening in dfinity and there's also this like derand kind of random Beacon running um and yeah so that this like here you know the dkg is like an important part it's the first step in the three-step process we have to run that first step every single time we want to generate new Randomness so if we want to be generating Randomness continuously we need to be running the dkg continuously and so now this does start to become important we don't want the dkg to just be very slow um so here we're running the dkg a lot we're running it continuously so we want it to be efficient and then also we're

running it in like a harsh blockchain type environment so we want it to operate in asynchronous environments as well right we don't want all the participants to have to stay online for the whole process yes yes why do you have to run the dkg continuously for a Randomness Beacon I thought for like d-rands they've really only do it if someone joins or which is pretty rare okay maybe for derand yeah but I mean so like you're basically in in dfinity they're just like signing zero so there's no entropy in like the message that's being signed and it's a unique signature scheme so the only like thing you can do to change it is really like the public key right to get yeah

but how often are they actually changing it in in dfinity I don't know what's yeah I don't know what they're doing today so I mean I know that Jens and Victor put out this paper that's like their own proposal for a dkg and they have this like uh threshold ecdsa signing service and there they're basically like running the dkg and then producing a signature that and that is kind of like an atomic signing process so there it's also like quite important that the dkg but yeah as for their random Beacon I honestly don't know what they're doing now but for this kind of like threshold signing as a service thing they're definitely using the dkg like so yeah you want it to be like as fast

as generating a signature uh or it's never going to be that fast but but okay um so this this sort of I think uh you know trend from kind of like okay classical use cases we don't care to kind of more modern cases I think is reflected in the kind of literature that's been published on dkg right so there was kind of this original so this is um I should say asynchronous dkg protocols there are many more synchronous dkg protocols um but there was kind of this paper by Kate and Goldberg in 2010 that actually is not fully asynchronous it assumes partial synchrony for proving liveness um but then there's kind of been this like real I think flurry of activity um in very recent years I think

reflecting this kind of renewed interest in these applications and this renewed interest in making these protocols efficient by the way one thing I wanted to say and I forgot to say is um as much as we think of a dkg as a cryptographic protocol or at least I do because I'm a cryptographer um it's as much a consensus problem as well right you need all these participants to agree on what this public key is um and so that's kind of like a hint of things that I'll talk about later um that this isn't purely a cryptographic problem this is also an agreement problem yep so they think n cube is the lower bound um we can we can see at the end of the talk what we both think about that yeah um I'll remember to weave in little

hints and stuff about that um but yeah so yeah so this yeah again sort of growing interest in this space I think it's been pushed forward quite a lot recently um and so yeah here's the kind of outline that I want to give for a dkg not every dkg is gonna kind of follow this outline but this is this is the outline I want to present so most EKGs are based on secret sharing so secret sharing is a primitive in which we can kind of have one party that we call the dealer share a secret among all the other parties all right so this is like deal or share depending on what if you're the dealer or the the participants and then the idea is I'm switching now

from T to t plus one um the idea is that then if t plus one parties kind of get together and you know talk about their shares in some kind of way they can reconstruct the secret itself um and so the most famous example of secret sharing is the kind of original uh proposal uh by ADI Shamir and so the way it goes um is as follows so to deal a secret the dealer will form a random degree T polynomial um with the secret as like the constant coefficient okay so basically they say this is the zero coefficient and then they pick all the other coefficients uniformly at random then they evaluate I mean there's multiple ways you could do this but for

our purposes we'll just say that then so to party I they'll send the evaluation of this polynomial at I okay or at the ice rate of unity if you care about things like efficiency okay and so now um each party has one evaluation of this polynomial and it's a degree T polynomial so if t plus one of the parties get together then they have t plus one evaluations of a degree T polynomial and so using LaGrange interpolation they can reconstruct the polynomial and evaluate it at zero to get the secret okay so this let's let's sort of see how we can build a dkg from Secret sharing okay so the idea is that basically here

we have one party and it's running deal and so right like it's secret share thing is some polynomial that it's made up and then it's going to just as we said send evaluations to all the other parties of their index or whatever and we have all the parties do this in parallel so everyone acts as the dealer and so at the end of that process everyone has like evaluations of their assigned index from all the other polynomials so then the idea is that we basically just perform reconstruction in the exponent instead of in the clear okay so we can see that instead of right so with

reconstruct I said you share the evaluation you were given and now you just share it in the exponent okay and then um we can interpolation and evaluation of a polynomial this stuff all can happen in the exponent you know just as it can happen in the clear so we can interpolate in the exponent to recover each individual polynomial and then we can sum all the polynomials to define the kind of common polynomial which is just the sum of all the individual polynomials and then we Define the public key to be that evaluated at zero again in the exponent and and so that's the public key okay and then I hope that it's uh yeah I

hope that it's reasonably clear to see how you would then do threshold signing or decryption or something like that using all your kind of individual right because everyone still knows all their points and stuff like that makes sense I haven't said anything bad yet right I've assumed that everyone is great everyone sends all their shares everyone's Shares are good and you know that's not how things work in cryptography so um I've left out all the details I'm gonna basically continue to just leave out all the details um but obvious things that might go wrong are you know the flamingo might not get their share right and that is true possibly because you know the dealer is malicious possibly because our

network is asynchronous and things just drop um or for example you know the dealer just sends like complete garbage to the flamingo instead of nothing right and then you know how do we tell that it's complete garbage so this is why we often use um something called verifiable secret sharing instead of just plain secret sharing which means that basically the dealer is gonna like commit to all the shares ahead of time and then you can just check against the commitment if your share was good or not um so yeah that's kind of one thing that we really need for a dkg and then the other thing which I'm not really going to get into because we don't really like it um is you again this is like there's a consensus problem at the heart of this

dkg which is so in the in the previous um example we just included the contributions of every dealer in the computation of the final public key right we summed all the polynomials in the exponent and here we might not want to do that right because they're like again someone might have given us junk someone might have not given out the share and so if we include that dealer's polynomial in the public key then we can't actually do anything with that public key because we don't have the shares to do it okay so this is why there's this whole complicated complaints round in a lot of dkg protocols where basically we have to kind of like as the name suggests like

complain about different dealers and be like oh like they were bad you know they didn't give me this share and then you have to like tell everyone that and then everyone has to be like okay I I heard you and now I don't like that dealer either and so there's just a big agreement problem here about which dealers are we going to like whose polynomials are we going to include yes what are rounds if we're in an asynchronous so there is it's a great question I'm not a consensus person there's uh so Kennedy and Robin Define this notion of asynchronous rounds um and we use that one but what is that definition I don't know

um yeah sorry I don't remember but we use a well-defined notion at least yeah do these typically us like assume there's a shared bulletin board that they can post to see like what everybody posted or are they sort of running from nothing some protocols in my opinion is a um so but there's a lot of really cool papers um that mean you don't have to do it so for example we're going to end up using reliable broadcast and we're going to end up using the like dos at all protocol from two years ago um that is like the the most efficient one so yeah but usually you try to start from that if you can yeah

so basically just to summarize this kind of like dkg recipe um so each party acts as the a VSS dealer and Deals some Secret each party participates in the VSS sharing for all the other parties when they're acting as the dealer then the like consensus e question all parties agree on some set of dealers using this complaints round or whatever um and then for all those like agreed upon dealers they then reconstruct in the exponent the sum of their kind of Secrets or really like the sum of their polynomials yeah according to your experience which is the most popular VSS scheme used in practice

uh used in practice I don't know if any of them are them um no like Feldman uh Peterson these are kind of like the really classical ones um that a lot of VSS schemes are derived from anyway um so yeah they're I mean I would say yeah the fell Maybe assesses a good choice it's synchronous though um so avss is a more active space I guess I don't think there's any like clear answer there do people ever use kzg we do it seems like Ridley yeah so

um well thanks for that question and it makes us yeah makes us sound very natural um yeah that's exactly what we're gonna do so basically um you know hopefully I've convinced you that even though this talk is about dkg I'm gonna have to talk a lot about VSS because basically from this recipe you can see that VSS is like an extremely essential ingredient kind of the only ingredient aside from consensus which is also very important um and so really it seems like the best way to get a better dkg is just build a better VSS exactly what we're gonna do so um yeah I'm going to now talk about a protocol um that will have appearing in crypto

this year this is with Abram Philip yavanovic Mary Maller and gelad Stern um and this is a protocol that we call Bingo it has many adjectives it's kind of like ridiculous when we it takes up like multiple lines in the paper it's really embarrassing so it's an avss so an asynchronous verifiable secret sharing scheme it allows secrets to be packed that means that we can share f plus one Secrets um with the same complexity as it would take to share one Secret it has optimal resilience meaning n equals three f plus one f is the number of adversarial corporate parties it has N squared word complexity

um and uh constant round complexity and it allows this is the most important contribution so if you remember nothing else it allows for adaptive Corruptions um so you know we we sort of view adaptive Corruptions as equally important in some ways in an asynchronous blockchain style environment as you know any anything else right if you have a set of parties who are sort of controlling an important functionality whether it's you know some proof of stake type component a random Beacon or something like that there's going to be a lot of incentive to corrupt those parties and if the set of parties is sort of relatively stable over time then you can actually expect really that Corruptions will happen adaptively as

the protocol is running um and so having these adaptive Corruptions meant we have like new definitions of VSS termination correctness and secrecy I won't talk about those at all but they're in the paper and we worked a lot on them so I'm happy to talk about them offline yes do you support any thresholds between F and N Yes actually we do which is really exciting yes we support high threshold reconstruction or arbitrary thresholds between yeah F and 2f actually I think yeah but yeah so yeah we're very excited about that part yep what do you mean by word complexity oh even Miriam are asking a consensus questions um so yeah we it was for the camera

ready we were debating this so the idea is a word is a kind of fundamental object in a message so it's things like counters or indices and basically any cryptographic object is going to require like o of Lambda where Lambda is the security parameter words so the idea is you know message complexity is a kind of quite broad measure messages might be like really large so word complexity kind of breaks this down so if your messages are like N squared and you send N squared messages then like your word complexity will be n to The Fourth Kind of I don't know it's it turned yeah we sent like a good

20 minutes yesterday trying to pin this down and it wasn't very convincing and my answer is not very convincing as a result well because on when you were showing previous work you were also showing there oh that was for the dkg this is just the VSS for now so yeah the kind of best known vsses all have N squared word complexity as far as I know I don't think anyone has slower this is just just any other questions okay I will now attempt to tell you how Bingo works and we'll find out if I did a good job okay so the idea is um how does dealing work so the idea is that a dealer is going to uniformly sample a bivariate polynomial

and embed its secrets in um in this way okay so we have the bivariate polynomial fee and we're going to embed the secrets um as the evaluation of fee at minus K and 0. okay and why do we do this I it's hopefully it'll become sort of clear um but yeah that's what we do and then the idea is that again this is like a packed VSS so we can just sort of put in um up to like f Secrets basically um make sense and then the idea is we're going to uh I guess I should have a star next to broadcast as well right because like what does broadcast mean

um so we broadcast a commitment to this polynomial so I'm not going to talk about the commitment at all in this talk um except to just refer to it very Loosely um but yeah this the we we had to design a custom commitment for this VSS we're not just using something off the shelf um but it is like a very natural extension of kcg um this this commitment scheme uh to bivariate polynomials so it's just kind of like if you think hey kzg and then you think how would I do kzg for bivariate polynomials hopefully like you'd roughly come up with with what we have in the paper as well um and then what you do is you set these kind of

like row polynomials and column polynomials so you have Alpha I which is the evaluation of Phi X and I so X is like the the loose term okay and so that's kind of the the row here in that thing over on the right and then you have the beta polynomials which are like the corresponding column polynomials okay so it's just like fixing one I guess I shouldn't have called that X that should be a y um but yeah you're basically fixing one of the terms and then so yeah Alpha and beta are kind of the row and column univariate projections of Phi um and so it really really really importantly this means that we have this

relationship between the Alpha and the beta polynomials right that Alpha I of J is equal to Beta J of I right and hopefully it's very clear why that's true and yeah I apologize my Matrix over there doesn't reflect that like the upper triangular part is basically equal to the lower triangular part because of this property okay and then what the dealer is supposed to do is send Alpha I to I okay so the goal basically of the share protocol is for each party I to learn their Alpha I polynomial okay so there are kind of two paths by which the party can learn their polynomial so the first one is the

obvious one I guess the happy path right we say at the end of deal that the dealer sends Alpha I to party I so if they just send Alpha I to party I and it gets there then we're done right we've achieved our goal and that's that's great of course we can't just assume that's going to happen for every party again maybe the dealer is malicious maybe the network is definitely the network is asynchronous so maybe the message just gets dropped and it doesn't get there okay this is just the uh environment we're operating in but of course we are we have to assume that like some messages get through and are well formed and stuff right otherwise we would just reject this dealer's contribution and

it's not interesting so let's assume that sort of you know three of these other like birds got their polynomials okay so what that means now in particular here for like the parrot is that means that they know um all like those five evaluations of their row polynomial right they know the whole polynomial so they can evaluate it at you know one two three four and five and get the the sort of those points okay and so what they can do is send those points to the parties that they kind of correspond to right so basically they send Alpha 5 of J to party J and they say here you go this is like your

evaluation of my row polynomial and now we're going to use our super important relation between Alpha and beta what this means is that party J learns an evaluation of their column polynomial of their beta okay so they didn't know beta before no one sent it to them or anything but they can actually learn it by being sent to these points by the other parties okay so if you know the three parties who got their Alpha polynomials send them then at some point if they're given this by enough other parties then the seagull here can actually just interpolate to learn their column polynomial and so now they know right so just like

before if you get your Alpha polynomial you know all the evaluations in your row now if you get your beta polynomial you learn all the evaluations in your column and so we just do the exact same thing again right now uh the seagull here sends out those points to the relevant parties they send beta 1 of J to party J okay and then again party uh J is learning something about their Alpha polynomial right because we're just like going back and forth between the alphas and the betas and so now super crucially for like the the vulture here right they didn't know this evaluation of their Alpha polynomial because they hadn't

gotten their Alpha polynomial yet but if they get these beta evaluations from enough other parties then they can interpolate their um their Alpha polynomial and they can learn it bingo protocol s right um yeah it's whatever we're academics um so yeah so this is the other more tortured way that a party can learn their row polynomial is by the help and support of enough other non-faulty parties this is basically in a nutshell how Bingo Works um of course there's a lot of complexities that I have hidden uh from you in this talk so one of them is I

mean pretty hopefully somewhat obvious um you know parties don't just like send out evaluations they have to prove that they're correct right and they have to it's like it's more work than it sounds for the commitment right so kzg um already has this notion of evaluation binding which basically says that if I give you an evaluation then um right then like it's it has to be the right evaluation basically against a commitment here it's a little complicated because what we have is a commitment to the bivariate polynomial from that we can pretty easily derive commitments to the alpha polynomials just by doing like a DFT basically um but then when parties are sending out evaluations of their beta polynomials we

don't have like commitments to the beta polynomials so it's it's all a little awkward to be honest um and so we ended up defining a new notion of what we call interpolation binding which basically says that if you get a bunch of evaluations that all like past verification you know evaluations and proofs there's always proofs that pass verification then the polynomial that you get by eventually interpolating those points is the polynomial that was contained in the original commitment so it's like it's a little more involved um referencing the talk from this morning we prove interpolation by to prove interpolation binding we end up needing the AGM I think compared to fatini we take a much more like loose

attitude to the AGM I mean I'm I'm personally completely fine with it I think I'd rather use the AGM than like make up some knowledge of exponent assumption and use that and I I yeah I don't know I mean anyway this is a whole separate conversation um but we use the AGM and we're completely happy about it and we don't really worry um the other complexity of course is I said oh that dealer just like broadcasts that commitment um so there we use again this um does it all reliable broadcast protocol and then of course the other like huge complexity is adaptive Corruptions right and how do we deal with this um dealing with it and the dealer is not so complicated because dealing is just like an atomic process like once you've

you've either dealt or you haven't and once you so like corrupting after the fact is not super interesting but yeah um so I mean yeah for PhD students in the room who like maybe bang their heads against the wall with proof some I mean this this took us like two years to proof um it's yeah we have like so many like 40 page proofs that just like went in the garbage um I'm laughing because I can't do anything else um so yeah it this was an extremely involved proof um for like a deceptively simple looking protocol um so yeah just to like give a little insight into the process here as well

um but yeah so those are the kind of things you know that actually make this all a little difficult okay so that's sort of sharing in Bingo and that's the really like hard part um reconstruction then is hopefully like reasonably natural you know given how I said like Shamir how it works for Shamir and how it kind of works in general so if we remember you know how the secrets were embedded in the bivariate polynomial the idea is that basically um everyone can just write so no one has this like minus case polynomial um but every party can evaluate Alpha J at minus K so notably um we we can perform reconstruction for

like only one Secret at a time right so remember this was like all packed and so we shared like K Secrets uh or M Secrets at the same time so here we're like reconstructing just the case Secret um and so we share Alpha J of minus K and then like same old trick it's yeah is given enough evaluations like that we can then interpolate the beta minus K polynomial and then we can evaluate it at zero to recover the original Secret maybe I'm missing something but doesn't the dealer need to prove that this Matrix is symmetric if yes how does the dealer do it oh um there's the Matrix is is for the slides like there is no matrix it's all the dealer the driver at

polynomial so all the dealer does is provide a bivariate commitment and then you can deterministically derive the alpha commitments using like a DFT basically um so yeah there's no trust in I mean so we need a notion of like polynomial binding which says that if you commit to a polynomial then later when we all like but don't you need that this diverted polynomial satisfies this relation like uh that it's symmetric or Alpha J minus k equals beta minus KJ no I mean it's because again like these are just projections

of that polynomial so it just holds like it can't not hold right we're like deterministically deriving these things in our minds like they don't exist in any other way so they this just holds like inherently it's there's yeah there's no like trick they can pull with the bivariate commitment such that this wouldn't hold yeah did you have a question sorry mentioned this is one round or no maybe I'm I are constant rounds yeah um how many because obviously so what well I don't want to count the rounds I I thought I should do this before giving the talk but yeah I mean you need the rounds for everyone to like share their Alpha evaluations and then share their

beta evaluation so it's it's a three or four rounds or something um but constant yeah the polynomial does not need to be a symmetric polynomial is that right for this to work no the only thing the polynomial the bivariate polynomial needs to to the the alpha beta relation that's literally just like two different notations for the same number right exactly yeah we're just sort of making it up in our minds um yeah okay so then that's how we can reconstruct just like the case secret basically um something really cool I think about this protocol is that we can actually do like Advanced reconstructions so um let's sort of consider now

reconstructing across multiple sharings so multiple different dealers so um let's denote by Alpha j i the alpha polynomial that party J gets with i as the dealer um then let's so let's imagine now we want to like reconstruct the secret across you know all the different dealers um so what the parties can do basically everything's just like homomorphic right so what um what the parties can do is they can compute the kind of like acrossel dealers polynomial Alpha J which is just the sum of the individual Alpha JIS and then they can just do the exact same thing right they can share Alpha J of

minus K interpolate beta K and then evaluate beta k at zero so what this is reconstructing is actually the sum of Secrets across like all the different dealers um and notably we can do this with the exact same complexity as we could for reconstructing one secret right we're just sharing like one point basically but that point is like representing all of these different dealers does that make sense okay so yeah so basically here we're reconstructing the sum of Secrets across different sessions um and then we can also do the same thing for the batch reconstruction of multiple Secrets right so one dealer is sharing like f Secrets at a time if we want a batch reconstruct like all their

secrets we can also do that with the same complexity too okay and that's in the paper if you're curious to find more okay so that this is like again a nice feature um again if if it is easier for you to think about it if I just say like oh basically everything's just like linearly homomorphic uh then that is true and that is kind of why all this um Advanced reconstructions are possible okay so if we now try to think about how do we take Bingo and build a dkg out of it um then let's revisit our kind of like recipe that we had right so everyone acts as the VSS dealer everyone participates in the VSS sharing well this is pretty easy to substitute in we just use Bingo for those parts right so

we use the Bingo dealing protocol we use the Bingo sharing protocol um notably this idea of like reconstructing the sum of secrets in the exponent is super easy in Bingo because of this like Advanced reconstruction property that I just talked about right so um notably like reconstructing the sum of secrets in the exponent looks like just doing what I just showed you but like with G to the stuff instead of just sharing the points directly right and so this is basically plus like what this means is that we can do this by sharing one evaluation Point rather than having to share n and then everyone like figures out how to sum them themselves okay so this is like a really nice thing for the dkg specifically

and then the other kind of big thing that we do is we don't use a complaints round we don't want to use a complaints around they're complicated they're really hard to argue about so what we use is something called a vava protocol I'm not really going to talk about this because I'm one of the cryptographers in the collaboration not one of the distributed systems people so I'm not really the right person to tell you about it anyway um and I've already I think kind of like done enough throwing things at you so I'll just really briefly highlight kind of what a varber is and how we end up using it in the dkg and like kind of the path to building it and then I can try to answer questions about it or just put you in my co-authors if you're you know really want to hear more

um so what is a baba baba stands for a validated asynchronous Byzantine agreement protocol um and the idea is that it brings in this notion of external validity into an agreement protocol okay so basically we have we have the kind of like standard notion of you know termination and correctness meaning online for all non-faulty parties eventually complete the protocol um and all non-faulty parties who complete output the same value okay so in that sense it's an agreement protocol um and then we have this notion of validity though which basically says we have some external validity function check validity and uh that the value output by all of these non-faulty parties is also going to be valid

according to this external validity function so in the context of the dkg what we're after um with this validity function is we basically so remember what we're using the complaints round or the vava for we're using it to agree on a set of dealers whose contributions we're then going to use in the final public key so what we have is we have this set of dealers and then we have an Associated set of signatures and these signatures kind of come from well from any parties who say I have completed the share protocol with that dealer and I I think I have the correct shares and I am happy for their contribution to be used so the idea is that we need at least f plus one dealers

in order to be insured that we have at least one on a stealer we need then at least f plus one signatures and then we need um all those signatures to be valid right like we need them to pass verification and that's basically it okay so if we have f plus one dealers then we know that there's at least one on this dealer if we have f plus one signatures then we know that at least one honest party completed the dealing um sharing with all of these dealers um and that's what that's how we Define our validity function for the dkg any questions about this so hopefully this is like because I I don't think I'm gonna give much more of an outline of how the dkg works so basically everyone runs share everyone

does deals all at once runs share with everyone once they've uh like completed a sharing session with someone they'll um add that dealer to their set and they'll like sign off on their index or whatever and then all parties enter the vauba with their set of dealers and their set of signatures and then the vava ensures that we all agree on one set of dealers who um enough who people have signed and then with those dealers we do the whole thing I described of reconstructing the some of their secrets in the exponent make sense okay uh so in terms of how we build this Faba we draw very very heavily on a result that we had at uh policy in 2021

uh the same authors plus Ellen tobesco um and so I'll just again like really briefly like hint at the outline of how this works um so the first kind of thing we build is what we call a verifiable gather protocol um so this kind of says that um that in like that any set so well parties will have like be like this is my set this is my set and the idea is that um all of these sets any set that will pass verification and kind of that other parties will like um in some sense um has to be a super set of some common core right so there has to be some like common elements in all their sets like

some overlap um so again it's kind of like vague notion um and so we build this based on reliable broadcast then what we do is we combine verifiable gather with a kind of threshold vrf like a local notion of threshold vrf um to build a proposal election protocol so proposal election protocol says that basically if you know every party comes in with their proposal then we want a protocol to select one of those proposals uniformly around them you could also think of this as like a leader election protocol and what we actually start with is like a weak leader election protocol which means that the probability um the probabilities around like

outputting dealers are very low like we don't have a very strong guarantee um about the leader of the proposal that we're going to Output but anyway so again like very vaguely this is kind of what we build on top of um verifiable gather and then we build kind of this vulva protocol on top of this proposal election protocol um and so in this podsy paper this is called like no win hot stuff built on top of the hot stuff like consensus protocol um and so this was the outline we used again in this paper um and we were using a dkg that um basically we're using like a synchronous dkg that was a eurocrypt 2021 um in in the kind of proposal election part and so here what we're doing is really in a nutshell we're just sort of

substituting in for that like synchronous protocol that we used in um sorry for that so in the in the eurocrit paper we had like a publicly verifiable protocol so we just kind of substitute in for that PVSS bingo okay and that gives us an Adaptive proposal election protocol and then it just like magically works out that then we can build uh and adapt well it's not magic it's just that the voba then inherits the Adaptive security of the proposal election protocol as well okay so basically by just substituting in Bingo for this like old PVSS that we had we can get an adaptively secure and the

vaba is what's uh in cubed words and I'm not enough of an expert in consensus to like say you know do I think we can get that lower it certainly seems really hard to get that lower um if you look at how these protocols work but yeah that's why I kind of think and N cubed is a a natural thing to aim for and getting below it would require like radically different agreement protocols um and yeah uh seems Seems hard to me um that's for sure yeah so basically the VSS as I said like the best squared the best word complexity is N squared for the vob of the best is n cubed and so that's why the the dkg is enqueued because again the dkg is really an agreement problem and a cryptographic like the SS problem so yeah that's kind

of that's kind of it so in terms of our sort of work um so we we matched the kind of best known word complexity and round complexity um yeah we have these high threshold reconstructions which um we're very happy about um because earlier versions didn't and it was another like torture path to get there very natural in the end um so yeah we can support arbitrary reconstruction reconstruction thresholds um and then yeah I mean the main downsides well apparently some people think that using the AGM is a downside so um there you go but obviously you can see that yes so we are the first adaptive Pro the first protocol to be proved adaptively secure but um you can see the the inverse in that like trusted

setup column right so because we're using kzg we do use a kzg setup um I will say Mary was like incredibly careful to make sure that we could reuse the like kcg ceremony um so we can just reuse their trusted setup we don't need like something new for the bivariate polynomial that was another like six months of work um but yeah but if you think that's a problem um then you can see there's kind of like an open question here of you know can we get adaptive security without uh some kind of trusted setup but at least for us we can bootstrap off of existing setup ceremonies which we're pretty happy to leave it at um so yeah and I should say um because there was like the so this previous work

um you know we were pretty happy with that too but the big caveat there was that it um the secret key was a group element rather than a field element for the dkg so for stuff like BLS it wasn't going to work um here we also get around that and our secret key is the field element so this is compatible with BLS yep does the egm I'm sorry the AGM comes from the commitments right from the polynomial commitments or you needed it that was the place where you said yes so the only place we actually do end up using the AGM is to prove interpolation binding for our kzg like bivariate polynomial what are the I don't remember what are the actual assumptions that the original commitments themselves for their normal binary qsdh oh okay okay there's no way to get to like usdh or

something from I mean so to be honest okay if we're going to talk about assumptions so the other thing is we end up proving not like a knight it's really annoying that I think we should have done it differently but rather than proving like secrecy or like a a kind of general standard property for um for the dkg we proved this like we tried that entailed so we proved this notion of oracle-aided algebraic simulatability which um yeah with Julian and his student Renos have it's like a CCS paper from last year I think my suspicion is that this is the same thing as proving

um secrecy or key expressibility which is this other secrecy-like property for the dkg in the AGM using the one more discrete log assumption my this is this is what I kind of wish we had tried to prove ourselves because I think that it's probably I think their definition is basically that proving key expressibility using omdl in the AGM so their paper is a really cool paper and it it kind of shows that it seems like it's impossible to prove this kind of stuff without using omdl so forget like qsdh right omdl is a very strong assumption I think um so that they hint at an impossibility around proving this kind of stuff

without the omdl I can certainly tell you from like years of trying to prove it that you know I'm happy to believe them on that right like I I would be very impressed by a proof that just used any subset of the things I've just said without having to use all of them um so yeah so that there is yeah I I would be surprised or I don't know if I'd be surprised I'd be impressed um for sure so yeah so basically yeah we're using a lot of tricks we're using AGM the equivalent of using omdl which is this like weirdo notion of oracleated algebraic simulatability which is a real mouthful um but we proved it we have a proof and we're really happy about that

so yeah um that's actually the end of the talk thank you very much um and uh any other questions happy to take them yeah yeah good question about the setups to say you're saying you might be reusing this for setup strings that ethereum is constructing so that setups like say one of them is 1 000 elements of Tau powers of Tau it means that you can support a thought threshold of a thousand or like uh no no does it maybe um I'd have to go back and look at the commitment okay um because it would be nice to have

flexibility yeah of course um doesn't mean that's all yeah because the degree of the polynomial I guess determines how many secrets you need to reconstruct so it's natural feeling is that it should Translate yeah I mean there must be some relationship there um whether it's like degree Tower not like yeah I could look later yeah and so I said that um the biggest motivation for this work was to actually get adaptive um security so I was wondering is there any notion of semi-adaptivity here so in some of this like protocols we have this like semi-adaptivity on Corruptions that the person had some time to do Corruptions

and I'm wondering whether you know if essentially some like you know lighter assumption on I don't see I don't I don't feel like it would make it any easier to be honest right because you're still gonna have to consider I'm basically trying to see if this could remove the setup so oh uh because this seems to be one of the I don't I don't feel that the adaptivity is tied that much to the setup to be honest I think the setup is just like you know we're we're happy like we don't really care that much about having the trusted setup um and it's just like the most natural polynomial commitment in a lot of ways

um so I I don't feel like we could get adaptivity because we used kcg I I don't feel like those two are so closely tied so yeah I think if someone else could come up with like a setup free pollen I feel that it's more closely tied to like the efficiency to be honest um that yeah if you don't have kcg like things things just might not be as compact or you might need like more rounds to do things um I feel like that is more of a thing than the Adaptive yeah so I I don't think you yeah I don't feel like you couldn't get an Adaptive thing if you use something other than kcg I just feel like other things would get worse great thanks a lot

[Applause]