The Dave fraud-proof algorithm — triumphing over Sybils with a laptop and a small co... | Devcon SEA

[Music] hello uh can you all hear me okay uh I'm Gabriel and today we're going to be talking fraud proofs you know like another session about fraud proofs uh we will present a new technique uh that we've just published in fact so it's been in the oven for quite a while and I'm quite excited to show it to you all but the bottom line is that we weren't quite happy uh on the current set of fraud proof so we created a new algorithm uh so first I like to thank caresia for all the grants provided and also my co-authors austo who is here on the audience and Diego uh so thank you all and also to all the organizers of this amazing event um yeah so first I want to get this question out of the way the Zeki question uh it may feel that when we're talking about fraud proofs that we're trying to figure out the best grass to feed our horses uh and I want to push back against that notion you know because there are no silver bullets you know ZK is not panaca uh when you compare them with front proofs there's a sharp contrast in throughput and costs uh which means that depending on the application you're going to prefer the different algorithms you know there going to be trade-offs in the end there's no silver bullets that's the point I wanted to get across so now let's focus on fraud proofs yeah the agenda today is that they're actually quite hard to get I hope you got that notion from Lucas St uh all the previous attempts were either unsafe centralized or slow and Dave is not yeah so fraud proofs are in a diff uh difficult position right now so we have the pressure you know on the top there's vitalic Suite essentially calling for stricter standards but if we look at L2 beat we don't see full pizzas right so we have the pressure but we don't have implementations coming and the reason for that is because it's actually quite hard to get fraud proofs right and by right I mean essentially three properties the first who are there um I want you to be able to become a validator I want you to be able to go there without a supercomputer without huge ons and be able to participate in the consensus in the protocol and the second property is that I want that you be able to defeat anyone by yourself even if you're facing against a nation state so if you get those two properties to defend an optimistic roll up all you have to do is set up a note on your own infrastructure you don't need to delegate trust to anybody else we inherit the security of the base layer uh so those are like the two like uh oneof end property and we want it to be decentralized uh and the next one is that we want settlement to happen without large delays we want settlement to happen quickly so let me run all the three of them together uh they kind of look like this you know decentralization I want you to be able to participate without a supercomputer or huge bonds there is security which means that tvl cannot be stolen even if you're facing against this nation state uh and liess no large delays and you might be getting some flashbacks you know like some PTSD like oh no do we have another trma and yeah kind of you know it's actually quite hard to get the three of them at the same time uh and you can always naively go from one vertex to the other um but you sacrifice one to gain the other you know so you can take this straight off so it does look like a a real trma and the reason for that is Cil attacks uh I will zoom in on only the first one which is resource exhaustion attacks it's like a Spam attack where you create like a huge number of sibbles and you just drain the funds of the Hest validator until they can no longer participate in the game and then you can steal the tvl uh so this is a Cil attack that targets the security of the algorithm and there are mitigation um strategies but they end up restricting participation and thus harming decentralization uh so there are three main uh solutions that we will talk today there are several others but we'll talk about these two the first two is by optimism optimism fault proof uh there's also arbitrum bold and our own permissionless referee tournaments PRT for short this is the previous algorithm we did that was our first attempt at cracking this uh and I want to highlight the very important fact that the top two you know the first two uh if you look at the tvl Distribution on L2 beat pretty much most of it is being protected by those first two you know it's either an OP chain or an arbitrum chain so we need to keep this in mind because we need to take the analysis of these algorithms quite seriously uh so this is the sneak peek comparison between you know those three and the one we're going to present today and the columns they map directly to those three properties so for example bonds uh if you look at bold you need 3,600 eth to become a validator so it's a very high Bond uh value and this has a centralization effect so the bond colum is related to centralization decentralization now expenses oh just to you know highlight this uh this is a 1 million ether attack scenario so we assume that the adversary is willing to burn that amount of money uh in that case uh if it's a op uh fault proof the defender has to match those funds so if you don't have also 1 million ether you will lose the tvl so that colume expenses maps to security and finally we have delay uh if you look at our own if there's this 1 million ether attack civil attack um you get 20 weeks delay which is also quite high so you know none of the three we feel are quite adequate and today we will present Dave which is on the bottom which strikes a good balance across all three of them cool so let's talk about some basic concepts of fraud proofs uh okay so first our threat model uh we assume that the layer one works however we also assume that it can be censored for up to one week so think like a censorship budget that the adversary has and they can spend it at will and we also assume there is one ons validator which we're going to say it's Willie And Willie has a laptop a few ether and values uh hard values so we begin with the basic primitive which is a pairwise reputation so the goal is that well you have uh two players we have Willie the adversary and the blockchain acting as a referee in the middle and those two will engage in a dispute to prove that the other is wrong uh and they want to in the end the the goal is to prove the result of a program to the referee and it's interesting because they don't prove the correct result directly they prove that the other is incorrect and since we assume will is there he's the one who's going to enforce the right result because he's the honest one you know uh yeah so they're going to fight to prove the correct result of a program now what do we mean by program the computation model has an initial State and a state transition function agreed by everyone and then we apply the state transition function over and over the initial State until we get the final State and that final state is the result of the program that's what we are trying to prove to the blockchain and the intuition of a reputation game is that first we're going to perform a binary search on this computation and try to pinpoint the exact State transition that they first disagreed on because if they agree before and disagree after somewhere in the middle they start started disagreeing and we want to pinpoint exactly that and once you find that Divergence you can execute a single state transition function you know the refere the blockchain and figure out who's lying and eliminate this liar uh so this is the basic intuition but we're going to make a slight change to this uh so instead of committing just to the final state which is really what we're interested about we are going instead to make a commitment on the whole history of the computation so we have all these transient States and we're going to commit to that so it's like a Merk tree where the leaves are all the transient States we meriz that we get the claim so we turn the dispute not just on the final state but also on the history and this change is important because we remove the possibility of false flag attacks which are quite annoying you know so we can join a s claims that are the same together on the same team and this enables a whole bunch of algorithms including PRT because we introduce this technique on PRT and and Dave which we're going to present today now the final piece to get all like The Primitives is deadlines because it's an interactive protocol so players acting turns uh and if they refuse to act we need to do something so we need to set deadlines to eliminate players who are not cooperating but remember we have the onewe censorship in our threat model so naively we would have to set a one week for each interaction which would kill the liveness of any protocol so what we instead do this is a technique that many protocols use is something like a chess clock so this allows you to amortize this one week across many interactions instead of having to pay it for every single interaction so you turn from like the sday multiplying each interaction for it to being like an additive uh part of the expression and then you only need to pay for each interaction the real time of that interaction in the absence of censorship because an interaction is quite fast you know it's like 5 minutes uh and we don't want to play pay on top of that five minutes seven days so we use the chess clock to amortize that now let's generalize this this is a pawise reputation first now let's do a multiparty reputation and there are two high level approaches one is the parallel approach which is more like what bold uses uh and the good part of it is that it finishes fast so we have Willie engaging every other claim in parallel at the same time but the problem is that we incurred a chance of overwhelming Willie right so imagine that instead of only five we had like one million sibl would have Willie trying to fight everybody at the same time and he could get overwhelmed and lose and lose a tvl so we have this you know oh it's fast but it might overwhelm Willie and we can mitigate that by increasing bonds but then we start centralizing the algorithm uh with PR2 which is our previous algorithm we went a different route uh we use this tournament idea right so we put sybl to fight against other cbbls so the number of round is logarithmic the expenses are logarithmic and the delay is logarithmic so this all means exponential Advantage willly has an exponential advantage on delay and resources but each round takes a week because of the censorship you know even amortising the week across a match every match every round still has to last at least a week so if we imagine this the analogous uh of 1 million sibles here there will be 20 rounds so it will take 20 weeks which is high you know uh but matches only take two hours in practice you know in the absence of censorship they would take two hours but because there could be censorship we need to add the week so we were thinking oh why don't we try to amortize this one week not only inside a single round but across the entire dispute so this is what we'll try to do so what I present now is an attempt to accomplish that okay so the algorithm is called Dave uh and it's just Dave it's not an acronym uh it's based on the D versus Goliath archetype uh because anyway um so the first change we make uh is we change the tournament to a repage tournament this is a fancy name just to mean matches are not eliminatory you don't eliminate um a claim as soon as it loses you give it a while you know it has to lose multiple times before it's finally eliminated so this is what repes Char means now don't try to think about how long this will take forget that let's just think on the soundness of it I want on this slide to convince you that Willie won't lose and he will defeat everybody let's think about time later um yeah so imagine that we have the censorship of one week but we reduce the rounds the matches to one day so every one day they rematches everybody including Willie uh and then they fight the next day rematches everybody again and so on when know that Willie can't lose unless there's censorship but even if there's censorship we know that Willie can't lose more than seven times because the budget is only seven days so it's like Willie has age hit eight hit points but the adversary has only seven bullets so the best the adversary can do is spend his whole budget and force Willie to lose seven hit points and then he's out of budget and now will is very angry indeed and he going to kill everybody else now this may seem a bit abstract so let's get it more concrete so this is a different example the previous one was with eight hit points this one is just three uh the optimal value is more like 21 you know but it's it's hard to visualize that so let's go with three first uh yeah so everybody everybody's on the same bucket in the beginning everyone has three HP and the uh white arrows point to the matchmaking so Willie is spared against red and green is spared against gray so red and green lose so they're demoted then we rematch again now this time Willie is against gray red is against Green so green loses gray loses and he keeps going like this you know this logic uh of bearing whoever loses gets demoted uh and eventually Willie wins you know he kills everyone uh but on this example note that we assume there's no censorship so will didn't lose any hearts he could have lost Hearts uh but it's you know it would take more images to do that so we're just assuming that you know there's no censorship for this figure but there could be uh so Willie could lose two rounds but not the third one but we didn't talk about how this matchmaking is done uh and this is quite delicate in fact this is at the heart of Dave the matchmaking we can't do it randomly we cannot do this uh adversarially bus you know it has to be done in a very specific way which is we need to do matchmaking by hit point so we want to match the same hit point with same hit point or at least as close as possible so looking back it's the same image you know we did the correct matchmaking so on the second round Dave is matched not Dave Willie Willie is matched against the gray one he's not matched against red or green has to be matched with gray third round is not possible to do a perfect pairing uh so we do our best and our best would be either gray or red and so on so like abstractly it's like as if we sorted every Claim by hit point highest to lowest and then we match them left to right yeah and when we do that we actually get exactly what we wanted you know if it was random uh there will be no um uh improvements over PRT but if we do the rematching with similar HP we actually dilute the set 7 Days across the whole dispute we get exactly what we wanted there's some constants there you know that's why I said proportional it's not exactly that but the idea is really we are amortizing seven days across the whole dispute and we're only playing paying one day in that 7-Day example you know that I gave earlier uh times logarithmic of sios uh I mean the real values uh is actually more like 10 hours you know then there's a constant we go on all of that with a lot more nuance and discussions on the paper so we can check it out uh yeah so this finishes the description of Dave so it's a repage tournament where we do the match making with similar HP and when we do that we amortise the seven days across the whole dispute instead of over a single round uh so concluding you can be with you only need a laptop and about a three e collat room you can defeat anyone because you have this exponential Advantage so this means that a rollup that uses Dave inherits the security of L1 and for any realistic Cil attacks it's going to take no more than four weeks it's going to be within four weeks and thus Dave triumphed over the sibbles with a laptop and a small collector but Dave had no supercomputers on his hands and we get those results yeah that's all I had to present to you today thank you very much for coming [Applause] great talk uh love the name Dave um thank you it's got a few few Q&A questions you can still add some of the questions um while we're going through some of these and up vote them uh but the first question is is a one that I've been thinking too um what if there's multiple Willies defending won't they eliminate each other yeah so that's a good question uh when we did the computation hash which is that commitment it means that everybody that's honest is going to be on the same team so if there are many Willies they will fight together against the sibl not against each other because the claim the same thing so we have this uniqueness of claims when we do the computation hash and we allow all the honest validators to join teams so we consider this single ton hero know it's just Willie but in practice there going to be many Willies and they all fight together pushing in the same direction cool uh next question is about your censorship model is your censorship model hard censorship and do inclusion lists improve these things yeah so the inclusion lists I don't think they help exactly on that uh so the censorship model you know luk um gave a very good uh intuition of it is that 7 days is the time we can try to organize a hard Fork so Suppose there is hard censorship my transactions are not getting to the blockchain so what's going to happen is that you know Twitter's going to catch on fire I'm going to scream to everybody look I'm being sensored for already 4 days is everybody's going to get uh you know iffy about this and we are going to together organize uh like a hard work or something to fix this so the point is not that there can't be a 7-Day censorship it is that if there is a seven week censorship the Ean Community will together realize and say that this is a problem and then hard Fork away and if we put like a one- day censorship I would convince nobody seven days it's the threshold that we consider to be easy to convince cool uh the next question what happens to levels in the current PRT uh will your plans be to eliminate it with ZK yeah exactly so PRT uh if you look at our current implementation we are doing it with three levels uh we think with some really good engineering effort we can do it in two uh we want to do it in one using ZK exactly that and this is a prerequisite of Dave so Dave already assumes that we manage to reduce this to one level cool so what happens if you mix algorithms together would that increase security do you see it working yeah so uh there are two ways to mix algorithms uh one of them is to improve liveness actually so PRT finishes faster if there are very few number of sybl so what we could do is launch PRT in parallel with Dave if there are no like very few sibl PRT finishes first if there are a lot of sibl they finishes first so then we take whoever answers first so this is an approach to improve on liveness now to improve on security we can also mix them with the goal of uh you know reducing the risk of bug so we could have like a a Consortium like a quorum of four members one member could be PRT but permissioned so permissioned PRT has no problems of liveness so we could have that one of the members in the Forum then we could have Dave as another member in the Forum then we could have I don't know a te or a quarum of T and then we could have a a multisig you know so if we have this Quorum of like many um you know it it would take a lot of effort to try to corrupt all of them at the same time so we reduce the risk uh by reducing you know the chance of there being a bug so that's how you could mix protocols cool so um what if the goal is not to disrupt the chain but just to delay the chain yeah how large would the cost be if the attack presuming the only goal is to delay by four weeks so if you want to delay by four weeks I think you need more than10 billion or something you know we have to burn the GDP of Japan it's crazy you know we sometimes lose sight of like exponential or logarithmic uh so really if you burn like trillions you can't even fit that on the blockchain then you you couldn't really push pass like this four or five weeks uh the next one ASM totically is um is it still logarith Matic delay right yeah exactly what we did is we reduced the constant multiplying it by about one order of magnitude okay um you have multiple Willies that are good but then I decide to go bad they can't because um they when they do a bisection they need to provide the merco proof and the proof w't won't just match yeah will just not match cool all right everyone clap your hands for Gabriel and thank him for his time he spent on the next session will be at 11:30