Manipulating Leader Selection in BFT Protocols with Matt Weinberg | a16z crypto research talks

Transcript

uh welcome everyone to today's a16z crypto research seminar very happy to welcome back Matt Weinberg professor at Princeton who is one of our faculty fellows last summer um so Matt's been finding game theoretic issues with blockchain protocols for a long time 2016 which of course is the Dark Ages um in this space lately he's turned his attention to proof of stake pbft style protocols he'll tell us about his latest work on that so Matt all yours awesome thank you um so I'm going to talk uh primarily um about this first work that was at um EC last year and uh throughout the talk I'm just going to briefly mention um these two ongoing Works um as well so I do intend to I think just kind of get like straight to the you know the

model and uh I'll spend some time on background in the model but I think I'm not going to do like a big broader pict picture overview but if that means that there are questions because I skipped some Basics I don't know exactly how many bft consensus talks you guys have seen over the summer but if there's some background I'm assuming feel free to just interrupt and I'm totally don't mind getting uh derailed that I think that seems to happen a lot and I'm really okay with that so at this point I hope it's maybe not like too bold to claim that it's kind of well understood how to manipulate longest chain protocols so like the seminal paper introducing that is now like 9 years old and there's you know like I think pretty significant follow-up works that are now

like 7 years old and I don't know if that's a little too bold to claim but I want to say that's starting to become much better understood um and I think what's a little bit less well understood is for these more modern protocols that are based on Byzantine consensus can you manipulate those in similar ways or how is that uh different so that's what I'm going to focus on in this talk and just to emphasize if you haven't seen um these kinds of presentations before what I'm not going to do I'm not going to show you how to like violate liveness that's not what these things are about we're not violating liveness we're not violating consensus we're not doing like attacks like that um but what is happening is someone's going to be able

to get a little bit of extra money by maybe being the leader more often or having their blocks adopted a little bit more often than if they were following the protocol uh honestly and so um the other thing I'm going to say is this is not a consensus talk so like I will give a couple slides just to recap in case you you know you haven't seen like bft style protocols before what's the relevant aspect of those but I'm not actually going to talk about consensus at all the entire talk is just about one role in these consensus protocols and how you can be the leader in these protocols more often uh so the main result is just going to be you know like there's a wide class of bft protocols I'm going to focus on a canonical one that I think captures a lot and they're going to be manipulable

I'll show you how to manipulate them and I will discuss how to you know optimize that process and be the leader as often as you can in those okay so the first thing I want to do before diving into that is give you some motivation that is technically different so um before is right before the merge so the technical details are not relevant anymore but before the merge in the proof of work ethereum um they had a difficulty adjustment and the difficulty adjustment was actually uh determined based on the timestamp difference between your block that you're creating right now and the previous block so fine and in particular that difficulty went down every 9 seconds and it seemed like maybe if you add some seconds onto your time stamp

this makes it easier for you to find your next block you can set the time stamp however you want and now all of a sudden you've just made yourself more likely to find blocks than you're supposed to be but that's actually not what you should do because in ethereum there are so many forks and ties are uh ties between forks are broken based on difficulty so it turns out that what you actually want is you want to shave some seconds off of your time stamp that will make it harder for you to find your next block but now you will win any tie Breakers in case of a fork so they proposed this and they looked at the source code confirmed that this was correct and then the thing that was amazing I think about their paper is that they showed that so this is the

timestamps for a specific pool I think it was F2 pool in ethereum proof of work and I think this is like super clear evidence that this was like really happening on ethereum at the time so you can look that every 9 seconds they produce zero blocks that have a 9-second difference or an 18-second difference between the previous ones and you can see that what seems to happen this should be like exponentially decaying and it really looks like someone just took the nines and moved them to the eights and the 18s to the 17s and so that's what they claim happen and then the other thing that happened was so this I believe is the manager of F2 pool who basically said like I think there was like three days after the paper came out was basically like yes we

did this and I interpret this last thing as saying like you guys should do more mechanism design so that this doesn't happen and so I now use this as like a motivation for the general theme of like why does manipulating protocols matter people are really doing this now I'm going to get into so all of that is technically has nothing to do with the talk but is motivating the same Concepts so Byzantine agreement um I assume probably someone this summer is talking about it in much more detail um basically it's a classical distributed systems problem you just want everyone in the network to agree on the same thing some people are adversarial and trying to stop you from doing that so what is a simple proof of stake blockchain protocol look based on uh bft you somehow randomly select um a bunch

of users maybe you do that proportional to their stake in the currency um they each propose a block and then you run a BFD protocol and then as long as at least some fraction um are honest they decide on the same block and the nice thing is that you know there's no Forks once this happens that everyone agrees and everyone agrees they agree forever and so I just want to emphasize because I I didn't fully understand this myself until I saw like enough talks that the nice thing about this is that if you have an honest user they'll never claim that they have decided upon uh multiple distinct blocks and so what that means is that if you ever find a witness that says there's two distinct blocks from the same round that each had a lot of people deciding on it this is like an explicit witness that

you must have had at least uh some number of dishonest users okay and so the way that these things go is you just need a large enough fraction of the stake owned by Honest users so that you hope that every round has some number of honest users and this seems like a reasonable assumption so um there's a lot of Pros in comparison to longest chains and there are still some challenges I'm not going to uh dwell on these there's still some challenges and I think the main challenge that's relevant for this talk is you need some source of Randomness to select the committee and um one Paradigm I guess that I noticed in a lot of the early blockchain protocols is they all have some notion of a

leader and that simplifies the protocols in the following sense so like a sample protocol to have in mind again I'm not going to give you like consensus level details is if you receive lots of different blocks then which one should you try to converge on well I should try to converge on the leader whoever that is and so then everyone eventually tries to converge on the leader and that helps make the protocols more streamlined okay so so Matt yes might be worth saying I mean you say need there needs kind of a strong word I mean I would say if you want some degree of unpredictability right then you need right like because some protocols some proof estake protocols just use round robin kind of stake way to drown Robin for leader selection so I'd say this is

a class of such protocols got it yes sorry so I think um I meant I meant to stick just to what I I meant to stick just to this which is say many efficient protocols have a leader I did not mean to say that you need to have uh something like this yeah so I so I agree with that thank you for clarifying and even if you have a leader it need not be random and even sorry even if you have a leader it oh I understand yes yes yes yes I understand so you're talking about this one that you don't need a source of well both you say source of Randomness then you say randomly select a leader yeah yes I agree yeah so you don't yes okay so I agree with that um you don't need to do that uh for the initial

protocols that got me looking at this that is what they did and my understanding is that a lot of protocols do this but you don't uh I agree you don't need to do that so why uh so like why is this a challenge like why would you care well the committee members and the leaders get rewards so maybe this is because they're explicitly transaction fees or block Awards in the protocol you know or like now you know there's meev and so like being able to dictate contents of the blocks is important and so like users want to be on the committee and they want to be uh the leader so what I would say is you know so again I'm not aware of evidence of these specific kinds of manipulations I don't know if someone in the audience is

um but I would definitely be concerned if it was theoretically possible to manipulate a protocol to be the leader more often that is definitely a profitable thing to do and so I would be concerned about that and then you know the reason I showed you the first couple slides was to say that like there are definitely instances of people in practice doing profitable things and so uh so my role is to try and highlight what are profitable things but I'm you know less knowledgeable about what's actually going on in practice okay so what I'm going to do now is I'm going to present several slides on just sort of like how might you do this and so this is motivated by um the you know the first protocol that like I was was kind of aware of was algorand and so definitely the model is

inspired by how algorand did it my understanding is that you know this framework is also how other people do it but um you know I'm not claiming this is exactly what ethereum does or exactly what other protocols do um so what is a representative framework to do this so every round has some seed and every coin based on that seed is then going to compute their own uh credential so what is that one way to do it is you can digitally sign it and that's going to make it unique to the account maybe let's also just like throw in the IDE of the coin when you digitally sign so it's Unique to each coin and then you hash it and so it's nice about this is it means that you

know once the seat is set you can think of you know hashing as being like you know it's perfect Randomness it's basically just giving everyone an IID draw uniformly from 01 for each coin and now you can say I'll say the smallest credential is the leader and the Thousand smallest credentials will be the committee and what's nice about this is once the seed is fixed that will just give you a uniformly random coin and that's going to be your leader so that's good there's like this inconvenient thing that I will quickly address just because I've notice that sometimes it distracts people during the talk of like exactly what should you do if you don't want to do one hash per coin so there a

simple fix I'll just quickly go through it on the next slide um but that initially sounds inconvenient but you can make it so that there's just one hash per wallet that's fine but the key challenge that's going to be the actual focus of the meat of the talk is how do you pick this seed across multiple rounds and so what you might be concerned with is predictability so kind of like what Tim was mentioning was that if you're not concerned about predictability then there's an easy way to do this you just fix them at the beginning of time and you have your your leaders and there's no manipulation that's it um if you are concerned about predictability then you want it to kind of be set later and then the question is how do you do that in a non-manipulable way or a minimally manipulable way so

let me quickly just um address this there's like a little bit of little bit of cool quick math so basically what you want to do is you want to somehow draw a credential in a way that is one credential per wallet that somehow ated by the size of that wallet right and you would like it to be the case the property you really want is you would like it to be the case that for example if my wallet has twice as much as you I'm twice as likely to be the leader as you and so then the question is is just a pure you know probability question what are parameterized distributions such that when you parameterize them by the amount of the wallet that having twice as much makes you exactly twice as likely to be

selected so the answer to that is those are exponential distributions Okay so just in case you'd like to see something very concrete what am I uh saying you should do um what you should do is say your credential you're going to digitally sign and hash something this is uniform in 01 you're going to uh take minus the log and divide by the size of the coins and then the smallest this is going to be the leader okay so this is just if you are really detail oriented and you want to see why does this give you an exponential distribution that's here but I'm not going to read that out loud and the two cool facts if you don't you know if you haven't seen them before

is that the minimum of an exponential with rate X and an exponential with rate Y is distributed exactly like an exponential with rate X Plus y so one thing that means that this is like Cil proof and it's also collusion proof right so it doesn't help you to split up your stuff it doesn't help you to merge you're still going to have the same minimum credential and the second cool fact is is just that uh the minimum of two exponentials with different rates is equal to each one uh with probability proportional to their rate so that's exactly what we want that we are indeed picking proportional to stake so what you should really do if you don't want to do one hash per coin you do one hash per wallet and you just scale it according to this and now you've solved

that uh that annoying problem um Matt yes oh if you're just taken the minimum why isn't everything invalid to a monoton transformation uh the distribution's not going to be like if you do um oh sorry this is a if if I want wallets of different sizes that's the issue so if I have wallets of the same size then yes any monotone transformation it's invariant under if I have wallets of different sizes I need to scale my like I need to scale my twice as large wallet so that I'm twice as likely to be the Min compared to you so there are other ways to do it I think this is just the cleanest function I

know did that answer your question yes okay I me Matt maybe maybe like conceptually way to say this is okay so previously you were flipping a thousand coins right and so um the thinking is like okay but actually you only care about the minimum of those thousand experiments right so why not just sample directly from the distribution the minimum of a th000 experiments and then all that stuff is just saying look you can actually do this in closed form really easily two separ points that's exactly correct yes so just to repeat that uh another if you wanted to do the math slightly differently but it would be conceptually simpler what Tim suggested is you could just simulate uh you actually have two

coins in your account or a thousand coins in your account so there is a distribution which is what is the minimum of a thous you know a th000 IID uniforms that could be what you do here and it turns out there are just other functions you can use and the exponential is simpler to use so now we get to the uh the key conceptual challenge okay so now uh so so I took these slides from when I was giving um you know like a class based on this so I'm going to actually you know the the several slides are both the animations and the content is sort of like as if I were teaching so I will pause if you guys want to like participate in the math exercises feel free to do so but if I'm not getting that Vibe I will just click through them so the first approach

is you would say like okay what if we just had trusted external Randomness right then you would say okay I'm just going to use that trusted external Randomness Beacon and that is going to be my seed for each round J and this would be great if you had that so there's no way to manip there's no way to manipulate a trusted Randomness Beacon if you actually trust it and it's not predictable so if you had this this actually would be perfect now what I want to highlight is it you know this may seem trivial the way I'm presenting it but this is not the case with longest chain protocols right so longest chain protocols even with proof of work are still

manipulable right and so you know and trusted external Randomness is even slightly more manipulable than proof of work so long as chain protocols with trusted external Randomness that doesn't fully solve the problem for bft protocols if you have trusted external Randomness to select the leaders and committees it fully solves this problem the kind of problem that I'm looking at so the entire challenge is how are you going to get as close to this as possible possible when you don't want to do this so the uh uh second approach and so this is this is a straw man that I would pause for participation in my lecture is what if we set the seed for round J equal to the hash of the J minus first block so this is good for

unpredictability because you're not going to know what's the J minus first block until round J minus one so you're not going to know the seed for J you can't precompute but I think there is a huge problem with this so there are so this is really manipulable and um so I I don't know actually what is like common nomenclature I believe that what I'm using is consistent is that I would call this like a stake grinding attack because there is basically an unlimited set of things you can try so you can try adding removing transactions you can try changing whatever you want and every time you change the contents you're going to change the hash and so what I would do if I was leader for J minus one I would just grind the

block contents and make it so that I get a good hash for the next round and then I'm going to be the leader again so I would just take over the chain and I would also like to point out so this is really really bad because it bleeds Beyond just being the leader that you know in theory you could also grind so much that you're now over represented on the committee and when you're over represented on the committee that's even worse than just being over represented as a leader because now you could violate consent ensus so I'm not positive exactly how realistic it is to grind so much that you like you know violate turnoff bounds but that is at least something that in theory is uh possible was there a question yeah Matt can you like I can

grind also by just grading the next block you're saying if I'm in proof of stake this actually becomes something more like a proof of work then I'm saying it's yeah so I'm saying it's actually worse than that because in proof of work like uh how would I describe it let me just repeat this part is that is the moment I'm the leader once if I have enough computational power to make myself the leader next round I will just always be the leader so I can like fully take over the chain like there's some minimum threshold of if I have at least this much compute then I can take over the entire chain

whereas in proof of work you know like there's you know you can invest a lot of compute and take a you know take over a fraction of the chain but if someone else chooses to match your compute then you still you know you're still only 50% but here there's just a threshold which says as soon as you hit that threshold you just own the entire chain and it doesn't matter if someone else has a hundred times as much compute as you you you've like locked it down did that answer the question yeah but um but in I'm just thinking that in proof of work you can say okay there's a threshold that's exogenous that depends on what are the competition what's the competition doing uh here you have a threshold that defined within the protocol respectful

to other what other people are doing but in both there's kind of like an assumption the protocol works because you can't grind too much yeah sure okay that's uh I I think that's fair to say it's maybe not fun Mally different I think it's fair to say that at best you're just reverting to proof of work and I would say this I do feel like is still worse because even if like like basically well okay we'll see a little bit later but basically even if I just you know do like 10 hashes this gives me you know 10 times the probability of being the leader in the next round right and so I think like uh something about that is very

different than something about that is still I think very different than proof of work but I'll get into that aspect in a little bit more detail later um but yeah I think it's fair to say at best you just revert to proof of work but I but I I do think it's worse than that so here's approach three so the um the the first place I saw something like this was zarand I don't know if there's an earlier reference or if this is something people have considered for a long time um but I thought this was really clever and so basically um what they wanted to do is they said like okay stake grinding is bad it's bad to let the seed depend on contents that you can just set however you want let's have the seed depend on something you can't control but still something that's going

to change from round to round and so the idea here is you say okay let's look at round J minus one and let's just look at their credential right so they cannot control their credential that's just they digitally signed last round seed they hash it they the digital signature is deterministic hashing is deterministic and so they can't control this so so just to elaborate on what this means conditioned on being leader there's nothing you can do to change the seed for the next round once you're the leader it's a deterministic function uh of your of your stuff and the other thing that's nice about this is that because it requires your digital signature that like until you actually

you know announce yourself as a leader in round J minus one Nobody Knows the seed for round J because nobody else can compute your digital signature until you actually participate they don't know what's going on um so that's nice and if you want to think about what that means so this thought is going to be relevant for later when you're trying to plan for the future you can think like what do you know you can say like well I see the seed for this round and I can imagine what would happen if I were to win if I were to win with any of my accounts I do know what the seed would be next round and then when you want to imagine what would happen two rounds from now you can only talk about those

seeds assuming that you win in the next round because as soon as someone who's not you wins that's a digital signature that you can't compute so you have no idea what the seed's going to be so what I would say is so if somehow you believed that every user has exactly one wallet and no one can create multiple wallets or something like that then I would say this also to me seems ah sorry I shouldn't have said perfect it seems really pretty good and maybe at the very end um we can talk about like how you can be very creative that it's still not maybe still not quite perfect but it's pretty good if everyone has only one wallet and uh foreshadowing towards what's the interesting math we're going

to do is you can think about uh What uh what you might do if you had multiple wallets um if you were participating in this protocol yes can you grind over the public keys that you register like if you know that uh you're going to be a leader for a while can you manipulate your public key that you're going to rotate good question so um so I would so if I were actually designing a protocol what I would suggest is I would say nobody is going to be the leader for more than like 10 rounds in a row or 15 rounds in a row or certainly not 100 rounds in a row so I would say whenever you create a public key you're not eligible to be the leader for like

at least 100 rounds in the future or something and then I would feel pretty safe about that because as long as there's as long as there's a single round that you lose between when you registered and when you're eligible to sign then there's no way that you could have had an advantage over choosing that public key and um or maybe even let me phrase it as when the stake is moved between public Keys like that there should be some between when the stake is moved to a public key and when that um stake is eligible to um be a leader and as long as there's one round between when the stake is moved and when you're the leader you can't possibly have like you know had any statistical advantage in

moving it to a specific public key so another thing that you might try so just to recap the approach three is the one I'm actually going to do math for later in the talk but I still want to highlight like what are alternative so another approach is you could do um some very expensive operation to set a bunch of seeds at once so for example maybe you say that I'm willing to use multi-party computation but I can't do multi-party computation every 13 seconds I'll do multi computation multiparty computation once a day I don't I don't actually have a sense of how feasible that is but you do multiparty computation once a day or once a month or whatever whatever the right timeline is and then what you do you you just had a a chunk of seeds all at

once and so what's nice about that is well like I mean MPC is really secure so like you're not going to manipulate any seeds by participating in MPC so that's nice um the downside is that the seeds are predictable like many rounds in advance um and so again so maybe I will skip the you know pause for lecture style discussion but like I think it's harder to quantify exactly why that's bad like I don't have a good mathematical model that says like oh yeah here's a clean explanation of why this is bad um right so like the stuff I typically think about there's no selfish mining you can do just you know you can't you can't manipulate anything you know what it is but you can't change

anything and so then I think the question is a little bit more outside the box of like what would you do if you knew that you were the leader a th000 rounds in advance and um I can think of some things I don't know if like other people like just you know s just on tape want to say like uh other things you could do but like it makes it a little bit easier for me if I wanted to solicit bribes for my behavior in that round because I have like a little bit of a window in advance to actually solicit them it's not like you can't do this if you only learn 13 seconds in advance but it's just easier if I have some lead time the other thing that I would say is maybe closer to stuff I think about is like yeah if I

knew I was a leader for like four blocks in a row I would definitely get better me out of that I don't have a good sense in practice of how significant it is but my understanding is that it's definitely non-trivial that you can get more me knowing that you're the leader of four rounds in a row so I don't know if there are other like major concerns but like these are the two things that come to my mind about why predictability is bad and it's just kind of like orthogonal to um manipulation you could also like if you know who's going to be elected you can focus your resources to corrupt them right that's also true yeah sorry I I'll just repeat what was just said that's also true that if you are a um attacker and I guess what's a little Challen alling is it um you would know that

you're going to be the leader because you can compute your digital signature and like it's may be risky for you to broadcast that but I I would still have to compromise you to learn when you're the leader or or something like that but I do agree that it's just like it's still just like another it's still just like one more security issue um to worry about but I agree with that the last so the last thing at least that I'm aware of there may there may be other things out there but the last way that I'm aware of is you could do some kind of hybrid between three and four so what do I mean by that I mean there's no expensive computation but you're still setting a chunk of seeds all at once so what you could do is I could say maybe um you know every

thousand rounds or every 10,000 rounds that for that round only I'm going to use the initial algorand approach I'm going to say the leader of round 99.99 credential is a seed from round thousand and then for the next thousand rounds I just hash the seed right so there's no influence on seeds thousand And1 through 2000 uh but the or through 1999 but seed th000 and Seed 2,000 and g3000 those are chosen by the same thing it's definitely not secure like multi-party computation because in the round where you're setting the next thousand seeds you can definitely manipulate those the question is sort of like I mean how much can you really

benefit benefit like if I you know if you if you manipulate a string of a thousand seeds like yeah you you definitely will gain something right by having multiple options like you can probably increase your representation by a little bit but it's definitely not going to be significant when averaged out over like 10,000 or 100,000 however many rounds right so it's kind of in between you get um uh you still get the predictability issues that you do by using multiparty computation but you don't have to use multi-party computation and you get like a little bit of the manipulability issues but you largely don't have to worry about them at the same scale um and so what I learned uh I guess it's not so recent anymore but at least last summer when I was like doing more prep

for the first time I gave a related talk um like I Mo I normally motivate this model by saying this is what alaran does and then I had to change say well this is what alaran did for like the first five years and alaran recently pivoted to something like this instead of the one um that uh refreshed the seed every round sorry so what's the advantage of this one so the advantage would be over the previous over multiparty computation or over the previous one so the um benefit would be it is just less manipulable so think of it as like if I gave you um so imagine if every round you're manipulating the seed for the next round having two choices for a seed for one round that will help you like every

single time if instead it's two choice is for a string of 100,000 seeds then like I would ask you okay by turn off bounds you're probably winning very close to the same fraction of both of those like yes in terms of raw numbers you're going to win more in one than the other but averaged over a th000 rounds it's just not that much just to recap the approaches so I think the the first okay so the first one I would say is is certainly viable but it's just pushing it off to trusted Randomness beacons the second one I don't think is viable like at best is just proof of work and I think is and like I was telling Jacob I think is worse than that so I think the three viable ones are these guys and just as a reminder of the trade-off so I

think like for four versus five I think that's just a crypto question as to like you know do you want to get rid of the mild manipulability in favor of using heavier crypto you know I don't know that's a that's a resources question for three versus four five is exactly what um uh Andy just asked I would say the trade-off is with three you have near termin iability that's what I'm going to focus on in the rest of the talk um but you don't have longrange predictability for the latter two you have longrange predictability but like either no or minimal predictability and then I just want to highlight an orthogonal concern which is that you know for all of these you can still ask is it possible to manipulate enough seeds not just that you're the leader slightly more often

but you manipulate the seeds so much that you can get higher representation on the committee I'm not aware of attacks that like I've thought through they would get you all the way to here but that's just an orthogonal concern to highlight That should kind of be on the mind is that it's not just about being the leader that if you can really manipulate so much you are getting more chances to be higher represented on the committee and if you're starting to get like an exponential blow up in the number of seeds that you can consider then that would start to be a concern for this so what I'm going to do first is here's a quick reminder of the uh framework and the one I said I'm going to focus on is the initial algorand

proposal which just says in every round there's a leader that Leader's credential just becomes a seed for the next round okay so let's think about how this can be manipulated so maybe you figured this out if you were thinking from what I mentioned it on the previous slide so what I would do I would definitely spread my stake across as many wallets as possible i' would make them all very small and here's what I would think through so if I owned two wallets and they both have smaller credentials than everyone else so this means I have two wallets that both would be the leader if they were the only one that I chose to broadcast everyone else then what I would do is I would realize this and I would say like well I'm going to choose which of these ones

I'm going to broadcast to everyone I'm not just going to blindly broadcast both and what this does is this gets me two choices for what the seed's going to be in the next round and what I would do is I would just evaluate these two seeds see which of these seeds looks better for me in the next round so this is some intuition for what I would do I'll analyze a manipulation that looks very similar to this and then I'll talk about how you would do the optimal thing afterwards okay so what does uh I would say Let me let me make a formal game out of this so I would say every you know every participant I guess I called them minors on this slide but every participant uh has some fraction of stake and the initial seed is just going to be a uniformly random number and

every minor at the initial part of the game they can split their stake into however many wallets they want and what happens in every round so every wallet computes their credential and their credential is drawn as we discussed earlier from an exponential distribution with rate equal to the size of the wallet and what I want to highlight is that every participant can compute their credential for any wallet they own in any potential seed because that they all they need to do is digitally sign and they hash they can do that for any seed and for any wallet they own they cannot do it for any wallet they don't own because they don't

know how to do the digital signature okay so um so I'm not going to explicitly model computation in this but I'm just going to say that the minor when in terms of what information do they have they have access to all of this information and they have access to none of this information when they're making decisions and so now what's the the actual game is every wallet can either broadcast or not broadcast that's the entire game and the leader of the round is just among the people who broadcast who has the smallest credential that credential becomes a seed for the next round okay so that's the entire game and what is your payoff well um you just want to basically maximize the fraction of rounds that you lead so this is maybe I

think this is a very good proxy for I think what I would try and optimize in practice it's not perfect because are higher me rounds I would really want to win the higher me rounds more often but um let me just start with this and say that even if you're just blindly doing this you're going to be you know you're going to be in better shape than if you're just honest the last thing I want to do is discuss um so if you guys are familiar with selfish mining there's a parameter related to selfish mining that they call gamma and that refers to how well connected are you in the network and so for selfish mining what's relevant is if you withhold a block and I hear that someone else sends a block how quickly can I propagate My Block in response to that to other people in the network so

they use gamma for that uh we chose a different Greek letter but um it captures the same thing which is just like when I'm choosing when to broadcast what fraction of other broadcasts have I already heard so for example beta equals 1 corresponds to being very well connected and that means that I decide what to broadcast after hearing everyone else already make their broadcast beta equals z means I'm very poorly connected that means I have to decide what to broadcast before I know what anyone else is doing and so here's a quick uh so I will not make you guys actually answer this live but um the ma you know the quick math test is you can just think if you have an alpha fraction of the stake and the game has parameter

beta then you can think through what is the uh distribution of the minimum credential that you will see before you decide what to do and if it helps just a thing so that's an exponential with rate equal to a beta fraction of the one minus Alpha stake you don't own that's going to be the distribution of what you see before you broadcast and then after the minimum credential you can also think through because you want to optimize for what are you going to see after you broadcast and you know what that's distributed like so you should use that when you do math to figure out what you should do and so what that's distributed like is there is a 1 minus beta fraction of the 1us Alpha fraction of sake you don't own

and that's going to be uh independent of everything you've seen so far so this is um you don't need to like memorize these formulas but this is just to show that like yeah you you can compute this and you should use this information when you're optimizing what to do how important is the assumption that everyone else is honest like if you were like an like a Nash equilibrium yeah yeah good question so um so I think I so I answer this question a lot whenever I give talks on this I view what all of the stuff I do I view view as more like impossibility results in the sense that everyone wants their protocol to be followed so what everyone really wants is at minimum their protocol to be a Nash equilibrium right so if their protocol is an asash equilibrium it's

not crazy to say people will follow it maybe if you're like really an economist you want more than just an ash equilibrium but you probably want at least that and so everything I'm doing is I'm trying to understand um whether it is a ash equilibrium or not to follow the protocol and if it's not how you know how far is it from being a asash equilibrium so you might tell me you're like yeah you're telling me that you can get 0.001% additional Revenue by being dishonest when everyone else is honest maybe that's fine so I'm interested in understanding like how much can you gain when everyone else is honest yeah that I answer the cool um so I think in terms of a positive result for finding an ash equilibrium that is super hard and I'm

not actually aware of like clean results for any of the previous models or this model that says here's an ash equilibrium I think that's very hard so let me show you a very simple profitable strategy that I will call the one look ahead strategy and I think well I will definitely present it and I may skip some of the math I had in here so what's the simplest thing I would do I would say I just want to maximize the probability I win the next round I don't want to sacrifice when this round and let me also just present it in the simplest case when I'm really well connected I see everyone's credentials before I broadcast so what would I do I would say I have some set of wallets that are

small enough to win I'm definitely going to win if this is non empty I'm not going to play very sophisticated games and lose when I can win so what would I do um I would just compute for every wallet I own I would say what is the minimum credential among all other wallets I own next round if I win with wallet W right now okay so this says I want to find uh next round what I know is that I do want the smallest credential possible that's more likely to win because everyone else's credentials are drawn independently of everything anyway I don't know how they I don't know

anything about them other than that they're distributed according to exponential at rate 1us Alpha so I'm going to do is I'm going to say which wallet among mine that can win gives me the best um credential in the next round so just to repeat that I'm saying for each wallet that induces a seed for next round for each seed for next round I sign it and hash with every single one of my other wallets and I see what's the smallest and then among all of those I take the smallest one I say that looks best to me I go with that credential for this realm so um I'm going to make maybe not pause on the calculations but I'll just highlight how would I analyze this so what I want to do is I want to say okay that sounds

great how do I figure out how good this is so the first thing I would do is I would say what's the probability that I have K wallets to choose from okay so this is the answer and then you can ask what's the probability given that I had K things to choose from and I went through this process what's the probability I win next round for the best credential that I take remember that I had K different wallets so this is K different seeds for each seed my best wallet in the next round is distributed like exponential of rate Alpha I get to do this K times independently and take the Min so if you remember the fun fact from

before this means that I have the Min of K independent exponentials of rate Alpha so that means that my best credential next round is going to look like an exponential of rate K Alpha cuz I got K times the options the others no matter what they're going to be distributed like exponential over a 1 minus Alpha because whatever happens there is independent of whatever I did because I can't do any of their digital signatures anyway so whatever happens for them as far as I'm concerned is independent of what I choose to do so that means that by the second fun fact that mine is smallest with probability K Alpha over 1- K minus one uh 1 plus this and that's just because right I sum the rates that's

this and then minus smallest with this Okay cool so um what that means is that so maybe you can you can see this is definitely you know much better as K grows this is getting much much better okay so now what's the next step is okay so if I want to say great now I want to figure out what's the fraction of rounds that I win this isn't enough because this is saying sort of like given that this round was unbiased I can compute this and given that I happen to win this round with K I know what this is but this doesn't tell me how to like really

average over all rounds so I think what I'm going to do is skip over that part of the math but I just want to point out that like um there is math that fits in just here twice that fully says exactly what the uh answer is so the answer is this divided by this that's the answer okay um so that's how good it is it's always strictly better than Alpha no matter what Alpha is and just to give you a sense of this magnitude it's not well actually I don't know what that much is like maybe someone will tell me this is a lot it's not that much but like if you have 10% of the the stake then with this strategy

you can get 10 point almost 10.1% of the rounds so I I don't know what to make of that like I think 10.1 is not that much bigger than 10 but that's probably a lot of money um I don't know that there are stakers that are quite this big in you know like the algorand or ethereum landscape but you know these numbers are starting to grow by a bit more um so it's like it's modest I think it's like not trivial but it's not like you know it's not like you're doubling your reward okay so I just want to maybe start moving towards wrapup by noting that I presented the idea when you know all the credentials CU that's a conceptually simplest to understand the same ideas work if you don't see anything in advance so what would I do then so i' say like well it's definitely

not going to be quite as good as this right so it's harder because if I choose to not broadcast a my lowest credential that might cause me to lose when I otherwise would have won and I just won't know whether that's what's happening um but why it's still profitable is I was like well I mean if I happen to have two credentials they're like extremely close together right so I have like a a you know like a 0.1 and a 0.11 there's some probability that that happens and like when that happens and one of them gives a much better seed next round like then I may as well hide the other because I'm you know I think it's reasonable to conclude you know what we actually know the probability that it lies you know that I would have won with my 0.1 and I would have lost

with my 0.11 is super small and the benefit that I get in the next round will probably dwarf whatever that probability is so I should just go for it um you know so that's you know that's not a proof but that's like intuition and the math you know backs that up okay so the other thing I want to do um so I know that uh I haven't given a selfish mining talk and I I don't know um how well everyone in the audience is uh knowledgeable about that but just to compare to similar kinds of claims for selfish Mining and longest chain protocols is I would say the big distinction uh so first I mentioned that this parameter beta is really conceptually the same thing as gamma from selfish mining it just refers to how well connected you

are and in selfish mining if you are poorly connected then honesty is optimal as long as you're not that big and for proof of stake longest chain the same thing holds okay so just to repeat what that means if you are very poorly connected in a longest chain protocol and you are not that big then just following the longest chain protocol is optimal to n equilibrium for everyone to do that um we know that there are some settings so like if there are transaction fees or me instead of the block reward or um or you don't have external Randomness and you have to you know do everything internally then these are more like uh this where you're

poorly connected but you can still do something strictly profitable no matter how small you are so that's like how I think of the big distinction is do you need to to be big in order to strictly profit or can you strictly profit even if you're tiny and so this one is you can strictly profit even if you're tiny yeah so when you did the first half of the slide I don't think in your intuition of why it still works with bit equal zero you mentioned stake being big or small but now you seem to be saying it matters a lot for that intuition um sorry can you repeat the question so above you said oh it's still going to work in beta equals zero because just think about this one case yes but then maybe I misunderstood but now I thought you were saying that

actually that intuition is wrong if you're small no sorry I wasn't saying that uh sorry let uh um I can try to quickly repeat what I was saying here is um I think that how I like to classify manipulability of protocols is basically do you need to be big to profitably manipulate it or can you do it no matter how small you are and so the um proof of work with a block reward you need to be big in order to profit by doing something like selfish mining proof of stake with trusted EX external Randomness you need to be big in order to profitably do something um like selfish Mining and then there's um on the flip side there's like proof of work with transaction fees or me where no matter how small you are there's

something you can do that's strictly better than being honest or proof of stake where there's internal sooner Randomness there's no matter how small you are there's something strictly profitable you can do and I was saying that um this class of bft protocols is more like the latter that no matter how small you are there is something strictly profitable you could do so uh okay so I definitely don't have time to do this which is fine let me just give um I'm just going to read this and then I'm going to click through um the math and I'll again say if anyone thinks like the math here is cool I'm very happy to chat about it so the one look ahead strategy is basically like I want to win the next round as often as possible um following a round that's unbiased and like something better you

could do is you could be like I'm going to try and win you know the next two two rounds as often as possible and starting from a round that's unbiased and like what's even better is you should really just look as you know with all the information you have you can compute your if I win for this round and I win with wallet W2 next round and I win with wallet 3 W3 in the third round what will the seed be in round four you can compute that you should do that and you should look super far in the future and consider all these possibilities and just say which of these looks best for me in terms of optimizing the fraction of rounds that I win so you can do that you should do that uh so one thing we did so we worked through um we do have

like a purely theoretical upper bound on the best you can possibly do no matter how far you look in the future and uh I don't think this is close to tight so just to give you a sense of the magnitude I showed you a strategy that went from 10 to 10.08 and this is saying you can't improve it better than 21.11 right so I don't think these bounds are anywhere close to tight but they're something and one reason they're not anywhere close to tight is that they also hold against an you know a really omniscient adversary who can like not you know who has more information than our player does because they can digitally sign on other people's behalfs so they can't change the seeds but they can see what would the seeds be if someone else won and digitally signed or

blah blah blah so even for there there's some upper bound but I don't think that's anywhere close to tight the thing that I'm more excited about but that is proven to be really hard is um you know I want to basically do it simulation based because I I don't think I do not think there's a closed form for like what the optimal thing is I think that's um sorry there obviously is a closed form I don't think we're going to find the closed form I don't think it's going to be tractable so I think what that means is it should be done with simulations and maybe the thing I want to do is I just want to make sure that whatever simulation we run is like going to be provably close to whatever the right answer is and the um so this part I'm going to skip for the math um or

like how do you get you know how do you take steps toward something being provably close the the one last new thing I want to say I just showed you in theory and there's a lot of Prior work in theory that says that in practice there are network hash rate whatever conditions that show that there are players who can strictly profit from deviating so for example I just showed you um I think an accurate represent representation of aloran for like the first five years it existed and anyone who was staking an algorand could have done this and as far as I know it was not detected right and all of these attacks with one exception of the one I showed you at the front most of these strictly profitable attacks in theory are overwhelmingly not detected in

practice and so you're going to ask why is that the case so just to confirm you know you have a permissionless protocol so it's not like you can figure out who did this attack and you know and go and ban them or Blacklist them or something you can spread stuff out among lots of wallet it's not going to be clear which one was being Mal malicious and who was just offline this one I just showed you is profitable again even for very small people and it's definitely true that like for smaller altcoins like people have had enough of the hash rate to like actually selfish mine or do things that have been known for like N9 years or whatever and the most convincing argument I've heard in response is that like look all of these deviations I showed you that you can get a little bit

of extra uh bft coin by doing this attack and it will def itely be detectable that someone is doing it so I can discuss in a second why would it be detectable and so what I might be concerned about is that like yeah someone detects that someone's doing an attack it tanks the value of the currency and now I'm like really excited about my like 0.008% extra bftt coin but they're worth like half of what they were before I launched the attack and now all of a sudden it's you know doesn't seem so profitable detectable is that someone is doing it and traceable is who is doing it so like if I wanted to say specifically I think you are selfish mining that's really hard to do because it's permissionless and like maybe you were just offline I saw two blocks come

at the same time one of them was honest one of them's from the selfish minor I don't know right like I don't know which is which um so that that's what I mean by traceable versus detectable but it's going to be very obvious if someone selfish mining there's all these forks for some reason uh so this is a project with uh uh Mariam was to ask sort of like well is it possible to do something strict strictly profitable in a way that's like undet able so like it really just looks like things are operating as normal so um yes for the longest chain protocol there is something you can do that's strictly profitable and undetectable so what I mean by that is it looks like there's just a little bit more latency than natural in the network and it looks statistically identical to that but you're getting more

profit this uh ongoing work so what we've shown is that actually for leader manipulation that's actually not possible in the poorly connected case so what I mean by that formally is it um so when you're poorly connected no matter how much hash rate you have no strategy satisfies the following two properties first strictly profitable would mean that you win more than an alpha fraction of the rounds second is the distribution of the leader credential in each round should still look exponential in something so for example if everyone is honestly following the protocol and everyone is online if I look at the

distribution of the minimum credential over all rounds it should look like an exponential with rate one right that's what should happen if a c fraction are online and honest every round it should look like an exponential of rate C and if somehow the distribution you see is not even exponential at all then someone is is someone is hiding stuff or going online offline online offline so just to repeat what the theorem is is that this particular detection method will catch anything that is strictly profitable for beta equals zero for being um better connected that's the ongoing part so I mentioned that this isn't a completed project the ongoing

part is here it turns out to be much more complicated but um if you force me to conjecture I would guess that it's probably also true for larger beta too yeah is that this is basically saying like in an Asm toote like if you got like it won't it can't be justified in asmt to do you have any notion of like how fast it converges towards this asmt like if I was like interested in like a like P like some sort of like you like comar test yeah so I think it I think it depends on sort of like so then you have to go back and try and trade off how much are you like what does it mean to profit in a short term versus be detectable in a short term I think that makes the question a lot Messier because then you say like okay I want to you

know maybe like make a lot of money in one week before anything gets detected and you can ask that question of how much money could you you know how much money could you make in one week subject to deviating from an exponential buy at most blah um but I think the I I I think I'm just saying you need to change a lot about the question and what counts as reward I think to really make that into the model yeah um okay so that was the last thing I wanted to say so here's the uh summary so I introduced I would say a canonical model for leader selection it's uh definitely not the only one I introduced a couple of different variants that are used in practice for how to randomly select the leader and then Tim noted that um you can also do it with like

round robin if you're not concerned with predictability it's possible that there are other paradigms out there that I'm not just aware I'm just not aware of but those are the ones I'm aware of um so I showed you a simple strategy that's always strictly profitable I gave you a very loose bound a theoretical upper bound on the profitability um I didn't give you details of this um but there is basically a recursion you can set up to describe the optimal strategy and then the game is to how do you make a provably correct simulation for simulating that uh recursion and then I briefly mentioned um undetectability okay so last last notes is um I focused on this canonical model but like the ideas definitely apply to other protocols so like the ethereum's Randal doesn't fit verbatim into this model but

the same kinds of ideas of like you know not broadcasting when you should broadcast they definitely apply there um and I've actually been meaning to look at this uh specifically and try and analyze it but I just uh haven't gotten around to that yet um the other thing I want to remind is that these issues can be avoided if you're willing to use heavy tools so like if you're willing to use multi-party computation then it's not manipulable you're in good shape um I believe that vdfs would also suffice that you can I believe you could probably replace NPC with vdfs um but I think it's still I'm not aware of like a concrete all the way detailed proposal of how to use vdfs for that but I feel

like my intuition is if someone writes it down carefully I would expect it to probably work um without these heavy tools we talked about that the trade-off is between uh predictability and manipulability that if you're willing to um say do round robin then it's predictable but not manipulable if you want to change it every round it's manipulable but not predictable um and I will still say like I'm curious whether it is possible to somehow get both without the heavy crypto tools and it feels really hard it feels like it might be impossible just because people have been trying to do it for six years and haven't done it but I actually don't know I I don't know sort of like a a

candidate proof approach for showing something like that um so I do think that that's interesting to understand what are the limits of this um okay sorry for going a little bit over um but that's everything I have thank you about the reason why we have not observed an attack so far I think that um actually it's a really serious thing if I can only own like 10% of the stake and I can tank the value of the coin by like to it's like 10% let's say from 100% because in this case even though the 10% I own will lose its value I might like short the coin's value with much larger amounts of money and I can make a net profit in this case even though if I just restrict my like payoff to the currency itself it seems like I am

losing money but I can actually get money in So yeah so so I would say I so my take is I definitely agree with that and I think that is definitely a concern if you were to ask me though still in terms of like why has it not happened yet in practice I would still guess that sort of like that's a very risky play to make and you would have to be pretty confident confident in exactly how much you're going to tank the value by in order to believe that your short is going to work out so I do think there is definitely like a positive expected value play you could make along that form which is you have some belief about how much you're going to tank it you short for the right amount you hedge

whatever and you do the attack and hope what happens but it's probably a really high variance play and I don't know if anyone here has a legal background I would guess in the US that's probably illegal too um so like that would also explain why no one's tried like that specific thing in like a you know developed Western Country um but uh but I definitely share your concern that like unless you're going to rely on the fact that something is illegal or the fact that people don't make risky plays or whatever um that my understanding is that the the short Market is large enough now to um to try and do something like that if you thought you had a good enough estimate I

think that's right okay all right thanks mat all right thank [Applause] you