Fraud proofs war

Hey everyone, I'm Luca, I do research at AltaBeat and I'm here to talk about fraud proofs. So there are many different types of fraud proofs. There are off-chain fraud proofs, on-chain fraud proofs, single round, multi-round. This talk is mainly about on-chain multi-round proof systems which is what the top optimistic roll-ups use today like Arbitrum, Optimism or BASE. And the thing is that these two proof systems so the one developed by Arbitrum, Optimism, or BASE.

But the thing is that these two proof systems, so the one developed by Arbitrum and the one developed by Optimism, are very different. There are very different trade-offs, and my goal here is to give you an intuition on why they're different, and the security trade-offs that they make. So first of all, what optimistic rollups it's very simple intuitively you need to communicate to L1 the L2 state so there is an actor could be yourself that publishes the state routes of the L2 on L1 and there is a timer if this timer expires the state route is optimistically considered correct so that it can be used for withdrawals. This is the happy case. You don't need to prove anything about the correctness of the state.

In the not so happy case, you can have this actor that publishes an invalid state root and now what do you do? You need to prove that this state route is incorrect. And as I said, there are a lot of different designs and this is what this talk is about. So the original vision about optimistic roll-ups was the following. That any single honest challenger can protect an optimistic roll-up with a fixed challenge period.

So, you know, So optimism and arbitrum have a seven days challenge period. If there is anyone monitoring the chain and they see that some state route is incorrect, they should be able to challenge it. So this was the original vision. The problem is that this is not possible at all. And I'm going to explain you why.

So the main problem on why this is not possible are Sybil attacks. So let's say that you're an attacker. What you can do in an optimistic roll-up is propose millions of invalid state routes at the same time. So you, as the single honest challenger, how do you defend yourself? How do you defend the chain?

You know, imagine you have millions, again, and you need to prove all of them wrong to protect the fans that are in the bridge. There are two ways to do this. The first one is what I call full concurrency, which means you have millions of embodied state routes, you need to challenge all of them at the same time. Which means that for each state route, there is a challenge period which could be seven days. All these challenge periods overlaps.

So the advantage of this approach is that since again all the challenge period overlap, after seven days some of them will be confirmed. So your settlement delay is seven days. The problem is that challenging state routes has a cost, has a gas cost because challenges are interactive, you need to interact with the one multiple times and what an attacker can do in this case is trying to outspend you. So the attacker again publishes a lot of invalid state routes, you need to spend funds to attack all of them, it could be that at a certain point, you don't have funds anymore, and one of the invalid state routes will be unchallenged, and it will be confirmed, stealing everything. So I have an example here with some data.

Let's say that the challenge period is seven days. They overlap for all these invalid state routes. The cost of challenging on chain, like the gas cost is one ETH. This is symmetrical for the defender and the attacker because challenges are interactive. There are 1,000 if in the bridge.

The attacker has 800 if. The honest challenger has only 500. At a certain point, the attacker is going to outspend the defender and the attacker is going to win. So right now, it's not true that any single honest challenger can protect an optimistic roll-up with a fixed period because not anyone has the same amount of funds as the attacker to protect the chain. So let's say I'm a simple user that only has $1,000 on a chain, and the bounty of the bridge is millions of dollars, an attacker can spend millions to attack it, I cannot defend it, clearly.

So this is not true, the correct statement is that challengers with more funds than the attackers can protect an optimistic roll-up with a fixed challenge period, which is a much stronger claim. The second option is partial concurrency. Which is, instead of challenging all the Invali state routes at the same time, I challenge them one at a time. So I create this kind of queue, and I play in one challenge. When I finish one challenge, I go to the next one.

And this is partial concurrency, because you can still have some kind of concurrency in the sense that if you have multiple defenders, they can play against different attackers in parallel, but like in the worst case, if you're alone, you need to play against all of them one after the other. So let's go through an example. Again, let's say the challenge period is seven days per challenge and there are multiple challenges. The cost is again one ETH. The funds in the bridge are 1,000 ETH.

The attacker funds are 800. And the honest challenger now has very little funds. Having little funds here is not a problem because you can play like you only need one ETH for the first challenge. Then when you win, because you're guaranteed to win, if you're honest, you will get the bonds of the adversary. And with that bond, you can play the next one.

So, like, you need very little funds. But the problem is that you have an attacker that can spend 800 ETH to play one challenge. You're going to have a delay of 800 weeks, because one challenge takes one week, and you have, you play them sequentially, so you will have 800 weeks of delay, which is more than 15 years. So this is what is called a delay attack. On proof systems that use partial concurrency.

So here again, the claim that any single honest challenger can play an optimistic roll-up with a fixed challenge period is not true. The correct statement is that any single honest challenger, in the sense that you need little funds, so it's very decentralized, it can be you, can play an optimistic roll-up with non-fixed challenge period because they use partial concurrency. So there is this trade-off. When you need to design a for-proof system, you need to decide whether you want to use full concurrency or partial concurrency, which means you either are affected by resource exhaustion attacks, which means that the attacker can try to suspend you, or delay attacks. There is this trade-off.

So now let's try to optimize these two cases, because it's not just as bad as I told you, but there is something that you can do to improve the situation. In full concurrency, what you can do is to add bonds. When you add bonds, you add a cost to create challenges. So as I said, the cost of one challenge can be one ETH, but if creating a challenge costs 10 ETH, it means that the attacker needs to spend 10 ETH to induce me as the honest defender one ETH of cost, right? So right now, there is asymmetry, like the C builds have to stake a lot of bonds, I only need to stake one, for each bond they induce me gas cost on playing the challenge, the bond is higher than the cost of one challenge.

So let's go through an example, again you have a challenge period of seven days. You have the bond that are ten ETH. The cost of one challenge is one ETH. The funds in the bridge are 1,000. The attacker funds are 800 as before.

Honest challenger funds are 500 as before. But now the defenders win because with 800 ETH, the attacker can only generate 80 CBELs, which means that I will only spend 80 ETH. I have more than that, so in this case I win, even though I have less funds than the attacker. The problem here is that this is very complex to do. You need something that is called execution history commitments, which means that you cannot allow...

The problem is you need to play the base action when you need to go through a challenge, and you should be able to allow everyone to play within the same claim, because otherwise the problem is... So the interactive game works as follows. I propose a state route, the game is interactive, the next player is going to ask me for a midpoint, the problem is I can lie. I can propose the correct state truth at the beginning and then propose an invalid bisection. And then I can lose on purpose in this way.

So the problem is I can only have this asymmetry if people can join together and state truths cannot lose on purpose. And the way that you do this, the way you prevent invalid bisections is by having a commitment over all the steps, the state after all the steps, so that when you bisect, you can provide a miracle proof that the bisection is correct. But again, this is super complex. You are not supposed to understand this, because as I said, this is super, super complex. So improving on full concurrency is very complex.

You need to add levels because now when you have execution history commitments over all the steps, you need to merkleize the state for all the steps. These steps are like on the order of 2 to the 70 steps. This is unfeasible, so you cannot merkleize all of them. You need to have bigger chunks. And then when you reach, when you bisect and you reach one chunk, you need to repeat the protocol recursively.

And then when you do this, you create another type of attack across levels. And then you might say, I don't want to use levels at all, so let me plug ZK proofs. Again, you're not supposed to understand this. You're just supposed to understand that this gets very complicated when you want to improve on full concurrency. So in practice, Arbitrum, the new proof system that they will deploy soon, and Optimism on mainnet today use full concurrency.

So they have fixed challenge periods of seven days. Arbitrum uses this very complicated set-up called execution history commitments. Optimism doesn't. And for this reason, Arbitrum can have what is called the resource ratio of 15%, which means if an attacker, let's say, has 1,000 ETH, me as a defender, to protect the chain, I only need 15% of the funds that the attacker is willing to spend to protect the chain, as the example we made before with bonds. While optimism doesn't have this, they cannot have this asymmetry, this advantage, and indeed if you are a defender and you want to protect the chain, you need 109% of the funds that the attacker has.

So like more than 100%. Like significantly more, I would say. So again, imagine you have a bridge with 1 million ETH, an attacker can spend a little less than that, and you need more than that to protect the chain. So it's a lot of funds. An attacker can spend a little less than that, and you need more than that to protect the chain.

So it's a lot of fun. The problem is you need very big bond sizes because your bond size needs to be a multiple of the gas cost to play a challenge. And in Arbitrum, this bond size is 3600 ETH, which is insane. So you affect decentralization by a lot. And you have this trade-off between resource ratio and issue on bond size, because, as I said, right now, when you increase the bond size, you can have better resource ratio, like a lower resource ratio, which is better, which improves safety, but affects decentralization.

Let's try to optimize partial concurrency. So, instead of having all the challenges one after the other, what you can do is to create a tournament, like a bracket tournament. This is something that was developed by Cartesi, which is another team working on for proofs. So what you can do is you create this bracket tournament, the matches are in parallel, and if you have a lot of C builds, since they are in this tournament, they will eliminate each other. Because they are in this tournament, they will eliminate each other because they are paired together.

So this is a strategy to eliminate symbols together. And then since the brackets are then sequential, the honest challenger will only play a logarithmic number of challenges compared to the number of decibels. So if you go to an example, right now the delay is not 800 weeks, but it's a logarithm of that which is two months and one week. And in practice, the current arbitrum classic protocol, the one that is live on Meta that will be replaced, uses partial concurrency. Cartesi will use partial concurrency as well.

Cartesi uses it in tournamentsrency as well. Cartesi uses the tournament. Arbitrum doesn't. Initial bond size, let's say, 3 ETH. Cartesi is much better than Arbitrum because, again, they use these...

There are a lot of caveats here, but to simplify, a tournament is a very nice optimization to use when you want to use partial concurrency. And the bond size that you need are super small as well. So now you also have this trade-off between initial bond size and delay attacks because if you increase the bond size in partial concurrency, you can create less C bills and when you have less C bills, you have less, like a lower number of challenge periods. So like a lower number of matches, which means also the settlement is faster. This is the summary, more or less, which means that you can see on the vertical axis that if you go full concurrency, you're faster, your settlement gets faster, but you sacrifice safety and decentralization.

If you go full concurrency, you're faster, your settlement gets faster, but you sacrifice safety and decentralization. If you go partial concurrency, it's very decentralized, very safe, because you need very low bonds, and your resource ratio is like, it's not even a ratio, it's constant. Then you can play with bond sizes for partial concurrency to be faster but less decentralized, or you can play with bonds on full concurrency to be more safe, to have a better resource ratio, sacrifice decentralization, or you can also play in principle with a challenge period to be like if you have a shorter challenge period, your settlement will be faster, but you sacrifice safety significantly. So I have some further points. I don't have time to discuss all of them, but one point is, is there any way to reduce this challenge period?

Because right now it's seven days for all of them. Can we go below that? The answer is no. I don't think we can do this. Because, first of all, why seven days?

The reason is to protect from a strong censorship, attack on Ethereum. So there are two types of censorship that you can have. You can have weak censorship or strong censorship. Weak censorship means that you have a certain percentage of builders censoring transactions. You know, like as a context, censoring is a concern because if the honest challenger is censored, the invalid state is going to be confirmed, right?

So if there is a percentage of builders that is censoring, This is not really a problem because you still have a high percentage of probability, a high probability of getting included within a short amount of time. The main problem is that if there is a majority of attesters, like 51% of attester censoring, all the transactions from the honest defenders will be excluded from the chain. So now we will need to coordinate a hard fork to hard fork away the censoring validators. And we agreed a while ago that to do this, to coordinate a hard fork, we need around seven days, so if your protocol uses a challenge period that is less than seven days, you cannot protect from strong censorship attacks. Do optimistic roll-ups make sense if we have ZK?

I think they do, in the sense that you cannot be cheaper than an optimistic roll-up. In the happy case, you don't have costs, apart from the bare execution of your state transition function. You don't have the proof generation cost. Your throughput is the same as the machine. And, well, in ZK, you can parallelize proof generation and so on, but there are also centralization concerns.

So, like, you want to exit from a roll-up, not everyone has the hardware or the, like, ZK ASICs to prove a lot of blocks by themselves if they are censored. So optimistic roll-ups have these nicer properties. But should more project be ZK? I think so. I think the answer is yes, in the sense that if, like, most of the L2s today, we have L2s, we have scalability.

The problem that L2s created is fragmentation. Most of the L2s want to fix fragmentation. Can you have interoperability with a seven-day challenge period? I don't think so. So every project that aims at being interoperable with a seven days challenge period?

I don't think so. So every project that aims at being interoperable with all the others, I think they should be ZK. For all the other use cases, if you're building a game, you don't need interoperability. I think the optimistic approach is great. So that's it.

Thank you. Wow, committing fraud is really complicated. I thought you just signed a different name on the check. So we got some questions from the audience. And the first one up there, I saw this one going up, it's really interesting.

In all optimistic L2s, how many times has there been a fraud actually reported and acted upon? We actually have a few examples of fraud proofs happening on-chain. But those fraud proofs are not the result of people being malicious. Most of the time it was just that there were some validators, some nodes that didn't upgrade their software. So they saw an invalid state root because they were running on a previous version.

This has happened in Chroma, I think. It has happened in Kinto recently, which is an Orbit stack, like an Orbit from Fork. So another example that is a fun one is on FuelV1, we L2Bit tried to steal $8 from FuelV1. And, you know, FuelV1 is this app-specific roll-up that no one uses, basically. There's no activity.

So, like, we wanted to see whether there was anyone trying to defend the chain, even if it was not used. The bond size was 0.5 if we lost. So like all the TVL in Fuel V1, it's like our funds. And because there was someone watching, indeed.

Yeah, that Fuel V1 story is going to be the stuff of legend. Next question. Can't the challenger just challenge the first wrong state root, hence invalidating all state roots that are proposed after by the proposer? Well, it depends on the protocol. Most of the protocols, like Optimism today, all the state routes are independent.

So invalidating one state route doesn't invalidate all of the others, but also you need to allow multiple proposals to be sent for the same state. Because it's not just that state routes are sequential, it could be that for a single point in time, for a single block number, you need to have multiple proposals because again you're going to have a lot of symbols, so you need to challenge all of them. You could have a fallback mechanism such that if multiple state roots are confirmed, you halt or something. But challenging one state root is not enough. That's the TLDR.

Cool. Next question. You kind of alluded to this in the slide. How do you see solutions like optimistic ZK hybrid solutions? Yeah, so this is an interesting one.

As I said, if you need to use these execution history commitments, which most of the optimistic proof system use, you have these problems with levels and recursion, and you might prefer not to do that because, as I said, it's very complex. Cartesi decided to go hybrid in the sense that they have an optimistic protocol but at a certain point instead of proving just one single step in their RISC-V machine because they use RISC-V underneath they prove a big chunk of steps. So I think it makes sense to improve the gas cost. Well you can have off-chain proving cost so that's debatable, but another approach is single round. Instead of going to the root of multi-round proof system, you can do what Tyco does, which is you propose, you challenge, and when you challenge, you need to provide a Zika proof either with risk zero or SP1.

So I think in the future, if an optimistic roll-up wants to use a fraud-proof system, it's very likely that they will also need ZK somehow in their stock. Cool. Next question. Can part of the answers be facilitating an honest offender having snowballing community support? The other honest observers can validate the challenge and support?

Yes. So to allow honest defenders to play together as one, you need ad hoc mechanisms. It's not super obvious. There are some proof systems like the current one in Arbitrum that doesn't allow honest defenders to play together because there are some issues. But the idea is, yes, the honest defender in an optimistic roll-up is going to win, is going to profit.

So that's the main reason why some of these projects say, look, it's not a problem if we need a lot of funds to protect the chain because it's profitable. A lot of people will join and defend the chain together. So yes, like the plan is to have multiple months. All right, everyone give Luke.