Stateless Ethereum Meeting 13

Transcript

okay um thank you all in the interest of time i think uh you know there's been a couple of good posts uh they were included in the meeting invite so uh the assumption on this meeting is that uh people have read at this point um vitalik's post as well as don crud's post the two that were in the invite um and the goal in this discussion uh i think we wanted uh so piper and joseph and i were talking about having this discussion um to level set people to get to a higher level of understanding of verbal trees

especially given the dramatic change of the economics of witness sizes which is a pretty fundamental game changer for the kind of options to do in statelessness and the italics uh post also um i think we're going to talk about vertical trees um first but vitalik's post also had quite a few things about um you know the trade-offs of expiring state and some of the edge conditions on retrieving it so it's a little bit orthogonal to vertical but hopefully we get that as well so i think i'm going to hand this off to don kraut here i think um judging from last time you gave a talk don crud

uh i think um probably the focus on um the engineering view of the vertical trees um is the most useful um you know given the the time frame that we have for this meeting you unmute yeah they state the mathematical assumptions but then move on to the engineering what we can do with those assumptions uh right um okay uh i thought vitalik wanted to give a presentation on broker yeah no i i i do have some slides but okay there's

also not too many slides and i'm happy to nick dan greg feel free to kind of jump in whenever as well yeah yeah sure yeah i haven't prepared i am going to share the screen um do people see the shared screen yep um how many ghosts are there um confirmed well plus all the ghosts we can't see right i don't know just um want to confirm people actually see and aren't just falling for the vr fire's dilemma um okay so virgo trees right so starting off kind of what is a vertical tree so the

high level goal idea here is that it is a data structure that serves the same function as things like merkle trees and some merkle treasure trees um and it tries to combine at least some of the benefits of trees and cryptographic accumulators so when i say trees i mean things like binary trees and hexary trees and virtual trees and aviola trees in that whole family and when i say cryptographic accumulators i mean like either katy commitments or some like rsa accumulators or like any of these fancy mathematical constructions um so vertical trees try to be a kind of compromise in the middle of these and have a lot of the good properties of

of both them accumulators and the trees so a vertical tree is a tree of vacate commitments so you have a tree and each node in the tree has a width of um in in this example 256 but really it's a number that you can set like it might be a good idea to to make it be a thousand and 24 or 2048 instead it's just a trade-off between kind of witness size and uh proof generation time basically um but you know 256 is a good number so just like mentally it will just stick to the stick to that value and so kind of on the right here you have a little diagram you know if you want to stick the word cat dog hippogriff and hippopotamus

into a vertical tree then each one of these nodes would just represent a letter of the alphabet and then you would have leaf nodes um in this particular structure we don't bother with extension nodes we just um we just only have leaf nodes and so you do have a bit of a kind of single child extensions um but in a realistic kind of randomly dispersed account set up like you'll probably end up having around like four layers of this and then a bunch of waves um so assuming the values are randomly distributed a path going down from the top to one value will only take the logarithm base 256 of n uh so this is eight times a fewer um

nodes in the path uh going down compared to a binary tree so for example if the state size is around two to the 32 which i think is a good estimate for a medium term size then like you can go down in four steps whereas in a binary tree and you go down to 32 steps and the hex tree can go down in eight steps now one now of course there is a problem with having a width of 256 if you just use a regular hash tree right and that problem is that if you want to have a yammer give someone a merkle proof then you're sure you can give someone four nodes but each of those four nodes will have a width of 8 kilobytes and so your proof is just going to be crazy long

and so this is where it makes like the kata commitments come in right which is why we want to use kate commitments for each of these nodes instead of just making the root be the hash um so katy commitments um dunk red has an excellent presentation i'm linking to and there's a that qr code is also a link basically they use elliptic curves and polynomial math to create a data structure where the inclusion of any subset of values so you can include like say up to 256 values and really it could be any number um but the inclusion of of any subset can be proven with a

single witness right so if i have this object and i want to prove that this not the number one is at position c the number two is at position d and then some hashes at position h then i can just provide one single elliptic curve point and that can be used to verify you know just all of these values um you could even go further um so this is this multi-proofs protocol basically if you have multiple commitments and multiple leaves and this could be an arbitrarily large number of like commitments and leaves you can make a single proof like less than 200 bytes that proves the membership of all of these values right um and there's uh another linky there that you can kind of click or scan on if you

want um so basically this um gives us like so the witness size the actual witness size here right like it is going to consist of like if he wants to prove a value going down here like just the commitments that go along this path right so you don't have to provide all the nodes instead you provide this commitment over here at the top then the commitment that is like the letter h and the commitment of the letter i then the letter p then the second letter p and then the o and then the p over here you'd have this kind of series of commitments but each of these commitments is only 48 bytes and then you just like slap one proof to the ends that says well each one of these values actually is in the correct position of each one of the other values

um so multi proofs are amazing right um and now hopefully you can kind of see how these witness sizes become smaller right like basically instead of being eight kilobytes times four like you would just be 48 bytes times four um now this is the other important thing which is why we needs to compromise right so why bother with trees of commitments instead of using one katie commitment for the entire state and so there's two problems with using a big kata commitment one is that it requires a very large trusted setup and very large stresses setups are very insecure right so like for the scheme that i'm suggesting here

has a trusted setup size of 256 right and so if we want to like we could literally just do a size 256 trusted setup and that is so easy that you could just do it all in javascript and we could get like 50 000 people to participate but if the trusted setup goes up to a size of uh you know the entire state so a size of 8 billion then well you know get good luck getting more than like 10 or 20 people to be part of it and so like these you know trusted setups are not binary they're qualitative um and it's the the problem is much less bad in the n equals 256 case than it is in the end equals 8 billion case problem 2 is that computing a witness takes of n time right so computing one of these

multiples or even a single proof takes an amount of time proportional to the size of this whole thing now it turns out there is a protocol where you can compute all n witnesses in o n log in time but if you use the pre-computation trick then even a single state update so like if there is a block and that block changes a value requires you to recompute everything right so basically either reading is of n or writing is of n and you're kind of stuck if you just might have used one pure kate commandment so verbal trees are a nice compromise because if you just have a tree of commitments then like instead of this oh if like the n here instead of being n b in the state size it's just ofc 56 and

it turns out that with a bunch of optimization tricks like that computing a witness actually is quite um i'm quite fast for a three of commitments uh so witness sizes right so a verbal tree witness going down to multiple values requires one the actual data right so like let's say if you're proving i don't know a hippogryph and dog you need you obviously need like um the key the value of the key the value um then you need all intermediate cutting commitments so in this case you would need like the letter d then you need like g o p b i and each of these things are 48 bytes and then you just need this one single proof that's like a bit less than 200 bytes that just proves that all the the relationships between all of these and

that all of them are correct um so here's just an example estimate um so assuming a state size of two to the 32 and assuming you're proving 5000 keys which actually is approximately via post um eip2929 maximum not including code uh so we do want to add a gas cost for accessing like individual chunks of code at some point um but you know that we do not have this yet um so assuming these numbers um there's three like if it's due to the 32 right then like roughly you'll have three levels of intermediate commitments right so the first level so three levels basically alright you have the root but the root doesn't count

because you already have the root first level has um two to the eighth commitments the second level has to the sixteen the third level has 2 to the 24 and then the last level that has 2 to the 32 well that's like you're really your data now in practice it's not quite so clean because what you might have more collisions in some places than other places but like it's roughly about like this right so if you're proving 5 000 keys then on the first level well you there's all 256 commitments will be part of the proof on the second level you have a bit less than 5 000 because there's a bit of redundancy on the third level you'll probably just have five thousand and so in total you have about ten thousand commitments about four genetic kilobytes

the data itself i'm 160 kilobytes um actually this is a bit of an underestimate because if you have keys and values then like you you actually want the 32 bytes for the key and also 32 bytes for the value so this could actually this should actually be 320k proof 200 bytes and so the total is going to be about 800 kilobytes which is only like about two and a half times as much as the theoretical minimum right so witness size properties are amazing um witness generation and verification um there greg do you have a numbers for how long the generation of verification take oh let me i i have a sheet yeah if you continue okay

no i can find it right but like basically um it's easy to provide it is very possible to generate these witnesses it's very possible to verify them um the one um there's a i think two uh kind of nuances that change from an ethereum client perspective one of them is that these trees are very wide i mean and so like storing them in the database the way a lot of existing ethereum implementation store them in the database is dangerous because like every time there's an update you would have to store the old thing and the new thing and you'd be duplicating 80 kilobytes and so like there's there's two ways of fixing this right one is to kind of add the database layer use some

kind of a kind of like layer on top a uh a tree structure that has a yellow width and then another approach has this something that i um i made a quick uh proven concept of which is like basically just updating in place um so and then the second nuance is from a uh kind of like sync protocol perspective like you're and from a witness provision perspective right like basically in a tree structure in a traditional binary hexagon providing nodes and providing a witness are the same thing whereas here providing a nodes and providing a witness are not the same thing right and i do think that with things like snapsync we are kind of moving away

it's moving toward having a distinction between the two but generally right like if you want to if you want to help someone sync your you provide old you provide the intermediate data but if he wants to give someone a witness then it's better to just have an explicit protocol and you give someone the intermediate commitments and you give them the proof and they have a witness so so that's the kind of prepared presentation but you know i'm happy to also answer questions so if there is anything important that you think that i left out right so i just posted my statistics from my this is my python proof of

concept uh in the chat um so i mean i would expect that can be accelerated by quite a bit um because i didn't try very hard to optimize field operations um and that's the main work that has to be done there um and yeah to like so so it's all measured in seconds basically so um uh as an example if you go to the 2 to the 20 keys um tab where um one million keys are basically inserted with a width of 256 then the time to generate 1500 keys um is approved for five 1500 pieces

three seconds and i'm checking the scoop was about half a second i mean intuitively do you expect a 10x speed up in an efficient language if not way more due to optimization right um yeah we have to be slightly careful because the main operations are the field operations and and python does have like a reasonable big end implementation um so yeah i mean maybe five to two one quick question with those numbers

were those numbers using a width of 256 or 2048 to 256 that's what i just wanted so they're all in the sheet right it has i vary the width so we can see like for example for 10 bits like the time to check it goes down very slightly but um the time to generate the proof goes up a lot to 11 seconds but you would mainly like yeah more of it would mean the reason to go there would mainly be to get smaller proofs rather than to get faster bifurcation i have a question um so in our current like hexory tree patricia tree land

um we've got like five years of people figuring out how to work with the tree in a way that's efficient and fast um today kind of landing on flat database layout stuff that kind of treats the intermediate part of the tree as ephemeral and it's just sort of the the things that um people have figured out how to how to work with the x-ray patient tree and still be fast um do you guys have a sense for like the performance hit we might take as we switch into this new like paradigm um like where's the where's the scariest part of the performance of this

um i mean i'm not a database expert for sure but i like my question is why why is the database layout and the um and so so we basically have two things right we have a database layout where you actually want to access that and we have this authenticated data extract so where you want to prove stuff to a verifier and the more i think about this the more i think these two are mostly orthogonal so i think this was like basically the big mistake with the hexary tree is to like think that the the data structure the authentication has to be aligned with the database but actually this is not the case if you think about it from the beginning in

that way then yeah agreed because that's where the efficiency gains came from in the hexagon tree i think a lot of it comes down to keeping if you treat them as separate then you have to keep them synchronized with each other perfectly otherwise you right you know can end up with a a very fast database that doesn't actually represent the the real data right um yeah and i think that there's i mean my guess is that there's a learning curve that's going to come with this yes i i think so yeah i agree i guess like the interesting thing would be like if um if some of the more cryptography oriented people would work together

with like the database optimization experts and then together we could figure out like what we need to do like i agree so there's definitely like there will be the i mean it's a big re-engineering of everything right so like there will be lots of engineering problems to solve i haven't seen anything yet that can't be solved in my opinion but um that's obviously my yeah right my intuition i kind of didn't expect like a like a detailed answer because i really i think it is one of those things that there's just going to be a bunch of engineers who have to get their hands dirty and figure it out same way that yeah okay i think vitalik has started doing some

implementation of the database um for them right well i i did that poc that i linked to um i think in the post like basically i think one of the yeah considerations it's just that like vertical trees are more aminable to kind of editing things in place and somewhat less aminable to just using the hash as the key for things because that'll just require pushing a lot of data around um but um where are you guys at on having any concept of like a spec or test vectors so that we could start getting implementations like beyond research going because that feels

like one of the big things standing in the way at least of being able to start trying this and using it and seeing what it looks like uh i do not i think do you um have you thought about directly like a vocal trice in um east one yet or is it so far just worker tries in general that you have started implementing um yeah the the goal is indeed to to start using the the whole snapshot so the all the key values from the from the main tree uh i'm doing the implementation to do to this end uh yeah i'm just making sure that that

it works before i run it into the into the domain uh yeah getting all the main like the data the key and values from mainnet um but yeah when it comes to an actual test vector um yeah something smaller i mean i could produce something if you're interested uh but so far so far there's nothing that that i can provide okay right so i think like one of the things that we haven't made a decision on yet what's the best is kind of this question so one of the things that you can basically you can get rid of if you want with vocal trees is extension notes which you need in binary trees because um like you very often have like uh length of keys that are the same over

several keys um whereas in worker tries that's just quite unlikely because each time you go at least eight bits deep maybe ten depending on what bits you choose um so like the the normal inner nodes are kind of their own extension nodes already in a way um but then if you if you don't use extension nodes then basically like you can't do this trick where you make several keys for the same account that are very similar at the end because then your trees try suddenly has full depth so that's one of the things we need to think about what's the best way there or maybe actually do a couple of experiments to know which one is kind of the most promising solution [Music]

but otherwise i think i mean there's not much in the way of writing something similar to the binary tri eip now and uh and being very concrete in that i think like it's yeah it shouldn't be too difficult to spec that out but it hasn't been done yet i had one question on the statelessness side of um generating new proofs um how much of the um how much of the additional data on each 256 element you know vertical group do you do you need in order to generate a new proof do you need to actually have accessible to you the other

all the siblings you like the way we okay so there are different designs um you can make a slightly less efficient design with this whole thing where you don't need the siblings to generate well you okay you don't need the siblings to aggregate proofs you need to them so that would be more of a kind of like design where you optimize for proposal statelessness as well i don't think that that's very good i think like we should like it's a bad idea to optimize for proposals so much and we should just like hit them with the cost of this because it's really not that much like it's quite doable as i showed like i mean it's really a few seconds and you can do all kinds of optimizations and

parallelizations and so on so like um i would say like just assume that the proposers like do this and um yeah be done with that it's my opinion here um and that will save us a lot of like other problems basically if we can do that i'd like to ask um can i state that real quick just to make sure i understood what was asked um that that for like a single you know node in the tree that has 256 uh child notes i don't know um that in order to generate like the proof as you walk down through that you need all 256 and then you generate the 148 byte proof and that's all that you need to

prove that level mm-hmm right but it's more precise so the the the node right so you have you have there are two parts of the proofs right like if you go back to uh to the picture like basically you need to give all the intermediate commitments of all the all the inner nodes in between right all the branch nodes um that's one thing those commitments you have right those you would just store them there's no need to recompute them all the time um so that for that part you don't need the siblings but then there's the second part where you where you compute all these katie proofs where you like for each commitment you show that it is the child at index i of its parents and for that the way we've currently constructed it you

need all the siblings you need one i guess question for database people it's like is it bad that you need all the siblings like one of some one important assumption that i'm going off of is that like hard drives have page sizes of like four kilobytes and so um grabbing a big chunk is not really significantly more expensive than grabbing 32 bytes i think that's true that big chunk being 256 48 byte commitments right it's actually 256 32 byte hashes of commitments but yes well you could do it either way i think

yeah i'd like to ask um a question that chad is getting too um as soon as these numbers are useful for so we have numbers here for how long it takes to generate groups and to verify them but if remember right classic commitment took a while to actually create the commitment like how would this impact um like block imposers how will this impact block proposers i feel actually making the commitments no no they might expect to make the proof the block proposals make the proofs now i think the question might be like what is the cost of updating in response to 5 000 rights right yeah by the way everyone has so this this cost is um well everyone will encourage not just

uh so i think we can i think we can compute this right now right like if you the way that the storage works is that we just store the commitments at every level right and and so if some 5000 leaves get updated then there's 20 000 commitments or or maybe like 15 000 commitments that needs to be regenerated and actually no no we did that they don't need to be regenerated right exactly they just need to pick up only one elliptic curve exponentiation um well no like for well no to generate a witness there's only one but to update and respond like to

update all of the commitments you need to do um 10 000 separate exponentiations yeah that's right right so like basically updating is a bit more expensive than reading because i'm doing almost doing a size 10 000 linear combination is um significantly cheaper than doing 10 000 uh elliptic or multiplication separately but um uq like stores are already like two at least two times more expensive than loads so the gas schedule already accounts for that right so basically five thousand if we assume that five thousand reaps at the

max then it would only be two thousand five hundred right right do we have a number off the top of our head for how long a single optical multiplication takes like it should be i believe it's like in the low hundreds of microseconds right or even lower uh one experimentation 100 microseconds 100 microseconds right there we go so multiply that by 2500 and you have 250 milliseconds well for every node in the tree so multiply that by another three or four oh yes oh you're right right because

we're doing 10 000 of them right and this is a worst case block that's doing like just um entirely rights right numbers come out to about one second there we're talking yeah so worst case is one second is that um like after all optimization or is that like as we that is fairly optimized like we are talking about using a good library so that that's not that's not like python code basically i don't want to say there are no further optimizations and i guess like this is something i haven't thought about yet if you can optimize rights further there

may be tricks by which you can you can multiple you can multi-thread it that for sure yeah um but maybe you can also let the prover generate something that makes verifying right yeah i haven't thought about it it's certainly possible like basically you you want to prove that you have done some updates i don't know i it seems uh very possible that there are large optimizations there or that maybe like let's say like that you could get it down to a similar course to read um how sure are you guys about this

stuff i know that's kind of like a weird like abstract question but like like is there something else coming on the horizon that's like oh look this is better again um we've definitely agonized over this question for a long time um and like we haven't thought of why with why this is coming so late in a way why because we're like always there should be something better i guess yeah right like the things that we've like we made that kind of open call for better solutions underneath the research i mean i even reached out to dan bonay asking if he asked us something better um i think the general feeling is that in the five-year horizon like or whenever we end up one wanting to do a

post quantum switch we will have um binary trees with and that can be the same code that's like that the binary tree people have already written but just replace sha 256 with a stark friendly hash function and then us dark over it but like this technology is expected to be about five years away from being safe and so so basically there's like so we had the like hexary tree the binary tree where we had like efficiency gains just from you know not having as many siblings now we're looking at vertical trees where we get efficiency gains by effectively omitting all of the siblings right like now now you get that efficiency gain and then the

long tail efficiency gain that's five years off is basically omitting all of the middle stuff right and getting kind of like a fixed size witness plus the leaf data yep okay and that's that's a ways off potentially then 10 years you don't even need the leave data because you can stack everything but yeah imagine yes but for now we need the leaf data yeah yeah i think like in addition so like there's two things we're unsure about like right now the performance of the starks is just not there yet like it's still like a huge amount of computation that you need

which would really like i think they got to like start where did gets to like um proving 10 000 per second on a gpu right so like if you require block producers to make gpus then like that you would actually be able to generate a witness for a block in like about like five to ten seconds the problem is that this is using exotic new arithmetic friendly hash functions and we just want to wait a couple of years for those to get cryptanalyzed and so it is joel's opinion or not that we should skip binary tree and go straight to this is that the kind of assertion or anything if we like if we wants to go to go to virkle trees i think skipping

binary definitely makes sense like um yeah it makes more sense the other way around actually like it's kind of better like workers tries are better as this intermediate solution before we are ready to like get full witness compression basically vocal trice will allow us to do the statelessness now um and we just yeah can can't quite get there it's like really really difficult to get there with binary right so i have one more question on that and then i noticed that paul uh has put up his hand so we'll let him ask that as well but just because it's related to this one is so you know the reason we wanted the binary tree was that it had the property of patricia

tree that every um every hash had a specific location to find it um is that the case with verkel tree as well because i didn't see you talking about it going down to the full two by you know two to the 256 possible elements no the the tree does like it is a try right so it does like if someone comes up with keys that positions x and x plus one then like it does go to go up to having 32 levels but like doing that is hard because it would require you to like basically do to the 256 work to actually find those hashes okay so like every read course like assuming randomly distributed addresses every read corresponds to like about three

intermediate steps assuming a adversarially generated address says it would go up to about six intermediate steps or maybe seven uh okay okay and paul why don't you uh chime in now yeah um maybe it was explained already but i missed it there are uh there's a pre-state and a post state that has to be proven and there are rights of course you know if you're only reading you just have one sort of proof for everything everything that you're reading but then some of the things you're updating or you're inserting as well there's this strange thing where you're there was a node there there wasn't a node there you have a proof of exclusion in the pre-state and then you have a node there in the post state and also deleting things there's all of these strange things are all of these

sort of numbers uh that we saw i think it was 600 or 800 kilobytes do they include because i imagine the post state would need its own you know vocal tree proof there might be some deduplication okay here's what you here's what you do like basically um all of these so like they work all very similar to binary mercury it's all very very similar you just have to like basically go up the uh the try and like recompute commitments and and you always have to do one exponentiation basically for every update um what's what what what you're going to do is basically that for for the rights like you basically have to add some extra reads potentially so for example for every right

that adds a key for a right that overrides a key that's trivial like that that's the easiest case if you add a key then you have to basically uh add something to the proof that proved that somewhere is zero basically where you want to write that that is currently zero um and uh when you want to delete a key it becomes slightly more complex then you will have to like um yeah you you have to write to add some extra things because there are some complications about uh what happens when one node goes down to having only a single child which is when we want to remove the inner node and propagate that child upwards basically in the in the try um but they're all doable there are some complications like but

but yeah basically it's basically you can think of it like to write something you will add some extra notes to your to your reads basically and and then when you when you do the right you check that those were like added and you can then do everything yeah let's do it by the way and send you a comment like i think you actually can't optimize the rights because you're only multiplying by one of 256 um lagrange points so you can just store a big pre-computation table so i think all right that's one thing that's nice it's just a briefly pointed out though because i actually had the same question earlier but i think i kind of um so i i think the point is that basically

you don't need a proof for the post-state correctness right because the verifier can also just update the the commitments themselves so you don't need to have any proof over the updated commitments but like every every verifier just updates the the commitments themselves and yeah i think that's important so yeah no proof very similar to binary merchantry basically where you like where you are yeah where your right proof is basically you do already have all the nodes and you just update them well but wait for for like a normal binary tree you would need those siblings though right and the very like for worker tree the the difference is that the verifier doesn't need the siblings against still there but think of the siblings that's the proof

yeah okay there's the obvious question of throughput i think by the way before i ask this don crud did an excellent job with uh his his multi you know his his work with speeding up the computations it was excellent there was changes of basis and all the standard sort of applied math tricks that people know but thank god creatively applied it here i think and um the question is with drew puts i think the two leading candidates it's sort of purple tree after this meeting is is obviously very very strong now but the question is throughput if we compare uh

regenesis as alexis numbers show versus this i'm curious which one would have more for example transact simple transactions per second uh right i mean i i think like the the thing is regenesis doesn't directly like you could you could do regenesis with vocal tries obviously right so that is not i guess that is not the right question the question is like what we want to push for is going to full statelessness and we basically argue that once you do that like you get all these nice benefits and uh and those are worth it um but in

direct comparison uh in the pre stateless world i guess like you you will lose something like you will lose some performance because you do need to do this extra work yeah i think there will be you made a good point there will be regenesis of the leaves i think anyway because uh if some contract code gets hot for example you wouldn't want to transmit that 30 24 kilobytes each time so there might be some network level being maybe not protocol level and that might be wise to do or maybe protocol level would be wise as well i'm just curious like so downcrowd can you confirm there could be regenesis for just the leaves um what does that mean right through regions for the leaf yeah so you just don't retransmit

because you have a witness okay uh you have the leaf data it there's there are two blocks uh one right after another they both have the same code would you rather transmit that so you're saying two blocks x axis the same state yes the same leaves right could would there be a possible network or even consensus layer regenesis not for the intermediate notes of course but just the beliefs yeah i guess one other thing on this point is like so this uh post that i published on youth research um yesterday this is the uh resurrection conflict minimize state bounding like the idea like the idea there is basically that it allows you to do regenesis like things but without adding

any kind of assumptions that say you can that you can kind of poke into trees and store powerful partial things with trees um just because like the more we're making deep changes to what tree structure we're using like the more you'd have to think about well what does this mean in binary land and what does this mean for in vertical land and what does this mean in whatever other land whereas like this approach that i recommended like it does basically treat trees as a key value black box um so like that kind of approach would just um allow the the different parts of uh the research pipeline i guess to be more nicely separated and one of the questions is a little discussion there in the chat

is um yeah so what's being proposed obviously here is like going to verkl and skipping um uh binary trees but in the future in five years when stark is um you know developed and stable enough then it would be actually going back to stark binary trees is that correct right though it would be stark binary trees using some like optimized hash function so like let's like even if we did binary sha-256 now there would still be a big um transition maybe slightly less from like the direct engineering effort on

the tree but like you still need to somehow copy all that state over right into a completely new hash function that's still reorganizing the whole tree i'm backing up a bit i think you already talked about this but why would we pick 56 over for instance like 1024 what would the tradeoff see between let's using how do we choose our width yeah basically the challenge with um having but the good thing about having higher widths is that you need fewer intermediate nodes uh so like instead of uh three per data item you might be or or even two per data item you could get away with like you know one 1.5 and that would cut the witness size by a

bit the challenge is that it would increase proving time um because the proving algorithm that we've developed it's um basically for efficiency reasons it just like works over the polynomials in their uh evaluation form directly and so if you have if the width of those goes up to it by a factor of four then the the cost goes up by a factor of four and so like given that um you know it's it seems like proving time is one of the bottlenecks of the scheme and witness sizes are already excellent like it just feels like it feels like keeping it smaller is the better trade-off makes sense i guess a lot of this

discussion here has been oriented around how the vocal tree is being used by the proposers to generate a witness for validation um i think we've had the previous discussions and so i'm wondering if we can just bridge a little bit to what would this mean for um for um like clients that are looking to get the state necessary to provide a witness with their transaction what would that look like in a vertical world right so having partial state needed to generate a witness yourself is one of those things that becomes harder in a vertical world and this is actually one of the reasons why like i think the the road map that day gret and i are recommending

is to like not go beyond weak statelessness uh for like basically all the way up until we yes until we do stark binary trees um and so like basically like you would not need transaction senders themselves to be generating witnesses well they get it from somewhere if they're right right so you ask your basically ask your friendly proposal nodes in your local network or something like that like generating a single witness is really not expensive so um like it would be easy for someone to just provide this as a service like

um in the current model if you kind of have a get no data style retrieval you can build witnesses yourself if you can retrieve things individually even if you don't have the state does that map onto this can you is there a so the thing that map that same yeah so actually there's a separate right there are transaction witnesses and uh block witnesses and we will probably use different schemes uh for them um i'm i'm more talking about just like in general like let's say that i want to proof about my account okay so one i mean one thing that you could do is you could just use get no data to just request the entire sister leaves

like it's not going to be efficient but for a single transaction like it's only 32 kilobytes times n and so if you're just trying to like compute the witness for one transaction then that might actually be an okay trade-off though not for a block cool so what i'm hearing there is that there is some some mapping between vertical trees existing trees and kind of how we um you know there might be a hash that we can reference each node by and you would look up all 255 siblings and and then compute the proof yourself i guess if you know all the siblings you can compute it yeah but if someone is willing to send you

all the siblings then they might as well send you the proofs i mean it's not much more expensive to compute than yeah and this is where i'm gonna have to play around with it at kind of a you know toy level and see what makes sense so we've got about five minutes left maybe it's clear to other people so be good to just kind of outline it it's not 100 clear to me of you know what are the concrete next steps in terms of you know um making material progress here and

you know i don't i don't love if the only answer is you know don crod you know you and vitalik think about this for a while and come back to us like what else can we other people be doing here i mean i think my ask is for some simple test vectors that say this is an example tree this is these are the things that you should get if you build an implementation of this very simple can be one vector even but right i mean like for the generic for just some worker tree we already have that right but the question is probably about a concrete one that would like that you could directly plug into each one um well i guess what i'm suggesting is that

if we had that then it means that we can all kind of build not all but somebody who's really interested in this can start working on a fast implementation to and that's i don't know it's like it's the way that i learn about things i'm not going to learn about i've learned about as much as i can by reading else posts and at this point i need to sit down and do some things but you do you have seen the proof of concept that i've written i have i've been i've been ingesting it um yeah yeah so how is that how does that not provide a test vector it i'm sure it does i just i haven't actually run anything i've been bouncing back and forth between because basically you could you could use that as you are like if you wanted to

generate like make like a c implementation of this you could test it against that i think like with some very minor adaptations but yeah um i think like the best way your kind of gut sense for i know that the thing that you made in the research thing is not necessarily i don't know it's probably not perfect but like is that a starting point for somebody who wants to play around with this in the context of the full ethereum state so as i said there's like this thing about deciding whether we want extension nodes that has to be done and if we do one then that's a slight like complication and if we don't want them then we need to

think about how we exactly restore accounts basically then the account would probably be its own tree of some sort um then and then i think well then there's a question about verifying rights so like i would say like this kind of what i've done sort of should guide about 50 to 70 of the implementation but then there are some gaps to fill at that point and i think the best way is so guillermo i know is already working on this so like i think um we should like coordinate around that effort and make it happen so that we have like a concrete es1 example to play around with it sounds like another big missing piece

is the trusted setup figuring out how that works so trusted setups um exist obviously we don't want to directly like use like use that on each one but at least it's good enough for any kind of test net proof concept and so on right we can just um use something that file coin has done or something like that um yeah but then afterwards that is true like basically i think like we discussed so for east 2 we will need that anyway right we have already decided that we are going to use kcg commitments for the data availability piece so uh so we'll need to do a trusted setup

and ethereum one and i think we discussed that we about half a year so before we need that we need to really start working on that and implementing that auditing there testing that and yeah and finally doing it but yeah i mean it's a good point that that is definitely a major piece that we can't ignore right if all signs on sharding point to kcg still in the summer um i think that's kind of where we're going to put the pedal to metal and getting that done um how does he know that's his hand raised yeah how does implementing on vertical trees

in gas might affect um the implementation of the merge and geth because right now it looks like guillaume's the only person and just pointing out as well that terence from prismatic is here and she's got you know they have a lot of um community members or contributors as well who are familiar with go thanks sorry did you say guillermo is the only one working on the merge on the other side it seems he's doing both um the vocal trees plus the the merge okay yeah i think the merge work is probably largely stable at least the next couple weeks one guest side working a lot of specifications stuff

and i do hope that as we get that specifications out and begin to have a regular cadence on a call there's many more people than working on the merge from multiple clients and maybe another member of guess but i won't speak for guillaume uh but yeah yeah i mean it does feel like more resources on that would be helpful if we can find anyone like i don't think okay like the worker tries themselves will be that complex but i think all the stuff around making it work will definitely be um yeah a lot more

the last question in the chat also seems um helpful here from puja like um where in the road map the system to typically look at london feels a bit close right like for because um london needs an eep in like the next two weeks so unless that's the level that it's at no definitely not london i would say um well i don't know i mean this is you start collecting with merge work towards the end of the year and so at a certain point like if this needs to get in before a merge then

you probably delay merge a certain amount so you can ship this um i i would actually recommend doing it the other way around i don't know my feeling is we should do the merge and then get this done i do i don't know you should do both at the same time like that's at a certain point the resources would be competing so we do need to make a call on one of the other yeah priority yeah also wouldn't it theoretically at least if both are ready on the similar timeline be preferable to do the tree migration before the merge because that would kind of okay i guess so yes um i guess i don't expect

it to be available and ready before we're done with merge work i don't know then here do you have a um there's a lot of moving pieces at this point the trusted setup might end up being the bottleneck if the engineering stuff's done but i i don't have a good feel for the implications that are like how deep this goes into the stack uh with respect to databasing and and and things like that like it's kind of thing that might like affect everything and in that sense it might take some time so i think we just need to kind of push forward on the r d on both and begin to refine specifications and move things to production as they're

ready quick one on the trusted setup so can that reuse um any of this perpetual powers of tower or any of that work or is it the new yeah uh it absolutely could um though well okay so actually i think we have like two routes for to go with a trusted setup right like uh one of so like the distinction that i see is basically do we make a big one or do we make a small one like if we because kate commitments or for an eth2 only require a trusted setup of size like two to the 15 or even like going week maybe two of the 19 if we wants to kind of go up a bit right and uh be able to survive um i think future increases in the block

size whereas the setups that are meant for snarks tends to have sizes that are like way into the millions um and if you have sizes that are small then like as i mentioned like you can just stick it in a browser right and that just it greatly increases the number of people who can participate so we could even just like start with the professional powers of talon like add even more people to it if we want around how many um people are we looking to participate because um that ppot i think i don't know if it's cut into 40 or 50 people already right like my personal preference is

definitely a lower a lower bound of 200 and what size do you need for the actual vertical trees if you put the shredded data aside oh for the the for the workout trees you just need your size 256. yeah i think the bigger like and the vocal trees once you've done them like you you won't increase them right because that would be a huge change and then you can make a new trusted setup anyway so the bigger constraint is really

like data availability where you may want to increase block sizes for example this is great thank you guys yeah this is really helpful um i think everybody got a much better understanding of um the implications of vertical trees um i will get this recording out and uh send that out by email to everybody um

and uh i think um the next meeting is likely gonna be our regular monthly meeting not a topic meeting if i'm looking at the calendar correctly so um look forward to seeing everybody there unless there's anybody else with any final things that came up in the last minute in their mind nope all right thanks everybody cool thank thanks