ZK Hack SPLA Study Group – Session #2

Transcript

So this lecture unlike the previous one is going to be discussing uh a little bit more practical things. Well practical is a strong term for what we're you know doing which is just pure math but but we're going to be discussing real tools. So so this if you are familiar with the literature in zero knowledge you'll see that these things that we're going to be discussing today. So things like the zero check or some notion of sparity check have probably popped up in your study of um ZK protocols.

So the aim of this lecture for the most part will be to rewrite a lot of those tools not just from the perspective of like so uh I guess taking a quick step back most of those tools as I've mentioned before and alluded to in the previous lecture are usually kind of dependent on things like okay we want to check that a polinomial is zero um and instead of checking that the whole polinomial is zero it is suffices to check that the polinomial evaluated at a random point is equal to zero and then that means with high probab probability the whole polinomial must have been zero in the first place. So that statement has an equivalent analog for uh in error correcting codes, right? Uh and and we're going to discuss that here. And

not only are we going to discuss it here, we're also going to give kind of what that analog is and a proof of that analog in very simple notation. And by virtue of the fact that, you know, we've kind of eaten these vegetables. We've kind of done the linear algebra part. We've done these weird uh probabilistic implications stuff. We're gonna get just kind of as a as a side effect of that, we're gonna be able to write proofs that traditionally take kind of quite a bit of of glass chewing as I lovingly call it um but take a lot of effort to write down and and you have to like be careful of keeping track of all these random variables because of the we've specified these are going to be very simple and you can think of them as kind of like okay now we have a bunch of Lego blocks

can we combine them in a variety of different ways to construct you know new tools from old tools. um with it with with I hopefully very little effort. So uh one of those tidbits is going to be in the homework uh and we'll talk about it here. And then so just to kind of get a feel for what it means to combine different tools using this notation uh A and B uh we're going to discuss another one of them which is kind of a deeper one here in the lecture and I'll give a proof of that a very short proof of that uh as like whatever three or four slides that hopefully will be interesting. Um, what we're not going to discuss here yet are things like the sparity checks that appear in Fry. Those are going to be

left for our next lecture. Okay. So, with that intro and caveat, let's uh let's get started unless anyone already has any questions, but feel free to I'm actually staring this time at the at the questions point. So, feel free to ping me at any point and I'll I can actually look. Um, okay. So, as I mentioned before, last session was essentially pure math, right? So, we we didn't really say anything that was interesting unless you're already interested in math. So, in this session, we're kind of going to start applying this math and saying things that are either familiar or if not familiar, they would be useful in understanding zero knowledge protocols as we know them today.

So the idea is let's take the tools that we've kind of you know we've done all this this vegetable eating earlier on. Um let's put those to the test. Let's actually can we say interesting real things about them that you know in some sense take what's known in the field and either generalize it or write it down in like a simpler way. Okay. So as the high level overview one important thing that we use in the paper is this idea of models. And we're going to discuss what those things are, but essentially models will allow us to take what are pretty, you know, hardcore cryptographic primitives and just kind of encapsulate them as as a very simple way of of modeling interaction between two parties. And in fact, we're actually

not even going to model interaction between two parties. That's all going to be implicit in how we formulate the problem. So it's all going to be very kind of, you know, like magically it's going to look very simple, but in reality, what's going on under the surface is actually fairly complicated. That's kind of the cool part as we saw with linear algebra. That's like a cool thing that we can do is you know we can encapsulate what are pretty complicated operations in a very small number of asky characters. We're going to do the same thing here uh but with this notion of like models. Um so in a sense we're going to kind of you know know in our heads that we're sitting on top of this like cryptographic foundation but never really discuss it uh because of the fact that we can kind of we can think about

that as kind of being abstracted away from our our understanding. So from there we're going to discuss specific tools. So uh specific tools are things like what I mentioned before you know checking that polinomial is equal to zero everywhere. Uh and how do how does one do that in an efficient way? Well it suffices to check that polinomial value at a random point actually equals zero. And so that that's that's one such tool and we're going to see an analog of that again the error correcting codes. But we're going to deal with you know the paper deals with two types of checks. So those are one call exact checks. this like you know this thing is equal to zero everywhere.

Um the paper also talks about sparse checks um which are things like maybe this thing is not zero everywhere um but it's zero in a lot of places and that is enough for us. So I'm going to leave those sparse tests we discuss only a tiny little bit but for the most part they'll be left for the homework uh and then if you are interested in the proofs of that which are a bit more involved uh for the paper as well. Okay. So the other way of putting this entire lecture is that we're essentially going to go build our toolbox of tools.

Okay. So first we've been discussing this notion of probabistic implications, right? And in this proistic implications, there's this this notion that randomness plays a key role. So as we kind of do stuff, right? like there is this statement that depends on some randomness, right? And that allows us hopefully that the point of this lecture was we will see that that allows us to simplify, you know, take a big statement that's very difficult to verify and simplify it into a much smaller statement that's very simple to check even though it has some probability of being false. Right? So in particular, you might draw an incorrect conclusion from checking this one

particular statement. Um but you know if that probability is very very small then that actually turns out to be fine for our intentive purposes. So one example one very concrete example is going to be the following. We want to verify. So we are given some vector X, right? So this is like, you know, this vector X is sitting in some server somewhere, right? And we're we're allowed to access it. And we want to verify that that vector is sparse. In other words, that most of its entries are equal to zero.

So we want to for example verify that less than 10% of the entries of X, at least 10% of the entries of X are non zero. Sorry. um at most terms of the entries of x are non zero. So in particular 90% or more of the entries of X are equal to zero right why this is useful we'll you know discuss later and it's again in the paper but but for at a high level it's like this problem this like cool problem and someone has handed us someone's like okay I have this vector you don't get you can like look at it by like looking at individual entries but you you know you'll pay a cost every time you look at one any one entry right and essentially they say okay but I want to certify I I will tell

you that actually most of this vector is zero but I need you to just certify that before you do anything. How does one do that? So if we kind of you know like do this without thinking right all we do I realize that for some reason I guess the thing didn't finish compiling but um so essentially we can start checking uh you know this big vector right we can start at entry one or whatever entry we want and then just like simply check every element until we find that you know 90% of them are actually equal zero right that's that's one method of doing it that's huge right so if this vector is very very large when when I mean very very largely it has a million 10 million maybe 100 million entries right so if we're checking you know that 90% of 100

million entries are equal to zero that's kind of huge and insane but we guar you know that's that's one way of guaranteeing that like the vector actually turns out to be mostly sparse uh on the other hand of course uh we have to do like 90 million queries uh for this to for any of this to make sense right so it's a huge number of queries and potentially like it's extremely expensive depending on how much we're being charged for every query that we make. Okay, so uh in the homework we'll see that actually this is you can't avoid this. So in fact this is this is unavoidable if you do not use randomness. So just uh keep that one in mind. Okay, but kind of getting back to that point checking every single

element, right? So yes, correct. This is the the bigo version of this. So checking every single element requires roughly speaking about n checks right if we want to check that 90% of the entries are zero right and we have n entries that we need about 0.9 time n checks to be able to certify that at least 90% of it is zero um ideally it could be more could be you know but but the point is we want to certify this is the case so the number to keep in mind is if n equals 2 which is about a million then that's quite a bit of queries that's about 900,000 of them on the other hand and you'll see this in the homework again uh is that we care about, you know, we don't care that like exactly, you know, 10% of the entries are non

zero. We care that like at least 10% of the entries are non zero, right? And so instead with some notion of randomness, we can be certain with up to two to the negative 100% probability uh that this is the case with using less than 700 queries. And so the the high level idea is what you're going to take you have this big vector and you're just simply going to randomly sample entries of that vector, right? And you're just going to check if that entry is zero. So you start with a big vector, you say, okay, I have I'm going to choose a number between 1 and 2.

Let's say it's whatever 32. I'm going to check if entry 32 is equal to zero. If it is, great. If it's not, then we fail immediately. And so the idea is if all of those entries are, you know, if all of these randomly sampled queries are zero, in other words, 700 of them are zero, then we know that the vector must be pretty sparse with very very high probabilities. So uh again, I'm not going to discuss the the exact uh probability theory there. It's it's kind of a fun it's not super hard. It's kind of fun. And the point is it's going to be in the in the homework. Okay. So with that, right, we we can kind of see

like where randomness helps, right? Like randomness is very nice because we start with a problem that if we did if we did it deterministically would require us to have a huge number of queries, a very large amount of interaction between two parties or between, you know, us and some data that's out there or whatever. And randomness kind of allows us to reduce that um by doing this kind of small let's call it a fostian bargain which is now you're not allowed to know that this is true with 100% certainty but you can know it with enough certainty that for all intents and purposes it might as well be true.

Um for you know feel free to close your ears if this is already satisfying for you. There's a whole question around what it means to be random and that's pretty complicated and there are like I'm pretty sure there are entire books written about this notion. So we are going to assume a kind of a very idealistic version of randomness which is pretty close in practice as far as we can tell. Um you know again thanks to cryptographic techniques. uh but you know the the point is the randomness here that we're going to consider is going to be the simplest possible thing where we say okay things are drawn uniformly from some distribution and that's 100% fine and we can achieve that you know by by whatever means necessary okay so let's talk quickly about models so as

I mentioned before models are how we can encapsulate kind of deep cryptographic techniques uh and interactions that happen between parties as a very simple kind of high level um interface if you may if you're familiar with programming. So in particular models are going to be you know as as I mentioned right the way that we encapsulate all of this kind of complicated stuff that happens in zero knowledge proofs interactions and cryptography specifically um in a in a way that we can access relatively easily with no problem kind of you know dealing with a high level math constructs. So the point is we can kind of separate these two these two things out right in such a way that like we assume cryptography works uh and we assume the

kind of like interactions work in the way that we expect and we can if we assume that right and we we now have this very nice interface that we can play with that lets us write very clean proofs about how the rest actually works. Um so for this lecture and in general for the paper we have two models of interaction. Okay, the first model of interaction is what we're going to call the direct model of interaction or the direct axis model of interaction. So in this model, this is very similar to the way to the you know the problem that we just recently described regarding kind of checking the sparity of a vector. So in this model there exists some vector X and that vector X is you know kind of out there somewhere.

Um I'll give you a a concrete mental image of what this means later but and the point is we would like to verify some claim that someone made about X. So the claim for example before could have been that X is actually you know has a sparity of of you know 10%. So 90% of the entries are zero at least 90% of the entries are zero. And in this model the only thing we're allowed to do is query individual entries of X. And every time we do that, we pay some cost. The cost is is left unspecified. But the point is we care about the number of queries that we do in order to verify this claim.

Okay. So the the way to think about this model is you have a you know you have a like a little hard drive, right? So and someone tells you I need to verify this thing about X and they hand you a hard drive and the hard drive is truthful. So in particular, you know, you can plug that hard drive into your computer and then just like verify the things that you need to verify directly. But the point is that the kind of because the hard drive is this passive thing that exists, right? The person who you are who is like telling you like you should verify this claim cannot, you know, um cannot adaptively respond to your questions, right? In some sense there's this is like this model of like okay I

have a thing that's out there and the response has happened. So I can when I query X I'm actually querying X. I'm not like querying some party out there that is like attempting to fool me in some smart way. I am simply actively querying X. Uh you might think that that is you know that's kind of weird right because it's very rare that we can do this and we we're going to discuss how one does this you know in a second. But the point is um if you assume that you are querying X right in some sense you've encapsulated some notion of like interactivity between you and kind of the thing that you're looking for. Okay.

So that's one model right this direct access model where you directly get to look at the entries of X. The second model is called the coding model. uh in the coding model there is a public code matrix or a public error correcting code matrix G right uh G as usual and as will be standard for pretty much the remainder of the sets of lectures and throughout the paper is an M* N matrix okay this code matrix is known so it is known to everybody it is certainly known to us and much like the previous case there some message that we do not know

ourselves like lying somewhere out there in space and we would like to verify a claim about that message. So that message X in this model we're not able to access X directly. So we're not able to look at you know entry three of X. Um but we are able to query a symbol of the encoding of X. Right? So if you remember from the previous lecture when you have a error correcting code matrix G you can take a message X. So in this case, x being the vector that we're checking stuff over is our message. And then simply multiply g* x. And that's called the encoding of x under the code g. Okay. And from you

know what this model says is okay you're not able to access x but you are able to access one symbol so one entry of the encoding of x. So I cannot access X3 but I can access you know the third symbol in the encoding of G * X. In other words, the third entry of G * X, right? So G * X is a vector. I simply look at its third entry. Um, and the point is I now pay a cost proportional to the number of symbols I have requested.

Okay, so that's called the the coding model. And this is the one that we're actually going to focus on for most of this lecture. Um, and okay again okay again okay again okay again okay again okay again okay again okay again okay again okay again okay again okay again okay again okay again okay I I'll get to how one achieves this in practice but the idea is relatively similar someone hands you a hard drive right and the hard drive has a little chip on it that simply encodes you know the the message X and then spits out the the not it doesn't spit out the whole code word but it spits out a specific entry of the code word uh corresponding to the message so it spits out a specific symbol of GX the one that you requested and again it is assumed to be truthful so Okay.

So, you know, I I I mentioned I alluded to this fact that like this is a very strong claim, right? Like I'm telling you like, oh, there's a message X and you have access to it. It's a very strong thing to just be able to do, especially in things like zero knowledge where you might not actually trust the other party. Um, so the models by definition require this notion of truthfulness. And the point is that this truthfulness actually you know thankfully people much smarter than me have been working on this idea for like a very long time and they're like cool like here is a black box that allows you to guarantee a certain notion of truthfulness and that notion of truthfulness achieved via cryptographic techniques. So one example of it is in the direct model right this truthfulness notion this fact that you

can actually query individual entries of X um can be achieved by just a Merkel tree construction how does that work so again if if you don't really care too much about this like close your ears for a second this is uh but it is a very important point and it is like very interesting um is instead of a person giving you a hard drive that says here is X please check this thing that I need you to check. Um, they hand you the Merkel root, right? And then you can query them. You say, "Okay, I need you to give me an entry, you know, as we discussed 132 of X and they give you the entry and they give you a proof that that entry actually like lot, you know, was

somewhere in one of the in, you know, the leaf that 132 of this particular Merkel tree." And so it's cool. Okay, here you go. here's X and here's a proof that the thing I sent you originally is consistent with the answer I just gave. And in some ways that's like a way of encapsulating this fact that you were able to access the original X that people wanted to verify. Um you know without any kind of like without the party trying to like mess with you without the party trying to be like oh I know what you know he or going to ask for in the next step. So I'm gonna try to like fool him by sending him just the right information to make him like you know be like okay this is this check passes. Okay. So if you close your ears, feel free to open them now. Um the point

is all of this kind of you know this deep cryptographic techniques are going to be completely elided. They're going to be blackboxed um as it as its own separate kind of ideal. We assume that this thing works. Uh we assume that we can access elements of X directly. We assume that we can access code words of X or sorry specifically symbols of a code word. Um how how that's achieved is usually via the notion of commitments. But that's you know that now that has been blackboxed we can like move it to the side and then focus on you know now purely the the linear algebra part of zk proofs. Okay and of course I will note that this is of a super fascinating subject and of course worth studying and this is this is you know a bunch of

cryptography that's super interesting. Okay so let's now talk about the exact checks. Um so here's a question randomness plus hashing used in a construction gives the same concept as digital signature is a concept similar um so signatures you can I think you can use some sort of signature schemes to construct commitments but in general they're not equivalent there's a notion of a commitment that is um very specific u at a high level a commitment simply says something like I am going to give you kind a like some number some x right and then you get and that that essentially

forces me to ahead of time commit to a fixed object that I cannot go back on. So because I gave you this Oh, sorry. Uh yes. So the question was uh I'm going to read it out loud. I'm I'm going to try to map it to something that I think is um direct, which is randomness plus hashing used construction gives the same concept as digital signatures. Is that concept similar to what I explained previously? So um at a high level just like this this notion of signatures and commitments like they're somewhat I think related and again I'm pretty sure there's some notion by which like they play together but a commitment fundamentally is like a different object. uh a commitment is is a thing

that lets me send you some you know object whatever that is right so in particular it's a commitment but um and then you can query me so you can say like okay please give me you know something about this object that you like have committed to uh and the point of that commitment is that in some ways I cannot go back on my word I cannot like go back and like answer you in the way that I want um if I wanted to fool you in some way right So I can only answer you truthfully based on what I've committed to. So if you think about it, there's like some like ma magical object X in the sky, right? I have a commitment which is like a thing that is depends on this object. I give that to you and then like you ask me, oh cool, is X a dog or

whatever, right? I can't like go back and be like, oh actually, yeah, totally 100%. Even though X is whatever something else. So that's kind of a weird version of it, but at a high level, uh the point is yes. So specifically we're going to look at the binding property here. So hiding is not going to be super important but the and this is uh this was mentioned in the chat I guess but the the point is we're going to be looking at this this notion of a commitment which is very useful but it's going to be encapsulated magically within this kind of like model this access model and so we won't talk about it anymore other than that. Okay so let's go through to the exact checks. Uh again I hopefully you close your ears

for another second uh between that question and this you know what I'm about to say. So the exact checks now are going to we're going to now start discussing like things that generalizations of things that kind of exist out of the literature in very simple notation. So from before uh exact checks work in this notion of a coding model. So in the coding model if you remember we start with some message and we're allowed to access you know symbols from the encoded message right um it turns out like exact checks so checks checking for example that a vector is exactly equal to zero is actually very hard in the direct access model and we'll we'll prove that in order to succeed with high probability you actually essentially

need to check a re-entry of x for you know for something to be if you want to check that x equals zero and you only have access to the direct access model essentially you're going to be you're going I need to check pretty much every entry of X uh to be guaranteed this thing. Okay, please see the homework exercises. Uh which yeah. Okay. So here's a setup. Uh and this is going to be fixed for the remainder of the presentation. So feel free, I would recommend if you have a cheat sheet next to you, this is the thing to write down. Um for the remainder of this section, we're going to fix a code matrix G. and G as before is going to be an M times N matrix um drawn from with whose elements are in

the field F but doesn't matter. The next thing we're going to fix so the code always has distance D and ideally we're going to assume that D is going to be greater than zero otherwise everything we say is going to be trivial. The symbol R will just be a uniformly drawn number from one to M. Right? So y m is because we can think of r as choosing a specific row of the code matrix g. Um similarly one way of thinking about it is if G you know if we take a uh if we encode a message X via G so we get G * X then what we're going to be doing is

we're going to be drawing the ar symbol of that encoding right so R is a uniformly drawn number g * X is an encoded message we're going to be drawing the arth index of that encoding Okay, so let's start with the simplest check. Uh this is classic. So um this is you know I want to check that something is equal to zero or not equal 0. A vector ideally is equal 0 not equal 0. Certainly I can do that for a number. If it was a number it would be super easy.

I simply just check that number. But if I have a a vector with you know a million entries checking that that whole thing is zero is actually pretty non-trivial. Okay. So how do we do that? Here is one simple idea. It's I'm just going to sample R. So I pick an R between one to M. And then I'm just going to check is that symbol that I've just sampled equal to zero. Okay. So everybody got this. So we are handed this hard drive spits out, you know, I get to request indices. Uh and then it gives me a symbol from the encoding. So it gives me an entry of G * X.

And all I'm going to do is I'm going to sample a random number and then I'm going to check I'm going to be be like please you know again I sample random number 132 or favorite random number this lecture apparently and I'm going to check I'm going to say please give me entry 132 of this vector of this you know encoded message. It's going to say okay great here is your your number and then I'm going to check if that number is equal to zero. That's the only thing that happens here. And it turns out this is actually a very effective check. uh so specific we can write it in probabilistic notation which is going to be useful very soon as okay g * x so that's uh you know again an encoded message I check this r symbol I check

that that's equal to zero right that's a statement that I'm making I'm saying I have checked this thing the arth symbol where r is some uniformly randomly drawn number and that's equal to zero and that if I check that statement and that statement is true then with probability with error at most p that's going to imply ly that X actually equals Z, right? And P here is defined as following. It is 1 minus the distance of the code divided by the number of rows of G. In other words, divided by M. Okay, so parse this pretty carefully. I'm going leave this up for like 10 seconds. Um, but what are we saying?

Again, we are taking a claim. So the left hand side, parse it all very carefully, is a is a scalar quantity. So g * x is a vector. We take a random entry of that vector given by r. That entry is of course a scalar, right? So that's a number. And we simply check if that number equals zero. And it it seems super obvious, but it's kind of crazy. that just doing that is enough to guarantee that the entire vector is zero with high probability. Right? We have reduced checking a potentially very large vector to checking that a single

number is equal to zero. Right? Whereas sorry, we reduced checking that a entire potentially very long vector is equal to zero to simply checking that a single scaler is equal to zero. Right? Using the notion of randomness, not multiple rounds, just doing it once. um multiple rounds will give us a better probability estimate but it turns out for almost all intents and purposes this is very very good. So and before you know as before the probability that this check fails is at most one minus the distance divided by the number of symbols in the encoding.

Okay. So we're gonna I'm going to give you some intuition for that bound. It's pretty simple. Uh, pardon my crappy drawing. If someone wants to, you know, do a pull request and tech this up, that would be great. So there, that's another extra extra credit homework assignment. But we start on the left hand side with some vector x is not equal zero. And let's say that the vector is created in such a way to like maximally trick us, right? So it's done in such a way that like you know it has like one entry that's non zero.

Okay? by definition of the distance, right? When we encode that vector, because that vector is not equal to zero, the distance of that vector, in other words, the number of nonzero elements that are in the encoded message is at least D, right? So if x is not equal to zero, then there are at least d elements in the encoded message that are also non zero. That's the definition of distance.

That just comes from, you know, the the thing that we wrote back in the good old days of the first lecture. I guess that was two days ago. Um, okay. So because of that, if we randomly sample an entry of G * X, right? Right? So we randomly sample an entry of the encoding. There are m entries in the encoding. That's the definition of our encoding. Um at least d of them are non zero. So that means that the probability that we catch you know the liar is d / m which is the same thing as saying is and that's an at least right? So it could be more there could be more entries that are non zero in which case it's better

for us but it is at least d over okay what happens what is the probability then that we fail well it is at most the probability that we you know catch one entry at most one minus the probability that we like pick out a non-zero entry right and so you get something like 1 minus d which is the number of non-zero entries divided by m which is the number of all possible entries and that's the probability that our check fails. So it's the probability that we like look at an element and it happens to be zero but the vector itself actually not be zero in the first place. Okay, so

cool. Um there are two questions I'm not fully sure I understand. So that's okay. I'm going to skip it for now. The the high level idea is um you only need to do this check this this is a bound for only doing the check once. Um in many cases d / m is going to be a very very very small quantity. So um it could be something like 2 to the 200 or 2220 and so that that's essentially like impossible. um in some cases it's going to be uh better but not you know okay so at a high level actually and uh this I maybe I'll make this a homework exercise is

actually this exact statement is equivalent to the one-dimensional Schwarz sipma so this is um this is the error this is the general general linear error correcting code generalization of uh the schwarzipilema or the polinomial zero check or something of the like And indeed we find that this is that short simple is actually exactly the special case where the code that we are using the code matrix G that we are using is a read Solomon code um where we essentially like every single row or every single possible element is included in the matrix. Um that's in the paper. I'm not going to like discuss it too deeply here. I might make it a homework problem but at a high level the point is this is a strict generalization

of kind of short simple two general linear error correcting codes. Okay, so now let's kind of do something a little bit weirder. Let's say we don't want to check a vector is zero. Um, there is a question here, but I I'm also going to defer this one because I'm I'm also not 100% sure what it is asking. So, uh, yeah, if you if you want to rewrite the question or maybe ask in a slightly different way, I might try to map it to something I, uh, but I I just not quite sure what the the question is.

Okay, so let's pop over to the metric zero check. So, let's say instead of a vector X, we actually have a matrix. And this is a big matrix. It's a matrix as we know is a collection of vectors, each of which is a column. Uh, and there are n vectors in this matrix, each of which is k long, right? says x capital x is f you know to the k byn. Um and so we're going to ask the same question does the whole matrix equal z. Okay so one big idea is okay cool we can encode every row. So instead of you know let's let's use our previous magical deducting tools. It's like okay we know how to check if a vector is zero right let's can we do that for a matrix? Well yes right let's you know take every a

random element from every row of x from the encoding of every row of x and then check if that is zero right so this is you know written in our notation is we're going to let x tilda i denote the i row so we have a matrix x right has a bunch of rows I want to just take those as vectors and then we're going to say okay please encode that for me and then give me the arth symbol of that thing so give me the ar symbol of the encoded first row, the R symbol of the encoded second row, and know that this R is the same. This is not a randomly drawn R for each one of these. This R is identically the same. Um, and then let's just check if each one of those things are zero. So all of, you know, we have n things that

we need to check are zero. um we simply check this magical thing and we're you know the point is that this gives us that if we check all of those things and each of those things is zero then with probability P the capital X must have also been zero you know the whole matrix must have been zero so if we encoded every row we check a random the same random index from every single row that we've encoded and we check out all those were zero then indeed the whole matrix X must have been zero with high probability okay and so I asked you this question which is what should P be here and as the the easiest hint is I would recommend you see homework one exercise 5.

So if you did homework one exercise 5 the thing on the left hand side should look very familiar um and you have to parse what that what that means for the thing on the right hand side. So um if you did that you should be able to reconstruct what P is here based on um the zero check that we just discussed. Okay, so here's another way of rewriting this is okay, instead of writing it as let's encode each row and then qu then check if a random symbol from each row is equal to zero. Let's do it the following way. We're going to this is the same thing as saying let's pick a random row from the big matrix G, right?

So G is our code matrix. Let's pick a random row from it and we're going to use the row as the weights for a linear combination of the columns of X. So if we call x is a collection of vectors each of which is a column right um we want to take a linear combination of those of those columns right and what are we going to use well we're going to use the randomly drawn row from g right so those are going to be the weights for the linear combination and what are we going to do is we're just going to check that the entire linear combination is equal to zero so that that is a vector right we've taken a linear combination of vectors gives us another vector and we're going to check if this vector itself is equal to zero um another way of writing Exactly the

same check that we just did in the previous slide is the following which is exactly what I just said. It is we take the arth row of g and then we simply use those as the weights for a linear combination of the individual axis. And because it's just the same thing that we said before just written slightly differently that is going to imply that the whole x equals z with the same probability as um previously. Okay. Um so does this make sense? Is everyone good with this? Okay, so let's get funky. Um, here's a fun fact, right? The vector zero, what is it doing? Like at a high level, we

essentially like the the vector zero check takes a vector, right, which is our message, and then somehow reduces checking that that vector equals zero to checking that a single scaler equals zero. There's some randomness and some stuff involved, but whatever. At the high level, all we have is we start with a vector, right? I want to check that the whole thing is zero. And then we reduce that problem to checking that a single scaler equals zero. Okay, the matrix zero check starts with a matrix. It asks the question, does a matrix all do all of the entries of a matrix equal zero? And reduces that question to whether all of the elements of a single vector equal zero.

Right? So the natural question is can you put those two things together? Right? We've reduced a matrix to a vector, right? We reduced checking that a matrix equals 0 to checking that a vector equals 0. But we know how to check whether a vector equals zero by checking whether a scaler equals zero. So can you put those two things together and get kind of you know the some sort of bound on the probability of error. And the answer is yes. And that is going to be an exercise for the reader. And that is one way of getting kind of you know used to this this notion that you can chain probabilities together that we discussed a little bit in the previous lecture but we never actually used until now. So okay so for the nerds in the room like me um

this check this idea that you can kind of take a matrix reduce it to a vector and then reduce that to a single scaler is actually a generalization of Schwarz simple. uh if you just naively apply the um kind of probabistic implications as as you'll see in the homework uh you're actually going to get exactly the same short simple lema if you if the matrix G is a Reed Solomon code matrix but it turns out it's actually not tight so uh we discussed this in the ZK hack discord which is this notion that you know the probabilities add together but like just because the probabilities add together that doesn't mean that the resulting probability is tight right? Like these these errors can kind

of add, right, using a notation. But but you might be able to actually do better than that, right? Because by using more structure from the problem or something of the like. And the point is in this is one of those cases where you can actually do better than the naive approach of simply kind of chaining these implications together by using more structure available in the problem. And so this this uh I won't I certainly won't discuss this and I don't think I'll put it in the homework but um it's in section 3.1.3 of the paper and it actually shows that short simple is not tight even for polinomials by a very very small factor which is roughly the square of one over the size of the field or something like that. Okay, so that's uh you know slash nerd. So that's the nerd rant is over. Um let's continue

with the final boss which we're going to call the vector subspace check. And here is we're going to put a bunch of stuff together and it's going to be a little bit magical but it's going to be very succinct and very short. Okay, so let's start with some matrix X. Again, same dimensions as the previous matrix. So K by N. And instead of checking if all columns are zero, we're going to check if all the columns belong to a subspace V. And if you remember from homework one, uh it there is a special case. So the the zero subspace in other words the subspace that only has one element which is the vector zero uh is is a valid subspace and exactly reconstructs the matrix zero check that we had before. So anyway so that's a special case of this.

This is a more general claim. So again we want to take a bunch of columns of X and we want to check whether all of them belong to a vector subspace B that that we know. And there's a question of can we do this cheaply? So can we do this in a in a way that doesn't require us verify every single like you know column of the matrix X. Okay. So let's do something very similar to what we did with the matrix zero check. The rewriting of the matrix zero check. We're going to pick a random row R of the error correcting code matrix G. Right? And then we're going to use that random row as the weights of a linear combination of the columns of X, which is the matrix that we wanted to check to see if there if the columns of X

belonged into the vector space B. And then we're going to check if the not the individual columns, but if the linear combination using that randomly sampled row also lies in the space B. Okay, so all we did was we used the same trick that we used before, which is we're going to s randomly sample a row. We're going to use that as kind of the the weights for a linear combination of the columns of X. And then we're just going to check instead of that being equal to zero like we did before, we're going to check if that thing is in a vector space V. So if that whole you know sum which is a single vector uh lies in the vector space V.

Okay, we can write this in the parabolic notation as this simple thing which is you know G of R1. So this is the arth row of G the first column times X1 which is the first column of X plus you know every the linear combination of every single column in capital X. Um if that is in V right in the big vector space V then that implies with high probability uh or in other words with error at most P that every individual entry of X or every individual um sorry column of X in other words each X I must have also been in the vector space in the first place.

Okay so let's let's do a quick proof of it. Um so this is where the linear algebra comes in. So we need C which is going to be a parity check matrix for V. If you don't recall what that is, you should take a look at the homework and or the paper. Um so then what happens? Okay, we we have assumed that our check succeeds. So in other words, that g of R1 * X1, you know, the the linear combination of the columns of X uh are indeed in V with this randomly drawn row um R. So if that's in V then by definition of a parity check matrix C times that whole vector must be equal to zero right because by definition a vector is in V

if and only if uh C * that vector is equal to zero okay now by linearity if you remember C is a linear operator so we know we're going to take the right hand side here of the first implication where all we did was move it down here to the bottom left um but C is a linear operator right so C is matrix. And so C * the sum of a bunch of vectors is the same thing as the sum of C times every single vector. Right? So another way of rewriting that is saying, okay, um C times, you know, the linear combination of the XI is the same thing as a linear combination of C times the XI's, right? Which is the equality that we have here on the right hand side. So

the right hand side we have you know a randomly drawn row of the matrix of the code matrix G right and we're using that as a weight to linearly combine C * X1 C * X2 all the way to C * XN and we know by definition that that whole thing equals zero for the randomly drawn thing. Yes. So someone's getting uh ahead of me, but yes, exactly. So all I did, I'm going to this is just simply taking the last equality that we had in the previous slide. I put it back up here. Um but this should be familiar, right? This this last equality that we have right here. So again, I just took

the right hand side of the bottom. So it took the bottom right hand side and just moved it up there. I didn't done anything to it. If you recall from, you know, 10 slides ago, this is exactly the matrix zero check, right? What was the matrix zero check? The matrix zero check said take the column take a bunch of vectors take a random linear combination of them using the you know the randomly chosen row of G and check if that whole thing is equal to zero. If that is true then we know that each of the individual entry each of the individual vectors must have themselves been zero with high probability with error at most P. Okay.

But by definition of a parody check matrix, if C * X equals Z, then X must be in the vector space in the first place. Right? So this gives us, you know, if we kind of put all of the implications together using the rules that we know and love that we've been talking about, this gives us exactly the claim we wanted, right? We put everything together. Um, we start with take a random linear combination using this like random row. um of the columns of X and check if that is in B and that if you follow all the implications implies at the end of the day that the columns themselves must have been in B in the first place. Okay, so we only used one implication with any error and

that was the matrix zero check. The rest were all just normal standard logic implications. So they have zero error and so they they add zero error to our conclusion. And so in other words, if we put everything together, we can write exactly the claim that we wanted before, which is it suffices in order to check that all of the XI's lie in a so all of the columns of X lie in a vector space V. It suffices to check that a randomly drawn uh you know a random linear combination of these uh where the linear combination weights are given by a random row of G. um also like that linear combination lies in B and that is has the same error probability as the matrix zero check that we had before.

Okay, so anyway, so this is like this is kind of crazy, right? Like we just did a proof in like two slides of like something that I think is pretty non-trivial um and would be pretty hard to do if you just like looked at it from scratch and we're like, "Okay, yeah, let's do this." So I would recommend going back through the slides and parsing it a little bit more carefully. I went through it bit quickly but all of a simil meaning and everything makes sense and you should look at which quantities are vectors and which quantities are kind of matrices and things like that. It's worth doing just carefully. Okay. So quickly through sparse checks is there is to every kind of check that we just recently talked about there is a sparse version of it.

So there's a there's a version of it where we actually don't care that the you know the condition is exactly met. So for example, maybe x is not exactly equal to zero, but it's sparse. Or maybe x is not exactly in a vector space, but it's close to a vector space in the choice of distance. We're not going to explore the proofs in this particular course because they're quite complicated and some of them require actually a bit of annoying glassing. Um, but I would recommend you check the paper and the homework which is related to the first set of exercise I was talking about uh for some of the proofs there. Okay. Um so essentially for the next lecture which is going to be kind of the you know icing on the cake we're going to use two types of sparse checks. So one of them is going to be in the homework

which is going to be the standard sparity check which was again the same thing that we discussed in the very first set of slides um like at the very beginning of this lecture and then the other one I'm going to give you an outline of the proof in the next lecture. Unfortunately I you know for this paper I found no easier way of proving this thing. Um it's not clear to me that there is because it kind of relies on a bit of you know deep it's not that deep but like somewhat deep linear algebra. Um so but if anyone you know that's a great exercise if anyone's wants to go ahead and try and find a nice proof of it that would be super useful. Um but I'll give a proof outline of why you know this this certain sparse check is true in the next lecture but we

won't cover the proof of it. So apologies for that. You'll have to go check the paper. Um, but the main thing to note is that it's really good to be comfortable with this kind of probabistic notation before that lecture. So I would highly recommend you do potentially things like problem five of this previous set and maybe the first or second of the problems of this next set. Um, okay. So where to from here? Okay. So fine, we rewrote a bunch of tools, right? We wrote short and a bunch of like other similar things. Some of them hopefully felt familiar if you if you know a bit about kind of ZK and stuff like that.

But the point is that we did all of them in you know we covered all these things in in a span of you know 30 40 minutes or something like that. So this kind of shows you the power of the the notation and the ability to kind of take a bunch of things and you know imply one versus the other and you know concatenate them in a variety of ways and kind of really think of them as as mathematical Legos that you can use to to place things together. Right? So that's kind of the the high level idea here. you know, now you have a bunch of tools in your belt and it's when you look at something, it's kind of easier hopefully to see how the pieces fit together as opposed to kind of being this kind of monolithic single um you know big proof that you

have to think about entirely before you understand it. So in the next lecture we're going to see how we apply these tools to explain this security of fraud. It's a very weak notion of security yet again and constants aren't good and then people ask this all the time they're like oh do you get better constants and it's like we know we don't. This is not this is not trying to improve the analysis fry simply trying to understand it in a simpler way and show certain notions of security. It's very possible that you can do better uh in fact I know you can do better in terms of constants than than our paper because simply we did we made it the simplest possible exposition rather than like the fanciest possible kind of you know most refined set of constants. But the point is this will serve as a as a kind of capstone

project, right? Like so far everything has been the first lecture was very abstract just pure linear algebra. The second lecture, this one is a little bit less abstract. You know, you've probably seen some of the tools here if you're familiar with ZK, but but you know, the applications of them are kind of probably not quite gelled yet. Uh and here we're actually going to see just a very concrete application of all of a number of the tools that we explored here um directly into proving kind of something that we know and love and actually turns out to be like very hard to understand. to me it was at least um which is the kind of why why does try work right like sure you know you know it's possible to know how how these checks work like that and possibly intuitively it's clear that they should

work but like why does it actually work kind of fundamentally um but the point is that's just going to be kind of a a cool application that's the best way to think about it um the idea is with this is that there are many hopefully many more applications of these tools uh to explaining a number of other ZK systems that might be useful and interesting in a variety of journals. So, um I encourage you, you know, as you kind of go through these things to a fun exercise would be to rewrite some of the proofs that people have in certain other papers using this notation, potentially maybe generalizations to linear algebra and things like that. So, cool. Thank you uh all for coming. We have about four minutes for questions until 10 a.m.

I I can stick around until afterwards. This one ran tiny a little bit longer than I expected, but uh feel free to to ask any of them and things like that. Great. Thank you all. Thank you very much. So, yeah, if anyone has questions, you can either ask them in the chat or, you know, request the audio and video to ask them here. And if you don't and you're already working on the homework, that's fine, too. I guess you're going to you're going to be posting them uh on the Discord as last time. Yes. So, a quick note on that, I guess, since there's no major questions pressing questions. Um there's two things. So, uh, I'll probably be posting the homework hopefully by Monday for next month. I look, if anyone's already finished all the homework already, like, you know, big hats off to you. Um,

that's good. You leave you leave us time to finish the first one. I I I did not, for instance. So, you for not putting pressure on me. What is this? You know, the model student isn't finishing, you know, the homework like three days before class. I'm really not a model student. You should ask my mom. Yeah. So, okay. So, that's that's part one. Um, oh, so sorry about that. I I I need to edit them a little bit more and there's some stuff that I I want to make sure I add problems for. And then uh number two is um and this is this is kind of a big one for anyone who's interested in solutions. I don't have solutions. I mean I I know the solutions and I need to write them down, but anyone who's interested in writing solutions um should go take a look at

the repository. I posted it in the ZK hack Discord and you should um feel free to do a poll request. So if you have a solution and you can write it up in latte, uh please do a pull request. Um it would be great by the way if um if you did people did pull request either per part or per problem because I I don't want it to you know try to merge a 500 line pull request is actually kind of annoying. Um so I will also give you a fair warning that I am a pain in the ass about writing. So we'll take a lot of editing probably before it goes on to the thing. But but know that uh it is you know with love in my heart uh to to make sure it's all clean. Uh, by the way, if there's errors and slides and

things like that, also feel free to pull request those to raise an issue um in the GitHub and I'm happy to to edit it or accept a pull request or edit it as needed. Okay, cool. So, there's um one quick question which is does the sublinearity of verification aka succinctness stem from the probability of queries according to M for this instance? So um let me I I think what the so the way I interpret this question is okay does the fact that verification you know is cheaper than kind of like checking the original claim um does it stem from kind of this notion of randomness I I okay cool so the answer is yes actually so so you cannot have and you'll see this in the homework for

a very specific claim you cannot have succinctness you cannot have sublinearity um of the verification without this notion of randomness. Like it is actually impossible. And we're going to you're going to prove an impossibility in the homework that says like you cannot actually check that a vector is like all equal to zero um you know by just like checking its entries unless you literally check a linear number of entries in in like n in the size of the vector. So uh that'll that'll be an interesting homework problem that will hopefully elucidate that question a little bit more. Um, anybody have any more questions?

Uh, can we apply this kind of logical operation to any other math logical operation? Uh, yeah. So there is, uh, the paper actually does have an if and only if version of it. Um, so there is a notion of if and only if in fact there's a notion of a lot of the logical implication rules, not just implication rules, but logical rules. um in this kind of weird setting. So the exist symbol is a bit funky and there probably is something like that. So uh because existence is a is a is not a logical notion. It is a set theoretic notion. So it's a bit different. Uh the equivalence is indeed the case. So so

logical equivalence works in the same way. Um um the if and only if also works, but actually you turns out you actually don't always want if and only if because it turns out one direction is always true. So uh for example, if you have a bunch of things that are zero and you multiply them by anything, you add them together, still going to be zero. Always going to be zero. So there's no probability of error in one direction. That's that's often called completeness in in zero knowledge proofs, right? But in the other direction, the soundness error, right? There's there's a probability that indeed the the the notion is false. So this actually what's interesting about the notation is that it very cleanly separates out completeness, right? Like there's no notion of completeness that we talked about here. We kind of use it implicitly throughout in the sense that like we

expect the check to work the claim is true, but we don't actually ever like mention the fact that the check you know if for example if x as a vector is equal to zero then certainly g x is going to be equal to zero right. So the check is always going to pass. But we never talk about that in this lecture, right? So so in a certain notion like this this idea is like completely separated from the these like probabilistic implications that we talked about, right? They those implicitly assume that the check that you have done is satisfied and then show that the original thing must have been satisfied. But it is possible the check that you do might be too restricted, right? Maybe maybe it actually almost never holds or something like that. Um the only thing this claims is that if

that check holds then the conclusion probably holds with very high probability. Um but it need not guarantee that even if the conclusion holds that the check does hold itself. So but the point is there there are equivalent versions of these you know implications things like that and you can construct versions of it where you have like asymmetric implications or one way is zero and the other way is probability P and all stuff. Okay. Um cool. Any any further questions? It looks like it's a wrap for today. So yeah, thank you everybody. Thank you GMO and uh yeah, we'll see you next week.

Make sure you register to the event for next week. It's going to be a new one. And uh yeah, in the meantime, uh have fun. Good luck with the homeworks. And yeah, let's study the part four. Next time is going to be the part four, right, of the paper. Next time is the part four. It's a little bit of part end of part three and end of part three and part four. So, um, yeah, thank you, Gaylord, and thank you, Anna, for for having me, by the way. Yeah, thanks everybody and see you soon. Bye. Bye.