The verkle tree upgrade / Guillaume Ballet

Transcript

foreign thank you before I start I've been asked to make a small announcement the ethereum foundation and uniswap are trying to fund local projects or are seeking to fund local projects and so you can help them choose which projects to fund if you visit the quadratic funding Booth yeah like very nice ladies they will show you how to uh how to do the the

voting so that you can help them choose between great projects and crazy projects and speaking of crazy projects I'd like to talk how ethereum is going to trans transition from vircle trees to uh sorry from the current Merkel Patricia tree and start using Virgo trees so I'm going to give a very quick primer on virgo trees and the idea is that ethereum currently stores all of its states in the leaves how does the clicker work here the leaves of a tree and uh What uh so that's a lot of data and so you can't summarize all that data

directly like you add all this data directly into the the block so what you do is you use a small cryptographic summary of part of the data and you build a hierarchical structure and the top of the structure is what goes into the block so you don't provide all the data but you give some guarantee some commitment that that data is the correct one and now the challenge is what happens if you want to prove that for example the Red Square belongs to the is somehow validated by by this information so the way we currently do it is by uh using a commitment technology that's called a hash and it serves its purpose well but the problem with the

hash is that to verify a hash you need all the data as input so if I want to prove that this indeed contains this red square I also need to pass the green square and then once I've got I verified this bit I need to uh I need the sibling here the other green sibling to verify that this was correct and in the structure that is used by ethereum you don't have two children per per node but you have 16. so uh it's uh for each level you need to pass 15 siblings and uh that makes uh a lot for a lot of data and we want to start making ethereum more stateless so we would like to uh people to not keep that data just

grab it from from the Block itself so if we want to put all this information in blocks the blocks would be way too big so what vertical trees do is that they replace uh they replace hashes with what's called Vector commitments that's the V for vertical and um what the technology of vector commencement allow you to do is to just pass the information along the path it gives you a way to prove that this is a member is verified by this without passing the siblings so the proof would become much much smaller and this is why we uh this is why we're we're trying to to switch to this technology

so very quick summary of changes um like like I said we replace uh hashes with a type of commitment as called a polynomial commitment we add the proofs to the block we add all the data that you need uh to for to verify the block to the block and then because the data because you don't no longer need to have so many uh like the number of siblings in a tree does no longer affects you we increase the the number of siblings to 255 and that makes for a more a much more shallow tree which means the path itself itself also becomes smaller shorter and as a result the proof gets gets smaller and another big difference is that instead of

currently we're differentiating accounts from this the contract data which is called storage we just um instead we we like the tree becomes agnostic all it sees is 32 byte values doesn't matter to it what what they are and the last significant change is the the gas instead until now the gas was geared at limiting the amount of of leaves that were at the bottom uh make it more expensive to add more leaves now we just try to make the block smaller so every time you need to add something to to the block proof uh it will cost you more but uh storage is no longer really the the

target so just a quick update on the the current state of uh of the implementation there is a test net that exists you can reach it at this address I've been told the faucet is broken of course as should happen during any demo but uh yeah apart from that is working well um and yeah we have uh basically two implementations that don't really didn't really manage to talk to each other yet but we we understand the problem so it will be fixed soon so let's talk about the transition now um the the problem of the transition is that you you have very large that data structure using one proof format if you

will and you need to convert it to a different format and on top of that this uh this this new format is a bit more CPU intensive so to do the transition uh it's going to it's going to require a lot of resources and that is the the biggest the biggest problem um yeah one thing I wanted to add is that it's not scheduled for uh like right after the merge there's going to be an intermediate fork in between uh because we need to to reduce to the to remove self-destruct and the reason why we do this is because I was saying we no longer make the difference between an account and storage so you can't really

know what uh what storage an account has so you you can't really destroy accounts anymore um so yeah we we're dependent on this feature so right explaining the issues the first one is memory you can more or less fit old ethereum all of ethereum data on the on like sizable disk but no one has enough memory to store everything so if you want to store this structure that is currently on disk here on into into RAM it just doesn't fit so what you need to do is instead because uh one uh because for example this this structure here can be

summarized by this one by this by this node you just replace it by its commitment and then it fits but the problem is it's called thrashing what if I've write a new value here um I I this node is not currently present in memory it's just a it's just a cryptographic summary so what I need is to make some space by replacing some subtree by its uh by its uh cryptographic summary if you will then load the previous state of the tree and finally do it right and that's quite intensive there's a lot of communication between the disk the ram Etc so that's that's called thrashing

and you can see in one of the early tests this represents the memory usage and the the memory user usage goes really high and then I hit the limit of the memory so I have to make a lot of a lot of space in Ram and you can see this is the the growth of the database every time there's a memory being freed there's a bit of a spike in the database so clearly there's also uh like the database is more efficient at storing data there's a lot of optimizations but the problem is is really visible here you need to to empty memory really often uh sorry so we have four proposals I'm

going to go over the first one is I would say the simplest also the most unacceptable it's about it's just saying okay the conversion is going to take a week to do for example uh for a week we just give empty blocks and so so that the node has the resources and available to to perform the transition so that's why it's also known as roll-up appreciation week because for a week all you can do is use Roll-Ups and hope no one is going to to try to to do anything nasty so it has a lot of advantages let's be honest uh if you if you omit the the visibility the the usability one uh

which is all the resources on the network are dedicated to to this but yeah use usability Wise It's not really recommended so there's another uh possibility which is uh to freeze the the tree at some point and then clients will only store the Delta for a period of time to give some only a limited amount of users with uh with a with a lot of computing power the time to do the translation and then the translation once it's done it's verified it's spread over the network and then clients apply their divs to it it's nice because not every client has to has to do it not every node has to do

it the problem is that you you need to make sure that the the result of the conversion that you are given is valid and that means you need to solve this problem at the the verification happens at the social level which is not as good as as an algorithmic solution um there's another solution that is a bit similar it's called the I I call it stateless think and the idea is that because the proof will end up in blocks eventually might as well use this fact uh sorry because the data the converter the data you're going to to use will will be present in Block you can reuse that idea for the conversion so uh you

download instead of storing the divs instead of each client storing the diff What happens is that the people doing the conversion also produce the proof with each block and clients basically clients have to trust even more but they have to do even less work um but the the issue is still there that those who produced the the conversion they still have to to track the network and that's that's a bit complicated the third solution is the one I'm going to detail a bit more it's called the overlay three and the idea is that you freeze uh the tree in place the the Merkel Patricia tree so the current format you freeze it in

place and then you start with a fresh tree so the and then other people can do the conversion and they can be submerging and I'm going to explain that uh with pictures so you decide that at a given block uh the Merkel Patricia tree is frozen so uh those triangles are supposed to represent an M for for Merkel and um yeah you say at this block this is the last tree that ever that will ever be produced and then the next block you start with a fresh root so it's an inverted triangle for vertical um and when you need to when you write to the tree you've right to that new route so the the old Route here doesn't change

so what you can do uh thanks to that is after a while because when you're sure that there will not be any reorgan you can delete the internal node because you can you consider that uh that all this uh all this structure here that is needed to verify the adequation between the data and the block uh yeah it's it's correct otherwise you wouldn't have made it that far um so you free some space and then the question happens what if you want to access a location that used to be present uh in the old tree but is no longer present well that's the problem of this approach first you hit the the vertical tree and you hit the vertical

tree because it's uh short is presumably smaller um so that's why you go there first and then if you don't find it you go to a key value store or the Moco Patricia tree and then you can make some improvements you can decide well because this data was present I might as well uh like in the old uh in the old storage I might as well bring it to the new storage if I'm asked for it next time and you can even delete it from the uh from the old uh from the old store um right and so some versions of this of these method assume that the the tree will be frozen

forever but what can happen is that while all the the chain progresses you can also perform the conversion offline and then when the the conversion is is performed you just merge everything and you can merge everything like maybe block by block your each block you add more let's say 10 000 leaves from the oops sorry from the old uh from the old tree into the new one and until finally you have no data left um yeah so that's one of the method uh I would say the biggest drawback is that it takes roughly four months to complete but uh during those four months at every

block you can verify that everybody is synced because you know exactly what the status of their uh of their vocal tree is and what's the status of their Miracle Patricia tree is um so that's the advantage the problem is of course that you're in lock steps with the smallest machine on the network because you only transfer for example uh 10 10 leaves one thousand leaves whatever the smallest machine can support without coming out of sync and that's pretty much it I don't know if there's time for a question four minutes for a question but before that what I invite you to do is check the test net very very interesting and

if you have uh I I also make some threads about vertical three questions from time to time so it might be interesting to to check that out as well okay anyone in the audience have questions for Guillaume early lunch I know um I was reading an article from vitalik I think he's it's an old article where he said that because the vocal tree uses polynomial commitments it's it uses homomorphic encryption to make it more efficient and that it could be susceptible to Quantum Magic

two Quantum Magic ah Quantum magic yeah and then we will need to scale back to some Stark Merkel I'm not sure I didn't understand it but the question is should we approach the the worker route or do we bet that it will happen and we should go another route yeah if if this happens if quantum magic happens um whether or not it's likely to happen is of course everybody's opinion but yeah if it happens we will have to switch to a different uh a different technology it's less it's less it's not Quantum secure that's that's true but

you can anyway the vertical tree is always one step we want to snark it all eventually so there will be more upgrades I'm not really worried about that okay I think we have time for one more question yeah okay troll alert be kind or be really really trolley um so question uh during uh the transition you have both Merkle trees and vertical trees and synchronization wise then would this synchronization be expected to sing both at the same time so depending on the method that was surprisingly nice thank you

depending on the method uh it might look for example the overlay method synchronization is expected to to happen on both on both sides yes when it comes to uh to offline uh yeah you need to download one uh one big chunk of data at once but then you need to apply to Delta so synchronization would force us to also download the data so in that case we would disallow synchronization for a period of time I think that would be the best the best approach does that answer your question Peter beautiful okay I think we're we're done for time

thank you very very much Guillaume [Applause]