ZK Hack SPLA Study Group – Session #3

Transcript

and in this lecture we're going to be talking about um kind of I think a lot of people mentioned an interest in this but this is um talking about how we can understand fry uh the fast reach Solomon inclusion I think is the the you know if you if you expand that adjective I think that's what it expands to um how it relates to the framework that we've representing previously so around you know how we can understand it from a purely linear algebraic perspective without much reference to polinomial or things like that unfortunately at the end of the day there are many tricks that fry uses in order to kind of get a sucin proof scheme that do depend on these facts about pols but they can

be just essentially distended or or carefully kind of pulled apart from the underlying protocol which actually is completely independent of those tricks but to get a practical protocol you have to use some of these like slightly more Advanced Techniques which give you a little bit more structure okay so but to do that we have to discuss something which we only vaguely mentioned previously which is Vector subspaces and specifically the subru the structure of vector subspaces so um okay I'll get to that but so this this one will be distinguished from the past two talks so in the first session we went through mostly math the second section the second session we went through a number

of tools that we you know kind of appear a lot uh in this session we're actually going to go through a specific protocol and we're going to introduce just the things required to kind of understand it at a high level unfortunately it turns out I tried my best but it's actually quite difficult still to come up with a full fully contained set of slides that is accessible to everybody uh for how to understand fry and and a simple proof so if you're interested in the actual proof of how all of this works I would recommend going to the paper um I will skip through some small details around the exact mechanics of things around finite fields which turns out to be required for this um but those are also in the paper but here we'll understand at a very high level uh not just at a very high level actually at a

much deeper level than I think many tutorials on it will go but we will not understanding quite yet at the deep enough level uh to be able to prove it security just from the slides so but again this this should set you up very nicely to go read the paper and understand the the structure of the argument and just be able to to prove it the proof is not particularly hard and none of it is particularly you know difficult in a lot of ways but but it is involved like it does involve details that are that are important okay so let's go through an overview what we're going to go through today and then we're going to rehash a little bit of vector subspaces and then we're going to do two things which is we're gonna introduce a kind of an exact version of fry I think is the is the best way I'm G

to put it uh and then we're g to see how we can generalize that slightly to kind of an inexact or sparse version um of of fry that will actually is is actually the the true protocol itself um so that's the high Lev structure the exact version would be easier to understand for a lot of kind of annoying mechanical reasons um and but that'll give you a good high level structure to understand the actual General check and how it actually operates but to do that we have to talk about Vector sub spaces so how these things are structured and why we care about them okay so as I mentioned before we've already studied kind of all the main tools necessary to understand this protocol and most of the major checks right that people kind of use in

um in kind of as as the basis of a lot of Z knowledge protocols so uh these were both done partially via homework one of which I have not released yet but which I will hopefully soon uh and also lecture so now we're this this lecture is actually doing something quite quite real with them um we're g to start with you know a bunch of little disperate tools like little Hammers and nails and things like that and actually put them together to build some tiny little structure that's hopefully useful to understanding kind of some of these more complicated protocols more broadly so the main idea as I mentioned before be to understand fry its construction and kind of how one can think about it very naturally how we begin with something that is you know if you just look at the protocol itself it

feels very magical but if you begin from kind of the linear algebra perspective and you just slowly relax it to fit this General framework it turns out that the the notion of how one might perform this check arises actually quite naturally uh it doesn't require kind of all the individual pieces that come together for you to understand the high level structure of the of the check so unfortunately it because we're discussing a specific protocol we're going to need some specific setup that uh is you know related intimately with the protocol itself so unlike the previous tools that you've discussed that are very generic here we're actually going to need a little bit more structure uh that is going to be we're going to use only for this protocol rather than for kind of being able to

say hey here's a thing that holds generically for a lot of things and the main tool that we're going to use is the fact that a vector space or a vector Subspace recursively decomposes so in some sense we can think of it as as a ntion of self-similarity I'll discuss exactly what this means in this slides but the point is we can think about a vector space as being composed of like two Vector spaces which are Each of which are smaller and smaller in some sense that's very practical such that we want if we want to verify something about the big vector space we can verify a smaller fact that's easier to verify of the two smaller Vector spaces right and if it happens to if this decomposition happens to do so recursively so in particular if the big Vector space decomposes into two smaller Vector spaces and those two

smaller Vector spaces decompose themselves into even smaller Vector spaces then you can just imagine applying this construction recursively and if we get a constant time a constant amount of savings at each step then at the end of the day we get an exponential amount of savings uh by going down down this tree as opposed to kind of you know try and verify the claim over the original space okay so much in the similar way of the structure of the previous set of uh lectur so the previous session which is we start with the exact case and then move to the exact case uh we're going to do the same thing here so we're gonna start with some notion of a protocol that kind of looks like fory that in this exact case and then we're going to relax it to the case where we don't care

about something being exactly in a vector space but we only care about being close to a certain Vector space okay so quickly let's go over vector subspaces and let's actually talk about what it means to be to have structure so what is a structure that we require out of these vector subspaces and again I'm actually St at the chat this time as well so please feel free to ask questions in the chat and I'll try to answer those as I go okay so let's start again with the Subspace so if you recall a sub sub space uh we're going to call it V here is simply a set uh and that set has the following property if you take any two

vectors from that set and you add them together they are also in the set and if you take any Vector from the set from the subp space and you scale it by any number then that is also in the set itself okay so we're going to have three subspaces here so one of them is going to be V and then V Prime and then V prime prime and they're all going to be part of the same they're all subspaces of nend dimensional vectors and we're going to say that V decomposes into the two Vector subspaces if for every Vector X that lies in this Vector Subspace um that Vector actually equals the sum of the two of two vectors one of which is in V

Prime and one of which is in V prime prime so Parts this quite carefully right what we're saying is uh we take a vector in x right or sorry we take a vector X which is in v and then any Vector that in in that space so X any X can be written as a sum of two vectors one of which is in V Prime and one of which is in V prime prime right and so ideally if some if by some intuitive way these Vector spaces are smaller right and and we'll we'll say what smaller means in a second but in some ways if these things are smaller than you know the original Vector space V then we've kind of we can kind of check something that is individually

smaller right we can check that Y is in v and Z is in B prime prime in order to check that X itself is the sum of those two vectors belongs in the original space and as a notion of notational convenience we write that as capital V equals V prime plus b prime prime so this is called the mowy Su up sets I wouldn't worry too much about it for now just think of it as I've defined the notation such that the bottom thing is true if and only if the top thing is true so V equals V plus V prime plus v prime prime uh if and only if you know for every Vector in V we can write it as a sum of two vectors one of which is in V Prime and one of which is in V prime prime so that that'll be the the

finished notation and that's called the manowski sum if you're if you're interested okay so the simplest example is the following okay let V be the set of all two vectors so these are vectors with two entries that's pretty simple um here's here's a simple way it decomposes uh and decomposes two subspaces one of which is the set of all vectors whose first entry is nonzero and then the second of which is the set of all vectors whose second entry is non zero right uh that's kind of a silly decomposition all we're saying is okay like uh a vector with two elements decomposes in two vectors of one element each right and then of course summing those gives you the set of all vectors of two

elements okay so that's a that's a very simple example but but the point is kind of at a high level it's this has a structure which is we take a thing right which is of you know two Dimension two right and we reduce into the sum of two things that are Dimension one that's the the like high level idea okay here's a more complicated example which we're actually going to use uh throughout this and and it's going to sound really deep when I formulate it this way I the next slide will show you that it's actually really not that deep of a statement um but or at least it's not that complicated of statement it's a deep statement but it's not that hard to understand so okay so from before if you remember from homework one uh we're going the space of read Solomon code words V which is

defined as a set of pols of degree less than or equal to n minus one um it's a vector of which you take that polinom and you evaluate it at a bunch of fixed points so these are called the evaluation points and we call those alpha 1 through Alpha that's a vector space if you recall from homework one um and so specifically we're going to call that Vector space capital V and that Vector space Also itself has this kind of um you know structure that decomposes very nicely so uh sorry here's a lot of text in the page and I apologize but we'll I'll give you a more clear description of what this means but if we Define the following two subspaces so V Prime is uh again the polinomial

evaluations except here's the following thing the polinomial only has even Powers so uh it only has the powers you know X 0 x^2 x 4th x 6 and so on and so forth and the degree is less than or equal to n minus one right that's so the evaluations of those types of pols are going to be uh are going to make a vector space V Prime and you should verify that it's a vector space it's it's clear that it's a reasonable thing to talk about it's just not clear that it's a vector space so that'll be a homework exercise um and then we have a second Vector space which is the same thing so the evaluation of a polinomial f uh over the same points except that it only has the odd power so it only has the powers of you know X the 1 x the 3 x

the 5th and so on and so forth all of degree less than or equal to minus one um then in that case the vector space V of all pols of degree less than or equal 10 minus one evaluated on Alpha 1 through Alpha m is actually equal to the sum of the even powers of those pooms less than or equal to nus one and the odd powers of Po one okay so uh take a second to kind of take this in this is going to be very important structure that we're going to use throughout but um at a high level it's kind of not a just if it seems too complicated it's not that hard of to save it and we're going to see why in a second so here's the idea let's let N be

even just for for now okay and of course uh a polinomial evaluated at Alpha what is that well that's you know the coefficients of a polinomial which we're going to call X right and it's going to be the first coefficient times 1 plus the second coefficient times Alpha plus the third coefficient times Alpha squ plus so on and so forth until the last coefficient times Alpha to the N minus one okay so if you can see right I have the following things are are outlined here um X1 * 1 that can be written as X1 time Alpha to the 0o right and X3 * Alpha squ can be written is is another even term right so X to the0 is an even power of X of sorry

Alpha to the zero is an even power of alpha um Alpha squ is an even power of Alpha and so on and so forth so those are the even powers of f of some polinomial and similarly we can do the same thing with the odd Powers which are here in red right so we have X2 * Alpha plus X4 * Alpha cubed and so on and so forth all the way to the last entry okay so in this sense of course a polinomial could be written as the sum of its even powers and the sum of its odd Powers right and so we can rewrite in the following way we just let's just rearrange the polinomial into two sections one of which is the even powers and one of which is the odd Powers um and of course you know from here right

that the first set of terms is exactly equivalent to the vector space V Prime here that we have and the second term is equal to the space b prime prime right so the point is it's not a deep statement uh or at least it's not a difficult statement that you can take a polinomial and divide it into its even and odd powers and have something and those even Powers those odd powers are themselves Vector spaces that are reasonable to consider okay so that's addition of decomposition we're going to talk about a notion of kind of recursive decomposition I don't have a better term for this so if anyone does I'm happy to take it uh but it's just a term that's made up it's called it recursive decomposition um which is okay so the first observation for this

is if we have a vector space V and some Matrix T which is consistent so in particular T is going to map um n vectors into M vectors and the vector space V is a vector space of n vectors okay such that the idea is if we pick an element of v and multiply T by that element um then we get an M Vector out okay the F thing is also a vector space t times every element of V aggregated into one set right and that's just what I defined here so that's also a vector space um this is going to be a homework problem

but um okay and the idea is we're going to say a Subspace recursively decomposes in the follow if if it satisfies the following property if there are matrices T1 and T2 both of the same dimensions such that V equals T1 * a vector space V prime plus T2 * the same Vector space V Prime and specifically the point is that the vector space between uh you know in front of T1 and T2 are actually identical so they are the same Vector space this is this is the notion of recursive decomposition that we're going to use um okay

so here's this you know it turns out the first example that we gave actually also satisfies this structure and this is pretty easy to see um if you think about it right the vector space of all two vectors right is simply the same as saying you're you're free to multiply the one zero vector by anything you want and you're also free to multiply the zero1 vector by anything you want and if you add those two things together you get the set of all possible um two vectors right again if you think about it scale the first you can scale the first Vector which is 1 Z by anything right that's what it means to do one Z time F so the set of all possible field elements and then the second one is says

okay you can also scale a 01 vector by anything right uh and then you can add those things together and certainly that gives you any any ve any two Vector that you want right again not a super deep statement but it's an important one to to parse right more broadly if we have an even number of Dimensions right we can actually generalize a statement and it's kind of silly what it says is it says okay any Vector space that has two times n Dimensions right or as an F2 to the N let's say actually can be decomposed into the following two things it can be decomposed into its first n entries and it's second n entries right and so of course if I take any Vector here and I

can take any Vector here and I can add those two things together I of course recover the set of all two to the N or two * n uh vectors and uh not a super deep statement but it's worth checking it carefully so I would recommend taking a of the homework okay so before um you know we gave an example around retman codes now there's a there's a question okay do these things also have recursive substructure and the answer is yes so we're going to start with it only one of the subspaces so we discussed two subspaces in the past is V Prime and V prime prime which were the even and odd

Powers respectively we're going to see that we can actually write the set of odd uh Powers as kind of some multiplication times the set of all even even power evalu of polins okay so from before you know we have the same Vector space the vector space is the original V is defined as a polinomial of degree less than or equal to n minus one evaluated at a bunch of points Alpha 1 through Alpha and we have the set of uh kind of even power polins of degree less than or equal to one evaluated from alpha 1 to alpha n okay and what is surprising and I'm going to leave this one as a homework excise because it's kind of hard to it's very easy to see once you sit down and write

it out but kind of hard to explain is it turns out that you can write v as the following sum the set of even Powers right plus a diagonal matrix whose elements are the EV whose diagonal elements are the evaluation points times the vectorace itself again so um I I'm gonna leave that one as a as an exercise for the reader because it's hard to explain in words but easy to explain when you uh sit down and write it but if you don't believe me on this uh recommend as a you know a follow along along exercise uh if you would like to continue with the lecture feel

free to believe me on this and and you can prove yourself in the homewor Okay so so with that we actually have kind of all the structure we need to to do the simplest possible thing which is an exact Subspace check I'll say what that means in a second but the point is these spaces specifically the the set of read Solomon code space pictor space of read solman codes of degree less than or equal to minus one but sorry it's a mouthful but the high level IDE is there um they have a lot of structure so we want to exploit that structure in some way to essentially prove that something belongs in the big Vector Space by proving that it belongs to these smaller Vector spaces as I've discussed previously okay so let's assign a

simple-ish protocol that does exactly that so what's the idea what is the check that we want to achieve well we start with a vector X and we would like to check that the vector X is in some Vector space capital V and we're going to assume of course that this Vector space it's this Vector space is known we don't know if x is in this Vector space but the vector space itself is known and we know we also know that it has this recursive substructure so specifically we know that it can be written down as the sum of two Vector spaces um T1 * V Prime and T2 * V Prime okay so it has this this notion of

recursive substructure where it's like the vector space V can be written in terms of these individual other Vector spaces V Prime uh sub Matrix times V Prime okay so what does it suffice to check well you know all we have to do by definition is if V equals T1 V prime plus T2 V Prime then that means that every X can be written as the following as T1 time a vector y plus T2 * a vector Z when Y and Z belong to V Prime right that's just the definition of this like kind of weird equality thing that we wrote up there that's the that's the definition that we say said originally and so now it suffices to check simply two things first we have to check you know we are given some Vector

y and z um that we that is claimed to be you know the the decomposition of X right so how do we think about that well we have to check first that the equality is satisfied so X actually does indeed equal T1 time y plus T2 * Z that's a reasonable to check and so that's that equal if that equality is satisfied then we're good with the fact that X is at least equal to those things and the next question is okay but we also need to verify that indeed like Y and Z each of them belong to the Spector space b Prime right um because if they don't then we have said nothing about X right so those are the two those two things will imply that X is in B by our our definition um so here is you know at a at a high level this already gives us

some savings so you could imagine for example that checking that you know a thing in V takes about n^ sare time if V Prime is a dimension about half of V which it should be it needs to be at least that right then uh we have the following property that we've already saved time right so we've taken a thing that scales you know super linearly in the number of entries and we've divided into a smaller the sum of two smaller number of entries right and so if checking that we line a vector space V is super linear the number of entries and we can decompose it into two smaller versions of that then we've saved a lot of time right because super linear means that the sum of the two things is more

expensive than checking of the the each of the individual uh elements okay um and so of course we also have this nice property that if V Prime itself decomposes further so V Prime is also recursively decomposes into you know T1 Prime V prime prime plus T2 Prime V prime prime right in other words it recomposing the same way that V does then we could apply the same procedure again to the individual entries uh and you know you can you can imagine that if this is true all the time then you can continue kind of following this tree all the way down okay so there's a question here though there's no Randomness here right like all we've done is we've given a deterministic claim and we can just

check it deterministically that's not a it's not too surprising so where does the randomness actually come in so from before this the same setup as we've had before as we have a matrix G which is some code right and this case G is going to have M rows and two columns so it's a it's a very kind of silly code and it's gonna have some distance D whatever the distance is so if you remember the vector Subspace check from session two which that one we actually did prove we know that um in order to check the two elements Y and Z belong in V prime it suffices to check that kind of this random structured random linear combination of y and Z themselves belong

in V Prime so if the if this random linear combination of these two vectors belongs in V Prime then we know that actually the original two vectors belong to V Prime as well with high probability it might not be always be true but it's generally going to be true and so now we can replace the last step of the previous protocol which is that y and z are in B Prime we can replace it with a single check for a single Subspace right which is we're going to replace that last section with drawing a random number R from 1 to M and then verifying that the random structured linear combination of Y and Z lies in B Prime right uh and of course you know because that implies that y and

z are in B Prime right and that along with the equality check that you have that xal T1 y plus T2 Z also hold then we know immediately that X must also have been in the original Vector space so um just it's worth thinking about right why does this weird protocol imply that X and B um with probability with error probability sorry here's the question by m uh does having a check in a recursive decomposed Subspace V Prime of vector space V help with anonymity and speed of proving a statement that could be extended to V it helps with the speed right not always so it it depends

on the structure of the decomposition so this is why we said like oh you know if it takes a long if it takes n squ operations to check whether something lies in V then in some sense we've have some savings uh if we can decompos recursively into V Prime and V prime prime that are slightly more structured but there are many decompositions that are silly that actually will not help you out um so the the point is yes that you can think about it as you know if it happens to be the case that these the individual smaller Vector spaces are easier to check inclusion into then we know that like this recursive decomposition will save us work at every step and so that's the high level idea okay so hopefully that answers the

question but back to the protocol so um stare at this slide for a second and convince yourself that this uh protocol does work right and the easiest way to do it is start from the bottom and go back up so start from two and three then go back to one right okay so I'll let I'll let everybody do that as a as a bit of a side exercise for fun in the this is not gonna be a homework problem but okay so now finally we can get to the Subspace distance check unfortunately this is even more complicated which is a bit annoying than the previous one but other than that it it's it's not too hard it's just there's one more set of moving Parts which is we have to Define what distance to a

Subspace means uh and specifically we're have to have one more definition around the distance of a matrix to a Subspace okay so what is the problem with the previous protal PR protocal is very nice right it tells us something very clean which is with some probability we actually belong exactly into a vector Subspace but the problem is of the construction right when we say something like you need to check that x equals T1 y plus T2 Z that's an exact equality so every entry of X has to actually be equal to the you know the entries of T1 y plus T2 Z right and so that's fine uh under you know the coding

model or something like that where it's easy to check exact equality but it's less fine under kind of a different model which is the direct access model right and this is from homework two which is yet to be released hopefully you'll be really soon is we know that checking exact equality actually takes roughly the same amount of time as just reading the entire higher Vector right and again if that Vector is very large then we that doesn't give us any savings in terms of trying to prove something uh in a cheaper way than it would be to just show the statement directly so not only does the previous protocol require this notion of exact equality um which we would like to relax to kind of something as close enough it also requires a notion of exact inclusion so

when we T when we say like oh you know Y and Z belong to the Spectre Subspace B Prime we're actually talking about of exact like inclusion like like Y and V must belong to this Vector Subspace um but from the same reason as before it's actually not possible um without significant kind of you know cost to check out that it holds exactly so we want to check instead is something like y and z are close enough for all intents and purposes to the Subspace that we don't actually care right that we don't care that they're not exactly equal to they could be they could not be but they're close enough so that the proof that we want to talk about actually makes sense okay so from before uh all this stuff is hard to achieve unless we

are explicitly in the coding model and in general we will not always be in the coding model so we want to relax that to work in the direct access model and this is true as I mentioned before for the exact same reason as a zero check okay so as I mentioned how can we relax these conditions right so from before we can relax the notion of exact equality to something being close enough and you know we can relax exact inclusion to also being something that's close enough and here's what this actually means mathematically so from a four from lecture two the distance between two vectors uh will be defined as xus y as the number of non-zero

entries of xus Y right so this is in other words the norm of xus Y uh and the reason why is because this is this is the same thing is saying how many entries of X differ from the entries of Y and this is going to be this thing checking that this is not too large it's actually pretty easy to do already and this is done via the sparsity check and for that see homework to which is again not released yet but we'll be really soon um so the point is this this idea that like two vectors are close together is actually very easy to do in the direct access model with very few queries so that's an efficient thing we can do and that's cool the other thing that we need to Define is the distance of a vector to a Subspace okay so again we have from here

we have a Subspace V and we're going to define the distance of x to the Subspace which going to write x minus V the norm of xus v as the minimum over the all possible vectors in that Subspace um and the distance between X and any one of those vectors so it's the minimum of all of the possible vectors it's like what's what's the closest element of in V to kind of you know X in this like notion of distance right okay so we need one more definition which is the notion of a matrix distance which is uh given a matrix X we're going to say that X is you know within Q close to V or the distance between X which is

a matrix right Matrix is composed of columns of vectors uh and a vector space v um the distance of those two things is less than or equal to Q if there exists a matrix y whose columns each every column is in the vector space v such that xus y has at most Q nonzero rows sorry this is the definition and unfortunately it is a bit of a pain in the ass uh so it's worth parsing super carefully I'm going to give a kind of pictorial version of this but um the point is what does the picture look like okay I want to you know your claim is that the distance between some Matrix X and some Vector

space V is you know at most Q what does that mean okay I have a matrix this Matrix going be an N by2 Matrix in this case right and it's going to be called X great and you know to prove that you have you know that X is distance you know no more than Q from v as you know to prove that little inequality thing definition above what you need to furnish is you need to furnish a matrix y Y which has the property that the vectors The Columns in y belong in the vector space right so we have our X we have our y whose columns belong in the vector

space and then we ask okay how many rows differ between X and Y so what does it mean for a row to differ well it means that you know if you look at the first kind of little red box with squiggles on it right it means that that specifically here the second column of X differs in that entry from the second column of Y and so that means that that entire row right is different so just a single change in one of the entries of that Row from y will deem the entire row to be different okay and similarly you know it it's not double counted so if both rows

differ so if both sorry if the the you know the last entry of both Columns of X differ from the same of Y then that entire row again is counted out it's just counted once so any error on any entry of the row will count as one kind of error right and even if you have even if that row has many errors so there's many places where those rows differ that whole thing is just going to be counted as a single error and so in this case even though we have you know three places where X and Y differ they only differ by two rows so Q here equals 2 okay um so anyone have any questions on that this is kind of a weird concept but Okay cool so let's revise the

original protocol that we talked about right we start in the original protocol we started with some X we decomposed it into you know Y and Z along with these matrices uh and then we went down and checked that y and z are close or are uh in in the vector space right and then doing that will imply that the original X was in the in the in the respective Vector space that we car about so let's start with a simple revision let's just you know relax all of the equal signs to distances okay so uh this is essentially okay first let's check that uh X is close to T1 y plus T2 Z that's fine that's just that we can do that's easy to check

and then we're going to draw a random R and then we're going to take a random linear combination of Y and Z and then we're going to check that that linear combination is close to V Prime which is the the the Subspace that we cared about and the next question is of course does this guarantee that X um itself was close to V right and and close to here is is we're going to Define it as some constant times you know the q's so in this case we've defined Q we've said Q is an acceptable distance for X to B from you know the vector space or or a constant times Q um at the very last line what we're saying is okay for that Q does there is there some constant you know two or three or four or something such that X is if we check that each of

the things you know satisfies those claims X is within you know a factor of three or four or something of Q where Q is an acceptable distance for us to to be happy with okay so the trick and this is a little bit annoying is that in fact this is not necessarily true so just because you check that x uh you know is close to T1 y plus T2 Z and you check that y and z are uh individually um oh yeah sorry uh please be sure to to put your question in chat as opposed to requesting video but um so if you check that sorry that X close to T1 y plus T2 Z and you separately check that y and z

are close to a vector space it does not necessarily guarantee that X is itself close to a vector space right you can imagine that like you know U there is some single entry of Y and Z say that if you change it they would actually change X by a lot right there's we made no assumptions whatsoever about how T1 and T2 interact with the the individual Vector spaces except in so far as we say like okay like they are like reasonable mappings so this this um you know notion of like the ti depends on the structure of the vector space right so so had the distance you know like if why what we need to guarantee essentially from this

previous thing is that if y and z are close to V then necessarily T1 y plus T2 Z must also be close to uh to V itself there we go um so that this is a this is a requirement that we have it it's not necessarily true of all matrices and indeed I think in the homework I'm going to probably put an exercise uh where uh I'm going to ask you to construct T1 and T2 such that a single error will actually cause you to be very very far away from the vector space okay so to do that we need to specify one more thing on T1 and T2 which is that they are basis aligned and that's here's the definition it's a bit silly because it kind of you know it's exactly a definition you need

to make this work but um which is we have a a so Y and Z here are a mat is a matrix and Y and Z have less than Q nonzero rows right this is the same thing that I was mentioning before which is like you know having a single entry of a row be non zero that will imply the whole row is g to be like marked as as a non-zero row okay so if Y and Z has less than a q nonzero rows then T1 y plus t2z has less than or equal to Q non Zer Q Prime non zero entries okay so in some sense uh you know if q and Q Prime are close then the the idea here is the this this mapping actually preserves the distances that we care about between the the

vector space uh and the you know the little Vector spaces and the big Vector space okay so in here's a special case which I will assign is if T1 and T2 are diagonal then Q equals Q Prime right and so these are bases aligned with like this very nice property that the number of of Errors of the big Matrix actually corresponds exactly to the number of Errors uh in the in this like vector after kind of applying these Transformations okay so at a high level uh sorry it's okay if this particular definition didn't make much sense it'll make sense once you start working with it but a notion of Bas alignment means that if y and z are Q close to V Prime then T1 y plus t2z which is like you know that definition that we gave before

is also Q Prime close to V and this is the last step that we need uh to kind of talk about fry okay [Music] so does the last statement go back to V equals V prime it does not right because V and V Prime are different subspaces right V is the Big H yes so so so yeah if it's the case that V equals V prime plus DV Prime then yes it is true that you could like reconstruct that from the original and we're gonna see one exact an exact example of this which is actually fry so okay so if you remember it like uh you know well here

I'll say in a second okay so here's one step of the fry protocol is we're going to start with V and the question is going to be you know fundamentally the protocol wants to check okay does an element belong into V in other words is an element is you know we're given some X and the question is we want to check if x is close to V so what does that mean in this case of you know when V is a set of read Solon C of degree less than or equal to 2 to the K that is a question of does X belong you know is X a vector of evaluations of a polinomial of degree at most 2K right that's exactly what fry is that's the high level idea and from what we know before from the recursive decomposition step that we had right we

have this thing of like okay if V are the readed Solomon codes right then we know that V decomposes recursively decomposes into a a you know a v Prime right of of degree that's half of the degree of the original right it's the set of even Powers so to speak of the um of the polinomial okay so from before you know we we made the relaxation of the protocol originally which is that we're going to check first that so we're going to be given an X and then we're going to be given a y and a z um the claim now is that X decompos into Y and Z and each of y and z are close to the vector Subspace V Prime okay and if we know that that's true then necessarily X itself must have

been close to the original Vector space V which is you know in other words x is the evaluation of a low degree polinomial right which is exactly the the fry check okay so the protocol again is says okay let's check that X is close to you know this decomposition and then let's check if this each of the elements in this de composition are close to the smaller Vector space V right which again it's easier to check because this is a smaller set of smaller degree right it's a polinomial smaller degree and the evaluations are are easier to check because you need less of them so to speak okay so how do we actually achieve this kind of easily well the first thing is a sparsity check from what we discussed previously in the homework and

the third thing is a Subspace distance check which we know can be achieved um this case not from the homework but from the paper um and so if you kind of you know add the two things together right by triangle inequality we know that x minus V is less than or equal to 2q right so if both of the state if the bottom statement is true and the top statement is true then necessarily uh you know X itself must have been close to to Q to V and the the ve this the constant that we have in front of like what close means is a vector of two so again if each of the two things are is Q close to each other then the the final you know originally X itself must have been two Q close to the original Vector space right okay so from before you know we have

this funny thing where it's like okay like at the end of the day this is fry right like this is just like one step of fry um we also have this thing where like this Vector space V Prime is also another set of read solement codes to some degree right and so certainly it also decomposes in the same way that the original Vector space decomposes so instead of checking the last step that we have in this particular you know protocol which is you know we need to check that this linear combination of Y and Z or close to B Prime um it devices to Simply kind of evaluate a you create a new Vector right and then run the same protocol again right all we're doing is we're replacing X which is you know a thing that we want to check is close to another substance space we're replacing

it with u you know another Vector which is and you know whatever in this case W uh and it's in V Prime so we want to check that W is close to V Prime instead of checking that X is close to V right so we can apply the same procedure again and recursively in order to get the same result okay and at some point you know down the line we're gonna get a claim that's so small that it's worth just checking directly as opposed to trying to use like yet another kind of one of these steps okay and so if we repeat this K times right with your appropriately chosen you know elements and things like that you actually get something like uh at the end of the day you know we've started with this x we decompose it into Y and Z and then we

said okay now we need to check that y and z are in some Vector space V Prime but instead we can just check that like some other Vector you know is a the new Vector which we're going to call W is also in V is close to V Prime but we know how to do that I mean that's the same check that we applied for X except we're just going to apply it over W and then we do it again and then we do it again and then we do it again and so on and so forth until kind of we get to some point where the last claim is so easy to check that they you might as well just check it directly uh unfortunately the details for exactly how one gets the sum to be close to you know how you get this 2 q and how you

like show that there actually is a significant saving in total amount of like checks that you have to do uh is a bit messy it requires telescoping series and crap like that which is it's not complicated and it's not hard it's just like there there's like a certain accounting that has to go on that's very hard to explain verbally so um this one I will not assign in as a homework because it's it's just like it's not that instructive it's it's simply kind of mechanical and so uh but for that if you're interested I would recommend you check uh the paper section 4.2 okay so at a high level result again what did we do we started with checking that some Vector is close to a vector space V and we reduce it to the following simpler check which is that we

have two vectors Y and Z that have two properties first you know this like T1 y plus T2 Z so this recursive decomposition property holds in other words x is close to these this recursive you know decomposition like linear or combination and second that y and z are themselves each of each close to V Prime of course we know from the vector Subspace check that gr1 y plus gr2 Z right if that is close to V Prime then that that means that the each of Y and Z must have also been close to V Prime Prime right that's uh this is just like the one of the checks that we stated and it's also in the paper right and so in

some sense we've reduced kind of checking two things are close to V primes checking that a single thing is now close to V Prime um and of course we then iterate because now we need to check the single Vector is close to V Prime well we know how to do that if V Prime decomposes into you know V prime prime or two two matrices over Prime then we can apply exactly the same procedure again one more time to do it that you don't have to check that this you know W or this gr1 y plus g2r z gr2 z our close to V Prime we can just apply the same procedure that we did over X except for the new Vector space um and doing this recursively you know you could imagine if you got a constant amount of savings for each round that you do this then at

the end of the day you get a con you get a an exponential amount of savings the number in the number of times you repeat the procedure and that's exactly what fry does and that's how it actually achieves sness so at a high level as well you know we have no notion of polinomial pooms aren't really needed in this discussion polinomial only enter in the fact that like it is a concrete set a concrete Vector Subspace which has this um this kind of recursive decomposition but they do make a great practical case right like it it turns out that um you know they have just the right properties to have this notion of basis alignment they have just the right properties to have this you know the checks at the end be a little bit easier at every step and

so on and so forth but the point is uh polinomial themselves are not exactly kind of the most necessary aspect of this you know there might be other structured codes that are also similarly useful um which you know could lead to kind of more interesting or perhaps more efficient similar kind of constructions okay and there's a question here which is is the iteration deterministic then I'm not sure what the iteration terministic is every step of the iteration uh has a random component um the number of iterations could be deterministic indeed yeah so that that depends on the protocol and depends on what you're interested in doing with it but generally the answer is

yes um so the number of times that you recursively decompose this thing should in general be deterministic okay um so anyway so quickly conclusion now we're kind of reaching up on time is we have finished the course so congratulations for making it all the way through uh the course you know began probably simple uh and kind of you know nice and then you know unfortunately to say real things there are details to it and so you have to have to chew a little bit of of glass um and so but you know the interesting part is that look we covered a bunch of tools right that are very general they depend on kind of no real structure of a lot of things um and they generalize things that we know and love from the ZK

literature and with those tools you know we gave an example of one application so here specifically is how to understand fry from a linear algebraic perspective and that's kind of all you need like the ne algebra is all you need if you want to make the mean um but the point is there's likely many more right like fry is almost incidental it was one of just simply a thing that we were curious about proving you know again a weak notion of security of it and we ended up doing it and so it's cool here's what we're presenting and you can understand it from a pure perspective of linear algebra but there's a question are there more things that you can understand in this sense and so one thing that know I encourage you to do is there are many proofs uh out there in literature that

can be Rewritten using this type of framework not all of them and indeed there's many that are not right but there's a few that actually might be like quite interesting to sit down and be like okay how do we write this proof which probably has a bunch of lemas and you know all of them play together in different parts how write this proof you know in terms of this probabilistic uh implication language for example or can we rephrase this proof which is in terms of polinomial in terms of just purely kind of er correcting codes and that would give us a general version of it um and so on and so forth so but the point is uh okay so so at a high level it's kind of a nice framework to think about stuff and it seems to be applicable in many cases one of the natural questions

that you have is how many more cases and so this is a that will be an exercise for the reader not because I know the answer simply because I'm just curious if anyone has an is um more broadly uh yeah so if you saw an error on the slides or you see an error in the homework or you have solutions for the homework uh please do a poll request on the gith pro Story the GI Pro should be up on the Discord in one of the pinned uh links and if you have SL feedback as well so if something isn't clear or you think you can maybe rewrite it in a better way or something like that please feel free if you want to you know Teck up some of my crappy hand drawings feel free to do that too um happy to take PO requests and things

like that and yeah and I you know none of this uh of course is is possible without everyone's help thank you so much for attending uh thank you an and Gaylord so much for having me here cool anyways thanks I'll be cool take questions now um so here I'm yeah there is one question actually so I'll let you go here okay so question does it reducing the number of errors in a row to one for the Matrix instance reduce the security of the protocol I'm not sure I fully understand what it means to one for the Matrix instance

um sorry forun I'm sure so EI either you can jump in on or maybe reformulate for for us to read um while you're deciding on that I wanted Anna to jump on go ahead question does it is it does reducing the number of errors in a row to one for the Matrix instance reduce the security so it's reducing the number of Errors to one um it does not actually change the security of the protocol as stated here I guess I I'm not sure I fully understand I'm gonna map it to something that I think I get um but essentially like one or many erors in a row will actually make no difference to you and the main reason why is because

you're kind of taking a linear combination of all these things so if any one of the entries is screwed up um then you have this like nice thing of like the whole you know that that entry after taking a Lear combination will probably also be screwed up so that's idea um next question what if we find a typo in the paper way to let you know feel free to email me ping me in the Discord there are actually funnily enough I if you again this is why I encourage you to read the GitHub uh version not the ePrint version so the GitHub version has um yeah unfortunately I don't have the paper up on GitHub but um the Epub version or sorry the

the version that I have on my website is actually up to date and has less errors than the ePrint one which I will update at some point but I have not yet yeah Chino I don't know if that answered your question earlier but if you want to make some prisions H now is the time if you want to unmute yourself yeah no unless you didn't mean to jump up with us maybe yeah I don't know um okay we can so yeah I think if this this is the end of our session I want to say a big thank you GMO for doing this like short ZK hack study group with us this was the ZK study

group mini we were kind of trying out this new format how did you find it me or yeah how did you find it oh yeah oh yeah oh there we go yeah there like uh wait work oh okay anyway so so uh I I thought it was good I I don't know it's it's nice to have a a short set of sessions that's contained unfortunately things have been a little crazy so I apologize about the the last minute slides and homework but hopefully they made sense I have no idea if they did that would be very curious to have feedback on that and again if you have you concerns conditions comments please

PR or just send them to me on Discord but hopefully it was good I don't know I'm actually CU us for everyone else's feedback on it totally yeah I mean and I think we're going to ask this in our chat but we're really curious from the audience what you guys thought of this kind of thing the sort of short form study groups um also we're using right now this ring central hopin like hopin was the tool we used to use and now it's been bought by another company I am wondering if people like it because we're thinking of running ZK hack online on this again which we' done in the past but we wanted to know if if it worked out I I liked it I don't know it seems like it's still working pretty well

um but yeah thank you so much gyo for taking the time and spending these two weeks with us thank you both for having me we're gonna be so we're gonna be releasing this video on the YouTube channel um actually it's might be good G mod to just monitor that YouTube channel too to make sure that because there sometimes people might actually ask questions on the YouTube videos themselves um and we're going to keep this chat open on the Discord for a little while I think as people watch the videos kind of after after the fact yeah and I know actually yeah we we had been talking gay ort and i' been talking just today I think about potentially creating

a little resource with all of these videos potentially in the new year so G yeah yeah it's actually not the end because there is a bunch of homeworks that I think people are going to wait for as well but yeah typically having the homeworks and maybe some links to the GitHub with st beginning of solutions or even final Solutions would be a great resource for future students so yeah looking forward um sorry apologies about not reling the homework uh I hopefully I think it's fine I'm not even sure so many people actually done the one from the first session yeah so this is fine I feel like for the time but yeah definitely we'll be looking looking for to it in the next in the next few days and weeks yeah yeah I think of this I mean I don't know how you feel GMO but I

feel like this is a nice kind of um companion to the paper it's very so when we have this in one place it might be cool to share it once again just sort of like here's the paper here's a video series that goes through the paper here's a bunch of you know exercises you can do and um yeah it's it's funny because actually a lot of them were based on uh questions that I had from people about certain parts of the paper where they're like I don't know how to do this proof and it's like okay homework uh problem you know one part one actually is exactly that it's uh you should you should work it out it's just sometimes it's easier to to do these things when you do them with pen and

paper than it is for someone to just tell you what it is you know anyways yeah thank thank you again it's it's kind of a fun it's a weird format I've never done this for any paper before um I've given lectures on it but never never with homeworks on on a specific paper but in a mini in a mini version the three-parter seem exactly so it's kind of fun anyway so thank you it was it's definitely entertaining I'm curious what people think very cool all right thanks everyone for coming out for the wonderful questions mmud you had great questions this time thank you so much for that thank you all yeah and uh I guess we will see you I think in the New Year like in terms of a format like this

I don't know if you all know this I'm just going to do a little plug for ZK hack online so we do our hackathons those are kind of you know weekend long hackathons but the ZK hack online event this is a four-week workshop online like in in a platform like this with a puzzle hacking competition and this is going to be running from January 16th until February 6th we're going to be making a bit more noise in the Discord about that I don't know if people have been the previous three this is our fourth time running this online series um but it'll be a lot of fun so we'll see you in the new year for that okay cool thanks everybody thanks GMO