Economic Censorship Games in Fraud Proofs

Transcript

Oh, hello everyone. Welcome to the presentation. So, today I will talk about economic censorship games in fraud proofs. This is a joint work with Ben Burger and Ed Felten from Offchain Labs and Benny Sudakov from ETH Zurich. I'm Akaki Mamageishvili. I'm a researcher at Offchain Labs. So, first let me give you some motivation. We know that Ethereum needs scaling and optimistic rollups are providing the scalability. And then this is done by moving the execution off the chain. So, to give you a little bit of mechanics how optimistic rollups

work. This works as follows. So, users send transactions to centralized sequencer and sequencer passes transactions to the execution stage in some ordering and in case of Arbitrum, that's mostly first come first serve with some priority. And when there are enough transactions to process, then sequencer posts a batch or recently blob to Ethereum. So, from time to time the state is updated on the Ethereum governance contract.

Um there are parties called validators that post the latest state on the Ethereum. And if there is a disagreement then uh fraud proof starts. There is a dispute that fraud proof protocol tries to resolve and this is interactive protocol which is happening on layer one, which is Ethereum. And there players send their moves alternately. So, first defender, then attacker, etc. or the other way around.

Each move is an Ethereum transaction, L1 transaction, and they promise is that defender is guaranteed to win this fraud proof game if all her moves will be processed. And this is exactly what we'll be studying. So, in the old protocol of Arbitrum, there was one validator that was posting a claim and it could be challenged by any number of other validators and then they would play this bisection game and one player out of two would always lose. But the winner wouldn't guarantee that this is the So, all players had to play this fraud proof game and in the end the winner

would be the probably the honest party. And bisection looked like this. They would present the hash of the middle state. So, what is the state hash in the middle of the execution, exactly in the middle. And if they were different, then we know that problem is in the first half. If they were the same, then we know that the problem is in the second half. So, the game moves to one of the halves. So, in logarithmic number of steps, the dispute is resolved. And then we come down to one step. So, there has been an improvement to this protocol which would take n minus one rounds and now we have this new protocol called Bold, which allows the game to be

resolved in one round, no matter how many how many players there are playing with different version of their states. And I'm not going to this details of the Bold protocol, but here also the idea is that it's interactive and defender needs to get processed all her moves. So, there are some references and the most relevant one is the first one, which is by Fox, Pi, and Resnick and we are generalizing their setting where they were studying the economic censorship for one transaction only because their setting was auctions. In our setting, the parties or the defender

party tries to get processed n transactions instead of just one. So, that's the main difference. We know that there is some challenge period and at this point it's set to one week. Even right now it's one week one week. And this is trying to solve the strong censorship attack where if someone gets 50% of the stake, they can just block you out from the protocol, from the from all blocks. And one week is set so that Ethereum would hard fork from this malicious majority.

But now we will talk about other form of censorship and assess how good is one week delay period. So, our model is of economic censorship attack where attacker can just bribe the block proposer not to include defender's transaction. So, it's not exactly even an attack because it is even socially acceptable to take transaction that pays the most and attacker can just bring transaction that pays more than defender's transaction conditional that defender's transaction is not included.

And this can be modeled by very simple auction. So, the defender offers inclusion tips something and if attacker pays or bribes higher then proposer will do whoever pays the highest. And then the game looks like this. If attacker succeeds in bribing, then defender has less time to include all her transactions. But on the other hand, attacker's budget goes down while defender's budget stays the same because defender didn't didn't pay anything. Her transaction was not included.

But if attacker does not succeed, then defender is one step closer to victory. So, one less transaction to post on chain. But on the other hand, defender's budget goes down. So, there is a trade-off. Do you want to win the current block and include your transaction or not? And that depends who bids how much. And we try to solve basically this game and solve what are the optimal strategies of playing this game of bidding. And who will win given some realistic parameters, defender or attacker? And that will give us recommendation how large should be the defense budget.

Okay, so now let's go to more formal model. We have two players. Alice for attacker and Daria for defender. And we have total number of rounds, which is how many blocks are in one week. For example, then n is number of rounds that defender needs to win. So, that's number of transactions defender wants to include in the block in the in the blocks during this one week period. And then attacker has budget and defender also has budget denoted by A and D.

And to give some intuition what we think these parameters are, Alice's budget attacker's budget is basically how much she can steal from the wrong claim of rollup state and in principle it's all the value that is breached to rollup or it's upper bounded by that. And defender's budget you can see it as attacker's deposit. So, all these optimistic rollups require some kind of deposit from any validator that makes a claim. And if the claim is wrong, so it turns out that it was an attack, then we can just confiscate that deposit and give it to defender. Or it can be some any other number you

you can come up with depending on the protocol. So, now question is how large should attacker's budget be so that she can win? And the opposite question is how much should be the defender's budget so that she wins. And we study three versions of this game where we vary number of proposers. In one we have only one proposer, which is the current state. And in the other version we study multiple proposers. So, it it can be either multiple concurrent proposers or fossil setting where we can have actually multiple proposers.

And another is proposer types and I will explain what are the different proposer types. So, simplest game is denoted by G1 and here we have single block proposer. So, in each round they are dealing with one proposer. And then the defender offers bid, which is less than the budget or the current budget. And then the let's say attacker observes this bid and can offer some other bid, which is less than her budget or current budget. But actually what we show is doesn't really matter who observes what and when. Optimal strategies don't depend on this assumption, but it it just easy to think this way.

And then the winner budget is deducted by the bid and we move to the next round. And so, first result is actually very simple and intuitive. We have uh if and only if condition for Alice to win. So, if the inequality holds in the other way, then Daria wins. And the intuition here is that Alice needs to win T minus n plus one rounds at least while Daria needs to win n rounds. That's by definition.

And then the ratio between their budgets needs to be compared to the ratio between these numbers two numbers. And the proof is actually quite trivial at least in the hindsight. So the strategy of Alice is that as soon as Daria bids higher than D over N then let Daria win because Daria is overpaying. And with this condition Daria cannot win N rounds. And on the other hand with this condition again Alice can afford that.

As soon as Daria bids lower than that then attacker will outbid Daria. So that's basically a proof of actually both directions. So for the other direction you would do the same. Daria just bids D over N and Alice cannot afford to win T minus N plus one rounds. So this gives us very simple condition for given parameters. Let's say if Arbitrum 10 billion dollar worth assets that can be stolen and defender needs to make 60 moves and there are 50,000 rounds to make the 60 moves then Daria needs at least 12 million

dollars to guarantee that she's always winning. So you just plugging in the numbers in that inequality. And solve for Daria's budget. So this game we can extend to slightly more complicated game where we have some special rounds where the proposer is not looking at who bids what exactly but looks at bids and builds the best possible block. So there is this greedy algorithm where proposer sorts transaction by decreasing priority fees and as long as she can include transactions she includes. That's a simple greedy approximation for knapsack

optimization problem. And here now Alice needs to fill up the whole block with her transaction and that means that if blocks block size is large then then she needs to pay K times larger bid than Daria makes. And if you if you look at the numbers at least this was the at the time of writing this paper the gas limit was 30 million gas at that point. Now it's 60 so it gets better now. So now it costs Alice double to censor in special rounds

Daria. Now but in that case she had to pay 59 times more. So she had to fill up 29.5 million gas so that Daria could not squeeze in her half million gas bold transaction because that's the size of a transaction that defender needs to make. It's quite large transaction. And if we assume that at least 2% of the Ethereum proposers run this heuristic for building the block then it improves the situation for Daria.

But we wanted to solve this exactly like find the ratio between budgets so that Daria wins. And we could actually not find it exactly but we found recursive formula how to calculate given how many rounds are there, how many transactions Daria needs to include and how many special rounds are remaining. So we have a exact formula how to calculate that and for any setting we can directly solve what needs to be the ratio.

And yeah we can solve this using very simple dynamic program but what we are interested in what would be the ratio between the budgets for our numbers assuming that 2% of the proposers are 2% of the rounds will be special then we would get this ratio between the budgets of almost 2,000. So with the same numbers 10 billion secured and defender needs to make 60 moves Daria now instead of 12 million needs 5.6 million. So that's an improvement.

More than two factor in improvement. But actually what we can observe is that if uh number of rounds is large and also uh K is not too large asymptotically the same strategy of bidding D over N is actually the optimal strategy. So we can obtain upper and lower bounds very tight on this ratio that we are looking for. And the strategy basically remains the same. So only mathematically we are interested what is exactly this value otherwise for large numbers and usually we have large numbers large number of rounds and

this K is usually small compared to T. So next extension is with multiple proposers. But now the idea is that you need as a defender any of the proposers to include your transaction not one particular or five of them or N minus one of them but any of them. So one is enough. And then it gets actually much better for the defense. And the payment rules that we looked into were symmetric and most logical in our opinion that uh Alice just the attacker offers some

fixed amount C to any proposer that doesn't include but doesn't make conditional payments while Daria can make conditional payments like pay much more to one proposer that is alone to include and pay something else if if multiple of them include. So with this special type of payment schemes we actually found very similar condition inequality to the to the original one where basically now Alice needs M times larger budget if there are M many proposers.

And there is only tiny gap so it's not if and only if condition. There is only tiny gap or asymptotically there is no gap. But in real numbers there is some gap where we don't know who would win. But if Alice's budget is large enough and or her budget budget is small enough we know that when she is winning or losing. And also if her budget is low enough we don't know it with probability one but with overwhelming probability.

So that there is this one caveat. So so far we only studied budgets as a constraint but in reality you may care how much you are spending. And you may care optimals about optimal strategy for saving the budget instead of bidding D over N in any round because D over N is actually quite large number if you think about D as 10 million and N 60 that's like almost 200,000 uh keep and nobody wants to start bidding 200,000 per transaction.

So then it's interesting how the optimal strategy looks like. Also in realistic scenario in bold the attacker can play multiple games at the same time and it's not clear how the optimal strategy would look like in that case. And we also only looked at priority fees and not the base fees but sometimes base fees can be very high and it would also be interesting not if the base fees were high by itself but if the attacker would start increasing base fees would that affect anything or not.

So that's all from my side. Thank you for your attention and happy to take questions. >> [applause] >> Do you have any questions? Thank you. How does bold react to increasing gas limit to every block? Like to 60 million. Yeah so as I said it becomes defense easier in special rounds.

It doesn't so this kind of defense now in special rounds attacker needs to outbid 120 times instead of only 60 times. And if there will be let's say shorter block times you would also have more rounds to play and that's better for the defense. Another question behind. I'm not sure if if it's the right question but how would that change dynamics if there are like multiple attackers but a single defender? Have you looked at

that? Yeah so it actually doesn't matter. As long as you are a defender and you include your transactions. It doesn't matter who is making a move against you. But of course we wouldn't have to assume that they have some common budget. So we would sum up their budgets. So if you just multiply attackers budget because there are many of them, that would be much worse for defender because then attackers would have more budget. But otherwise no no change. Thank you. Thank you.

>> [laughter]