Fraud proofs war by Luca Donno | Devcon SEA

[Music] [Music] hey everyone I'm uh I'm Luca I do research at Alit and I'm here to talk about FR proofs uh so there are many different types of FR proofs uh there are offchain FR proofs onchain FR proofs single round multi round um this talk is mainly about uh onchain multi-round proof systems which is what uh the top uh optimistic Roll-Ups used today like arbitrium optimism or Bas and but the thing is that uh these two Pro system 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 uh the security trade-offs that they make um so first of all what are optimistic rollups uh it's very simple intuitively uh you need to communicate to1 the L2 state so there is an actor can be yourself that publishes the state roots of the L2 on L1 and um there is a timer if this timer expires uh the state rout is optimistically considered correct uh so that can be used for withdrawals and this is the happy case uh you don't need to prove anything about the correctness of the state um in the not so happy case you can have dis actor that publishes a an invalid State rout and now what do you do you need to prove um that this uh State rout is incorrect and as I said there are a lot of different designs and uh this is what uh this talk is about um so the original Vision about optimistic rollups was the following that any single Challenger can protect an optimistic rollup with a fixed challenge period so you know optimism and arbitrium have a 7 Days challenge period if there is anyone monitoring the chain and they say that some State root is incorrect they should be able to challenge it um so you know this was the original Vision the problem is that this is not possible at all um and I'm going to explain you why so the main problem on why um this not possible are Cil attacks so let's say that you're an attacker what you can do in an optimistic rollup is propose millions of invalid State rout at the same time so you as the single Hest Challenger how do you defend yourself how do you defend the chain um you know imagine you have millions again and you need to you need to prove all them wrong to protect the the funds that are in the bridge there are two ways uh to do this the first one is what I call full concurrency which means you have millions of invalid State Roots you need to challenge all of them at the same time um which means that uh for each state routs uh there is a challenge period which could be seven days all these challenge periods overlaps um so the advantage of this approach is that since again all the challenge period overlap uh after 7 Days some of them will be confirmed so your settlement delay is 7 Days the problem is that challenging State routs um has a cost has a gas cost because uh challenges are interactive you need to interact with L1 multiple times and what an attacker can do in this case is trying to outspend you so the attacker again publishes a lot of a lot of invalid State through you need to spend funds to attack all of them it could be that a certain point you don't have uh funds anymore and one of the inval state TRS will be unchallenged and it will be confirmed uh stealing everything so I have an example here with some data um let's say that the challenge period is 7 days they overlap for all these inval State rout the cost of challenging on chain uh like the gas cost is one e this symmetrical for the defender and attacker because um challenges are Interactive there are 1,000 if in the bridge the terer 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 rollup with a fixed period because not anyone has the same amount of funds as the attacker to protect the chain so you know let's say I'm a single I'm a simple user that all has $1,000 on a chain uh and you know the Bounty of the bridge is you know millions of dollars an attacker can spend Millions to attack it I cannot defend it uh clearly so this is not true the correct statement is that Challengers with more funds than the attackers can protect an optimistic rollup with a fixed challenge period which is a much stronger claim the second option is partial concurrency which is instead of challenging all the inval state routs at the same time I challenge them one at a time so I create this kind of queue and um 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 uh 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 let's go through an example uh again let's say that the challenge period is 7 days per Challenge and there are multiple challenges the cost is again one e the funds in the bridge are 1,000 e 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 uh like you only need one e 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 is that you have an attacker that can spend 800 e for to to play One Challenge you're going to have a delay of 800 weeks because one challenge takes one week and you have uh you play them sequentially so you will have uh 800 weeks of delay which is more than 15 years so and this is what it's called a delay attack on part on proof system they use partial concurrency so here again the claim that anything Challenger an optimistic rle up with a fixed chall perod is not true the correct statement is that any single on Challenger in the sense that you know you need little funds so it's very decentralized it can be you can optimistic rollup with nonfixed challenge period because they use uh partial concurrency so there is this trade-off when you need to design a forof system you need to decide whether you want to use full concurrency par concurrency which means you either are affected by resource exhaustion attacks which means that the attacker can try to expand you or delay attacks uh there is this trade-off um so now let's try to optimize uh these two cases because it's not as just as bad um as I told you but you know there is something that uh you could do to improve the situation in full concurrency what you can do is to add bonds when you add bonds you play you add a cost to uh create challenges so as I said the cost of one challenges can one challenge can be one e but if creating an challenge costs 10 e it means that the attacker needs to spend 10 e to induce me as the honest Defender one it of cost right so right now there is this asymmetry like the cills have to stake a lot of bonds I only need to stake one for each Bond they induce me um gas cost on playing the challenge the bond is higher than the the cost of one challenge so let's go through an example again you have a challenge period of seven days you have a the bonds that are 108 the cost of one challenge is 1/8 uh the funds in the bridge are 1,000 uh the attacker funds are 800 as before onest Cher funds are 500 as before but now the Defenders win because with 800 e uh the taret can only uh generate um 80 80 cbbl which means that I will only spend uh 80 if I have more than that so in this case I win even though I have less funds uh than the than the attacker um the problem here is that this is very complex to do uh you need something that is called executionist commitments which means that um you cannot uh allow um the problem is you need to you need to play the B section when you need to go through a challenge and you should be able to allow everyone to to play Within the same uh the same claim because otherwise the problem is um so the interactive game works as follows I propose uh I propose a St rout the the game is interactive the CH the the next player uh is going to ask me for a midpoint the problem is I can lie I can propose the correct State Ro at the beginning and then propose an invalid B section and then I can lose on purpose in this way um so the problem is um I can only have this asymmetry if people can join together and St TR cannot cannot lose on purpose and the way that you do this the way you prevent invalid Bas actions is by having a commitment over all the steps the state after all the steps uh so that when you need when you BCT you can provide a miracle proof that the B section 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 uh you need to add levels because now when you have execution history commitments over this all the steps you need to meriz the state for all the steps these steps are like on the order of two to the 70 steps this is unfeasible so you cannot meriz 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 um and then you 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 uh when you want to improve uh on on full concurrency so in practice uh arbitro the new proof system that they will deploy soon and optimism uh on Manet uh today use full concurrency so they have fixed challenge periods of seven days arbitr uses this very complicated setup uh called execution commitments optimism doesn't um and for this reason arbitrium uh can have uh what it's called the resource ratio of 15% which means if an attacker let's say has 1,000 e me as a Defender to protect the chain I only need 15% of the funds that the terer is willing to spend to protect the chain as the example we made before uh with bonds uh 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 you need 109% of the funds that attacker has so like more than 100% uh like significantly more I would say uh so again imagine you have a bridge with 1 million e an attacker can spend a little less than that you need more than that to protect the chain so it's it's a lot of funds the problem is you need uh very big Bond sizes because you need to your bond size needs to be a multiple of the gas cost uh to pay a challenge and in arbit room this Bond size is 3600 e which is insane uh so like you affect decentralization by a lot and you have this trade-off between resource ratio and na Bond size because as I said uh right now when you increase the bond size you can have better resource ratio um like a lower resource ratio which is better which improves safety but affects the centralization let's trve 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 uh this is something that was developed by cesi which is another team um uh working on FR proofs so what you can do is um you create this bracket tournament uh the matches are in parallel and if you have a lot of cbls since they are in this tournament they will El eliminate each other uh because they are paired together so uh this is a strategy to uh eliminate sibles uh together and then since the brackets are then sequential uh the honest Challenger will only play a logarithmic uh number of challenges compared to the number of the of the cbbls so if you go to work example right now the delay is not 800 weeks but it's a logarith 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 Meed that will be replaced uh use partial concurrency CES will use partial concurrency as well cartesia uses the tournament arbitrum doesn't initial bone size let's say three if uh cesi is much better than arbitrum because again they use this um there are a lot of um caveats here but like to simplify uh a tournament is a very nice optimization to use uh 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 cills and when you you have less cbls you have uh less uh like a lower number of uh challenge periods uh so like a lower number of matches which means also uh that settlement is faster this is the summary uh more or less uh which means that you know 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 partial concurrency it's very descent centralized very safe because you need very low bonds and um yeah very low bonds and your resource ratio is like um it's not even a ratio it's it's constant uh then you can play with Bond sizes for partial concurrency to to be faster but less decentralized or you can play with Bonds on full concurrency to be more safe to have a 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 uh significantly so I have some further points I don't have time to discuss all of them uh but one point is is there any way to reduce this our 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 it's uh we can do this because first of all why seven days the reason is to protect from a strong censorship a tu on ethereum so there are two type of censorship that you can have you can have weak censorship or strong censorship weak censorship means that you have a certain percent percentage of Builders censoring transactions you know like as a context sensoring uh is is a concern because if the honest Challenger is censored then Val State R is going to be confirmed right so if if there is a percentage of builders that is censoring uh this is not really a problem because you still have a high percentage of probability a high probability of getting included within you know a short amount of time the main problem is that if there is a majority of a testers like 51% of a tester sensoring um all the transactions from the honest Defenders will be excluded from the chain so now we will need to coordinate an hard work to uh hard work away uh the um sensoring validators right and we agreed a while ago that to do this to like coordinate an artwork we needed around seven days so if your protol um uses a challenge period that is less than seven days you cannot protect from strong censorship attacks do optimistic rollups make sense if we have ZK I think they do uh in the sense that um you cannot be cheap ER than an optimistic rollup in the happy case you will not uh you don't have costs apart of you know the bare execution of your state transation function you don't have the proof generation cost um your throughput is you know the same as um as the as the machine and uh well in zik you can parallelize proof generation and so on but like there are also centralization concerns so like you want to exit from a rollup uh not everyone has the hardware or the like ZK ax uh to uh to prove uh a lot of blocks by themselves if they're censored uh so optimistic rollups have these nicer properties but um should more project be ZK I I think so I think the answer is yes in the sense that um if like most of the AL today like you know we have alus we have scalability the problem that alus created is uh fragmentation most of the al2s want to to fix fragmentation can you fix can you have interoperability with a seven days challenge period I don't think so so every project that aims uh at being interoperable with all the others I think this should be ZK for all the other use cases if you're building a game you don't need interoperability I think optimistic uh the optimistic approach is is uh great so that's it thank you wow committing fraud is uh really complicated I thought you just you know signed a different name on the check so we got some questions from the audience and uh 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 uh we actually have a few examples of FR proofs happening on chain uh but those FR proofs are not the result of uh people being Malayan most of the time was just that there were some validators some nodes that didn't upgrade their software so they saw a a like an invalid State rout because they were running on a on a previous version this has happened in chroma I think it has happened in a Kinto recently which is an orbit stock like an orbit Fork so another example that is a fun one is uh on fuel V1 we Tobit try to steal $8 by from fuel V1 and you know Fu V1 is this up specific rollup that is no one uses basically there's no activity so like we wanted to see whether uh there was anyone uh trying to uh defend the chain even if even if it was not used the bone size was 0.5 e we lost so like all the tvl in fuel V1 uh it's like our funds and because there was someone watching indeed yeah that f one story is going to be the stuff a legend uh next question can't the Challenger just challenge the first wrong State Route hence invalidating All State roots that are proposed after by the proposer [Music] um well it depends on the protocol like most of the protocols like optimism today um all the state roots are independent so like invalidating one state roots do doesn't invalidate all of the others but also like you need to allow uh multiple proposals to be uh sent for the same state right because like it's not just that state roots are sequential it could be that you know for for a single point in time for a single block number you need to um you need to have multiple proposals because again you can have a lot of cbls so you need to challenge all of them uh you could have a fallback mechanism such that if multiple State roots are confirmed like you halt or something um but like challenging one state R is not enough that's the tldr cool uh next question you kind of alluded to this in the slide um how do you see Solutions like optimistic ZK hybrid Solutions yeah so this is an interesting one as I said if you use this uh 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 uh 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 risk five machine because they use risk five underneath uh they prove a big chunk of steps so I think it makes sense uh to improve the gas cost uh well you can have offchain proving cost so like that's debatable but like another approach is single round instead of doing going to the root of multi round uh proof system you can do what Tao does uh 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 um in the future if an optimistic rollup want to use um a a FR of system it's very likely that they will also need ZK somehow in their stock cool uh next question can part of the answers be facilitating an honest offender having snowballing Community Support the other honest um the other honest observers can validate The Challenge and support yes so to allow honest Defenders to play together as one you need uh adoc mechanisms it's not super OB obvious there are some proof systems like the current one in arbit room that doesn't allow honest Defenders to play together uh because you know there are there are some issues um but the idea is yes like the honest defender in an optimistic rollup 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 fend the chain together uh so uh yes like the plan is to have multiple months yes all right everyone give Luke