KVaC: Key-Value Commitments for Blockchains and Beyond

Transcript

perfect uh hello everyone uh my name is srini srinivasan and i'll be talking about one of my recent works with shashank agarwal titled uh key value commitments for blockchains and beyond the primitive reconstruct is called quack like a duck quack kvac so that's what i'll be talking about today um as i get started i'd like to talk about uh i i'd like to tell you a brief story on uh why why we're thinking about this problem and that has to do quite a bit with ethereum itself and in particular ethereum one point x uh so one of the things that's been

uh gaining a lot of importance recently uh within the ethereum community particularly because of state bloat is the concept of stateless clients so can we have uh clients and nodes maybe many of them maybe all of them we don't know yet that could support this feature of being entirely stateless where they don't have to store the state the growing uh state of uh ethereum in order to verify uh blocks and and and further add to them potentially so this is a concept that was introduced way back in even even in 2017 and has been gaining a lot of attention

since within the past couple of years and the idea is something like there is an implicit of course like ground truth state that that is agreed upon uh by the people who are using ethereum um but you don't want people to carry around or store this state as much as possible uh traditionally what will happen is you have this state and then you would you would make claims about certain uh entries in this state and then people could just verify them because they would have the state in hand but what if i try to do something else what if in the effort of going stateless now what we do is in addition to claiming things about the state since since the person who's listening to you doesn't actually have the state you

provide them with proofs right so you provide them with what's in the state and a proof saying that you know what uh this is actually what is in the state and even though you don't have the whole state i can prove to you that what i'm saying is indeed true uh so that's the idea uh behind uh stateless client stateless validation essentially but how is this going to work right so so let's actually see how this would translate to in terms of concrete uh realizations of a state-based client so the state and ethereum is uh organized in the form of some kind of tree or try i mean uh choose your pronunciation um and of course uh it could be severely optimized right

so it's some kind of tree structure uh that's optimized in a certain way but then effectively if you want to encode this in into some sort of serializable fashion you use something like an rlp encoding and you end up with essentially a dictionary or a key value map right so at this particular address you have this particular value and so on this is an encoding and this is important i've highlighted key and value because this is going to come back later in the talk so broadly you can think of the structure even though it's organized maybe implicitly as a try it's concretely organized as some sort of dictionary right and this is the state this is a huge dictionary that represents the

state of ethereum and now how would you prove things well going back to the implicit representation of a try if you want to prove something let's say for instance about the the green note right at the bottom right there uh you would essentially give uh the merkle proofs on the path from that leaf all the way up to the root right so that seems simple um i mean concretely this would be you know you go traverse up the height of the tree essentially and you'll give a bunch of hashes and then verification is easy you just do computation of so many hashes and then you're convinced that this is indeed the value stored at that particular leaf in this try but of course things aren't quite as

pretty as how they're shown in this picture they're quite a bit more ugly right there's a lot a lot of the state is huge and then you have issues when it comes up to like also having smart contracts and then the state of the smart contracts and and so on so it's actually a pretty big structure and now if you ask okay fine so let me actually take this monstrosity and ask what is going to be the cost of doing merkle proofs on something like this it turns out to be somewhat high right so the block proof size in total will uh if you if you look at some sort of estimation of this seems to be around one megabyte right which is pretty big uh and if we want to look at a split of how we get these numbers

uh roughly if you want if you look at the code the code bit of it the smart contract benefit that goes uh into it this is going to be something like 250 to 300 kilobytes and then the rest of it is somewhat evenly split between regular hashes right hashes for showing non-contract uh uh variables and then uh roughly about the same for showing stuff about smart contracts right so really apart from that 250 kilobytes you're spending 750 kilobytes proving hashes and quite a lot of them um and and this is kind of the ground truth if you if you if you think of uh trying to do full state with clients

this is the this is going to be the cost if you're working with merkle trees so this is a big concern right so the size of the block proof being one megabyte is is is quite a lot now we could call this down a little bit and ideas have been explored like for instance you could say you know maybe nodes are not entirely stateless they're somewhat stateless partly stateful so you keep around some say path like an idea that has been explored as you keep around say past block proofs right so you don't get rid of all of them and remain entirely stateless you keep some state and then maybe you don't have to send all the proofs every time you want to prove something to somebody you assume they have some of the proofs already and then you send the additional

ones and the other thing is of course to use things like starks to to maybe take all the hashes and make one proof you know that all that that you know all the hashes that would uh eventually lead to the proof but again this this could be somewhat uh difficult i mean a lot of work especially today a lot of work is going into uh doing proofs particularly on merkel hashes but but yeah i mean uh the cashback hash that's used uh in ethereum it is pretty it's going to be pretty expensive in terms of writing a star proof so that's something to keep in mind it is an avenue that's being explored but let's look at the other one because it's a little like easier to make progress on you know just look at

statelessness as a spectrum or statefulness as a spectrum right so you can be completely stateful which is what kind of what you have today and then or you could be completely stateless now if you do something like partially stateful right so you store 250 blocks the past 256 blocks or something like that uh then we observed that you know you you could get the proof size drastically down from one megabyte you fall to something like 200 200 kilobytes or 175 kilobytes right which is which is a drastic gain so this tells us that well if you think of statefulness as a spectrum this could actually this is actually viable and the and the other

sense it makes uh uh it makes sense to think of it is that the more stateful nodes essentially are going to be working with a large state within themselves and so they have to do a lot of work in terms of io memory and so on and of course bandwidth for communication goes down though because you don't have to send these proofs and of course if you're more stateless then you don't have these memory issues but then you need more bandwidth because you're going to be transmitting larger proofs uh so so it seems like statefulness as a spectrum is probably the most practical way we can think about bringing statelessness into uh into ethereum and uh that's sort of my short summary on

what's been going on with regards to statelessness in ethereum uh particularly one point x and and this is actually a somewhat condensed version of many many blog posts that have been uh written in in this uh so i didn't come up with the same one x files by the way it's too cool for me to come up with it's actually existing an existing series of blog posts on on uh that follow the development of statelessness within ethereum one point x and the ideas that have been uh explored right so i i would definitely recommend going through them because they're written really well and uh and and it's truly exploratory in the spirit of research and trying to

find out what's the what would be the right way to get this going right the summary is that statelessness is here now and i think one of the things that is mentioned in this blog post is that even before even for ethereum two right so uh this would probably be an important feature so uh statelessness is something that we should be working on uh right now to get where and and to find viable solutions because that's going to be important as we go ahead and that's where our work comes in key value commitments for blockchains uh in particular this is essentially going to be key value commitments for say stateless uh validation stateless

ethereum if you'd like to think about it uh so our work uh is essentially we construct a key value commitment if you don't know what that is yet don't worry i will define it later but it's a primitive uh that has very efficient representation particular just has two group elements uh like two big numbers maybe you think about it that way and has very efficient operations where you can modify the underlying structure very efficiently you can add stuff to it take stuff out modify things inside and so on and uh you don't there is no implicit uh uh assumption on how big the structure we're operating with is uh so there's independence with regards to the size of the map

and then we can do additive updates oblivious to prior value again this would probably become clear a little more later uh once we talk about key value commitments it basically means you can modify the structure pretty easily okay so as a side note our work kiva commitments that kind of subsume uh two other primitives that were introduced before this which were accumulators and vector commitments or even sub-vector commitments so we get state-of-the-art accumulators and state-of-the-art sub vector commitments kind of as a freebie after constructing this key value commitment so why why did we do this again we talked about it now that you have the context it's for stateless validation of block chains and as we recall

statelessness is here and now this is a problem we should be looking to solve okay but how does this even like fit together right so we do know that um we're we're thinking about statelessness and i'm telling you key value commitments are the way to go so what is it and really the power of cryptography or i guess like any science in general is the power of abstraction right so so we're going to think about statelessness uh via abstraction essentially statelessness is enabled by having state that's compressed yet verifiable right so there's some state in this in the case of ethereum it's this uh maybe this tribe which eventually

gets organized as uh a key value map or a dictionary as you recall and uh the fact that i can compress it means that i can effectively become stateless right um but even though it's compressed it's not losing information completely because i'm able to verify things about this state right so that's the idea of having the state being compressed yet verifiable i'm able to show things about this state right and then the cryptographic security properties say that you know you can't really cheat me right so even though i've lost potentially most of the information about the state you can't trick me into believing things about the state that are untrue

and that comes from the cryptographic security i mean if you think about it merkle trees are tries are doing precisely this right so you the whole tree or try is compressed into one hash at the root right so the whole state is compressed into one hash but by providing hashes from the leaf to the root you can convince me of elements that are rightfully inside that state and because of the security of the hash you can't really convince me of things that are not in the state so that's so merkle trees or tries are basically an example of this but more broadly we can think of you know we want statelessness that is enabled by compressed yet

verifiable state right and this idea has been around and by changing the data struct underlying data structure you'll get new primitives right so accumulators which are probably the oldest and merkle trees are in some sense an example of accumulators have an underlying set that gets compressed vector commitments have an underlying vector that gets compressed and in a similar manner key value commitments are going to be key value maps or dictionaries that get compressed right so this data structure matters because you want to think about which data structure you're actually working with and the reason is you might want to do operations on this underlying data structure

and uh you pick the right one that lets you do these things right so if you want to update things in a particular way and or you want to add entries delete entries or reorganize the structure maybe whatever right so you have operations that you want to perform on this underlying data structure on the state and ethereum as we're thinking about the parallels uh and those should be supported efficiently even though now i'm working with a compressed state right so that's really the key point so accumulators as i mentioned work really well for uh situations where the underlying data structure you want to work with is a set so utxos the utxo model makes total sense because

you have a set of utxos and that's the state i can compress it and i can provide proofs of membership right so this this works really well for that model but once we come to um account based systems then you're looking at something that's quite different from a set uh sometimes and and probably even recently people think about it as maybe like being even a vector but really the right uh the closest approximation is a key value map right and as we looked at it before once you do this encoding and serialize the state it is essentially a key value map um so this this is probably the closest data structure that you want to think about

and then you want key value commitments which are essentially a way to compress a key value map right so you can think of it as a count ledger or essentially the whole state of ethereum which is kind of represented as a key value map and then you could provide proofs with respect to the values corresponding to keys right so you could say that um you know here you can say that the first entry the value is v1 right and i can prove that i can prove that at key shot 3 of rlp encoding of that 1 2 v 1 the value is v 1. so that's really what you want to show right and then once you show that you can convince people about what's happening

within the state so let's actually look at a definition of this primitive uh essentially once you do the initial setup generate the initial uh commitment to the empty map you can add key value entries right so you can uh take a a key value pair k comma v and then insert it into into this existing commitment what that means is implicitly if you look at the underlying key value map a new key value pair has been added right and then you can update the value corresponding to keys and we support additive updates the reason is we were thinking of uh maybe not all the way up to smart contracts but just to begin with uh if you're thinking about simply

updating balances you know making payments uh i want to be able to pay somebody which means i need to be able to decrease my balance by some amount which is essentially subtractive or additive with a negative sign and then add the same amount back to someone else's balance so i want to be able to do this operation and i want to be able to support that right so that's the the update operation now the thing is uh in each is these processes especially when you insert elements and and so on every in order to prove things right so if i want to prove something about my balance i need a proof we've talked about in statelessness you don't have uh no one's essentially carrying around the

the full state so if you want to prove something to them you need to provide a proof right saying uh my value is 5 and i can prove it to you right so there's a proof pie associated with my key that i can show that would convince a verifier that the value is indeed what i claim it is right and but this proof is going to be um how do you say somewhat fragile so if the underlying struggle underlying data structure changes the proof is going to have to change and this is an inherent like lower bound is not something you can get across it has to do with the fact that the state is now compressed and you can think of

it this happens in every every case right even in merkle uh trees your proof you could could change because if i change the value uh at some part particular leaf all the hashes from there although to the top are going to change i mean the the commitment itself would change and then hashes along the path will change now it depends on where you are with respect to this changed value on whether your proof would change a little or a lot uh but yes in principle you are the proof is going to change so this is something to do with compression and not to do with the merkle or non-merkle if you're if you have compressed representations this is a cost you're going to have to

pay so that's the operation proof update is essentially to keep your proof uh current if you want to think about it that way if the straight has changed your proof has to change and then a verifier can verify the proof against this commitment for a given key value pair and be convinced as to whether that key value pair is exactly what is in the map or not uh and what are the things you want you want correctness right so if you do things correctly proofs are correct they verify and so on and you want key binding that is you can produce proofs for keys that don't have any value associated with them or if they do have a value you can prove an an incorrect value so if the value is 5

you can't prove it's 10 right so that's key binding and that's again the cryptographic security right so similar to proving that the value at a leaf in the merkle tree is is something specific you can't claim another value because of the security of the hash similarly we want key binding that says you can't prove another value against a key okay good so this is going to work really well for for an account based model as we've discussed the question is do we have solutions for this and the answer is not quite before our work there were some other issues and uh particularly for people who have looked into you know can we use rsa type schemes and things like that these are some of the issues that immediately come up

and i think are on the top of minds for everyone so um the first one is sometimes these constructions have a bit by bit efficiency right so in other words if you wanna if you're thinking about values that are uh 200 bits 400 bits you're gonna have a scaling factor of 200 or 400 in terms of how big these commitments or the proofs are going to be and that's too much you don't want to you don't want to deal with that the second is some implicit bound on the size of the map and uh and the worst part is sometimes the constructions their concrete efficiency depends on this bound right uh and that's a strict no-no i mean we definitely cannot have

efficiency depending on the size of the map that's not okay uh but what about having an a prior rebound on the size of the map well uh sometimes this manifests as larger public parameters which i guess is also going to be too much depending on how big the structure is and even if you didn't have that in in a world where the the the state is growing so quickly it's probably not going to be reasonable to think of a long-term bound other than something just you know exponential or something like that so it's hard to come up with a conservative uh bound that makes sense uh and then the last thing is uh the updates require knowledge of prior value

which in the example that i cited i just want to make a payments if i wanted to pay somebody uh why would i need to know their balance i just need to know that i have enough money to pay them while in earlier constructions you would have to know what the other person's uh balance is and only then pay them so these were the problems with prior constructions and so our work gets rid of single-handedly gets rid of all these problems right so you have efficient representation everything is small no blow up depending on the on the size of the map on all block depending upon the bit length all operations are efficient in the same way everything is is constant and if you remember from the previous slides it was like two or three at max

and then we can also handle updates that are oblivious to prior values if you want to compare against i know there are a lot of numbers here i will i won't expect you to like go through all of them but but particularly maybe of interest is merkle trees and and quack um really the difference is you can see in our work everything is a of constant size right so your proofs are of constant size the time to verify is only a constant number of operations the time to do uh changes to this underlying structure also is only a constant number of operations while in merkle trees everything is logarithmic now the immediate

like concern here is though you have size of h size of a hash on the merkle trees and you have size of group elements or field elements in quack yes of course uh i don't deny that hashes uh are much smaller much easier to compute um while rsa operations for instance are going to be group operations are going to be a little slower group elements are larger i don't deny that and on a first theoretical front it is interesting that we can go from logarithmic to constant but on a practical front which is probably more important for this audience we'll come to it i mean uh particularly

when you're moving to larger and larger situations the you're going to this difference is going to show up where being logarithmic versus constant does make a difference and really the killer uh application of these so-called public key primitives right versus hashes is that they have additional properties right so they have algebraic structure that gets you something else so for instance our quack commitments are going to be aggregable i can take any number of proofs and put them together and give you a single proof uh in merkle trees uh this is not going to be possible there you're at the mercy of how the data is organized in the

structure so you would have to think about um whether you know paths overlap and only then you can you can sort of uh combine uh proofs of course the other way is to go starks like we mentioned earlier but again uh things are getting mature on that front but you me it may not get get to be as good uh and finally uh there are other the algebraic structure that is offered by public key primitives uh while it might seem discouraging that they're slower uh it they could potentially become faster too and it is my strong belief that if you put the same effort behind public

key primitives that you put into say optimizing starks you would be able to get these things to run faster as well and only thing now is you get other properties for free and that's something to look into and definitely supporting things like rsa isn't a bad idea in any case right so there have been of course there have been eips that look into doing rsa signatures and so on supporting them to be more efficient and yeah that is something that's never going to be a bad idea in my opinion right so so that's uh basically how we compare with other works and and why we claim we get the state of art even accumulators and subject for commitments

so i'll i'll give a quick sketch of how i'll go through the rest of the talk is just mainly going through some aspects of the construction i won't go into too much technical detail but just to get a flavor of what the printed looks like so we start with what we call an insert only key value commitment and while we did this initially just for the ease of and modularity of describing our construction it seems that there are many applications that only care about you know inserting things and and never changing them so that's uh that's something to think about because sometimes this this construction might be more efficient than the main construction so like i promised i'm not going to go

into too much of the technical details but just to show you our insert on the key value commitment commitment to a key value map that has kivi key value pairs looks like this and although the expressions and the exponents are kind of scary uh they're just two group elements right so that's what i would like to tell you so you we're working groups of unknown order example rsa groups if you're interested in trustless versus a trusted setup you could work in class groups you also get better sizes and you wouldn't need a trusted setup um and yes zis are are primes right so so this is the standard rsa setup but yeah as i pointed out the

important thing is it's just two group elements and that's really what's important the commitment itself is two group elements and the way insertion works you can believe me uh and we can come back to this if someone's super interested uh but basically inserting a new key value pair completely takes you know one hash three exponentiations or three group operations and then one multiplication and that's it right so so this is a constant doesn't depend on how big the map currently is uh doesn't depend on how big you think it's going to be and doesn't depend on the bit lengths of these values or anything like that it's always the same one has three exponentiations one multiplication the proof is going to look also exactly

like a commitment in fact it's the commitment to every key value pair apart from the one you're trying to prove right so this is just some context this is this is usually the case in many of the constructions because and it gives you a few properties for free when you insert a value the old commitment is your new proof and then when you want to update your proof you just do insertions and as we saw insertion is super efficient right so proof updating is super efficient verification is also an insertion which again is going to be efficient so in one shot just by the fact that insertion is efficient and the structure of our commitment every operation we're thinking about is efficient

and that's basically the insert only construction uh security is based on rsa the rsa assumption i'm not going to go into why it's secure but but you can take my word for it that it is secure under the rsa assumption the increment only commitment is a commitment that lets you that assumes essentially that you know you have all keys with value zero and then you can increase the value at a corresponding particular key by something fixed let's say here one you could do arbitrary doesn't really matter but but uh for us it suffices to think about incrementing by just one um you can see it again we're working in the group of unknown order

now you only need one one group element right so it's even simpler uh and as we go on we will actually see that this entry mimics the second entry in the insert only uh but yeah for now it's a single group element incrementing is super easy it's basically just one exponentiation after computing a hash and the proof though becomes a little more complicated uh and this is why we need field elements basically you can think of it as the proof has two components that talk about uh the exact value so if i'm trying to prove that the value within

um this uh with a particular key is say five right so the way this thing is constructed you can in principle if i don't add additional pi 2 and pi 3 if i try to go the same way as i did for insert you can make false proofs that the value was 4 at one time three at one time two at one time and so on and if you don't want this to happen you have to provide a what's called a non-membership proof so i'm proving to you that there are five and i'm also in some sense proving to to you that there aren't six right so now you can't prove four because you can't prove four and not

five because there are five so that's basically why these two elements come in and they're basically going to be um something like field elements they're doing uh primarily uh like co-primality checking in the exponent uh that's a rough uh idea of what's going on there but but even though we've added these elements remember like field elements are going to be like fixed length like even if we're thinking about 128 bits that's that's like totally fine and the proof updates are still they need more than just one exponentiation but it's just you add one more multiplication and do some modular arithmetic over these field elements so

that's not that's not much at all verification is also similar in terms of its cost so that's the increment only key value commitment and why did we construct this increment only that will be clear in our final construction which is quack basically if you look at quack and if you stare at the exponent of the first component you can see that it's linear in the vi's and remember i want to support linear updates to vi right i want to be able to add delta to vi if i wanted to um and and you would think that oh well because it's essentially a linear function you can do this right so you you can just essentially

take the coefficient of vi in that linear expansion g to that thing and then raise that to delta and then if you multiply you're good you would actually update it except that the computing uh that term where the the exponent is essentially the coefficient of vi is going to be expensive because if you see those coefficients are big products of of z's right so now computation would start depending on n so that becomes a problem uh so in order to avoid this uh we're gonna take what seems like a really silly uh route uh like even a cop-out but but let's go with the float right so what we're saying

suppose when we want to do an update we essentially pretend that you know there wasn't a value to begin with and we just insert right so in some sense uh 5 is already stored at a particular key i want to change it i want to add 3 to it but i'm like i'm just going to pretend 5 isn't there because i don't know anything about it and i don't need to know anything about it i'm just going to say i'm going to insert three at the same spot and then see what happens and turns out this is actually a very good idea it changes the form of the of the commitment a little bit but but it does do the job if i insert oblivious to what was there before it does

update the value at the corresponding key so you can see that v1 changed to v1 plus delta even though i added an extra z1 and that's fine uh but the value changed correctly i'm still able to track i'm able to track the values corresponding to different keys very clearly and you can see that i can keep doing this i can uh do the insert as before and then i can keep continue inserting things as before if you insert at values that have already been inserted you're essentially doing updates and that's the semantic change but you don't need to you don't need to be worried about whether someone has inserted there before or not

you don't need to know what the value is you just go ahead and insert oblivious to what's happening and if there was a value it gets updated the other way to think about it is uh you can pretend that the values are the keys were zero and then as you do these updates you're changing the value corresponding to keys so this does as i said change the form of the commitment but in a very cute way so you can see the second component essentially starts tracking the number of updates so every time you do an insert you are effectively updating that location and the second component keeps track of how many updates you have made now you can see where uh

the increment only commitment is going to come in essentially every time you do an insert or an update what you're doing is you're increasing the number of updates by one right and the second component is a commitment to how many updates have been made in each of those spots right so our fulcrum this is essentially our full construction and uh it it continues having only two group elements and in terms of how would you prove things well we can do that again by abstracting this out and looking at it the first component is basically an insert only key value commitment and the second component is an increment on the key value commitment put them together you get quack which is a full blown

key value commitment it's it's it's so clean it's almost like everything got wrapped into a nice uh nice tiny present with a bow right um and so how would you prove things uh about this commitment well we already separated out saying there's an insert only key value commitment and an increment only key value commitment so you give proofs for both and then you're done so remember that we already knew how to prove things for insert only key value commitments as well as implement only key value commitments you kind of combine them together and that gives you the proof for quack how do you update these proofs well update the independent parts right and we already know how to do that and the part to recall is that each of

these were efficient in terms of representation and execution which means quack as a whole is also going to be completely efficient in terms of all the operations okay um so that's essentially the summary of the work we get a key value commitment quack that's efficient from the representation operations you don't need there's no bloat depending on the size of the map on the bit length of the values that are being used the whole construction is independent oblivious to the size of the map that is ever going to be committed and you can do perform updates to this map oblivious to the old values just a quick uh two-liner aggregation we can aggregate proofs and

and batch uh verify as for now only for the full construction if you've aggregated proofs once you can't further aggregate them what we call continued aggregation so if i have an aggregated proof can i aggregate something along with that that's hard this is a property you might you might actually desire because um uh you mean you can imagine maybe uh proofs being passed along from one minor to the next and so on and then people might wanna add on their proofs right so you want to take one proof and then people add their own proofs or transactions they have done and so on and this this is uh i think an important question

something that we are looking into it's a hard problem for sure but i will say that if you don't care about updates if you're looking at a essentially a static data structure where you can only keep inserting new values uh we can actually support unbounded aggregation you can do this thing where you know you aggregate some proofs together and then other people come in and add their proofs and aggregate produce another small proof and so on you keep doing it so this is something that we can do in our insert only construction it's just that the increment only construction because of this non-membership proof that i talked about has the problem that you can't aggregate aggregated proofs uh but it's something we are looking into potentially there's a solution that we can come up with uh so that's basically it so now the

question is you know i told you so much about quack claiming that it's going to do statelessness and the question is you know did it work does it actually give you what it wants uh let's let's let's actually uh figure out well we can't we didn't actually go and implement our solution but uh we did do what we call a back of the envelope calculation to see how quack would fare if you put it through put it to the test right so we're getting some numbers right so this is from i think somewhat recently a couple months ago we're looking at the number of transactions in a block trying to see essentially you know the block rate and things like that and so if you want to do high level back of the envelope

calculation if i assume something like 200 transactions per block and run the calculation our block proof size if you used quack instead of merkle hashes is going to be 400 kilobytes as opposed to the one megabyte right so you're saving quite a bit and i think this is what i told you right at the beginning is i promise you that as you get bigger and bigger the fact that you have logarithmic versus constant is going to matter and the fact that you have property is like um aggregating proofs that's really what's happening if you look at the proof uh uh size here that we've estimated of like 0.8 kilobytes that's because you

can actually combine proofs and and if you recall from merkle trees that wasn't possible right so even though uh these group elements are bigger you get you you gain quite a bit on the proof size so we can do 400 kilobytes as opposed to one megabyte and now if you're asking what about the 175 kilobytes well you can do that here too if you can think of statelessness or statefulness as a spectrum and again do the same calculation and you would win again because we're going to get the same benefits of not sending around all the proofs and just storing things right i will say though that particularly if you want to look at the

cost of operations in terms of time and uh and maybe uh thinking of other benefits that merkle trees do provide in terms of hashes being small and fast mercallizing uh this data structure in some way quack in some way would also be very beneficial and for instance in the like people are looking into vertical tries and things like that right now where you're combining in some way essentially vector commitments and merkle trees right so you could do the same instead of looking at vector commitments uh particularly if you think the key value commitments are more more suited to this data structure you could multiply ski value commitments right and come up with a core course right i don't know something like that um and and the thing to be noted is that

uh something like that is probably the way to go the reason is the mar the reason merkel trees win so much is not just because of their size and and their efficiency it's that by giving up on on the asymptotics right by giving up on wanting to do constant size proofs and say we're going to do logarithmic size proofs uh there's some amortization that that can happen in terms of updating many proofs at once for instance can i sit and can i look at all the merkle person update to them at once uh merkle trees kind of win there because because of uh the fact that the proofs are longer it means that updating all the proofs at once is actually a little easier while if i compress the state way way

down and the proof's way way down you kind of have to change all the proofs and this isn't something you can get out of so if you want to get all these properties together right the size and time benefits of merkle trees these uh updating multiple proofs at once amortization benefits of merkle trees uh the fact that you get many interesting properties like oblivious updates uh adding uh sorry aggregating proofs and things like that the properties that public uh key primitives offer you yeah i think the way to go would be to look at some sort of combination of these two primitives and that will be probably the best of all worlds that we

can think of so the moral of the story is you know hatches are great if you don't have way too many of them and today's vlog means we might have to jump ship right you might have change boat and go start including some public key crypto which is never going to be a bad idea and i guess bottom line is we won't know if we don't try so i think there are a lot of things in place to explore this option and so i think it's a good idea to try it uh again final thoughts statelessness is here now it's uh we have to think about solutions for this quack could be a way to do it uh at least a part of the puzzle that could help help with this all right so we construct

this uh uh key value commitment with everything being efficient that gives you the accumulators and sub vector commitments even right so it gives you the best of all all these primitives and that's all i had to say for today i'll stop and take any questions thanks everyone okay sure thank you yeah you too thank you

you