Economic Censorship Games in Fraud Proofs

Transcript

See if this works. Okay. Hi everyone. Uh buenas tardes. Um my name is Ben Burger. Thank you so much for coming to this talk. Uh so I'm going to tell you about joint work uh with uh Ed Felten, Akaki Mamageishvili. Both of these are my teammates at Offchain Labs. And with Benny Sudakov who's a professor at ETH Zurich. Okay. So I'm assuming that everyone here has heard and knows about L2s. Uh but still I want to give a very very oversimplified introduction to what these are so we all sort of have a similar mental model to think about about these uh in the context of uh of this presentation.

So layer 2s as we all know, uh this is uh the main scaling solution for Ethereum today meant to increase Ethereum's limited uh throughput problem. And a layer 2 uh like uh any blockchain will receive uh process and order a sequence of transactions. And the computation of each such transaction updates the state of the layer 2. Um and every once in a while, um uh the uh there will be some party which uh posts the current state of the L2 onto Ethereum with the goal of convincing Ethereum that this posted state is really the true result of the computation. Um so and the idea is to offload the expensive computation off of

Ethereum and use Ethereum just as a means to record and verify that the computation went correctly. Uh so in this picture, uh these uh orange rectangles at the bottom, these are uh like the intermediate states uh resulting from the computation of these subsequences of transactions. And each of these orange uh states will be posted onto Ethereum at some rate. In the case of Arbitrum, this happens roughly uh once every hour. Okay. So of course, what is the challenge of such a system? Uh how do we convince How does the layer 2 convince Ethereum that the posted state is indeed valid? And so, there are two main approaches for doing this today. There's the ZK roll-up approach, which I will not talk about, and there's the optimistic approach, which is the uh main subject of this uh

talk. And so, how do how does the proving mechanism work in an optimistic roll-up? Well, each interested party can submit their claim on what is the current state uh of the layer two. And in case that there are more than one uh claimed states, then there is a dispute, which is resolved via an interactive protocol, which is run uh and governed by a set of smart contracts on Ethereum. And this mechanism is usually called a fraud proof, a fault proof, or sometimes a dispute resolution protocol.

And the idea is that uh at a very high level, without getting into the details, the competing parties will submit moves uh to this protocol, and each such move uh is a uh an Ethereum transaction, which sort of reduces the dispute in question uh in a recursive manner. And when designed correctly, uh these systems have the very nice property, uh it's called sometimes a one out of n property, that the honest party that represents the correct uh claim is guaranteed to win, if, and this is a very big if, all her moves uh indeed get processed and included in the canonical uh L1 chain.

Okay. So, as I said, these protocol moves are Ethereum transactions, and because of that, they might be prone to censorship, which in this context is defined as any malicious activity, which is intended to delay or exclude the inclusion of a transaction from from L1. And in the context of fraud proofs, the censorship of honest moves, uh what could happen is that the wrong state can be can get confirmed in the end, uh which is, of course, a total catastrophe uh if this happens.

And so to mitigate against this possibility the parties in these protocols get a significant time window to have all the required moves processed on chain. And this is this time period is called sometimes it's called a challenge period in different context it's called a withdrawal window. And the idea is that if a party's timer run runs down to zero then that the claim that that party represents gets disqualified from the from the protocol.

And so today this challenge period is set to about one week in the major optimistic rollups. And this is aimed primarily against so-called strong censorship attacks. Whereby the the potential attacker is assumed to control over 50% of the L1 stake. In which case it has full jurisdiction over which blocks are added to the canonical L1 chain or not. And so this attacker will decide to remove a block that contains the honest parties moves in the fraud proof system.

So this is of course the doomsday scenario for Ethereum. Um but but there are other forms of censorship that are possible much simpler to execute. And it's not clear how the challenge period defends against these types of censorships. So this brings me to the topic of this work where we consider what we call economic censorship attacks. And in this attack the attacker what it will do so these attacks exploit the fact that the L1 block proposer at any block has full power over the contents of the block. And so the idea is that an attacker will go to this block proposer and try to bribe him to

exclude the honest parties transaction from the block. So the scenario that I want you to have in mind is that uh if the defender or honest party that submits the move offers the proposer a priority tip, total priority tip of P, then an attacker will try to will offer a bribe of B to the block proposer and the bribe will be successful if B is greater than P. So, of course if if this bribe is successful at some block, then what will happen? Well, the defender's move will not get included in that block and so it's timer ticks down by by one block and and and so the time to get the moves on chain

decreases. On the other hand, the attacker paid the bribe and so its budget for future bribes decreases. On the other hand, if the bribe is not successful, well, the defender is one step closer to victory because it got its move in, but the defender also has a budget and that also decreases. And so, the goals in this project were to sort of try to understand the dynamics of these sorts of attacks in the context of a fraud proof systems. In particular, we want to understand we wanted to understand what bidding strategies or what strategies the players will use, what are the optimal strategies, um and ultimately we want to to know who is expected to win this sort of contest given the

parameters of the of the system. And in the end, we want to understand what is the meaning of all this uh for the security of optimistic rollups. Okay. So, with this goal in mind, we study we studied a stylized multi-round game model between an attacker that wants to censor, a defender, which is the honest party, and L1 block proposers. And this multi-round game is parameterized by these four parameters. T, this is the total number of rounds corresponding to the challenge period, the length of the challenge period, and this is the number of of those T rounds that the defender needs to win. I think of this as the

amount of transactions the defender might need to put in the to conclude in the fraud proof protocol. A is the attacker's budget for censoring and D is the the defender's budget for getting all his moves on chain. And in this work we study three variants of this which differ in how a round is conducted. And the main question that we try to answer is how large does the attacker's budget A need to be relative to the defender's budget as a function of all these parameters such that it can guarantee victory in the game.

Okay. So the first model I and now I want to explain go more deeply into the results. So the first model that we study we call the G1 game. This is like the straight most straightforward model model you might think of for this which models a world with alternating rational block proposers. And so it each round corresponds to a block and what will happen is that the defender will offer a bid B. This is like the tip that I talked before which is upper bounded by her budget D. The attacker will get to observe this bid and then offer a counter bid B prime again upper bounded by the budget A.

Um then the attacker will win the round if and only if B is smaller than B prime. And the winner of the round will get her budget deducted by exactly the the amount that they bid. And then a new round begins. And so the defender's goal is to win N of these rounds. This is just a single round what I explained here. And well the the attacker wants to to win essentially the the T minus that. Okay.

So, this brings us to like and what what can we show here? We show that in this game as I presented, the attacker can guarantee victory if and only if this inequality holds. So, if T minus N plus 1 divided by N times D is smaller than A. And so, what this shows you is that the larger the challenge period T is, the more funds the attacker needs to use in order to guarantee victory, right? If T if T increases, then then A needs to be bigger as well in order to be able to guarantee victory.

And so, this is consistent with our intuition that the bigger the challenge period is, the more secure the optimistic roll-up is. And I want to go over the simple proof of this just so you get an idea, and I'm going to prove the if direction. So, let us assume that this inequality holds between the budgets, and I want to show you how the how the attacker can guarantee victory. Well, consider the following strategy by the attacker. What it will do is it will see that the at any round, it will see what the defender bid. If the defender bid more than D over N, then it will just let the defender win that round.

Otherwise, the attacker will match the the defender's bid so that the attacker wins the round. And the observation here is that the defender cannot win the entire game because she doesn't have enough budget to win N rounds. On the other hand, the attacker does have enough budget to to do the strategy and win the attacker's required number of rounds, which which T minus n plus one. Okay. So Okay. So, this is like a very simplistic model, but still to get an idea, what does this mean for example in the case of Arbitrum Bold, which is Arbitrum's fraud proof mechanism? So, if you assume

that the budget of the attacker is $15 billion, which is depending on what day you check is roughly the TVL of Arbitrum One. And plugging in n equals 60, which is roughly the amount of transactions in one path of bisection that that the defender will need to do. And if you plug in t equal 50,000 50,000 blocks, which corresponds to one week of a challenge period, then what this tells you is that the defender can guarantee victory only if it has at least $18 million.

Okay, so that's what this tells us. And of course, $18 million sounds like a lot. Which motivated us to sort of refine the model. And and so so we can get better results essentially. Um and so and so this motivated us for to study the next variant. Uh which we call the G1 sub K game. Here K is some constant larger than one. And this game is very very similar to the game I showed you before. But now we have now two types of rounds. We have the regular rounds, which are exactly like before.

And we also have special rounds. Uh which are conducted as follows. Basically, they are conducted in the same way like a regular round. Only that in order if the attacker wants to win the round, it needs to outbid the honest party by a factor of K. So, these are rounds where it's much more expensive for the attacker uh to uh to to win the round. And and so uh and so in addition to the parameters TN and the budgets DNA from before, we also the game is also parameterized by the like the configuration of regular and special rounds. So we assume in this

simple model that both players know exactly in advance which rounds are special or not and they can maybe take advantage of this in their bidding strategy. Okay. So now what is the motivation or where do these special rounds come from why why do we even think about them? Well so Uh, today it is estimated that about like between two and five percent depending on who you ask for the analysis between two and five percent of the ethereum proposers Um, don't like the way that they build their blocks is not through the more common proposal builder separation or MEV boost framework

but instead to build their blocks they rely on the default block building software Um, that is that is provided by the by the execution client by by essentially all execution clients of ethereum. So this is like they consider only the what's called the local block instead of like externally built blocks. And the way that this block building algorithm works essentially is that the the proposer will look at all transactions in its mempool it will sort them by decreasing order of priority per gas and it will just include the transactions it will include transactions in the block one by one as

long as there is still room in the block but the block has a gas limit. Okay. And so why is this relevant to us? Well, in the case of bold a typical bold transaction in the fraud proof consumes around 500,000 uh gas. And when Fusaka uh uh will will deploy in in a few weeks, uh the gas limit in Ethereum will be uh around 60 million gas. And so, what does this means? It Assuming that the bold transaction that the honest party is willing to put a priority fee, which is the highest one among all the regular transactions in the mempool, which is I think it's a

reasonable assumption, then if an attacker wants to censor that transaction when the block proposer is of this type, it will need to submit to the public mempool uh more than 59.5 million worth gas worth of transactions with a higher priority fee than the bold transaction. And so, this is the this is the where this parameter K comes from. This is 59.5 over 0.5 uh times as much as the defender would pay to to get the transaction So, so, so, so, the the bottom line here is that to to censor here, the attacker needs to pay 119 times more than the defender would pay to get the

transaction in. Okay. So, okay. So, now just a bit more into the the analysis of or what we did here. So, to recall, our goal here was to again understand how large the the attacker's budget needs to be uh in order to be able to guarantee victory. So, to this end, we we define as a tool this curly A expression, uh which is the the minimum budget A such that the attacker can guarantee victory given the other parameters of the game.

And our goal here is to calculate curly A, basically telling us how much the attacker needs to bring to the table. And so, we prove first dilemma that this curly A is uh is linear as a function of D. And also, that it's only dependence on the special round and regular round configuration is just on the number of special rounds, but not not on their location within the entire sequence of rounds. So, what this means is that we can redefine curly A to be a just a function of T N and S where S here now is the number of special rounds out of those T rounds, which is the minimum number R such that the attacker can guarantee victory given

T N and S if and only if the ratio between the attacker's and defender's budget is at least R. So, this was a lot to digest, but just to give a flavor, what we proved in the first theorem for the simple model is that in in the case that there are no special rounds, but that that was the previous model, curly A of T N and 0 is T minus N plus 1 over N. So, this is the ratio between the the minimal ratio between the the budget such that the attacker can win.

Um okay. So, for a very long time, we tried to find a closed form for like a nice formula for this curly A, but we couldn't. Um but what we did do is is find a recurrence relation that it satisfies. So, basically there are these boundary conditions that allow us to compute it for like edge boundaries, and we also have the recursive step that tells us how to compute curly A of T N and S given like smaller instances of of this function. And so, I'm not going to go over over all of this, but uh the observation from this is first of all, because of this recurrence relation, this means that we can compute

or calculate this curly A in time which is O of T N S via dynamic program dynamic programming, and this is feasible to do uh for the parameters that we find in practice. And also another artifact of the proof is that the optimal bid uh by the defender is always a fraction of her budget, uh which only depends on T and N. So, it doesn't depend We don't need to assume that the defender knows the attacker's budget or something like that. Uh so, if we believe this model and we again plug in the relevant parameters for bold, we find that this ratio is uh 2,718, which again if you assume that the attacker's budget is $15 billion, then

now the defender only needs $5.5 million in order to be able to uh to get to to sort of mitigate this economic censorship. As opposed to the $18 million from from before without special rounds. Okay. So, uh I'm not going to going to go over all this to for a lack of time. I just want to talk a bit about future work and like what we can take from this. So, this was like uh a an initial uh This work is sort of an initial attempt to incorporate this very realistic possibility of economic censorship on L1 to the fraud proof context. Uh but this is still, you know, a a simple model and there are many ways to extend it to uh to sort of get more

insight uh uh for the practical relevance of this. So, for example, uh as a as an example in bold, uh or I think in most other optimistic roll-up systems, uh the attacker can effectively increase N by placing a new stake in the protocol. So, how do we include that in the model and how will that change things? Uh I think it's important to understand. Another thing is that the bids uh and the budgets that we uh talked about here really only capture the priority fees that are paid to the proposers, but not for example the base fee that is burnt and so the proposer presumably does not have interest uh in that.

So, uh that also should incorporated in future work. Uh and one last thing is that I'm finishing 10 seconds. Um is to consider more refined utility functions or happiness functions. So, here the defender really only cared about winning or about winning. So, he didn't care about how much of his budget was sort of spent for this purpose. But, in practice, of course, the defender would want to both win the fraud proof protocol and while losing as less of his budget as possible. So, I think that that is also an interesting direction for research.

>> So, thank you, Ben. Thank you so much. Sorry, running out of time. Um >> My apologies.