Intro to SNARKs 2: Math (to get to PLONK) part 1

Transcript

this actually so looks good um like I said we're still a little early so we're just doing some checks and then wait a bit longer and see who joins us and then we'll um get going so just be a pause for five minutes or so thank you for sharing the link there Kong I hope people gave Ani a go and try to make some flash cards so

that the stuff we cover will be remembered better thanks Tyler I think we also have a backup recording as just in case but I'm not 100% on that I mean guess I can try and record somewhere don't know how though three backups okay I think that's I think that's plenty yeah

okay sounds good hope people had a nice weekend got some rest ready for people's favorite day of the week Monday if there are leftover questions from from last week this would be a good time for people to to Ping those if any the top of their

minds um just in these in this spare five minutes whilst we wait for other people to arrive or any clarifications you want or other things you just had questions about Qui

uh to Nan's question what we're hoping able to take away from this series I think the most important stuff to take away is what we covered in the first session and that's just kind of like the the core idea of what snarks do and that's the scalability and and and zero knowledge aspect like how do they sort of work beyond that it's a bit of a basic understanding into some of the inner workings which is the mathematical Concepts and stuff like that that we're going to do in this session and the next session and then lastly um is a bit more of a broader exploration of a few different proof systems that are out there in the in the last um session this is like a more beginners introduction that's kind of like fairly

Broad and a very good basis but it's trying to be in this intermediate spot of like more than a blog post but not like a six week course but a 6 hour course instead okay so I mean it's three parts now but I don't think it's entirely fair to always wait five minutes 10 minutes to be able to turn up for something that starts at particular time um you know generally speaking we choose a

particular time because that's when it's supposed to start so I think we'll just kind of get going with this second session now that it's a few minutes past and then stragglers will kind of come in um afterwards so welcome back for for part two I hope you made some progress with understanding part one and all the the content we went there and also maybe making the flash cards like I recommended to help commit that stuff to memory so that it's with you when you need to discuss this topic and so that otherwise you you know you come to one of these courses lessons and then you learn it you understand it and you never practice the understanding again and then it kind of goes so then 3

weeks later 3 months later when you have a conversation about it you can't properly engage um with the with the discussion um Fran I don't fully understand the question saying you wrote cards and an can can you put the question here if you got a question about an that's very welcome as well ah okay interesting what's the point of drawing a circuit if at the end of the day we must look for a solution of pols um the circuit represents the computation that we're going to claim we we've completed that we've done correctly one of the ideas from from the

last lesson um the the the the circuit that we draw encapsulates what we're saying we're going to do polinomial are used to transform this circuit into like a representation and then we kind of conduct math maths there um to make this claim the the um we're not actually looking for a solution to the polinomial like if you filled it incorrectly then you'll have a solution is kind of the the key point so the they serve distinct roles the the circuit the drawn out circuit represents the computation that we're saying we we completed and the pols is how we're going to make the proof is yeah that become a bit clearer in the

next couple lessons as we cover more of the um mathematical foundations um some general points the course material is at this link Kong dropped this in in the side chat so if you if you don't have it you can just um check check there again feel free to stop me if you have any questions um if you put them in the chat I will see them so I will stop and and speak about them there so ask them as they arise and if there's anything um undermining your ability to understand me whether that's audio or my drawing or anything like that just let me know as well and I can make make more changes there and then for asynchronous questions there's the intro to snarks channel in the PSC Discord um is a good place to ask there

and if you add me I will get a not notification and respond quickly before going into session two I just wanted to highlight um a couple of the key points from from lesson one maybe a couple clarifications um I'll answer infen question after these clarifications I didn't I didn't necessarily say all these things but I want to emphasize them so making proofs requires doing the computation that you said you were going to do plus some additional work to make the proof so it it costs more than just doing the computation and in fact I say plus some

additional work it's not a small amount it's it's a fairly large blowup um but the benefit of that additional work is that verifying the computation is now going to be very very quick so when does it make sense to do this well there's two main places if loads of people have to check the computation if loads people have to check the computation then rather than have them all redo all the computation if they all check a proof instead and checking the proof is quicker than redoing the computation we're going to gain value or if privacy is important and you don't want data to be revealed then the computational um blowup factor is going

to be worthwhile as well and generally speaking the larger a computation is the more sense a zero knowledge proof makes um because for small things like a transaction on ethereum cost 21,000 gas but verifying a plunk proof takes 300,000 gas So it's 15 times more expensive so if you're just doing one transaction in a plunk proof and it's not going to be worthwhile but the punk proof actually is a general computation so the punk proof can can have hundreds of transactions inside it and if you do that then the um it scales and you get a lot more value from it so coming to these questions can we do man Constructor snar in the end um we

can't do that necessarily as part of the course but if you want to do it like searly yourselves outside I'd be very helpful happy to help answer questions it'll be like a really really good learning exercise you can try and Implement like um a basic version of plonk um there is also a plunk by hand series at the end of the course material there's a few links to a few different places we try to put a few different links of types of things that people might be interested in um but we didn't want to be one of these things where there's like 30 links and you kind of don't know where to start but that plunk by hand is a very nice one to see because it's literally like written out how it would actually happen um trans the verifier receives the commit so if it receives the commit

receives the witness within the verifier cry from um the commitment um we're going to do that next session understand the commitment a bit better but in a sense you get loads of data in the polinomial and then we um collapse it commit it together into a single value and that binds us to what polinomial was because if we make changes to the original polinomial now um the commitment is not going to work as it's supposed to work um but but you can't just take the commitment and go back to the values okay but we're going to cover the polom or the commitments in more detail

um on Thursday and then we can get going with session two now um the the core point of session two and also session three this Thursday is is going to be to go dive into some of the mathematics that we're going to be working with and it's it's not straightforward we're going to be covering a lot of stuff and like I mentioned last time we keep building on stuff and we really do that a lot here we're going to start with modu arithmetic and then that's going to be used in something called a group and a group's going to be sort of used in something called a field and the field used in the polinomial and there there's a theorem about polinomial so we're

really going to be building a pyramid and this is why you really need to like understand um the fundamentals as well as possible so that we can grow this pyramid more effectively and we're doing we're covering the mathematical objects and tools that we need more specifically for plon so different proof systems that are out there will use different um mathematical ideas or systems um there's a lot of over between different types well certain types of systems um and the ones used in plon are seen in a variety of other places as well so they're going to be quite useful and again for for plon I may have mentioned this on last week but the reason why we chose plon is because it's

a very it's a much more intuitive system compared to the other ones um specifically in the arithmetization from last lesson when we make the circuit from the addition multiplication Gates that's kind of like nice to think about um previous systems like gra 16 they use something called rank one constraint system arithmetization and it's like a larger Matrix and it's like a sum um of a you multiply two sums together and it's just yeah much less intuitive but so that's why we're choosing plon because it just kind of fits nicer to work with in terms of passing understanding particularly a visual understanding so we're going to go with

modular arithmetic as the the first kind of object we want to understand and this is also known as as clock maths right because we're going to be going around in a clock if you're I mean I think you're basically all developers in which case you probably understand this decently because if you've worked with like an I8 or u32 or or whichever you know that once you hit with an I8 you know you have or u8 let's say you got eight bits and once you pass the eighth bit you can't just make the number bigger you actually just wrap around and go back to zero the same things going to going to happen here um but we want to understand this in a bit better detail um I couldn't copy the gifts across to the presentation but we're going to be

sketching this all out by hand and I do recommend in the course content online if you can look at the gifts it does help a lot like this one here so in mod arithmetic we have a a set of non- negative whole numbers like 0 1 2 3 and 4 and I say non- negative rather than positive because we include zero zero is like technically not positive or negative so not neg non- negative means like all positive numbers and zero and we want this to be whole numbers um in you know there during the introduction of the math there's a variety of simpli simplifications I make

um that basically say um ignores the the truth which is you know way more complex and I would have to explain all these different things so sometimes I'll just say um I'll give definitions that are more specific to to what we want to work with so you don't get overwhelmed with all these different changes because a lot of math is like very abstract and that's so that it can be used everywhere but we're only interested in the setting of snarks um so if we have this set the 0 1 2 3 4 um because we have five numbers in it when we get to five when counting upwards we just go back to zero okay and this GIF in the online content you can kind of see it wrap

around um this is also why the set of five numbers doesn't have the number five we treat number five as the same as zero um as yeah as um we do in programming as well with the zero position is actually the the first position so we can try and do bit of a sketch here just zoom in a bit be modular arithmetic and I said we can work with zero one 2 3

four and when we count we have 0 1 2 3 4 we don't have five we just kind of go back to zero right in a sense what we're doing is we have the number line of zero to five well I mean the number line actually goes everywhere but we extract portion so we're left with 0 to five and then we just kind of bend it into that's bad Circle a circle zero so that these two

ends are connected together usually we actually have zero at the top but I've drawn it at the bottom here okay and that's why when we count we go one 2 3 four five sorry that's too many steps there we start at zero we get a one two three four and then we end up back at back at five okay so actually the visual online in the course material is actually more helpful another a very effective way to think about this is in this modular arithmetic set we have one important rule because

this has five numbers we say that five is the same as zero mod 5 okay and I this is this equal sign is different on purpose it has three lines here and not two because it doesn't mean equal exactly it means something quite similar which we say it means it's equivalent to zero under this setting and to specify the the modular arithmetic um space that we're working in we have this Mod Five which you know means modulo modulo five okay so the other example in the in the online

GIF is we got uh we've got this set up to 10 that doesn't include 11 and you can try and guess what the rule here should be it's going to be that 11 is congruent to zero mod five so if you're going to be working with snarks being able to do arithmetic in this space is uh like important to find it very easy in the same way you add normal numbers when you're working in um yeah just normal settings if you're working with snar snar you want to be able to understand this idea very very easily such that you can just kind of

straightforward um just figure out how you're going to have to account for things okay but this this rule encapsulates most of what's happening in in in modu arithmetic so the reason why we can just use this rule instead is that if we're in this setting where 11 is congruent to Z mod 5 if we do like four * 5 well that equals 20 but then how do we get back into our set well 20 equals 11 + 9 oh sorry I put Mod Five here

uh oops that should that should have been a mod mod 11 11 + 9 but because of this rule again 11 is congruent to 0 + 9 right and that just equals 9 mod 11 okay if we work in the smaller group The the Mod Five we can do like 2 * by 3 = 6 well six is bigger than five so we got an issue but we know that 5 + 1 is the same as six and that's congruent to 0 +

1 the same as one Mod Five and you can you know keep doing this as it gets larger if you have 3 * 4 which is 12 well we can see this is five 5 + 5 + 2 right which is equivalent to 0 + 0 + 2 is the same as two five okay just how many fives go into it and I wrote 5 + 5 but we could also just do 2 * by 5 um + 2 which we know will be 0 + 2 um and that equals 2 five okay so you

want to get useful used to working in these the in these groups uh sorry in this in this setting of M arithmetic we're going to do groups next yes so this is like the base case so we're no longer doing arithmetic on the normal numbers the real numbers from minus infinity to positive Infinity with all the um decimal numbers in between and things like that we are working now in just like a small set for right now in the examples the small set 0 1 2 3 4 or up to up to 10 um with this this rule okay and then we're going to keep Building from here to add more structure so that we can work with these objects

in in in more interesting ways um so from modular arithmetic we go to groups and for groups kind of take a modular arithmetic and add more structure to it and that structure is going to be very useful to us um the modular arithmetic just defines how we handle addition multiplication um but the group has more things and it's got three um things inside it we've got the set which in the previous example one of them was0 1 2 3 4 that's the set of numbers that we we're working with we've got a binary oper

ation for example additional multiplication the binary all it means is that you take in two things and you get out one thing so you because binary is two addition is binary because you take in two numbers and you add them together you get out one number same as multiplication um and that that in the parentheses at the end I say but not both in a group you only have one of these operations you don't have addition and multiplication you'll just choose one of them so group like mathematical groups are way more abstract because there are tons and tons of binary operations we can choose from but like I said in our setting all we care about is additional

multiplication so the fact that others exist doesn't matter to us and then lastly we need something called an identity element and this this sounds a bit confusing although when you see an example hopefully it'll be way more straightforward but the identity element when it's used in the binary operation be it addition or multiplication um it should do nothing okay so in addition we're going to have to add if we add the identity element we should get out the same number we started with so if we're going to do three plus something and plus the identity element we should get out three okay so hopefully that will be clear to you want you think about it a bit is that it's

going to be um zero okay but we're going to do Live sketch to make this AIT a bit clearer so there going be a lot of live sketching this um this lesson and next lesson as we go through these objects um groups and I said so we're going to do take this set it's just going to be 01 two so very very small set we're going to work with here and it's going to be modular arithmetic so the rule here is going to be three is congruent to zero sorry it's equivalent to zero mod three um let's take

addition as our binary operation and I said we need an identity element I said that was going to be uh zero okay so we can check that the Zer is indeed the identity element because if we do 1 + 0 we get out one one which is exactly what was supposed to happen and if we do 2 + 0 we get out two the output is the same as the input and the same here so um so zero is indeed our identity element you might it'll be good to ask yourself quickly What If two of addition we use

multiplication then what would the identity element be well it would be the number such that 1 multiplied x equals one so the question here is what is X and hopefully you can see that X is going to be one here yeah well then so I mean that's fairly straightforward but this should hold for whatever the input is so we can check that if two times uh one is this going to be two

yeah we get out two so if x is one the identity element okay it should always be be the case but you might realize now that actually if we check and we do Zero multip by one we get out zero we don't get out uh we don't get out one uh sorry we don't get out hang on what's I'm going try to explain here okay no scratch that sorry ignore that um we we get the same thing that we

wanted here so this is okay in all three scenarios there's only three possible multiplications we can do here uh with one Zer Times by one 1 times by One and Two Times by one and in all three of them we get back the number we started with so we have an identity element here as well okay we're not actually done with groups yet that's not actually what a group is and we're going to come to these these next rules these are just the things contained within a group we have the the set we've got the set we've got the binary operation and we've got the identity

element okay um in our example is three identity remember the identity element is tied to the binary operation so are you talking about under a addition or under multiplication so just get the answer there so under addition let's just do this in in whatever this color is the left side is our um addition so let's let's look at what you're asking you're asking if three is an identity three well hang on we we already said

that zero is the element but we also because we're in the modular arithmetic group three is congruent to0 three so under our setting in in modular addition three and zero are actually the same same thing so three is also the identity element but we'll never actually work with three because we try and stick with the numbers in our set and if three is the same thing as zero then we'll just use zero in instead so when we're working with these sets just try and stick and only use numbers that are inside

them okay the similar to like an I8 or u8 you know if you're programmer because things wrap around larger numbers the same thing as the smaller numbers that have the same mod under the two to two to the eight okay but we're not actually done with groups yet that's just the objects it contains we're going to add a couple a couple of rules um firstly there's the notion of an inverse element so again invers like you're undoing something but what are you undoing undoing it this is again going to be tied to the binary operation so

it's going to be tied to addition and tied to multiplication and you maybe have already sort of guessed that undoing addition well that sort of sounds like subtraction and undoing multiplication sort of sounds like Division and that is going to be the case and it's this additional structure is why we only need addition and multiplication and not subtraction or division because we're going to have the same thing as as subtraction and the same thing as division using these inverse elements so let's look at an example of what those might be uh go back to

Blue so in our addition example the one if we're looking for an inverse element of one this is going to be 1 + x um there's another step here because if you're undoing then like what do you get back to well we have to get back to the identity element okay so under addition zero is the identity element because anything add zero um is the same thing as what you started with so um anything that satisfies this equation is going to be X is the inverse

element of one and then I should actually go on here and say under addition or call it the additive inverse element in the modular set 012 okay and what's it going to be here well we got to find something to add to one to get out zero but remember that Zer is also equal to three under our setting so since 1 + 2 equal 3 which is congruent to Z mod 3 then 2 is the inverse

element well the additive let's see and so again see here that we we actually just did subtraction um because one 1 - 1 is zero but also here in the same place 1 + 2 is zero so we don't need the notion of subtraction because um we're going to have something called the additive inverse now this is actually a bit of a small group with three numbers but perhaps working in a bit of a larger group would would add a bit more clarity we can do it in um in in a larger Group after this but let's just continue from this example what's the inverse of 2 2 + x =

z we're going to find something that satisfies this maybe some of you can can kind of figure it out but we're do the same thing because we know that three is the same thing is zero um 2 + 1 is 3 which is congruent to zero mod 3 right and these are actually yeah yeah it's one these are actually um if it goes both ways if if two is the inverse of one then one is going to be the inverse of two so they're actually sort of connected to each other by nature and zero we can also check zero as well you know 0 plus X is0 but because zero it's zero it's the identity

element anyway um the inverse of zero is is itself so minus 0 is the same thing um is let's just minus 0 is the same as plus 0 um + two is the same as minus1 and + one is the same as minus 2 okay because we're at mod three we just have to like add a number to get to three it's sort of

fairly straightforward and if we're going to be working in the modular group with five elements you want to find the additive inverse of one you just got to do 1 + y = 5 it's just going to be four so with addition it's it's more straightforward with multiplication it gets a little bit harder let's see what we're going to want to find 1 time something equals what are we supposed to get out well we're under multiplication and we're supposed to get back the identity element which is the multiplica of identity element which in this case is one so one * what equals 1 well I mean obviously 1 * 1 equals 1

so I'm I'm not I can expand on that now but um it'll probably be a bit clear to do two first 2 * x equals 1 what what's going to be what possible values for X could we get get here we can try and we can just try multiples of of two until we get there I mean two is not we get to four but hang on but four is the same thing as 3 + 1 okay but in this scenario that's congruent to 0 + 1 right which is the same thing as 1 mod okay so I know there's not immediately

straightforward and in in this these are the places where math is very much like programming you really have to try and like grab ideas yourself or or examples and and play around them with them yourself to grasp them more effectively um we're going to do another example afterwards using a bit of the group with Five Element sorry the set with five elements so it will be um hopefully a bit clearer with that one as [Music] and to Jimmy's question now are we saying that X is is X a fraction um x x needs to be needs to be in the

set right this is our set 012 we don't contain any fractions there again like I said we're going to do division without needing division so instead of dividing by two we can multiply by something and it'll be the same as dividing by two normally you know you'd multiply by a half which is a fraction but in our sets they have particular structure that means we don't need to multiply by a half there'll be another whole number that we can multiply by by and it'll be the same as dividing by two so this here you know we think that X is is should be a half a fraction um but it turns out

that um two is the multiplying by two is the same as divide by two in our set in our arithmetic setting okay so the more and more examples you see of this hopefully the more and more comfortable you get with it but we're not fully done yet um I said the rule is actually okay sorry we're just introducing the idea of an an inverse which is related to the

binary operation okay so that's what an inverse is and then we're going to like finalize what actually a group is if something's actually going to be a group it needs to have two two rules that it satisfies every element that you sorry every element has to have an inverse element according to the biner operation okay and every element um that you get out of the buying operation should also be in the set okay so now let's see if we actually have sets let's take a different oops example here we're

going to do 0 1 2 3 four okay and we're going to do this with addition and we know that zero is going to be the element okay so is this a group is the question we're now asking ourselves we've got to see whether it satisfies the two rules we just set set out one does every element have an inverse to is output from

operation in the set okay that's what we want to check and we can just do this Brute Force because there's not that many um things to consider here so one does every element have an inverse well the inverse is tied to the um binary operation which is addition in this case so 1 + x = 0 because remember that's the equation we've got to satisfy to find an inverse well we know that 1 + 4 is five which in our setting is congruent to Zer mod 5 because remember in this modular setting we have the same thing our primary rule

is that five um sorry five is congruent to equivalent to 0 mod 5 okay if you can before I say them try and work out the other additive inverses here so what about 2 2 + x is Zer well we know that 2 + 3 is 5 is congruent to zero mod four five okay and what about the case for three 3 plus what is zero well I said these also they work with each other so if three is the inverse of two then two

is going to be the inverse of three so 3 + 2 is 5 congruent to 0 5 same thing for four because four is the inverse of one um 4 + 1 is 5 to Z Mod Five so our first rule I mean it's also 0 + 0 equals 0 so 0 does have an inverse element our first rule is is satisfied and then the second rule is everything from the the output from the binary operation in the set we've got to check if 0 + 1 0+ 2 0+ 3 0 + 4 and 1+ 1+ 2+ 1+ 4 Etc the result of all of those are in the set um but we have that because of the modular arithmetic that

we were doing anyway um you can write that out if you want but that that's sort of inherited from the the modular aspect of things so object is a group we've got a set there we've got our operation B operation and we've got the um identity element of the operation and everything in the set contains or has an element okay what about what about if we do multiplication and multiplicative

identity is one well when we take a look we're going to want want to find inverses again so 1 * by x = 1 how are we're going to solve this well I mean of course 1 * 1 equals 1 so um I'm going to do this notation here to the power to the power minus one that's the same as saying like dividing by one is the same as multiplying by one this is like the inverse the division um thing because it's going to be the same thing as division what about for 2 2 * x = 1 well what do we have here

um well let's just reiterate so make sure we know in our group we have that sorry in our Moda setting we have that five is equivalent to 0od five so what are we going to do um well we can just go we can just go through multiples of two until we either find one or or or don't find one so two is not one um four is also not one uh six well actually six is the same thing as 5 + 1 which is congruent to 0 + 1 which is 1

5 okay I mean this this here was just 2 * 1 and that's 2 * 2 and 2 * 3 okay I was just going through the multiples trying find the uh um the the inverse of two right so we can also sort of say that two the inverse is three because 2 * 3 is six which is the same thing as one to Nan's question does using modular arithmetic create or allow the existence of these sets in groups that that have certain mathematical properties we then

exploit to do oneway maths um I mean modu arithmetic it contains the set that you're working with in many ways mod arithmetic just takes all whole numbers all whole numbers and then adds in this rule where 5 equals z or where 11 equals 0 or where 3 equals 0 and then normal arithmetic applies um so they doesn't really create the existence of something it's more taking something that does exist and and modifying it a little bit

um yeah I I'm not entirely sure exactly what the question is so if if that's not too helpful you can try and rephrase it maybe but we're not done in our example yet we're trying to see if this set with multiplication and one one is is a group so we found an inverse for one it turns out to be one we found an inverse for two it turns out to be three we now want to find an inverse for three um but we said it goes both ways so if three is the inverse of two then two is going to be the inverse of three so we can just check that so if we do 3 * 2 that's six going be congruent to uh sorry I should do try and be consistent that's the same thing as 5 plus + 1

equivalent to 0 + 1 is 1 5 right so the inverse of three is 2 and what about 4 4 * x = 1 um well not immediately clear so we can just go through the multiples of four until we either find one or don't so we've got um let me just write out in totality 1 * 4 is 4 which is not 1 2 * 4 is 8 which is 5 + 3 which is congruent to three so that's not quite it 3 * 4 is 12 which

is um 2 * 5 + 2 congruent to two so that's not it and 4 * 4 is 16 which is 3 * 5 + 1 and that is congruent to 0 + 1 which is 1 Mod Five so the inverse of four is for itself apparently okay so 1 2 3 and four all have inverse elements um but what about 0o 0 * x = 1 and then if we start to think about this a little bit we'll hopefully

realize that if you ever multiply by zero the only thing you can get out is zero like when you take zero lots of something you're only ever going to have zero so zero doesn't have an a multiplicative inverse element this is not not a group right why because zero doesn't have a multiplicative inverse we can turn it into a group if we just remove Zero from our set um because everything else had an

element right and that would actually be consistent then we would have a group but 0 1 2 3 4 with multiplication and one is not a okay so that's groups we've got this we we've got a set we've got a binary operation we've got identity element and then it's got to have these rules where every element has an inverse element okay which you got to kind of manually check at least in in the beginning right but the the inverse elements are How We Do subtraction and division okay so again to get more

comfortable with these ideas you're going to have to start like going over a few examples yourself when when you can the isn't immediately obvious like it takes a while to get used to these ideas don't expect for it to be obvious immediately it will take some time and efforts Okay so we've done mod arithmetic and we've done groups um okay I mean yeah this was time permitting we don't really have time to to do this so I'm going to skip this it will be an additional exploration next up is a field and a field is kind of like getting two groups and just smushing them together into one thing so

the group had three objects inside it it had a set it had a binary operation and it had an identity element the field has five things it's got a set and it's got two binary operations instead of one and it's got two identity elements instead of one and of course the identity elements are tied to the binary operations so for us the binary operations are going to be addition and multiplication and the identity elements are going to be zero and one so again we're building up more structures of these objects um in terms of rules the similar rules apply um everything that you get

out of the binary operations has to also be in the set and also everything has to have an inverse and now we don't have one type of inverse we've got two types of inverse everything needs to have an additive inverse as well as a binary inverse except for one exception which is that zero doesn't need to have a multiplicative inverse um and in terms of the Live sketch for this we've already done all the work here like in this left side we know that with the set 0 1 2 3 4 they all H you know this this modular

arithmetic um setting they all have an additive inverse and that all results from addition are still in the set and on the right hand side we've also already done all the work we know that everything has a multiplicative inverse we found them all all here except for zero but that was the one exception to the rule that zero doesn't need to have a multiplicative inverse and the reason it doesn't need to have an inverse multiplicative inverse is because it it can't like by definition of how this stuff works it's like a very unique thing um it would be great practice for yourselves if you have time to try and

see if something else is is is a is a field or a group you know this is the mod arithmetic with five elements maybe try to do it with six elements and also with with seven elements you should find that the one with six elements is is not a field um and but the one with seven elements is um what you will find is that um it's only ever a field if the number of elements is prime this is why we use prime numbers everywhere well one of the reasons that we use prime numbers everywhere cuz if the set itself is prime you're always going to have these

inverse elements it's not fully true it's not just primes it's also Prime Powers so you know four is not prime number but it equals 2^ squ um so it will be a field but six is uh no I mean you have a field with four Els but six is 2 * three and that's two different primes so it doesn't doesn't work okay uh funny question Z friendly um if you want an example of a elliptic curves are an example are going to are going to be an example of a

group that is not based on on modular arithmetic um the thing is if you're using um if you're using normal numbers we're probably we're usually just doing additional multiplication so it's hard to to get away from from from that kind of stuff and it just being mod modular arithmetic but we're going to do it with with with a group but groups are like a very very abstract idea they they're a big part of like fundamental the theoretical physics like the understanding of the universe and um essential particles they have like this the Symmetry group so you can see the um like rotation of an object soor this is

like a USB drive you can see rotation of of an object uh as a group because if I can trans I can rotate at 90 degrees and then another 90 which is 180 and then to 270 and then to 360 and I can also turn it this way around so instead of like in modular arithmetic we do like a number plus one plus one plus one and we keep doing that to find other elements in the set in this scenario it's the position like the orientation of the object where we have this and you can rotate it once and rotate it twice and then three and then four um so that's why a lot of these definitions are like extremely abstract

because we will actually just write a letter in math you know we'll just say that we have the element a which is very much uncomfortable for people who are new to it because we'd rather work with an actual number uh but there's really really it can be very very abstract so we're at 54 minutes um I think it's best to take a short break now and have questions before we go into the the second part where we're going to do polinomial and the Schwarz Schwarz zle Lemo um but the again these ideas just keep building up so you really want to like make foundations so let's say that we'll restart again at at 9: and we've got the six minutes just

for you guys have a little break or to ask more questions and clarify I mean I can go over another example in in this um short window if people want that as for

e um as for how they're going to come and connect in the context of snarks is um snarks don't work with like normal numbers they'll work with elements from a um and again so the reason why we only have addition and multiplication Gates is that because we're working in a field we can do division and subtraction using the inverse elements instead okay so those ideas are integral to to how how we use

snarks um we're just working with abstract algebra and yeah all in snarks we don't we don't use the number three we use the number three in a field or you know in in if in a particular field or the third element in a in a group an elliptic curve group so we don't really use normal numbers in in snarks I mean that's like a very high level potentially not not not too useful but because like I said these ideas just keep building up and up in order to explain how we use them later we first need to know sort of this idea and then

some other ideas for this to make sense otherwise I can say things but it won't actually mean anything um cuz we're going to we're going to represent all our computation using field elements um and then we're going to map them to a group and then we're going to represent all of this so we'll represent it all as a polinomial and then we're going to map it to a group and then we're going to check this stuff based on rules and theorems that apply to Fields um so this is the language we use in in snar s um fields and groups are used in every as far as I can think of right now

every snark there is pols is are not used in all snarks but you can the ones that don't use polinomial you can think about what's happening in in terms of polinomial as well in in from um certain senses um in such a set 0123 four when finding the inverse of four we found four and we wrote the answer as 3 * 4 + one are the mules of four count when we write the answer let me just check so just want to check so I think you're talking about this here where we found inverse of four right so we found four

we the answer is 3 * 4 um this 3 * 4 here if that's what you're referring to that's not our answer we we checked 3 * 4 and it gave us 12 which is the same as 2 * 5 + 2 which is congruent to two um so that wasn't our answer it was the one below where we have 4 * 4 which give us 16 turns out to be 3 * 5 + 1 3 * five oh right so okay this 3 * 5 here essentially what I was doing before with this equals you know um so 16 equals what I was doing before is I was trying to lay out like every single

detailed step where 16 is actually 5 + 5 + 5 + 1 which according to our rule because 5 is the same thing as zero this is congruent to 0 + 0 + 0 + 1 right and it will just keep kind of growing like that but instead of doing 5 + 5 + 5 I just collapse it into three * 5 the point is that's going to be zero anyway so we're just trying to put all the zeros together and then ignore them not ignore them but treat them as zero okay it is now nine I know that's not yeah it's a quick

five minute break so yeah the math it moves pretty fast so when mathematicians learn fields and groups they take it quite slowly they do tons of examples it's like a whole course for groups and a whole course for Fields uh but when physicists learn these things they also do groups and Fields in like first lecture and it's kind of like hand waved and done very very quickly cuz they don't need to know all the details really they just need to know a bit of Basics about what how they're defined and how to work with them um of course the deeper you're understanding the better because if you're going to be working with these ideas at a higher level you want to be

as comfortable with them as possible but you can build that like the the the basic overview and definition is uh a really good starting point so I just close the uh screen share check your screen one moment and believe we're back now yeah so in this second half we're going to be going over pols and then this um theorem we introduced polinomial last lecture but we're not interested in all

all possible polinomial we're going to have another condition and you know surprise surprise we're going to be restricting ourselves to ones that that work with Fields um okay so let's just go and sketch this sketch what oops sketch out what we're talking about pooms like we said last last lesson uh let's do p X is going to have an example is like 3 +

4x + 7 x² okay we've got P we've got X as the variable right we got x and x squ because X is a variable here we we cannot actually have like multiple Vari P of X comma Y which is you know 3 + 2x y + 4x^2 but we're not really interested in those a lot of the time we can just restrict ourselves to to single variabl so just just X and these Powers um this is there's actually a one here these powers are are whole numbers okay so that's what we said a polinomial

was we're actually interested in a subset of all polinomial like I just said and the Restriction is that um the the coefficients the numbers in front of the variables so four and seven and you don't see an X here but this is actually x to the 0o um anything to the power Z is is one so we can treat that as the X to the zero term so three is also sort of a a coefficient all of these have to in um a field okay they're going to be in a field um for for notation uh we just said that we just figured out

that this is a group over here this uh well this with also addition and zero we call that field we do this F with these two lines and then underscore and we put a five because it's the field with five elements in it so this means 0 1 2 3 4 um with additional multiplication and0 and one as the as the identity elements Okay so for example here we might be interested in F in these being in in a field for example F 11 okay so three four and seven are all

clearly in in f11 we and then the notation here is that we want P of x to be f11 square brackets with an X inside it this is the notation for the for the pols that we're interested in again it might look a little scary but it's just saying that it's a polinomial where all the Co polinomial in X you know just one one variable where all the coefficients are in in f11 so this one here this polinomial is is in in the desired set oops of of

pols let's take some other ones f of x = 20 + 14 x cubed is this in our set in our desired polinomial area and hopefully by now you're getting a little bit more comfortable well in f11 we have that 11 is congruent to zero mod 11 so this actually equals well this is equivalent to 9 + 5 x cubed okay so this is uh an accept acceptable

polinomial what about G of x = 3 + x^ 1.4 well no we can't have powers that are not whole numbers what about h of X which is um 2 + x the -1 minus one is a whole number but it it's negative that's not actually allowed and if you have a negative it's actually the same thing as doing one plus uh sorry 2 + 1 /x it's same as like dividing like we have the notation of the multiplicative inverse before as division that's not a

polinomial the the powers of X have to be again non- negative whole numbers okay and then maybe if J is x equals three a very bad three is this a polinomial and you might be wondering because it doesn't contain an X term that it's not but it is still a polinomial um it it's a very simple one it's a constant one it's a very very easy one also polinomial is a really kind of scary word like it just sounds a bit bad but it's um uh it just means function like you probably worked with lots of functions in school that was f ofx equals this thing that's you know it's a subset of

functions polins are a subset of all functions right and sorry uh to Clinton's question we can just keep adding terms here 4X cubed plus plus um 2 x to the 100 um you know we can just keep going up and up and even if we're working in an f11 we can have higher power terms of of X um because that's still going to be useful to us these are still going to be different things okay so even though the numbers will the coefficients will be between Z and 10 in our example we're working in F1 the FI with 11 elements the powers of

X can just go up to Infinity but of course when you have a concrete polinomial like a specific instance of a polinomial there is a largest power and this has a name and we say that the the degree of um of let's do this F ofx is three because the highest power of X in this polinomial is is three in a bit short in a bit shorter hand notation we do de um of oops not g of f equals three okay so the highest power and so the degree

of of P up here would be 100 because that's the highest power okay so the degree is also an important term sorry when I said concrete polinomial I I meant like when I'm writing P of X here it's kind of abstract I'm saying it could do this and just saying you know it could go up to anything but a concrete polinomial is like if you actually hand me a polinomial it's already decided what the polinomial is defined as okay a specific instance of a polinomial rather than just like talking about some abstract potential polom um so concrete is not like a math term that's me trying to explain that I I mean mean like a one that's already

been defined right so this is the polinomial ring which means that you know it's polinomial INX and f11 is where the coefficient can come from and degree is another term that we want to remember oh I didn't do a minus value um I mean we show that 20 and 14 are the same as 9 and 5 if we had minus three um okay let's just do a quick quick example if we had FX = 4 - 2x^2 then is this a polinomial well it

is because again mod arithmetic because we're going to have this is the same as 4 + 9 X2 okay so this is like the additive inverse of nine um of of two sorry is is nine that you can it would be good to try and understand yourself at home just to get a bit more comfortable with with these ideas again um and we can also evaluate obviously so we take let's let's stick with this F ofx

what was it 20 + 14 uh let's do 20 + 14 x rather than X2 we can evaluate in in our polinomial sorry we don't want to use 20 do we we want to use 11 and and and um five 11 + 5 sorry 9 + 5 my bad 9 + 5x okay we can evaluate in our Pol we can do F of 3 which equal 9 + 5 * 3 which is 9 + 15 which is 24 which is the same thing as 2 * 11 + 2 and that's

going to be congruent to 2 mod 11 okay we you know I put in three which is sort of like just any number we can do this at F of 1.2 and then we get 9 plus plus 5 * 1.2 which 9 + 6 which is 15 um but we we really shouldn't be doing putting in 1.2 and we also shouldn't be putting in like three as some whole number probably won't be a surprise but we're only really interested interested in in

evaluating our pols at values in some field and probably we're just going to use the field that the that the polinomial is associated with so if um if our polinomial f ofx f ofx is in f11 of X we're probably just going to evaluate that

okay so we can evaluate our polinomial and to get more abstract we don't even have to actually evaluate polinomial at numbers we can we can actually do evaluation of the Pol at the abstract example group that I mentioned before which is rotations of of an object you know because this is one rotation and then two rotations there's ways where you can just put these rotations into the object because it's just abstract like you can represent any if it's logically consistent you can represent some action um as a as a as a number and we're going to evaluate

polinomial at um not at numbers but something that's not too dissimilar in the next session not today and we come to the the Schwarz zipple Lema firstly the the name might be a little scary but it's just the names of the the discoverers I mean I guess they were German and Schwarz and and zipple I think on the Wikipedia page there's also a third name um but they're just the names of of the discoverers so don't don't worry um to too much about that but yeah this it gets you know kind of more complex um it doesn't it's never particularly easy but this idea is like very core to

how plunk and also a lot of other proof systems work um it's not the only piece but it is one of the key pieces the the core idea of the of this Theory also just quickly for the for the naming this this is called a Lemma um in so I mean you probably know what theorem means it's like some idea that we we we sort of think is well proven to be true in math we also have a Lema which it is actually the same thing as a theorem but usually we reserve theorem for like a more important idea and a Lema is just a less important idea to help prove a theorem but this LMA is actually particularly

important so you can just think of instead of the word LMA just think of the word theorem so what it says is that if you have two different pols um but those polins have the same degree remember which is the highest power and you evaluate them at a random point and the evaluations at that random Point are the same then with overwhelming overwhelming like likelihood the pols are the same and if you remember from last session we said that what what a proof says is that with

99.9999 Etc percentage likelihood uh the computation was done correctly or you know the proof is valid or the person knows the thing that probabilistic part is coming from this Lemma when it says with overwhelming likelihood we actually know the exact probability of it um passing by by by accident and we can make that probability arbitr arbitrarily small okay so this is like one of the core ideas in in in the proof aspect we're going to sketch out what the the core idea is so it's a bit bit clearer um the way I phrase the Lemma is is only true if the if the field is

large enough um because if you got a small field like in the one we're working with with with 11 elements um there's a good chance that just by chance you're going to end up at one of those 11 the one of the 11 elements that that was correct um but we usually work with huge fields that have like 10 to the 80 elements and so there it's going to be like insanely small and we can out the exact probability okay let's um let's explore what what that means we'll start let's

towards Schwarz zipple Lemma so the sort of statement of the core idea if there's that if we have um f ofx our okay let me not introduce more notation f ofx um f ofx and g of X both in FP with X these polinomial rings and P is just some arbitrary prime number um and the degree oops of f is the same as the degree of

G okay and then we get take a random R in FP so random number in in FP now here's the statement if F of R equals g of R then um the polinomial are the same f ofx equals g ofx and we can say this in different ways like the the more specific part we could say uh overwhelming

likelihood but we don't have to say with overwhelming likelihood we can actually work out like the exact probability of of of that happening the exact probability would be uh the degree the degree of f because it's the same as G over P okay in in practice remember p is the size of the field in in practice these values might be around um the degree of f might be around 2 to 30 f f is going to have like U the highest power of X will be in the like

millions and P what we just said before it's going to be like 10 to the 70ish but you can also think of it 2 to the 2 56 maybe so and that equals around one over 2 22 six like a really really large number this is the this is going to be the likelihood like a more specific likelihood of this happening by accident and that is just uh phenomenally um unlikely not not not going to Okay so we're going to explore a little bit as to why that's true and try and present a a visual a visual proof because I've told I told you that this

is the probability but but why is that the probability and and how can we have some intuition for that if we look at functions are pols I mean if just going back to the slides we have two images in the left image we have f ofx x and then we have FX = x^2 we're going to be looking at like the bendiness or how many bends the these have so f ofx equals x if we sketch it out apologies for quality of sketches but this is going to be a straight line like that I maybe let's just do these

the lines themselves are different colors okay straight line no bends f of x = x^2 if we sketch that out you'll get something like this and you're going to see you see that we have one Bend zero bends go a bit further do f um I I'm not going to write out the exact I don't know I don't know the exact equation but we're going to have X cubed plus I'm just going to say

ax2 plus BX plus C and A and B and C are arbitrary terms and I I don't know their exact values I'm going to explain why I'm doing that right right now basically I want this curve is going to look like this okay you see here that we have two two bends the reason I didn't just do G of x = x cubed is because if I sketch that it just looks like this and it doesn't really have any bends and it breaks the rule I'm trying to show you a little bit but what the

pattern you'll see emerging is that the the polom can have um up to a certain number of bends so if something has degree three like this here degree three because the highest power is three it can have at most two bends it doesn't necessarily have two bends but it can have at most two bends which is why this example didn't work perfectly um right so we see so the rule is a degree D polom can

have at most D minus one bends okay so we the polins that when we draw their their graphs out they're going to have a certain number of okay let's explore what actually happens in in the exact space now if I draw out so now I'm drawing out not negative

on either side because remember we're actually working in a in FP which is a field so it doesn't we don't actually treat it as having negative numbers it just goes from zero all the way up to P minus one and the same on on this side P minus one this is still FP we can even sketch out like a little doted line for the limit of it okay so we don't actually need to work in in in the negative part so if we have two pols let's do F

ofx and we also have G of X and let's say that D equals three in this scenario if we're to if we're to draw the graphs of these two functions right now we don't know what they actually look like but we do know one thing now it's going to have at most two bends so if we do F ofx okay we've got our two bends here's one and here's two and then we can draw up G again it can look like anything

but okay it's it can have at most two it's Bend one not very visible but bend two so remember that what the what the theorem is saying if if we take random R in here right we're going to take a random R which is the same as just taking a random Point here if we just go back and forth and then stop somewhere and let's say we stop here do that different color we just stop here then if we go up we're expecting and we see these two

to be the same that's going to be um that's going to be when the theorem applies because remember has this if then if the evaluation is the same then then the value is the same but if these two pols if their degree three they have at most bends because of that they can only overlap in at most three places one two three here okay these can only overlap in at most three places the only way two polinomial that have the same degree can

overlap in more places than their degree is if they're the same polom of course if if G of x equals F ofx then the the the drawing of G uh of of G of X would be just going over F ofx okay then they're the same everywhere okay but if they're not the same they can only inter over um overlap each other in three places now okay and that's why if we're going to take a random value somewhere on the

bottom and then look at it and then go upwards the likelihood that we chose this random value to be one of the three locations where they actually overlap is just phenomenally unlikely again we can work out exactly like here we have three there's three possible positions where they overlap so the top is three and the total space is p which again we're going to do three over 2^ 256 you know it's like you take a random Atom from this universe and expect it to be the one you

will hoping it to be you know that's the scale of this um so this again is where the probabilistic aspect of proofs come from we know that guessing the correct answer in fact you're not even guessing the correct answer because because the number is taken at random like if if this wasn't random and I could just choose it I could just I just choose one of these overlapping uh coordinates you know I would just choose the value that would make it make it pass but we don't get to choose it's

going to be it's going to be random and it's forced to be random by by a a Technique we called the F Shamir transform where we're just going to like hash stuff to get a random value okay so because I can't choose a random I can't choose the value myself and it's taken at random the likelihood that this random value is one of the tiny tiny tiny tiny uh situation where these pols evaluate to the to the same uh yeah we we we get out the the probalistic aspects we want so hopefully this kind of visual sketch helps you understand why that is the case in general when we actually prove this I

didn't want to do that because it makes a bit more it the proof is actually cleaner but you have to do a few more steps if you're just to look at the the difference between these two pols for people interested in the mathematics if you look at the difference between these two pols you'll get a polinomial that will be at most degree three as well and then that can only cross the be zero in most three places is the simplest way to prove this but but this is like a more visual you can see that these the these drawings can't overlap in more than three places okay so that's what we're going to be using later to make the claim that because these values are the same the

polinomial must be the same and therefore um the computation was done correctly of course there's a lot more steps even in between making the computation the the circuit arithmetization and getting to those specific polinomial okay but you see we just keep growing and building on these ideas we had the mod arithmetic uh scenario and then we built groups on top of that and then we put groups together to get fields and then the fields of the sort of the number system we use in our pols and now we have a theory about pols and then we're going to do lots of other stuff with polinomial a lot of what happens in snars can be thought of as creating and

playing around with pols so yeah the more comfortable you are with these ideas the the the better and that's kind of everything I wanted to go over today um think it might be best if I just well tell you the homework quickly I Me Maybe you can snap a photo the same as before the these ideas are not straightforward the more time you spend with them the better and the more examples you can remember the better that's actually what happens a lot of the time that you try and think like is this a group or is this a field you'll be like well I remember in this example you know F5 or a group with three

elements it Mak processing it a lot easier in the beginning if you just commit a few examples to to memory particularly also the definition like if you want to check if something as a group or a field you got to remember what that actually entails on top of trying to remember things it would be really good to play around with another one I mean I did zero um the set with six elements here in the question but you can do it with anyone you want and then if you turn those into an cards it'll be really really good so we didn't actually share the slides last time so I mean we we can share the slides but if you want the the homework it might be quick a few just to take a screenshot so thank you for for coming

to this session just before I answer questions I want recap so in the first session we did like more high level idea what is a proof really doing and and what are the some of the consequences of that and in this session we're starting to get going with some of the fundamental mathematical ideas or objects that we use and then in the next session we're going to build up more complex ideas about how we work with these mathematical objects um to do some of the things that we do with the inner workings of of snarks and in the last session we'll have a quick look at how those are all put together in plonk itself and then we're going to do a brief overview of a few different proof systems out there in the space but again I I mean I keep

emphasizing this but no one no ever like looks at the definition of a group in a field and be like oh yeah cool and then they can just work with it it takes you know a bit of effort to be more comfortable with these ideas um so now we can just kind of go on to questions and I'll stick around for you know as long as people want to keep answering questions so no's asking if we can think of as field as as two-dimensional I think I would actually personally say no usually when I think of a dimension I think of like a way of representing the elements in two Dimensions um if I'm thinking of two

Dimensions I'm thinking of like representing stuff in in two different um like axes sort of thing but I think there's more like two perspectives on what you can do with the things in a field because you can use one binary operation or or the other if thinking about it is two-dimensional if you find a way that that's kind of logically consistent then then go for it um and also in this time now if you want me to go over anything I we went over or if you want me to do another example of one of the things um we we can we can try yeah that's good to hear the

visualization was was helpful um yeah it's there's a lot of the um yeah problemistic aspect coming from there um but it's also the same kind of idea the fact that you have this huge face makes it hard to figure out like what the input was that's where the secrets come from as well like it's all kind of very connected to each other

yeah we'll see in a bit more detail next session as well when we bring in elliptic curves and then kind start to understand a bit more of what's what's going on so elliptic curve we're actually there's going to be a group there and we're going to have something called elliptic curve Edition but it's not going to be normal Edition as we're used to it um it will be like a different type of binding operation yeah anything from three blue one brown is like solid quality content like really really good math math YouTuber um in fact the the visuals I made in the online content I he like built the software I think he worked at

K Academy for a bit where you know was like kind of sketching on on tablets like I was doing here and then he thought there was a better way to do it because he's like a math computer science major so then he he kind of built his own software so you write these an in Python and they're very high quality it's called manim mathematical animation um so it's it's a python library and then you can build these really really nice visual visualizations everything I made in the course content is from there but he so he like made the software so he's like phenomenal at it and he's like made incredible visualizations not just that he's made incredible Vis visualizations but also

that he explains it in an amazing way with like really fitting visualizations I think the the video there is also talking about these rotations as um as as group as a group um so yeah any content from him is like very much worthwhile to take take a look at but yeah having visualiz visual representations of some group elements and some examples is like very helpful for your group understanding but don't forget to also play around with a group yourself and like try just check

if a few things are a group um is going to be um sort of essential and Z friend your question if the degrees have to be equal they do have to be equal because if they're not equal then they're definitely not the same polinomial you know if one is highest power is X to the 30 and the other is X to the 29 then by definition we know there's a term that doesn't match between them I mean yeah so I mean you can sort

of drop that requirement anyway like if you just say they have a maximum uh degree of like a million if they have a maximum degree of a million then the same if then statement is still going to apply because this this mouse here will change instead of three over um 2 to 2556 you you'll have a million over 2 to 256 and a million is a lot bigger than three but 2 to the 5 2 to the 2556 is still a massive number and this will still be um like. no and just go on for for ages so that will actually still be still be safe as long as it the degree above is a

degree is bounded right because the the polinomial can overlap um f and g can overlap because they're degree three they can overlap in most three three places um the the degree kind of specifies how many places they can overlap and if you don't have a maximum bound these can be different polinomial but if their if their degree equals 2 to 256 minus one which is just like an insanely large polinomial that we can actually we can never evaluate it because it's too big unless it's very sparse when most of the terms are zero

then these two polinomial will actually be overlap everywhere on the curve in our space except for one point um so theg we don't necessarily need them to be equal but they has to be bounded thank you

Alex like I said you can always ask questions in the intro to snarks chat if you add me in there I'll get a notification and I should respond pretty quickly and yeah please try um get used to some of these ideas we're just going to keep building on them and elliptic curves are not straightforward either but the next session should be the the next next hard session it'll be the same time 8:00 p.m. on Thursday um next session is going to be tough again in terms of mathematical content but then the fourth session not that it'll be easy but it won't be like as in intense I know when all these ideas are introduced in the beginning you're just a bit like what is going on but the more examples you see the more

you'll get used to it and even if you don't understand it perfectly now if you try and put in some work and then later on you'll do another course when you start that course you'll be like in much better position um um to take on everything and just keep expanding your your knowledge base perfect

well question sort of slowed down I'll probably hop off now but again you can just ping my name in the chat and I will I will respond quickly so thank you all again for coming and yeah we will see you on Thursday