The Soul of a New Machine: Next-Generation Optimistic Rollups with Cannon

Transcript

okay hey everybody so i'm here to talk to you today about uh optimism and the way we secure or roll up so title talk is the soul of a new machine next generation optimistic grow up with canon and canon is our fault-proof system which is how we secure the roll-up so this talk today is all about that so before i talk to you about how we secure our labs i have to give you a very short introduction to what draw-ups are otherwise the stock is gonna make absolutely no sense so this right here is ethereum uh it doesn't scale it doesn't scale for a very good reason actually because it's

committed to decentralization so that anybody with a laptop and maybe ssd can at home did the blockchain you can trade at home maybe you've already done it you can actually control everything that's going on in ethereum but because of that nodes can't be powerful enough to scale the blockchain to accommodate thousands or even tens of thousands of transactions per second which is what we want in the long term so roll ups how do roll-ups work you have your ethereum right here and you have a term user he has a top hat because it's rich and it can afford ethereum and you have the poor uh layer two users the lyric users talks to a machine or a set of machines called the sequencer

and what the sequencer does is that it receives transaction layer two transactions and executes them on its own and then it will take these transactions it will make blocks it will all right it's better it's better all right so the sequencer will receive the transactions and then we'll make blocks and we'll post the blocks to ethereum what this means really is that you will take the transactions and put them on ethereum but not execute them either that would be very costly you just put the data there and also it will post what you call an output route an output route is something that commits to the result

of executing the transactions so if you're a little bit familiar with how ethereum works this is mostly like the state routes so the something that commits to the whole state of the layer 2 blockchain so all that is posted on ethereum and the system is secure because there are other actors verifiers they download the transactions the l2 transactions that you put on ethereum they download them and then they re-execute them to check that the sequencer did the job correctly and they rederive the output routes then they compare if they get the same output root as a sequencer everything's right no problem if it's different it probably means that

the sequencer has a bug or maybe try to cheat somehow in that case you want to be able to challenge the results say no no i i verified this it's not correct and that's the fault-proof process that we're going to talk about this process of challenging an incorrect result so two things to note these machines are meant to scale so today you could actually run them yourself but in the long run you're gonna need something much much heavier like a data center or something and the other thing which is i've written here is that there's an additional security assumption uh compared to ethereum which is that

you trust there's at least one honest verifier so there's gotta be one guy you know maybe there's 10 100 1 000 verifiers there's got to be one that's honest and you trust that uh this is a very weak assumption right like it's compared to a 50 assumption just having someone that is honest is a pretty safe bet and there are natural people that want to be running a verifier right if you're a bridge it's in your own interest to run a verifier to make sure people are not exiting with funds that have been acquired through some kind of a manipulation by the sequencer and that are going to reverse due to a fault proof so you want to be running the verifier in that case

and we're already done so this was the basic idea of what a role an optimistic role i should say is so how does the fault proof work and a big canon because of fault-proof systems called can very subtle um so this is like this is like a summary the security depends on there being a verifier as i said and how this process happens at first you do what's called a challenge game it's a gameplay between two actors and we call them the verifier and the defender and really to simplify you can think of them as the verifier is a validator that disagrees with sequencer and defender is going to be the sequencer the defense no

no what i posted was right and i believe in it so the guarantee that is key to these roll-ups is that as long as the layer one so ethereum works correctly as long as this theorem is secure then the challenger if is right will be able to prove that indeed the sequencer misbehaved so the key assumption is that the security of an ethereum guarantees the security of the system by guaranteeing that incorrect statements can be challenged and so this prevents like fraudulent funds to escape to r1 so uh this is just the same thing said

in a different way so you got layer one the verifier downloads the transaction batches recompute the output roots it also gets does this actually work yeah it also gets the output root from now on it compares them if they're the same you're very happy i suck at drawing [Music] and otherwise we initiate this fall proof challenge on our own okay so how do you actually prove that you computed the correct result but the sequencer computed incorrect result there's a mobile way to do it and there's other ways that suck as you can see the first naive solution is to rerun the whole block on the evm

this is not possible because there's a huge overhead into running an avm interpreter on the evm like i put one redex i don't actually know what it is but it's huge and simply you're trying to run a block in a block with overhead and so you don't have enough gas okay what about something else what about uh you know ethereum runs evm anyway so we could just take the l2 byte code put it on r1 right and then run that the problem is that there are cons contextual up codes that need to be changed so an example is this block number thing well when you run it you want it to return the l2 block number not the l1 block number

or when you read memory you don't have the whole l2 memory posted on a one so you need to somehow have a manager that can be fed the pieces of memory and um and get that to you so this is quite complex it still has a ton of overhead you still need to feed all the data that the block is gonna touch and so it is not practical in practice okay okay but what if instead of running a whole block we run a single transaction maybe that's enough yeah maybe that's what optimism tried to do and it sucked so

there are a lot of subtle issues there's still gas use issues but like to highlight just one issue that's particularly nasty is that um you need to take your contract you need to deploy the bad code on a one and you need to patch the up code right the contextual ones the problem is that the patch contract is bigger than the original contract because you take your uh you take your block number of code and you can replace it by a call to an l1 contract and so that that takes more up codes and that means that the size limit on the contract is going to be much smaller on l2 than on r1 and that's that's nasty and you just don't want that so the solution

ultimately is to use a challenge game the principle challenge game is to figure out a single step in the execution that you disagree on so if you disagree on the result of a 10 000 step execution there must be one step that you disagree on it might be the very first step but it might be the step in the middle and so what's a step well it could be one evm bytecode instruction or it could be one assembler interaction and i'll tell you more about that in a second um and so yeah the the challenge game is played between validator and defender so our system is called canon uh the initial design in the proof concept was implemented by uh georg hart who's famous for uh hacking the iphone and the playstation

yeah it's a pretty fun fun dude and we're developing and currently including myself and uh it's important note that canon is not the first system of scanned and i'll mention just uh two alternatives which are the the car tc blockchain which just fall proof for like whole linux programs and of course arbitrary uh but it's the first uh full proof system that that supports avm equivalents and i personally also think it's pretty slick in the sense that it sort of removes all the extraneous concerns and just focuses on the core of what you need to do all right so let's let's dig into the challenge game

so change game performs what we call a bisection if you're a programmer you might recognize what it is if you're not don't panic i'm gonna explain so the idea is that you have this execution trace so if you run a program you can create a trace that is a list of all the instructions that were executed then the question is well what program are you running well you could be running an evm program directly so a transaction and then your trace would be made of evm output or you could be running the validation code to the node code go ethereum for instance directly and then your trace is all the assembly execution is

executed when you're running go ethereum this is what we do so we do run a modified version of go ethereum that validates l2 blocks on our one we call it mini gaf and basically what miniget does is that it reads from it reads the inputs the batches it derives the layer two chain and performs uh the validation so it's the minimal amount of stuff you need to verify that the output route is correct and we compile it to maps maps an instruction set and it's a simple instruction set that's why we picked it because it's easy to implement a maps interpreter on chain and it's also easy to compile go code

as the name implies go ethereum it's written go it's easy to compile go to maps so it doesn't make it easy for us and uh you know we're lazy and we like the simple easy stuff so once you have this idea that you have this execution trace you need to figure out which step in the trace is the step that we disagree on the way you do that is that you you run the program offline partially until a certain step of the execution and then you stop and you supply a commitment to the memory a hash or if you you know what it is a america root um so you start and you execute half of the the validation program of mini gf

you stop at 50 you take all your memory convert it to a hash you send that to a blockchain the validator does this the defender does this unchain you verify the result if it's the same it means you at least agree on the first half of the execution and so you will next submit a snapshot a hash at 75 execution if you disagree means your disagreement is before 50 and so you will submit the memory hash at 25 and you keep doing this shrinking the possible space of this agreement behalf until you found a single step of the agreement and this single step is a property that you agree on the memory before so the

hash of memory so basically you agree on memory before the step and then after the step you disagree on the memory so running the single step over the memory that you agree on will show that uh someone is right you know it will show was it who's right and who's wrong and then once you have figured out the steps you actually need to execute it on chain for which we use a unchained mips interpreter which is very simple less than four lines of code two things are interesting is that at that stage you only have a hash of the memory but the hash doesn't give you the whole

memory and you still need to access some memory not much because you're just running one assembler instructions you probably only need to access one or two memory locations and you also you might also need in a special case to access the batches and the batches already live on on layer one so they're not in the memory or at least you need a way to get them into the memory so how do we do that for accessing the memory the actual memory as i said is a miracle root and i'm going to explain marker rules right now but it's suffice to say that if you have a merkle root it's possible to try to prove any byte of memory so say the byte that location 100 the memory is three you can prove that using something called a

miracle proof and so if your instruction is going to access the memory at location 100 you can make a proof of what that is and you can supply that before executing the instruction uh and then the other thing you might want to do is access the bachelor now one and first we use something truly magical called the premature recall and that's going to be explained in detail in the rest of this talk also all right so this is just the same thing i just rambled about but illustrate it so this is your execution trace for challenger for defender uh these are the same size but in practice they could be different size it doesn't matter so you so each each square here is a

instruction in the trace so you take this step you take a memory snapshot you compare them let's assume it's the same then you go to 75 percent you compare the memory snapshot in this case it's different you go in the middle you compare it's different etc you keep doing this until you've isolated a single instruction that's a single step of this agreement that's the challenge game and now the premature article oh i'm sorry all right so the premier record was a bit of a mind-bending idea but the interface of it is very simple it's just a function that if you give it a hash it gives you

the pre-image of the hash so this is normally impossible it's impossible to invert a hash and so of course if so say the say the pre-measure requires an on-chain contract you will need to pre-supply the pre-image otherwise it's impossible to answer this query but the program that uses the premature record will assume that the oracle has access to the pre-measures that he's interested in some example of why it's useful to have this if you have a block hash the privilege article will give you the premature the hash which is the block header and particularly interesting is that every header has the hash of its predecessor block so you can walk all the block headers if

you just have this interface similarly a miracle try so much try i guess i will explain it briefly um it's a tree and that's a three data structure where every node can be represented by the hash of its children and so if you have a node or hash you can expand it through the premature oracle to find all the children these children are also hashes and so using the premise oracle you can traverse the whole tree using just this interface uh the premature article and basically if you put all these things together the result is that you can access any l1 data just based on this interface

you can walk back in the blockchain through the block headers as far as you'd like and in every block header you also have a marker route for the transactions and you have a marker route for the state at this point in time and so you can access any state at any point in the blockchain and you can access any transaction that was made in the blockchain using this interface jesus um okay so this is the same idea illustrated so say you start by running the block hash up code to get the hash of the previous block uh this will give you the block header so it's this it has a bunch of fields but as the previous block hash it has a

transaction marker route that gives you all the transaction uh let's say we're going to zoom back to the previous blocks block 41 through the pre-image or the previous block hash so like if you follow the greens green arrows here these are applications of a premature oracle so we go here we expand the previous block hash then we expand the transaction hash this gives that gives us the root of america tree and we can traverse that all the way down and we can find whatever we're interested in in this case we want to look for transaction batches these are stored in the code data of ordinary ethereum transactions

oh i'm so sorry all right so how does this work in practice well uh in miniguef the miniget is this program that we run that we get an execution trace from and that we play the challenge game on and so minigef re-implements the go ethereum database using the premature oracle and so that's that's how we were able to access like the the state and on top of that and this is not in this slide unfortunately but we there's a step before the validation of the block where we also read the transaction batches and derive the the l2 blocks and this also uses the premature alcohol

actually it uses it in the way that's like outlined here to find the transaction batches so there are actually three implementations for prevent oracle it's implemented on chain on chain is very simple you just pre-supply all the hashes and the pre-measures in advance and because you only ever run one instruction on chain it means that you only need to supply a few per images to get these pre-measures um well first actually i should say you also executed off chain in in mips so you take minigath compare it to maps and then run that off chain why do you need to do that well because you need to find the memory hashes that we talked about in challenge game and for this it needs

to be maps memory because that's that's what we'll run on the chain and these also use uh prefetched hashes but in this case you need the hashes for the the whole block the prematures for the whole block and so how do you get these per images you get them by running the normal go ethereum so compiled to whatever your architecture is probably x64 and in this case we get the pre-images using the js and rpc methods and the tool we use is get blocked by hash so this is like straightforwardly you give a hash it gives you a block header and this git proof and this you give it a storage slot it gives you a miracle proof of block and there are some very fun challenges in implementing that because it's not

exactly what you want so you need to be very like creative with it but trust me it works all right we're almost done our consent was faster than i thought it would be so in summary optimistic roll-ups are secure as long as there's one that's divided there this is the security assumption if the validator disagrees with sequencer initiates a full proof using canon and the validator and the sequencer play a challenge game where they exchange memory hashes until they find the single step of this agreement

once the step is found is executed on chain supplying three images of the memory which can be proved against the merkle rooted memory and uh yeah and batches can be read from now on using the premature rocket and where are we with this so george delivered a prototype to us which allows you to challenge l1 blocks on a1 this is not super useful because l1 blocks are correct by definition but it showed at least that the the idea could work uh we've been playing with it a little bit and so what we have now is almost uh just a very simple port of this to altus proving that or changes to uh geth or

out we don't break anything so we can challenge autoblocks and l2 and what is next is to actually do the real thing which is challenge the l2 blocks on l1 and so what's necessary for going from here to there is that it needs to add this this step of alto chain derivation which basically reads the the the batches on r1 and derives the l2 blocks from the batches and if you're interested in that my colleague josh will have a talk i think later today about that so about bedrock which is next next version of the system and i think it will go into detail of chain

derivation from batches and if you really want the detail tomorrow we have a workshop come talk to me i'll give you an invite and we'll cover technical details of both bedrock and canon tomorrow uh and yeah so less detail this might seem like a lot of work but actually this is work we already did because or uh roll up node so that you know the thing that runs the blockchain act already needs to read the batches it already needs to derive blocks otherwise there would be no blockchain and so what's fun is because minigap is a go program we can just use go modules and import the logic that we already wrote and reuse that directly into minigath and compile it to

maps so that's pretty neat it requires some sacrifice like when you compile it in mips it's like fully single threaded so you can use channels and things like that but otherwise once you if you think about in advance and write the module in the first place to be compatible with canon so just not don't do multi-threading basically then it works pretty neatly so we don't expect this to be a huge undertaking and we're done [Applause] and uh yeah there's plenty of time for a for a few questions nice presentation i just wanted to ask

the um um in in you you mentioned at some point that most in for most of the op quotes uh you didn't need just one one memory zone so one memory access or something like that yeah or two or three but two or three yeah but there are some some special op codes like create or uh ext the one that you get the the hash of a code or even deploying a transaction itself you need uh to prove that you deployed the transaction that this requires a lot of access uh to memory how you handle that you partition that in many select parts or how you're handling that so that's correct the key here is that we're not actually uh using evm up cause instructions we're doing it on

maps instructions and so actually when so the maps code in go ethereum runs an evm interpreter and that uses the maps instructions and the map sections in themselves they don't have these cases where they access a ton of memory so in reality if you have a if you deploy a contract you only ever challenge a tiny piece of the logic for for implementing that so you so you're very so you implement the full upgrades and ethereum in this mips uh language somehow yeah but the key is that we don't implement anything because we just take go ethereum which we modify we're very careful about making a really minimal modification so we can always

keep up with upstream like we have like literally one comet on top of upstream gas you're a compile guest yeah okay totally too much directly interesting like i said we're super lazy yeah do you want the microphone maybe okay thanks yeah a question regarding the threat model in the challenge game so basically to find this step which differentiates between the validator and the sequencer both of them need to compute the hash of the memory right and is there some trust that they will compute this hash memory correctly for every step in in order to go to this uh step that it differs

because i was thinking like what happens like for the 50 percent both of them compute the hash correctly but then every other hash differentiates so basically this will lead to less than 50 plus one but the real difference would be let's say at 95 percent or something like this um so the assumption the base assumption is one of them is incorrect right like one of them is lying so it is already baked in and so in your scenario if they agree at 50 and then they always disagree then they will end up saying that the last step that they agree on is actually the 50 step and that that's the one that you will run on chain

and then because they both committed to a hash for after that step that is different like we verify that because otherwise you would have taken another step right because they both committed to it you can just run it on chain and then you'll see who is right by getting the result directly on chain guaranteed by ethereum doing the execution correctly okay so i assume that this challenge game overall requires some tens of hundreds of transactions and then how do you defend from possible

denial service attacks based on multiple simultaneous challenges it does not require how much you say yeah it requires a few tons of transactions because you take the the size of the trace and because you cut the space in half each time it's a logarithm so if you had like four billion instructions executed it would take you 30 steps uh you know and it like it grows fast right like if you want 16 million it's just like you just add three transactions yeah okay but what would happen if hundreds of different challengers will try to challenge and start this game at the same time then it's a dos uh on ethereum not on us but there is there is something um

interesting there which is um yeah basically making sure that all challenges have been initiated are able to complete and we haven't um we haven't decided what we're going to do yet we're looking at the options um i think it's possible we end up with a design that's very similar to what orbit rom is doing which is that we um you would basically wait for every challenge to complete and there's like some kind of expiration windows you do have to answer within a certain time bound but if the parties are a virtual you could like it could take a while but every challenge eventually times out

or completes yeah we're ready to look into that like what are the exact assumptions how big the time bound needs to be like this comes down to how costly it is to censor uh someone that would be um honest and would be would want to do the challenge how much does it cost to censor them on the long term because that's how you differentiate like a censorship from someone that just playing the clock and just trying to do as the chain by waiting anybody else dumb questions are accepted by the way there's no dumb question um can you talk a bit about the security

assumptions of the premium image article and like anything around where that could fail and yeah okay so the simple answer is that it's secure because you supply the pre-image and then you hash it and then you just get the hash um and so that's verified on chain you just do hashing on chain the complex answer is that there is one pitfall to it which is that most of the cases in a good therm when you wouldn't want to use the pre-measure recall the pre-image is pretty small right it's a block hash block adversary or something like that there's one case where the premature could be huge and that's the receipts because the receipts they include all

the events that have been emitted during the execution of a transaction and if someone wanted to do su they could just emit a huge amount of zero you could use like a whole like the worst possible case they just take the whole l1 block worth of gas uh i didn't give the context for that um okay quick context is that you can if you want a bridge from l1 to l2 you can do what's called a deposit and that's a l1 transaction then we'll bridge over to r2 basically and to read them we read the events that they emit because there's a deposit event and so to derive the l2 chain we need to read these events from the la1 blockchain and so we need to invert the hash of the

receipt and this per image if someone was maximally malicious they would take up a whole block l1 block of gas and just emit events in a single transaction and that could be like like hundreds or even a gigabyte or so and uh yeah you can't post like you can buy the data on ethereum that's a pretty big dos so uh we're looking at solutions there what i think we'll end up doing my best guess currently is that we'll do a very simple zero knowledge proof so that because because we're running mips mips never access a bunch of memory together only needs one byte or one word

in that receipt and so you can do a zero knowledge proof to prove just one byte of the receipts so and you can probably do it with something very simple like circum that's like available off the shelf you don't need to invent a whole new kind of cka so i think we'll do that okay quick feedback what was the talk like easy to understand was the how's the difficulty level who who was completely lost don't be shy i've been to plenty of talk with ours completely lost who got

half of it all right who got mostly everything you know maybe not everything but like yeah a big a big chunk of it all right either i'm great or you're all very nice so if you have any questions left don't hesitate to come find me afterwards i'll hang around and uh i hope you can and like i said tomorrow we have this workshop so um hope to see you there you need an invite though so hit me up and i'm yeah i'm north swap everywhere basically twitter telegram add me if you have a question if you don't find me thank you very much [Applause]

yes