Stateless Implementers Call #31

Transcript

okay uh everyone welcome to stateless implementor School number 31 um I've shared the agenda Link in the chat so anyway can read that so the agenda for today is first having the usual team updates then I will do um a prey muchi generation presentation um then uh we'll touch a bit on the ethereum stateless book announcement that happened some days ago and then we'll wrap up with the multi multi client State conversion topic so yeah let's start with theme

updates um I can I can start so personally I've been working well in this pretty much file Generation stuff that I will present in some minutes and I've done a bunch of writing for this stat L book so yeah that's mostly from my side um yeah I've been on holidays so not much um just also did some writing on the book or more exactly a lot of reviewing and um we were also engaged in trying to get more specifics uh in terms of what would the binary tree proving

system would like um still an ongoing effort um yeah I think that's pretty much it for now on bizu so we made some progress on the stateless part uh thas still working on the state reconstruction and pro verification uh I had to switch uh on the transition so I just started today so I will try to set up something uh first implementation like that we will be able to do this transation with bizu maybe more in the coming wings and yeah it's mainly that we did also some

modification in the gas cost part um in order to be able to manage Atomic and no Atomic implementation so and we fixed also some issue on this part yeah all on the bus side on the ethereum JS we have a merged our binary tree implementation along with some tests some of them coming from the python from ignasio and some new ones that we came up with to test some you know random output and get operations and things like that we are now working on creating like better documentation for it so that

if people want to play with it the the can and also working on U creating a state manager that will allow State Management with an underlying binary tree structure anyone else want to share some updates if not we can move to the next item okay so the next item is uh pretty

much Generation Um file or research so I will share my screens because my screen because I have some slides uh for a second okay hopefully you can see my screen yeah yeah okay so um yeah so this presentation that I will be doing is based on this e

research um post that I wrote some some days ago so if you want to see the full um explanation probably you should read this thing uh but let me share a bit more like a high level um high level explanation so okay let's start with a bit of what this is about so we already know that if we are going to change the state tree um we have to do this state conversion which is basically moving data from the existing

tries to a new try and this um task has some kind of orthogonal challenge which is we need the preimages of kak for for really doing this task so a bit of motivation and background I think most people in this call already know about this um but I think is it's for a refresh or maybe somebody else um um maybe doesn't know it so as I said before uh the motivation around this preimage file generation is based on uh this intention that we have on changing the current merco Patricia tries with a new tree uh that being a

meral tree or a binary tree it doesn't really matter for this problem in particular particular and the problem with this is that basically for moving the data from the old try to the new try you basically have the the keys of the of the existing tree are hashes AR ketak hashes uh and for calculating the new key in in whatever new tree we introduce you need the images um and the main problem is that today um the majority of clients um do not have information so the ldr somehow uh we

need to provide this information to All U the clients before this conversion starts so double clicking a bit on why clients do not have this information um basically the point is from a spec perspective the three uh keys are actually the hashes so apparently there are no motivations for clients to actually save the pre-images which basically led to many clients um not really storing this information by default um if you enable some Flags they can record these pre images but

this isn't the default Behavior so to look look at some cases um like many clients have some flat DB for accessing the state um um faster than using the tree and in these cases for example G has a flat DB which the keys are actually the hashes um the same hashes as the trees so from this flat DV you cannot really get the preimages other clients such as Aron and re have designed the key of this flat database differently and they actually use the preimages so on these clients you can actually know all the preimages

of the current state so technically these clients could do enough work on themselves to get all the preimages and other clients such as nine don't have like a flat DB yet um so they don't have the preimages uh but yeah um depending on what they end up introducing because they are working on this um they I think they won't have it anyways so yeah the dldr is that most of the network um don't have these preimages and we have to find a solution to generate this this information and and

spread it through the network so uh where does this PR image thing fit into the big picture if you want to like Ultra simplify the problem we have a today which has all the state in the Marco Patricia try or tries I should say and we basically want to yeah kind of wave a magic wand and somehow have a reality where we have the new tree with all existing data and yeah call it a day of course things are a bit complicated and this mic one is um requires some

effort so here I basically show the current idea that we have discussed before in multiple sqls and the idea is that this magic one is basically uh doing two things the first thing or what I call here the stage one is a fork in which we introduce an over tree which basically means having a frozen MPT and a new Fresh Tree on top and yeah just only doing that so as we keep executing blocks we only write to the new tree and keep the old tree read only and then at some point in a stage two we actually start the conversion

process so if we kind of zoom in into this stage one and what that means is is as I said we have the evm uh we have this overlay tree that is introduced in at this point in time this overlay tree is basically this new state tree uh bying bural tree or binary tree doesn't really matter and we have the current MPT which is read only so the way this works is basically DVM whenever I have to do a write it does this in the new state Tre and when I have to do a read it tries to read from the new state tree and if it is not there it will have to read from

the Merk Patricia fry that's kind of the tldr now after this is done as I showed here that was a stage one we have to do this waiting period so this waiting period is basically uh waiting enough blocks for the this read only MPT to finalize so we know that no blockchain reorg will um change this fact which simplifies a lot um um yeah El client implementations and also pre-image generation then um this state two that I

showed here with this black rectangle it's basically uh all this other EIP which describes the conversion process where basically you have the same set as before but what you do is on each block you add this new rule in which you move X entries from the real only micro patri Tri to the new tree so what does this mean is basically something that I show here is we Define a way of walking the Marco Patricia try and say um yeah do this deterministic working and migrate X conversion units from the old

tree to the new tree keep doing that on each block and at some point since this block since this tree is read only and Frozen you will reach a point in which you will end up moving all the state now it's at this point in time that when we are doing these movements we have to we kind of read a entry from the existing tree which basically describes a key a key which is a hash of something and we need that something to really um rehash and have the new key in the new pre so for doing this um step we actually need the

preimages of of uh of the tree and that's where this Pim file appears okay that was a bit of context so um this presentation kind of zooms into this preimage file and what it means and multiple angles of it so I will be talking briefly about distribution verifiability generation and encoding and usage so the main focus is actually generation and encoding but I will be talking about these other things um just for completeness so regarding distribution this is something that we have talked about I think last year in multiple C calls

but the point is okay we don't know yet how this file is generated how is this encoded or whatever but at some point we have to distribute the information to all the clients in the network or most of the clients and yeah how how how how we do that really and there are multiple options we have this option which is the most pragmatic one which is yeah let's generate a file upload it to multiple C cdns and just people will have it available to download this file um before the conversion starts there are other proposals uh using maybe protocol channels so we have like an in protocol way of sharing this

information or there were other ideas about you know um kind of packing the needed pre-images per block so um yeah this information is bundled per blog so you don't have to really download anything before the conversion starts each option have different tradeoffs it's not the point of um like this presentation to dig into all this but um currently the main consensus seems to be the pragmatic one of just uploading the file to multiple CDN and um yeah because this is like a onetime thing so we have to think about like complexity and any kind of technical depth that is left into the

protocol too on the verifiability side um let's assume that we are downloading this file from some CBN or whatever of course the CDN are entrusted or there can be some kind of hacked hacked supply chain maybe whoever uploaded this file um know chose the wrong file or is invalid incomplete corrupted uh you know intentionally or unintentionally so the problem with having an invalu file the problem with like just unloading the file and assuming it is correct is that whenever the conversion starts and you have to start using it uh if this file is not correct you will be blocked at some

point and that will be pretty bad because it means that you will you won't be able to attest and that would be pretty bad so we need to be sure that um this file is verifiable and there are like two main strategies for this we have like the fully trustless one which is you download the file you actually go through the walkin of the tree you verify that every tree key that um you will move is actually like this file actually has the preimage and you have to do this before the conversion starts completely because um yeah if you do that and you verify that every all information that you will

need it is there you are guaranteed that uh to be safe and that you won't be blocked in the conver process uh of course you have to do this after the mark try is finalized so you know you have that guarantee because since the three is read only and Frozen uh it's a safe assumption that in the future yeah that check will be valid another more like pragmatic approach is saying okay maybe some of your clients will simply want to check this file themselves and baked into the client a hash of the file so the client will actually download the file just hash the entire file that was downloaded and check that

that hash check matches so from that perspective we are kind of trusting the L client team but this kind of check is much faster right and so yeah I know this will be up to each e client I guess but you have those those options okay so let's move more into how to generate this file and how how we encode the information which is the main intention of this presentation so if we think about how to solve this problem like the ideal encoding would be an encoding which optimize for the spected reading pattern as mentioned before the working algorithm for the uh way we have

to move data is known so we actually know which preimages we'll need in which order and even in each block right um because how many things we move per block is a fixed number um so yeah ideally the way we read this prage file should be aligned with that reading pattern so you can have the lowest amount of overhead from the resource perspective another thing is yeah ideally we want this file to be as small as possible uh I wouldn't say this is like a incredibly critical constraint because this is a file that you only download

once but and yeah I mean if it is as small as possible it's better than if it is bigger and as I said before uh ideally we want to make this generation and encoding not really be complex because it's like a onetime thing if we kind of come up with a really complicated encoding for the file everyone will have to implement that uh we have to you know test it a lot do some fasing and all that uh so the more the more complex the encoding is and the more work we have to do to to know that we are safe so there's like a super simple and obvious encoding for this file which is

the one I show here in Red so um the the encoding is actually incredibly obvious and it just um appending to the uh flat file the bites of the perimeters so for example when you start the conversion process you start with the state um the state the the account try so the first thing that you will move is some address a this address a might have a storage try so you continue in that storage try and the first key in that uh storage try is some storage loot a so you put the bytes for that and then

you continue with slot B for that account a up to maybe that's the last stor slot you continue the walk with some other address B and you yeah continue with the storage try so this is basically putting the 20 BYT address a then 32 bytes storage slot a of address a 32 bytes of slot B of address a and it's simply like the the minimal amount of things that you have to add to really provide information this encoding doesn't have any overhead like this is like the minimal amount of information that you need there's no

like prefixes or something like that um this is not entirely needed because even if address a is 20 bytes and storage slots are 32 bytes whenever you are working the tree you already know which kind of preimage you need to read if this is a storage slot or is an address so the reader already knows if you have to read 20 or 32 bytes so there's no need to really put a prefix here which is really nice and the other benefit is that you are doing a linear forward only read because the order of this stuff is actually the working order so that's really nice because you simply read this

linearly which is really nice for for diss so I created a tool for actually generating this file with this format uh you can see the link here I basically use a a r node database it doesn't need to be an archive node it's just simply a full node and yeah you have like a pre-image tool uh and you have some commands so so there's like this generate command with which basically generate this file and there are some other commands for other things for example the verify command where you can have a block we have you can have this for example downloaded

file from somewhere and you simply verify that this thing is correct and this other command is for something else I will say later um let me check the time okay I will be a bit faster so if I generate this file with this format the generation time is 1 hour the uncompressed size is 42 gigabyt and if I compress this simply with STD this compresses to three six gigabytes so that's kind of the big picture now there's like a fair question which is okay which is the encoding efficiency of this

because if we look at the format we know that everything that is an address something so any address isn't duplicated because whenever you walk the account try the these all these accounts aren duplicated so that's fine and some value address X can be compressed because it's basically a hash output so I mean this is not compressible information so from from that perspective address X think in this file um we we can't do much about it now for storage slots X kind of values they are duplicated because for

example there can be two accounts that both use the same storage slot so that means that the file will have M multiple times this storage slot for example one so this is duplicating information and actually the the preimage is a 32 byte um bendian encoding of this number so this storage log number one we have like a lot of zeros right so there's like a lot of compression opportunities not only for like zero prefixes but for example even if you have an

array which is the entry in a hashmap so like the actual Base address is pretty random all the entries of of the array will have the same kind of prefix so um yeah there are other kind of compression opportunities so in this same tool I did this storage slot free Command which tries to dig into these details and here I'm showing the top 20 um results so let me explain what this is doing what I'm doing here is basically saying okay I want to know from all the pre-images of this

file um how many repetitions I have for a 20 n by prefix okay so the idea here is for example all the storage slots that are top level contracts um variables will be in storage slots 0 1 2 three four five six or whatever right so all those will have this prefix which is basically 29 zeros and the last three bites will be you know will change right um so if we look at all the of the file we have around 70 uh 55 million entries which accounts for 1.5 gigabytes of the

file um here's like a relative measurement um for example the second item most repeated prefix is this thing and if you think about it this prefix corresponds to um the cat hack of storage slot number eight so this is basically showing that for example arrays which are at storage slot number eight um are like on the top are like the second most repeated preimages uh because yes this this array will have multiple entries and all or most of the entries will have this

prefix right so this accounts for three 13 million uh so I have here like a cumulative thing so if you move down you kind of start seeing like how much the top n prefixes account for the total size if you want to see the full output there's here in this link um right I show the full 1,000 things it's a pretty long thing but already like seeing this um percentage you can see that there's no like low hanging fruits and the tail is pretty long so I think that's good to have a sense of of of what the the things are

okay so coming back to encoding we can have this op one which is okay let's not really do anything else and simply use this Ultra simple forward read only encoding uh using STD for compressing the file already compresses all these cases in a kind of automatic way without any extra implementation effort uh and it saves around six gigabytes right now another option is saying well actually I want to do some custom d encoding to really try to come up with some clever way of solving this within the encoding

format so we will take we will remove this automatic compression because the encoding itself will will try to do the duplication my take on this is that might not worth it because if you look at the file and the you look at the top 1,000 storage loot prefixes and you go to the bottom that accounts for around 4 gigaby of saving so there's no like a there's no like a a clever way of saying yeah let's simply D the top 100 prefixes and that's kind of enough for getting something better than just

compressing the whole file so my I think that my uh take on this is it might be better to maybe simply go with the simplest option of course we have to discuss this at some point but um yeah the compression the automatic compression already goes further than compressing the top 1,000 prefixes um so yeah that's kind of the the the kind of insight I want you to have to really look at this pray images and have a sense of how much it is worth uh going with something more complex okay and finally regarding usage of this uh simple encoding um yeah as I said

before it's only forward read so El clients whenever they use the file can keep a kind of a a cursor of which is the current place of the file for this blog so um this is really nice because if you have some kind of chain reor you can simply seek the file into some previous place that you already know so handling reor is pretty simple you can also do some kind of preloading so you kind of load in memory the next 100 blocks so you don't even have to go back and forth in the file to handle

reorgs uh or amortise these grids um with time instead of doing one per block or similar and if you want to go while into saving dis space because you have to yeah somehow store this 36 gigabytes or whatever um I know maybe after some finalization point of the chain you can start deleting all uh entries of the file and save some space but I I don't know if it is worth it really so yeah that was the presentation um thank you for for your time and I know if anyone has a question uh yeah go um just one quick

remark maybe misunderstood something um but if you go back to your slide basically with the format where you basically say you just concatenate all the prage in the order that the client is expected to use them um but these prees have different sizes right depending on the type of data that actually get or it's an account slot or a storage slot right yes right correct um but I mean I'm just wondering because I mean whether it if you do compression anyway whether it would be better to just use the same length for everything because as of now I'm having a different size here has two downsides which is that in case of a reorg um if you you said you can use a pointer just something into your file but the problem

is if you basically go back you need to know how far you get back into the file because if you go back I don't know 10 units you need to know how big those 10 units are in actual bytes which depends on the type that you just read in the last 10 slot so it's actually a bit more complicated here um rather than if you just had the same size for each data item and just refix it with zeros you would just know oh I need to go to this position in the file which is arguably easier from an implementation point of view um the second problem is um if you I mean it's fine if you use a CDN route of Distributing the preimages but um due to the fact that these files have different lengths it gets much more complicated if you want to sort of Chunk

up your pre-image file into several chunks and and verify them individually because you it's hard to sort of seek into the correct position if you don't know sort of the offsets coming from the different lengths and if you're using compression anyway I would expect that just prepending sort of the shorter PR images with zeros just to pad them um the cast in sort of distribution get gets pretty much away because sort of a comparation algorithm would probably take care of that I'm not sure whe this is a better idea just something I that I would think maybe easier actually from an implementation point of view yeah yeah I totally agree with that um because if we use some compression for the file yeah making it each pretty

much have the same size will definitely simplify the cursor thing because moving back only depends on the number of of conversion units you do per block instead of that plus which kind of entries you like that block has so yeah um and yeah the compression thing will basically remove all that like overhead so yeah I think that's a an interesting idea to to simplify stuff uh yeah just regarding the reorgs that's actually not true because we save if we have a reorg we have a pointer to where the blog started reading so we this is saved um so we can

I mean at least we we have an efficient and easy algorithm to do this so the the reorg itself at least is not is not the problem yeah should mean you can do it was just it's easier to do it because you don't have to just it's more easier way to do it uh I think there was the third point I just don't remember what it was like there was the compression there was the reorg and you said something else uh yeah if you sort of distribute the pre-image file sort of into chunks then you would want a client to sort of to get I don't know the third chunk of the pre-image file you would want to um be able to verify that chunk individually without knowing what the first two chunk

are and for that you need to know sort of where in the globe the total file this thing starts that is harder to get if you unless you include some additional information where it starts into individual chunks it gets harder I mean if you go via CDN it's not a problem but if you sort of do other routes it gets more complicated yeah so we didn't think about Distributing it in in chunks uh that might be an option we just haven't considered that at least I didn't um but I would say in that case what I would do is add the header to which account right uh okay maybe to clarify the the verification is pretty simple you just start uh in your database at address

zero and you go over the file and as you go over the file you go over all the key values in your snapshot or your flat DB if you do the same thing if you do with chunks instead of starting at zero you could have a header that says this chunk starts at hash so so and so and you could do the same thing um yeah okay I guess we could do this that wouldn't be at least that be workable yeah I mean it it's it's definitely workable I mean it was just the comment that it would be easier if you it would just be easier if you just use the same size not that it's not workable because you wouldn't need that header yeah anybody

else yeah go ahead sorry no I was just thinking uh I wouldn't know if like for example you had to ch that was you know stopping in the middle of the contract storage but I guess you could have two hashes instead of one and yeah okay I think uh okay let's uh yeah I don't want to to hug the the call I think it's workable I just have to think about it yeah I think at some point we have to resume this conversation about if this CDN it seems to be the right I mean I have the Sensation that until we discuss this in ACD we will never know for sure this these are the kind of things that are pretty hard to be sure about until like the real discussion happens uh but

from from what we have discussed in previous seq calls and in the last Deon with gon we met with the with Piper and other people from the portal Network it seems to be that most people seem to agree that the CDN might be like a pragmatic way of solving this but yeah probably we won't know until we discuss in ACD was pretty tricky um okay uh the next agenda item is the ethereum stateless book uh maybe yam you want to mention something about that um yeah we we wrote um the we wrote mostly ignasio I was just reviewing uh the stat

books so it's at this available at okay already gave the link stat. FYI um maybe if I can share my screen I can go over it quickly uh so where's the question here we go um can you see can you see my screen yeah yes okay cool yeah so we basically uh start with something fairly simple like why you know what is the reason for stateless uh there's a we discovered there's a lot of people that you know are not working on the stateless topic day today and they're

asking questions so you know of the of the utility of of stateless so we we have some some ideas we have uh a few things like we go over the design of trees so how we encode uh the the data in the tree how like we have we we go over the 31 byte uh chunk model we want to add the 32 byte chunk model later so it's a living it's a living book it's not complete uh but nonetheless we talk about veral trees we talk about binary trees we talk about the block hash uh situation um we talk about EIP 4762 why we had to remodel the

gas and what does it do basically uh State we talk about the state conversion so I guess that's going to connect to the next topic but we explain the we we give explainers about the eips um the pre-image distribution that ignasio just talked about um and then there's a series of use cases that we are going to expand in the coming month um as well as a series of resources I mean most of them should already be known to you it's a they're taken more or less verbatim from from from the ver the old veral doino website um and actually I'm not sure oh yeah right and we also have information

about the current Dev Nets uh how to run the the execution spec tests uh if you want to contribute I mean you guys should not need this but uh people who want to contribute might look into into this and of course there's a summary of all the previous uh s calls except this is U this is the first oh no right um this is the the history so we have um we have the list of all or at least we want to list all the previous sick calls um and I don't know how far it goes actually I um do you know ignasio I mean you know you wrote it um yeah okay so we started at call

2021 okay uh yeah so that's pretty much it if you're not aware of that already have a look it's it's quite good and and if it's missing something of course let us know yeah I just want to say that this repo is public so um we are inviting people to collaborate or fix things so f for to open PRS or or whatever okay um next and last item is multi client state conversion um yeah maybe you want to leave this one

I give a bit of context on some conversations we have been uh we we have we have with the research team about the future and all that so which are like a good way of moving forward y um yeah so we want to have some we did have some conversation with the research team trying to to make sure that what happened with veral does not happen again um and trying to fix the road map maybe not entirely but at least well enough that we can uh we can work we can you know deliver something like clients can deliver something um without without having the taking the risk of having to

to start again uh in uh in two years um and one of the I would say decision points although that's not really up to the research team to to decide guess it's I mean not alone it's it's more like an ACD conversation to have um but at least one agreement or um one yeah agreement of what uh how the decision can be taken would be to demonstrate that um that the conversion it is easy to do which uh which I can tell you as the as the sole implementor of the conversion in gu um well actually sorry ignasio this it's a it's teamwork

but as the sole team who implemented the conversion so far um we we know it's fairly easy but we want to prove that it's easy if you do it in a in a multi client context so um yeah we would like to invite you to focus on implementing the conversion and um ideally we would be a B to demonstrate uh some kind of Shadow fork in you know the next um ideally three months but six month at the latest um that should be doable so I mean feel free to descent um but from what I

understand it's uh it should be fairly easy to manage we we can of course Provide support and um and yeah um if um sorry I forgot my train of thought but yeah like basically we want to we want to to focus on that maybe more uh urgently than working on the next test net and uh and so if we could if we could get this done I think that would go a long way to prove that the model of stat less well probably with binary trees is the viable one in the for for having a fork a stateless Fork late 2026 and more realistically you know early early

2027 for testing the state conversion should we uh well do we have a finalized dip for that and should we do it with veral as a Target or are we aiming for binary as a Target so it doesn't really matter uh I mean I would say veral because uh indeed like the the whole binary tree there's a lot of things to to still flesh out what are the what proof are we using what proof system are we using uh what hash function are we using um I we like we want to Target Poseidon but posidon hasn't been proven I mean never

will be proven secure until it's broken but at least um the effort that the etherum foundation is currently leading to to break Poseidon is is ongoing and is going to take uh at least a year and a half if not two years um so I think currently everybody or most clients in this uh in this room have uh have implemented vertical trees there's no urgency to to replace it like I said the EIP the tree structure itself is pretty easy to implement and the proof system is completely undefined uh whereas for binary trees I mean whereas for veral trees the the tree structure is well known the proof system is well

understood it's already implemented and uh the idea is that you can switch like the design of the binary tree EIP is designed in such a way that you can swap binary trees like veral with binary trees in no time or very little effort so it doesn't really matter uh and I think at this point verco is the is still the the way to go yeah ignasio yeah I want to touch on a question that Spencer did in the chat and yes I'm planning to start working on execution spec test for the conversion last year I wrote a hgmd dog with all the test cases that would be

worth testing so I kind of already explore like all these kind of Border cases and things like that so I can start working actually implementing these test so I can give like these fixtures to clients and we can actually test implementations without launching devance and things like that which is yeah pretty nice for for everyone to to move faster so yeah the answer is yes I guess Spencer yeah please get in touch okay um anyone else want to mention something else um about this

topic or any other topic we have some 10 minutes before the call ends if not we can finish early yeah I just have a quick uh maybe something to add um I don't think I missed it there's um if you look at the EIP of the conversion EIP we translate the code sorry the the storage before we translate the the account and in the binary like flat file form it's the other way around the the account comes before the storage and I I got confused for a minute uh but we need it this way right ignasio uh I got lost a bit why why does

binary matter here no no there's no binary it's just the conversion itself so you're saying that we first migrate the storage in the right in the IP we first migrate the storage and then we migrate the account but in the flat it comes right so yeah I agree I agree it comes first the account and then the storage so for a linear read we will have just flip this order yeah I mean I don't have like any push back on that I don't know if that's the case for every client I guess this depends on how the flat database is designed for each client right no no the the reason why

the account comes first in that case is because we need the account like we need the pre-image to for each slot we need to have to know the address to do the hashing uh but I was confused but I wanted to you know bring people's attention to this like the order is inverted but there's a good reason for this is because you need the address to compute the storage uh key slot of the in the Target train right so the thdr is that probably we will change the IP to flip this order right uh I don't think we can okay let's take that offline then uh but yeah you see there's there's a bit of a confusion we need to refresh a bit on this okay um I think that's everything

for today uh thanks everyone and we'll see we see you again next time thank you thank you for leaving byebye thanks it thanks e

e for