Introduction to Selfish Mining with Matt Weinberg | a16z crypto research talks

Transcript

so I am going to focus this talk on giving um an introduction to selfish mining okay so uh uh what's my goal so I'm gonna spend the first portion of the talk um just giving a clear introduction of uh selfish mining so selfish mining is um this uh attack that was discovered uh now maybe eight years ago uh um specifically for Bitcoin and that refers to just some way that you can um not follow the longest chain protocol and you can make some extra money if you have sufficient uh hash power to do so and uh what I'll do is just dive straight into that

what I want to focus on is I'm going to present a formal model where this analysis was done and I'm going to show the analysis technique so I'm not going to slog through all of the calculations to get the result but I am going to show you kind of like the interesting part of how to set up the calculations for that and then afterwards I am going to kind of uh it's at some Pace rush through some subset of what I write on this slide for like um what's happened uh since this attack and what I am most uh comfortable presenting is

um okay so here's uh first some follow-up work that came soon after which gives an alternate analysis technique that I think is super useful um for follow-up work so I will also briefly uh overview that analysis and this analysis is useful because this uh alternate style actually lets you find the optimal strategic deviation not just this specific one that's called Selfish mining um uh but then since then sort of like one of the things that I've been involved in is uh you know people you know we asked sort of like well what if you took Bitcoin but instead of having the block reward you had transaction fees how does that change the Strategic Behavior it turns out it changes it a lot and you said like well what if instead of having

a proof of work based longest chain protocol you have a proof of stake based longest Chase protocol and so it turns out that changes it a lot too um and so if I have time I have basically just created quick slides where I said here's the change in the model here's the new result and there's no proofs or analysis or anything for that um so if I have time at the end I'll try and uh just give a taste of those okay um so now I'm gonna Dive Right into selfish mining um hopefully um uh what I guessed uh everyone's background is was close to correct but uh definitely feel free to interrupt with whatever questions are needed okay so um here is a quick recap of when

I talk about being strategic in Bitcoin so what are things that you can't do in Bitcoin so you can't be strategic by forging transactions right to do that you would need to be able to break digital signatures you can't be strategic by retroactively changing the contents of a block because in order to do that you would need to break the CR the security of the hash function that's being used so there's a lot of um you know strategic deviations that you don't have to worry about because state-of-the-art cryptography is great and because we have good cryptography these issues are not a serious concern for a Bitcoin

um now there are things you can do right so the Bitcoin protocol says when you create a block please add a pointer from your block to the existing longest chain and another thing that the protocol asks you to do is when you create a block please broadcast it to the entire network right away and another thing it asks you to do is it says please include as many transactions as possible and you know subject to whatever block size limit there is and please prioritize transactions that have paid higher fees now these are actual decisions that when you create a block you can choose to follow that protocol or you can choose to do something else

and the only way to reason about this is by reasoning about the incentives that it gives the miners there's no amount of cryptography like these are not cryptographic problems or security problems to solve right there's no amount of cryptography or a clever security protocol that's going to force someone to broadcast something immediately or that's going to force them to have heard about some block right the reason that you can point to any block is because maybe as far as you knew that was the longest chain because you didn't hear about something that was broadcast later so these are inherently incentive problems okay so what I want to do on this slide and then um I will pause a little bit for discussion to make sure this is

clear is just try to abstract away a lot of the security details and latency details and all of that from how Bitcoin like really works and try to just zero in only on the incentives okay so what's the setup for the game so uh there's a set of miners every Miner has some fraction of the mining power okay that's just saying that right there's uh some distribution of mining power and X is denoting that at all times every Miner has some directed tree of blocks right so the tree refers to every node in the tree is a block there's an edge coming out of it pointing to the Block it's pointing to they all share the same

root and I'm just referring to the fat distinction between there's blocks that have been created but maybe minor M hasn't heard of them yet maybe because they haven't been broadcast and the ones at minor m is aware of so I'm just using G of M to refer to that okay so what's the actual game so what are the strategies that the players have so uh random Miner is selected to mine proportional to their computational power what do you do when you mine when you're selected you excuse me create a node that's a new block you just made and you add a directed Edge to any other node that you've heard of okay and again you are allowed to pick

any node that you've heard of the game would like you to pick the long but the actions you can take are anything um also each time step you have the option to broadcast any nodes that you've created or heard about to everyone else to simplify the latency and not worrying about like what happens if someone hears about uh something before someone else what if you selectively broadcast we're just going to say there's one broadcast action if you broadcast everyone hears about it and they hear about it instantly okay and so this you can choose to do right so you can create a block and you can choose not to broadcast it or you can choose to broadcast it you can

choose to broadcast it in a later time step that's okay okay and so now what are the payoffs so the previous bullets that defines the entire game the payoffs are just at the end of the game you get reward for every um block you have in the longest chain so let me just kind of parse through this so um uh the eventual payoff is just gonna say as T goes to infinity look at um you know look at the limit of something uh what's going on here is there's some longest chain at time T So among everything that's been broadcast there's some longest chain okay that's uh this now for every minor M they have produced some number of

blocks on the path right on this longest chain that's this and they get reward we'll normalize it to one for every block that minor M has created on the path from the longest chain to the root okay now this is um the slightly interesting thing is the payoff to The Miner is equal to the steady state so this is just the limit as the game goes forever of the number of blocks that they create on the longest chain to the length of the longest chain so it's not just the number of blocks they create it's specifically the ratio of the blocks they create to the length of the longest chain

okay so let me um quickly go through so I will pause on this slide for questions about the model but first I just want to State why did we choose this specific reward function okay so first remember that in Bitcoin there is a difficulty adjustment so what that means is that Bitcoin is set up so that whatever strategies the miners happen to use If it creates orphans creates more orphans less orphans whatever there is one new block on the longest chain produced every 10 minutes in expectation so what that means is that the rate at which the longest chain grows is one

block per 10 minutes and so in particular that means that if I look at uh dividing by the length of the longest chain this is proportional to physical time so if I'm interested in understanding something like how much Bitcoin are you making every 10 minutes that number is how many blocks are you getting per uh uh per extra one length of the longest chain okay so that's a key that's a huge part of the analysis and so I'm trying to spend a little bit of extra time motivating specifically why this fraction instead of just this sum yeah maybe it'll be helpful to just say

like what's what would be the first thing you write down sure sure yes so what I can say is the the first thing that I might try is I might say let me just look at um instead of letting things go to Infinity let me just pick a fixed capital T and say that your reward is just this sum the number of blocks that you create in the longest chain or if I really wanted to let things go to Infinity I might normalize by the number of time steps right so I might say like well I mean if the game goes on you know for a thousand time steps I want to look at my reward per time step and the main thing that I'm trying to point out is that one time step in this

game is not equal to 10 minutes of real life because that depends on the strategies people are using if everyone is being honest and is just building on the longest chain then it is then one time step in this game means the uh the longest chain Grows by one that means 10 minutes has gone by but if they're doing all sorts of crazy things and maybe half the blocks are being orphaned so let's stick with that if half the blocks are being orphaned then that means that one time step really only adds one uh two time steps are needed to add one block to the longest chain so actually two time steps are needed for 10 real minutes to go by okay and so what that means is that I'm

saying you know what let's just put all of that math that we need to do is perfectly captured by just saying that we're going to normalize by the length of the longest chain because the length of the longest chain is exactly proportional to physical time and what I really want to capture is how much reward am I getting per unit of physical time that's a meaningful measure how much reward am I getting per block that's created that's not a meaningful measure can we ask why why is the payoff zero if it doesn't exists sorry that's just a uh that's just a technicality I first made these slides when I was trying to give uh talk to a

very you know mathematically formal setting and uh that's just to be mathematically formal um but you should you should expect the limit will always exist there's no reason and all the analyzes we're going to do the limit will always exist there's no reason to suspect that the limit should not exist the communication network and to what extent it's unrealistic and to what extent would you care if it's unrealistic yes so um in this communication model we have abstracted a way that there's like uh point-to-point communication we've just said when you speak everyone hears right and so that is obviously that's unrealistic for sure right so I know that's not how the Bitcoin network works

um uh right into just to be clear there's two things we've abstracted away one is when you speak everyone hears there's no point to point two is when you speak everyone hears during the same round there's no latency and that latency is not the idiosyncratic now um there is a really nice uh mild how would I phrase it um slightly later in the analysis I will show you how the original authors tried to capture things like latency or connectivity with a parameter um I will Hint it how that affects the analysis and how you should interpret

that um but one thing I can promise is that the analysis is still convincing even if you acknowledge that this is unrealistic it's not how things work um that basically we're going to be as uh pessimistic towards the attacker as possible and when doing this analysis in other words like this strong assumption should only make sure that the result stronger right as far as yes the superpower they don't have or you know even then yes that's correct all right that's correct so for the um yes that's correct

so for the the way that I personally like to State the result so again so I'll mention this near the end there's a range of parameters and variants of this result um that are in the original paper um the one that I find most convincing um is that even if exactly as Tim put it even if you let all the honest nodes communicate instantly and you let them have significantly lower latency than any communication that happens with the attacker that even under and even under this assumption um and the attacker can't do point-to-point communication the attacker has to broadcast to everyone when they broadcast even in these settings there is still something clever

that the attacker can do so that's the version that I personally like um presenting and that's the what I'll present is like the main result so so we also we all know that like the real way that Bitcoin happens is you know everyone it has these separate mining processes right everyone's mining on their own everyone's mining on their own and then at some point someone succeeds right and uh that that is not captured here I've just kind of said like well each time step I'm gonna select someone right so so related to the previous discussion I really want to think of a Time step as somebody just created a block that's what a timestamp means to me okay and um what we know is that because

of the way in which Bitcoin mining is done it is still true that even conditioned on someone just mind the block who that minor happens to be is random proportional to computational power it's independent of the past and stuff like that so the first thing I want to do is just sanity check what is the longest chain protocol in this language right so we've abstracted away all sorts of things but just focusing on the mining incentives we said okay the longest chain protocol says whenever you're selected to build a block point to the furthest node from the root among those that you've heard of and there's this uh subpart that says if for some reason you have to break a tie

break ties in favor of the node that you've personally heard about first okay and you should always broadcast when you create a node broadcasted immediately um and then prior to uh the selfish mining paper okay so you know most most the way that the Bitcoin Community operated they wouldn't have said oh here's a formal game here's a theorem that I believe is true but I think prior to the selfish mining paper it was widely accepted that um if everyone else is following the longest chain protocol and you have less than 50 percent of the computational power in the network then the best thing you can do is just to follow the longest chain protocol as well and there was even this um correct random walk analysis in nakamoto's white

paper where they considered a specific deviation so the specific deviation that they considered was well what if you just try to make your own chain and ignore what everyone else is doing and that specific deviation if you have less than 50 that's a very bad deviation you're just going to waste all of your blocks if you have more than 50 then yes you can make your own chain and you can just take all the rewards um so that part was correct but what had not been previously considered was whether you could do something more clever um and so uh then this uh someone will work that's now referred to as the selfish mining paper showed um this uh clever strategy and uh here's the version I like the phrase so

um if you have at least a third of the computational power then there is something better that you can do than uh following the longest chain protocol assuming that everyone else is following okay and this is the version that um I like the one third is the number that I like remembering this is the even if we do everything reasonable against the attacker but the attacker has 34 of the total uh computational Power they can still uh strictly profit okay so um now what I'm gonna do is present um that strategy I'm gonna build up intuition first and then like I said I

will uh touch on the analysis um so here is uh some quick intuition for why it works so imagine that you are so well connected in the network so this is the unrealistic one this is favorable to the attacker you are so well connected to the network that if for some reason there's ever a tie so you and someone else have two blocks of the same height everyone else will have heard of yours first and this is true just imagine like no matter what the reason is that even if like this one was broadcast first and you heard about this one and then after that decided to broadcast this everyone still hears about this first you're so

well connected and I'll say that everyone breaks ties in favor of you that's how I'll capture that so here is something you can do that's clever if you are extremely well connected like this as you say well why am I in a rush to broadcast my blocks the moment I create them let me just wait until someone challenges me with a block of the same height and then I'll create mine or then I'll sorry then I'll broadcast mine and everyone will hear about mine first anyway so mine will clearly get into the longest chain because everyone's going to hear about mine first and I have this added bonus of getting rid of someone else from the longest chain and remember that we want to increase my

fraction of blocks in the longest chain so this is great for me I'm getting rid of other people and all of my stuff has been getting in so what this strategy would look like is I'm still always building um on top of the longest chain I tie break in favor of myself and the only thing I'm doing differently is I'm just waiting to broadcast until my block gets challenged okay so let me just run through I have a quick animation of what's going on so in the in the uh graph so blue means it's been broadcast so in this uh sample run um the first thing that happens is uh one of the honest miners finds a block and then I find a block and I don't broadcast it because I've I'm in no rush

why would I do that and then someone else finds a block and they broadcast it and that triggers me to broadcast now the block that I found and because I'm so well connected even though the order of operations was that they broadcast first then I hear about it then I broadcast everyone else is still going to tiebreak in favor of me okay and so let's say what happens is that you know I find the next block again and so I point um to my own block I hide it I'm triggered by another broadcast that causes me to broadcast mine and then this is right this is where I'm using the assumption that I'm so well connected that even when an honest person finds an x-block they still point

to mine how this happens okay so um here so so so this is this part of the analysis again is just for intuition for what's going on right so this is a very powerful attacker but if the attacker is this powerful then this is the best strategy you can use why is it the best strategy you can use because all of your stuff is getting in the longest chain and every each one of your blocks also kicks someone else out of the longest chain and that does strictly better than being honest I have a great question um is the assumption that they're well connected separate from the fact that they have more than a third of the hash power or is it like as a consequence of

it sorry those are uh those are distinct assumptions so uh let me clarify first so far for these uh these two intuition slides I'm making no assumption on the fraction of computational power if your computational power is X x could be less than one percent you can still do strictly better with this attack but the key assumption for this attack is you better be really well connected in the network because you need to make sure that if this sequence of events happens that you might you create a block have not broadcast it

then someone else makes a broadcast before anyone else hears about that you hear about it broadcast your own and then everyone else hears about you so as long as you can do that then you can get this X over 1 minus X which is strictly better and that holds for any uh any X you don't need it to be a third for the real Attack that I'm going to go into um I'm gonna get rid of this really strong assumption that you're super well connected and then there's going to be like a teeny bit of math and the math will work out whenever you have more than a third um did that answer the question yes thank you awesome okay

so now let me first state the um state to the strategy and then I will walk through with pictures again what it's doing okay so let me say maybe first here's the um okay so I have pictures coming soon so here's the main idea the main idea is that actually let me say the main idea before uh uh presenting the text so um the main idea is that like you know you can't rely on this like sequence of broadcasting to be able to beat one block with one of yours if somehow though you find yourself with two blocks here then no matter how slow you are at broadcasting everyone will always

believe your chain of length too over some other chain of length one so the game now is to see like well I'm gonna try to get some chain of my own that's at least strictly longer than the chain that others have so that's going to be the game and the downside is that there's going to be some risk trying to do that so here's the text for what the strategy is doing I'm actually going to step through the example iteration first so here the first thing that happens in this um uh simulation is an honest person creates a block and then I find the I find a block now what do I do I point to the longest

chain because this is what the strategy always does and I'm going to check whether I should announce it so one reason to announce it would be if there's another block here it's the same distance to the root that doesn't happen or then there's this special case which is basically saying like well if you know this block points to something that's trying to kick something else out and I'm in danger of not having other stuff to point to it then I should broadcast it but this doesn't get triggered here either now I find a second block I hide that one too because neither of neither of these trigger so this you should recognize is like this is the good situation

because now I have two hidden blocks with two hidden blocks I can sit tight and wait and when I get challenged then I can say well you chat you know the honest network has one block but I have two so even if I'm super slow everyone's still going to mine on top of it okay or I could get even luckier I get a third block here that I hide okay so now what happens is uh the rest of the network uh produces a block and that triggers me to broadcast that triggers this case one there's some other block that someone announced it's the same distance to the root okay so now I broadcast okay so now remember that what's going to happen is that um the rest of the network is

not tie breaking in favor of me anymore I'm poorly connected right so every single other minor heard about uh this honest block first so if they create a block they are definitely going to tie break against me okay so they tie break against me that's bad news it seems like bad news for me and then what happens is this triggers me to have this case one so this block I'm going to broadcast but now I'm also like oh crap my lead's about to run out and I should just broadcast this one too to get this chain of length three in the longest chain and kill two honest blocks okay so that's what the strategy does and then no matter how poorly connected

I am again right so even if everyone you know they I have latency whatever they're still gonna this is still a chain of length three compared to a chain of length two so everyone's gonna build on top of them okay so um so so this disc sorry so this previous example this is kind of like the what could go right so this is great if you find you know two blocks in a row and hide them that's excellent next example is the what could go wrong so I hide a block right because I'm saying like oh cool I'm gonna get my lead of two that's going to be awesome um but instead I don't get a lead of two and now they find a block so what's gonna happen now is that this is going to trigger me to announce with

case one but I'm not safe yet right so what's going to happen is maybe I find the next block if I find the next block that triggers case two because right I realized that as soon as I create this block this is very dangerous to continue hiding this so I published that immediately um and that's good that's still fine the bad thing that might happen is maybe I don't find the next block if I don't find the next block then this one that I hid that's just orphan forever right because now everyone's everyone including me because this is what I want to do to maximize my own future profit books is to um continue building on the longest

chain okay so um so now I can uh state uh so state to theorem right so the theorem is that um if everyone else is using this longest chain strategy so remember that um they are always going to tie break against you so that means you are so poorly connected that whenever you try and do this uh you know broadcasting in response to them you will always be late and on top of that you can't broadcast point to point you have to broadcast to everybody when you broadcast so even under those situations if you have at least a third of the mining power then this selfish mining strategy is strictly better

than being honest okay so what I want to do now I am going to give a taste of the analysis or show you how to set it up and the main thing I want to point out is that um even though I didn't show you the analysis for the lucky selfish mining the one where you win all the tie breaks that analysis is easy so like you know if I was teaching a class I would assign that as like a homework problem I think that's very feasible to do and it's easy because there's no risk right all of your blocks are in the longest chain you just have to figure out how much you're kicking out right and once you figure out how much you're kicking out then that's the entire math for the real selfish mining when you

lose all the tie breaks um there is some risk right there's this risk where you create a block and then the honest people get two right afterwards and then um this is the risk you lose that block the reward is like what if you get two in a row or you get one they get one you get one and somehow we have to you know we have to actually the point is just that we have to do some calculations right there's no way to like just think a little bit and see like oh yeah clearly this is better um we have to do some calculations and you know maybe more evidence that we have to do some calculations is that this is not always profitable right it's profitable if you have lots of mining

power that's because you're more likely to be in the reward than the risk case and it's not profitable if you're you know you have less than that um so again what I want to do I'm going to set up the analysis and try and have as much structure um as possible and then hopefully you'll kind of see how these ideas um could be used for other strategies or other settings um okay so the kind of terminology I'm going to use I'm going to set up what's called a Markov chain um and I think it'll be clear from the pictures what's going on um but I'm going to use this terminology I'll refer to a state I and that just refers to the fact that the selfish minor is created exactly I uh hidden blocks right now

okay so um how does the game start the game starts in this state zero there's a unique longest chain everyone agrees on the longest chain the selfish Miner has nothing hidden this is where the game is right now uh one thing that might happen is maybe the an honest Miner creates a block if an honest Miner creates a block then they broadcast it immediately and we still have a unique longest chain the selfish minor has nothing hidden so I'm drawing this as a transition to say okay we're staying in state zero if the attacker mines a block then now they have one hidden block because they choose to hide this block so I'm going

to refer to the state where now when is State One okay from State One if uh honest minor mines a block then we have this special case right where now we've triggered that there's these two competing blocks and the moment that the next block is found this race is going to end I'm going to broadcast mine if I found it the honest Network's going to broadcast theirs if they find it this is like this special State I'll refer to as the race um but if the selfish minor mines a block then now they have two hidden blocks so we go to this state okay and um let me just go through uh this this last one I'll skip the rest of the transitions but hopefully you can kind of see the picture that we're

building as we're saying like Okay from this state what happens if the honest and honest Miner finds a block and what happens if the selfish Miner finds a block right so here no matter what happens we're going to go back to state zero but um you know it's uh but if the honest Miner finds a block then it means that the honest network is going to have this in the previous block and the longest chain if um we find a block then it's going to be us that has two blocks okay so um so all of this is just to say this is how you build um this picture and this picture kind of like has different states that stores how much is hidden right now and um

let me skip this too yeah yes this is the kind of type respect and the information we've talked about before because um yeah so can you first like it was really nice state where you're like oh you know if if you're the taper time zone was broken for you you can just cancel one on this block with one of your blocks and you just keep doing that because that's a great starting point then you have this nice situation that said okay well even if files are broken so I always lose if I have two of my own blocks in a row I can use that to cancel one on this block and so I feel like that's kind of like the first simplest strategy you might try in that case right so don't worry about like canceling more than one

last block at once and so just like somebody extra complexity that you see on the slide is because you're like well you know why stop it can't say one on this block like maybe I should not only came as many as possible so in the off chance I have this big lead let me just make sure I sort of you know rather than wasting two of your blocks to cancel one on this block you're going to be waiting you know you're going to be using K of their blocks to cancel K minus one on this box okay that's the reason we need like this big state space coming off them yes yes can I just clarified the state transition from two when the when the selfish minor has two hidden vlogs and an honest minor mind something why

did we go to zero great um so this is let me go back to the so let me first just confirm that is correct let me go back to um the picture here so let me actually step through this and say how the states would be so here we started in state zero I found the block and hit it so now I'm in State One I found a second block and hit it now I'm in state two I have two hidden blocks I found another block and hit it so now we're in state three I have three hidden blocks now they found a block that triggered me

to broadcast this so now I only have two hidden blocks right now also if they find the next block this is the transition you asked about so I'm currently in state 2. they found a block and that is going to trigger me to broadcast both of these I see I'm basically like skipping the race exactly exactly um or sorry so I'm skipping the uh I'm basically saying uh every transition in that picture corresponds to one time step or one new block being created so it's not like every transition corresponds to me doing something with a block I wanted every step to correspond

to a new block has been created and then when that block is created what changes so in this case when this block is created a lot changes so that's why it was kind of like a big single transition that went from two to zero um incidentally so for here the race the race state is um is different the race state is because I hit a block here so now I'm in state one now I enter the race state and from the race state if um I find the next block now we're going back to state zero if they find the next block we're also going back to state zero so that's why this race state is special and different from just being in state 1 or state zero

again um did that in did that answer your question uh this part about why go from cool yeah but what about the state transition at the like n log going back to n minus one like The Black Arrow from three to two where does that correspond the diagram we went over yes so that is here so currently we're in state three so we have uh lead of three and now the next block is going to be created and it's not ours so that triggers this and now we only have a lead of two but like theoretically if we were to like cash out or like broadcast the lead we'd still end up with three right like so

why does the state go back to two good so um I think I can I think that I will do a better job answering that maybe like five to ten more minutes um internet talk um basically what I want to say is that um so far I have not actually said what does this how am I going to do analysis from here I haven't actually said exactly what's going to happen all I've said is like well this is one way to describe the state that we're currently in and I haven't yet said why like how are we going to cash out basically or how are we going to compute rewards so I think when I start talking about how to compute rewards it'll be convenient that we describe the states in this way

so like if it were me I'm like a very nervous person if it were me I would just like freak out and post all my hidden blocks all at once and I assume we're gonna see why that is like a strictly inferior strategy got it so I am not going to explicitly do those calculations I think what Tim said is the best quick intuition I can give so just to repeat what Tim said is that if you so if we do what you said where like oh I have a I have K hidden blocks and you found one I'm gonna publish okay then I have now used K of my blocks to kill one of yours so that's a ratio of

like K to K plus one right okay um uh so or sorry I'm like uh how would I phrase it I'm I'm decreasing the denominator by one and that's consuming like K of my hidden blocks to do so If instead I can decrease the denominator by K minus one that's better because now the denominator is getting even smaller um when I do this so basically so the the idea is that I want to get rid of as many honest blocks from the longest chain as possible and get as many of my blocks into the longest chain as possible the exact trade-off between like is it better for me to have one

extra Block in the longest chain or remove five of theirs from the longest chain that's what requires this kind of analysis to exactly figure out but definitely if I can just say remove one block or remove K minus one it's definitely better to remove K minus one so you want the honors miners to waste more time making more blocks that you want to keep the satisfaction yes that's absolutely correct and if it helps one way to think of this is so we already said the reason that this is happening is because um there's this difficulty adjustment so if you want to see the full chain of what's happening is that by getting the honest Network to waste their

computational power you are lowering the effective difficulty to create a new block right because if really there's like a hundred units of power in the network creating blocks but you get them you know if if you're 40 and they're sixty percent but they operate as if they're only forty percent because so many of their blocks are getting orphaned then now what's happened is you have lowered the effective difficulty it used to require you know 70 leading zeros and now it requires 69 leading zeros or something so what you've done is by getting them to waste their stuff it's now easier to create blocks and so more of the blocks that you create twice as many are going to wind up being

successful so if it helps to see that direct chain that's kind of the direct chain for what happens is they waste their stuff that lowers the difficulty by lowering the difficulty your hash rate is now more um is now more successful at producing blocks than it was before did that um did that answer the question artificially having the difficulty looks higher than it is um yes that's correct yes that's correct and that's because the uh the difficulty adjusts based right so remember that all of the Bitcoin adjustments exactly it's only based on that chain itself right so that chain itself doesn't know that

there's equally you know it doesn't know that there's twice as many orphan blocks going around that it does the difficulty adjustment based on its own um its own chain only okay oh one more quick question just make sure you find us in the intuition if tie breaking is just done by at random you will still work I guess it's not right so if tie breaking is done at random that's actually better for the attacker so here's what would change is um let me go back to this so if tie breaking is so so let me repeat so the very first thing I showed um here this we said tie breaking is

perfect for the attacker definitely tie breaking randomly is worse for the attacker than this here we basically said the attacker is losing let me go to here the attacker is losing every tie break compared to this winning sometimes is better so the reason that would be different is so this is the same if you are the uh if you're the attacker you're always going to tie break in favor of yourself and even if the protocol says please do it randomly you're going to be like no I'm tie breaking in favor of myself if the rest of the network finds the next block then if they are tie breaking randomly then sometimes they'll happen to point

to you right and so this means that you can actually get a little bit of extra reward sometimes just by luck in how the randomness goes so the so the number let me go to here so if you change the protocol to ask everyone to type it randomly this one-third number becomes one-fourth so that's another number that um happen to be a cleaner number to remember from their paper that if instead of tie breaking against you tie breaking is done randomly then you need 25 in order for this attack to be strictly profitable um did that answer the question yeah thank you awesome

man a good quick one I don't know whether you're going to get into this specifically but is this um does this fully explain the reasons why Uncle blocks get rewards in other proof of work so I actually think it is the opposite so um Tim maybe can correct me if I'm wrong but I think that uh giving Uncle rewards is actually uh makes selfish mining more profitable because now you are less stressed about that's risk in the first block it's not I don't remember the ethereum team had was aware of that I mean my understanding is the basically ethereum wanted to crank with block grid

yeah or something like that and so that means you're just going to get a lot even if everybody's honest you're gonna be getting a lot more kind of more things and so I almost like the the the uncle rewards are optimized for fairness in the all honest case but then like you say Matt when you do this analysis you know you realize that actually if there's selfish mining which we can discuss maybe it's what extent it is so defining it but at least in principle it makes it actually safer for the attacker yeah that's right yeah um yeah and I can just repeat my understanding is similar to Tim's that like um assuming everyone is honest a well-connected minor would have less orphans and so assuming everyone is

honest it would be disproportionately profitable to be a well-connected minor because you would have less orphans so my understanding was that the uncle rewards were to try and make it more Equitable between well-connected and poorly connected minors um so that even if you were poorly connected and your blocks were getting orphaned more often that you would still get some report for that quick comment is it obvious that um it's only better for the attacker because correct it's not obvious that's why I was deferring uh that that's why I wanted to confirm yes exactly but I think when the dust

settles it is in fact true that it's easier to attack ethereum right yeah so that is my recollection but I don't remember so yes I don't remember I'm not comfortable saying I remember that confidently and that that's correct but that's consistent with what I pretty remember but um the good news is that the analysis that I'm about to show you the kind of analysis is very easy to adapt to handle Uncle um uncle blogs Uncle rewards too and then you just have to change like a couple numbers and Chase through the car I mean it's not going to be pleasant you have to chase through you know some calculations but like uh the setup is not hard so I think what I will do so

I'm clearly not going to get to any of the uh bonus stuff that I mentioned at the top but I will at least just try and finish wrapping up um how do you actually do this analysis so here's the goal I want to compute three things okay the first thing I need to do is I want to compute in this diagram what is the fraction of all time steps what is the fraction that we spend transitioning from State eight to State X to State y so that is something that can be done um if you've seen Markov chains before you need to compute this thing called the stationary distribution once you compute the stationary distribution these probabilities follow so this is something that can be done

the second thing we need to do is we need to say well when I take a transition from X to Y how many blocks does the attacker get in the longest chain during that transition and let's do the same thing for the honest miners let's see for every transition when I take that transition what is the number of blocks you get in the longest chain during that transition if you can compute all three of these numbers then there's a very simple formula that says what is the fraction of blocks created by the selfish minor so let me just quickly walk through um let me be clear so this is a this is a theorem I'm stating and it applies to any strategy right so this is why oh you

can just modify these numbers if you can compute these numbers for um uh with Uncle rewards then you can compute solve push mining with Uncle Rewards so what's the numerator the numerator is just saying well sum over every transition the fraction of steps you spend taking that transition times the selfish blocks during that transition the numerator is just on average during a state how many blocks does the selfish Miner get the denominator is doing the same thing it's summing over every pair of states the fraction of time that you spend going from X to Y times now I'm just summing the selfish plus notice blocks you get during that transition so that's the average of you know like a average over time steps of the

um total number of blocks that enter the longest chain um so like I said sorry so this means the goal is just I need to say how do I compute all three of these things for each pair of states okay and that's the entire game so this is the framework if you have any strategy you want to analyze and you can do this computation then you can analyze that strategy and find out what its reward is so I told you so I'm going to skip this is the calculation heavy part um is finding the stationary distribution of this Markov chain it's not that bad but it's calculation heavy and I'm gonna skip it um the easier the cleaner part is figuring out how to do this Counting

okay so here's what I want to do I want to say for every block when am I going to count it I'm going to count it during the transition when that block is first published and I know during this time step that that block is in the longest chain forever okay the first transition where I know that that block has been published and is definitely in the longest chain forever that's what I'm going to count it I'm not going to count it during any other transition and I'm not going to count any other blocks because I might be wrong about that so for example this is the Full Table of counting let me just zero in on uh let's

say this one here so when I transition from State 0 to State 0 to 0. the attacker produces no new blocks in the longest chain the honest group has produced One new block that is broadcast during this round and I know it's going to be in the longest chain forever okay how about when I go from X to x minus 1. when I go from X to x minus 1 this means that I had a lead of x the honest Group found a block that block is actually not going to be in the longest chain they broadcast it but I know it's not going to be in the longest chain so I'm not going to count

that because that's going to be wrong what it does do however is it triggers me to broadcast one block and that block I know is going to be in the longest chain so I'll count it okay so this is just the the others uh you know follow similarly um this I will skip but it's just there's another way to count if you want um I just wanted to show the flexibility of this but as long as you find some way to count every block during exactly one transition then you have a correct scheme and that's it so that's all you have to do so um just to repeat this first step this is the calculation heavy part it absolutely can be done it's finding the stationary distribution of the Markov chain but it takes some calculations

this uh these two these two are easier you just need to be a little bit clever sit down and focus and then um you know the numbers you have to deal with are you know zeros ones and twos it's not that bad okay um and then it turns out you got this uh this function this is the reward you get from selfish mining um I don't know how to explain why you get particularly this formula but this is what you get and it's bigger than Alpha um if and only if Alpha is bigger than a third um so let me so I have basically no time so maybe I will do the wrap up with um this on the slide and I will just State uh I mentioned

earlier that um there was some way to talk about abstracting away the network protocols with one parameter and the original paper uses parameter gamma to refer to that they basically said like look however well connected you are in the network or whatever is going on let's just parametrize that by gamma let's say that I don't know whether it's because of latency I don't know whether it's because of point-to-point communication let's just say that if you happen to try this specific thing of wait till they broadcast then I broadcast that a gamma fraction of the time you're going to succeed let's just parametrize it by that and as long as you no gamma you can do the analysis um and so they did that there are other formulas um

that I'm not going to get into and then maybe the very last thing I will state is just that um there was follow-up work that uh that I was going to discuss but I'm not going to it shows that um you can do a little bit better this selfish mining is not the best thing you can do and the best thing you can do is not that much better so as long as you have less than 32.9 of the mining power then there is nothing clever you can do okay so that is a theorem and that does mean that if you're really concerned about selfish mining you only need to be concerned when there are large miners so not 50 it's not a 51 attack it's like a 33 attack but you still need to have 33

in order to do something clever um okay so let me pause uh let me pause here I was going to pause for a discussion but I guess I'll pause because it's the end of the talk um instead