Deep-Dive Into One-Step Proofs in Arbitrum | Tsahi Zidenberg - Offchain Labs

[Music] uh my name is tahi zidenberg I am a tech lead in offchain Labs I work in the uh Nitro team and today we're going to talk about onestep proofs in arbitrum for me uh this is the most basic explanation of how arbitrum or most optimistic rollup actually works and uh what Mak it uh correct uh we'll start with a toy simple problem let's say I want to do this computation I want to do a factorial of uh non uh of of a not small number modulo and another modu and non small Prime and uh this is just a toy problem of course but for me as a uh as a programmer it's quite an easy problem to solve right all I do is I write some code in this case I write it in a go uh I compile this code when you compile the code it compiles to an assembly uh This was done on an arm64 machine so this is an arm64 uh uh assembly and I execute this on my laptop specifically uh this will take more than a second less than a minute to uh execute and in the end I will have a uh I will have a result not only will I have a result but anyone of you that will execute this code will have the same result and that's all fine and good but how do I prove this result on chain how do I prove to ethereum that this is indeed the correct result so the first simple uh simple in a quotes approach would be well to prove it on chain what I need to do is execute it on chain right so instead of go code I will write solidity code this is already a little bit problematic because solidity has a few constraints you can't do a uh a few things are harder there and I will compile it to evm evm is the assembly used on ethereum and then I will execute it on chain this is a major problem because uh executing this one I didn't go through the uh uh through the gas compute calculation but I I hope you trust me that it's very easy to define a problem that will take days and years of executing on taking the entire blockchain space so sometimes I want to prove you the uh result but I don't want to execute this computation on chain so what do I do what do I do is a third approach which is provable execution so it will look like this I will start with go code it is exact exactly the same with some caveats but basically exactly the same go code that I used originally for my uh when I executed it on my laptop I will compile this go code not to uh arm 64 or x86 but to wasm wasm is web assembly it is another type of assembly made to be uh emulated by software originally web assembly because it was made to be emulated by uh browsers and I will take this web assembly and I will execute it on a special emulated machine called arbitrator after I execute it on arbitrator all I do on chain is prove the execution on chain using the fact that I executed it on Arbiter and what that means is what we will go uh into depth right now so what is arbitrator arbitrator is uh written in Rust it is a fully emulated machine so a fully emulated virtual machine it executes weam it is deterministic it has hashable State and it can produce one theep proofs all of those we will uh talk about now so the first thing I said is arbitrator is fully emulated and deterministic that means that if you look inside arbitrator if you look inside the code what you will see in essence is exactly what you would expect to see of every fully emulated machine and even of every computer and every CPU so the arbitrator machine has a representation for the code that is executing it has representation for the memory for the entire memory space that program sees it has a representation of stacks for the local and wasm um uh for local and wasm stacks and it has a program counter which is a pointer that says what is the next instruction that I am going to execute and if you look in the code in essence the arbitrator does exactly what you expect of an emulated machine which is it has basically a huge Loop this Loop fetches the next instruction that needs to be executed it loads the it loads it it at advances the program counter which is the pointer that says what's the next instruction that needs to be executed and after that there is a huge select or in rust is called U uh match which goes over what's the op code and according to the op code I will just do the thing that the op code says in this case uh uh the code we have here is of the op code i32 eqz it's a wasm not pop the uh top of the stack if it was a zero push a one if it was not a zero push a zero and that's basically when you compile your code that's what all code compiles do a sort of very very simple uh instructions what uh uh arbitrator has that not true for most emulated machines is first of all uh we've said it is deterministic which means there is no source of non-determinism so mostly clock time W clock time has no meaning in arbitr right there is no place it can get data that is not fully deterministic um another property it has is it is hashable which means I can get a 32 by hash that depends on every bit of state of the arbitrator machine so the entire memory all the code all the stacks the full machine that is currently emulated if I I can go and get a hash what 32 by hash that depends on every bit of State in the entire machine so when I say arbitrator execution is provable what I mean is this given a machine hash at some point I can prove the next machine hash so if we both agree or if we if I have proved machine hash in Step n I can prove uh uh AB absolutely what will be machine hash in step n+ one now by extension uh it means that if the first machine hash is known so the initial machine state is known the entire execution is provable right because step after step it is all provable now this extension is not at all trivial right uh proving billions of steps from proving one step is not at all trivial it is a huge undertaking this is what we call the Bold protocol I uh uh think it is an ingenious protocol I love it I recommend everyone to learn about it but this is not our topic our topic is this given one machine hash how can I prove the next one and when I say prove I absolutely mean prove it on chain prove it on ethereum which is which means I have a smart contract I have a smart contract that does this proving smart contract I I have here the link to like the code path in the Nitro repository for it and it has an entry point which is called prove One Step prove one step is a function it receives two important input there are other inputs but we won't talk about them the two important inputs it receives first of all what was the previous machine HH what's the given that we're proving from and second of all it receives a large bite array that we call a proof its output thanks to these uh uh two inputs its output will be that next uh provable machine hash so it will tell us the next machine hash and if it agrees then we have proven basically our claim and to talk about how it works we I will first talk about arbitrator machine in solidity so we have have the arbitrator machine in Rust right the local executed machine this has the full state of everything it might have hundreds of megabytes of State uh in memory the solidity imp imp presentation of course cannot have hundreds of megabytes of State what it has is it has small state it has State uh uh it has state of a few functions so it has the full program counter uh it has uh for example it holds uh modules Ro so it will holds one hash which uh depends on all the modules and all the modules hold all the code and memory and Global variables so all of that is condensed into one hash the stack is interesting interestingly condensed into the top the top few elements and a hash of all the rest that's because TX we're not using Merkel tries we're using Merkel Stacks if you will uh that Mak proving Computing hash from this sort of thing uh simple so the one step the the proof that were the on the proof entry accepts that large bite array the first part of it will be the deserialized machine so it will be code it will be a bite array that solidity deserializes into arbitrator machine right and the first thing the almost first part in the onstep roof entry is I deserialize this machine and then I go and I check what's the hash of this machine if the hash of this machine matches the given hash that means I have proven everything in this arbitrator State machine so I have proven the top few elements of the stack I have proven the program counter and I have proven the uh uh module route The Next Step just like I have a representation of the full machine I have some small representation of a modu the current module and it will come uh I will add into the my proof the uh representation of this module and a Merkle proof this Merkle proof proves that my module really is a part of that arbitrator machine that I have already proven after that in the same manner I now prove a a piece of the code so I Merkel prove a piece of the code against the module which I Merkel proved against the arbitrator machine and now I have proved what's the next instruction that has to be uh executed so I have proved the right part of the code I have proved the top few elements of the stack and I have proved what's the program counter the next step in the one step proof look looks very much like executing you looks very much like the execution of arbitr so it will do exactly what the uh local arbitrator machine does which means at first it will advance the program counter then there is this large select right what check what's the op code match it against uh uh every possibility of a legal op code choose what you're going to do and then execute it and here is execution uh execute eqz which is the solidity implementation of the same thing we saw on Rust so I know that now I need to do an eqz and uh so pop the head of the stack check if it's a zero over one push a zero or a one accordingly when I did both the uh function uh when I did both the uh program counter uh uh advancement and that uh execute eqz I changed the representation of the arbitrator machine I changed what I now know about the world so all that's left for me to do is check the hash of this new updated machine and this will absolutely 100% proven to be the next machine hash so I have solved the problem I uh showed you at first I proved that given one machine hash I can prove what the next machine hash is going to be by extension using bold algorithm I can prove given the first machine hash I can prove to you the entire execution of everything that can happen now in Nitro an execution what it does is it produces a block knowing the the previous block so given so if we both agree or if I've if ethereum believes that it now knows what's in Block n what's the hash of block n and what's the next input I can prove to ethereum what's going to be exactly block n+ one the Arbitrage the and that's how uh basically ARB one is proven there is then another step of uh extension which says that uh given uh we divide the blocks into something called assertions so every assertion proves a bunch of blocks and that's all also done using bold so because we can prove one block we can also prove a bunch of blocks those are called assertions and what you see on chain in arbit room is you see onchain assertions and each assertion is proven by accepting that the previous one is correct and we know uh the all the all the rest of the input okay so uh let's go over what exactly is that code so I didn't have code samples here because it would be um too difficult and uh I'm doing something very much more handwavy but uh uh this command replay main.go we have the actual code that is the onchain provable execution so we said we are executing something over arbitrator and proving that that's what we're executing over arbitrator in uh uh in ARB one so the algorithm goes like this first of all you need to read the previous block hash then you need to load the state of the block from that block has then you need to load what the next transactions are what is the next input then you execute those transactions and some of those might be a stylist transactions then you compute the next block hash and you finish execution 99.999% of those instructions of the uh of the wasm instructions executed are going to be just like the eqz that we saw they they use very simple things that are entirely in web assembly right write to memory load from memory push to stack pop from stack do some computation but there are a few uh uh places where you need some communication with the outside world where we have added uh wasum like instructions we call it wav uh wavm uh instructions to uh assist the uh the extra required functionality so for example to uh get previous block has and finish execution and compute block has we have something called a global State Global state is basically the main input output of the system so uh when when when I said the first machine hash is given the first machine hash is one toone computable knowing only uh the global State and uh and the constant code which doesn't change so the first machine hash uh is known by just by global State the last machine hash is no is only only depends on global State and that's how uh so when the my executable has an input of the previous block has and at output of the next block has this is how that works uh we have an interesting uh uh Read inbox so I can to read the next um to read the next transactions what I need to do is read the inbox the inbox is something that was posted on chain my once approver knows what's posted on chain because it exists on the same chain so it is very easy to prove to it what was uh uh proven what was uh what exists on chain and then I can uh Read inbox from it and uh my personal favorite um one of the latest additions to the wavm is a link modu link model allows you to add a new module to the same arbitrator machine which means you can now load dynamically more code which is exactly how stylus works so uh when we so when we allow a proving uh wasm executed the smart contract this is what's going on under the hood um the interesting part and to uh when designing all of those is to make sure each of them can be one state provable so for each of them we have both an implementation that executes them and a solidity implementation that if required can prove them absolutely can prove the next block hash from the previous one um at this state I will say thank you um I'm tahi from offchain Labs come find us at the arbitrum booth in the full event that will start and I am just on time thank you very much