ZK9: Linear algebra and zero-knowledge – Guillermo Angeris (Bain Captial Crypto)

Transcript

foreign [Music] Guillermo is going to come up and share a little bit about linear algebra and zero knowledge welcome Guillermo back to the stage as a speaker this time and the speaker this time for better or worse I guess we'll find out next um yeah cool so uh this is work done jointly with Alex who's actually right here so if there's any mistakes on the slide please direct them just straight at him not me but I really do hope you catch some mistakes because I'm sure they will exist and I would prefer to not have them all right great so with that let's get started um so very quickly what we're going to

do in about 10 minutes is we're going to do a hilarious amount of things which is namely generalize a number of things that we know in ZK to just way more broad situations so specifically ZK depends a lot on the fact that their you know polynomials have this very nice structure they have this like property that if you test you know a specific point of a polynomial with high probability if it's zero then with high probability the coefficients of the polynomial must have been zero blah blah we're going to show that actually none of those results depend on polynomials and all uh they're actually properties of something called error correcting codes um so and the idea is to do this with something called hopefully good notation uh linear algebra and just a tiny tiny tiny you

know salt-based sprinkle of eccs okay so for anyone who is not well aware of linear algebra linear algebra is very very nice over the real and complex numbers everything is lovely your intuition makes sense you know the sun is shining and the ponies are out unfortunately linear algebra over finite Fields it's an Eldritch monster with a nine smiley face in the front that says yes sure you can do linear algebra come in but it will eat you extremely quickly so beware okay so unfortunately in order to get everything in 10 minutes you have to eat a few vegetables before we can get to the dessert so let's get started on that so what we're going to say is we have probabilistic implications this is kind of a weird thing that only exists in

data science and I'm just going to pretend it exists everywhere else what does it mean it means so we say PR which is a statement that depends on some Randomness R implies another statement QR that depends on Randomness QR Prime with pi probability if that implication is true with or is false with probability at most P so if p is very small it means that the implication is almost always true right so there's a number of interesting Downstream consequences this is just you know this is what people call soundness error but here is like a calculus for these things which is you can chain implications together there's a simple variation of this it says if P implies Q with probability p and Q implies t with probability P Prime then indeed kind of

as one would expect you can chain those things and say p implies T but the probability here is slightly larger it's p plus P Prime so as this is kind of you know an extension of the normal notion of implication that we all know and love which is that if a thing implies another thing and that thing implies something else then the original and the last thing are implications of each other um so many other things follow this is kind of going to be the only one that's important but we have to carry around this extra error term okay so what is an error correcting code I'm going to just put it out there a linear code is just a matrix and the Matrix has M columns and N row or sorry M rows and N columns we say we encode a vector X into a much larger code word g

of X and here's my shitty drawing of an encoding which says you take an X and then you blow it up to some larger message or in this case code word g of X okay the trivial code also says here's my encoding you give me a message congratulations you got the message back that is a perfectly reasonable encoding under our framework although it won't be that interesting but the probably more common encoding in ZK is the read Solomon code what it is is it says if there's anything you get out of a stock is forget all of the linear algebra what we're going to do is we're going to say x as the coefficients of a polynomial of degree n minus one G of X means you're going to encode that polynomial or encode that message into a polynomial and gxfr says evaluate that

polynomial at a point R that's it so this is the one you know if you ever get lost in the sauce like I would recommend just go back to this one definition and we'll this will kind of set you back on the right track but this is true for arbitrary linear codes and there's many of them that are not just reads element codes okay we're going to use exactly one definition for coding Theory and that is the distance D of a code this is D of a code is a very weird but actually useful thing that says I'm going to encode all possible messages so there's a list of messages that are all possible messages encode all of them and then find the one that has the minimum number of non-zero elements that number is going to be called the distance so the idea is if you think

about it you have some if you have a vector and has a some error right the encoding if the distance is large will actually expand that error into a bunch of other places in the like encoded vector and this is kind of you know going to be useful because if you have some error somewhere you want to have high probability of catching it by just like checking the output or a very small portion of the output and that's the point of an aircrafting code okay so the trivial code is just an example has distance one of course any non-zero Vector will have distance that's not zero because it needs to have at least one non-zero element but it's going to have this is exactly one because there's you know take a picture with only a single one and zeros everywhere else the retirement code actually has this funny

little distance which is you can think about it as a blue message with length n has you know can be encoded into a degree n minus one polynomial right so it has at most n minus one zeros and minus one roots so because of that if we think of like a set of all possible evaluations of that polynomial it's going to be zero and at most the field which is all possible evaluations minus the places where it can be zero so it's going to be non-zero in all of those spots so it's very it's essentially a very very large number okay we've eaten all the vegetables let's get to some interesting results very quickly we're going to do a bunch of ZK in like five minutes so the usual zero check what are we doing all right take a vector X and code

it and then check a random symbol from the encoding check if it's equal to zero if that's equal to zero then with high probability the original thing must have been zero why well that's kind of the definition of distance right the definition of distance says anything whatever it is is going to have very large distance d right and with high probability if that thing is non-zero I must have like if D is you know very very large relative to the size with high probability I'll hit one of those non-zero entries so for our resolvement code this is exactly the same as like the one-dimensional short simple everyone wants to think about it but the point is you get exactly the same bound that you would expect which is what's the probability that a non-zero polynomial value is zero at a point at a randomly chose a point but it's the

degree divided by the field size so a generalized here check says okay well I don't want to check if a single Vector is zero I want to check if a bunch of vectors are zero what are we going to do we're going to smash all the vectors together in this particular way we're going to choose a random row of G I'll give a diagram for this in about a second choose a random row of G and then use that as the coefficients for a linear combination of these like zeros of these vectors sorry so you have y1 through YN you want to check if all of them are zero I don't want to check if each individual one is zero what we're going to do is we're going to smash them all together right and then check if that resulting Vector is zero to do that again we'd pick a random row

we use that as the linear coefficients we smash them all together and then we check that that resulting Vector is zero and indeed if that resulting Vector is zero then with high probability the original vectors must have been zero in the first place in fact the probability bound is exactly the same as the original one for the original test and for our retallment code this is exactly the same thing the degree of a polynomial or the number the length of the message -1 divided by the field size okay the picture of course is we have M rows we choose a random row uniformly at random and we use that row as the coefficient of the linear combination of y1 Y2 all the way to y n and then check if that's equal to zero the high level proof is kind of silly but it says look okay I'm going to take

a linear combination of a bunch of things that are non-zero then with high probability that you know that places the non-zero are going to be kept in the final Vector that's again just from the definition of distance okay now you could be like haha I'm very smart what am I going to do here's a bunch of math um I have a thing that lets me check if a single if a single Vector is zero by like checking a random element right I also have a thing that says I can take a bunch of vectors and smash them all together into one vector and check if that thing is zero so why don't we just put the two things together right I'm going to take a list of elements a list of vectors I'm going to smash them together into one vector and then I'm going to encode

that vector and then check if that element is zero right all we're doing is we're kind of concatenating the two previous things that we talked about into just one single protocol and indeed what you find is of course by the fact that we can have these very nice implications with additive soundness error we get the probability of this final check kind of written out in math not super important is actually at most you know P plus P Prime and it turns out actually if you guys are familiar with this this is exactly this word simplelemma and it turns out that this actually shows that it's not tight and it's generalized also to arbitrary linear codes so it does not depend on the fact short symbol does not depend on the fact that polynomials like are in the mix it's actually true for any general linear code okay

finally we'll say one interesting thing that I don't actually think is known that says let's say I want to check that a list of vectors each belong into some Subspace B how can I do that well sure I can check that each individual Vector belongs in Subspace V instead I can do the same trick that I did before which is I pick a random row of a mate of the big code Matrix I use that as the weights for a vector combination and then afterwards I check that the resulting single Vector is in the Subspace V and that indeed will high probability will imply that the original vectors must have each been in the original Subspace for every Solomon code again same probability bounds okay

finally we're going to so you might say okay the probability bounds are all the same it's kind of silly like you know maybe we know a few of these things maybe we don't there's some quick sparsity results and these are going to be very similar to those of the Harrow very similar to those who fry and spirits so The Spar zero check says Okay I want to check if a vector is sparse there's many ways of doing that of course I can go through every entry of the vector X and then check if the number of non-zero entries actually matches the bound that I want instead I can just say okay I'm going to randomly sample a bunch of elements from X and check if all of them are zero if all of them are zero then with high probability you probably don't have that many things

that are not zero and indeed the bound is kind of exponential in the number of tests that you have so s here is a uniformly randomly chosen subset of the entries that you are checking and P here is exponentially is the probability which section is decreasing and how many indices you test so this is the hero light which says okay I'd not want to check if one vector is in this like you know esparz I want to check if a bunch of vectors are individually sparse and lo and behold the same trick happens to hold you take a random row you sum all of the vectors using those weights and then afterwards you check if that one single Vector is sparse and with high probability that will imply that the original vectors each must have individually been sparse

um this is again kind of weird right like the same trick is popping up over and over and over again we have it all in the same notation all in exactly the same way and I need actually you can show this implies the original claim and finally we have this generalized the arrow so this is almost but not fully proven but the point is a classic thing you want to do is you want to check that a bunch of things are close to a certain Vector space one way of doing that again is checking that every individual element is close to a vector space but that's a bad thing to do because it requires a lot of work so instead you can just take a bunch of linear random linear combination of all of those things and then check that the resulting linear combination which is a

single Vector is close to the vector space itself that will again hopefully with high probability imply that each of the individual elements must have been close to the vector space in the first place there's a condition on how far you know how sparse your thing can be but that you know we'll punch it for later the point is actually this part of this proof is still open and for technical Reasons I'm happy to get into later so please come and chat with us this is interesting anyways so we just did seven checks in a little bit over 10 minutes uh very fast so hopefully everyone got it there's going to be a quiz at the end of this um many of the generalizations here but the point here is like all of these things are kind of straightforward right like you write down the map and

everything looks kind of exactly identical and you're just doing the same thing over and over and over again in a bunch of different things right in exactly one framework so we can replace the point here second Point here is that we can replace Reed Solomon codes with General linear codes and we kind of don't really lose anything um there so there might be codes that are more or less computationally efficient that might be interesting to use in certain parts of proofs depending on what's needed and finally and most importantly we could understand many of the systems that were many of these like individual proofs that we like all end up dealing with all the time and just one single framework so with that the paper will hopefully come soon although I make no promises okay I make a few promises but with high probability promises and then I just

want to say thank you for listening and thank you to Aki for actually some of the interesting conversations cheers should we take one question I think I had you start like does anyone have a question on this yeah I think everyone understood everything but everyone understood right 100 right great okay oh you got one okay oh just one second I think we're gonna bring you a mic uh with regards to this uh codes themselves have uh do they have to be

MDS or it can't be any linear any code I didn't even Define MDS actually and that wasn't just out of spite uh that was actually just uh it was actually not required it was super question thanks cool okay fantastic thank you I don't think we really have time for another one anyway so thank you so much Guillermo