zkStudyClub: Vitalik & Dankrad on using polynomial commitments to replace state roots

Transcript

welcome to the ZK study club just so you know this is a bit of a hybrid setup in the previous one that we did with Elly it was kind of using the crowdcast interface this time we're doing a zoom call with crowdcast because we needed to do that for this format so feel free to ask questions add your comments in this comment box that's awesome and yeah I'm really excited to have a chance to do this specific study club and also share it with so many people if you hear if you have any issues or whatever just put those things in the image pad and I'm gonna actually be troubleshooting that as well

so I want to welcome vitalik and Dan crowd and Justin from the etherium foundation and here they're gonna be talking about polynomial commitments to replace state routes Vitalik do you want to take it away sure so I guess I'll start off with just a quick introduction to what polynomial commitments are just because they are this in a very powerful new technology that's gotten a lot of interest in hype especially over the last six months or so and polynomial commitments have been used in snarks they've been used very successfully along for example but they can also be used as a tool in a whole bunch of other protocols so basically a

polynomial commitment is a special kind of hash of a polynomial so it's say in a very compact way of representing this thing that contains a huge amount of information so polynomial if it has some very high degree you might have a huge number of coefficients and you kind of hash it and represented in one constant size thing where this hash has some extra properties and the main extra property that you have is this ability to make opening groups right so given the commitment to a polynomial and and the polynomial and given any value is dead that you wants to make an opening at the prover can provide an opening

proof that proves that that polynomial evaluated at that coordinate said actually give but whatever number a that it actually is right and so if the prover sends along this said commitments to P and then the groover sends along this opening q and so the verifier then the verifier can take the commitment and the opening in the verifier can verify that the polynomial evaluated at that position said if actually does equal to a so you can use polynomial commitments as an alternative to your Merkel tree so

given a bunch of data so given say n pieces of data you can create a degree of less than an polynomial that represents n pieces of data and the way that you do that is basically you just kind of encoded in the coordinates right so ki evaluated at zero would be the zeroth piece of data P evaluated at 1 would be the first piece of data P evaluated at 2 do the second piece of data and so forth right and using like Lagrange interpolation or whatever we actually can't just say like give me a polynomial that evaluates of these values at these points and then you can

just use openings instead of local branches right so basically you kind of hash together all of this data 0 to TN with into this polynomial commitments and then if he wants to reveal any one of those particular DS then you can just use an opening proof at that particular coordinate and um it basically does the same thing that a miracle tree does right so polynomial commitments gives you the same thing as miracle trees but what else can we do right why do we care about them and we'll see I'm in a couple of slides right so before we start just kind of quickly go through a couple of I

know we all commitment schemes so the two most developed ones the first arcade commitments which are based on elliptic curves in the second is fry which is based on hashes and so the way that keeps commitments was elliptic curves work is basically that you in make this trusted set up where you have some secret number s and you basically just provide a whole bunch of powers of s and have multiplied by the generator it earns you provide one power of s multiplied by G - so you provide the generator G then G times s G times s squared and so on and so forth and the way that you encode a polynomial is basically you just take the abri in cro

the encoding and or you take these individual coefficients and you would basically take the end of it the zero Degree coefficient multiplied by g take the one degree coefficient multiplied it by a G times s take the degree two coefficient multiple multiply it by the degree to coefficient called the polynomial and and so forth and the way that we prove that some polynomial actually evaluates the some value at some position so the way that you prove that P of Z equals a is basically you prove that P of X minus a has a 0 at said and the way that you prove that it has a 0 at said is you basically prove that the kind of minimal polynomial that

has a 0 at Z which is just X minus n is a factor and you prove it's a factor by providing the quotients and you prove the quotient is also a polynomial so you're providing the polynomial commitments to the quotient and you verify with pairings basically you just use pairings to kind of perform this multiplication right say basically checking that Q multiplied by X minus said actually does equal to P minus a and with a look to curve pairings you can do this pretty easily so that's Kate with Fri basically the idea is that what we do is you do this in a series of steps where you start with a degree n polynomial then you kind of decompose it into two degree and over two polynomials

where one is an just the even degree coefficients and the other it's just the odd degree coefficients so for the even degree coefficients basically you take in a P of X plus P of minus x over two and you can see that for any odd degree coefficients those two things just cancel out to 0 and then for the odds you do the opposite and you notice that evens of x and odds of X and divided by X are both degree and over two polynomial with an x squared and you can calculate them for evaluations appear and then we add a generator Rams of value we combine the to make a linear combination of them in the way that you had have proved equivalents is basically

you and commit to all of these polynomials by providing merkel roots of them and then you just do a whole bunch of random checks from the Merkel tree it's a prove that these and if each step is equivalence to the next step at most positions mid so the sin if as accurate as I can get in terms of describing Fri within half a slide but basically you just keep on and of proving this sort of equivalence between P of X which has degree N and then P prime of X which has degree n over two and you keep repeating until you get the degree one or some really low degree where you can check directly and if all of the checks passed and the thing you had originally is a polynomial and then the way you open it is you can just do the same thing that

you do in K commitments except instead of checking with pairings you would check by once again kind of opening at a bunch of random positions so that's enough quick introduction to polynomial commitments so now next up what are we doing this for right what's the point now so the etherium state tree this is the state that contains all of the accounts all of the contract code all of the storage key is all of that information something like 50 megabytes and it's growing there's somewhere around 300 million entries I think much more than 300 million and at this point and we can model the etherium state as

basically being a key value map right so you you can think of it as an mapping a field elements though mapping number mod P it to and other field elements another number mod P in a single block after the East one point exchanges that are intended to and have cut down witness eyes will be able to access at most maybe two thousand to four thousand keys currently it can access about fifty thousand well so basically what we're doing here is if we can think of the etherium state as this key value map ends in any block that accesses a bunch of these keys we just want to provide

proofs that show that the that the value is that those keys actually are correct it ends so far we've done this with morkul trees so this is the state tree but what we wants to do is we wants to get rid of all of the really long merkel branches and so we want to try to do this with polynomial commitments so basically here's what we're trying to shoot for right so what we want to have is a witness so kind of a proof that would become part of each block that contains all of the keys and all of the values that get read as so we're not gonna try to make a kind of oh of one

size proof of the validity for the entire block or anything like that yet we're just making a proof that the witness is correct so we would still kind of publish in the queer what all of these are so what all the address is what all of the contract storage keys are and we would also publish what all of the values are so the things that are actually at those positions in the state and instead of being something like a thousand bytes per access this goes down to basically being 64 bytes which is just 32 bytes for the key 32 bytes for the value ends chances are with simple compression you can push it down to maybe even something like 6 to 15 bytes

right basically the reason for that is that half of things in storage that you would access are gonna be like slots that are right beside each other so you have K cables one cable sqk three you can compress that trivially in the values themselves a lot of the time might be 32-bit integers they might be counters it might be even bits true or false they might even values you can fit into 64 bits so basically we could go down from something like a thousand bytes per tiem that have to be published to maybe it on average your 10 bytes per to you that would actually have to be published so the way that we can think about this is that in every block we have this kind of read witness that beat

which is an actual witness said it's in codes and if what keys and what values have been read and we can provide some polynomial commitment proof that they're correct and you have a right witness which is basically so when you execute the block it generates a record of what things are supposed to be updated and what are the new values that it's supposed to be updated to and so our goal here is basically to encode the state using polynomial commitments instead of Merkle trees and what we want to do is we want to do two things right the first thing we want to do is we wants to be able to efficiently improve

many reads so unlike in the case with the Merkle tree is where if you wants to prove a whole bunch of values you have to provide a separate merkel branch for each one in the case of following a little commitments actually here what we can do is if you have a whole bunch of things that you're reading we can provide just a single proof just single commitments of fixed size that proves that a whole bunch of keys and a whole bunch of corresponding values are part of the state and we'll get into how to do this very soon and the second goal is to prove what I call a map a map merging arguments which is basically updating

the state right so given a state s and some set of rights W or that you want to make basically you provide as Prime which is a commitments to the new state and you prove that s prime actually is s and of da old stayed updated with W you're right mate and the keys are just gonna be the Union so if IKEA was in the old stated set a new state effect II was in the rights it's also in the new state and the value is basically if IKEA is in the rights then the news the new state would have a record with that key that's equal to the thing that you wrote and if it's not in the rights then you just pop

you over the old state so we want as we wants to have some kind of very compact proof that proves to you that the new state actually is the correct updating of the old state it ends just kind of reminding you for context the thing that the verifier has so the thing that clients have is generally going to be for the stage just the commitment so a polynomial commitment to the state and s prime is also going to be a polynomial Commandments W is not going to be part of the data at all because it's just generated by the block and the keys and values that get read are just available as a whole list and so that's kind of the information that we're working with

so first ingredients right this is starting to get into a serious math so this is a multi opening proof so suppose you have a polynomial and he wants to prove a whole bunch of evaluations at the same time right so you want to prove that P of Z I equals AI for a whole bunch of zenzen for a whole bunch of A's you can do this with only one commitment right so here's what we do so first of all we can generate the polynomial that will call the interpolant and oh I see a question why today the key is a thousand bytes I think the question it's not the

key let's a thousand so it's the merkel branch for the keel it's a thousand bytes right so the state has something like a few hundred million elements and so it's gonna be a tree that has depth something like 25 and so you just need a whole bunch of hashes going all the way down to the element like literally today today it's actually even worse that's what four thousand bytes because we're using a very suboptimal tree structure but even if we use the best possible binary tree it only goes down to one thousand minus-- so back to multi openings so we uh we generate so you don't need to actually ever kind of encode this kind of the prove ER and the verifier can both generate this polynomial called the interpolant which is just the minimal polynomial that has the property that i

of z i equals AI for every set iron for every AI so instead of the lowest degree polynomial that passes through all of these coordinates right so if you wanted to prove that p of 5 equals 42 when you have ten equals 100 then i of X would be the polynomial that passes through 42 at 5 and passes through 100 at 10 which would be basically minus 16 plus 11 point 6 X I think right so if it's two points that's a line and if it's three points it's a parabola and so forth you can generate this period you so I'm then

Z of X is and of the 0 polynomial so it's the simplest polynomial that evaluates to 0 at all the X's that your or all of the Zed eyes that you care about so if we're doing five and 10 then it would be X minus 5 times X minus 10 and then our strategy is going to be that we prove P of Z I equals AI for all eyes by proving that P minus I of Z I for every set I equal zero so you should be able to see right that it because if P of us ni equals AI then by construction I have said I equals AI because that's how we created AI and so ki - I have said I is going to be a

minus AI which is 0 right and so now we've reduced the problem to a simpler problem which is proving that P minus AI is a multiple of Z so it's a multiple of like X minus 5 times X minus 10 or whatever things we want to and we do this by basically just providing the quotient right so we just provide here P minus I divided by said and this cue thing is the only thing that actually has to be provided by the prover and then oh and then after he commits to cue then you basically randomly select the points and if you randomly select the points in a large field then with very high probability P minus I divided by Z at that point is only going to equal to if those whole

polynomial is actually satisfy that equation so that that's basically how you just do a multi opening right so that's how you make a whole bunch of reads and so now the question is well how are we going to compute it if how we're going to king how are we going to actually use this to make a bunch of key and value reads right so basically I get a question I think the statement is only true if the degree of P equals

the degree of Z equals the degree of I sorry when I say multiple I don't mean constant multiple I mean that he could be said or P minus I is going to be said multiplied by some other polynomial so the degree if he is gonna be way higher than the degree of said normally so what we do in the state is basically we just encode kind of the keys and then we encode the values and we just in the clear we're just gonna be really lazy we'll just add and if in the clear as part of the witness a couple of bytes to refer to the basically what is the

actual index in SK and what is the actual index in s via that some particular idea is going to be add and then to really basically just make a whole bunch make a multi opening and you prove a whole bunch of keys and you prove a whole bunch of values at the same time if he wants to prove no one membership if he wants to prove that something is not in the state then one simple approach is we keep the keys in sorted order and so you just provide two adjacent ones and you can kind of prove that the keys are sorted or another approach so show later is that you just have kind of a special and if non-membership proof that just walks over all of these years and shows that

none of them are part of the thing that you want them or none of the keys in the state are the thing that you're looking for so that's reading but for writing we need something even more complicated which is this map merging argument right so to get to the map merging argument and I'll introduce another ingredient and muscles this is part of Polanco this is and if not you it's been known for a while and the goal here is basically that if he wants to prove that kind of treating polynomial evaluations within a range so within a range like a to B or some range C to D as multi-sets I want to prove that the

multiset of the evaluations of P of X and summary and Jada BIA and the multi set of evaluations of Q of X and some range data D which could just also be A to B R is the same except it's possibly in a different order right so treating point on the polynomial is evaluated over some range assets or as monkey steps we just want to prove the equivalence of them even if those polynomials might be different so here's basically the strategy right so what we're going to do is we are going to choose some random R and that are we can just do a Fiat Emir and grab it from the

hash of each of the commitments to P and they came into the queue and then will generate and accumulator polynomial which satisfy in this condition oh it just looks like I made a slight mistake here it actually should be basically AK of X plus 1 equals AK of x times R plus P of X so not 1 plus R times P that should be it R plus P of X and it needs to satisfy this condition in the range A to B and the way that we do this is we basically prove that a curve X plus 1 minus AK of x times R plus G of x equals 0 across the entire range in the way that we prove that that

expression is 0 across the entire range as well we just and if he was the thing that we did before right or and it turns out that if you evaluate it across certain specific ranges then it's actually very easy because the 0 polynomial at for certain kinds of ranges has a very compact expression right especially if you use like roots immunity or something so you prove that this expression acti of X plus 1 minus AK P times R plus P of X is a multiple of the simplest polynomial that 0 across the range and then the accumulator evaluated at B divided by the accumulator evaluated at

a is this kind of random product of the randomizations of all of these values and I call this this accumulator of all the values between a and B it and then you do the same thing for Q and you check equality so the thing that we're doing here is we're basically kind of running a product that we're kind of stringing through all of the evaluations if P between a and B and then all of the evaluations of - between C and D and we're checking that this product is the same and to avoid kind of carefully choosing values and multiply to the same thing we're kind of shifting all the values but randomly before we do the product and so that way you can treat so this gives us and if you multi set

equivalence and so here is the map merging argument right so this is actually simpler than what I just arrived in the research post there and if considerably so the way that you get simplicity is just through a bit more laziness so for every right we're gonna do two things right so first of all we're gonna include every right into the read so everything that gets written I gets read and so that way for everything that's written we know whether it's part of s or whether it's not part of us and so then we just well we don't even need to supply the one bit we already have the information and if for every right isn't a right to a t and s so are we and of modifying something that's already in

place or are we adding something completely new to the state and so what we'll do is we'll basically and if separate the right witness and the two sets so we have n K N and V which is under the new the new rights and then we have you can'tyou V which are updates so you write some union of creating you new entries in the state and we include those in the reads we verify them and we don't need a special proof to verify them the verifier of the block can just do that client-side and then we'll also kind of on the verifier side we generate this polynomial and if V which is

basically a list that contains the Oh old values at all positions that get updated right so if you have some update that corresponds to some key in the state then Oh at the at the same position as the update is going to be reveal the old value and so what the goal look that we're gonna do is we're gonna basically prove that as multisets so we don't care about order yet that s prime equals to s and then subtract out the old keys and the old values and then we add in the updates and the updated values and then we update or we add in

the new keys and the new values now you can do this with a multi set equivalence arguments but you need two new tricks right so the one one new trick is basically that we're not doing kind of equivalence between the two ranges we're doing equivalence between a range and a collection of ranges some of which we're adding and some were subtracting and that's actually fairly easy right because basically all you do then is you just I know do this map this accumulator polynomial for each one of them individually and then you and have multiplied together all the results on the right side well you divide out the old ones that you're removing and then you can clearly just see that well basically if well the left is good the

lot thing is gonna contain the same elements as the right thing and the second thing that we do is we just generate a linear combination so that we can do these arguments of and a through and of SK and SV or through the keys the values as combinations and so and so we can kind of force the permutations to be the same so that's the map merging argument if people have questions didn't feel free to and if continue asking an obeah happy to answer i'll probably just kind of stick a stick to this slide for a few seconds and pause also italic do you want to check the chat in zoom itself

because i saw there was a little bit going on there yeah hold on oh okay yes I so know Justin is answering from Georgio's poor Ellen Tabasco used a random ploy why not use their pairing through your highness another important thing there is that just I mean you could theoretically I solve this problem if you just add more powers of G to the Trece setup but the way that the trust the existing trust set up for plonk is done you only have one power of G tool and so unfortunately we can only use pairings to check and one power directly yeah yeah I guess that's kind of a lame reason because you can just make a new trust setup but if he wants to work with what exists then you don't want to be

checking kind of more than degree one multiplications and using the elliptic curve pairings directly mr. reminder to everybody there isn't this question those who are watching on crowdcast there's an ask a question box if you wanted to add something in there for later or just add those questions in this side because I think the talaq you're keeping an eye on a day I can see that yeah okay so I'll probably start talking about the sorting argument then so basically for the sorting argument we'll hear what we're doing it so basically if you wants to prove that some set of keys is in sorted order and the reason why we

want to prove that the set of keys is in sorted order is so that if he wants to prove non-membership then you can do that by just kind of providing the two adjacent key isn't showing that it's in that it's in the middle kind of in the queer and the Storting argument says based on kind of aspects knew a batched range roof but basically the idea is that to prove that the list is sorted we're gonna construct a new polynomial and if DF of X and we're we're deaf of X equals G of X plus 1 minus G of X so it's kind of

differences between adjacent evaluations oh by the way in case any pedantic people are listening to this in this presentation I generally kind of talk about ranges as being kind of plus one minus one and kind of range is going from A to B or 0 to K and in any actual implementation you're gonna be using group kind of powers of roots of unity and so to go to the next one you would multiply but just for kind of simplicity of exposition I'm pretending we don't do that we just add so you know so diffic the reason why we do the minus one is because we are we don't just wants to prove sorted order we wants to also

prove non-duplication I mean technically we don't have to do this but and it's just it's a totally free and extra check that we will that we can do and so this the way that doing D f of X minus one proves non-duplication is because if the difference is zero then the difference of X minus one is going to be negative one and then you're not going to be able to make a range group for minus 1 so we get uniqueness 2 so for any two adjacent values you get different X minus 1 which is just this polynomial containing differences and then what we're gonna do is we're gonna express those differences in base to the 16 in this illustration I have base 10 to help people understand but in reality like you probably want

base 2 to the 16 so 53 is 5 because like 5 3 with 10 1 0 12 1 to 10 or 1 0 1 7 0 7 and then what we do is we have this other polynomial P of X and with a of X what we do is we're gonna use another a multiset equivalence arguments to basically show that a of X and it combines together all the values from e1 of X and all the values from t2 of X I'm and all the values from any higher digits if we do base through the 16 for 2 to the 256 size numbers then we're gonna have 16 1 all the way up to be 16 and then you just have I of X from 0

from 0 to 9 this is just the identity and that just makes sure every value is in there at least once and then what we're gonna do is we're gonna just prove that in a of X every time you step up by one you're either increasing by one or you're keeping in the same and so that's just an if Y of X plus 1 minus e of X is always within 0 1 so that polynomial we just proved that like that thing - 1 - that thing equals 0 across the range which we know how to do and then you show that you are you doing opening to show that it's 0 at the beginning and then it's the base minus 1 at the end and so you sure that all of the values are kind of sandwiched

between the two and so now we can prove that these numbers are sorted with maybe something like a few dozen constraints per number because you still have to express it in a medium-sized base or maybe yes sorry to interrupt you there I didn't realize you were about to make a really good point I really sorry about that I'm just actually I think is your phone vibrating um I don't think so and I'm holding my hands just to make sure that people can hear it better if anyone's not muted um and you you know well you still let you sound great okay well I interrupt you there keep going

yeah cool so that's the sorting arguments ok well thanks for the pause now if people have sorting argument questions you can ask them so alternative to the story of the arguments basically we can get rid of a sorting complexity by just making a plain old proof of a kind of multi non-membership and basically we prove that some polynomial does not evaluate to any of a whole bunch of numbers for X that's within some particular range and the way that we do this is basically we just have an accumulator that kind of walks across the entire range it starts at 1 and it satisfies this expression that the accumulator are at X plus 1

equals the eighteen-wheeler add x times X minus k1 times X minus k2 Ababwa times X minus K n so basically if at any point X s any one of those values the accumulator goes to zero a minute stuck at zero and basically we just verify at the end of the accumulator is not zero now this does kind of bring up a feasibility question because like n is potentially gonna go up to a few thousand and so you might ask well is the accumulator gonna be crazy degree and fortunately the answer is No basically because like the act this actual check right so the accumulator might have a degree of like we'll say a hundred million and then the check

itself so we have a degree 100 million equals degree a hundred million at times a polynomial which is just the degree of a Q thousand and the verifier can generate that coincide and the V R and so it's like it's not it's like you're not going to get a kind of like a hundred million multiplied by a thousand blow up is basically what a basically what I'm saying now I'm sure that other people clever than myself can come up with even better alternatives to the Storting argument so it's kind of a bit of an open problem to just come up with the nicest and cleanest to line thing to prove that a polynomial does not contain a whole bunch of values anywhere within

some range and the reason we want to use this alternate or sorting argument is basically that if we don't care about about sorting then like the number of constraints goes down by a lot right because distorting arguments is gonna be a few dozen constraints per value but maybe we can push it down to something like maybe five or ten constraints per value basically by you know instead just explicitly providing a non-membership proof for any value that you read that you discover is not part of this date so here yaimai kind of big parts over and we can switch the tank read doing the

teaching sure yes do we want to have any questions at the moment before I take over here by the way if you wants the meter advance the slide just shout okay all right I'm in actual in the zoom cost welcome to just jump in here - all right so I'm going to just go over a quick sort of like alternative construction - to what Vitalik has just shown i guess mainly this is to show that we can like I mean the the

polynomial commitments sort of construction is very very powerful in itself and we don't we don't have to construct lots of mesh machinery around it to even use it right now and make it much more complex and so the idea here is like we used the polynomial commitment once again to store basically a function and on the range 0 to n minus 1 and then what we're going to do is that that each in at each point the polynomial will actually contain as its

value the roots of a try so like try is this this fairly simple structure where you can stores like it's it's a tree but but basically the the access of any key is by by the digits and that key so basically if your key starts with 0 0 1 that means in in the try you will go left left right basically 0 4 left and 1/4 right until you you hit a leaf and where your value is stored or not then it is not in the try and which is basically how usually like state a store

today but by using a boolean commitments and we can basically cut cut out the first yeah many layers from this try like for example if we have two to the 28 positions but just like possible with current trusted setups then we can cut out the first 28 layers from the try and as an acceptor we would probably want to add that if any of these tries are empty then we just saw the value 0 so that makes it much simpler and be like yeah I have have to do much less copy computations when lots of these are empty which is the expected state most of the time and so like when when only

one value is stored in a try then then actually we get like the full power of the polynomial commitment in the sense that we will not need any additional information to to reveal the value at one point as in like it's it's all already store contained in data itself which is the key and value which we always have to provide and unless we want we are going to do a full snack over the actual state transition we always need this data to to verify it so this construction only has one sort of weakness in a way debatable how is how strong that weakness actually is because

so basically what what can happen is that and if I know that you have some contract or account that wants to access a certain key then I could do the sort of dos attack on you by inserting lots of keys into into the same try and pushing you're pushing your key further and further down that try so that and suddenly you your witness would become much yeah much bigger now this actually already exists in current in current structures it's only kind of this makes it much more apparent because usually the witness is almost nothing basically

there's only this one group element for the whole of the data and and suddenly for for these keys it would become much larger so that's kind of I mean I guess you could say it's kind of annoying because yeah you view the the overhead over the sort of other accounts becomes much much larger metallic would you change to the next slide Thanks so we can actually also do something against that which is yeah kind of nice so the the idea would be that instead of having one try where you

can insert your key value pair we compute a number of tries so here I basically give the example for three different tries so basically you compute the hash of the key and one modulo n and two the same two with two and three and so you get three possible values like points of the polynomial where you could insert your key and we create the additional rule that you have to insert it into the currently smallest try and so what would happen is basically that now if you wanted to so basically now if

I have if you can predict that I want to insert a new key somewhere and you could perform an attack on that but but if you wanted to fill up my space you would have to fill up exactly those three points in the polynomial which becomes quite hard because you basically have to find something that hashes exactly to these yeah where where these threes are these three are the same you you could you you can do a bit little bit better by saying you want to you want to and attack more tries at the same time but very quickly it becomes very very

expensive because you would actually have to insert so many keys yeah so exactly a sort of very very simple and a construction that's based on the current on the current set up already and basically mainly you would say it cuts out sort of like a large number of layers from the current local tree based structures Integra do you happen to have numbers on how much it would take how much computational power or take to break the scheme if you put and it's

very small maximums only a number of T is imma try so like if you say I try can have maximum size three or something is I have an instinct that in my it might go exponentially high you know but three would be tiny why would you limit it to three right even even a thousand is fine right I mean that's still only like ten so I guess I'm just trying to like avoid having Burkle branches yeah yes but you but I think like I mean this only would would only happen in attack scenario right so like without an attack you expect these to be extremely empty in the normal case yes yeah and the other

reason why I think it would be nice to have it be really small is that if instead we instead of doing a try you can just kind of use sequential positions to represent values then it might be possible to still kind of keep everything within polynomial commitment lands and then make and I single proof for everything so you can't do that so you could you could do it like in hashmaps there's this alternative approach where instead of storing like lists at every position you know you hash again or you hash the key comma like something like here and you jump

until you find an empty space but the problem is that this performs very poorly once the once the hashmap becomes a bit fuller red like this kind of scheme this has terrible performance when the hashmaps becomes much more than 50% food I think so yeah I guess it depends on the kind of health all you envision the hashmap being like 50% is it 5% something else yeah I guess an interesting extension would be can like how easy is it to split the hashmap we could we could think about that like if you if you could easily go from one

to two polynomial once the first one becomes more than 50% full then maybe that that would be an interesting approach but I haven't thought if there's like an easy proof you can do to go from 1 to 2 polynomials yep do you want to go on putalik yeah so I guess actually I guess first off another thing that might be good to mention before we go to the next section is that Alastair yesterday came up with yet another scheme for representing

polynomials assets I mean ouster do you happen to be in the column listening right now I'm here yes and you want to talk for a bit about what you did so the basic idea was user pointing equipment is a set commitment by using a polynomial whose roots a hashes of elements of the set now this this sort of allows you to do some things that you couldn't do as hey RSA accumulators for sets things like proving an easy proof that the that the intersection of two sets if something is just by finally breaks comment division and we can sort

of prove that and you can do the Union and some things like common L on proofs for many sets or proving bits assess if a multiset has no duplicate elements that's sort of which you can do by proving the greatest common divisor between something and this derivative is zero is one and I'm not entirely sure that I have a a a a plan for how to do the state it's things like state using this but it's

good to be useful for some things you it seems like you should be able to just do the kind of the same map merging formula that I did right like the SKS vs prime equals s minus sin u uo question u plus n you know you know I can think about this more by the way would you mind just two leaving a link to your notes thing when our or whenever it's ready to publish somewhere and I'm sure lots of people would like yes of course and still need to editing but I was wrong yeah bigger picture so basically all of these are a polynomial commitment

ways to restore the state and you read from the state prove that the state was updated with some set of values and if you work do you work with the stage but they have a major weakness which is that both reading two and writing from the state and even a small number of reads and writes and making proofs require work on the order of the whole state size right so if you have a state with 300 million accounts and you wants to read just a hundred of those accounts well too bad for you you're still going to have to do and a 300 million items of work this is not true in a marquetry in

a more country you would only have to do a hundred times log 300 million actually a hundred times log of 300 million over 100 or so log log of 3 million so and if with Merkle tree is you only do a bit of work to make proofs for reading or writing a bit of the state but here what we're doing is well what's polynomial commitments you just you do need a kind of a huge amount of work make even small or even small updates can we avoid this so if we want to focus a bit on writes this was the cash structure that I

proposed in the youth research post so basically the idea here is that you have multiple layers of caching so see you have c1 and then c2 and then a switch is the full state and if we use my scheme and then for each of these caches you would have a polynomial for the key is an ax polynomial for the values so we'd have c1 k c1 VA c2 k CQ v s KS v and if we used an craite scheme or some others in then it could be different and but the idea is you have these multiple caches and it's kind of the ways you discover the real state is that the lower levels of caches take precedence

and you kind of walk through the caches until you find something that contains the key you're looking for right so if I want to access key 42 then I would first have to read a c1 and if it isn't c1 that I'm done and I get the value of 42 and C 1 and if 42 is not in c1 when I would read c2 and 42 is not in c1 or it's not in c2 than what we read 42 of s and if it's in none of you is that so if it's not in c1 c2 or s then I would just return 0 so then c1 get would be a medium-sized thing so instead of being 300 million accounts it might be say 1

million or even a hundred thousand accounts and c1 gets updated every block then every day what we're gonna do is we're gonna take C one we're gonna kind of move it up to c2 and then we start the c1 so make the c10 again and then what you now do is you have an entire day during which some node can make a much more bigger calculation where it basically takes e to and it introduces that into any kind of update s right so s is really big it's gonna be 50 gigabytes hundreds of millions of entries but fortunately you have an entire 24 hours to perform this

computation and so it's not that risky at all right so basically that that's how you do how you do right so you basically just have this and a series of caches and then you have smaller ones that get updated frequently and bigger ones that get updated less frequently and you'll let those proofs for updating the bigger ones just get constructed in the background and so this is one approach there are also an of other approaches potentially now we can also talk about reads now reads in this case are kind of ironically enough harder than writes the reason is that unlike writes where you

can just say that and if c1 is smaller but you read you write to it every block and then s is bigger but you only write to it every day reads from every level meet and proof some reads from every level needs to be made in every block right and so you need all layers to be efficient right if I access some piece of data and that piece of data is not in c1 or c2 it's in s then well I still have to come up with a witness for it and those witnesses still need to be aggregated even though s is like 50 gigabytes now there are solutions for this and there's different approaches for cade commitments and for fry as so in the case of Cape commitments we

basically use what justin calls the Chinese remainder theorem technique basically you can show that there is always a way to take a fixed linear combination of a set of the the individual witnesses for particular points so if he wants to prove four at five and ten then you would take the witness for five in the witness for ten make a linear combination for them and that generates it turns out a valid witness for five and ten based on the linear combination formula and then justin also has a somewhat different format for and they're storing values and making proofs and then i'm Shh I

don't know Justin if he wants they're gonna up and and pop in to talk about it briefly or make a link or both yeah I mean I'm happy to add a link I think thank had made a partial right out of the idea well I think the idea here is well even for this this Chinese marina thing is like to make use of pre-computation so you know generally when you want to build these proofs you need to do order and work but you don't want so it's kind of the way out here is that you do the you know order and work upfront and then you you know you have to store all these opening proofs which

you know does come with overhead potentially a gigabytes of overhead but then when you're asked to build these proofs you you know the the runtime is more like oh okay YK is the number of elements that you want to build the proof for and you know if you're working with you know with a nice basis like the like Ross bassist and the math kind of turns out to be two workouts nice thing you know so basically right you just pre generate the individual witnesses for

every way that you might want to access them and if you want to make a single witness for any subset of points then you just use this algorithm to combine the individual witnesses for every element and that's upset into a single one so and then so that's for kid great weekend Kade commitments because they are all up to curve points they have this nice mathematical property that you can just like add and subtract them and multiply them by constants and make a linear combinations Frey is based on hashes and so in fraud you do not have this luxury but in Frey we can do another thing which is basically instead of doing a one-dimensional Frey to store the state we can do a two-dimensional fry or possibly an even bigger fry and if you

do that then instead of having to read all of us to generate the proof you will only have to something on the order of the square root of s or the cube root of s and have multiplied by the number of things you're accessing so it's still a number of reads that's fairly manageable so in both cases there is a solution so I'd say challenges are basically that developing these schemes is all fairly new and we're still hungry for the possibility of even better ones so are there better map merging arguments are there better ways to represent the state can we make reeds cheap including making

leads from big states cheap in potentially even just in a way that's not dependent on the specific Ono meal commitments because that would just make life a lot easier for us um can we make right-side cheap in a way that's not dependent on polynomial I can have in details can we make rights cheap in a way that doesn't require this kind of cash structure so basically just are there ways of representing the state and of representing proofs from the state that have kind of better property is especially in terms of prove our efficiency than what we see so far cool yeah yeah no that's a that's the

end of the presentation part so I guess questions happy it's a talk you can talk about things I'm sure Justin in Bank read and others will talk about things do I have a question could you go back to the writing slide you had a slide about efficient right so this reminds me of this generic technique for taking any static data structure that is sort of you have a order n time algorithm to create a static data structure like the vector commitment from polynomials and turning it into a dynamic data structure that supports updates efficiently which is what you're trying to do here if I'm

understanding correctly right yes so in that technique roughly speaking you keep around the log n different data structures and you get you can turn you know order n worst-case appends into order log in worst case appends it's called my Overmars technique I can give you guys some references have you looked at that at all so is I don't we've never never heard of that by name I mean is it the same thing it's just doing this but having like a higher number of caching layers does it do something different it's making so so I I think that's

really about it it's more or less equivalent to this except with log and layers of caching I believe I don't fully understand the technique myself but it's just when I saw this it reminded me of it that's very good to know yeah yeah I can I can send you some references wouldn't that make reads quite expensive well even this makes reads a bit expensive use aggregation right so you would also use aggregation there I suppose yeah and in this case like what for reads you deaf you do need kind of walked through three different things

instead of one different thing and if instead of to be here's some some higher constant than you the the size over the thing that the block directly writes do become smaller but on the other hand the and he overhead of the whole scheme goes up so it's an integrator I'm sure there's an optimum I wonder are there any other questions or comments I know it might take a while for the audience to actually get that message but there's anyone else here and then you mentioned in the zoom chat by linear accumulators I never heard of those can you expand on

that yes so this is a line of work started in 2005 by n Guin it's called by linear accumulators and it's representing this set as a polynomial with roots at that set elements so I actually there's a few papers that extend that this work including intersection subsets the straightness proofs I can give you guys some references it's really just polynomial commitments except the polynomial being committed to is as described by Alistair it has roots at all of the set of limits okay very cool yeah it's interesting how

you get totally different properties if you go there's roots or in colors evaluations or encode those coefficients I mean one of the things that I've mentioned is that the like there is this this other you know polynomial commitment the dark ones which is you know quite nice and it has these nice that that we that is useful in the country cases but the one thing that it's it's a downside that I only realized recently is that it's it's not it's not friendly to the to the evaluation like including coefficients as evaluations basically it's not what I

call like wrong friendly or like launch basis friendly it's mostly kind of friendly to the standard coefficients in the monomial basis so that's why I'm have lately it mean more bullish on cat a the thing that the technicals Kate because it has both and anise which is [Music] cool well I don't if there's anything else that we could

talk about if we want to I just shared a couple links in the chat that were shared in here I think I'll definitely go through any other chats happening and try to compile what I can I just wonder is there anything else that we should talk about or should we wrap up I think we've been over an hour I mean go ahead sorry one thing I wanted to bring up that might be the thing that you wanted to bring up I don't know is that there is also this possibility of kind of just taking this brute-force approach in doing polynomial or end doing uh snark over hashes instead of

using polynomial commandments directly which on the one hand has much higher approver time but on the other hand doesn't or has nice broad look doesn't have any of these kind of reading and write and writing in efficiency issues huh do you think that the trade-off on using cat purrs on the need for an for multi-part computation to instantiate cat a justifying the gains compared to say doing Frank and also the linear security assumption of fascism try versus painting chicks I

don't know I feel like the the whole trusted set up thing is always enough more matter of personal ideology than math and it always it has been since the beginning so it is an updatable trusted set up so yeah that is true and one thing I will say is that kind of one of the reasons why I had that line in the slide about wanting mechanisms that are not polynomial commitment dependence is that if we do something that uses cater cat a or will however want to pronounce it then we wants to be able to upgrade to

something based on Fri or whatever else when quantum computers come along you know and so having a scheme that is and have in principle of just changeable to the other mode without changing too many other things would make our lives easier you so what kind of a scale can you get for generating these trusted set of parameters you said you could go up to a hundred million oh so this is this is a very good question so so far the largest trust that setups that we've successfully done

have gone up to either 100 million or a 300 million and I think if we once to have like really many participants and I think going far above a hundred million is likely a bad idea what number of participants did you have in the 100 and 300 million case so in the 100 case it was something like 200 participants in the three million case well I think it's still ongoing I was participant number 24 about a week ago but like for example in the hundred million case um and without G two powers one thing that I was able to do as me can alternate implementation

in Python using IECC and then participate with that but I did the calculations and for the bigger one that would have been impractical and so I just went with the implementation they already had so that was a bit of a kind of weight loss loss of security from going up there but like one piece of good news though is that if we wants to have states that are much larger than the the number of powers that we can handle then there are it's not particularly difficult to just split the state between like a hundred different polynomials and then you can still have one roof that kind of walks over all of the different polynomials together and I

talked about one construction for doing that in the e3 search post so there's definitely ways to get around B yeah a 100 a 100 million or 300 300 million a limit if it wants to have bigger states do you have a place where we can innovate is how we do the ceremonies themselves so this ceremony with a hundred million I think took like 30 days one month and so you know if you want to get to the ends of the plans as opposed to the hundreds one one technique is to basically avoid having the possibility sequentially one by one so instead you can have kind of a

pipeline where multiple participants are are building the the powers of tau together and like my a rough intuition and slash back-of-the-envelope is that you can you can get a 10x improvement there either in terms of the number of participants or maybe slightly smaller extent the size of the of the powers of tau so the idea here is like you you basically have multiple possible spots at the same time you know there's gonna

be some dependencies there whereby if one of the consequence goes offline or misbehaves then you're gonna have to trash some work but that's okay because you can always just restart but I think we might be able to even not do the trashing right so what if you have a scheme where every participant provides their powers of ass I know based based on the previous participants values but then also based on the original just basically just the G times hours have asked by by itself and then if some participants participates but provides

some of their powers and goes offline then you can kind of divide them back out I'm not sure if this works you have to do the math but it might be possible to do something like that actually possibly no because then that would be a yeah right you can subtract elliptic curve points but you can't divide them and one thing I'm curious about is as I understand and then you've actually worked on this a PhD thesis and there's some exciting work when you published recently in blog

posts sure do you want to talk about that well we have a new vector commitment scheme where you know you have Q s th public parameters you can commit to a vector of upper bounds by SKU and you can compute all proofs for this vector in time and log n well Q log Q I guess where Q is the size of the vector we use roots of unity and the high-level idea is we evaluate the polynomial that represents the vector using a multi-point evaluation and we commit to this multi-point evaluation

which has the form of a tree now our truths are logarithmic size rather than constant size but they're pretty fast to compute but I think you know it's it it seems like the new result by a bank rather than Dmitri will likely outperform ours so i implement that their technique it seems to be slower in terms of proof computation time but the proofs are smaller but i'm hopeful that that their technique can be sped up and my implementation is just you know a first attempt at it so so far their their technique is seems to be up to four times slower in my implementation this is on B and 2/5 for

curves [Music] yeah that because because the Fourier transform is twice as big for the Triplett's matrix multiplication it's not just that it's also because the Fourier transform is on group elements and as far as I can tell I don't know how to leverage multi exponentiation x' when implementing that Fourier transform so all explanations that you do our single exponentiation whereas in our technique when we committed that tree we can leverage multi axis yes I agree I think I think you cannot use mod X for this one yeah yeah me neither me neither but who knows

so I think we're gonna wrap this up now I want to say thank you so much to everybody for presenting Thank You Vitalik Thank You Jan Craig Thank You Justin Thank You Ellie for weighing in Alister Giorgio it was really great to have you on this call and thank you to everybody who was listening from crowdcast and sharing ideas I've started to put a couple of the links that were talked about in here and I'll try to add a few more if you do have any questions I think you can actually still write in this chat even after we finish so that's kind of cool can come back to this as a

resource in general this is the study club it's usually about an hour we usually talk about you know a paper or an idea and then and then dig into it like this and in a bit more of a back-and-forth casual way not pure presentation I do want to give just some some shoutouts to some upcoming things for example last time like before I sign off last time we had Elly on the study club and he's actually gonna be doing a follow up to that study club this week he's doing it tomorrow that's Ellie Ben Sasse on and I think you can find out more probably on the stark where Twitter that might be a good place or if Ellie's in the crowdcast

maybe you can add the link there so that's another event to check out and just I really want to make sure everybody knows this next week on Tuesday is the zk summit and the zk summit is a full day of zero knowledge research and we're gonna be talking about all sorts of different topics there it's if you fought if you actually click on my name in the crowd cast you should see it it's listed there and I'm also sharing it around and all of us or share it in here and I hope to see a lot of you there too so we can keep talking about all of this stuff so yeah thanks again to everybody thank you thank you all right and I will see you at the next study club then