Folding with ProtoGalaxy - Liam Eagen

Transcript

this meeting is being recorded So hello everyone uh today's September 13th 2023 and we are with uh Liam again one of the authors of proto-galaxy which is probably the latest paper in regards folding folding uh up till this date if I'm not mistaken uh so Liam is basically going to guide us through the paper and the protocol um and basically try to resolve any kind of questions or doubts about it aside from trying to guide us through the entire thing and and help us to understand the entire the entire concept so thank you Leon very much for attending to this session

and the floor is yours thanks um yeah so I'm going to talk about photo Galaxy um joint work with Ariel capison um like Carlos said and uh yeah I guess I'll just get right into it so first maybe some motivation for you know why why we care about folding I mean I think everybody here probably already knows but um you know we we have snarks uh so snark we have an arithmetic circuit and a witness and uh we want approver to be able to convince a verifier that circuit evaluates to one on the witness

um you know lots of ways we can do this equivalently showing that the witness is part of uh an NP relation Um this can be made non-interactive using Fiat Shamir um but you know it's it's usually more straightforward to talk about interactive protocols between approver and a verifier because we have this abstract way of dealing with it um there's lots of ways we know how to do this uh growth 16 Marlon Starks many others variations all the different trade-offs you know some faster approvers smaller proof sizes different assumptions

Etc trusted setup but all of these snarks are monolithic so we have one witnessed and the prover sort of goes through proves the witness satisfies the circuit to the verifier and that's it they have the whole witness at once construct the proof you know one shot um now given a non-interactive snark we can use it recursively in the following way um we can take the verifier which since it's non-interactive is is just another algorithm in fact can be represented as an arithmetic circuit

he can embed the arithmetic circuit into your circuit and then a proof into your witness right so proof for some other relation into the witness and then by checking the outer of arithmetic circuit you verify the inner proof recursively so recursive proofs are sort of generically sufficient to do lots of interesting things like incrementally verifiable computation where you have you know you know typically you have some long-running computation and you prove it incrementally so you prove like one step and then in the next step you prove that

you proved the previous step and prove the the next step and so on and then proof carrying data which is a very sort of straightforward generalization of this where instead of proving in sequence you've proven in a bag so you might have multiple incoming proofs and you check both of them and then prove the next step attached to the node in the Dag and then more generally recursive proofs allow us to prove things in parallel or even in a distributed context with multiple provers and there's lots of performance or potential performance benefits that come from doing this you know ZK proving is kind of inherently parallel in a way

that computation is not necessarily so yeah and uh yeah so all this is to say recursion allows us to kind of break up snark proving in interesting ways between multiple people between multiple um it's units of time yeah but there's a problem proving the verifier in circuit is often expensive it might involve checking pairings or in the in the worst case if you don't have a sort of efficient verifier if you have a linear time verifier like as in the case of bulletproofs it sort of just doesn't work at all because your circuit

ends up being bigger than the initial circuit and you know maybe there's ways to avoid this but doing the entire verifier in circuit is a problem and and we would like to avoid it if possible so how can we do that um one way is folding schemes uh so rather than verifying an entire proof inside of the circuit we Define a new relations we have our original relation for the circuit and the witness and and then this new relation which is in some sense relaxed which we will you know expand on later but once they have this relaxed relation we we can Define protocols to fold the

relation and the relaxed relation into a new relaxed relation or folds to relaxed relations into another relaxed relation um and then if the the new you know folded uh instance is uh valid it should be the case that both the inputs to the folding were valid with an overwhelming probability so I mean like at a very high level the way this works is you you kind of have your witness and you have your your commitment to your witness and you can take a linear combination of them um the details of this vary but you know the that that's essentially the trick and then when you do that and you

evaluate your circuit over the linear combination you don't get exactly you know a linear combination of the the outputs of the circuit so to speak you end up with some error terms from non-linearities in how the circuit is computed so you have to compute those and send them to the verifier and uh you know this linear combination means that we can't use um or we have to use homomorphic commitments like Pederson or kcg or something you can't use fry for folding at least as it's currently you know used uh yeah and so the point of doing all of this is that the folding steps where we combine the relation and the randomized

relation um are easy to check uh like I said they're essentially taking a linear combination of commitments and that doesn't this doesn't depend on the witness size necessarily at all you can have a very large commitment or a small commitment to a very large witness and just take linear combination and so the folding verifier which is the part that just checks this folding step can be very simple whereas the final verification where we would check the randomized instance can be very expensive for example in the bulletproof case it might be a linear time verifier in the size of the final randomized instance but it doesn't depend on the number of times that we've

folded um yeah so we were we're able to reduce the recursion overhead as compared to kind of more straightforward uh recursive proof composition because we don't have to do the whole verifier in circuit um yeah and so allows us to use bulletproof potentially although you don't you don't have to uh yeah so some brief history of folding schemes they they uh were introduced to Nova for rank one constraint system um

and then extended to other arithmetizations like Planck and look up arguments and extended to folding multiple R1 CS instances in Supernova for non-uniform incrementally verifiable computation which is just like normal incremental incrementally verifiable computation but instead of having sort of one step that you take each time you have potentially you know a number of steps and you take one of them and you want to be able to fold that uh and then in hypernova we use a customizable constraint system which is kind of like a generalization of r1cs to higher degree Gates

uh yeah and then in protostar uh we kind of take a step even further back in terms of abstraction and we just fold a polynomial so the arithmetic circuit that I mentioned initially uh in in sort of typical snarks you wanna you wanna arithmetize your circuit in some way that's efficient to prove so this would be something like r1cs or Planck or ccs uh and that's because in the kind of Monolithic setting that's that's all you do right you prove it and then you want it to be efficient to verify I suppose you want it to be efficient to verify in

produce or unfolding right you only do this big expensive verification at the very end um so one interesting aspect of protostar is that maybe we can use polynomials that are like less efficient to find to verify in the decider at the very very end to decide if your whole folding was done correctly um and uh but are more efficient to fold so and then in proto Galaxy we Ariel and I extend protostar to fold multiple instances so that's kind of what I'll talk about now um and there's some you know other

differences small differences from protostar so just to compare kind of the the state-of-the-art I think uh I I think cycle fold is is newer but I'm not sure if it's I feel like much of this will probably hold for that as well um yeah fold is compatible with protostar and actually it's compatible with basically anything okay yeah cool so hypernova folding scheme for CCS uh the way this works um this is written a little bit non-standardly but I think it it's helpful to think of it kind of this way

you have your your polynomial G which in the standard way of writing it is the sum of our subsets of these uh Matrix Vector products and you're kind of applying this row wise to the Matrix Vector products A1 X A2 X and so on um and you can sort of see how this is a very natural generalization of rank one constraint system where G in that case would just have three inputs it'd be like a b and c and it'll be a times B minus C and yeah so we checked each row of this vanishes and that's what it means to satisfy

the constraint system so the way hypernova sort of works is it does some check uh in the folding verifier so to speak the the prover unfolding verifier interaction and the way this sort of works is um that you you do some checks to reduce each of these Matrix Vector products to a scalar and then you can kind of evaluate this outer gate polynomial G on those scalars um and so in doing this you you're you're going to have login hash functions where n is here the number of uh rows in a uh in A's and the sum check will then be

over degree D where D is the degree of G um so yeah um protostar by contrast folds arbitrary polynomials um and in particular it is possible to fold a CCS with protostar if if you wanted to this polynomial G has written up here is also just a polynomial in X right like if you kind of Imagine playing the X out and you've got your G evaluated a times x and then a 2 times x so this polynomial can be folded uh using protostar it just generically um

and so in that case would be like f is equal to or f of x is equal to this expression um over all the eyes yeah and so the when I said we take a linear combination of the witness that I mean in protostar this is more or less literally what you do right you have your this is kind of informal but you have your f you have your witness zero and your witness one and if f is homogeneous which is necessary in protostar if it's not it's very easy to homogenize F but just assuming that it's homogeneous and you evaluate it over these sectors or this linear combination of vectors every term is going to have degree D

because it's homogeneous and so if you gather up all the terms that don't depend on X you end up with exactly F of w0 and if you gather up all the terms with uh degree D and X you'll get F of W1 and this middle part is the the error terms so folding here is basically just this you got to compute the error terms but you can encode your original uh instance satisfiability on the lowest and higher highest order terms um importantly in comparison to hypernova we don't do some check this is this is it we there's a there's a randomization um of the the independent F equations to

turn it into a scalar equation rather than a um vector equation but we don't do some check so that's probably the the biggest difference I think besides the generality uh to hypernova um and uh because protostar is so General and F is just a function or a polynomial um it's very easy to support lookups and non-uniform incrementally verifiable computation efficiently uh just by sort of constructing your F in an appropriate way uh and this this is an interesting part of the paper where there there's these constants that sort of appear in in analyzing how

the proverb performance or what the proverb performance is and it's hard to say generically because the f is so General that it sort of depends very much on what your f is right again the worst case your F could be very expensive to compute but that's typically not the case so anyway um and I think at this point it's still kind of an interesting open question how much benefit this unstructured F get to compared to something like CCS which is more structured or plunkish or whatever and uh the trade-off ends up being in the decider so if you're doing a lot of folding you'd kind of expect that maybe

there's some benefit from having a highly unstructured F but you pay for it in the designer and you know I guess we'll have to see um so produce star supports binary folding right we have an instance in randomized instance into a randomized instance or two randomized instances into a randomized instance and that's sufficient to fold um here it's just like in instances and M randomized instances um you just sort of fold pairs of them n plus n times you can fold in a line if they're produced as part of like a IVC thing or you can fold in a tree if you get all of them at once which is maybe better for

uh definitely better for parallelization um but yeah proto-galaxy instead supports folding sort of all of the instances at the same time um so when you fold in in pairs you you have a hash uh for each pair that you fold and you do a scalar multiplication for each pair that you fold when you fold multiple instances at the same time we're able to avoid some of that overhead uh which is the goal of protostar so for example we have a k MSM instead of K kind of independent scalar multiplies which for large K is a potentially significant savings especially because you're doing

all of this in circuit so Computing kmsm is cheaper than Computing K scalar multiplies uh separately and uh yeah there's some other differences um I don't know uh I I suppose yeah the the main ones are are that we use instead of a Proto star which has this this uh thing here we we have a LaGrange polynomials here which you know more straightforwardly generalizes to more witnesses and the randomization of the F's uses a different constraint separation but

that'll probably make more sense in a second um this is taken from the paper and it's the verifier the folding verifier complexity for uh the different protocols so we have hypernova for I think just two uh inputs here um protostar uh Proto Galaxy and so there's actually two types of Proto Galaxy uh there's uh well I'll talk about it in a minute but uh one of them uses a multivariate some check and one of them uses a univariate um captain of zero check mod Z and uh the basic difference is the number of hash functions so uh you'll notice here that this K comes out

because oh and then the sun check version also folds multiple accumulators but um yeah anyway um another difference between protostar and Proto Galaxy is uh that protostar has a sort of constant size accumulator and as a result of that they have these two group additional group operations that you have to do in circuit um Proto proto-galaxy uses just login scalars and so the size of the accumulator is not constant but you don't have to do the group operations in circuit the group scalar multiplications I should say

yep so just some definitions uh you know f is a prime field cm is a commitment scheme um see I'm here like I think there's a footnote about it but it's it's not necessarily like one commitment it could be more commitments but for the analysis like for example here I think we assume that it's one commitment everywhere um but protostar in addition to being a folding scheme is uh a kind of a compiler for special sound protocols into uh foldingx teams and in that case you have multiple commitments corresponding to different rounds in the in the special sound protocol

um zvex Vanishing polynomial uh typically like a you know K to the x minus 1 because of ffts but it doesn't have to be um the LI or LaGrange polynomials so these are going to be one when evaluated on RI and zero when evaluated on the other roots of Z standard K will be a Boolean hypercube which uh it's just bit strings and dimension log k EQ is uh kind of like the well it's it's sort of like the multivariate you know analogy to LaGrange polynomials um I mean you kind of like write it like

this or like the B encodes the index into the Boolean hypercube and the I is the index since the roots of Z but you can see here that if a and b differ and uh they're both bit strings then I should say if they're both the same then either every value is uh or each value is one in which case this term will be one and this will be zero or they're both zero in which case this will be zero and then this will be one and if they differ then both of these will be zero so the whole product will be zero so EQ is only one when a equals B over bit strings um the mle multilinear extension of a vector is just this

multivariate uh multi-linear I should say polynomial um that when evaluated at the bitstring B gives uh the V with index B and here I'm kind of abusing notation but you know if we're indexing V with integers then this would be you know the integer with those bits um and then finally pow is just a function that we use for um taking random linear combination of constraints uh yeah and it's just the product of the xg's and so you know it has this nice kind of thing where if you evaluate it on these powers of 2 to the I Powers by 2 to the I you get x to the I yeah so

protostar style folding so we're going to fix some polynomial F of degree D that takes uh some Witness Omega of length M and produces uh some Vector of length n and we say that the witness satisfies this function this polynomial um if it's zero on Omega and it is an element of the relation if Phi is a commitment to Omega um so we have our relation and this is super General right F could be R and CS CCS some weird polynomial that is useful in some situation it could have lookups

and non-uniform stuff and so on and then in order to define the relaxed version of this we can add e and beta to the instance so we're going to have Phi which is the same commitment beta and E and then Omega and this is an element of the randomized relation if the linear combination of F5 Omega by power I beta gives us e um so the intuition here I guess is that um eventually we're going to have like Omega naught Plus x times Omega 1 or Omega naught times LaGrange plus Omega 1 times the LaGrange

and when you do that you kind of end up with some some error terms and as long as the folding verifier checks that their our terms are constructed correctly then everything works out but you have to keep track of that here in the randomized uh I can ask a question here so uh this is sort of similar to what is done in protostar but with uh like two challenges that they use for the final uh for for the like gate compression trick but here but here you are not your Edge and logarithmic amount of Challenge and this beta is the reactor actually

right right and uh are there actually challenges or are they like just some additional variables how does it work so this is a good question um the betas are they're they're a little bit like challenges they're sort of like a folded object that includes challenges um so uh I think it'll be explicit on the the next slide but um in protostar uh instead of using so these pow functions have log degree log the number of uh log n right um and they're log betas

um and like like on the previous slide they're just this this product thing which has log terms because there's you know log bits and I um in protostar instead they have two vectors of length square root n and uh each sort of random coefficient here is just a product of one of those two uh and it's sort of an interesting space of of possibilities here because you have this pow I right and here we're taking log inputs but you can imagine instead that how I was like in base three or something right and so instead of having x x squared x cubed x to the eighth it would

accept like two times log three values um being like x x squared and then like x to the third and then x to the sixth then yeah maybe this is not a good thing to explain in words but it's sort of the tensor decomposition of like a vector of powers you can sort of factor this tensor or this Vector into a tensor product and so protostar does the Other Extreme it factors it into just two vectors of length square root n whereas we here Factor it into log n vectors of length two or implicitly um yeah so so to answer I think your question beta is kind of like challenges

and it includes challenges but in order to fold it's not it's not like just a challenge right it's not just powers of something it'll be powers of something plus you know random linear combinations of other stuff okay so specifically but you're relaxed relation is just this equation it has no a difference in protestator will be additional equations on Powers of challenge oh definitely yes there are no additional equations but here it is just one equation that's right yes okay yeah cool uh yeah this is different um and uh just you know some people have asked me about about this this sort of

this transformation because the way the paper is written we fold one R and one randomized uh R uh but if you wanted to say fold two r's there's this very like straightforward way to lift from R to the randomized version because if you take in this case this should be a vector or betas but if you take any like random Vector of log betas then uh your e is just going to be zero um so yeah what if you want to fall to our grants together you you are forced to relax one of them at some point or because in hybrid Nova for instance when you execute the sound check is not only uh

to kind of like reduce the problem into a smaller one but you are also you are also basically applying some real randomization of the terms so the randomnesses are homogeneous and then you can fold things together what happens here um so the there I mentioned before there's the two proto-galaxy style foldings but I think essentially the same thing will happen if you have two RNs then we need to make the betas the same for both of them to fold um and that that is what we do um when you fold multiple uh are so if you fold two orange you end up with some linear terms in here and that that turns out to be fine we can still

do everything in linear time if you have like many many betas in there then then it ends up being a bit of a problem and that's why we do this the some check proto-galaxy uh as well which I'll talk about like second but okay yeah I think to answer your question yes you you have to make the betas the same and then fold like uh like in hypernova I think yeah thank you then protester you do not need to do it with different challenges no problem hmm as a single equation of degree in product star Z plus two here it will be

Z Plus Logan and fold yeah uh yeah yeah uh well like you're saying like the betas are part of the I guess the witness or the instance and then yeah they're like public inputs basically yeah yeah uh yeah I guess maybe my answer to the previous question was was not quite right uh that I I guess that's actually more like what you do in proto Galaxy um uh yeah yeah okay in this in the sum check folding multiple accumulators thing it's more like the Proto star thing where you you treat the betas as part of the instance and you folds all of it and you just treat them as like any other

variable and uh yeah yeah okay yeah yeah um okay so two Vanishing checks uh Technique One mod z uh you know this is they're just trying to show that v v is a zero um um and uh yeah so PX is is like this maybe we compute PX in some some way that is not just going to result in identically zero over here uh and then if p is zero mod C then V is zero off mod c um yeah and so if you want to test this this is very easy to pick a random value

evaluate it at X being the random value um so in in uh in here right we're gonna have some something like this some some linear combination of lagranges and it will appear inside of f here and when we do that f is of degree D and this is of degree K so when we compose them the degree will be D times k so the degree increases linearly in the number of instances to fold and there's also this extra log D that comes from you know working with higher degree polynomials um just multiplying them and so on but it's simpler to describe and it uses

fewer challenges so that's why we included it in the paper uh the randomized sum check is the other kind of Vanishing check so we we still have a vector v we want to show that it's zero pick a random R maybe a random powers or you know a tensor product of some random values or just you know and then summing gives zero if V is zero with overwhelming probability uh you just like uh Technique One like could you like wait a bit oh yeah I do not understand it uh so um you're trying to to fold to just

folder multiple right now just fold uh well yeah no this is for for K instances each each L is going to be the LaGrange for um x to the K minus one so the the idea here is that P is going to be of degree k you know roughly as written it's kind of abstract and maybe a little hard to follow without the the concrete yeah I'm just trying to compare because like uh I am I was implementing for foreign uh just because you need to compute your

closed terms but here you are saying that if you are don't get the lagrangian basis you can fold multiple multiple uh Solutions yeah you can fold multiple instances uh with these lagranges um and so like I guess I just skip ahead Maybe yeah it shows up here right so we have our instances uh this is what we're doing right we're folding one randomized instance and a bunch of uh you know pure instances and inside of f we have the the randomized one and all

of these and so this this whole thing will be of degree degree k right uh and then f is of degree D um and so that's that's kind of how it shows up and oh again I understood okay okay uh let's see since it's clear for me but okay okay um yeah uh so degree K composed with f is going to be degree K times d um yeah so here we take the random linear combination and if we use multivariate some check it'll have log uh it should be log K log K challenges um or No it should be logged in uh well it

depends on the length of V it's not specified here how the length of V is um and it turns out that this is what we will use to fold multiple accumulators um one question go on left load yeah my question was that this subject will be against the polynomial which is not multilinear but of Multiplicity because the result of application of your F to the linear polynomial multilinear polynomial right that's right yes okay uh oh yeah so I have I have another question which is uh in this technique tool if we applied something like xenomorph for example and

we go from the multivariate to the univariate uh world do we end up in similar results as in Technique One not in the sense of the LaGrange but in in the sense of performance amount of operations in asymptotics uh or or no we have another landscape I think um the right way to think about using xeromorph to go from multivariate to univariate would be kind of like uh you know at the end so to speak right like the the degree Decay that you get in this univariate case is is eliminated by using like multivariate some check here

then after you use multivariate some check here you you would use something like xeromorph I mean and in this case I don't even know I don't think xeromorph would actually quite make sense just because you're not you're not really evaluating like an mle you're taking a linear combination of things in a some checky kind of way but you already have them as separate commitments um but uh no I would say like the way you you have like this expression and you can either like some check it and then you get you reduce it to um mle evaluation claims and then that's where you would use xeromorph or you uh evaluated on a univariate in which case

you have a quotient computation and uh and a higher degree but you use fewer hashes um and this this is like I mean this is like a pattern I think that shows up all the time um it's kind of the a lot of the the reason where I think has been taking stuff that that that was written using like kzg and quotient computation and seeing if you can shift it to just use some checks I mean of course you can um and then seeing how the the trade-offs play out um that's that's the the main difference between these two I think xeromorph uh just wouldn't wouldn't really affect that

okay okay thank you oh and uh I think I have another question about this randomized some check version so if you are uh doing IVC then it's not exactly clear for me so for example uh in some check you need to open some multilinear commitment and then right so in hypernova you like carefully defer this uh to the later uh to the later rounds of IBC so you only need to do the opening once and then but here it seems you would need to open it right now right like after the following so it's it it's a little bit like

um um sorry uh so the the difference is is basically in the randomized some check version we're we're not so in hypernova right you have your X and you you have the or you have a times x and then you have these mles that you evaluate and then then you're saying you fold the evaluations here you have like multiple instances and you use some check to take a linear combination of the instances um you at least as protostar is written you don't you don't fold that you actually in the folding verifier you just take

the linear combination of the instances um if that makes sense you don't you don't take like an mle and evaluate it you you kind of have multiple instances and then the the step where you would ordinarily have an mle evaluation you just take a linear combination of commitments in the same sort of structured way uh but but you would need to open them in different points very eventually so you cannot take 99 and I will take random combination um okay maybe maybe we get I I hope we get yeah sorry uh

yeah yeah okay here we go um okay yeah uh yeah I hope it'll be clear when we talk about it more concretely um okay so this is the mods The Vanishing check um and so it's just going to be some some algebra but we start with a randomized instance and we have beta and then we have a bunch of uh instances here that we want to fold into a new randomized instance with the Stars

so the first high level step is we will refresh the beta with new Randomness in light of these new instances that we're folding uh what kind of like lift all of these instances to use the new Randomness beta Prime I should be beta star but um then uh combine all of these new lifted instances with the same Randomness uh using the LaGrange zero check which is analogous I think in some ways so the hypernova you know lifting or folding of evaluations um choose a random value to evaluate the lagrange's and uh finally uh you know just compute these

this new instance after we evaluate the lagranges so the way this works is pick a random Delta linearly interpolate between the the existing beta and the new Delta and this is how we're going to generate the new Randomness beta beta star or beta Prime um this polynomial f is going to be this and you'll see that when X is zero this just becomes power I of of uh this should be beta it's written backwards it should be power I beta so beta plus X Delta and then that would give you e and these error terms um so here if we have uh beta beta Prime

coming from another R random instance how this beta Prime will be included into this f of x yeah the this version of Proto Galaxy does not support folding multiples okay okay okay okay fair enough fair enough yeah it's it's a good question I mean it the so like the one way you could do it at least um in principle is here instead of having beta plus X Delta which is what this should be you'd have like beta 1 times a LaGrange plus beta 2 times the LaGrange and so on um when you have K accumulators right

this inner expression would be like degree k and then this outer path thing is is degree log n so the degree of this whole factor is going to be K Times log n and you're going to need to do a lot of polynomial multiplications of things with degree K and that is uh specifically what what we want to avoid with the sum check version which it which it does it avoids those those log or that those degree K polynomial multiplications that would come from there um that makes complete sense thank you very much yeah um yeah so we send these error terms we receive this Alpha

and uh we would compute the new beta uh here what does what does a in the third yeah I just noticed that I'm I think that might just be a typo I'm sorry uh this thing yes yeah I don't think that's supposed to be there it's supposed to just be sum of f High x i here and get this part uh yeah yeah um and I guess maybe one important point that we should we should dwell on a little bit I I haven't written it down in the slides because I feel like it might be a little bit too too dense to to fit into the slides but I can look at the paper if anybody's

interested um anyway you can construct this F so this F has degree log n right because this is degree one and this is degree log n and so degree login um and if you were to compute it sort of naively um you would you could compute each pow using I guess it's something like log what we'll call it like you know of login things like oh Vlog and squared or something like that uh field operations right because it's a product of these linear terms and there's log n of them and so on um it's

like login Times log log N squared maybe um and then you'd sum them all up so that would be an additional like a factor of n uh or you do that n times I should say and then you have to sum them all up so the naive way of computing F would would not be o of n in the number of of F's uh what we do instead in proto-galaxy and uh is as you start out with the tree um and at the leaves of the tree you have all of these f i Omega values which we assume that we already have which is reasonable I think then if you think about how these powers

are structured they're products of log terms and as you go through the bits of I each term appears or does not appear based on whether or not I is one or zero because remember pow is um when when it's evaluated over Powers it actually just gives you the power power um and so in in our tree we have all the F's at the leaves and then the first level you have like the first bit and so like uh maybe it's the highest order bit I'm not sure but like these two values differ in only one bit right the the first term and the second term so zero and then

like one and then the the factors label the edges and so we start with F0 here and we start with F1 here then we would take the first factor of pow multiply it by F zero and then multiply the I guess it would actually be one but we multiply it by F1 and then add the results and so we do that for each pair of leaves and so there's n over two pairs of leaves and then the second layer of the tree is labeled by linear polynomials we can do the same thing again because of the structure of Pals so in the second layer of the tree we would multiply this first this one by a linear

factor which we can do in time linear in the degree of the node and this would be multiplied by one let me add them up and we get a degree 2 term on all of the second level then a degree three term and so on and so the total amount of computation that you have to do here is going to be like n over 2 times 1 plus n over four times three or two and then n over eight times uh four anyway the the degree increases linearly as you go up the tree to log n and the number of leaves or as internal nodes at each

level decreases exponentially and if you sum up all of that that's how much field computation you have to do you it turns out that F actually only takes o of N Field UPS asymptotically to compute even though the degree is is log in here and the sum has n terms so this is a this is actually I think fairly similar to how um like linear time perverse for a lot of multi-linear stuff work but in this case we're we're working with polynomials so there's the additional complexity of the degree and uh yeah this allows us to have these um login beta values in the instance

um and still have an oven prover uh sorry and another quick question so do I understand correctly that all the cross terms that you send are field elements but you actually still needs the commitment to Omega I mean in the instance structure you still have the commitment to the uh with definitely yeah fee is the commitment to Omega um that's what you're asking yeah okay yeah cool I might I might try and go a little

faster sorry uh yeah so we want to linearly combine so now we've computed this new beta and we can just lift these to use the new Randomness so since cm is linear we we what we want to end up doing is take a linear combination of Omega and these Omega I's and then since the commitment is linear we can similarly take a linear combination to the fee and the fee I uh yeah and so there's this helpful little Lemma in the paper it's uh I think not super surprising um there's a very simple kind of argument for why but basically if we evaluate F on this sum of lagrangeas then the F kind of like commutes in so

we end up with f of Omega times the first one F of Omega I times the rest of them and then this quotient quotient term over here um and you know to see why if you evaluate both sides at a root RJ right all of these terms except for one will go to zero and then LJ will go to one so we'll have when you evaluate this at RJ F of Omega J and similarly when you evaluate this at RJ all of them will go to zero except for one and you'll have F of Omega J and then you'll have uh this just goes to zero because zrj is zero so both sides agree on all of the roots and uh

that's basically all the information we need all of the other stuff is encapsulated in this error quotient term so the prover computes Q which does require the sort of degree D ffts I think that we mentioned earlier because f is of degree D and uh at least degree d right um and so yeah we compute q and uh just send Q do you get so from these Lemma that you have here do you get any benefits from being able to um remove the omegas from from the like from being together with the with the LaGrange polynomials like can you basically pre-compute something

then still have this uh lemon quality holding or not um I don't know I think probably uh not but I'm I don't I'm not sure it sounds effort for me are not pre-computable maybe I'm missing something then oh F of Omega is definitely executable yes and so it happens with f of Omega y right yeah in fact all of these because the Omega eyes are just part of the relation we'll go to zero zero and then this this comes from here which you might assume that that we already have pre-computed okay fair enough okay in fact all of this is this just vanishes and we're just left with

this which is what we're gonna yeah so after we send Q the verifier chooses gamma to evaluate and uh yeah we're just gonna sort of plug that in everywhere um so if you look here um F of uh Omega actually I guess a little confusing but yeah whatever um yeah we we end up with the E that comes from the l0 and Omega evaluated here we end up with the linear combination of commitments that we've mentioned from here and here and we end up with the linear combination of witnesses uh from here and here and um

that's it now now fee fee uh star beta star e star and omega star is a new randomized instance and uh foreign if I mean you know if you sort of go through the paper I think uh it's it's not too hard to see how this uh you can write an extractor you know to show that if if this is a valid random instance then this must have been a valid random instance and these must have been valid instances um so yeah that's the first version of Proto Galaxy uh yeah so the second one

um here uh there's you know in the paper we talk about folding multiple accumulators or folding you know accumulators and instances but I think it's it's probably fine to just look at the folding multiple accumulators case here because like I said before you can sort of trivially lift instances to accumulators maybe you don't want to maybe it's more efficient to not do that but the paper has more details um so in this in this case like we were mentioning before we have all these betas that are different uh for each randomized instance and we want to kind of make all the betas be the same or something like that and uh

if we were to try and fold like protostar or try to make the betas the same in some other way you end up with this issue when you use the LaGrange polynomials because they're of degree K and the pow function is the degree log n so you'd end up with like a k log n here and a KD from the K into the inside of the f um yeah um so this is exactly what I mentioned before we have these K degree K polynomial multiplications that we'd like to avoid and the way we're going to do that is to use the randomized sub check um

yeah so we have K there's a Boolean hyper Q I'm sorry like wait it so yeah so it is possible it is possible to add multiple accumulators in this version right with the lagranges like the the yeah I mean it is definitely possible um for example it's uh it's okay to consider Gates of relatively High degree like d equal to I don't know 50 or something like this um yeah yeah minus clearly small I'm sorry log m is clearly smaller than D that you can afford in protostar for

example okay sure sure that that's true um I mean this I'm not understanding the third uh ballot Point here uh so you're saying that well I will be much harder to computer what yeah yeah uh that is that is what it's saying so the tree um computation I was describing before where you have the leaves and then you have the factors that come from the power I along edges and then you kind of compute everything in linear time when the degrees are of uh degree K labeling the edges um and it's no longer linear or I should

say I mean it's linear and N but it depends then on on K uh okay yeah I guess it's a matter yeah no it definitely it definitely is possible to use the lagrange's in in more or less the same kind of way is here right instead you we have the lagrangeas with the witnesses you could just as well have the LaGrange there's the betas in here and the lagrangeas with the Witnesses in here and all you'd end up with is is just a polynomial of higher degree and the pals would be more expensive to compute but that's I mean not necessarily like a problem if uh uh yeah depending on the

I don't know does that answer your question sort of uh also okay I'm sorry that I'm like stalling the lecture but I really want to understand something they're not currently clear so um when you were folds and can you maybe open the previous slide so when you were you're folding so uh this queue there's also uh I mean I have an impression that at some point you need to send some commitment maybe to the emotions polynomial or or

something like this but you are saying that you are only sending field elements yeah um so you have to send I suppose you to send like an oracle to queue you don't you don't have to you can send the field elements if you that's fine you can send a polynomial commitment to Q um it's you know I I think in the paper we just sent you okay okay well whatever it's relatively low degree sure yeah yeah yeah maybe that's that's another reason why you'd prefer to avoid adding more here because when K is very big

sending Q is uh is large right um it's gross linearly in K uh because Q comes from this like composition of degree D with degree K or or degree D plus log n with K in which case it would be even bigger and then you have to send that commitment to q but maybe that's fine it would it would definitely work I think okay foreign so the so this is the subject version

um right we have the randomized instances we have a Boolean hypercube of Dimension log k uh we're going to sample some Randomness as before and here we will Define this uh multivariate which yeah I think if so this multivariate if if you like ignore this term and you kind of squint and and pretend these eqs are lagranges is sort of what we were just talking about right you'd have like your LaGrange of X here times beta and you have your LaGrange of X here times Omega and uh

yeah and then it would be Universe instead of a multivariate you'd replace B with a capital x but here we have this multivariate and um because we're doing uh some check Vanishing check we need these sort of randomizers out here um yeah and if we think about this multivariate and you evaluate it at each J and K then uh this sum everything will go to zero except for one of the eqs um similarly here all will go to zero except for the EQ where l equals J so we're going to end

up with beta J and Omega J in in here and uh then this is just going to be J times Delta and so given our randomized instances uh it should be the case that the sum of Pau beta J and Omega J here gives e j that's that's from the definition of the randomized instance and so it should be the case that g evaluated in each J in the Boolean hypercube gives this value so if we sum over all the values in the Boolean hypercube you get G of J minus this value should vanish this is what we would like to check if this is the case then it should be also the case that

each of these is a valid range of instance one question here so here we just have a randomized instance but we don't have like the regular ones you have said that basically you can lift the regular ones into being randomized ones and then plug the plug them in the question is do you get any savings for like is there any way I guess is the first question too merge together randomized with randomized and with not randomized so like all up all at the same time which is exactly what happens in hyperboa well yeah yeah exactly what happens exactly yes it is uh in the paper the section before we describe

holding multiple accumulators there's also the folding instances with an accumulator sort of in the previous way but if you want to do n randomized instances with M non-randomized regular instances yes what you'd sort of do is is you do this to combine the randomized instances and to generate a new beta and then you would use that beta with the non-randomized instances and then fold those uh okay can't you just like in in this session can't we just Lift Every anonymized instance during the most one and then

use this thing as a black box yeah you can I I think it might be slightly more efficient to do it the other way but I mean it's not obvious to me saying it right now if that's actually true um but yes you can definitely just lift it so in that case you you just like pick another random beta say for all of the non-randomized instances and then you'd end up with randomized instances and you get a zero in here and you just do this that would that would work as well is is it the case maybe that you could uh go the unibody at the slash LaGrange way for the fall of the non-random ones fold them and leave them all together

into a random one and then go for this yeah I I think that would also work for sure will that bring you any benefits I don't think so right it will it will basically be the same um yeah I I don't I don't know that it would have significant benefits the like like we were sort of talking about um when K is large the LaGrange version I think starts to make less sense because of how big Q ends up being um which is theoretically weird no because normally you use LaGrange when you have big things so it's a bit counterintuitive no like I mean I mean it's it's not like so big that

it's impossible to work with it's it's just like I think I think less efficient probably than the some check version although I I don't I don't know I guess it's sort of an empirical question how the trade-off ends up working out um but hashing I think in circuit is is fairly cheap so I don't know fair enough uh yeah okay so this is the sum that we use some check on so we're summing over these JS and then each round we're going to make one of the bits of J uh a variable send a degree D plus log n right because this

is log n and this is degree d uh and each of them will be evaluated on a linear polynomial um yeah and so we'll send that and then verify we'll choose a random camera evaluate that move on to the next J and um it turns out I think that uh that basically well I think it's very similar to the tree computation I described before um in this case the leaves end up being these degree D F's and the edges are once again labeled by these linear polynomials that come from

inside of here and so we can still compute kind of in in a way that is linear in and linear in the number of F's uh we can compute each of those responses in the subject type protocol in the paper these are called p p a polynomials I think uh yeah and so so that that's pretty pretty convenient we like to have linear things and ultimately it reduces to this evaluation claim for G and a while back uh I was saying how we don't we don't like have an MLA of the witness we just have this this is the

mle that we have to evaluate this G of of gamma um and evaluating G of gamma does not require like simplifying beta or simplifying Omega if we plug in gamma here this just becomes a scalar and then this is like a linear combination of the betas by EQ Gamma or yeah EQ gamma L times Beta And this is a linear combination of the omegas by EQ gamma L and um so on the next slide I guess I don't explain but after running the sub check we want to check that g of gamma equals some constant C that was produced by the

subject and uh and so in order to do so this this check ends up becoming the basis for the next randomized instance um so we have G of gamma is going to equal this expression evaluated at Gamma equals c so to put this in the right form for a randomized instance we have to divide off this extra EQ evaluated gamma which is what we get here and we have to combine these the sum evaluated gamma to get the new beta which is what we do here

and similarly we have to combine the omegas by the gamus and then since we've combined these omegas by these EQ with the Gammas we combine the fees with the eqs with the canvas um yeah and so this is the part where you're evaluating at Gamma this computation and this computation specifically is evaluated in the folding verifier the folding verifier checks that these commitments are properly linearly combined um and so yeah this is this is just an MSM of size k so the second second row second equation

is analog of uh computes and your LaGrange uh combination of LaGrange polynomials at random point exactly yeah you you it's it works out almost exactly the same you have the LI gamma as sort of like gamma yeah like how is it dynamism of size and like I should say as K I think because this is a site okay is it isn't it too big though to to put it inside of the circuit um no your thoughts on key things of course you need to linearly combine them oh yeah yeah okay fair enough fair enough fair enough I forgot about the

multi-folding okay yeah yeah if it's multifolding it definitely makes sense okay yeah yeah yeah uh this is like extremely similar to hypernova's last step of the multi-folding like yeah it looks the same but changing it's just changing the names yeah yeah uh okay yeah and then just some stuff about the verifier uh has to check this kmsm we were just talking about so compared to um protostar you'd have K scalar malts in each of the pairwise foldings um and because of tippinger this this

can be this can be faster approved um there is some interesting work I guess it's not like in the paper but um I think it's it's interesting to explore I thought I would include it in the presentation I mean I can talk about it if you if I don't have like concrete stuff but essentially here we're checking a linear combination of commitments right we have the feed JS and we're taking a linear combination by these eqs um the folding verifier doesn't necessarily have to compute that maybe it's possible for the folding Pharaoh flyer to Simply check that fee star is this linear

combination and it's possible using inner pairing products to to check this linear combination um I think I have a comment on this I think I have a comment on this so uh at least for me it seems uh that when you are in the high degree world uh then uh your inner product argument is likely less efficient than properly than people because um because it's actually quite a low degree your with your weakness I mean if we are talking about your inner product

argument then uh it's weakness it's actually of the great too it's it's circuit is actually very very uh wide Circuit of degree too because and some some of actually physically one because your Computing your witnessing a bunch of points and so um so it's a bit hard to come up with uh to to use to our advantage that we have access to the polynomials of crazy but maybe it's possible to come up with something um okay I'm not sure completely follow

we could discuss yes okay sure sure uh yeah and that's that's all I have um so any any uh further questions or discussion um but uh yeah that's that's it I have one question which is in regards of designers which we haven't spoke or spoken about then I'm not shooting the paper uh like was deeply explored and what I'm what I wondered is from like since the check is really similar to hypernova what I presume is like mostly what works for it

uh should also work for for that protocol but do you know like like do you have any kind of preferences or do you think that something might be better to using the decider like some kind of protocol uh than any other one like for instance is it better to go for Spartan or is it better to go for good author long I don't know whatever it is yeah um so I think I think that it's not necessarily possible to say in general it depends very much on your f um if you're f is chosen to have you know structure that that aligns

nicely with a proof system then it probably makes sense to use you know the snark that aligns with the structure of f uh for the decider okay um yeah uh yeah I think uh the yeah I don't know if there is like a generically correct answer right if F has something that looks like uh CCS maybe maybe it makes sense to use that or a proof system for that if it actually looks like Planck then so on um makes sense makes sense yeah and I I think I also

have a comment on this so uh sorry so maybe there is something in some some coming yeah there is a question in chat oh I can't see the chat hold on binary tree IVC like paranova with hurricane emulators [Music]

um interesting yeah um I mean as written in the paper when you fold multiple accumulators it doesn't really work with um or the LaGrange version written in the paper does not work with folding multiple accumulators would it be better to go with the LaGrange insurance I think if we're two accumulators they might actually end up being almost the same um a thumb check of two things is just going to have like two terms um and uh those two terms are maybe not exactly but like almost just the LaGrange polynomials for Vanishing set of size two

um so I don't I don't know that it makes a huge difference uh it's probably at least as written easier to go with the some check version but it would end up probably being the same or very very similar in overall performance characteristics to the LaGrange version foreign which is in regards of the of lookup arguments that we can plug in into here uh can you like at least give the intuition on how this will look like and will affect the the folding equations like that we just have like an extra term whatever we take into account all

of the lookup related stuff or like we do we have another round drought to take um so I think that I mean we don't talk about it in the paper but it should be the case that the lookup argument from protostar works with either very little or no modification in proto-galaxy um and the lookup argument from protostar is pretty pretty neat it's a log derivative based but also each folding step does not incur cost proportional to the size of the table you're able to like defer that all the way to the decider which is uh you know very nice um in terms of like lookups generally I

think that's the that would be the easiest one to use for sure because you already have the stuff from protostar and hopefully it'd be just very similar to that um something like uh uh which lasso or something would be harder to integrate just because it's you know newer I don't know what the status of people folding lasso is well uh my status is that uh it is possible to fold the monitor around protocols in particularly care but I'm not sure that you should fold glass or maybe you should fold something like look up um but it it is sort of doable uh yeah

um yeah yeah and I wanted to to say that for decider uh actually um I think whatever whatever wrote you take uh it is very likely that you would need to use uh higher degree Gates either higher degree Gates or um um I I would say that it's pretty unlikely that your reformatization if you do if you optimize stuff correctly of the decider coincides with uh what you can do inside of the protester and so I think it's more um it's uh more logical to just optimize

for the following and then have decider to emulate um to emulate this in your arithmetization uh in your chosen a reputation like for example Blanc yeah I think that's that sounds right uh yeah well definitely okay are there any other questions otherwise we are on time already and we should lift Liam uh after one hour and a half so I will assume not as I don't see anyone writing on the chat or asking anything

so Liam thank you very much for being here today and for showing us the entire protocol and going through as many details as we have been able to ask uh yeah it has been a pleasure so hope to see you soon here and and I said uh very grateful for for you coming thank you thank you cheers everyone have a nice day