Statelessness & Verkle Trees

[Music] [Applause] [Music] next up we have guillaume and he's going to be talking about statelessness and vocal trees a really interesting and awesome topic and uh without further ado let him introduce himself and take it from here welcome here we go okay perfect uh yeah so cool thanks for having me um so i'm going to talk about statelessness and vertical trees so i'm i'm gum from the from the guest team uh just like marius and i've been like in the past six months i've been working on what comes after the merge so i yeah we wanted to share a bit uh let's see an overview of what's coming uh what to expect after the merge like the merge is the big thing on the horizon but uh there's more exciting things uh uh coming after that so uh yeah i've been mostly uh working on uh on vocal trees but i've been asked to to give an over uh like a broad overview of statelessness in general what's coming so uh i'll cover i'll cover a bit of that as well and the first question is why uh why do we want to to achieve statelessness and it's uh it's pretty simple in fact uh have you tried to to synchronize a node recently it's taking a long time you need a lot of data so that that really prevents a lot of people from from joining like smaller devices phones or raspberry pi's i mean raspberry pies technically can do it but it's not very sustainable there's a lot of centralization associated to this you need like a lot of people using fiora and uh there's also the the problem that for example a dab developer or anybody uh there's a lot of data to download but not everybody is interested in all the data in fact most people are not interested in in the data so uh it would be great to have uh just to be able to download the data that you care about and and keep on keep going on with the rest of the of the network so this is uh these are the goals that we're trying to to achieve and so uh there's basically three components uh with uh uh that yes statelessness is uh is has three main components uh there's vertical trees the this is the technology we're going to use to uh to basically make statelessness possible because it uh it allows for very very small proofs or yeah much smaller than what we used to to have until now there's the the state expiry which is uh something that has been attempted many times in the past but is coming back with uh with a new tech a new technique called address space extension that i will cover and uh the last uh the last uh component is state networks so um since syncing the state is so difficult uh the question is can you can you just avoid dealing with all that state and so this is yeah this is the question this answers so let's get into uh into the vertical trees uh currently we we have uh a merkle patricia tree so it's using hashes each level hashes is children and and so on uh until the top and hashes have been very useful in in the past but the problem with uh with hashes is that if you get the whole uh commitment if so if you if you have a vector of values and you just want to prove that one value is in the vector and you're not really you don't want to reveal what's what's next to it you can't really just take the hash oops sorry you can't really just take the hash and uh and take that value and somehow prove that this value is at this specific position in the source data the only way you can you can prove that is by passing the entire vector um so you have other like an alternative technique to that has many similarities with with the hash is a vector commitment you have a vector you commit to it you provide a commitment but they provide also they also have the ability to uh to find an opening which is a smaller piece of data compared to the size of the vector that you can use so if you have the commitment plus the data plus the opening you can prove that this data was indeed at this location in the vector and you can use this to to hide some data if you don't want to reveal all the data but the reason why we care about this is not because we want to hide data that is public we just want to use it so that we don't have to pass all the data and this is quite important because if use like if you want to prove that something is in the current tree um you have to because you're using a hash uh you have to pass all the all the siblings of a given node along the path so that's uh 15 like the the merkle patricia tree has each node has 15 siblings or 16 children and you have each time at each level you have to pass all 15 siblings and the depth of the tree on average is seven eight so you have 15 times eight uh 32 bytes it's a lot of data so because of what i explained about vector commitments you could use vector commitments to just pass the data that you need add some commitments and uh that's already for each level much less data and on top of that uh the the depth the average depth is four and the reason for that is because since you only pass like the the number of siblings doesn't matter you can have much larger uh like nodes with many more children and because your tree becomes much larger uh it becomes automatically less less deep so more shallow so you you pass you you move on from from a structure that is really really high and and not that not that large i mean the mpt is quite large but it uh but a vertical tree would be larger and and uh it would be shallower which means you you also reduce the number of uh of items in your proof uh which yeah contributes to making the the proof smaller and there's also an an interesting point that i'm not going to to cover really uh today it's the fact that any uh currently you have a tree for all the accounts and then each account has its own tree for storage we're no longer having that with vertical trees everything gets merged into one giant uh giant tree uh but yeah i won't cover that it's just uh good like interesting to know uh one question um that comes often is people say okay but if you have a commitment if you don't have to pass the siblings why not pass you know a single a single vector commitment with only the data you want and uh that's that's a good idea but calculating a commitment takes a lot of a lot of time just like calculating the hash of all the data takes time um so what you do is you try to look for a sweet spot that makes smaller proofs but doesn't uh doesn't require a lot of time to to compute and so we chose uh we chose 256 children uh initial implementation or initial proposals where 100 sorry 1024 children but it made things more complicated to implement and 256 children seems to work so uh this is what we we went for um so yeah come just a general comparison of proof sizes uh between merkle and veracle the first in the first case you have the leaf data so sorry in both cases you need to include the leaf data but in the case of miracle you have for each level which is roughly seven you have 15 siblings each uh of of which is 32 bytes so if you have 1000 leaves that's roughly three megabytes and we're getting in block size so we want to have the the proof integrated inside the block and as a result uh that that makes a block that is uh you know bitcoin territory basically and in fact bigger than this so instead of having a block every uh every 10 seconds 10 ish 15 inch seconds to that gets propagated over the network uh you need uh yeah you need 10 minutes maybe maybe more so that's that that's why the the merkle tree and that's why we want to switch the tree uh the tree that we use to store the data because uh that's impractical whereas vertical trees um so you index you have the the index that the the child is in the in the node um you have the the value you have the commitment to it so it's uh it's a slightly larger value but you only have four levels and you don't have the siblings so you end up uh even though you have a tiny overhead i mean um yeah it's uh insignificant not insignificant but you it's definitely not the biggest contribution so you end up with a with a block size of roughly 150 k sorry for the proof so the block size it it basically doubles the block size um and that's much more manageable uh right so uh the next idea is uh state expiry and the idea is that because the state is getting uh too big in ethereum that's uh like the yeah there's the state blood problem and because you end up um you know when you store something on ethereum at the moment you pay some gas but the implicit promise is that this uh this value you store will be kept forever so that's effectively free um we we want to go back on that promise a bit because it causes state bloat so the idea is that after a while um the the data expires of course uh it's not completely forgotten there's uh we keep we start with a fresh tree uh we delete the data from the previous tree actually from two trees ago and uh but we keep the route so that if you have a proof of your data that your data was present in the tree uh at that time you can resurrect it you can bring it back to the to the current epoch so there's you pay an extra cost to bring it back but if you don't need it you can still just keep the proof and and just let it wait for the time you needed uh to pay the resurrection cost so uh right now we are so we def we divide uh the time into periods the period zero is the one we're currently in but when this the state expiry scheme becomes active um it will uh you will have one period each year or each six months and uh when that happens you freeze the tree of the previous period and you start with a fresh tree so we had pair zero what you do is you start adding values to it and you so far you still need to you still have to keep the data of the previous uh the previous period and when the period one comes to an end what happens is you start again from a fresh tree you are still obliged to keep the data of the previous period but the the period before that you you can delete the data and you just keep the root so you can start adding more data to it and when you want for example to if someone wants to recover data from peer 0 they pass a proof and that gets included in uh so the the data gets brought from period zero into pair two one thing uh that um is not specified on this on this diagram is that the data had to be absent from uh from period one um so the when when the the data that green data got recovered from uh from period zero there was a check that it was not present in period one if you find yourself at period three and you want to uh resurrect something from period zero uh you have to pass a proof of absence that you have to prove that the value you're trying to resurrect was not in period one because uh otherwise what could happen is for example alice has some funds in pair zero she transferred them to period one then she transfers some funds to to bob period two happens pier three uh happens and then alice resurrects um the funds she had in pair zero and that's a double spend so to make sure this does not happen you need to pass a proof of absence um right so uh this state expiry uh uh like mechanism comes with what's called an address space extension so um we had addresses that were 20 to 32 uh sorry we currently in ethereum the address are 20 20 bytes and they are the first 20 bytes of the hash of your public key so um now we want to make those address 32 byte long but we don't reserve the 32 bytes like the this is not the whole hash we only take 26 bytes of the hash and then the remaining six bytes are uh used for uh well half of them are used for versioning and uh yeah future use and the other um three bytes are used for uh like to to denote the epoch sorry i keep saying epoch but it's actually a period um it's used to denote the period that um that the the address was first accessed and the reason for that is because there's a cost associated to resurrection so for example if bob wants to send alice some some tokens to to alice but alice hasn't resurrected the the address either bob pays for the resurrection cost to resurrect alice's account but if he doesn't want to then he can send it to an address that is also controlled by alice in the sense that for example so i have this example here for example let's say alice owns the public key sorry the private key that controls address zero zero zero uh she has a balance here um and then let's say uh bob sends uh yeah bob has address zero one for example so both those addresses have the the counter zero because they have been seen for the first time in uh in in period uh zero then you period one happens so this is uh this is not in the in the period one tree but alice might receive some funds from bob and bob's instead of resurrecting this address from alice actually uh sends it to alice but with an address containing the current uh period so it's uh it's seen for the first time at this address in period one um and alice still has the the private key that controls this hash so she can still uh she's still the owner of the fonts but it's like she has two addresses with one private key she has two addresses now and in period two uh alice might want to get the the the value she had locked during period one so she she passes a proof um to resurrect the address and uh we can see that the value that was in pair zero is now available in period two uh and uh the value so when bob sent some funds to alice in period one this value was not overwritten alice now has one two three four eth in one address and nine one zero one uh in another address so that's an interesting scheme it's also a fairly complicated one because yeah i like to make this joke address state extension like asc can be pronounced assay which is sweat in japanese i think implementing it is going to require a lot of a lot of sweat um but um yeah it's it's nice because it makes uh still expiry at least it proposes a concrete approach to state expiry which is something we've been talking uh uh about for uh for uh yeah a few years already the problem is that it's still quite complex um we like a lot of contracts on the on the on chain today expect a 20 a 20 byte address and they actually use the 12 remaining bytes for something else um so it would not work like if they are given a 32 byte address it's going to to break the contract uh so there's a good idea by uh the epsilon team uh bridge contract i'm not really gonna talk about this today it's it's quite involved but it's it's promising but uh let's i mean i don't want to to uh to make uh false promises uh it's a very complex scheme and uh and statelessness thankfully does not entirely uh depend on it so it's nice to have but we can still launch without without it the last uh the last component is state networks so um there's the main proposal is by the piper and the python team the portal network and the idea is currently you have to get all your data uh like when you want to to participate in the network you need to download the data from like all of it most of which you don't care about so the idea is to provide a network alongside the uh uh the the block propagation propagation network where every uh every machine on the on the network only stores a fraction of the data and if you need it uh on a on a per need basis you can go and query that data to one machine or to a subset of all the machines um as you need it and that's that's quite nice because that's really i mean it has many applications first of all you don't have to to store all the data obviously but even if you want to be uh for example a validator in esto you don't really have to to store the data yourself you could uh you could uh just send uh send your request ask someone else to store the data for you and uh request the data when when you need to to propose a block um of course i didn't say that but uh that data is validated you have to pass a proof which is where vertical proofs once again are interesting although i guess miracle proofs could work at this at this stage um so the road map is yeah basically uh vertical tree is uh is almost there at least we have a prototype we have we are going to build another prototype with uh uh using um using rust vertical so uh yeah there's there's geth that currently is able to produce vertical blocks with vertical proofs and an ethereum js is interested in writing a stateless stateless client or that will just execute blocks without actually downloading the data and then when vertical has been delivered uh address space extension makes uh like can be also delivered but if it's if it turns out to be way too complex you could also uh skip it and the portal network like i said doesn't really require like vertical proofs per se so it could be delivered independently and when you have at least two but uh preferably three of these of these things you achieve statelessness um so yeah i'm uh running out of time so i'm just going to uh to uh like i had this slide to to explain a bit what uh what stateless theorem would look like uh in the future the biggest thing to know is that your data like to realize that your data won't be kept accessible forever you have to to keep your proof or you have to pay someone to uh to give you a proof um but it's uh it allows for uh for nice uh more decentralization because ultimately you you would not need to rely on on infiora or on uh or on on miners or slash validators uh the data could be spread all over all over the networking you could just download what you what you need and you could also why not make make uh like make a profit by hosting data for for other people so uh yeah overall it gives a uh it gives a more decentralized uh more decentralized world a more accessible world because uh there will be like lighter clients will be able to join so yeah all those people that are currently priced out of the of of the network because they for whatever reason they don't have the the space or the bandwidth or whatever to to join uh ultimately and we hope can can also join the party and uh yeah that's it i don't know if you have time for questions but i think it's uh hey we um we are a little bit over but i think we can do a couple of questions because um hopefully i think they're a simple one so um there's three questions here um some of them might be related to each other so the first one is what kind of proof is used to bring back data after state expiry um so that depends the first the first tree is mpt but it needs to be converted to it will be converted to vertical at least that's the plan over time uh so initially like let's say it's going to be a vertical proof yes got it um would vertical trees help lower gas prices by letting us store more transactions for block uh that's a good question uh i'm gonna say no maybe maybe vitaly can pitch in on this one i think he's in um he's in the chat but uh my understanding is uh no all right well um maybe we tell you guys to comment when you promote it in a minute um what possible alternatives are there to asp okay hey i got promoted um i guess okay the the the the question was um if i can be a uh if uh would vertical trees allow us to increase scalability um i guess the lower gas price right right right increase the gas gasoline and lower gas prices i guess maybe right because right now state size is a big bottle one of the big bottlenecks on increasing the gas limit and if we add vertical trees and if we add proposer builder separation so if we have both of those things then we can move toward the world where the only actors that need to be stateful would be the egypt builders which would be a a much smaller number of notes um so if we have that world then like we can i think like the the negative consequences of letting the state blow will blow up to like a terabyte or would be lower right so um i think uh increasingly awesome it would be safe there but then adding state expiry as well would uh allow us to go even further um we'll do one more quick one um can users pay stateholders restlessly or will this happen out of the protocol oh sorry i didn't quit here can users pay stateholders uh trustlessly or will this happen out of the protocol uh yeah i mean it's not uh okay i'm not i'm not an expert in uh in the protocol but um i know like if i compare to like clients uh that's exactly what happens so i yeah i'm gonna say yes it's uh it's gonna happen in a protocol correctly it's easy to implement let's say trent hopefully that's a satisfactory answer if not i will ask him to uh put the answer in chat and follow the discussion there thank you so much that was a really awesome overview and uh yeah appreciate your time [Music] [Applause]