Fast and Cheap Dispute Resolution - Akaki Mamageishvili

Transcript

hello everyone welcome to the presentation today I will talk about bold fast and cheap dispute resolution so the slides will follow the paper that we wrote get together with our colleagues so this is the list of them all of all of us are at of chain Labs so the slides are a bit outdated because they were prepared last April when the paper was out so some things changed but I will let you know what did so to motivate uh um the talk we know that ethereum needs scaling and so far the most viable solution to that is rollups and today I will talk about optimistic

rollups but there are other types of rollups also for example CK rollups so at that point last year in April arbitrum was was the only optimistic rollup that had life fro proof mechanis but that changed now optimis chain also has it so now how the rollup Works users send the transactions to a sequencer sequencer receives transactions and then uh passes for an execution execution is happening off chain so that's where the rollups uh gain and when there are enough transactions then sequencer compress system and post a badge and now it changed to blobs mostly to the

ethereum main chain and these transactions are canonical transactions and then validators update the state on the contract on ethereum so one of the validators makes a claim what is the state so it pulls a hash and then it becomes canonical within a week so if nobody challenges it then that's the true state of a rollup or at least from the contract perspective so we have a state uh that's like very similar to ethereum State we have a state transition function so how the transactions modify the state and this is important that it's deterministic and

then the transactions that are posted on the ethereum main chain in the governance contract are the canonical transactions that are given as an input to the state transition function so all validators if they execute correctly should reach the same state because it's a deter istic process okay so the protocol it's still current actually the Bold will go online next month I believe but it was already voted positively so it will be a new protocol so the current protocol there is one validator that post a claim and uh any other validator can challenge it but it's sequential so

the uh challenge protocol is sequential and um uh once one interaction is over then the the other game starts and one of the players will always lose because there cannot be two competing right States so the winner advances to the next round and it's done by very simple bsection protocol that I will present now and this will be useful for bold as well so the players present their versions of the stage the hashes and they need to be different and that's when there is a conflict and then they present the middle State hashes and if they are

different then we know that the conflict happened in the first part of the execution and the game moves in the first half and if they are the same then we know that the conflict must be in the second half so the game moves to the second half which means that uh in at each iteration the state size becomes half and that's great because in logarithmic number of moves we get to a single step and the single step can be D directly checked on the smart contract so that's cheap enough but we cannot do the whole uh execution on the Chain these ideas uh we observed long

ago in 1997 and uh very similar um yeah um paper was also in 2013 uh published by Keta and Rod Plum and then the arbitrum original arbitrum white paper was based on the same idea okay so what's the problem with the current protocol so there is a delay attack because now the attacker can introduce n challenges sacrifice n stakes and delay the um advancing of the state by end weeks because each uh game lasts one week okay so we don't know

that the winner of one game is necessarily the Hest party so we need to let everyone play that's why current protocol is permissioned there are 12 to 14 but the numbers can change white Whit listed validators and bold uh achieves permissionless validation okay so now uh what are the advantages compared to the current protocol so now it doesn't matter how much takes the adversary or adversaries sacrifice the state will um advance advance in constant time and I think it's like two weeks and also the

competition is not between different accounts or challenges but it's between claims or in know our case it will be execution proofs but there are some drawbacks also it requires large takes from honest parties But Here There is a um catch that honest parties can unite their stake and individual honest party may need to stake actually little amount but if nobody's helping one honest party then one on his party needs to stake a lot and it may require a lot of computational power from an honest party again if nobody helps but we expect that honest

parties will share both the stake and the computational power as well so there is another protocol that uh was developed after arbitrum Classic protocol by caresi project so these are the co-authors and co-founders I think of the project so what they are doing is they basically take classic protocol that I describ sequential and make a binary tournament tree which reduces delay to uh login rounds and that's quite simple um Improvement reduces linear delay to logarithmic delay and

they have even um more updated work very recently after VA paper now where they claim that um it's again I think totically Logan delay but they improve factors a lot but they rely on being able to prove some computation using ZK and that b doesn't rely on okay so we have censorship and that's actually where this one we delay come froms because uh honest party needs to interact with L1 contract it can be censored by adversary on the uh base layer but uh there is a social consensus

that no censorship will last more than seven days so that's where the 7day delay comes from because from from the protocol perspective there is no need to wait for seven days you just need to wait for as many blocks as there are moves in the ideal scenario so in logarithmic many moves you would need yeah something like 50 moves and then that would be 50 block times which is very short but there is a sensorship and to analyze bold we actually take quite pessimistic view we assume that adversary can enable censorship mode at any time and disable it so like sensor for one day then turn it off the

sensorship and then sensor some other time time for few hours but what we assume is that in total it cannot go longer than one week so this large C parameter is one week and the Delta parameter is just um how long it will take for one transaction to land on the main chain okay so there is one version of Bold which is not the implementation itself but it it will give you an idea how it works so in the single level bold there is a commitment to an execution so execution looks like a sequence of uh

moves or state transition um steps and then we take hash of concatenation of com commitments of uh half um half execution okay so anyone who makes a claim makes uh sense a hash of the whole uh computation and then so something happens in the protocol but at each time the L1 contract so the governance contract or B protocol contract maintains all ongoing commitments that have not been defeated

so so far so that gives a binary three structure on the computation these commitments but what is now here very important that when the commitment is challenged then there is only one valid B bsection so you cannot make up uh what is the middle um commitment because it needs to satisfy this condition and if the HH function is not invertible then you can only make one move and that's very important because it can be that some malicious parties St on the correct uh state but it cannot make

a wrong move so there is only uh correct moves that can be made the commitment can be wrong itself the full commitment but move is always um always needs to be um consistent with the commitment and there is only one move and whoever makes a move advances the state of that commitment okay so if the commitment is not challenged it accumulates some score and then parent commitments so parent means so this is the parent commitment of these two uh children commitments also can claim the score of children Okay then if we reach again

single step one instruction then the um layer one contract can just check if this step is executed correctly so when the root commitment score cross is a threshold so threshold is some suitable function of this Delta and C then it is declared the winner and all claims that lost so their route commitment didn't win the game they lose all the stakes and then winning claim takers are reimbursed for for all their gas fees and maybe paid some extra from the slash deposits of losing claims

okay so the problem with this approach is that it's too much hashing computation because there are too many steps in one large claim the root claim so it's it is too slow that's why uh it is split into multi levels and this is done by grouping the steps uh into batches and calling them the single step okay and then we do this miracle commitment on these batches so when in the single level bold I was talking about reaching the single step here we are reaching the batch of single steps or batch of batch of single steps

because there are three levels okay so when this bsection reaches this that's what I said the new level starts but on this new level you can come up with arbitrary number of claims that's why we need staking on each new level so we need staking on the root level when you are committing to the holes uh computation but also on these uh new levels and that becomes a bit complicated and in the end we reach some kind of optimum uh that on the very

original l we need 3,600 that's about $10 million worth ether stake and on the next level we need 100 ether and on the last level we need 10 ether and that makes sure that uh adversary is spending a lot if adversary tries to uh saturate funds of honest parties and uh we look at the optimal ratio how much adversary spends versus how much honest parties spend but again pooling can come uh to help here because it doesn't matter who

brings uh stake as long as it's put on the right commitment anyone can advance that uh commitment or challenge also we can introduce some rewarding here because most of the time nothing will happen but there will be $10 million worth uh ether locked not that only this amount is locked initially so if there is no dispute these amounts are um not locked there is no need to lock them on these level levels new levels and reward doesn't change game dyamics because rewarding will be some

small percentage while the aders is losing 10 million dollar worth eers so that's all for me thank you have any questions [Music]