Accelerate OP Fault Proof via EIP-4844-Powered Multi-Section Dispute Game

Transcript

[Applause] [Music] yeah hello everybody uh it's my great pleasure here to present our work on accelerating the op forof using the latest ethereum upgrade EIP 4844 so um next oops it's not working next okay cool yeah so first of all a create intro of myself I've been working

in the web area since 2018 before that I was a software engineer at Facebook Google got a PhD um primary working in the infrastructure so my primary interest is in etherum data availability and L to Technologies get some uh support from both op and also uh Ean Foundation um for example Vali personal grants on Cross layer to bridge data web sampling and storage and so for today's talk is also uh sponsored by the uh the op Grant uh okay so here's the online I will give first give a quick intro what

about what is Optimist R up and it's Cor responding BC uh dis dispute FL proof gain and then I will introduce our propos multisection for dispute game how we are able to accelerate the whole procedure to one to the 10 10 uh time and then uh lastly I give a summary um so optimistic R is uh one of the uh basically most popular Ro these dayses including for example famous OB stack and op um the basic idea is that we can perform a lot of uh uh offchain computation uh which is very efficient with a very high TPS or very large memory model and then

we using onchain some smart contract to verify the offchain execution um for example we can use in the word ZK SN proof to verify the validity of the transaction results or we can also use in FL Pro to prove that the execution result of the op chain is wrong so how it works basically there's a proposal Defender that submit a claim which is the execution result of the off chain uh and then this is a subjective claim that the proposer believe this is correct and so anyone is able to uh challenge the claim uh within called

called challenge window and when the challenging is happens there will be we call dispute for game a dispute a thought dispute game which will basically interactively tells which instructions in the offchain execution is wrong and then once this execution is fail we can basically uh submit Unchained uh verification to tell that challeng wins the game within this time window and if no is able to challenge the claim with the T window then we will believe that actually the smart Contra

we believe that this is assumed to be correct so this is basically basic mechanism of the optimistic rup so optimistic R has a lot of benefits versus for example ZK rups first is much much simpler to implement and also uh to implement is PR for example in the zika the major CA is the pr cause which takes a lot of time first to make Implement correctly and second to prove the option execution so for optimistic Ro that would be much simpler and second but face like um the major disadvantages of optimis optimis Roa is that it had requireed a very long

settlement time uh for example in the current optimistic um like op stack for proof it requires 33 moves in the for distribute gain and which right now is generally require 7 Days uh especially consider some attack vectors and also takes about 80 million gas which causes about3 Easter at about 20 ea uh jary price so the question is that can we reduce the moves to much much smaller ones for example less than 10 uh interactions and also we able to reduce the gas cost to l stand one to the

10 um so that's basically idea why we proposed the multi session for proof so before we dive into the details uh I will give some quick overview of what the current for prooof dispute uh game happens so first of all we have a state which represent the uh current state of the viring machine for example in a fib Fibonacci case we will have the two last variables of the fibach sequence and in the more compli cases for example Specific Instructions architecture like Ms swom then it will contains a list of like registers memory stack and we also have a state trans trans transition function which tells

that after running this state what is the next stage looks like for example in a Fibonacci Sequence then we basically sum these two last two sequence the last two variables in the sequence and and then move the last one to the previous variable so that we can have the new ST which is bi uh and then bi plus AI plus bi and in the virtual machine cases that will be a one-step execution of the MPS op code here I list all the OB code that is uh defined in the MPS [Applause] spec and so in order to execute a large number of transactions in general we

will have a multi-step State transition function which just repeatedly apply the state transition function on the state with M times so that we will have execution Chase for starting from the uh initial called preate and the postate of s plus uh i+ M so here is an example of the Fibonacci example that when we start with the initial state with uh two variables in starting with 11 one and after 16 execution then we will end with a result with 1,597 and

2,584 and we also have the corresponding execution Chase of running repeatedly running this uh Fibonacci sequence for uh 18 16 times so the question is how we able to make sure this six uh s s16 is correct especially uh if somebody is wrong then we can find out which Step of this execution is wrong and then we can use an onchain verifier to challenge in corresponding execution and to tell that there's something wrong that is made by the uh proposer so first of all before we uh basically start again we need to know

what is a claim if the claim is very similar to a multi-step State transition f function but just tells that after running some PRI with M steps we get a corresponding post day and the client is said that hey this is the post state that we will expected to uh return from the state uh transition function or you can also claim that this is not the case which is not the corresponding uh postate uh that we uh given this uh claim so so in the Fibonacci examples basically is we want to using the dis uh dispute for uh for proof to tell that

given this objective execution result given initial State and the coresponding uh postate and we want to basically have this uh for example this claim is given tells that this is a valid claim because the execution result is the same as the the uh the state transition function but it's also for example suppose this a proposer propose a claim with a wrong result and this claim will become invalid and that is the for dispute gain trying to convinc by to the smart contract that somebody is something is wrong by the proposer so what is the for dispute game

is basically doing that given a initial state that is generally a offchain for example block transition so that we have initial uh state of the the work state of the of the layer two um viral machine and then given a state function for example in the evm case that will be the evm uh viral machine and then um and the where both the defender and Challenger agree how these two uh that is written on a smart contract Tru and we want to design an interactive game to prove on chain that uh suppose there's a invalid claim um that is of a

a long offchain execution for example running a very very long sequence of Bachi uh result and that is really wrong by the smart on Smart contract and in this cases this m which is the offchain execu number of steps can be can be super super long for example in the optimistic op stack cases this number of Step can be 2 to the^ of 73 that basic can covers most of the l two like transitions uh with a large large number of the for examp B blocks and another thing is that the one step State transition function uh is

able to be verified run on top of a block chain so that we can verify any onestep transition is correct or not and so this is example in the OB stack it provides MPS Sol so that we can verify a one-step mys op code execution that onp on top of blockchain so now the the gain is becomes that the defender agrees that I have a proposed a ro claim that starting from initial state with some execution steps option execution steps and we get corresponding uh execution results while the Challenger says hey this something

is wrong and I would like to challenge in how you execute this data and what are intermediate state in during this uh execution and then fdg will be able to run as a smart contract on chain to determine who is the winner so for Fibonacci cases is basically we want to prove that uh suppose a claim is wrong like like objective is wrong then we can Us in the this game to prove that it's actually wrong on the smart contract but we cannot prove that if CL originally is valid then uh we can prove

that is is incorrect or uh we cannot prove any claim that is correct so this is the basically the capabilities of the F uh distribute game basically we just suppose the claim is invalid then we would like to use in this game to find something is wrong and so the optimistic assumption is that suppose there's nobody is able to challenge the root claim for a specific time of timeing though then the protocal assume that the root is valid which means that the finality window which means that nobody challenge the game must be greater than the minimum challenge window uh which right now requires 73 interactions of the onchain

transactions and generally it takes about uh 7 Days uh why is uh such long time uh the founder of OBA C give a really good uh thought about how this uh can happen and one key factor is that it highly depends on the number of the the interactions or we call fdg moves between the smart contract and also the defender and the uh Challenger so in order to basically to play this game so one party for example right now this is Defender will first uh if I disagree with this result it will

basically submit a list of sub claims in the bicep case section cases they will two sub claims to divided this two uh the whole root claim into two sub claims which counter corresponding original claim saying that hey I disagree with your claim and this is my intermediately execution result and tell me which one you disagree and so this requires the counter subclaim contains uh the new state the intermediate States um which must be data available and the rest of the state is already uh exist on chain so they don't

require this additional information and at the same time this H sub claim hases original uh claims number of steps so that we would like to reduce this step to one so that we are able to finally decide who is the winner using the onchain verifier so the the defender must response that I either disagree with with the the first part of the execution or the second part or agree with the first part of execution but disagree with the second part of the execution or it may fails to response within timeout so that again he will fail again and so suppose the defender agrees with the C2 that's pre previous half

section of the execution but disagree with the second half then it will counter the second half of the subclaims and this repeatedly and finally it will reaching uh state that with that both party disagree uh actually agree with the previous state but disagree with the corresponding postate and with only one step execution and one reaching the state now we are able to settle the whole dispute procedure us the on chain uh onestep verifier so this is BAS B how the for prooof dis uh dispute gain looks like and here we can have this call fdg

uh claim tree which will basically be able to find the corresponding uh counter counter claims given a uh corresponding original claim so basically this list all the possible claims in the whole procedure so for the bisc fdg this require log to m moves between the defender and the Challenger and suppose we want to support a lot of lot the offchain executions then it requires lock to 2 m moves which m equals to 200 suppose 2 to the^ of 73 that require 73 moves to determine which step is disagree between the defender and and

the correspond Challenger and then they can settled by the correspondent onchain One Step verifier and this takes a lot of the time and also Gess cost so one natureal idea is that in that of split the full execution uh Trace into two segments why not we are able to split this into multiple segments so that we just need to uh able to accelerate this procedure with much finer granularity in each move so this basic idea of multisection uh for distribute gate so for here here give a example that we split the who execution Chas into four sections and then provide additional three states to tells that

the corresponding execution result in the middle and then the defender must response to with four choices either it disagree with the first uh quarter of the execution results or the second quarter or third quarter of the last one and or the defender may also fail to the gain by uh timeout and so this will basically reduce this we only need to two moves so that we are able to find out which execution result is disree uh the step disagree between the Challenger and also the defender and so that we are able to greatly first reduce the number of

claims in the this tree so for all this for example claims in uh for example in the uh a two of three and all these layers they will be removed because we basically using this each time it will it will create four counter proofs in the previous example and at the same time also reduce number of interactions so we require only two moves or interactions that be able to find which instructions is disagree between these two parties and this is will be the claan tree of the multisection for distribution gain using k equal 4 so the good thing is like using multisection FR proof we are able to

reduce the number of moves to log from log to n to log to log to n where n is number of the uh sections for example if n is 4,096 then we can reduce the number of moves to 7 uh from 73 to7 and the coins is that since we need to carry more data to tell the corresponding intermediate stat of the execution for each uh counter moves uh in increase The Quon gas per move for example using n equal 496 that will suppose we put is uh the corresponding intermediate execution

Chase using core data that will need extra 2 million per guas in each move that will be considerable large versus the the current BC game so the question is can we reduce the gas while har the benefit the key idea here is now we are able to useing EIP 4844 blob which is just launched about uh two months ago um which introduced a new object for binary large object which can be able to carry 128 KOB of data and now the key idea is that why not use this blob to carry 4,096 95 state hashes so that we can

able to submit one transaction with one block and be able to counter uh 4,0 uh 96 uh subclaims and in addition thanks to the upgrades The Blob cost versus Cod data is um this is huge huge number uh that is cheaper versus the coda which means means that corresponding actual gas can be almost negligible using the BL to carry those um those intermediate uh hashes of the subs so here is the Closs summary using the current Nal 2 requires about uh more than one uh 18 18 million gas with uh

more than 73 moves and we can use in the Cod dat to carry the corresponding intermediate States uh for example using uh n = 256 we can reduce the number of gas to 3 million uh with about nine moves and we can further optimize this using ip44 and so that we can reduce the moves to seven and further reduce the number of the um the the the total gas to 1 million which is 10 times uh smaller than the original Nal 2 that is the current implementation of of the OB stack um So currently we have a proposal that is submitted to the ob stack which

is already uh accepted and we also have a specification to basically describe mathematically rigorously to how this multisection for appro works and there's also uh ethereum uh optimism uh discussions so if you have any questions feel free to share comments there and we also open source The Who code so that if you have any ideas to contribute or test this feature welcome to uh contribute to the report and so with all these features now we are able to do a lot of uh uh crazy ideas for example we are able to prove a super super large execution on of chain for example uh artificial

intelligence interference or training procedure using uh optimising for proof and be able to almost instantly set the corresponding for game if something somebody is wrong um so we co-work with aura to develop all this opml so that we get able to employ the benefit of multisection for approv to accelerate this procedure um so many thanks for attending my today's talk and if you have any questions feel free to reach out to me and i' love to uh see you there thank you much thank you so much thank you yes working uh thank you are

there any questions yeah any questions nice thank you hey thank you for having me so and the question is like how do you envision like the future of uh like what you're building like what you're trying to achieve in jally speaking and what is the a kind of end goal which you can call a success basically in terms of development of the features maybe and so on thank you yeah so the question is what's the future of these prop proposals and how do you define the success uh metric so basically we are right now running this the whole

proposal is be able to first uh implement the all this feature pass all the test and then and and test this feature on the test net and they deploy op stack be able to do the fra proof and actually this is current stage of of a bicec uh op OB St approve and next step is once they have been launched in the menet we also launch the whole feature on top of mainnet and then um so that we are able to collect more detailed results what's for how how much gas is been saving and and all those um like the number of time that is reduced uh and this is this is the basic the metric so so we definitely the multimate goal is running on top of the mainnet and there another proposal that are we going

to discuss tomorrow is to using the ZK fra proof to also accelerate the the final step or maybe a multiple steps so that the ultimate goal will perhaps to reduce the uh interaction for prooof to one or two times so that it can reach almost instant um settlement using the fra proof while saving a lot of cost both the op fra proof and also the ZK th proof itself so uh we will discuss some ideas tomorrow about this ZK fra proof uh dear thank you so much CH working now yeah thank you so much um

I believe we are out of time thank you again we're going to be getting ready for our next talk thank you thank you [Music]