Stateless Ethereum, Layer 1 R&D - Day 2

[Music] um yeah so i'm going to talk about stateless ethereum there are several aspects of it i'm going to focus on vertical tree because that's what uh that's what i'm working on uh there's more aspects there's state expiry uh there's the portal network will uh yeah there will be other talks about uh about that uh afterwards um so i start with a big list of changes uh we're just going to skim over them um but the the main idea of vertical trees is that you replace hashes with polynomial commitments it's um it's the same principle but uh the idea is that uh you can open a polynomial uh polynomial commitment so you can get some information about the the source data without actually revealing the data and uh what we do uh what how do we use this we start we we build stateless blocks so we put blocks we put uh a proof and the pre and the post state in the block so you no longer need to keep the state locally on your machine you just receive it along with the block you uh execute it you verify it's correct you move on to the next block um and there's a lot of i would say practical changes that also get introduced uh in order to some of them are just to reduce the size of the proof so for example we look for a much wider tree which means it's going to be much more shallow and so the proof end up ends up being smaller everything gets merged into the same tree we switch to 32 byte keys and i'll get to the gas changes in a minute so the proof why why do we talk about vertical uh vertical proofs uh suppose you have a state and you want to prove the the red the red rectangle in a merkle environment you just need to you need to pass every single sibling because you need to the whole uh s pre image to hash the to hash to get the hash and to to verify in uh vertical proof because you get some information like you can get some information about the pre-image you just pass the information along the path so um yeah in short this is why you want you want to use vertical proofs block creation so what happens you start with the pre-state so when you produce a block you start with the pre-state you figure out executing all the transactions what are the leaves that are going to change and what are the paths to those leaves and then you just generate a proof like a vertical proof and you also get the keys and then you add them to the block so at the at the bottom of the block you add the keys and the values uh and uh in the vertical proof and then sorry at the bottom of the header and then you of course you have the transaction list and from that uh when you receive that block what you do is you rebuild the tree and so the dashed uh the dashed uh rectangles are not available to the to the verifier but it doesn't matter this all the information you need is in the is in the solid line rectangles and so basically you just maintain a key value store and when you do this you just update it you update the tree you do not need uh the the other data you like the the block has been that has been given to you made sure that you would not need those uh other values if you do then that's an invalid block and once you updated all those values what you do is you calculate the the root commitment so it's no longer the root hash it's the root commitment and you just verify that it's the same as the one passed in the block um the way the keys were changed um so you switch to to a 32 byte keys and what we do is we group keys by uh sorry we group values by by groups of 256 leaves and each account is has its components so the nonce the balance everything represented by one leaf and each value is available at one given offset so for example the the first offset is the version the account version then you have the nonce you have things like this then a bit later you have the code uh and then you have the the the storage data so you know which slot you have which code chunk you have you hash it uh using a patterson hash it's like a hash but a bit more sophisticated and easier to translate into zk snarks and then you have this you take the offset uh like the last byte of the offset verbatim and you can uh index into that group and that gives a tree structure that is a bit scary at first but it's quite uh simple once you understand the basic principle so what you have is because the tree is very shallow um you you have a high and very wide you have a high branching factor so the depth the the estimated depth for for main net would be a depth of four so that means the fourth uh the first four bytes of the key would be uh yeah would correspond to a branching and after that the the rest of the stem for the following bytes until the last byte you would have um basically that you would be the only key with this with this prefix so it would be very wasteful to insert internal nodes so there is there are extension nodes at only at the bottom of the tree it makes no sense to have extension nodes inside the tree because like i said there's a high branching factor so you will never need a um an extension node in the what's called the stem tree the the yeah the the part of the tree with only internal internal nodes or branch nodes and then uh you have this uh kind of finicky problem uh all values are represented by field elements and those field elements are 253 bits so if you want to store a 32 byte value that's 256 you miss three bits uh so what you have to do you have to split it and you you have to split it into two uh element sub elements of 16 bytes and so you find yourself with having two 512 values instead of 256. right still 256 value but broke like divided into each so you need to have some kind of subtree um so you have two subtree called c1 and c2 which are effectively the yeah it's like an internal node but it's at at this level it's a bit uh it's it's a bit uh surprising at first when you know the the previous tree but you get used to it uh after uh after a while um so just go going back to the to the first slide i wanted to go back to the to the gas change um you have instead of because you're no longer storing data in the database or at least you don't have to what you do is uh you uh no longer charge uh like you don't no longer pay gas for storing data in the database that's no longer the the problem what you do is you compete for block space so um you have when you access one of those groups that i was talking about you have to add more elements to the proof so you find yourself having to uh pay um some gas to access to add this uh yeah those elements to the proof if you're doing that for the first time once it's been added so once you pay the the gas cost once you uh don't need to pay again because it's been like the the evil has been done you added something to the proof you added uh you bloated the block so you no longer need to to pay because you already paid for for block space and then every time you access a leaf for the first time you also pay some gas because you add it to the to the list of key values right so what is the current state we have uh three library implementation there's one in rust there's one in python and there's one in uh in um we have one and a half client implementation so we have uh geth with a modified uh version and there's also nethermind uh that hasn't really we haven't we have three consensus bugs so they they haven't completely joined the test net but it's uh it's there uh we're getting close and uh yeah there's a test net if you want to to go play with it it's uh i've been told it's unpronounceable so it's it's pronounced that's if you need um [Music] and uh yeah so what are we going to discuss this afternoon uh well the open problems the transition the transition uh is a bit of uh uh it's a problem that existed before we were talking about vertical trees um there's we were already mentioning that for the for the binary trees so initially uh the the hope was to do some kind of state expiry scheme uh i'm still hoping we can do that but it's it needs more definition yeah more defining uh there's still the old id uh eip 2584 of overlay tree so you just add a new tree uh you add a red read write tree you you make the merkle tree read only you only uh write to that tree and then you slowly block by block you convert uh you remove some of the data from the miracle tree and you insert it into the into the the vertical tree and then um it's an idea that has been suggested to me yesterday by ed uh from rb term um it's uh so this is not i don't think it's going to be useful for l1 but in l2 they will also need to to to adapt to whatever the l1 is doing and they were thinking of doing some kind of uh interactive proof uh like what they would do so what they would uh sorry what they do when they have a fault proof in in arbitrarium so they would do some kind of uh if uh sorry the client would propose a vocal tree root and if someone disagree they can they can just make a claim and have an interactive game where they figure out where in the tree something was wrong that means effectively that your reorg is based on an interactive game i don't think that's gonna fly for l1 but for l2 it uh it could make sense then there's the problem of stateless sync uh the idea is simple it's one of the big advantages of of stateless because you received the state in the block you can just accumulate the data if you want to save it and then you can go backwards in the block chain to to get all the the leaves that were not overwritten looks simple in theory in practice i'd love to discuss that this afternoon there's the cons the issue of address space extension so i don't think it has any champion at the moment um there was some proposal in the past with the epsilon team who talked about the bridge contract that was uh yeah i think because we're switching from 20 byte addresses to 30 32 byte addresses some investigation should be done but so far no one does that and the last oops and the last problem uh is data availability and there's piper's gonna make a talk about this uh that's it for the overview thank you and check out [Music]