ZK Hack SPLA Study Group – Session #1

Transcript

Cool. Well, anyways, thank you everybody for being here. Uh for those in the West Coast of the US, uh thank you for being up so early. For those everywhere else in the world, thank you for being here so late. Um hopefully it's at least a little bit of fun. Unclear yet, but I guess we'll we'll find out next. So, Okay. So, this session is, you know, session one. This will be kind of interesting cuz it'll be a another I what I lovingly call eating vegetables session. It's going to be the session where we go through and remind ourselves what linear algebra is and kind of intro this funky little notation that we have in the paper that we call probabilistic implications.

Um but for the most part, we're not going to be doing anything truly real this session. We're going to be kind of just reviewing material that we're going to be using heavily in the next two sessions. Uh a lot of it will be very familiar to people who have taken linear algebra. Um so, if you've taken linear algebra, feel free to just take a look at this slide and, you know, wash over you. If you haven't taken linear algebra, you should probably pay attention to this particular set because it is going to introduce just the amount of linear algebra that we're going to use for the remainder of the paper and for the remainder of the sessions.

Um so, again, if you, you know, I know there's like 250 pages of reading. Uh there there was no expectation that you would read all of that, but it was important that you know, you at least took some time to review the parts that were not super clear to you at the time. And this will go kind of through not just, you know, all of linear algebra, but specifically kind of the things that we're going to use throughout. Uh and so, you know, if you if you didn't spend a bunch of time reading Boyd and Vandenberg, you know, exercise 13, like don't don't worry, you know, it's it'll it'll be okay, I think, uh for the most part. But but I do highly recommend that you go through it carefully if any of

the stuff here is like a little bit weird or shaky. And then certainly no nobody here has seen probabilistic implications before unless you read like a paper from 2008 that had it in some data analysis context that's kind of completely irrelevant and I in fact we had no idea about it until we wrote the paper and looked up references. So that'll be new to everybody. Actually probably also new to me if I'm not careful but other than that. Okay, so let's let's get started. So kind of we're going to break this lecture into into four big pieces. The first is going to be just high-level ideas. This is you know why why do this work? What are we going to do? Kind of where is it going from here? The next will be the review of linear algebra that we talked about and immediately after the

probabilistic implications. We're going to talk a little bit about it. I'm going to send you know there's going to be things that I will just simply casually say that are totally not obvious. In some of those you will find the explanations as homework problems and then in some of those you'll find the explanations in the paper and in some of those you'll find the explanations nowhere to be found except in some textbook I sent over the chat. So I'll hopefully try to outline which is which but I make no guarantees about the you know the total coverage of the code here.

And then the last thing is kind of you know where are we going to go after this lecture? But again if you find this lecture today's lecture to be kind of a little bit oh okay, we have these things we're doing stuff with them but we don't yet know what we're going to do with them. Don't worry next lecture and lecture after we'll start doing like very real things with just a few tools that we've set up here. So first things first. What is the high-level idea behind the paper and behind the set of lectures? So what we're going to do is we're going to take a bunch of crazy concepts from kind of sync proofs or ZK or whatever you want to call it. Examples include things like the polynomial zero check and things like that. And then we're going to reduce those to linear algebra with just

a smattering of error correcting codes. The idea here is and and I mentioned this before, but a lot of the content from things like succinct proofs depends heavily on things like polynomials over fields, over finite fields. The argument here is that actually the polynomial part is not as important as kind of the fact that there is a there's a slightly higher level of abstraction, which is error correcting codes, that lets us do many of the same things that we do in ZK, but in a more general like kind of regime or a more general lens.

So, how are we going to do that? Well, the idea is, okay, once we've, you know, taken this idea of, okay, let's replace kind of polynomials or like total, you know, randomness with kind of a structured notion of randomness and and error correcting codes, we're going to use that and then introduce some succinct notation to kind of show how one might think about these kind of probabilistic proofs. To do that, we need to have this kind of crazy concept, which we'll discuss today, which is we're going to take traditional logic, things like A implies B, uh and B implies C means that A implies C, and then we're going to relax that to a probabilistic notion. So, a notion where those things aren't true always,

but they are true, for example, with high probability. This is not super obvious, it's not really a thing I've seen before, uh but it's a thing that we kind of implicitly use when we write a lot of these protocols. And so, the point here is, kind of, you know, much in the same way that we have the rules of logic, we're going to have the rules of probabilistic logic, which will tell us how to compose certain statements in a way that preserves the probability of error or, you know, bounds the probability of error of this like logical sequence. The you know, for those who are interested in things like programming languages and that kind of stuff, I have a little bit of a thing in the homework for you, but the way to think about this notation and

the reductions that we're going to present here for the rest of the course is you can think about it as a proof carrying protocol. So, a protocol, roughly speaking, is, you know, a sequence of steps that you take to verify some outcome. And a proof of that protocol says something like, if you take the sequence of steps, the probability that you discover that someone has lied to you by giving you an incorrect proof is very high. The idea behind the notation here and the construction that we have is to kind of merge those two things together. In a certain sense, what you're going to get is you're going to get a proof of the protocol that describes the protocol itself, um and also kind of at the end of the day spits out a probability, a soundness error, so to speak, uh that of this

particular protocol that you've enunciated. And of course, you know, what's cool, what's not cool to do is to present a bunch of formalism and then say, "Okay, go off and do your own thing at the very end." That's kind of boring, right? So, the kind of tip of the cake, the or the icing on the cake, the tip of the iceberg will be something to show like, "Okay, we're going to actually use this to show the security or the soundness of something that most of us, at least I, didn't understand, which is FRI. Uh I found it quite difficult to actually even read the proof. I To be fair, I actually did not try to even try to read the proof of the soundness of FRI.

Um but we're going to use kind of, you know, this library, this arsenal that we've built up to take a protocol that many people know, um and then show its security via just kind of these like high-level constructions. So, that'll be the the kind of, you know, final lecture. We'll be defeating this final boss. Um we're going to show a very weak notion of security, but the the bounds can certainly be improved and the constants certainly be improved, so don't worry too much about it. The point is just show the power of this framework that it can actually show interesting things that we know and love and can reconstruct things that we expect.

Okay. Unfortunately, to do all of this at scale as mountain, we do have to eat some vegetables first. And that'll be the purpose of this lecture. So, at a high level, why do all of this work, right? Like in a in a lot of ways, kind of a traditional argument that I've heard a few times is like, "Okay, you've done all this stuff. That's very cool and like you've generalized some things." But you know, is it truly like novel? Is it truly like, "Wow, like this is kind of crazy." To some people it might be, to some people it might not be. But the main point is this is mathematical tradition to take you know, things that exist, concrete objects, and then generalize them in a way that's very simple.

And that leads you down a a big rabbit hole of a of a bunch of like consequences. So, the idea is given something that we know exists, you know, for example, these zero knowledge protocols that work, you know, using polynomials and the station of randomness. One idea would be, "Hey, look, let's try to find a minimal a minimal set of requirements for all of these protocols to work." Right? And then because you kind of have the minimal set of requirements for this thing to work, you can now tease out what parts of the assumptions that are made are truly important for the security, for the implementation of a given protocol. Uh and those that are kind of incidental.

They're nice structure that is very nice to have, but is not a requirement for this thing to work. Uh and that often actually helps clarify the exposition of certain protocols and proofs of certain protocols and their security and things like that. So, you know, this hopefully says like a little bit about why, but the main point is that additionally, removing these requirements helps understand the protocol at a deeper level. Certainly, removing requirements also allows you to do things like generalize protocols to broader settings that were not previously known before. And that helps, you know, guides and it helps be a guide to new

discoveries and things like that. And the main thing, which is kind of something that's been happening over, I would say, the past five or six years with ZK, is that it lets us take protocols and kind of divide them into its their constituent parts. So, now, for example, you know, before at a time you kind of had to understand a whole system end to end, now we can kind of think of ZK protocols as being composed of two parts, which is, you know, an IOP, uh and a polynomial commitment scheme. But, we kind of tease that out even more in this set of lectures into things that we're going to call kind of randomized reductions, uh and then we can study those individual things and improve those individual things, which will improve the overall

kind of set of protocols that exist. Uh and so, that's that's the high-level idea that you should keep in mind when working with these things. But, you know, I won't belabor this point too much. Philosophically, we talked about this a lot in episode 294 with Kobbi and Eran uh around like why do this kind of work and why it's interesting and why this particular paper might be uh fun to do. But, in reality, the real reason we do this work is because it is damn fun. Um anything else is kind of I would lovingly call it cope. Uh but, okay, that's a little bit facetious, but the point is there. Okay. So, now let's actually get to the real meat. I'm going to go check very quickly to see if there are any questions.

Um um so, I guess there's two questions, which is the probabilistic logic is mostly uh zip limit. The answer is no, actually. So, uh it it's going to be much more general. And you'll you'll see this in the homework and in the paper. Uh and I'm glad it's uh clear that uh, you know, Turn and I are different people. Maybe. This might all be a deep fake. So, keep that in mind. Okay. So, to linear algebra. Okay. So, linear algebra starts with the main notion of vectors. And a vector, which is what we're going to call an n vector, is simply an ordered collection of n elements.

Uh, specifically, the ordered part is very important. So, it is not a set. An n vector is an ordered collection of n elements. So, uh, I haven't discussed what an element means. We'll do that in a second. So, one example is a three vector, which we're going to call x. And x has three entries, which are going to be three, five, and one. You don't have to remember this. We'll use this example a few times in the future, but the point is you can write it in this way. So, um, you know, it's a block. So, it's usually not parentheses, not little squiggles. It is a block. That is, you know, the first element is three, the second element is five, and then the third element is one. You notice that it's also a column. So, this is almost universally the case um, in this

in the paper and in this particular course, vectors will always be written as like columns. Um, and sometimes we will, when it's convenient, when we want to write it in a line, we'll write this vector as x equals, you know, parentheses three comma five comma one. And that'll that'll also be a column vector, which is with elements three, five, and one. Okay. So, one important thing of vectors is that we can index the collection. So, we can ask, okay, what is the second element or the first element or the third element of this vector. So, we can denote that as x sub one. And of course, x sub one here equals three. And similarly, x sub three equals one. So, the third element is one.

Okay. Those are the two kind of important thing notational things about vectors. So, of course, vectors are not just useful by themselves. They're useful because we can perform certain operations on vectors. So, we can scale vectors by any number and we call that number a scalar. So, in general, if we just have like a number that sits around, we're going to call it a scalar in the context of linear algebra. So, from before, if we take the same vector, three-element vector, 3 5 1, we can scale it by two and we write that as 2x. So, what does scaling mean? Well, scaling means that we're going to take every element of x and we're going to just simply multiply it by its coefficient.

So, in this case, we have 3 5 1 * 2, right? Or in other words, 2 * 3 5 1. And that, of course, corresponds to 6 10 and 2. I hope I didn't screw up the the math on any of these, but it's very possible someone should call me out on it if I did. Um another operation that we can do is we can add vectors. So, um we can take x and we can add it to the vector 1 2 3. What does that mean? Well, that means that we're going to take uh so, by the way, it's very important Okay. It's very important that the two vectors that we add are always the same length.

It is kind of a a type error or an operation error to add two vectors that are of different lengths. Um okay. So, with that, we can take x and we can add it to another vector, a three another three vector with elements 1 2 3. And what does that mean? Well, that means that we're going to take every index of x, we're going to add the corresponding entries of the two vectors, and then we're going to spit out the result. So, in this case, 3 5 1 + 1 2 3 means a new vector whose first entry corresponds to 3 + 1, it's four. Uh second entry corresponds to 5 + 2, that's seven. And third entry corresponds to 1 + 3, which is four.

Okay. So, again, if you know linear algebra, it's all fine. Uh if you don't remember linear algebra, this is hopefully at least a little bit kind of new. Okay. And the point is, of course, we can do both at the same time. This is uh you know, given three vectors, which we're going to call x and y and z. It doesn't matter uh what, you know, length these are so long as they're all the same size. We can do things like take a linear combination of the three. So, we can do X + 2 * Y + 3 * Z. Right? What does that mean? Again, phrasing very carefully, uh this is we have a a list of numbers X of some size. Uh we can add it to 2 * another list of numbers + 3 * yet another list of numbers, all of the same size. Uh the

important thing to distinguish here is that the symbols look identical to numbers, right? But only certain operations are allowed. So, the plus here is not the same plus as, you know, one would have for numbers. This is not the same plus as one would use for 1 + 2. This is a vector addition. So, it is very important to carefully parse the types that are going on in each expression. Uh and so, anyways, things that of this form, so things where you have a list of vectors that you're are being added together with some scalars multiplying each of them, is called a linear combination of those vectors.

Okay. So, fixing notation here, it is this is super important to also to, you know, help you parse the types of different things is first, vectors will almost always, if not always, be written as lowercase Roman letters. So, things like X and Y and Z and little case G will all be vectors in this case. Uh so, this will help this is kind of like the the type calculus, if you're familiar with that, the one we'll use to determine what type of object a thing is that you're talking about. Um scalars, pure scalars, will almost always be written as lowercase Greek letters. So, alpha, beta, and gamma. Uh of course, a very important thing is, if I say something like X sub 1, that is a

scalar. That is the first entry of X, right? So, in that case, it will not be a lowercase Greek letter, it'll simply be a Roman letter with a with a subscript. Okay. So, as I mentioned before, you know, we have this these vectors and we can do things like linearly combine them. What are the two things we need to do perform a linear combination? Well, we need A, a collection of a bunch of vectors that we wish to combine linearly, and B, a collection of scalars which we're going to sometimes call the weights of the linear combination, uh which are going to be the kind of the coefficients that appear in front of each vector.

So, of course, B that's just a vector, right? It's a it's an ordered list of numbers. It's an ordered list of scalars, uh and that is the definition in our case of a vector. The question is what the hell is A? And so, A is what we call a matrix. A, a collection of vectors, an ordered collection of vectors is what we're going to call a matrix. So, more specifically, uh we will say we have an m by n matrix, and matrices will almost always be m by n, um which is going to be an ordered list of m vectors.

So, in other words, we have n, you know, different vectors, each of length m. Uh as I mentioned before, in order for addition to make sense, these things all have to be the same size, so that's fine. Uh and then the point is we have kind of, you know, n of these things that we want to linearly combine. Okay. So, the point is given that, uh you know, one example is okay, we have a vector Z, which is going to be 4 8 2 in this case, and it's going to contain the scalars for our linear combination.

Then, if we have a matrix A, which has three columns, uh and it's, you know, it can be arbitrarily tall, then we define the matrix-vector product, in other words, the linear combination of the kind of vectors corresponding to A as an M by 3 matrix, so uh sorry, the result is a M vector uh which we define as A * Z. And that M vector is simply does the the following. It takes four, so the first element of Z, and multiplies it by the first column of A.

It then adds that to the second element of Z multiplied by the second column of A. And then third, it takes the third element of Z two, and multiplies it by the last column of A. So, this is standard notation that we're going to use, which is we're going to denote um we will say this explicitly when it's necessary, which is we're going to denote um a matrix um the columns of a matrix as an indexed collection of vectors, right? So, again, this is very important to parse this super carefully because A1 is not the first entry of a vector, it is the first vector uh of some collection

of vectors, right? Um when you will notice, this is not always true, but this is generally true, is that vectors will be uh often X, Y, Z, and W. And matrices will often be A, B, C, and D. So, it it is going to be a a bit more difficult to confuse the two uh terms. So, even if we're using lower case A to mean the columns of A right? Um you will distinguish that from using X, for example, and X1 meaning the first element of X. So, uh this is again you'll get plenty of practice with this if you go look at the homeworks and stuff, but just keep that in mind.

Okay. The point is though that you know, we've taken this kind of complicated object, which is you know, A, let's say we're adding, you know, a bunch of eight vectors. So, the vectors are of length eight, right? And we're taking a linear combination of those things. That's going to be eight times three, 24 numbers that we have to deal with, along with a linear combination of those things. But, we have replaced that kind of complicated operation, which is scaling a bunch of things and then making a bunch of things together with super, super compact notation, right? Which is simply A * Z.

Okay? Um that's not just so, you know, this is one notion of abstraction. It's very useful, but it's not just useful because it's a nice, simple kind of like we took taken this complicated thing and made it very compact. Um it's useful for two other reasons. First is a lot of the operations that one can do on matrices and vectors resemble the things that we can do on numbers. And so, kind of having this like, you know, intuition for what things are reasonable to do with matrices and vectors be the same as the things that one can do with, you know, just normal numbers uh should have been very useful for proofs.

Uh and number two, and this is going to be very important if you're interested in implementing these things, is that we've known and have optimized insane libraries for linear algebra, for these exact types of operations over the past 60 or 70 uh years. Um so, you know, if you know anything about machine learning and things like that, you know, we have special purpose processors in our computers just to perform these kinds of operations. So, when you write A * Z, you know, where A is a matrix and Z is a vector, uh know that you actually often don't even have to implement that procedure by hand. You can simply dispatch it to a special purpose processor, which is going to be way faster than anything you could do on the CPU.

Uh so, anyways, this is for a bit more of a of the nerdy side, but if if it's of interest, we can chat a little bit more about it on the Discord, too. Okay. So, as an example of a matrix, this is probably the way that people most people have seen matrices is you can think of it as a rectangle of numbers. Uh every column corresponds to one of the vectors, you know, belonging to the matrix A. If you recall from the previous slide, we said an n I'm sorry, an m by n matrix is an ordered list of vectors, right? Then, that's the same thing here as saying that A, the matrix A has columns, each of which is a vector.

So, the number of rows of A tells you the number of elements in each vector, and the number of columns of A tells you how many vectors are in the collection specified by A. So, one particular case of a 3 by 2 matrix is going to be a matrix A which has two vectors, the first being 3 5 and 1, and the second being 1 2 and 3. The main point is that notationally to remember is a matrix will almost always be uppercase Roman letters. And they will almost always be at the beginning of the alphabet, unlike vectors which are almost always going to be at the end of the alphabet. This is notation that we've just said. So, examples include A, B, and C, and so on and so forth. A, B, C, and G are probably the ones you're going to see

the most. Okay. Um a quick aside. We have talked about matrices and vectors, but we haven't talked about kind of what their elements are. So, the numbers that we have in these vectors and matrices exist somewhere. Uh I hope everyone had this one of the parts of the review that was probably the most important, which is that these things lie somewhere, and we're going to say that they lie in a finite field. We're going to call it um bold F. So, notationally speaking, we say an n vector lies in some finite field uh x. This is just a definition if, you know, x is in F to the n. So, this is a This F to the n you can think of as the

set of all possible N vectors, which take on values in the field F. Uh, then simply what we're saying is an N vector X is in that field is is a is an N vector from with elements from the field if X is in F to the N. So, this is notation that you'll see throughout both in the homework and in the paper. And all it means is that X is an N vector with elements of field F. Similarly, an M by N matrix A, which has elements in the field F, is written as A belongs in F to the M times N. So, again, you can think of the right-hand quantity F to the M by N as meaning the set of all matrices, M by N matrices,

which take on values in the field F. And A simply is an element of that family. So, this is just notation. It's not super important. Just it's worth parsing carefully. And you'll see this notation over and over again, so don't worry too much about being comfortable with all this. Uh, more broadly, if I mention something and it feels fast, either once you look at the homework, you'll probably get used to using this stuff, so it it'll become a bit more second nature, or B, it's worth, you know, going back and taking a look at Boyd and Vanderberghe and seeing kind of the notation is pretty much identical to that book. So, it would it is worth seeing kind of what what things you're feeling like are not quite gelling and looking those up in the book.

Okay. Uh, I'm going to pop over here, see if I have any Um, so the answer is in general, yes, but there are a lot Sorry, this is question here, which is aren't those libs and processors designed for composition and suitable for crypto and doesn't know about operating in finite field. The answer is generally yes, but there are many cases where um, you can have things like fixed-point arithmetic and modular operations, which are not always obvious. And a lot of them actually do have some way of working over finite fields. So, uh the book is in the Discord. So, Okay.

So, Okay. So, finally, you know, we're going to get to vector spaces. Um So, there's a question of kind of okay, we have these things. Uh what are we going to do with them? So, there's a natural set over which this all of this stuff is matrix vector products and these vectors work. Uh and those things are called vector spaces. So, vector space is simply a set of which is closed under linear combinations. In other words, it does the two things that we expect vectors to do, which is they, you know, if you have two vectors in this V, uh then you can scale them and add them together. And that new vector is always in the set V again.

If it satisfies that property, then set V is called a vector space or more specifically a vector subspace. Um the point is, like, there's kind of two operations that matter in linear algebra, and that is the fact that you can add things and the fact that you can scale things. And these sets simply tell you if you do either of those two things, you are cool, you're still in the same set. Uh and those sets are important because they're going to provide a lot of structure for the way that we do this. Uh and we'll see particular examples of this in both the homework and certainly in the paper.

Okay. So, here's a vector space. Well, it's the set of vectors which only has the zero vector. Certainly, I can take any any vector there and scale it. So, 0 + 0 still 0. Uh sorry, and uh and add it. Or I can scale it. So, 0 * any number still going to be 0. Uh remember that here, by the way, parse this super carefully. This is the zero vector, not just the single element zero. Okay. Part two, uh the second simplest is uh the vector space that is the set of all n vectors which take elements in the field of F.

Certainly, if I add two n vectors, then I will also get out an n vector. And if I scale an n vector, then I will also get out another n vector. So certainly that also works. Okay, the third simplest is a little bit more complicated is ray, it's called. So for you give me a fixed vector x and all I'm going to do is I'm going to scale that fixed vector by all possible scalars. Okay? So that if you think about it in kind of, you know, in like finite fields are a bit weird, but if you think about it in normal geometry, this corresponds to a ray. So it is it is a ray that simply goes, you know, starts at zero and then draws a line from infinity and then back down.

So adding any two vectors on that ray gives you another vector in that ray and then scaling any vector in that ray also gives you another vector in that ray. So one useful thing here is that even the finite fields are weird and don't really have a super nice notion of geometry. Um, we can often import a lot of the notions that we know in normal linear algebra over the real numbers into this kind of space. And it sometimes, actually I'll say it often won't work, but sometimes it'll be super useful to figure out what the hell's going on.

Okay. So another thing, finally, is we have a matrix. We can ask for what its range is. So the range of A, written R of A, is equal to essentially A times x for all possible n vectors x. Um this is another way of parsing this is this is the set of all possible linear combinations of the columns of A. And that is called the range of a matrix. Um, so the range of a matrix in some sense tells you what things are reachable by just taking linear combinations of the individual vectors contained in A.

Uh, and you will this is of course, one possible vector space. And to prove that, see the homework. There is a homework exercise on that, uh, which I'll release afterwards. Okay. Um, there's another vector space, which is super important, which is called to be called the null space of a matrix. And that is the set of all vectors which are mapped to zero under the action of A. So, if you think if you take A * Y, right? It's a set of all linear combinations of A which end up of the columns of A which end up in zero. There's a very different vector space, but it will also be very important in the proofs that we see.

Okay. Finally, let's get to codes, and then we can stop with the linear algebraic part. This is If you know linear algebra, probably all of the previous stuff has been just complete review. Uh, if you know linear algebra, but don't know error correcting codes, here is where you might want to start paying a little bit more attention. Um okay. So, at a high level, here is the definition of a linear error correcting code. It is simply a matrix. We're going to call it G, just for fun. Um, actually, it's for traditional reasons, but, you know, whatever. We won't talk too much about that. Um, so, we're going to call it G, which is a sometimes called a generator matrix, and then it's going to be an, as before, M * N matrix.

And the idea is the matrix G, by being an M * N matrix, will simply take in an N vector, right? And spit out an M vector. Uh so when we are talking about error correcting codes, we think of an the input to this operation, so, remember that if you have a matrix, you can multiply a vector by it, right? So, you get if you have a uh, a vector X, right? And you can have a matrix G, you can do something like G * X, right? We can think of it as an operation. And that operation is going to take a message, which we're going to call X here. It's an N vector. And then it's

going to map it to some M vector, right? Which is going to call Here we're going to call Y. Uh that mapped vector, we're going to call it an encoding of the message. So, all it's doing is it's you know, we start with a message X. We then pass it through this big matrix, right? Which you're going to see a bunch of examples of. And then out is going to come some big message Y. Right? We have not said anything about the messages or sorry, about the codewords or the encodings yet. So, Y is going to be called either an encoding or a codeword.

Um but we will soon. And we'll see what properties of that are important. Okay. So, what is a classic code? So, remember that I simply defined a code as a matrix. Uh this is a bit different from normal definitions, but it's okay. Um the simplest code is of course the identity code. Here Here is my encoding. You give me a message and I give you back the same message. That's a perfectly reasonable encoding under our definition. And in fact, it might be useful. Another one is called the repeated code. What are we going to do? Well, we're going to take a message, so you give me a message X, and I'm going to give you a message X repeated several times.

So, I'm going to take the message X and I'm simply going to make a vector which stacks the message X many many times. Potentially K times, for example. Um this will also be another useful one for a different reason and it's a perfectly reasonable code. Um so, there are many many more examples, some of which you'll find in papers, some of which you'll find in the homework. Um one is the Hadamard code. This is kind of a difficult one to reason about, but the point is you take a enormous matrix G, and every row of the matrix is going to be one possible, you know, N vector from uh F. So, this is super weird, but the point is that matrix G is going to contain every possible vector uh as one of the possible rows. This is an enormous matrix. I mean, this matrix

is like super super huge. Uh but it's a perfectly reasonable code by our definition. Another one that we'll see, which I highly recommend you see in the homework, is a Reed-Solomon code. Uh and that one actually will be a will recover a lot of the things that we know and love from ZK, which is kind of this notion that you encode things via coding messages by the coefficients of polynomials, and then you evaluate the polynomial somewhere on the domain. Uh for some of that stuff, see the homework and see the paper as well. So yeah, you'll you'll notice that the homework already has like five exercises. So uh I hope I hope everyone's excited for it. I mean, there's no requirement that you do all of them. I would only recommend you do the ones that are kind of you want to focus on, particularly interesting.

Okay. So finally, uh the last definition that we'll go through in linear algebra is that it is is that is going to be super useful for us. It's going to be the distance of a code. And this is of a code is super simple. It says the following. Um I'm going to take any mess any non-zero message X, and I am going to encode it. So I'm going to multiply G by this X. Okay. And then I'm going to ask, what are the number of non-zero elements? That's what these kind of bar zero mean.

What are the number of non-zero elements in that encoded message? Right? So if the message is non-zero, ideally, there are a bunch of non-zero elements in that thing. Right? And then we're going to count that. Let's say it's five. Okay. So that message, or that sorry, that uh encoding is a we call it is we say it is weight five. And now we're going to ask, okay, over all possible messages that one could hope to deliver, what is the one that has the minimum weight? In other words, what is the message, the non-zero message, or the non-zero encoded message, that has the smallest number of non-zero entries.

We're going to call that the distance. So, again, parse this definition super carefully. Right? We're going to say, encode every possible message that you could ever hope to make. And then we're going to measure the number of non-zero entries for each of the messages, each of the encodings. And then we're going to ask, what's the smallest number of that collection? Okay. So, this is called This is what we're going to call the distance of a code. This will become very useful later on. We're not going to discuss super why it's useful today, but at a high level, uh the distance will tell you something about how much So, if you have an error in the initial message, so let's say one bit is flipped in the initial message, the distance will tell you, roughly speaking, in how many places will it differ in the encoded message. So, if it

differs in a lot of places, then you have very high probability of catching kind of some error happening here. Okay. So, what are distances of codes? Well, the identity code, if you have x equals x, has distance one. If two element If two things are the same, then they differ in no places, so, you know. Uh but, if two, you know, if x has anything but an, you know, one non-zero element, then distance is exactly one. So, that's the best we can hope to do. Um the repeated code has d equals k. So, if x kind of is, you know, one in a single place, then that single place will be repeated, you know, k times. And so, the distance is k.

Um the Hadamard code, which is the one that we discussed prior, uh is this kind of crazy thing, which is, you know, the field the size of the field to the n minus size of the field to the n minus one, uh which is huge, by the way. Uh and similarly, the Reed-Solomon code has distance d equals m minus n plus one. And then I would recommend this is going to be part of a different of the same exercise that I referred to earlier, which is uh which we'll discuss why this is the case. Okay. I'll pop back to check if there are any more questions. Uh what is a mess So, okay. So, what What a mathematical purpose uh or link of having vector spaces as field elements where the fields are also algebraic structures with specific properties? So, this is a great question.

Um, one of the reasons why we specify fields is because linear algebra will work over those fields. So, fields have a structure where you can add, multiply, divide, and subtract elements. Um, that it the the the fact that you can divide elements in a field turns out to be very important for linear algebra as we kind of know and love it to work. Um, there are generalizations which do not require fields, they require less structure. Those are called modules. Um, but in general, uh, it turns out that just for most cases fields are just way easier.

Um, we will not be covering the codes the codes used in breakdown. Uh, but but actually that would be a very cool set of exercises for someone who's interested in it. Essentially proving breakdown with a simpler with a different proof. But, okay. Um, cool. Um, breakdown is a is Yeah, I would highly recommend just go go look up uh, breakdown as spelled uh, here by Lance. Okay, so with that let's get to the last meaty part and then we'll go to the full Q&A, which is the probabilistic implication. So, this is you know, if you know linear algebra, probably everything I've mentioned before, and if you know our great codes

and last part of what I mentioned before are fine. Um, this is the one part that is new, I think to pretty much everybody here, including myself. So, let's talk about prob this this weird notion of probabilistic implications, which we kind of just totally made up for this paper, um, and why it's useful. Okay so let's start with like, you know, here's a big thought experiment. Just close your eyes, you know, dream, and we're going to start with normal logic that we know and love. Uh normal logic, things like implications, things like contrapositives, things like you know, conjunctions and disjunctions of statements. I'll explain what all this stuff means if you're not super familiar with it.

Um all of these things that we know and love let us prove things that are useful. ZK proofs are not concerned with exact truthfulness. They are concerned with a fuzzier notion of truthfulness, which is this notion of probabilistic proofs. So, proofs have some probability of kind of, you know, being wrong or not catching the error that they were supposed to catch. So, one thing that we can do is we can take a step back and ask, "What do we require of logic to encompass these probabilistic proofs in such a way that we can talk about

both things in one framework?" And that is going to call this probabilistic implications or probabilistic logic. Um it is different from fuzzy logic if you're familiar with that cuz there's many Yeah, there's a bunch of differences there. Uh and it is somewhat different from kind of like kind of uncertain logic with uncertainty, which is also um about it's it's more about bounding uncertainty regions than it is about kind of this notion of probabilistic implications, which we'll discuss here. Okay. So, traditional logic. In classical logic, we have statements.

Uh so, let's call them P and Q, uh capital P and capital Q. And statements are either true or false. Okay? Um assuming the law of excluded middle, which we will assume for the rest of this. So, what are things that we can say in traditional logic? Well, we can say things like, you know, P and Q. What does that mean? That means that is that is me making a claim that both P and Q are true. Right? So, this is what's called an assertion in math. Uh there is no such Often there's no such thing as assignment in math. In math, when you write something, so you write something like a statement, and you say P, that means that you are claiming P is true.

Right? If you claim not P, if you simply say not P, then that means that P is not true. Right? So, this is important to to distinguish if you're using programming languages, which is like you want to check that some assertion is true or false or something like that. Um the notion that an assertion is true or false in math is not a statement itself. A statement is, you know, uh simply a claim that I am making. So, again, it's an assertion, not kind of uh a question here. Okay.

So, here another thing that we can say in traditional logic, which is that P implies Q. So, in other words, if P is true, then Q should also be true. How do we write that in logic? If we say P implies Q, then it's the same thing as saying the following, which is at a high level, not everything, P and not Q. So, it is easier to understand the opposite of the statement, which is, you know, P So, P implies Q is the same thing as saying uh the following is not true, P and not Q.

Why does Why is this true? Just if you think about the truth table, P implies Q means the following. Whenever P is true, Q is also true. If P is false, we have no idea whether Q is true. So, that's fine. Right? That's the only thing this means. But, whenever P is true, it must always be the case that Q is true. So, the way of writing that in logic, if you kind of work out the truth table, which I recommend, it is simply saying that P and not Q cannot be true, which is exactly what we have written here, which is not parentheses P and not Q.

So, it cannot be simultaneously true that Q is a false statement, yet P is a true statement. Okay. And, you know, one consequence of this, which we know and love, is that if you have two statement three statements, and you have P implies Q, and Q implies T, then you know that, of course, you can chain the implications together to get P implies T, which is the last thing. Um see the homework for how to prove that using just the definition of logic provided here. So, okay.

Those are kind of the two big things that we're going to use from logic. How do we think about this probabilistic notion of proofs? So, at a high-level, zero-knowledge proofs will deal with this notion of implications with this additional notion of error. Right? This notion that like somehow you can screw up and not catch a liar. With very low probability, but you still can. Um so, one idea here is, okay, let's try to take that notion and codify it purely notationally. So, let's try take that idea of proofs can screw up in some way or another, and codify it in some simple notation that lets us kind of have the same like logical rules, like lets us use the little lizard part of our brain that

deals with logic all the time, and apply it to the these kind of slightly weirder proofs. So, that's that's the idea behind kind of this what hopefully is powerful notation. And so, we're going to relax this notion of an implication to a probabilistic implication, which is, in other words, an implication that has some probability of being false. Okay. So, to concretize that, in zero-knowledge protocols, you one makes a statement, right? So, you say something like, "I have checked that some entry of a vector is equal to zero." Or that some polynomial evaluated at a random point is equal to zero.

The The point is that that question, that statement depends on randomness, depends on some randomness that we have. You ideally get it from a coin toss, but often you get it from something like the Fiat-Shamir transform or something like that. If you don't know what these things are, don't worry too much, but the point is there is this notion that a claim that you make in zero knowledge depends on the on some randomness that you draw. So, we write that in our notation as P depends on randomness R, where randomness R could be, you know, a number randomly drawn from one to, you know, 10 million or something. We write that as P sub R.

So, it will depend on some randomly drawn R from some distribution, which we will be very clear about whenever we talk about these things. So, in other words, P sub R is true or false depending on the randomness that is kind of given to us. So, in a traditional implication, we say P implies Q if, you know, kind of the thing we discussed previously. If simultaneously P and not Q is not true. The same thing is This is the same thing as saying like an implication does not hold if there exists some time where P and not Q are simultaneously true. So, a relaxation of this is, okay, maybe we don't want it to all to like all essentially never be the case that P and not Q simultaneously hold. We want it to be the case that P

and not Q simultaneously hold with very low probability. I'm going to call that probability P. Right? So, we say you know, P implies Q or P sub R implies Q sub R prime with probability kind of with error at most P if the probability that, you know, those two things are simultaneously true, um is very, very small. It's less than or equal to P. And of course, if the probability that that is true is zero, we recover the original definition because if the probability is zero, we're claiming that it never happens.

Okay. So, to do this, we'll define some convenient notation, which will be kind of given by this, which is we say P sub R kind of implies Q sub R prime with error at most P, uh which we write in this form, uh whenever kind of the probability of P sub R and Q sub R prime is less than or equal to P. And R and R prime are randomly drawn numbers from some distribution, which we know. And here is a crazy fact is that this definition lets us chain implications. So, remember, these are random statements. These are statements that can be wrong with some probability. And what we're saying is that by defining it in this particular way, we can take statements that are true or

false with some probability, right? And other statements that are true or false with some probability and chain the their implications together with an additional error. Um one fun exercise is to note that if the error of that if the possibility of error of those statements is zero, right? Then the we recover exactly the traditional notion of logic, right? So, the implications hold exactly. Uh and indeed, you know, 0 + 0 = 0, so therefore the implication has a final error of also zero. Um we can also, of course, take contrapositives. So, uh classic thing to do is, okay, we have two statements, P implies Q. Uh this is same thing as saying not Q implies not P.

So, that's these are very useful for proofs. Uh and there's many, many other things that we can do, one of which we'll see in the homework uh and we'll kind of complete a proof uh of the paper that we left unsaid. Okay. So, the point is, at a high level, is we can create a basic logical language that is probabilistic and consistent with traditional logic and you know, whenever that holds. And it acts, you know, like some sort of syntax for some specific rules that we have with probabilistic proofs. So, we can take statements that are probabilistic, not just true or false, and combine them together in a variety of different ways and have them imply other things. And you know, if we follow the arrows, if you remember from this previous thing, if we follow the arrows here, you know, at every point you simply accumulate

some extra error whenever you perform these kind of fuzzy or, you know, probabilistic implications. Right? And the final proof will have a error that kind of sums all of these things together. And so, the point is um you can think of this as kind of like a proof-carrying, or sorry, a kind of error probability-carrying protocol. If you start with some statement A, it implies B, and that thing implies C, and so on and so forth. That's like a traditional notion of a proof, but each of these things has a probability of being false. When you add them all together, you get out a certificate that says the probability that the first statement is true, yet the last statement is false, must be lower than, you know, the sum of all of the individual implications. And so, in some sense, you can think of it as like,

if you're familiar with, you know, formal languages, you can think of it as a as a program where you add everything together, right? And then spit out a certificate that says, "Your program is correct, and also B here is a probability that your zero-knowledge protocol, you know, here or here is a soundness error of your zero-knowledge protocol." Or something like that. So, an open project for anyone who's very interested would be to formalize this in a way that is clean and clear. Okay. So, where do we go from here? This is finally the last of the slides. We have all the basics. So, I've just lectured at you for like the better part of 50 minutes. So, apologies for that, but hopefully it it'll be useful for what's coming next. Um what we're going to do is the next lecture, we're going to rewrite a lot of the basic tools of

succinct proofs in clear ways that are very general, that depend not on, again, things like polynomials, but that depend on things like error-correcting codes that are, we'll see, more general than those. Um and then that means we'll finally start saying real things. You'll finally see kind of, you know, lemmas like the Schwartz-Zippel lemma and things like that appear in a very different form, um indeed in a more general form than kind of one sees in in these proofs. And we'll hopefully do all the do all of that with very compact and one might say synched notation.

And then for FYI, the homework will be released after the lecture and the Q&A. So, thank you all for attending. I'm going to pop over to the questions. But first, I will say something quickly about the homework is the homework is long and I don't have solutions for it. So, what I will do is I will make a GitHub repository. I encourage everyone to do the parts of the homework that seem the most appealing or feel the most difficult to them and feel like the most useful. You'll probably have an idea of what this means.

And what I will do is I will open up a GitHub repository with a skeleton set of answers. And people can do pull requests for each of the individual answers. I will probably edit them heavily, but it'll be kind of a collaborative like let's come up with the solutions together for a PDF. And the point is of course if you, you know, don't know how to solve a problem and you've tried for a long time and you have no idea. Ideally, there will be some PR or hopefully a merged PDF that contains all the solutions at some point over the next few weeks. It is long, so I don't, you know, I'll be very impressed if anyone finishes the entire homework by the next set of lectures.

So, just pick and choose your own adventure and, you know, if you have questions about what things feel hard and stuff and which exercises you recommend, I'm I'm happy to to oblige on that. All right. Thank you all and let's switch back to Q&A. Cool. Um let's see. So, what does error look like in binary logic? Um not sure what that means exactly, but um Okay.

So, where is this P So, sorry, Mahmoud, I'm not fully sure I understand the the question. Here, P plus sir, Q&A. No, there's not. Okay. P plus P prime is also in P and Yeah, I can actually your computer is telling them. So, if people feel like it, maybe you can jump actually on, you know, ask directly if you want cognizant that the session is recorded. So, if you don't want people to see your face, well, don't do it. But, yeah, if someone wants, by the way, just request sharing your audio and video and I can talk you up on stage. In the meantime, yeah, Guillermo, maybe you can continue.

Yeah, I'm also happy to read the the questions here. So, there's a question by Philip which is the probabilities R and R prime means we don't know what value we will take on for P and Q, correct? So, one particular say I haven't Again, all of this will be much more concrete as we actually start doing proofs using this toolbox. But, what it means is P sub R, for example. Let's say Let's say we want to check whether a vector is zero. Right? And the vector is actually not zero, but it's not zero at a very small number of entries.

I would say P sub R set is is simply the statement that the vector is zero at a random entry R. Okay? So, that statement, if it's true enough times, will mean that the vector is probably zero almost everywhere. Right? But, the statement has a probability of not being true. Right? Uh in fact, the probability is the number of non-zero elements divided by all the elements. Right? So, that's that's what it means. So, so, the reason why a statement might depend on randomness is in some sense you can think about it as like someone's trying to fool you, but you don't have time to check the entire solution. You can only check a few elements of the solution. You can only check a small part of the solution.

You do that randomly. Right? So, you you flip a coin and you check randomly. And the probability, you know, PR is roughly speaking, if it's true, then it's like, okay, my check passed. Um but, if it's not true, then my check failed. So, the question is, what's the probability that your check fails given that you know that the statement that they're making is not true? All right, that's kind of like the the high-level idea behind the probabilistic implications. is you don't have time to check a a thing, so the statements depend on some randomness, and the probability that the implication is not true should be ideally very low if the statements do depend on the randomness.

Uh and let me now post the homework, which is here. I brought it Mahmoud. Uh I guess maybe you wanted to clarify your question from earlier. Mhm. Yeah, do you hear me? Yes absolutely. Uh okay. So, my question is if P implies Q with a probability P, and Q implies T with a probability P prime, then you said that P implies T with a probability P plus P prime. Yep. But if I think in my logic it should be multiplied because like that increases.

That's why this is my question. So That's a great question. It's absolutely a phenomenal question. So, the simplest way to kind of think about it is like you can think of Q as being kind of an intermediate variable. Right? So like Q might be true, or it might not be true. Right? You have prob- some probability of screwing up from the first implication, right? So, maybe the first implication is actually false.

Right? Um but the second implication actually turns out to be true. Right? Like like the point is the the way to think about it is like you have you have prob- some probability of screwing up each implication. One of them is P, and the other one is P prime. So, maybe you don't catch someone in the first implication, but you catch them in the second implication. Uh or maybe you like don't catch someone in the second implication, but you catch them in the first implication, right? So, Q might or might not be true. Right? Um yet the the final implication like turns out to like evaluate to true for whatever reason. But you're not checking the middle implication. So it's it's it's it's kind of weird, right?

Like the point is like there are two places you can screw up now, not just in one implication or the other implication, but indeed in both. So with the the multiplication thing comes from the fact that uh because of a slightly different fact, which is if you have two things, which is PR and QR prime implies T. Then you can multiply the two elements if R and R prime are independently distributed. That is true. So in other words, if I check a claim over you know, it could be the same claim, it could be a different claim over kind of independent randomness, then the probabilities do actually multiply because if they're independent, right? Like in some sense there you have independent times that you can catch this person for lying.

It should be less, less probability. That's right. Yeah, so in that case it's definitely less. Right? But in the in the former case it's not true, right? Like one implication that the the the point is like by kind of having these statements chained together, you have more places that you can screw up. Yeah, right? Like as you go, there's like there's like more places that you can be like, oh crap, like I not only have an error of screwing up, you know, statement one, but actually have an error screwing up statement one and statement two potentially or statement two, sorry, not and. Right? Like these are the two statements that I can also screw up now. Does that make sense?

Okay, yeah. And in a sense that improves soundness right? Um that reduces soundness. Reduces soundness, okay. Right, so P is the probability of error, not the probability that you are correct. Hmm, oh okay, I understand now. Right. It's the probability that the implication is not true. So yeah, but this is a great question. This is like these are the kinds of things that and and it once you work on you know, once you'll see the examples and stuff, which this is why this lecture is a little funky, uh you'll see like, oh like there are actually places that I can screw up that are extra and you can see it in a very concrete like animal way that you can be like, "Oh, crap. Like, yeah, that's right."

So, hopefully it'll make more sense next lecture, too, once you work with it more. It's a bit magical, so I apologize. Do you have a bit more time to bring us kind of on stage? He has a question as well. Absolutely, yeah, yeah. I am chilling until a little bit later. So, like 15 minutes. Okay. You can take your time. But yeah, I was actually a bit annoyed with this P P prime as well cuz at some point maybe it's going to be more than 100 and it was a bit low. Oh, sorry. Wait, you have a There we go. Thank you. Sorry, what was the last thing you said? Yeah, I was confused about the fact that you can add the P P prime etc. with many implications and it ends up being more than 100%, which is a bit That's right. That's right. So, it's

only a bound, right? It could be bad. Like, if you if your implications are very very like like have very bad error, of course there's a there's the you know, you end up with things that are above 100%. You can always cap it at 100% if you want, but it's not going to help you, right? Like, it doesn't It's just like I don't know what the probability of error is. Yeah, of course. Sorry, go ahead, Skanov. Up to you. You need to unmute. You're unmuted, by the way, just in case. Do I unmute myself?

I wonder what the question was. No worries. I I don't either, so. So, I guess people are eager for the homework, so I hope you you get that. posted it. So, uh hopefully it's good uh Well, I guess what what Skanov was uh Oh, never mind. Okay. Um Yeah, for sure. Um so, for anyone who is doing the homework, um please, if there are any weird mistakes or something feels really hard or something. There are some problems that are supposed to be hard, but they're not supposed to be impossible.

So, if anything feels like really hard, please like message me on the Discord and I can either add a hint or rewrite it in a way that's a bit clearer. I just literally wrote the homework while I was writing the slides and I was just thinking like, oh, what would make a good homework problem? Um some of them are actually quite difficult, but none of them should require a solution that is longer than about a paragraph or two. So, that is a one big thing to keep in mind. Okay, anyway, that's also why the Discord is here. I mean, that's a study group, right? So, let's uh let's study together. Yeah, post your questions. That's also the purpose of this. And uh yeah, we'll debrief after.

Uh okay, well, if if there is no more questions, I think we're going to call it today. And uh yeah, anything coming coming uh coming up, feel free to ask in the Discord, too. And uh I guess we will see each other again in the same uh virtual room uh in a couple days. So, yeah, I will create the event for next week later, but yeah, the next one is going to be here as well, same link, same place in 2 days. So, yeah. Have fun, guys. Looking forward to checking the homeworks as well. Yeah, thank you all for for attending. And again, just ping me on the Discord if there's any questions or anything like that, but I highly encourage you to do the homework cuz it'll we haven't done anything concrete here and it's worth doing some concrete things with some real paper. Uh tomorrow or not

tomorrow, Thursday, we'll do some real concrete things uh that will actually hopefully also help kind of you know, settle all of the stuff that we talked about today. Cool. Awesome. Glad you could make it, guys.