Turbo-Geth and Stateless Ethereum

Transcript

although yep hello thank you very much thank you very much for coming and sorry for this technical difficulty so I'm here to present you the two things first thing is the turbojet is the the project that is going on for a while and it's also related to another thing which we've been talking about today just as a theorem as as I had tried to show on the slide so on the left there's a logo the new logo of the turbojet is just a little rocket or this sort of diamond styles and on the right there is no official logo for the stateless a theorem yet but that's what I found that ghostly that the ghostly diamond thing Maya well we probably would be better would do better in the future so as you

can see there are multiple organizations supporting this project and support in the past which we're really grateful for so let's go on so now it is so basically this project started in the end of 2017 and so as a hobby and then it progressed through the timeline so we have now a much bigger team and we are hoping to actually do make the trip get fully functional really soon really really soon we're almost there so some of the people are actually most of the people that you see on this picture are in this earnest or in this in this room you can

actually you can raise your hands guys yes okay so okay so now let's I'm gonna try to explain as quick as I can what is the main objective of turbo guess what problem it tries to solve and how it tries to solve it so you let's look at how EVM so we we talked about the state of a cerium mostly in terms of a try and is this Mirko tree but the the first insight that you get when you're looking to turbojet is that you need to look at it first of all from the EVMS point of

view when the EVM executes things in a theorem it doesn't see the try at all it doesn't care about a try it doesn't care about the Merkle tree about how these things Merkle eyes what it actually sees it sees the account where their addresses it sees their balances will they abide codes and storage data and storage data could be represented as well as a some sort of mapping it does not see the storage roots it does not see the code hashes sometimes through special code up codes but generally most of the patient's don't care about Merkle trees it's just this and this is the main like first inside so the the inside is that we only need a miracle tree when we

trying to compute the state root of the state to put in the block header and that's it that's the only use for the miracle tree and so from this insight let's see what's the next page okay so like this is a this is what I mean by this the State Route owner for state hash in in header so is you see in this picture these little things on the top are the block headers and they there are four important bits of information there which about all of them are 32 byte hashes some of them uncle or Omer hashes transaction hashes receipt hashes and the ones we were going to be talking

about is a state hash so the the whole Merkle tree state try thing is only useful to compute this 32 bytes or and as you if you're a minor you put it in in the header if you're not a minor to compare that what you've got is the same as in the header and so here if you have a very sort of simplified representation of what actually happens when you're processing the blocks so those little stars are let's say block execution in IBM and as input day they take transactions and they take some access to the state which are these yellow things and then as the result they modify the state and produce some

receipts which people can like some people call them logs I mean their logs inside the receipt and so this one bright yellow thing is the current state as the as the block execution progresses we always have something which is called current state and this is what this is what evm sees IBM cannot see most of those things in the past it can only see this state so nothing like that again this is another insight so if you look at if you're asking the question why the like this here most of the through implementation when you run in random and so-called archive node why they take so much space is because they keep all all these things in not very efficient way so now

so now let's let's look at how the state route is actually constructed so we start again with the EVM you so EVM looks at the accounts or storages as the simply keys and values so the keys are so here for the simplification of visualization I present you not the binary not the heck sorry but the coronary representation just to make it more fun and also not not just for fun but also it's a bit better than binary because it can show you some features so you can see there is a quaternary keys and it's the some sort of values I don't disclose what this values are because

there's no space here so these can be accounts or storage palace at the moment you can see they're not sorted now first step in order to compute let's say that we this is our entire state and we want to compute the statehood what we do we do as is described in the yellow paper and it's implemented in every implementation so first thing we do is that we are we sorting those keys I mean to be strictly accurate we also have to hash them first but I'm gonna omit the state imagine that we're not doing it extra extra hash in which is sort them so next thing we do is that we are making this or what I call the prefix group and so the definition of the prefix group is the group of keys that

share the same prefix and there is no smaller group that shares that prefix so if we're let's take this and it is an example these three things they share prefix to three and there's no sorry no so there's no larger group that shares the same prefix so that's the your prefix group definition and as you can see that we can group everything in prefix groups and then we can observe that we can combine the prefix groups in in a larger prefix groups like you as you can see there and so that's first step so then so it's the second step sorry and then we we apply what they call optimizations so we're if we in each

prefix group we're essentially taking the this prefix out of the keys and move them up if you compare this to pictures we move them up and we essentially away where you saw the hierarchy of the prefix group you can see now these branch nodes and so and then having this type of structure we then apply the Merc wise hashing so we start making the hashes of these things these things and then we combine we concatenate them we make a hash of this prefix group and then we do this we will do this prefix group in the end we are come up with the state root of that stuff right so it's

just basically what I trying to do here to try to represent you the semantics of the the miracle hashing in a slightly different way not in the same way as it written in yellow paper but it I believe this is kind of the more more mathematical way to go about it to introduce the prefix group so now if you look at the goys serum and other clients what they do is that they take this representation and they port it straight into the database because it was the most straightforward way to implement it back then in whatever 2014 and 2015 just take that and so the inside here's that imagine this is the directed graph so

what you saw and the Leafs here is these pieces diamonds and these are branch node and pay attention to the arrows so the arrows essentially like imagined if this thing is in memory the arrows are the pointers if these things are in database the arrows are like sort of hash pointers so what we do here is that each each figure here which has the arrow pointed in on into it is addressable and so we are when we're addressing something which is pointing arrow into it and in our in this representation and address of sir object is the hash of its ROP that's the address and then when we refer to it

from other element we use that hash as the pointer as an address so that means that we can represent so this structure on the left is the database layout on the right and you know if you want to calculate how many records do you need you need to figure out the number of these blocks which have arrows pointing into them so if you count them you will get the same number as the number of records here because each addressable block is one record and that also determines how you traverse this tree you will start from the so if you want to to access let's say v4 and you start

from knowing only the root hash first you use the root hash as a pointer and you're trying to dereference this pointer to it to find the object by it using address and your end up treating this record on here and once you read this record you will get this representation and you will be able to deserialize this object this one and then once you have that inside this object there's three other pointers which each of them is a hash and you use the same process you're kind of know that they're the address of this element like in terms of key and you know that you will need to dereference the fourth one and then you repeat the process

until we get to the to the v4 one thing to notice about this process that it there is a data dependency in this navigation so you cannot dereference this bit until you dereference both of this bits because you don't know its address and that means that you cannot paralyze it it has to always happen in the sequence and and it also means that the deeper your data is the data are the longer it takes you to to to access it so the depth matters and this is one of the reasons why here I kind of kept skipping over this the fact that usually you don't start with the actual keys but you start with cryptographically

hashed keys because then it gives you some sort of like randomization and a balance so that the adversary cannot create very deep trees so that you will pay a price of accessing them all the time now this is how the most of the current implementation stored a history of state oh no that's not it I would it will be on a second slide but let's imagine the two blocks this is the our Genesis block the Genesis or a state with three accounts a B and C and there in the first block there's a minor e who mind the block and get rewards two E's and there's a there's a transaction sending one east from from account a two

new account D which did not exist before minor also didn't exist before and so in a second block you just there's an empty block but just with the mining reward and as you can see here how the state changes here we add a new extra leaf and so you get the slightly larger tree and so here you see the a prime which means that the value of the a has changed because it it deducted one either from it and then again here we have a a prime because the e has changed it's got now four es so and if you were very naive you would apply the same principle as before and you count number of blocks

which has arrows pointed on them which are the addressable elements and you would conclude that the you would have up sixteen records in the database is that right no because as you might notice there is some deduplication could be made so you might observe that certain things did not change from one block to another for example B and C so instead of copying the same records you can just refer to the same records by by their pointers so we arrived at number 10 so this is this is how the historical state is now stored in most implementations I mean I I'm pretty much can say all of them in said but just to be on a cautious maybe somebody secretly

developing something right so now this is where are we going to talk about what we do in turbo get instead how we're going to improve the situation so I have crossed out the Patricia Terry word remember our insight that we only need Patricia tree and Merkel ization only to compute that state route so what if we separate these two things so in turbo gas we store the data in a much more straightforward way we do not try to mimic the structure of the Merkel tree we make it optimized for EDM rather than formalization and Merkel ization we solve it as the side problem

that arises later on okay so we're saying okay this is how we're gonna do it we're gonna optimize for idiom and let's see how we can figure out the the miracle miracle root problem so in this case let's say that we wanted to access these bits and do they imagine that they are not in the memory at the moment we have this thing in the memory this thing but not that and what we do interpret yes we are we know that all these things because it's a prefix group they will start with a prefix 0 and so we do range query to the database I should not 0 1 because I make it more for the for their usual humans not for

the programmers so this starts with 1 so we know it's a prefix group so we query from anything which starts from 1 so at the end we get the two results and then using some you know the algorithm which based on those prefix groups and stuff like this we can reconstruct the entire piece and plug it into our tree in memory ok so what do we do now when we store the history of state we also do it in a different way of course we have the notion of the change set so when interpret yes we process the blocks we have we basically we now change it making it into a multi-stage

process so first stage we are computing the change set we are computing everything that has been modified all the accounts and all the storage items that have been modified in this block and we actually sort them and we place them in a special place in a special bucket in a database and then other things like miracle witness creation and other things you can actually use that and so our history is mostly custom by consists of of the change sets so every time I process the block we generate the change set so for example here we know that accounts B and sorry no account which one is e and D did not exist so

therefore in this change set we are saying that they have zero values so the change set this is an important thing here is that they tell us what the values were before the change not after the change so that's the crucial thing so we say that here is a not a stays prime because the change set tells us this was the value of a before we change it and the reason why we do it is because if you were at this point after you've just executed block one you already have a prime in your current state why do you have to store it again but it is interesting what it was before in the same way these things have just appeared so we are just mark it as empty so that they have just come to the state at this point and so forth so and then

the change that are good when you're for example want to do the rollback and stuff like this but they're not so good if you let's say if you're now 1 million block later and you're asking the question but what was the balance of the account a at the block 1 what is it you don't want to go through like a lot of change says so there for that reason we have a special index which on a lat which I show on the left that for each account will contain the basically like the the time series the the list of numbers where in which blocks was this account modified and this is what we call now the thin history is one of the like latest

projects we are finishing off and when I said it's gonna be ready soon so this is one of the things that we have to finish before we ship before we release the first client and it has a lot of promise because so this is a courtesy of Boris who produced think this graph so this is actually six hundred fifty two gigabytes so some people were called archive note but I don't want this terminology because you can now like you can pick and choose what you want in your note and so this is the maximum like if you turn it on everything everything that you record everything that is possible at the moment and then you sink to to 24th to january this year you get six

hundred two fifty two gigabytes and then the way the thin history is is the change that we're testing right now you observe the difference in multiple places so we remove the receipts unfortunately here so this disregard is receipts will still need to be enabled so that was just we just didn't have the data without with the receipts so but you see that here the change set is split into two logical pieces for accounts for the storages you might if you if you're good with maths in your head you might figure out that this number is actually the sum of these two numbers is less than this one can you figure it out now you also observe that the big difference in a history of

accounts because these things are now just indices pointing into the change set and previously they were essentially duplicating information with the change set but that's basically yeah the current state so it's one of the projects we were finishing off another project that we're finishing off is solving another issue so this is I'm gonna show you what the issue is and this is the currently my personal main criticism of chop Agathe why'd I think it's not ready for prime time yet for some for lots of use cases so imagine this is so here for simplification it's binary treats no heck sorry but it will be easier to explain you what I mean and imagine this

is our entire state like 32 things yeah and because store baguette does not store the the the hashes and stuff like this it only stores the this bits imagine we shut down the node and we're bringing up again and we do need to start verifying the state route so what do we do now well we're gonna read out everything all the state the entire one the entire state which currently is about 32 gigabytes which takes mmm well and depending on your hardware might take anything from one hour to five minutes best hardware you can read it in five minutes but the thing is that you read it very efficient you just read it

like through the it's all together it's not like you have to search for it in the in a random space anyway you read it and as you read it we have a efficient algorithm for not buffering at all but we on the fly as we read it we actually compute the state route and we also keep certain number of top elements up there so we spend a lot of time optimizing this kind of stuff so we can we're very good at reading pieces of State and hashing them and only leaving the things that we need this is all kind of been worked out but still the problem is I don't want to wait one hour or whatever ten minutes to start up the node I want it quick so now what is the problem why

and and and the second second part of this problem imagine this is our cache so we obviously if we have RAM if we have some RAM we would use it to to cache some of our state trees so that we are it is quicker for us to do the state route and imagine this is our current cash so this is what in the in the memory and some transaction comes in which accesses the cold data which is not in a cache needs this oh how we're gonna get this so this is how we do it at the moment we have to issue this range query remember that was range

query because we know this hash rip corresponds to a prefix group we know the prefix we issue the range query for all the entries with this prefix we read them all we use our super duper efficient algorithm to hash it but still you have to read all of these entries just for the purpose of access in one and that's the inefficiency then what we do is that we remove this card as part of our efficient algorithm would discard those things as we go and what we're leaving in the cache which is now hot because it's been accessed we live in these things some siblings and some of the hashes so that helps us to

compute let's say if we modify this this will help us to compute the state root after the block execution but it's unfortunate I think this sort of this effect so as we we saw before that the first effect means that the the startup takes a long time sometimes but this also means that after you've started up your first let's say 10 20 blocks are getting really slow because there's a lot of cold state you have to keep fetching it until your cash grows to reasonable size so that you can go it's faster so it goes like you wait like 10 minutes for loading up the the initial state then in the first block takes you one minute and the next walk is 30

seconds and then it goes on and on in an Indian like 100 millisecond we want to fix this no way and then the next step is that because your cache is limited you you evict something show something which hasn't been accessed for a long time we evicted and these things will be replaced by sorry yeah that we fix it essentially then we're gonna just replace it with the with the hash in there but I didn't show it in the picture sorry so now this is now to the solution this is our one of our other project which we kind of coded up but we are reading to debug it so the idea is that we're gonna start actually

storing some of these hashes that would have been in a tree if we were guest or parody but they're not but still we are restoring them by using prefixes again so I the key in our database will be free prefix and they can take either the the value is going to be ya the prefix and the hash yeah so now let's look at our situation again again the same exact problem we have this kind of cash we need this element and but this time we also have some intermediate hashes stored in the database so the way it goes this time is that okay we are going to read only this amount of information only four entries from the database

we're going to reconstruct the tree and we will be much faster and as you can imagine that this will also speed up the the startup process because it will not need to read the entire state database and there are nuances in this for example we decided not to keep all the intermediate hashes but only those that where you know like if you let's go back to this so here this is a binary tree so it means that if you have a key goes all the way down each level is one bit one bit one two bit three bits four bits so if you look at this one it will be have

a prefix of one two three let's say four bits right and then another one will be the same one but the five bits so how do you distinguish between something which is four bits and five bits if you only is if you always store them as a byte so we had this problem and we just decided okay let's not store any intermediate hashes whose prefixes are not whole bytes which is gonna do whole bytes like if it's a binary tree we're just gonna here store them for every age level if it's a hex root 3 which is gonna store them for every second level level so in this case all our prefixes are always whole bytes and we should be okay we still have to test the performance but we think it's going to be enough it will

also make it easier for us to transition from x-ray to binary trees because we won't need to do special logic for that and that's the first new ones the second new ones that is that we are not keeping intermediate hashes of the things which are in memory so going back here so if this this is our cache we do not store any intermediate cash sorry hashes in the memory in in database because they're in in insert because they're in the memory so we we always have this invariant if something is in the memory is not in database and the other way around which if you give it a lot of thought you think that

you're understand it makes sense but that's what we do and that's how we we prevent the like a thrashing of the database because the the root of the tree will be the most modified like it will be modified all the time and you don't want to rewrite your database all the time so we say if it's in memory we don't touch it in a database it's not exists in there and one of our biggest the create to has always been Porter baguette because it allows you to recreate the contracts in the same address and and there's lots of pain in this but we're going to be fine we're fine you know it's a it's a hard problem to solve but yeah now oh yeah there's the baseline so we haven't

produced the the performance metrics on the intermediate hashes yet but we will soon and this is what I was trying to figure out recently I was trying to see where we're gonna go so in this is kind of a bit confusing but I'm gonna explain you as much as I can so the red line is the time in the millisecond that super gas is spending to simply execute the block so let's take all the transactions run through it with the cache of let's say 1 million nodes and just execute it and sometimes when there's a cache miss it goes into the database but the database is optimized or the for this kind of thing so then the resolution the blue line it corresponds to so the resolution

corresponds to this process when we missing something and we need to load it up from a database so in some like it there will be multiple places in the state where we have to do it and this the entire process in total I call it resolution for historical reasons it may be very confusing word but it's a blue line so you see it's like a fluctuating with the intermediate hashes project we're hoping to reduce that we just bring this blue line down and make it less volatile we don't have the data yet but I hope it will be somewhere there right and then the yellow line is what is it a stateless execution oh yeah this is actually very rough data it's just for fun to put here

like how long does it take currently for Troopa guest to ingest the witness for that block and execute a stateless lis at the moment it takes longer than executed non seriously but we always say that it will be optimized and the other lines are just essentially the range one is that once you've finished execution of the block once you pulled up all the necessary data how long does it take you to recompute the State Route and it's currently like about ten milliseconds yeah and then the green thing is that it's not the experimental feature is that what if what if we did not need to modify to try to compute the State Route how long this is gonna take

I'm not gonna try to explain what it is but this is used in our mining engine because when when we turn the mining engine in surrogates who basically have only one single copy of the Tri in memory and what happens is that the mining engine usually competes with the with their usual execution because it produces what we call speculative blocks that there would mine and usually if you were trying to mine the block they would try to disrupt New York try which is which are using for your other blocks and in order to prevent this we have this logic which where you can compute the state right without modifying a tree it's it's interesting and involved process but this is the Green Line and

I'm also trying to bring it down so that we can potentially swap it we can remove the orange and put the green instead of it and so we have it we make it the normal mode of operation we always first compute the state tri-state route and if it's correct only then we modify the tree otherwise we just don't touch the tree at all and it will help us with some situation where we get invalid blocks at the moment true bagasse suffers if you if you give it invalid block which is valid in terms of proof of work but it's invalid in terms of state hash it has to flush all the the cash from the tree because it's corrupted and then basically rebuild it again so we were hoping to remove that problem with this green thing

okay that's that concludes my part of the talk for stateless client I hope you're not too tired yet because I'm gonna go on for another 20 minutes all right so I'm gonna take all the questions in the end I'm hoping to get through this very quickly because I think it's just only five slides and a lot of things has been said before me I'm not sure if I gonna bring you any more new information here but essentially if you remember my previous picture about the block execution this is a slightly modified version here might remember that in the previous picture we had the states here like a yellow bits which were representing the pieces of the state and then there was another big yellow bit here which is the

current state what has changed those things disappeared and as it as it would in a stateless client and instead the instead of just you receiving the header and the blog body you're now also receiving as a package the block witness this is the like Lois this like looks like a some kind of building but it's actually block witness and you understand why bit later so what we doing now is that we don't need to look at state it's enough for us to look at all this information to make execution pro do it provide DM the receipts and verify that our you know the State Route matches I think it's that one or that

one no that one yeah matches them much is the the State Route in the header okay and and it answers the questions that were asked before that et is full validation in this in that sense okay so now you must you should understand why there was things like a building in there in that picture so I did this visualization which some of it Sina used it probably that part of it and he also kind of rotated at 19 degrees 90 degrees clockwise so you might remember that bit so it's it's from the same block so so we found this really relatively small block on the main net which was that 5.7 million and it was good because it only had two

transactions and one of them went to a contract rather than just so yet there was the one transactions which went to a contract which then created this blob here and another transaction simply moved Easter from one account to another and as you can see here because we touched that contract we invoked it and they probably touched some of the storage so this part of the try the Bou sorry the witness which is actually part of the try is account so you see this little you see these this vertical things are the accounts so and these things are storage items and this is the contract code and this is actually demonstrates another thing which some

people who are familiar with if you remember the employment a shion's they know that in most of them there is a certain that these entities are separate there is this account try and there's a separate storage twice what we have done interpret yes we have actually merged them into one single try and the way we did it is actually quite simple we just introduced a new type of node in a tree which is called a count node and that is the connective between the this try and all these tries which is basically simply hang the the storage tries on on to these account nodes it works brilliantly and it also helped us to to do witnesses regardless of whether they penetrate into the contract storage or

not they just one thing which you can assemble from the input okay so I hope that that picture demonstrates you how many hashes we've got because we have a hex three trees in lots of positions we have almost 15 sibling hashes yep okay just for two transaction yeah no no it was a the reason why we merged the the accounts in storage is because it made our code simpler and then it happened that it made the witness

production simpler it was simply just some illogical thing so logical refactoring that seemed to be like naturally occurring like it naturally falls out of our what we wanted to do yeah but you I think you might be right it actually did occur when we were trying to fix the create two problem I don't know I don't remember exactly how but it did happened during this change when I think Boris was trying to do this we were introducing this concept of incarnation especially especially to support grade two and then during this huge pull request we have merged the trees and stuff like that and then it's stuck and it turned out to be quite useful thing to do like to just put them and everything together and it will

become useful when we go into the snapshot sync our rhythms because you don't have to treat them in separate ways you can just look at this whole thing is one big blob and then you just sync it okay let's go on so people were showing different graphs before but this is what one that I produced so so in this graph which is actually pretty old you see we're now on almost on the nine something nine point five million but what it demonstrates is that like this is the size of the witness with some sort of moving average starting from just past the shanghai attacks because if I show deshaun attacks it would be

like over there on the on the ceiling probably maybe yeah something like that so but these are the kind of the something that said what was said before by Cena the blue portion is the hashes which you could see in the previous slide the red portion is the code called bytecode the yellow portions is the leaves those were that these these kind of thing the leaves these these are the leaves and the what is another one the orange portion is what I call the structure so the structure is the extra information that allows you to take all these things and connect them together in the correct

way so instead of having like a big soup of hashes big soup of leaves and everything else so you tell you take that and connect it all together into this particular structure that is so that what I call a structural information and it's orange it's not significant so that's where this is explains why we're looking at binary trees first because it addresses the the biggest thing and so what the girl discovered that if we do that it this will shrink like three times and when it happens the red thing will become dominant and that's why we attack in that second and that probably would shrink I don't know what the number is now but shrink further it's no point looking at these things yet and

therefore when people say that okay well you know what about different type witness encoding is that it's not really important right now because that is just really tiny compared to everything else this is not the biggest problem we have to look at so we can make the more modifications in the structure you know they will not affect that much and we get into almost to the end so this is the graph that Iger produced which kind of reinforces what I said before and the blue line is the current sizes I think these are the megabytes this is the correct thing they hear the movement average and this would what it would look like if it was a binary tree and

then this is a repeater of the Sina slide I'm just gonna so here I was just gonna say that we so I would like to to make the the miracle ization of code oblivious to what the code means so I now start to call the be oblivious chunking for various reasons and I think we have even yesterday just yesterday we had some injury singing insight about how to do it even without doing static analysis but we'll all right to download suppose we just were talking yesterday sitting in there

at nine o'clock p.m. sitting in the hotel in in a lobby with a and I was trying to explain them what is the problem with his job destination and after they said okay but why don't you do this way so what he essentially proposed this to include the list of job destination I'm sure we talked about it before include them into the marquetry but we'll we'll see that later so now the did I already start talking about reduction strategies I guess all of these were reduction strategies yes so sorry I didn't announce this switch obviously the the size of the witness is what are the biggest problems and so therefore we're looking in different reduction strategies and the first one is the binary to hex to binary second

strategy is the code localization in the matter of priorities and then there's another strategy which is non-consensus which that's why i underlies because Vitalik wants to stress this out for everybody this is not this is average case optimization or maybe even like most case of Tamizh a ssin we might not be able to use this to base our guys gas pricing on because there will be nodes which have no cash in so what this basically picture shows that if you have this size of the cash if you have like a million nodes of the state try always present in your memory and you are using

LRU eviction policy then you will not need to see most of the witness you will only need to see the witness which you don't know yet so if you go back to the this picture if you are if you have a very large cache of this stuff most of that information that you receive you already know it's already going to be in your cache so what we're doing is we taken that out and we only leaving out the information which is new to you and we're measuring how much is it going to be and with this particular like magic number million and it turns out to be a quite a significant drop we haven't tested it on

different numbers yet and that's another topic Russia research but anyway so and then there's more there's another reduction strategies which we discussed a little bit yesterday we can use some sort of CIP computational integrity proofs systems like Starks and snarks should remove intermediate hashes so at the moment we're not actually pursuing this we did some inter preliminary research on this we realized that it will require some a fair amount of professional work if we did this work we would probably need to spend like at least a year on doing this if we hire some professionals it will be

shorter but they will be have to take him out of their sort of revenue generating projects and yeah it currently it doesn't seem feasible at this point but if the project gets more traction we might be able to to justify taking those professional out professionals out of their projects to help us and there's some other like an edge case H case complexities which were discovered yeah you need to have a two proofs before execution and after because you're if you remove the intermediate ashes you lose the ability to compute the resulting state root because you simply don't have the hashes to do that so then in this case you have

to be proven twice you have to be proven that this is the data that belongs to the am the initial state root and and this is the data that is belonging to the resulting state root after the execution you also need to specially include the proof of not non-existence for certain things interior well it's not hard but it has to be said and also it makes it hard harder to split the witnesses into pieces although some people might point out that looking at this picture you know what we're talking about if we remove this blue line and reduce this basically the the CIP approach removes

the blue the blue part completely and replaces it with a fixed size proof then you know do you really want to chunk the remaining things but maybe you do but so but I needed to put that on a list anyway so so this is for completeness and I think that's the last slide thank you very much and I will take any questions [Applause] your optimization is a good one as many caches how much you referring to this

right to the intermediate interesting yeah okay no no blue ones not in RAM so here yeah okay lets me talk about so the blue things the intermediate hashes they are not in ROM they only on a desk so I when they get into ROM I delete them from the disk so this is actually interesting so when I utilize those things so they're currently in the database there and there they are the thing on the heaven Ram is this only that route so those things are in database they will help me to fetch this element with the proof without reading everything in vicinity of this element

but once they've read them what will happen so I'm sorry I didn't make it clearer so let's say that we have used those light green things to fetch this to using only for records from a database at this point I will remove those things from the database because just in case this needs they are modified they would be inconsistent with a database we we basically ensure in the consistency by always removing things from the database that we read at memory and the vice versa we are putting them in a disk when we unload them from memory so when we evict something here when we evict or not where was it we fiction yes so let's say

that we evict this in our ideal scenario when we evict things we actually add those intermediate hashes into the disk because we know that this is now cold we have to provide some extra stuff so that we can fetch it quickly later so and that means that in order to modify anything in our scheme you have to first load up in the memory so when you load it on a memory you remove it from the database and that removes any possibility of inconsistency and and there another reason why we can do that is because we use a said transactional database which was would allows us to do these things very easily we simply bind all these removals additions with the

same transaction as the basically modifies the state and push the blocks and we have a guarantee from the database that they either all succeed or all fail so we we cool with that it will be much harder to do that with the things like level DB I would say because you might be able to you might be stuck with some inconsistent hashes in your database which you didn't remove because the light turned off at that point or something like that yeah this is the person who is implemented this by the way against the attack which try to make your tree

unbalanced okay so we're not removed this bit so the in the in old implementation including topic yet the keys are still hashed before they are logically or physically added to the Merkel tree when we store them in a database even now we we use in we use in hashes of the addresses rather than addresses and the reason why we do that is because if the etherium white well we yellow paper whatever did not require us to pre hash the keys before we add them into Merkel tree then of course we would have preferred to just store addresses

and the storage locations but because we have to then use those things to compute a miracle tree it just becomes much more easier it becomes easier to store the hashes of address you might notice that everywhere we just use that hashes of addresses and store addresses it confuses a lot of people but that's unfortunately reality so we're not removing that no we keep in that because it's a consensus agreement it's like it is how you calculate the state route you Oh microphones but you still store the prefect's of the tree in not hashed way so the prefix is referred to the

prefix of the hashes not of the keys but I just wanted to make it easier for you so that you don't have to deal with the cognitive load of remembering about ashes so that's just simplified representation I thought it was ya know it's original question you know a couple days ago telling I think talked about he's one of his VIPs where he wants to merge the dia can try and the storage tries ok I was wondering how would you update your like how'd that affect your your implementation of rebuilding the I don't know how he wanted to do it but I don't

think that we will have to change much because it to my point from my point of view we don't even need the IP to do that it's just it's just implementation detail I don't know maybe there is a reason why you have to do ap for that but we just implemented it if you store the values under the hash of in the country so like the main tree also like has the hash of the account addresses but also hash of the storage keys of the country well basically the the argument here is that the this so the the hash of the storage keys of all the storage sub

trees can be looked at in the same way as you look at this intermediate hashes right like I could even in the future remove those storage roots from the accounts because I have these blue things and then blue things will be exactly what I need instead of the storage roots so what I'm saying is that it's so to me it's implementation detail you can do it if you want to in your any in any implementation may be there is something interesting that in IPS so I'm but I'm sorry I didn't look at it yeah yep slides towards the end where you said the tree structure is very small relative you can see that unknown oh yeah yeah yeah that one's okay this one

yes so it looks negligible the yellow yellow is the Leafs and then structures orange okay so the structure looks like it's almost nothing oh yeah so actually I think the this slide this your graph was done with the even like really old version of the structure I didn't bother to update it because it doesn't really matter too much anyway so it will be may be it may be now the structure becomes slightly smaller okay slightly smaller relative but this is you know visually we someone consider that this huge and that's almost negligible so it's not worth looking at but this is for the hexer II case and now we have a binary optimization we might have some more optimizations here and there and the orange relative you know visually oh yes it might be

relative Gregor yes so what is significant five percent ten percent at what point do we think that the orange is significant relative I don't know I don't have this threshold but there's another interesting thing is that this way when we go from hex tree to binary tree the structure will also reduce a little bit and the reason for that is because currently in the unfortunately I cannot I cannot zoom it in but if you look at those things there's a little like a horizontal bars what they represent is these 16 nibbles from zero like a digits from 0 to F and when we

encode this witness we need to take into account that sometimes there's not all 16 of them are populated sometimes there's 14 sometimes with 13 and so what we do is that we add a special mask that like it could be represented in 16 bytes but sorry in 16 bits bits but we do it in one bite which tells us like how to position those as children in a binary tree as you might imagine there is no such need because you always have exactly two children so you don't have to actually specify this so there will be a slight reduction in the structure branch of codes correct yeah sure

actually that's interesting insight maybe we should look at these orange part in a binary trees yeah okay Judah and fortunately we are running out of time so thank you very much Alex a well we can take it we can take it outside I think because there might be some other talks happening thank you very much [Applause]

you