Stateless Ethereum: How Verkle Trees Make Ethereum Lean and Mean by Guillaume Ballet

foreign [Music] hi um yeah excellent so uh yeah I'm going to talk about Virgo trees I've been making a few presentations about those already but they tended to be a bit too uh deep technically speaking so because this is Defcon and we're trying to onboard more people this one is going to be a bit more high level so hopefully enough to to raise your interest in in vocal trees um so yeah why do we what do we uh why are we considering vertical trees it's basically a big change in the in the way ethereum functions so what do we want to risk this well there are several reasons the the first one is we want to be able to build uh blocks as a self-contained execution units at the moment ethereum has a bit of a problem that when you want to join the network or if you haven't followed the network for a while you need to go through a process that's called the sync synchronization you cannot access the state directly it's uh like you cannot just down download the state I mean you can't download the state but it it's a fairly convoluted process so the idea is that if you include in the block everything that you need you can just download the block and execute it and see if you're interested like even before you uh if even if before you execute the block you can even know if it's going to be of interest to you or not and if it's of interest to you you can execute it otherwise you don't even have to to care so it's something that is it's to build something that is in between a full client and like a full node and a light client in the sense that you are still supposed to follow blogs but you don't have to hold the entire State and it's nice because it paves the way for other upgrades or it makes other upgrades a bit simpler for example if you want to shuffle committees between between shards in the future you want shards you don't want shards to full short validators to keep following the chain at all times like several chains at all time so it's something that's going to help them get up to speed a bit faster and of course uh there's the the idea of State expiry like the state of ethereum is quite large so we want to be able to delete some of the states but we don't want to delete and forget forever if your state has been deleted but you want to use it again you need a you you need to provide a proof to resurrect your state and the idea is that vertical trees make your proofs smaller so it will be cheaper for you to resurrect the state so uh because it's a fairly uh like deeply technical uh topic I have tried to re to make a simpler explanation with pirates so imagine you have four Pirates and they they bury a treasure somewhere and they plot the directions to get to the treasure on the map and then they want to go their separate ways so if they adopt the method like the metaphorical method that we we currently use in in this in these terms to store the ethereum state what they would do is they would split the the map in four bits and then each of the Pirates would get their own bits and when uh they want to get when they want to access the the treasure they need to to put all the the pieces of the map together the problem is inheritance if one of the Pirates wants to retire and for example wants to uh to sell you his bit of the of of the map uh how do you know he's not selling you a fake map a fake piece of the map uh he's a pirate after all so you should be careful well the problem with this the method that was chosen to figure that out you need at least the other two Pirates to check that the the pattern matches the proof size is quite involved it requires you to take a the siblings the the symbol The Sibling pieces now if we use the variable the proof the proving technique that is uh that is suggested by vertical trees which is called uh like it's based on something called Vector commitments hence the name vertical what you do is you uh like cut out something at the center some little stub and you make this little stub as hard to reproduce as possible ideally cryptographically uh impossible to to fake and then everybody goes their separate ways and when you want to buy the when you want to buy the your your part of the map all you have to do is make sure that your piece fits into that uh that proof uh that little stuff so of course we don't use pieces of paper we we use cryptography as stronger cryptography than this and now this is your proof size and so how do you transpose this to uh vocal trees well the current ethereum state is stored in a tree where all the data of ethereum is at the bottom of the tree and then you group them the parent is a commitment the parent node is a commitment and then the parent of that parent is also a commitment all the way to the top and the the root of the tree is ending up in the block so if you want to prove in the tree for example the the purple Square here if you use the current method it's the same thing as with the pirates for each level you have to pass the siblings and here this is a very simple representation but in in ethereum each parent node has 16 children and the consequence of this is that you need to pass 16 sorry 15 other value for each value at each level for each value you want to prove so there are thousands of values per that get touched per block that's that's a thousand times 15 values per level and if I remember correctly the the the depth the tip the average depth of the MPT is between 10 and 15 I don't remember exactly so that's a lot of data that's roughly uh if you want to pass the that data in a block that's three megabytes we are in Bitcoin territory so yeah it's a bit too big to pass around the network in a reasonable time if you use the Virgo commitment so you have the equivalent like you still have the oops that doesn't say yes you have the uh the little cryptographic proof but all you all you have to pass as as your proof is the the nodes along the way to your value and that is much smaller first of all because you don't pass the siblings but on top of that because you don't pass siblings there's a virtual cycle that allows you to widen the tree you can have more children per tree and per per node and as a result the tree gets shallower so your path is even smaller even shorter and as a result your proof is is that much smaller so there's a unfortunately it's not that simple there's quite a few changes to to introduce at the same time uh like the first one is putting the proofs in the block that's uh that's that's the whole point but we also need to change the tree structure and I'm not gonna get too deep into the details because once again it's quite involved there's an EIP there are other talks about it uh look at them look them up if you're interested but the idea is that all the data ends up in a single tree So currently accounts have their own tree and for each account you have the another tree that encodes the storage for this account well here everything is kind of uh yeah hashed or mixed together and spread over the tree um each item like each account item for example the balance the nons uh the code the any any slot like for example uh if you're thinking of crypto Kitty each cat is uh uh accessed independently because we don't want to add more to the proof that is uh required so if I'm sending funds to to a new address well I just need the address the target address balance I don't need to know how many uh how much code they have I'm only interested in in the funds um right and like I was saying the data is spread all over the tree but we are trying to group things that belong together a little bit so that you don't spend your time jumping all over the tree all the time so it's grouped in batches of 256 and I'm going to go over that in just uh just a bit so this is a picture that comes from the EIP itself I'm going to describe on the left side you've got What's called the stem tree and it's the basically the top of the tree so the tree is flipped to the side it's rotating 90 degrees to the to the left and um the route sorry the the stem tree only has a branch node so that means every node in that tree has at least two children when the when you take your key and you follow the you follow the the past Trace by the key at some point you will reach a moment where there's only one group that is a group of 256 that is uh pointed out by this key so there's this intermediate uh like what's called an extension yeah I don't quite see the pointer here sorry but the blue the blue box um that the extension says this is the prefix the 31 byte prefix that every key below me have uh like are keyed by so um that means that if when when you go through the tree and you come you have to compare the key that you're using with the the encoding the the key encoded in that blue box and if it's the same that means your data is uh in the group below it otherwise your your data is not present in a tree and then there's the suffix tree so that corresponds to the 256 values and there's a force column that we're not going to cover it's not really important for for this talk um so like I said every every piece of data is broken into chunk that means for example the code is broken into bits into 31 byte pieces that are fitted in a 32 byte piece the storage slots are also have their own uh on at their own data the the balance has its own value and each of these values each of these chunks is given an offset and for example the the the balance is always offset one the non-set offset two and then a bit further you have the beginning of where the code is supposed to start and then even further you have the the bits where the all the data slots are are supposed to to be and the way you find them in the tree is you take the address of so you have a key that is made of two two parts the the 31st bytes are called the stem and the suffix it's just a byte that indexes in the group that we saw before um I'm talking about the the third column here so the the last byte is the index in there and um and so to build the stem what you do is you take the address of the account and you take the the first 31 bytes of uh the the offset of that chunk and you you hash them using what's called a Pederson hash so it's like uh it's like catch Shack but it's much more friendly uh for uh for ZK applications and it's also much slower but uh you get uh you so you get a 32 byte values you take the the 31st bytes of this value and uh that gives you the stem and the way you use it when you compare it to the tree uh the stem will give you the pass through the stem tree and the extension and when you you found that you use the suffix to select the the value in the group so like I said uh just a recap vertical trees are are nice because you can make the tree much larger much smaller uh much more shallow sorry you can also experiment with uh with ideas like you could sing so I know that this is very interesting to dub developers you can just download the blockchain not care about the state and when you look at the when you look at the proof in the block at the witness you can you can figure out if you're if that block is accessing something you're interested excuse me interested in so for example if yeah if your crypto Kitty you want to see if the crypto Kitty contract is accessed if so you just execute that block to update your internal state if not you don't care um yeah and I was uh there was just a recap for the rest of the slide so what is the current state of uh vertical tree implementations uh we have one and a half running test Nets um the we have one test net that is uh fully working it's a proof of work test net called I'll give the address at the end um and so uh proof in blocks uh it works it works it's been working for a while and then uh there's a proof of stake test net that is currently in bring up phase so unfortunately I wasn't able to get it to to work for for Defcon but it's going to happen shortly when we do performance we currently have like performance testing we see that is currently five times slower than a regular magnet so when we replay blocks from Main mainnet on a translated vertical tree layer it's five times slower um we have been uh we took it down it used to be 40x so it's it's a bit faster already we have another Avenue to to make it faster but it's I mean in my opinion it's all is going to be a bit slower than the current method but it offers some opportunities to to build interesting applications so I think it's worth it um and they are uh there are like three implementations uh and there's a fourth one uh ongoing with uh with Basu so I wanted to I don't know if it's quite readable but I wanted to give an example of what you can do with vertical trees so there's a block Explorer on on that test net on the running test net and there's a piece of software uh that is able to read the block and reconstruct a view of the network sorry of the tree that is uh everything you know to re-execute the block on top of it so I don't know if it's quite visible I still don't see the pointer but basically you can see that the the leftmost branch here is an account the the next brand the branch the right of it is another account I mean I can tell because uh because of the way the the last level looks like and you have the the other two branches from the root these do not have a very deep tree and that's because this is a proof of absence so that means this is the way you signal that those branches those locations did not exist before the execution of the block and what definitely happened here um is that those two accounts on the left probably send funds to those two accounts on the right that did not exist yet and that they will exist after the the execution of the block so it's quite interesting because you you can see what's going on you can visualize it this way without loading the whole tree uh right so this is the current state what are the challenges we still have to overcome uh one of them is the transition uh converting a Merkle tree to a vertical tree is no there's no walk in the park uh it requires a lot of ram it requires a lot of this space um and uh yeah it's uh it's it's quite difficult so um there are two methods really two Avenues to do this uh this translation either untrust the conversion to very powerful machines I have a test machine that that is a Xeon it takes its uh six days I know Aragon is able to do it in like uh less than a day but even even for arrogant it's it's not instant um and uh where was I yes um so that's the First Avenue the Second Avenue we have to do the translation is simply to Pace it to the slowest machine on the network so uh that would be to do a translation of let's say 5 10 100 values per block but this would last for a month but then every node on the network would theoretically be able to follow um so these methods are have names uh the one where uh like you follow the pace of the network it's called the overlay tree the other one was called offline conversion there's a third one that is known as the roll-up Appreciation Week where you just do nothing for a week or a month and you wait for everybody to be done translating that's uh it's just here because it's a cool name no one's really considering that um yeah one last thing I wanted to say about this slide is uh pre-images so uh most of most clients including guests do not encode the addresses directly they just write the the hash of those uh those addresses so to do the translation and because we use a different hash system we need the pre-images it turns out that most clients do not store that Aragon does but the rest of them don't so pre-image availability is another problem that needs to be uh needs to be addressed and uh it's not a it's not an easy one another thing is the slower cryptographic Primitives it's not as fast as ketchak so this is one of the latest uh runs and you can see that roughly 30 33 35 is spent just doing uh elliptic curve operations so um cryptographic Primitives is really where uh the uh well the effort needs to be the optimization effort needs to be made so either by writing faster crypto or uh by uh by not calling those functions as much so uh caching for example is is a technique that has worked well uh yeah there's a slide on database design so basically the idea is that uh that like current most clients have written their optimized their database layout and their database access layer for the current MPT a lot of those assumptions are no longer valid uh let alone help helpful with vertical trees so there will be some need to adapt to something that is a bit close to to what Aragon is doing uh but that will take time unfortunately and I wanted to finish on people on what you can do if you want to help uh the first thing would be there there are test Nets so the first thing you can do is just try to deploy your contracts on on test on the test net and see if that works um if uh you can also try to run your own client um like uh hashtag testing The Verge you can also modify a CL client to figure out how to propagate the proofs because currently uh it's not it hasn't been defined so it would be interesting to to run a fact-finding mission yeah finding out where and how the proofs need to be need to be propagated in a in a proof of stake world like I said crypto is the is the bottleneck so if you can find a better crypto cryptographic primitive than what we have that would be also quite helpful um yeah it's also going to affect Layer Two Solutions like presumably Layer Two uh layer two groups don't really want to to diverge too much from from the main net so um they will need to they will need to um to adapt as well there's no really there's not a clear path for that yet like I said pre-images are also a problem so if you have a way to to make pre-images available to everyone that's a very good that's a very good test very useful and then you can go crazy you can try to prototype the interaction of vertical tree with the portal network with uh try to implement Statics by reusing vertical trees all of that no no no no all of that is Greenfield but it's also quite interesting to to get some some information some ideas of of what is to come and with this that's pretty much it I have put the addresses of the two test Nets knowing that the second one is still in a bring up phase so it will probably not work today but the other one is the landing page for the proof of work testnet and this one works or should work and you can you can look at the Explorer you can send you can send transaction you can you can try everything and that's it thank you [Applause] thank you so much Guillaume do you mind taking a minute to answer our questions if you do have any questions for Guillaume go ahead and raise your hand and one of the volunteers will actually come towards you there's a question right there in the fourth row of fifth row with the black sweatshirt you mentioned accessing data is going to be a little bit different does this imply that like um tooling teams and wallets and such are going to have to like enforce access lists now moving forward no uh it doesn't mean that but it means that the gas model is going to change to uh to follow this this new model uh which is why I was like if you've got a contract please deploy it on the test net uh but you do not need access lists are going to disappear they're replaced by something else that is not really exposed to the to the to the user so to for the end user in theory apart from the gas cost everything will be transparent oh there's one more question do you mind answering one more can I repeat the question real quick oh sure I'm just going to paraphrase it real quick and they said that they wanted to know if there's any drawbacks to the vertical trees yes there's plenty of drawbacks like I said there's the the transition the the slow crypto otherwise uh yes like the biggest drawback I only alluded to uh in the previous sensor it's that the gas model changes and that means that a lot of code uh you know like contracts into some contracts than to be very optimized for gas those optimization can turn out to be completely Obsolete and counterproductive uh so that I would say that's uh that's the biggest drawback I can think of awesome if you have any other questions for guillong I'm sure you'll be over to the side feel free to ask him after the talk too thank you awesome thank you