BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes by Binyi Chen

Transcript

okay so just to give a small introduction uh hello everyone uh we have bingi Chen again with us uh B was already with us uh to explore protto Galaxy which was uh one of uh his papers last year and he has kindly accepted to to come back here and talk to us about one of his latest Works which is bful so um I want to first show uh appreciation to you and and thank you very much V for for coming up again and and guiding us through through your new uh work the floor is yours so please feel free to I'm happy to do that yeah you're welcome

Char of operations so iess I guess I get started then sure sure sure okay yeah hello everyone my name is B and today I'm going to presenting one one of my recent Works called bbold with which is a new polinomial commitment scheme for marinia polinomial such that it can support arbitrary fuse and is built based on a new primitive called photable codes which I will explain later so the main motivation of this work is to try to construct a much more efficient TK snarks so I think all the audience should be familiar with TK

snarks it is a powerful primitive allow some Wick device to um to check and verify the expensive computation efficiently I think there's a already a question or should I okay yeah so I I just going continue and if any question Callos please ping me on the on the chat so I can answer uh in time I I'll definitely do that thank you yeah yeah so it is uh flight more form is aing Z not proof showing that there exist some secret witness together with some public input and then it satisfiable by some buling circusy so usually it consist some pre-processing

phas so given some public parameter and some high level program or some circus C it generate some proving key and verification key and later the prover after receiving the public inputs and the witness should be able to generate a short proof and verifier after getting the proof we outut a bit indicating whether it accepts or not so as always it satisfies SE several properties I think most of people are already familiar with so I will get go through it really quickly so it has to satisfy completeness meaning that the no approver after having this secret witness can compute some correct proofs that pass the verification and no sness means that no

matter what a malicious Prov does if he can uh like pass the verification with hyper ability it must be the case that he actually know some correct witness and Suess means that um the proof size is should be much much smaller than the original witness and should be fast to verify and dur knowledge means that the proof should be um kind of like hiding the information of the original witness so we have already seen there are tons of applications of ZK snar in the field of blockchain as well as other fields like machine learning or some other privacy preserving payment system and so on and the dream goal or timate goal here for CK snarks is to try to do

the proving as fast as Computing okay so the goal is to try to um make the speed of generating a proof as fast as the speed of executing a program uh meanwhile we still want to preserve this small proof size and verification cost even for large statement however in the reality there is still a very huge gap between the proving and pro program execution so in order to improve it there are usually two ways to try to improve the state of the Arts so the first direction is about front ends well we want to um come up with some efficient transformation from some high level program or circuit statements into some algebraic relation statement that's easy to prove for

example our CS constraint system or plish constraint system are some examples so here the goal is to try to convert a statement into as fewer number of constraints as possible and after having this algebra ration statements the second question or second direction we can improve is to come up with much faster proving algorithm for proving this algebraic correlation statements the timate goal will be like the proving time will be linear to the number of constraints you have so there in our work this will be having impact on both directions so there are so many framework for doing snars and one of the most promising

framework for having a really fast prover is the so-called multivari RP based snarks and in this framework initially we have some circuit statements or high level program statement and we transform into some algebraic relation statements like R1 Cs plish and air and then um the prover and the verifier will runs the some protocol soal poly protocol to prove that this algebra relation statements holds true so in this polyp protocol there will be um the several runs and each run the prover will send some polinomial uh to the to the verifile and verifile will reply with some challenges

and finally after all the runs ends the verifile can carry some PCS or polinomial evaluations to the polinomial oracles and according to the answer he output yes or no so this kind of Pop protocol at this point is not succinct yet because in each run the prover needs to uh send some really really large polinomial that is linear to the size of the number of constraints so you has to be combined with the So-Cal polinomial commitment scheme that allows you to commit a large polinomial into a short string and later also generates more proofs for proving certain evaluation like polinomial evaluation statements

and this com combination makes us a uh snark so initially this kind of framework was uh introduced in the setting of universe setting well the polinomial are universe polinomial but later it has been expanded and extended to the multivar setting as well by Spartan and hyperplan so you may ask why we care about multivar polyp here or multivarious kns um the key reason here is that in the multivar setting we have a significant more efficient poop protocol which is based on the Su check protocol the key Advantage here over univ Pop is that it can the pro only is to perform a n number of f field

operations rather um rather cusing inar number of operation in the univ PO IP because of the use of ffts moreover there's no restriction mostly like um there's no restriction on a field Choice except the field size um so that s still holds so indeed there is a big advantage of using a multivari RP however this this framework this s framework doesn't see a very very significant advantage over the universe KN in practice for now why the reason is that we don't have a significant more efficient polinomial commitment scheme so it turns out at at the current uh state of the Arts the com complexity of univ PCS is not that bad

compared to Martin PS so there are several options to construct a polinomial commitment scheme in the Martin line setting the first one is to do this variance of kcg or B proof but this type of scheme is not very good on the pro side because it involves some really expensive El scaler operations okay so another option is to use the breakdown or liero those are one Mar PCS um built from the called tensor based IOP which uh for IOP I'll expand a little bit later so this kind of scheme has really really fast booer which is gracing however um it also has some some

drawback um mainly because it has really expensive proof size and verification time the complexity is about square root n rather than logarithmic so given this there's a thir option that built from the fry so-call fry po nomial low degree testing protocol or righty our PP protocols and uh I will explain a little bit more on how it how it works but uh um at hevo it has the following advantages first it has no expensive cryptography operations as well so there's no elip curve operations on the only operation is just field operation and hash operation which are all amazingly fast and second is transparent

and pl post contant secure and finally this still preserves Pol logarithmic proof size and verification which is Advantage compared to breakdown however it also has its own disadvantages um the first thing that requires the use of so-called fft friendly field because it inherently needs to run ffts fft friendly means that it has some like uh large multiplicative subgroup that is a order of power of two or power of three for example and and we do know that there exist some other work which is the very elegant work that get rid of these constraints so you can do fft even without fft friendly field however this

construction is not that concretely efficient and also in the in the setting of building a PCS the syntic complexity also has some log log logarithmic factor of loss that's the first disadvantage the second advant disadvantage is that in this PR based Mark PCS it's actually goes through several compilation step or transformation step from the original fry into the final PCs For example you need to transform fry into a univ PCS first and then transform univ PCS into mtiv PCS so this compilation has an extra overhead which makes the PCS less efficient hence our question are the following um first can we have now a fry

like IPP but doesn't require the fft friendly field and this is what we call the field agnostic and second is whether we can have a more direct compilation from the IOP to a Martin PCS that doesn't need to go through these many Transformations which has extra overhead the answer is of course yes and before I presenting our contribution let me highlight why we really care about this field agnostic and this will Echo with my um T Direction I mentioned before so with the flexibility of choosing the field first we can in the front end side we can avoid those non-native field simulation in the circuits and uh for example a typical

application will be the ecdss scens verification circuit in which the curves will use some field that's toally not fft friendly so suppose you only can use the algebra relation statements over ft friendly field then you have to like translate this all this uh operation over a different fi into this fft friendly Feud which is super expensive you need to do a lot of constraint to just simulate one operations so with the flexibility of choosing a field you will will never have nonnative field simulation and this will be a great saving on transforming a circuit statements into an algebraic relation

statement and the second Advantage here is that with field agnostic we can use those field that has the most efficient CPU and hardware implementations for example typical example including meren fit and baby bear fit which are super fast in CPU and Hardware but they are not fft friendly uh I guess I I'll take questions for now any questions right now okay cool yeah okay great so I can I'll continue then um so our main contribution is following so first we generalize this fry RPP and or fry low degree testing protocol that only

support resol and codes into a more General IPP that can work for all the so-called foldable linear code which we will introduce later and second we construct a new foldable code like free Solon code is a special case of foldable code but we construct a new foldable code that can support any field which resment code doesn't uh quite satisfy and this any field this is a there's still some minimal requirements on the field but uh I think that's minimal and it's not a big deal and finally given this uh generalized RPP we have a really lightweight uh compilation into a marity PCS which uh use Su check and overhead

is minimal on Su check side and on the other hand if you instantiate this IOP with some U field agnostic foldable codes then the resulting Martin P s is also fit agnostic so it's obvious to see that this advant advantage of this construction is that now is supposed almost arbitrary fuse not only fft friendly fi and second there's no longer a Univar to multivar compilation overheads uh which is another kind of saving and this uh this saving the second saving works for arbitrary field for example even if you use resm code you can still enjoy this kind of advantage and finally preserves other efficiency advantages of the fry

RPP and we also know there are several related work um and that's also generalize our P for other type of codes like polinomial code algebraic geometry code and it would be a very interesting open question to see if we can unify this framework into a one General framework okay the agenda of the talk will be following um first I'll explain how to generalize R RPP to support them br the class of codes and second I'll explain how to construct a new photable code that can work for almost arbitrary field and finally I will give an an explanation on how to compile this IOP into a Maring PCS okay so let's start with the first

part uh as I said before I I mention a lot of times of IPP but you may not familiar with what IOP is so to give an a bit context IOP stands for interactive or orle proofs of pro proximity proximity and the goal of it is to try to um say we have a Oracle string which can be quite quite large and the goal here is to for the Prov to convince the verifile that this orle string is close to some code word okay for example in the resol code setting or in the fry setting the key the question here will be try to check that this Oracle is close to the uh is is the evaluation of some low degree polinomial and usually the format of IPP will be

follows so you involves several rounds of interaction and in each interaction in in run the approver will send some Oracle some other Oracle strings and verifi reply with some challenges and then adaptively the prover will send some other challenges in the next R and so on and finally the verifier can carry some entry uh of these oracles and get the answer of these entries basically just and get the values of certain index of this oracles and after that the verify will output yes or no and we requireed to satisfy sever property versus completeness means that if this Oracle string Pi is indeed a code code word and if the Prov is honest

then he should always pass the verification and second if this Pi is Far From Any code words then uh the verifile has to be no matter what proofer does the verifile will output reject with some hyper probability what this probability is proportional to the distance between pi and and any code words so that's why also the minimum relative distance of this code word also plays a role here because that's determines the bond of the soundless error and finally the complexity is measured by both the computational time of Prov and verifile as well as the number of queres made by the verifile and Fry RPP just one particular

instantiation uh that particularly works for reolon code or or univer pooms so here the Oracle string would be the evaluations of some polinomial f um that's evaluated at the theand L for example you can understand L as something like the set of two to the n's roots of unities and here the goal is to check this Oracle string is a real Solem code word meaning that it is a it is the evaluations for some low degreee polinomial like for the for example here the degree should be less than 2 K an idea of R is falling well given this polinomial F we can decompose it into two parts so we can collect the

coefficients for those even degree monomials into a polinomial f x² here and collect the coefficient for those all degree monomials into FX s here so you can rewrite FX as FX squ plus x * FX s and then after receiving a random Challenge from a verifile the pro will fot this Fe polinomial and fo polinomial using this random challenge C1 and then he run the resol encoding and send the encoding or the set of evaluations as the second Oracle and send it to the verifile so why we want to do this the great feature of this round of

communication is that we have reduced original problem into a similar problem but with one smaller Dimension before want to check an oracle should be close to a code word like should should be close to a code word such that the message is a a poomi of degree less than to DEC and now it turns out that if Prov is honest and it does the folding operation correctly this new Oracle uh should be a for this new Oracle should be an encoding for polinomial with degree less than 2 to the K minus one and here the demand L1 is also half of the demand L you can understand as the set of two the N minus one root of

unities so now we reduce the original problem into one similar problem that has one smaller Dimension and we can do this again and again right basically and finally after login runs we want need to check that this Oracle is a constant polinomial for which the verifier can very easy to check you check that is constant pomal but at this point I'm missing one things um is that I assume that Pro is honest so he will always do the folding operation of this FX plus C1 Foo correctly and honestly and send the Oracle to the verifile but that might not be the case of if the pro is malicious he might be able to just send some junk polinomial in the this

intermediate runs right so that's why we need another uh procedure to detect this kind of malicious behavior that's called consistency check we the verifile we example some random index on this original big demand L and from this index youu you derive also other index to be checked on the intermediate oracles and then we check that for each adjacent two Oracles in the adjacent two runs the Oracle are consistent with each other and how to check the consistency mainly we are checking if folding operation are correct with respect to this PO with respect to this entry and the entry in the previous article so we want to check that this F is equal to Fe

plus C C C Foo and uh the question is what is exactly Fe and fo here how do you check that and this will come up back to this uh decomposition formula we had before so given this decomposition formula we know that this value can be interpreted uh interpretate given the previous Oracle by just square roots okay so this is the main idea any questions so far can can you elaborate a bit more on how and why you are doing this interpolation from from the part where you pick this random view I got I got lost so you have been so far trying to

see the proximity between a code work right between code work so now you sample this random U with the goal of what trying to the go to check yeah with the goal to check that for example let's see the example from the relation between F and F1 right we want to make sure that the the first Oracle is consistent with the original Oracle yeah so that means that uh I want to check that fub1 is computed correctly that definitely f1x should be equal to FX plus C1 Fox right and definitely it should be the case that this holds true at a random point right oh I see I see I see I see fair enough fair enough yeah and now Fu and fou can

be recovered from the two values from F because there is is the relation between Fe and fo and F which is this FX equals f x square plus X FX squ so to get the value of f x you only need to get the value of f on Square U and minus Square U so that you can do this uh polinomial interpolation to recover the value of Fe so that you can check that it's consistent with F1 is consistent with f here that's the general idea yeah that makes sense uh thank you and there's also another question the chat which is so you will do this check for each step or just for

a randomly chosen one uh so I would do this check finally so after run all this uh runs the verify will example one index and from this few1 index he'll deterministic derive some other index for other runes and he'll check this consistency for all the runs for all L runs actually together finally Yeah so basically you you real do have a check for each for each in runs for each step but this the the index required are kind of correlated which is also very important for the security analysis yeah do that answer your question so basically also I mean that this U1 is

randomly chosen but all this U2 to UK which are chosen which are checked for the other next oracles are not uniformly are not independently chosen they are correlated to the origional uh index yeah okay sounds good so one of the inherence limitation here is that the this this kind of scheme requires this field to be fft friendly for two reasons first reason is that you need to do resoling coding in each round which involves uh some fft like algorithm and second is that we also require this field this demand L to be quite smooth so that you can quickly go from um the the I demand

l i into the i+ one's demand l i +1 using some very simple algebraic operations and particularly here will be just square or do square roots so these are the two reason that you really need the fft friendly field so natural questions can we generalize Beyond this res solement code and before generalizing is let me explain an alternative understanding of this resoling coding the FR case and that will gives you a flavor on how to generalize it so in Fr setting we are basically using D difference resoling coding scheme well the iing coding is just to is encoding that has massage space of un VAR po nomial of less than 2 to the I and output space will be the

some 2 to the I plus C evaluations on some theand okay and uh we we we can extract some foldable foldability property from this set of resolvement code basically in suppose we want to uh encode A polinomial F of degree to 2 to the k+ one or two to I + one um what we do is that as we said before FX can be un as f BX s + x of o x s and then the result coding is just the evaluation of this polinomial at the set of roots of unities okay which is omega Omega 2 to Omega 2 to I plus C and this is actually can be rewrite written and re like

understand as follows U so I'll explain more what is means so first let me uh prove that argue that this is correct is indeed correct so basically the upper left this blue box here is actually initially what we want is should be the evaluation of f x s right on the demand of Omega Omega 2 Omega 3 and to Omega 2 to the I + C minus one and then you can rewrite this as the evaluation of f x so we replace x squ with X but the points becomes the square right so basically the points becomes Omega Square Omega Force Omega 6 and Omega 2 to the I plus C and you see

here as I said before the demand of l l i and l i+ 1 is exactly a square com relation so this this Omega 2 Omega Force and Omega 2 the I plus C is exactly the demand for the resoling encoding of Fe in the I encoding scheme so you can trust me that indeed this is correct so the upper left hand side is indeed the encoding of Fe On The I res encoding theme and similarly uh this also holds true for RSI Fox and the right hand side so now what you can see is like you can understand this this code words as two parts the concatenation of two parts and the first part is just the some smaller

encoding plus some other smaller encoding head my product a some Vector here and this Vector is just some powers of R of unities and this Vector on the left hand side is slightly different from the right right hand side basically is the left part of the demand L and right part of theand L you has this kind of property so natural question is whether we can generalize this property into an broader class of codes rather than only resment code and that comes to our new notion of this foldable Nar code so similar as before a foldable n code will specify by a list of the encoding scheme and I encoding scheme we have some U message lens to I and block length C * to the

I and it also will specify by this kind of T vectors here we which which will explain a expand a little more so now the followability can be un understand as follows so basically we want to make sure that there exist some structural relation between the i+1 encoding and I encoding scheme and in particular you should like looks like this which is very very familiar with what I said before right so basically everything's the same and except that this T vector and T vectors in the resol case is just those powers of root of unities but here is more General it allows arbitary type of T vectors like the only constraint we have here is just the that for every column J the TJ should not equal

TJ so why we want to have uh this kind of uh description of this property and there's a very intuitive understanding so you can understand that the encoding of ml and encoding F Mr they can be understood as some coefficients the coefficient form of some C * 2 to the I linear pooms or degree one pooms so here each column will correspond to a polinomial here right each column C some coefficient of ink IML and ink IMR and also now you see that this encoding of ml con Mr can be understood as some point evaluation form or or

interpreted form of the C * 2 the i n pooms okay so there there won't be some information loss here and for example consider any column J on the left hand side is just the evaluation of the J's degree one polinomial at points T LJ and similarly the J column on the right hand side is just the evaluation and tij so this is some way for you to understand how we're actually just doing some interpolation or like uh BAS transformation from coefficient form into a evaluation form when you do this followability um so any questions so far so after generalizing the class of

codes you may ask the natural question will be how to generalize this I uh for any for any foldable code for not for only for restall code the idea is actually uh pretty simple so we can just rerun all this logic and proving ideas in Fr our PP again but more generally so record the goal is to check this string is close to some code words and here the particularly our goal to check is close to some code words in this encoding scheme of this foldable code and then what we do is very similar to before what we do is we split this message into two parts ML and Mr and then we encode ML and Mr to get e and er

respectively and and also recall that we have this structure probability uh struct property about followability before so that there exist a relation between p l pi r and this e and eer and after receiving The Challenge from verifile what we do is very very simple we just fold these two encodings of ML and Mr respectively so just it will be just e l * C1 * e r and by the linearity of the codee you see that this new Oracle will be just the encoding of the afforded message which is ml plus C1 Mr okay and suppose Pro is honest and

suppose Pi is inde the code words in CD then you can see this is indeed a code words in CD minus one as well so we can do something similar before by the reduction we reduce some problem into a very similar problem but with one smaller Dimension so it's almost the same as before in Fr PP and similarly we also need to do this consistency check as we mentioned before to detect malicious behavior from prover and here the check is also very very similar well we also example a random index in L and get and check the consistency between the first Oracle Pi 1 and the original Oracle Pi which is um which is basically we want to check that this folding

operation is correct basically Pi 1 U equals e l u plus C1 e Ru at this random Point VI well and because of this foldability property eel and er are actually be able to uh extracted or interpreted given the previous Oracle P so that's the general idea uh and actually pretty simple and we can migrate all the theorems and results and bonds from fry R PP into this new setting okay I guess this is a good time to take question before I jump into the next step so any questions so far I I want to ask uh in regards the

previous slide that we have seen what are we sampling the the challenge upon for like is e and e what we are sampling the challenging the challenge for what how example you mean how do we example this U C1 for example in this case C1 is the random Challenge from is a fi elements from verifile based on PM PR I assume no it's just a uh it's just a random random Challenge from verifi field element is similar to yeah but you I mean ver has something I assume no saying you do F Shamir yeah yeah yeah

exactly oh okay I see so when you do F Shamir what you do is that you have this high or this Oracle here right and you have a large Oracle but in practice you definitely needs to commit it like for example using some merco tree uh to commit it and the approver will send some merco roots for merco commitments to the verifile and we'll do F Shamir from this mirle commitments and generary C1 so basically uh what we do is I verify we generary C1 from the commitment of Pi here okay fair enough okay and uh and the appr where generates pi one which also correspond to another commitment right and verif after receiving this commitment we generates the next challenge C2 in the next run so

this is how it how how we do uh f f sh transform it's almost identical to in the FR setting okay okay does it answer your question yeah yeah yeah completely yeah okay so now we come to uh the second um part which is the randomized photable linear code so I will construct a new randomized photable linear code that is field agnostic and recall that by this property this code is uniquely specified by the base code and these T vectors here well in the resal just powers of roots of unities and here now the question is that how can we set

these TL vectors and TR vectors so that support arital field and still have good relative distance and our construction is embarrassingly simple basically we just choose these T vectors and TR vectors to be some independently random example field elements but I note that the we we we W zample zero we example all the units in this field uh F here and the TR will be just the negative of T and this certainly satisfy this constraint in foldable uh in our F code and the good thing here is that there's almost no restriction we can choose arbitary field and the only con uh only caveat or only constraint here is that

you have to make sure that the field size is relatively large which is related to the minimum distance bound we can get so usually it's fine as lines is larger than 1,000 which is not a big deal and finally we have a trivial recursive encoding algorithm that's trans uh that's due the due this encoding in CIA time with very small con constant so in order to encode ml concat Mr what you do is encode ML and Mr recursively first and then you do this vector addition and HMA product to get the encoding of ml concat M so it's very really really fast in our construction so this is the idea so you may ask why

why we care about it why what's anything novel about this the thing noal about this is that the we need to analyze that it indeed has some really good minimum relative relative distance which is important for the PCS Suess Bond we get and to analyze is um relative distance it suffices to analyze the nonzero Hing ways of any nonzero code words okay because this a for CLA theem in the coding three because the difference of any code words is still code word by linearity so the number of difference of two of two different code words will never be more than the minimum of nonzero Hing weight so now now it suffices to argue that for any

nonzero message the corresponding code word will have very few number of zeros on it and to prove it we'll reuse the property we had before about this uh pability property so the encoding of ml con Mr can be uh represented as this form right basically we have two copies of encoding of ML and two copy of encoding of Mr and in the middle this orange Vector will be this the random t v vectors and trr vectors so in order to analyze how many zeros in this blue uh in this blue string we are consider three cases the first case is that so first we know that there will be some zeros in the coding of ML and in coding

of Mr and the first case is that for such a column that both zero both green and both and the black part are zero so in this part definitely we know that the corresponding blue entry is always zero because 0 plus um A1 a AI * 0 is still zero in the second case is only one of them are zero for example here is 0x here is y z in this case we know that the blue entry will never be a zero will be always non zero and finally we have the last case where both like for some some column both the green entry and gray entry are non zero then in this case we know that the blue entry will be zero on

with probability over one one over F minus one where the random is chosen from this a vectors here right because we as we've seen here this a vector are independently and randomly chosen so that means the number of zero since blue shaded area will follow some Bly transformation with parameter around one / f so now this gives us way to analyze how many zeros are here so supposed by induction hypothesis we already have have some Bond about the I coding scheme and we know that for the iing coding scheme all nonzero code words we have at most L Zer on it then we know the number of R zeros will never be more than 2 L right so given that we know the

probability that this blue encoding have two more than two L plus Delta zeros will be very the probability will be very very small so long as we said Delta to be large enough and we need this probability to be negligible so at this point we know we have a bond on this number of zeros for a certain fixed message ml con CMR however what we want is a bond for arbitrary nonzero code words right so that's why we also need to take a union Bond over all possible messages so this probability needs to be multiplied by a really large factor which is really really bad because that means we have to choose a really large Delta in order to

make it negligible so given this we want to have a more tighter bound the observation here is that in the previous estimates we have a really loose Bond on on the number of red zeros in the first case because for many cases actually we know that encoding of ML and encoding Mr they have significantly fewer number of zeros than L because L is just a worst case bond in the iing coding scheme so therefore our idea is the following so we want to have a more f estimate on the number of resid here so for any message we'll Define a maximal set S as the set s which is a subset of C *

2dii or the subset of the block such that the encoding of ml as well as the encoding of Mr on this subset s should all be zeros and also this s should be maximal okay so this is exactly the a very very precise um description for the first case so basically the number of red zeros in this case is exactly two * s right therefore we can uh because we have an the number of resid the bond is 2 s rather than 2 L we can have Mar sharp bond for the number of zeros in the encoding of ml conc Mr which is described here basically we have a much

much smaller bound which is because of this red terms 2 * L minus s here so now can have a union Bond now the idea is to do separate Union bond for each category of s so for every s we will have some message to satisfy this maximum set requirements and we'll multiply this with the bond we had before so this reduce the question to check how many Cod words are here such that they are all zero on subset s and we want to have arer bound on this uh on on this and the idea to prove it is not very hard so we consider two cases the first case is that the subset is has

a size that's larger or equal than L and by the induction hypothesis we had before we already proved that all nonzero code words in the previous encoding scheme will never have more than L zeros right so that means that that's the the only code word that satisfy this is will be only zero code words so there won't be more than one uh code words in inside this case and more interesting case is when this subset s is less the size of it is less than L and in this case we can reduce to the first case the idea is following so given a message M the map to the encoding of M on subset s is exactly some Matrix map right because we know uh

linear code can be understood as some matrix multiplication on the message so this correspond to some Matrix map G here and to argue how many message are here that maps to all zeros it basically reduce to check how many message are here in the kernel of this Matrix map and to analyze this we can consider a superet of s say S Prime where S Prime will contains s and the size of S Prime is exactly L and as we proved before for all those cases that has size larger or equal than L the kernel of it will be zero right only single elements will be there in the kernel and also because G

are just some subset of columns of G Prime basically uh is G is just a g Prime deleted some L minus s Columns of it so that means the kernel of G will have uh like the rank of Kernel of G will be less than or equal than L minus s so you will be some Vector space with rank about um L minus s so the number of element m in this Vector Space by some rank lity serum can be bounded so the number of message here will be no more than F to the L minus s this for this we get we have a upper bound on a number of message that has encoding to all Zer on subset

s and now we can do the union Bond again and it turns out the final bond is very very good and the final Bond we get is almost the same as the bond we get in the previous naive analysis without the union bound and this is the Delta we get here okay so this finished to prove why it has a really good relative distance so any questions so far yeah I I have a question on that how do you fix the parameters uh the parameter C how do you pick it or does it come like from uh parameter C you mean yeah c yeah exactly C * yeah so the C is just the uh the rate of the of this encoding right

oh enough yeah yeah yeah okay okay okay it's just the encoding scheme you have message space you have a uh you have a uh you have a block space and you make yeah your school points that you have to make C larg enough so that's uh uh like you have enough space for for arrows so you do the C is kind of uh uh how do you say is usually what what we pick like in our in our station usually is just eight or four I think it's more than should be definitely more than four uh but I think Eight is Enough okay I see that makes sense thank you than you okay so um finally let me uh go

through the last step so we have this space for IOP let's see how we can uh transform into Martin PCS so recall the notion of polinomial commitment scheme so in the Pol Comm scheme after generating parameters in a setup phase for some polinomial size Bond the prover given some Martin polinomial of the different variables um it will be able to generat a short string committing to this polinomial here by Martin linear polinomial I mean the is a polinomial with multiple variables and the degree of each variable is less or equal than one and as a commitment scheme definitely have to satisfy The Binding property and hiding property and I'll

focus on binding here which means that it is invasible for the prover to generat two different V uh pols that commit to the Sam string CF and later in the evaluation phase as a polinomial commitment scheme we should also be able to generate a proof or convincingly verifile that the the CF is the commitment of some pomal f such that F evaluated at some point Z equals y and to do this the pro should be able to generate some proof which is a proof of knowledge meaning that suppos the verify accept there must be the case the prover knows some witness polinomial that maps to this evaluation that satisfy this

evaluation statement so in the Martin setting we do have several constructions for it that has relatively fast approver uh which I also mentioned a a little bit before so we have this FR transformation one we starting with some fry rppp we can transform using the coent trick into univer PCS then we can transform into Martin PCS using some other transformation and examples includes the gini hyper plong and zero moth they all explain and describe some kind of transformation here the advantage here is that it has relatively fast verifile and a relatively small proof size which is usually hundreds of kilobytes it's is not very very small

but uh it's still much smaller compared to breakdown which is like several megabytes or tens of megabytes size and the drawback as we said before is not field agnostic in requires to use fft friendly field the second approach is this breakdown approach which compil some so-called tens into Mar PCS the advantages has really fast Pro and the field agnostic however and the verifile and the proof size is really really uh expensive so our construction is a third option well we can build based on any ipps for this foldable code and Inter leave it with a s check and then we can obtain a new marke PCS and because the

sound check is super efficient uh the overhead is almost negligible compared to the complexity of IPP itself so the advantages is the first it can be made Feld agnostic if we use some feeld agnostic foldable codes and second we don't have any expensive transformation step anymore so it's a also a significant Pro Improvement and finally compare to breakdown we still preserves logarithmic verification and proof size so the construction is actually pretty simple so suppose we are given a polinomial f which is a minear polinomial and we order the coefficients of this Marine polinomial according to a

vector and the commitments of uh f is basically the encoding of this F Vector uh and make it's exactly the Merle commitment of this encoding of f Vector so basically what we do is that we build a merco tree and a leaves are exactly the foldable code for this message uh F Vector here and the M Roots will be our PCS commitments and then in the evaluation proof space in order to convince the verifile that c is the mer commitment for some polinomial f such that F evaluates at Point Z equals s our idea is that we will transform this evaluation statement FZ equals s into a

su check Clan so it's by this Fork martinal extension theorem we can EV represent the evaluation of Martin polinomial at the point Z as the sum of as the interpolation of many of the this of all the evaluations on the booing hyper Cube so basically you can rewrite FZ where Z is outside booing hyper Cube to be the sum of f uh FX times e EQ ZX well X is enumerated over the buing hyper q and this EQ ZX polinomial is this interpolated polinomial you can understand it as the like range polinomial in the Martin in case okay so now we have transformed this evaluation

statement into a s check clim and we have a very efficient and famous protocol for proving S Check clams right so the goal is to convince that given some Oracle F we want to prove that sum of evaluational f of f is exactly some claim value s now eily what you can do you can let the verifile to carry F on all the points in the booing hyper cube right um but that's really really inefficient because the verifier needs to querry two Tod entries of f but this protocol is a protocol that allows you to only make one query which is super efficient the idea is following in the in the first round the Prov will send a unit polinomial HDX which is the sum of 2 to

the D minus one univ pooms which is fbx here and if this HDX is correctly computed and equals the right hand side then it reduce to the check of hd0 plus HD1 equals s right so this original sumra clam is equivalent to this two this clam about the sum of hd0 plus HD1 and after that the verify of this check the verify reduced to to check that the prover is indeed sending the correct polinomial right it might be possible that prover is sending some junk polinomial HDX that doesn't equals right hand side but by the zip Lama we know that if HDX doesn't equal to the right hand side then with overwhelming

probability of some random challenge the sum won't be equal the evaluation sum evaluation the evaluation on the left hand side won't be equal to the evaluation on the right hand side so now it reduce the original task into a new task to check that this new S Check clam holds true which has Dimension D minus one rather than D so we can do this again and again and again and finally reduce to one small sum check which has Dimension zero which is basically just checking this single value equals H1 R1 and this single value can be made can be carried by verifile um using single quy to F so this is the idea of sum check and after having this background we can

go back to our goal of doing evaluation proof so you see here that this actually there's a tiny tiny but also subtle difference on the task in our case so basically for now even though some check uh works but finally still needs to make one query to this committed Oracle F right so finally when you want to check f equals H1 R1 how do you make sure the F value is exactly what we want so basically it seems that at first glance we are just transforming a arbitrary evaluation query to a random evaluation query to the PCS on the random points R1 to Rd so doesn't seem to give any um any advantages here right so we still need to reun this PCS proof

but the key Point here is that this R1 to Rd are some random challenges that we can exploit we can use so our ideas is to use this random challenges as has the random challenge in the IOP as well so record IOP after receiving some challenge Rd we'll do this folding and we can order the vector of f in a way so that the left hand side the message left hand side F L are the co are the coefficients of those monomials in the mar mar polinomial that has no term about XD and the right hand side are those monomials that has term about XD so the folding will be exactly FX L plus rdf r and if you look more closely it

will be exactly the coefficients of this partial polinomial FX1 XD minus one and RD and this is exactly the polinomial used in this new reduced sck claim so that means we we similarly have a transformation and reduction as before where initially we have some uh evaluation Claim about some D Dimension D pooms now we transform to a um like evaluation CL about Dimension D minus one pooms so we can do this again and again and finally we'll come to the last case where we want to check that um the evaluation Claim about a zero Dimension polinomial which is that

I want to check that H1 R1 equals some F0 * EQ ZR well F0 I want to check this F0 is consistent with Oracle in pi Z and this is very very easy to check either the verifier can decode this Oracle Pi Z or the prover can send the message underlying this encoding and verify check that encoding is consistent with pi Z and that's finish our proof and also as we have mentioned before the prover might need to might send some junk polinomial in the middle so that's why we also need to use this consistency check which is already covered by the IOP verification case right so we will do this check in IOP verif verification

phase and used to detect any malicious behavior and if malicious behavior doesn't uh happen then we know that okay this is exactly the value we want so the intuitively this is a very very simple construction but turns out that U the proof for knowledge sness and evaluation binding are much more non-trivial to prove uh for time reason I guess if if the audience has has interest we can talk more about how to prove it but I think I'll skip this here because it's not that uh important but if audience has any interest I I can go through later okay so that's the idea of the

Martin PCS construction and which is super super efficient basically just uh you just have an IOP and Inter Lea with arra efficient S Check and you are done so this is is our main contribution in summary we have made three main contribution first we have generalized the fry RPP that it can now work for any so-called phable n code for which the resol code is just a special case and second we construct a new photable n code that has fast encoding and is also F diagnostic finally we have a efficient compil compilation from base for IOP or generalized IPP for vable codes in

margin un PCS by intering it with a su check and the complexity of this margin PCS is almost identical to complexity of IPP okay so that's it and there are also several interesting open questions so first is that you see that our our foldable code is still C linear has still has a c linear or an O login and log and pro time so it's an interesting question whether we can have a linear time encodable for the code and the impact of it is actually really really significant because the only places in our PCS that has a CA in linear complexity is exactly the encoding of

affordable code suppose we have linear time encodable code then that implies that the PCS we have is also linear time which is a great breakthrough because now that implies that snark itself is linear time so is this is a really really uh challenging but also very very useful and interesting open questions the second open question is that whether we can have a foldable code that has the maximum possible relative distance but also is fi agnostic so first for the resment code we do have this maximal relative distance property but it's not F agnostic while our random code construction even though it has good minimum distance it still not far from

optimal but it's F agnostic but it's a open question whether we can achieve both re the best of both words and finally uh we can generalize this uh the finally the question is whether we can generalize this IOP to a broader class of codes like for example unified the framework of the all those related work and also uh there's some new work called beus which uh allows you to commit some polinomial that has two small coefficients like like field of size two and it will be a great open question to check whether it can be this trick can be combined with that trick to uh have commitment scheme that's super efficient

for those polinomial that has really small coefficients and finally is that whether we can have a better PCI soundness proof uh I think that's it uh and now I'm happy to take uh even more questions so first of all thank you very much B for your for your timeing for the explanation I have two questions um one of them is related to uh if I understood correctly you are using the elements that you get within the intermediate rounds of the S protocol like all of these uh challenges let's say and you reusing those for the split of the polinomial uh that you

explained at the beginning of the presentation the one that has the coefficients it's mostly for folding uh let me see it's fry here so you saying here yeah exactly so here C1 is used to fold these two Fe polinomial and fo polinomial here so C1 is a scalar so that's after folding because fex and FX all both have lower degree and after folding you have a you also have a lower degree polinomial can you uh can you elaborates on your questions yeah so did I assume

correctly that the C1 that I see here uh it's basically coming from the S check that you have previously performed and you oh you are saying in the mark construction exactly yeah are you like reusing these things such that you okay okay okay okay exactly exactly and this is this what then complicates more the the the knowledge soundness and the security proof okay I guess it will be nice if I can explain to you why it is complicated uh yeah so this is a really great question and that's one of the reason why the complicated because you are reusing this challenge here right and uh and as we see before that so to argue this The Binding property meaning

that if if the protocol passes then there exist some unique polinomial F such as some clam H um so so I want to argue that this surack clam HS basically the sum of f ZX is is equal to S and that is implied by the final evaluation clim about F right basically I want to know that FZ f z r is exactly the value I want to get from F right yeah that's cor so so basically I want to make sure that for the last Oracle Pi Z Pi zero is exactly the encoding of FR okay oh okay and this is not guaranteed uh by IOP even if you are

reusing this random challenge because IOP only tells us that every oracles is close to code words you not it's not going to give us a guarantee that it's always close to the same code words right yeah yeah yeah yeah so the the question is why do we know the last Oracle sent by the prover in the last round exactly consistent with the first Oracle the original oracles s by the by by the prover which is the commitment of polinomial right so we have to prove this and in order to prove this the idea is that in each intermediate runs the Oracle sent by the prover should always be close to code wordss which is the property by the IOP and supposed for contradiction that the pro switch from

one polinomial to a different polinomial at the end then we can reach some contradiction using this consisten check because that means there exist some R before this r the prover is is sending some Oracle that close to the polinomial F to the partial polinomial of F and after this run is sending some polinomial close to some other different polinomial G but we can argue that the Oracle will be close to both code words and this reach some contradiction uh so that uh so that we can argue that we can guarantee that uh that this last article is exactly the same is exactly the encoding of f r where R is using is

is a Oracle is a random challenge exactly used in the in the Su check so if you if you do this sequentially then the analysis will be very very simple but when you do this sequentially you go back to a circle right and as you said be here is because we really reuse this random challenge in both IOP and some check and this makes this analysis more involved as you said because we need to argue that finally the the last Oracle exactly consistent with the evaluation of f on this random challenge R which is not that easy to prove and is that is that worth it in the sense of what are you saving up at the end you are saving up hashing I assume right you're assuming

duplicating hashing or doing twice as many hashing as you were doing uh I'm saving I'm actually not it's not a pro it's not a problem about saving it's a problem of feasibility so if you do it sequentially okay let's say you do this sequentially you don't you don't do it um like in parallel then after running this Su check you reduce to a new PCS evaluation um f evaluation quy uh problem right and then you need to generate a new PCS evalation proof and you go back to a circle you can never do this sequentially yeah because you can go after going this circle you you transform to a random evaluation query and you run this again some again

you run you come to another PCS evion Cy you will never go into an end you can that means you can never generate a PCS evaluation proof so it's basically if you don't do this inter living you basically cannot have the PCS evaluation proof so it's it's not only about efficiency it's about feasibility you can only achieve it you can only achieve it only when you do this inter leing yeah wow okay that's really curious okay okay and the the other question that I had is um is there any way to although you want to be fi agnostic choose the T parameters on a smarter way that it's not just negating one uh negating the

previous one such that you get better uh distance uh properties I mean you I don't know if that influences or not it might not have anything to do with it but can you like is it just just okay to negate uh T to get TI or can you do it like on a much smarter way uh such that you get better properties for the entire scheme yeah it's totally possible it's just the we didn't find any like um like any approach that can improve like impr improve it further and this is the most natural way we have think because Randomness is is a really a great power

powerful tool and as you said maybe there's some really structural way to build a TR rather than just do NE negates that allows us to have a really better Bond um that's good point but I I haven't thought really deeply about this yet and uh yeah I maybe yeah maybe there's some way but uh I haven't figured out like if you do this what would be the corresponding analysis of minimal distance but that's a really interesting question and definitely I think it's possible but I have just just I haven't s really really deeply about it yet yeah okay that's fair because you are I mean you can only count with the properties of a field I assume right if you want to be agnostic so there's a very limited amount of operations that

you can do and very limited amount of assumptions that you have so okay thank you very much thank you yeah are there any are there any other questions uh I don't see anything in the chat okay have a question um so like regarding the Quasi lanar ver verification time so uh verification time is not cing in it's Pro time proof size the pro okay I guess my question is so generally uh how people resolve like the size of I of of fry is that they do recursion right uh so that we compress that into like a constant size proof and um now that you

compile fry into multilinear PCS um you have any comments on recursion like do we still have same tool toolbox to solve this quasy linear issue so that we can p put the proof on chain uh so first I want to clarify this cost I think what you means logarithmic right yeah yeah yeah sorry not C it's logarithmic okay logarithm yeah yeah and uh uh and second yeah I I think the the the this recursion trick will still be able to use in our setting basically you can still still do this recursion of this logarithmic size proof in base fold and do do the recursion to make it constant size it still works and why we why we

don't consider about recursion here is that we want to make a fail comparison right because everything can do recursion but the key key here is that we don't want to do recursion now because recursion really adds a lot of overhead on the pro side as well and this overhead is dependent on the size of the proof as well right so basically for example if you do recursion on Fry uh is much much cheaper than do recursion on breakdown right because breakdown has a really really large proof size and the verification cost is also larger so the corresponding recursion overhead is also larger so here the key key question is whether we can have a scheme that before recursion

is already very efficient and also has a relatively small uh verification cost and that means when you really want to do recursion the overhead can be relatively small so that's that's the principle and philosophy here so in summary first our our trick and our construction as similar can be extended similarly as as we do for FR PCS that we can do recursion and the second that we don't consider recursion is because we don't want to add overhead on the pro time so in some in some applications we the proof size and verification is fun uh for some hundreds of kilobytes appr proov size then definitely the best way

is not to do recursion right because we want to optimize the pro time but if you you cannot afford to have a 100 kiloby Proof then you are right maybe we should do recursion and the reason that we can still preserve a logarithmic verification cost is something helping you to do recursion uh compared to to those scheme that has really really large proof size right so it's a is a Improvement on recursion um comparing to at least Lao and breakdown yes so if you want to do recursion then definitely it's better than I think that definitely better than than breakdown and uh the recursion overhead is similar to fry I think and

compared to fry is field agnostic right which is another great saving yeah okay makes sense okay cool thanks okay so are there any other questions okay I will assume not so B thank you very much for for coming and explaining uh thank that well this entire protocol uh I will upload the recording as as soon as I can and yeah as always it's a pleasure to have you with us uh it was it was really nice being here so once again thank you so much and have a nice day yeah you have a nice