Beginner's Guide to zkSNARKs 3: Math (to get to PLONK)

Transcript

helps welcome to the third session I'll quickly go over the intro stuff as I have done the past couple times uh follow along in the online course material for for this session and the next session you might want to refer to the online material a lot more there are visuals in there that we made that aren't in in the presentation because we can't put them in that can help get a bit of a better of understanding or intuition for how some of these objects we're going to see actually work and I'm going to expand more on why that's so valuable yeah if there are any issues um mention in the chat side's working unfortunately so I can see questions as um clarification nothing against to

me if you have any questions now's the best time to ask them also still from session one because of course it wasn't easy to ask questions last time um I think a question is being written so I'm just going to wait uh the online material link is uh there's this link with hmd with all the stuff and the the link to the book is there as well that's probably the best place to start uh okay cool then seems like there's no questions from the previous sessions or lingering things that

weren't entirely understood so we'll just press press ahead welcome to lesson three um oh just prior to actually cont we want to discuss the meta of why we're we're doing this uh to work in the zedk space or cryptography in general um you know I don't know what your backgrounds are or where you're looking to go but this is a zedk course and it's not General cryptography but if you're interested in ZK you might also be interested in general cryptography there's kind of two hard skills that you probably want and be know very well and one of the reasons why it's such a job and command because it require you hard skills like learning one of

them obviously math and programming people who are very good at the ma um generally speaking they're probably in Academia and things doing research and it's very hard to become to get a role like that unless you go down that exact path of somehow doing a PhD or just finding lots of research jobs um and I think there far fewer and for people who just do programming you can't it's not really wise to code cryptography without knowing the maths as well one you can't what the paper says or the things it talks about because it's written in the language of mathematics and two there's lots of things that you have to know in order to make sure what you code is safe and secure so you do want to know both of

these skills to be doing this kind of job because most of the ZK jobs are applied ZK it's take a look at the space look at the different proof systems look at the different protocols try and figure out which ones to use try and optimize parts of it for your own system or create things from scratch and code it obviously so you do want both of those skills um I guess some people come out of University with both of those skills but I think by and large most people come out with one of those skills and learn the other I think it's easier to you know study maths and then learn programming afterwards um but uh yeah of course you you know if you all already have one of the skills you're not going back in time but the better you know the math and the the better you understand

it fundamentally the easier all this is like without the maths if you look at these papers they just mean complet like absolutely nothing even with like a strong mathematical background once you start reading these papers they're very tough because there's like theoretical computer science type stuff um that's hard to understand but the better you have the the these fundamentals down the quicker you can make your way through things and uh be a better Z k um applies a person uh the things we're going to cover here

in in this session on Thursday we'll do some other stuff then uh is something called modular modular arithmetic something called groups something called fields and something called pols which we actually touched on briefly before um these are like the most fundamental building blocks some of the definitions I think most of these definitions are actually fairly straightforward but you can just do so much with these objects that there's loads to learn we're only going to touch on kind of the most fundamental definition aspects of them if you go on to do Advanced courses you will you want to know these these objects like really really well and they'll just be doing much more advanced things with these

objects showing much more uh special behavior of them so the you know seeing these now will be very helpful before you go on a a harder course and some of this hopefully should actually be familiar to you if you're a programmer the mod arithmetic part should be clear there's actually I I deleted it off the list but we'll do a fifth part as well called the Schwarz zipple Lemma and is a very important theory that actually um gives us the percentage of proof of the probability of a proof passing okay um and I I discussed why we chose PL in the previous session so I'm not going to discuss that again it's just a

very good one to start with uh and we're also kind of choosing the math based on going towards understanding plon specifically the different proof system will require different maths but by and large there's like categories there's like clonk like proof systems where if you know this math you know that stuff and then there's a bit of overlap with kind of starks but you you know you need to learn some other stuff for the Starks but once you know one of them you could the other kind of Stark like systems you can understand much more easily so it's not like you have to learn loads of new math for every single proof system there is a lot of overlap mod arithmetic is the starting point and it's sometimes called clock maths and um do ask me questions that parts of it

aren't unclear because this is I the kind of thing I did so long ago and was so fundamental I can't necessarily remember remember the things that people struggled with this when they first leared it you know even I would have had issues when I first learned it too um but basically you're going to count up to a number and you don't you just hit enough limit and instead of going beyond that you're going to Loop back to zero and if you're a programmer with with like I8 or U 32s or any integer value you know that you'll wrap around so with an I8 you'll get to 255 and instead of going up to 256 you'll go back to zero and that's the exact thing we're going to have here but we're kind of defining it in a mathematical way as an actual

sort of set so this is the kind of picture thing that's an animation on the the web material so it' be very helpful to see the the animation and how you step through but we basically have uh a part of the number line from zero up to some number and it's a whole number like 11 in the image it could be 0 1 2 3 4 and with this is not a continuous um it's not continuous um length you know we don't have 0.1 or any of the numbers in between we just have the whole numbers um yeah I mean in programming terms the the minus one index will be the last last number so in the set 0 1 2 3 4 the minus one would be the four and

in the 012 up to 11 the minus the last index would be uh the number 11 uh well technically 10 actually um yeah and this is kind of it so I'm going to sketch this but when we count up instead of counting past our limit whatever we set it to we just loop back around where's the thing there we go so this is called modular arithmetic if we take this set I gave 0 one 2 3

four this does have five numbers right because we start at zero we even though it goes up to four the fact that we start at zero means we have five numbers alternatively we can sort of draw dra the number line that's the zero and I've got to decide here whether to draw a five or a four because it seems like these things aren't the same but because we're going to wrap this round into a circle zero and five are the same number so even though this line goes zero one 2 three four we not very well spaced

obviously three four even though it goes up to five it doesn't include the number five because five is treated as the same thing as zero uh one two three 4 One 2 3 4 so if we're going to count on this we'll go 0 1 2 3 4 is that if we set let's say we want five numbers then

set five to be the same as zero and you'll see here I use in this equal sign it has three lines and that's like a specific mathematical notation that we use in these in these groups because if I'm to expand that out we use this under the scenario zero mod you know mod arithmatic zero mod 5 this zero mod 5 is telling us that in the set that we're working in we're treating five to be the same thing as zero now if you if it's your first time seeing this kind of relationship it might just feel strange and you know out of the blue and a little bit

uncomfortable and you'll just get used to it like you know there's nothing more there's nothing really deeper going on it's just that we just save we just treat five as the same thing as zero because we imagine it as this clock and there's no reason it had to be five we could choose any any number we could do a different example with a so this previous one is called the the um like Mod Five kind of example we could do a a mod 7 example and then of course it would go 0 1 2 3 4 5 six and we could say it's seven but actually we know that's the same thing as zero mod

seven similarly if we start to do more than just count if we do our normal operations that we're used to from normal maths let's say 4 + 5 well that equals 9 but nine isn't a number in our set so we can't say that it equals nine so we got to do something else and we can also we can see that we can just remove well not remove but we can decompose this because 9 is 7 plus two but we know that 7 is zero so this will be congruent to two mod 7 yeah so all our normal math still applies we can add and multiply numbers and still be in our set

uh similarly if we do a multiply four * 5 obviously we get 20 + 7 + 6 well we can but um we can just do it more quickly by seeing the number of sevens which is 2 * 7 + 6 but we know that all the sevens are the same thing as zero so this is just the same thing there six mod seven yeah so if we draw we draw a little our clock as we had before we have

zero one 2 3 four five six one two oops two three four five six then if we're to do the the the nine example we count up to four and and then we go round five steps we go 1 2 3 4 5 you'll see that we ended at the two which is why we had this two mod 7 okay now I don't know your backgrounds like if you've done if you're programmers and you work with you know I8 and things like that and you've seen this kind of thing before this might be extremely easy for you um but we're defining it much more clearly in in sort

of more mathematical ways it's called arithmetic we have this notation with this you know triple line equals which we say it means it's congruent to and we Define the group we're working in to be mod mod five okay um so we're go on to our second object and these objects actually just kind of actually keep building on each other and getting get more complex so groups take mod arithmetic and what they do is they add more structure to it mod arithmetic sort of told us the

relationship between the numbers um but a group takes a set which is the the mod arithmetic set itself and then it adds some other things um it adds a bilinear operation and an identity element which sounds like gibberish but it is like very real mathematical terms which will make sense to you soon but this is a very abstract way to think about this stuff which is also why it's so valuable um so what are the objects inside it I said we had this set of numbers we can do 0 1 2 3 4 we can go 0 to 10 um you know which would be 11 numbers or whatever else we want to

choose we'll have a binary operation and what that means is it's an operation that takes in two things which is why the binary part of it is there so addition is an example binary op operation you take in two numbers and you add them together multiplication is another example but in a group we only have one binary operation we'll choose which one and it might seem like that's it in terms of the the types of operations but you can Define arbitrary binary operations for example you could Define a power one so if you take in A and B you'll do a to the power B you know like 3 comma 2 would be 3^

squ and that has very different properties or you could just modify a normal um you know addition multiplication instead of doing a plus b you could do A+ 2 B which is still a binary operation and it's not addition as we know it but it is still something we could put in for our for our group and then we have something called an identity element means that when you put it in the binary operation it does nothing okay so that's much easier to understand with an example what does nothing under addition well that's the number zero because 3 plus 0 is three

any number plus Z is the same number that you started with um yeah and um if arbitrary operations the way multiplication is made from addition um we can see multiplication as being made from addition but uh yeah you I mean you can make it in different ways like arbitrary just means that as long as it's a binary operation it doesn't really matter what it does you know even if it does something really odd or boring um it just has to be a binary operation so arbitrary is also a word used a lot in mathematics and that just means that you have like a huge set you

know maybe a finite set that you can choose from but the point is it doesn't matter which one you choose as long it is something from this area you know as long as as long as it is a binary operation any of them doesn't matter which um you know that's the kind of thing you have to choose there for example if I say let's choose an arbitrary um integer so integers are all whole numbers positive and negative then an arbitrary integer just means any one of those numbers you know it doesn't mean 0.1 but it could mean one or two or three or minus 100 or anything so there math has a lot of terms that mean very specific things that bit by bit you will get to know if

you read mathematical papers there will be lots of this terminology that bit by you'll pick up on and it's what makes it so hard to read in the beginning because lots of stu stuff is very T to read and just very tough to decipher meaning from um yeah so identity element I said that zero was the example for addition because it does nothing and maybe whil I sketch this out you can think of what the identity operation for multiplication would be so let's move over to do our groups um so we got our

Set uh we got set Banner operation and element so let's say that set was the mod Edition and I say the set was the mod modular addition but like the the set is actually just the numbers modular addition applies a bit more structure and tells us one way that we can wrap these numbers together um but it's actually our binary operation that's going to determine uh how things work and in our example we can do this

this plus you know the addition and the identity element like I said it has to be the one that does nothing which is going to be zero right and we'll actually usually write these together in like kind of brackets 0 1 two three four addition and zero and this is a group is those things together which again before the first time you see this stuff it's very strange because it's very abstract um but this is what a group is and you know we can play around with s of things in it we can do the 0 + 2 well that will give us two we can do the 1 +

2 well that give us three we could do the 3 + 4 well that gives us seven but that's not in our group so that's something we're going to have to do something about and because we got five things in our set this is the same as 5 + 2 which is the same as congruent to two mod two sorry not not mod two mod Mod Five yeah we could do a different set we could do 0 1 2 3 4 five 6 so we've got seven elements in it and we could instead

choose multiplication which we usually use a DOT for rather than the little X um but then there's also the identity element of multiplication if you thought about it a little bit you probably realized it was just the number one the number one because under multiplication one does nothing 2 * 1 is 2 1 * 6 is six so it's the one that that does nothing okay so those are the three things that have to be in our group but that's not actually enough to be a group

yeah a group contains these three things the set the binary operation and the element but a group has more structure than this and I'll get to those those things now but this first group the zero to four with addition and zero that is a group but this second one is not actually a group it will fail one of our tests so we're now look at what those requirements are to be a group and first we got to define something called an inverse

element I Define the identity element if you remember it's the thing that does nothing under the operation but our inverse element is going to kind of get you to the identity element um so that sounds very odd um I talk about it a little more but really once I sketch this out that will be the clearest way to understand these things um but so the inverse element gets you from your input to the identity element so if your identity element is zero it has to be and addition is your um binary operation it has to be the thing you add to this number to get to zero so if we work in this first

group that I said was actually a group mov this out the way then let's see what's inverse element of two but what's the inverse element of two um it will be the number a so a is just to stand in for a generic generic number it will be the

number a such that and this little phrase such that is we use it tons in mathematics to kind of specify some requirement it will be the number a such that 2 + a = 0 yep so we're looking for the the number that satisfi satisfies that property and as sesa that pronunciation is Right noted in the chat this is going to be the number minus two because 2 + - 2 is

zero okay but this does leave us a little problem can anybody identify what the little problem is if we use minus two as our inverse element yeah yeah as you've noted minus two isn't in our set of numbers we got zero we've got one we got two three and four so we can't use minus 2 as far as we're concerned it's not really a number that necessarily exists in our group or potential group we haven't proven that it's a group yet um and as Kim noted it will be the number

three and why is that and that's because we actually just have to satisfy this property and if we check the number three as suggested if we do 2 + three well that equals five which again doesn't seem like zero but under our modular group it it is zero because we're under Mod Five okay so that's what a um an inverse element is similarly we can try and do it under this multiplication this isn't a group but we can still maybe find the the right thing um so let's say we want to find the

inverse of oh just before that let's just do some notation quickly so I wrote minus two like this here that is generally how we will denote our our inverse element if addition is our operation the inverse of will be the minus so two will be paired with its inverse will be minus um but we have to note that minus 2 is not in our set but we can note the inverse element as being minus 2 and then we'll have to find what that element actually is uh and under multiplication let's do three under

multiplication we can do divide by three or one over three or 3^ minus one they all mean the exact same thing um but yeah just note that this number the 1 over 3 or 3 to the minus one it doesn't exist as that number in our set in the same way minus two doesn't exist in our set but we can still denote the the number that has that property with this notation but yeah let's try and find a multiplicative um in terms of inverse multiplication

I'm going to get to that in a minute but let's just first try and find an example of a multiplicative inverse this another term we can use you know we can say this this minus 2 is an additive inverse because it's with the binary operation and with the multiplication it'll be a inverse let's say let's find 2us one I will usually use this power to the minus one to denote a multiplic multiplicative inverse uh what does that mean it means this means we have to find a such that 2 * a =

1 okay and now of course you might think a equals a half you know the two to inverse but the again these don't exist in our set we have to we can brute force it we can check zero and 1 and two and three and four and five six which is essentially what we're just going to do but one of these should hopefully be that number and if we but bearing in mind that we're under the condition we're in a mod like the modular arithmetic set we have that seven is congruent it's basically the same thing as zero so we could just for example write out the mult multiplicative table we're

could do where it goes two and then it goes four and then it goes eight and then we might pause here and say well 8 is the same thing as 7 + one which means it's congruent to one mod 7 which is the thing we're looking for so 2 * 3 sorry I I did hours there that that should be times four I I skipped out six in this in that list uh 2 * 4 it gives us eight so four is the same thing as to inverse okay so these do exist

multiplicative inverses do exist um and I see you're talking about rings as well so yeah if you know that stuff that that's very good we're going to get onto that more complex stuff very soon so that's what an inverse element is just kind of the definition so what does it mean to actually be a group aside from that setting where we have the set we have the operation and we have the additive sorry the identity element we have two main requirements every element has to have an inverse um and every element that we can make using our operation has to also be in the

set so in our first example if we add all these numbers together we know we can get back to numbers between Zer and four because it's modular arithmetic but in terms of additive oh sorry yeah additive identities we do have to prove that those all exist as well and we can we can just brute force that now we have um how do we get from one to zero well that would be minus one equals it seems like you guys know this decently well so I won't go into too much detail but minus one will obviously just be four two we just did how do we get from two to zero well minus two we know that is three uh and then these actually kind of

wrap around where there'll be the inverses so so opposite so how do we get from three to zero well it's going to be minus sorry minus 3 is same as two and for four to get to 0 - 4 is going to be 1 because 4 + 1 = 5 which is congruent to zero uh okay to actually answer your question if we don't have inverse multiplication we have a ring um the the the difference between a group and a ring is in our group we have one binary operation and one identity element um in the in the ring we're going to have

two binary operations right because in a group we're basically just choosing addition or multiplication or whatever it is but in a in a ring we'll have two operations available so we've essentially just shown that this this group is actually a group because they all have the the additive inverses and everything we can add together is still in our set but I said that this isn't a group and does anybody know why okay no comments yet but this isn't a

group it fails our group test because not every element has a multiplicative inverse you know if we do 0 * by a equals 1 what is a yeah this this a does exist you can't multiply something by zero and get to one so as Sir said you can't like divide by zero this would be 0 inverse which is one over Z so we can say that we can't divide by zero to get back to one so that's why this isn't a group but if if we if we remove zero is it a group now now we have 1 2 3

four five six multiplication and one is the identity element would this be a group yeah it is it is now a group okay I mean we can we can manually show this we can one's inverse um is one itself because 1 * 1 is one two well we just did a minute ago U what was it it was four and we can find it for each number what would three inverse be uh three would be what would it be it would be five because 3 * 5 is 15 which is 7 + 7 + 1 and we'll get rid of the sevens and then

four we can do this quickly because it'll be the opposite thing like this will be two and five inverse will be uh three and six six inverse will that be um well there's no other pairing for it actually itself because 6 * 6 is 36 which is 35 + 1 okay so to be a group every element has to have an inverse element and it depending on that will depend on what the the B operation is I'm just going to wait for this question and then move on so yeah if you guys have seen rings and things like that will probably quite

basic for you but the better you understand it the the better and group theory is like you know people who study math they'll do an entire course on it and there are much more advanced courses because you can do much more advanced things and have like much more special properties about them in different places um you have groups of matrices uh well elliptic curve stuff will be a type of group we won't be working with normal numbers but it will still have the properties of a group so this set you know we're working with normal integers that we know know very well and it seems very easy but there's no reason why we have to do actual numbers a group is a generic thing and that set sets can be generic so one of the when if you study

group Theory like one set you'll look at is rotations because if you rotate phone if I rotate this like that way that's different to this rotation and you can see that these will actually make a group because you can have as the identity element sort of like being flat like this or let me do it this way way being flat like this and if I do this rotation once I do it a second time I get back to this identity element this kind of starting point right so there is no reason why the set has to be numbers it's just like some weird abstract set that can be anything and as long as it has these properties every single Theory we have

about groups will apply to it so rotation rotational things I think I used in like quantum physics like quantum physics will be using groups in a variety of places because it's noticed patterns you can have groups in forms of matrices like they're very generic objects but um so yeah the more places you'll see them the better you'll be with them um in terms of your question with Modo not being the operation of the group yeah cuz I mean I introduced modular arithmetic to help you understand and how we will treat uh how we will like you know maintain

what what we do in our own set um it's it's it's it's like an equality relation that we apply on our set to make sure we stay within it the mod the mod 5 01 2 3 4 is basically saying we'll take this set and have that five equals z that's kind of the the setup from it and that's how we know that additional multiplication will always give us something back that's inside that set because we have this simple way to work um yeah it helps us Define our our

binary operation a little bit as well by telling us what we'll get back out um it it is a it this goes a bit into like some of the deeper stuff that's happening and I can't answer you perfectly well but I think it's more a part of actually the addition operation we can the binary operation can be defined in any way I can Define let's do this uh star thing this is my own operation

and I will just Define it however I want and I'm going to say zero and one will give us two and I'm going to say that if you do it the other way around it will give you three okay and if I Define every single possible combination this is a binary operation will it make it a group that depends on on like how well it's defined so the the mod arithmetic part is is more a part of uh I I think is more a part of the of the binary operation because the binary operation if you do 2 plus three sorry 3 plus 3 is six well the addition actually is

basically just saying 3 + 3 is 1 yeah yeah actually let me think on that a little bit it's a good question it's been years since like I've covered the the pure Basics we work with this in such implicit ways I've never I haven't had to question it in in like five years um maybe maybe no maybe I I I'm wrong maybe it's actually a part of the set so with uh 0 1 2 3 4 yeah we we can do it on the congruency

classes so it's actually Zero Bar and one bar and two bar and three bar and four bar so we're not actually working right this is I think this is actually the correct thing we're not actually working with the number 0 to four we're working on their on their uh equivalence classes and zero is the set of all things of the form 0 + K * by 5 um such I use this c on it mean it means such that in this formulation such that this is like normal mathematical notation as well such that K is an

integer so this Zed thing like that originally it's from the German number sorry German name like zalin which just means like integers so all whole numbers positive and negative this Zero Bar contains everything of this form so that's zero that's 5 that's 10 that's 15 that's minus5 that's- 100 you know all you know infinite possibilities are represented in this set similarly with one it's going to be exact same but this is going to be replaced by one so um yeah it's not actually in the operation itself it's in the set that we're working with okay but good good

question okay yeah so here's a question will we always get a group like is there a simple way to know whether we'll always get a group uh when we do whole numbers up to a certain point so that you know 0 1 2 3 4 You Know 0 to 4 is or 0 to 7 or 0 to 11 or 0 to a million is there an easy way for us to know whether we'll get a group um don't have yeah I think we we don't have too much time to dig into it but if it's addition hopefully you'll see that we'll always get a group should be straight because we can always have the additive inverse easily um in multiplication um we do have to remove the zero we can't start from zero we've already seen that um but we will get a

group if the number we go up to is prime okay that's something that we can prove uh and that's also why you'll see that Prime's used in so many places it's because it gives us this special property that one two three all the way up to a prime number that will always be a multiplicative group okay so if we say that we use a prime here usually it's because of this fact specifically it means it gives us a group okay so going to speed up a little bit so we've got fields and you were talking about Rings earlier and rings and fields are kind of like if you get two groups

and smush them together um we have the set but instead of having one operation we'll have two operations and instead of having one um identity element we're going to have two one for each of the binary operations uh similarly with rules when will something actually be a field well everything has to have an inverse it has to have an additive inverse as well as a multiplicative inverse except for the number zero because it doesn't have it can't have a multiplicative inverse and let's just sketch a thing so the thing we've already worked with a

lot Z 2 3 4 uh we'll do addition and multiplication oops 01 to imply the uh the identities this is a field and we'll we'll have this notation F5 because it's the field with five elements in it okay and we already know that everything has an additive inverse and everything also has a multiplicative inverse um except zero doesn't ex you know zero inverse doesn't exist but because that is the additive

inverse it's impossible for it to have the the multiplicative inverse so that's that's fine okay so groups and fields are quite similar but we'll just smush them together two groups together again prime numbers um because of the thing I just said if if we do f s or F nine there s 11 you know if we put a prime number there it's always going to be a field um but if if we do the zero up to nine so we have 10 elements um it won't it won't be a field yeah so F10 doesn't really exist

okay so the point is we see the word Prime in a lot of places and it's because of this it's because of this property we know we'll get a group from it or well a field also from it um yeah so field is the group with two groups much together you'll have two operations and we're we're only really in cryptography we're just interested in finite fields and finite groups you can have infinite groups but we can't work with those properly in cryptography okay

so we're now just going to touch on polinomial again and then I'm going to give you a low down of something called the Schwarz zipple Lema which is very important for plon um we actually already looked at polinomial we said that you know we've got 4xy + 3x - 5 we can have multivariable we can have X and A Y and a zed um and you know any number of variables in plon we're only interested in in a single variable so we'll just do like X's but the number in front as well also uh is also going to have a have a limit we have four in in this example we have a four and a three and Min - 5

under our circumstances we're only going to allow coefficients that are from a field so if we work in f11 you know the field with 11 elements in it then the four is fine and the three is fine but we can't have minus5 there will be an equivalent since since 6 + 5 is 11 which is the same thing as zero in in our in our modu arithmetic set um minus 5 will actually be the same thing as six um sorry Kim I don't know if you're asking a question Kim if if you're saying you've forgotten the difference or if you know the difference now between rings and Fields no understood I haven't uh uh

explained the difference um and that's because like in cryptography we never we don't really talk about Rings because they don't have the propert they don't have the useful properties we want we want the things to be filled because they have such useful properties um I'm actually just checking myself quickly because I I'm I'm I'm pretty sure from memory that the ring is the same as the field but you don't have everything doesn't have to have a multiplicative inverse I think it has to have an inverse for all the for the first bing operation but not the second um so F10 for example is not a field but it's a ring

because uh because two * 5 two and five don't two two two doesn't have a multiplicative inverse um I can show you that quickly if you try and do let just do a smaller well yeah 0 one two up to nine so we've got 10 elements uh and we have that 10 same as zero one 10 yeah so yeah under this scenario what is what is the inverse of two well

two basically two * a equals 1 what is what is a under this setup a does not exist there is no such a two does not have a inverse okay so this can't be a field but it will be a ring um the reason why it can't be what why two can't have a multipli multiplicative inverse is because numbers can be one of two things they can either be a multiplicative inverse uh which we call a unit more generally or they can be something called a zero divis but because you can do 2 * 5 which equals 10 which is the

same as zero because you can get from two to Zero by multiplying it with a number from the set it means that it can't be a unit I'm not going to get into that that stuff because it's out of the scope like I said you like we never read about rings in cryptography or extremely rarely because they just don't have the properties that we're interested in they're not conducive to doing the things we want to do so in the ring you don't have to have a multiplicative inverse for everything okay but the polinomial um let's do that one 4x^2 + 3x -

5 4 x^2 + 3x minus 5 I said if we're working in F1 then four is in the set so is three which is fine but - 5 is not but we know that - 5 + 6 = 11 which is congruent to 0 11 which means that you know- 5 equals or is congruent to six so we'll convert this polinomial to 4x^2 + 3x + 6 okay so all these coefficients have to be from the field that we've we've set for ourl pomal and we refer to this more

generally all these pols we can Define what we represent with this notation f11 square brackets X this means like all pols of that format you know we can have 3 + 7 x um 53 sorry not 53 because that's not in f11 obviously 5 + 10 x to the A th000 and you know plus any other term but this notation means all pols of this format yeah this is what we just did

this notation uh we've got the term polinomial degree we did the minus that's fine the degree the degree of this polinomial is one because the highest power of X is is one if if we write on it X on its own it means that the power is one as you probably know here the degree is two here the degree might be a thousand because I've got this plus dot dot dot we don't know what comes afterwards but we know that it's at least a thousand right and I I've mentioned before but a lot of what we do in proof systems is is

polinomial uh representing numbers as polinomial checking that polinomial behave in a certain way checking the degree of a polinomial seeing its highest degree proving that its degree is is upper bounded by some number um right so polinomial is do a lot of things which is why we want them the coefficients to be Fields because then we know that they'll have certain properties useful properties um when we evaluate the polinomial as well the number we'll get out will also be in the field like now everything we're doing isn't with normal numbers they're with the field

elements um so let's do this let's do F of 3 well that's 4 * 3^ 2 + 3 * 3 + 6 which is uh 4 * 9 which is 36 + 9 + 6 which is 51 and then what's this well we obviously we can't just have 51 we got to know what congruency class that's in and that's in uh what is this 447 11 right because it's equal to uh 4 * 11 +

7 okay so we don't work with normal numbers in in cryptography we're always in some sets usually a group or or a field in elliptic curves we we go from a field into the elliptic curve Group which is actually a group so it doesn't have it only has um this's actually one annoying thing about elliptic curves is that uh because it's only one operation we sometimes do it as additive notation and sometimes as multiplicative notation and it can get a little bit mixed up there because it's only one operation and elliptic curve group isn't like normal numbers it's unclear whether it should be additive or multiplicative um yeah so that gets a little annoying but yeah we do a lot of stuff

in in fields okay so we're almost done just gonna I just want to go with the core idea of the Schwarz zipple Lemma and then and then we're done uh we actually just removed this from this this lecture because it it it's quite complex and um this lecture already already took a bit of time but I kept one slide because I wanted to go over like the core idea and if you recall I said that in a proof system the actual proof says this statement is true with probability 999999999 and this 99.999 whatever the error term the error term is the. to one

this comes from this LMA specifically and this LMA relates to pooms and stuff so the the the the intuition is if we to sketch out our polinomial let's say we have we havex you know arbitrary polinomial we don't know what it is right now if we sketch out what it looks like it will you know do this sort of thing uh yeah there's a few things to mention here so I do sketch out like this but remember this isn't actually entirely true but it it helps for the the sketching

because the on the bottom we're not we're not working in things anymore we're working in a field F FP same on top same on the top so if we have zero and one what are these numbers in between well in a field they don't exist so I I'd have to sketch a value here for the function and then it'll be here but I can't draw a line between them so when I sketch the function it should actually just be you know a DOT a DOT a DOT in different places but that's really annoying for intuition right so we do for intuition

we're just going to sketch it as an actual curve okay now if we get a second function G of x if G of X is the same polom as F ofx if it's the same polinomial what will its curve look like well obviously oh cool if it's the same polinomial the curve is going to be the exact same this green is the exact same of course more more same than I'm drawing

it okay so if if we evaluate if we if we pick a random number to and I say does f of does f of to equal G of to well if they're the same polinomial and Tow was here then obviously they're going to have the same value here and if to was here this would be the same value if it was here this would have the same value you know at all these points obviously f and g are going to have the same value but what if you have another function h of X but it's not the same as f and g what

will its function look like well its graph look like we don't know exactly but it will maybe do okay so if we now do the same thing a random check if we do h of tow equals F of to will we get the same value well here in this first one no those are apart what about in the second one no those are different values and this third one those are different values as well in fact if they're different functions different pols they

will be different almost everywhere what's the percentage likelihood of them having the same value it depends on the size of but if we have a f to the 2 to the 256 you know a massive number the likelihood of them having the same value um is Tiny it is .0 whatever percent that's exactly where our term comes from in a lot of our proof systems in plon we evaluate polom at random places and if they're not the same polom we will get out different

values and that's how we do our verification you know if you were honest if the Prov was honest and did everything correctly we we have an expectation of what their polinomial valuation will be but if they try and cheat if they're not doing computation honestly they will fail this the polinomial will work out to the wrong value okay there's a lot more math behind there to prove it and to give you the to get the actual percentage it's it's straightforward you know it's the size of the field you're working with and the degree of the polinomial um but yeah that the statement the very specific statement in our definition of of

proofs the percentage comes from this Okay so we've added in a bit more detail we started we draw out the circuit with Gates and wires and we put in the values we turned the values into pols then we committed to them then we sent them then we evaluated those Pol polinomial again at random values um and then that's actually kind of what we're using here we're going to compare those random values to see whether they have this property okay using the Schwarz zipple Lema so not every proof system will do it like this they won't use the Schwarz zipple Lema but plon does and so do a bunch of others okay okay so that's it for this session

um I've I've not really been setting homework it's more of an an optional thing you know I'm recommending things to do at the end of last session I spoke about anky and and memory and how unless you review stuff you'll just forget most of it pretty pretty quickly um so if you want to take up that advice and you want to use zanki and you want to remember stuff from this session I would recommend you uh make some cards on these things like and some of the art of anky or and memory is like figuring out what to make cards about so if you know something pretty well you know maybe you don't need a card um but it's for the things you don't know as well like what are the definitions what are the rules you need to satisfy in order to be a

group what what is it a field what's the definition what's the difference between a field and a ring what's the the main idea of the Schwarz Lemma you know anything like so it would be good for you to go and make those cards um our last session where we're going to do some more math see some more advanced stuff which is elliptic curve group will be this Thursday at the same time so Thursday starting at the same time uh yeah and then we will be done and you will be have a lot more knowledge about how these systems work and the tools behind them uh again I mean these are very complex systems and

to actually understand the systems you have got to put these tools together in very complex ways but we're just covering the what those items are to start with uh cool any any questions okay just waiting for the

typing thank you Loren thank you Lao thank you a shock yes same time on Thursday um okay in the trusted setup context how can the key be the back door for the false proof um how can the key be the back door for the false right uh so that will be easier to explain next

session because um in this schwart zipple scenario um we want to make we we we do our test at the End by checking whether our polom ials have the same value at some random number to right and we don't know where to is you know it could be anywhere um if you know to if you know what the random number is going to be you can

make your polinomial well I'm going to draw it I I can make my polinomial if I know if I know here is where Tower is going to be I can make sure that whatever polinomial I make crosses over at the exact place okay so now my polinomial is definitely different but I designed my polinomial to do anything I wanted but just have one condition where at to specifically it has the value that they're expecting so if I know to I can cheat now in The Trusted setup

ceremony again I can explain that will make sense next session we will make this random number towel but nobody will know what it is which is strange because you know once we know it how do we not know it and that's because it's not a number it's an elliptic curve element it's it's in an elliptic curve group so it will be a number but it will be like the elliptic curve group element added to itself to times so we have a group element but we don't know what the actual value is and it's a very odd thing because it's a random number we make but we can keep using the random number and it will stay random even though it doesn't change um but yeah that will be a lot easier to understand

next session so ask please please ask that again next session I mean there's good chance I will explain it anyway um but yeah in terms of actually how you how you can um how it's a back door for the false proof if you know where it's going to be evaluated you can just cheat very easily the kind of key thing going on here is that TOA Is Random so if it loses the randomness you can make the polinomial that matches at the right place okay cool cool cool uh nice work everybody um I will see you all on Thursday for the last session in the second half of the match