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

Transcript

here for this third session out of the four please let me know if there are any issues if you can't see me presenting can't tell if I am good to okay cool um yeah so well done for constantly keeping up the energy and and coming back I know not all these sessions are easy yesterday I mean last session was particularly hard and this session is um not as hard but you know some some way in that direction um apologies for not getting the recording of the last session out um

too quickly it just went up a couple hours ago there were unfortunately someone was traveling and didn't have internet and um okay can't see the presentation yeah that is a it does say nope I'm no longer presenting hold on did I drop change audio output huh strange let me just close Discord and re open it

okay go back to Port stage speak on stage share your screen um yeah so unfortunately we didn't get the previous session out too early if for those of you who weren't able to see it I hope that the online content was hopefully somewhat sufficient after all what we're presenting is just a um interactive format of the online content similar General points we've got the the um online material I think everybody will have a link if they don't you can ask in the chat and then we'll drop it for you and please do stop me at any time if there's any kind of issues if my screen

goes off again let me know if if it does I might just move back downstairs where I did things previously and didn't have any issues um Because the Internet is occasionally choppy here but we'll see how it goes I just want to quickly recap and go over what we did last session again you just kind of see these ideas again and again and you'll get more and more used to them and we built things up like I said we're kind of building up a pyramid and you need to have the the lower levels in order to get to the higher levels as well so we started off with modular arithmetic wherein we have a relatively straightforward rule something like five equals zero and that

we have this clock arithmetic you go 1 2 3 four instead of going to five you go back to zero and you can set that to to whatever 11 or 200 and in general we've said it's like a very very large prime number we can use that set and setting to build a group that takes the set gives it a binary operation an operation that takes in two things like additional multiplication um and we also have an identity element which is dependent on the binary operation so in addition the identity element has to like when you add that number you have to do nothing to it so that's add zero and with multiplication it would be multiplying

by one we then smush two groups together to get a field because we had the set and instead of having one operation we'd have two and instead of having one identity element we would have two so just growing this up we then had pols over X and we introduced Pol in the first session as well but we specify I'm sorry my mic here it's off um we specified pols to be um powers of X we stick with one variable just X we don't need to have an X and A Y and a zed for example and all the coefficients all the things in front of the powers of

X you know if we have 4X the coefficient is four we kind of restrict those to being in a field for example F1 or [Music] FP we then built up to this final lemur or this this idea the Schwarz zipple Lema and it says that if you have two polinomial and they're the same degree and you evaluate them at a random number from a very large field then if their evaluations are the same with almost with overwhelming likelihood the pols are the same we kind of sketched out a bit of a proof of that last session and that will come into

play a bit later to argue that a computation has been done correctly okay so we're going to take these ideas in the f um in in this session in the first half we're going to introduce one more thing called elliptic curves and this contains fields and groups and we're going to be using polinomial as well we then have something called dlog which is like really really important security assumption and there's a particularly interesting Rel ship to um wallets in particular your public key and we're going to understand that a lot better and why that security um works as it does and then the second half we're

going to go into polinomial commitment schemes which is um I've said before that a lot of what happens in snars is to do with polinomial and US manipulating them and a lot of the way we manipulate them is related to a polinomial commitment scheme okay um so I hope you're ready right what I just said oh okay no so many snarks do what they do over elliptic curves um in particular most non-quantum secure snarks so snarks that aren't resistant to quantum computers they will generally speaking use elliptic curves and the

reason they do is that it it's kind of a more efficient place to work in okay mesh can't see the slides is everybody can other people see the slides or is that going to be a general issue if it is I will just quickly move downstairs it will be frustrating okay okay if it's one person then I think maybe to continue um so most non-quantum secure snarks will use elliptic curves because they're just a very efficient place to do um to have our security in and we're going to touch on that a bit

later um maybe restart Discord I think I can restart Discord but uh if it happens again then I will run down oh well sorry gong okay almost there oops okay sorry I got jump the gun there a little

bit um so let's dig into um what what curves elliptic curves again they're just a curve that we can draw on on some axes and this is the basic equation we have y^2 = X Cub + a x + B I'm just going to oops go to um sketch so cures we got y^2 = X Cub + a x + B and here A and B are just any kind of normal numbers so you know a could be three or it could be uh minus 4 or it could be 5.1 or it could be

271,000 sketch them out on some axes they also look fairly non-complicated they'll either just kind of let me do a different color here they'll either look sort of just like this and they'll go up to Infinity that way and down to Infinity that way or they'll kind of they'll look the same except they'll have a sort of egg or bulge just to the left of the axis so they're not particularly scary looking

curves one thing to note it's not abundantly clear from my from my sketch but these are um symmetric so if this is four and this is the Y value then when we go down we go across here this is going to be minus 4 basically if we have you know the top half if we just mirror and reflect it onto the bottom half we will get out the bottom half okay so they um they have symmetry about the x-axis and that's because of the definition of the equation this Y2 what what this implies is that if y satis

satisfies the equation then minus y also does because um - y^ 2 equals y^2 because the negatives cancel out okay so we have a a symmetry in this in this curve yeah here's a couple more images also online you can have a kind of bold coming out to the left and it may or may not be connected to the main curve you can also have the situation where it sort of like touches it

oops you can have the situation where well this is very bad sketch it sort of the bubble just kind of touches it like that but this it doesn't matter much they just a bulge and a line and it stretching off to infinity and stretching off to infinity and so to the left here all the way to kind of negative Infinity there's no curve there because none of the X values there have a can satisfy the equation but all the way to the right to Infinity you can have values that satisfy the equation

we can do something particularly interesting on elliptic curves so I did pre- sketch a curve here so here we're going to be doing oops eliptic curve addition so here i' got another sketch of one of these curves I spoke about and we've got two points we got p and we've got Q we can add these points together and this isn't going to be normal addition we're not going to take the coordinates and add them together we're going to kind of Define a new binary operation a

way to take into things and spit out something else but it's not going to look like anything we're kind of used to in in maths so the way we Define this is we'll get our two points and we'll draw a line through them and we'll just extend that line until it crosses the curve again here we're we're mathematically guaranteed to cross the line of the equation at a third Point um if we drew it through two points there's mathematical reasons for that and they don't particularly matter to us right now we just can accept as a black box that there is some proof that shows that

we will always intersect it at third third point and then what we do is we just reflect across the X AIS till we get here and then we'll call this point P plus Q okay so that's all we need to do is draw draw the line through and then find in section and then reflect again okay so even though it's a kind of strange idea that we can build a new

binary operation this one's quite visual it's kind of quite nice to do to calculate it by hand the coordinates is a lot more annoying um but it's not too complicated but visually it's quite nice and relatively straightforward just going to copy this can use it afterwards oh well fantastic try that again okay

I'm going to um let's let's explore that a bit more because I'm mentioning a binary operation you're probably thinking back to groups because this is the where that terminology came in and you're going to wonder is there a group here somewhere and there is there will be and in order to get that I want to demonst at a couple more things about what we have here let's paste this in

oops okay so let's rub up some of this as well so firstly what else if we if we have a binary operation and we're looking for a group what else what might we be looking for what else is kind of important any anybody remember we're going to need a set yeah yeah yeah we're going to come to the set but what's the other thing that we wanted we're going to need an inverse as well we'll get to that after there's before we get to an inverse

there were three things we needed in a group um in a group everything has to have an inverse but but that was like not one of the three objects we need in there yeah yeah we need the identity element so remember that for addition if we want to we need to be able to add something and it should like do nothing to it so that three plus something and you'll get out three and of course the number that satisfies that for addition is is zero for addition zero was um the identity element for multiplication it's one but if this is our binary operation where we draw lines between um curve points then you know this gets a bit weirder what what's

identity here and we can think through it a little bit we remember that the last step in that addition that we did is that we actually reflected across the x axis so if we want to end here at P well the step before that is to reflect across the x axis so here so somehow we need to draw a line through p and somewhere else and end up in the reflection of p in the in the x- axis and if you think about this the only way you can achieve that is if we just have a vertical

line right we'll have a vertical line because that's the only way to intersect the curve in the reflection um down here but but if we've got to draw um lines between curve points is there a curve Point kind of directly above P well if this just kind of if the curve is going up this way way to Infinity we would say no that there's not a point above here that we can just draw a line through and there's not but we can just add one we can just in a sense we can have our coordinates like this that

stretch off to infinity and just say there's kind of a circle around it that is infinity and we can add a point here at Infinity but Infinity to the north at the at the top so it's it's a bit strange you can just say there's a point at infinity and of course because Infinity is all directions you can go in any direction to get to Infinity but we're talking about when you go just up there's like a North star a northern infinity and if we just accept that that's a possibility we can then draw a point from that North Star we can just imagine a point of above p and draw

vertically down through it cuz if we do we'll intersect here where we wanted to intersect and then reflect back over to get the P okay so a little strange when we call this point at Infinity o kind of like a zero you know we can do the same thing with Q if we've got Q here and there's a point at Northern Infinity I'm just drawing it here because it makes a bit visually nicer then we can get vertical line through it intersect here and then reflect back over and get out

Q right so there's a point at Infinity here the the the important thing to think about with the point at Infinity it just lets us draw vertical lines and if we can draw vertical lines because these curves are symmetric we can turn out to be able to get back the number we started with or the curve point we started with so now we have an identity element so and like people asked last session we're starting to find an example of a group that's not justes doesn't just contain normal numbers

but you also said when I was asking this question what else w't we be looking for we're going to look for a set and we're going to get to that um in a couple slides but for the inverse we have a similar kind of thinking problem we're going to just this up we're going to need to find an element that when we conduct this addition we should be getting back um the identity element because that was the oops because remember like we want three in originally in the normal groups of

normal numbers we want 3 plus X to equal um because it's addition it should equal the additive identity element which is zero um so X would equal minus 3 and in here we're going to want P plus X whatever it is and we want to get out the identity element which is this big O um so now if we try and think through that again a little bit about this okay get that now we want to

find something um thinking backwards again we kind of want to end at a point that such such that when we reflect across the x-axis we end up with the point at infinity and that's a little strange kind of Unsure how that should work we can sort of go in any direction to to Infinity but we also want to make sure that that um this will be consistent with addition and how we expect it to behave um so so someone's asking is the identity element unique in the way we

just defined um like it is a unique element there's not here two separate points to kind of represent the point at Infinity but that was just it makes it look a bit prettier we can imagine it just being Northern infinity and wherever we get to it we can only get to it it's actually about the the gradient and if it we can only get to it if we go like perfectly straight up you know we can't deviate a little bit sideways because then we won't get to the same point we just want to do the the vertical up so it is a single point there's not multiple copies of

it and here if we want to get to that point that goes perfectly straight up the only way we should really be able to do that and is by going yeah a line vertically through which brings us back to this opposite Point again and we can kind of maybe guess maybe this should just be the inverse element we call this minus P because what happens if we do um then if we draw a line through these two it will just go up to infinity and also sort of go down down to Infinity but if we go up to Infinity we should hit the point at

infinity and then maybe we have to reflect across the xais which sort of takes us to Infinity going downwards and it sort of does um but here when you're getting started it's best just to kind of accept that it's um if we go vertical we're going to hit the point at infinity and we can take that to be the result because we're more interested in angle okay so this is our uh element okay so what happens now if we

just check does this kind of obey our normal expectations about how addition Works let's find out out so we have a couple interesting points here we've got oops we've got p+ Q over here right and we also know that here well what we're expecting now should be minus P so what happens if we add minus P to P plus Q so p + Q plus minus p i mean our expectation by writing out should be that we just kind

of get out Q so let's see what happens if we draw a line between these two and then you know giving some leeway for my qual sketching quality we get out Q right so that's actually what we were kind of expecting um yeah natively to happen with with our operation and if we do this it turns out to be quite logically consistent so we've got our binary operation we've got our identity element we've got our notion of an inverse element something that undoes it the last thing we have to

clarify is actually specifically what set are we interested in because we're not going to be working here on this infinite plane when we actually do stuff okay bringing in more of these ideas we're going to work with something called elliptic curve over a finite field so rather than working the infinite plane we're just interested in finding field so I draw a little sketch here um here we're working over f11 and in our y axis

we go from 0 to 11 and in our x axis we go from 0o to 11 okay and because this is uh a field because it's a field and we we have like the modular arithmetic work in f11 we have that 11 is congruent to zero what 11 so these Dash lines at the top this dash line at the top is actually in the same position as at the bottom it's kind of like if you get a bit of paper and fold it together and have the two lines touch those two lines are actually the same

line as far as we're concerned and the same is true on this right side with the left side the left axis okay so we can connect the paper up one side and for the other two sides we sort of have to connect it again we can't do with real paper we can only do it with one side but it helps you visualize it a little bit now if we take our elliptic curve equation let's just say it's y^2 = X Cub + x + 4 you know I don't know exactly what it actually looks like but let's say it looks like this curve we were just

working with then if we try and draw in cuz here was sort of working with this quadrant this portion here right so if we try and draw in that line let do the same color for purple then this line kind of goes like that sort of through the middle then we can sort of draw in this line like that okay but because of this modular arithmetic group because we have the 11 equals z if this if this point here is the same as

this because we can take away 11 and get between them we can repeat that process and it it turns out that this point here is also the same as these two and also going up you know that's that's modular arithmetic for us so this bottom quadrant can also sort of be mapped over to there which means that this line is also in our space okay and then we end up mapping every single infinite quadrant like this into this single

space right so we've got taking this infinite curve and mapping it into this finite area but this area this 11 by 11 this is not infinite you know that you know it goes to 11 only but even there it's discreet so if we just zoom in here and let's say that this point is 1 comma 1 then we have all we have an infinite number of points in between here right we got 0.1 and .01 not point1 And1 and that just goes on to Infinity but none of those points are actually in our finite field because they're not

whole numbers and so even though in this area there are an infinite number of points in this 1 by one square we only have a single point this this one there okay so when we draw over these these lines from the curve they will only actually be in this space if they happen to go through one of these integer coordinates let's just say this is 41 right so of this whole curve the only part that's in the curve is that bit and the rest just gets

rubbed out and this vanishes too and what happens is this in curve turns into a finite number of points here because if this is f11 then we have 11 * 11 which is 121 there's only 121 points in this actual graph you know it's not continuous we only have 1 one and 1 two and 13 and 01 and 02 Etc so now the elliptic curve I did pre-draw it all these yellow dots are all that's left of our elliptic curve and here there's two four six eight 10 11 points in our elliptic curve

over finite field this now looks kind of scarier right originally our original curve drawing was actually quite straightforward you just have a bendy line that goes up to infinity and down to infinity and we have a little leg sometimes but then we end up in the finite field with just some points weirdly spaced about about you can see that they're still symmetric about this line okay so there's still something there that's familiar but it looks very very different and that's actually quite valuable to us important because you can't it's very hard to connect the points to each other and that kind of adds to some of our

security which we're going to explore soon so elliptic curves oh sorry and specifically this is the set that we now want to work with all these 11 points here is going to be the set that we work with in our elliptic curves over a finite field and going back to the idea of a of a group it it turns out that if we conduct the the same um uh but addition logic we had where will'll take two points and draw a line through them like this point and this point if we draw a line

through them well we're mathematically guaranteed for the same thing at some point this um line will intersect the curve at a third place and here we can kind of go to this point and then we'll go back up here because again that's because of modular arithmetic that's the same and then we continue with the same gradient and we we seem to hit it here and then we can sketch over to here so if this is p and this is Q it adds to P plus Q here so now we have all the things we wanted we've got a set a finite set is

what we're particularly interested in we've got a binary operation this weird curve addition that we can just draw lines between two points and then reflect at the other intersection we've got the inverse element P minus P because of the Symmetry and we still also have this point at Infinity you know we can draw vertical lines and that's part we just kind of accept to be true it's a bit for a lot of these tools in cryptography especially in the beginning it's much better just to kind of accept some things as a as a black box that we don't

know why but we know how to use it again it's kind of like Wi-Fi like I don't know what Wi-Fi actually does I just I know that it connects me to the internet I don't know how I don't know what protocols it uses or how it splits up data into packets but I I know what I can do with it I can connect to the internet wirelessly and that's sort of the understanding you should be going for here we know that there's this point at Infinity that allows us to draw vertical lines doesn't matter why it's there there we can draw vertical lines and we're symmetric here about the x axis or the or the middle right that's elliptic curves over finite

fields and then you can see that addition works as well so there are like little gifs of this in the online content and we've covered all the aspect of groups we've got the identity element and the inverse so then just before the break we can go over this discrete logarithm problem that I just told you about um and this is actually going to be very interesting relate to um our crypto wallets discrete log problem yeah the so it's actually discret uh

logarithm problem let's just do a problem and this is where we'll have the same setup with the finite fields and we're going to have um a bunch of points I'm trying to draw more here just to make it a bit bigger okay so we have this weird curve and if we Define this point here to be G and G stands for generator we're going to use um G is going to be the standard kind of name for a lot of points if we add uh we can add G to it

itself and get out various different points so here um if we have let me write this out here if we have if we take n lots of G and we get out P okay so G added to itself many times so for example if we add G to itself we might the first one might be here and then get reflected here so that would be 2G and then we draw oops to get to um 3G we're going to draw a line between G and

2G and then somewhere this is going to oops intersect let's just say it's here we have 3G and we can repeat this process and get up to some number we can call it n or for a concrete example let's just say it's um 11 use 11 let's just say it's 9 gal P here's the statement of the problem if you are given G and P can you work out n okay you're given G and you're given P

can you work out what n is so if I give you specifically here 9 G which is p and I give you g can you then figure out that it g was added to itself nine times right so that's the statement of the problem and then we have something called The dlog Assumption and the assumption is that you can't that it's just it's hard the dlog assumption is that dlog is hard and what we mean by hard

is it which means that there is no simpler way to solve this problem than Brute Force so if you want to solve this problem the doog problem in this example here the only way to do it is just Brute Force you'll check G you'll check 2 G you'll check 3G 4G 5G 6G and you'll just keep going until you find um that 9g

matches P so the the assumption is that there's no quicker way to do it you just have to Brute Force here and then this means is if if n something we know if n is in FP for you know a finite field with P elements for for some really large prime number P then you can't work out um you can't solve dlog you can't work out n okay like theoretically you can you

can just keep running computers but when we make p be large enough it will take the world's best supercomputers millions or billions of years to Brute Force um one of these okay and that's like a lot of where our security comes from when we do elliptic curve cryptography and particularly interesting is I said is an assumption like it's not a theory most stuff in in math we're like we're certain we know for 100% we have a mathematical proof that shows us something is true this is one of the unique cases where we we don't have a proof and it's it's nothing to be

worried about that basically every mathematician believes that it's hard because for elliptic curve cryptography people have been trying for hundreds of years and they've made no progress whatsoever you can be smarter about how you conduct The Brute Force but there's no way to properly directly solve it um and this is kind of related to some other big problem in math but it it's it's kind of easy to show that you can do something because you can just do it but in order to prove that you can't do something is very very tough there's an interesting

example with ruler en compass and that if you let's just draw it here if you have this and you have this angle can you perfectly split this in two and the the proof is nice remember we got Compass so you put the compass here and draw a circle around that point this is very bad drawing and you could put it the other side and draw a circle around that point and then when you get this intersection apologies for the very poor drawing the intersection will perfectly split this in half if you do it correctly with a with the compass and

that was proved thousands of years ago they they knew that I think that might have been nucleus elements they showed that you can perfectly cut this into two but then it was asked can you cut it into three pieces into three pieces so have a line there and a line there with with a with a compass and ruler and they couldn't do it and they couldn't prove that they couldn't do it either and it seems to have taken around 2,000 years to prove that that's actually impossible because to do it to show that it's possible you just can find a way to do it and there's often more than one way but to show that it's

not possible requires a lot more understanding and it's actually group theory that allowed a proof of this to be made that given the operations you can do with a compass and ruler it is impossible to to split it into three so even though this is an assumption nobody is is worried about it and with relation to crypto wallets um this is your secret key public key PA your secret key secret key is some number in a large um

field and your your public key does it equal Secret Key multipli by G well G is a curve point so it's got It's got two coordinates it's got you know this um let's do this here SK G it's got its x coordinate it's y-coordinate but public key is like the same you know basically the same length as the secret key so it's not equal to the secret key of G but it is equal to the x coordinate um of SK multipli by G right that's actually what your secret

key is is a number in this Prime field and then that's why you can work out your public key from your secret key because you can just um add G together to itself again and again and again until you get SK G right and then we have signature schemes and other things that allow us to to prove that we we own um the secret key right and again people can't work out your secret key because we assume that they can't but if it ever happens you know it things would change quickly it seems to be very very safe and this is also this dlog problem this

why elliptic curve cryptography is not safe against quantum computers because we know as a fact that there is a Quantum algorithm Shaw's algorithm Shaw's algorithm that can that can break dlog assumption that it can take for example s your key G your public key and work out the secret key okay but so now you're starting to get to the point where you can understand more of the cryptography used in general in in the crypto space there's not much more complex objects

Beyond this there are some more complex tools like hash maps and even hashing itself I you're starting to get a very good basis of everything around I think that's is that um just for anybody who's done kind of cryptography before if you know of RSA which is how a lot of online security was maintained in the past it's similarly based on an assumption that if you multiply two large prime numbers together um we can't figure out how to factorize them that was also an assumption and this replaces that because it turns out you just you can have the same security for a smaller number number which allows you to have

shorter keys and things like that but if you don't know that don't worry that's just for people who already have some awareness of it and we can take a take a pause here and then come back in five or seven minutes for for the second half where we're going to see a kind of more complex tool to work with polinomial we got a question from Fran to get your public key you got to enter G andk how do I get random SK um yeah I don't actually know what protocols they use for this to to generate the secret Keys there's many ways you can use sort of what's happening in your computer to derive some Randomness and the all these

methods seem to be like safe enough some mathematicians complain that it's not like true random there not like it's not perfectly random but it's it's very plenty for for our um purposes like I know there's one company that they use kind of lava lamps if you know what lava lamps are they kind of like the the liquid that moves around inside them and they just take an image of them and somehow use that their random movements cuz we can't guess how they're going to move to make random numbers but I'm pretty sure it should just be something going on in your computer that that has some random like if you code you know you can get random number generators and some lots of them are based off of uh just what's going on in your computer um alternatively actually

that's not entirely true because um I guess some of them do use a different technique because you also you know for your secret key lots of them are not um they are a string but instead you might just have 12 or 24 numbers not numbers sorry words you know like tree jump flop what whatever those words are and instead of calculating a secret key directly I guess what oops what they have guess they a sort of dictionary let just do this L case allies

jump you know whatever all these words are zero and then it will take take 24 from here at random so you want to calate random numbers to get out these words and then what you do is you're going to do a hash function and a hash function is a kind of um we assume them to be random functions they kind of take in something and their output is random and a a way you can think about the method we think about for for hash functions is that it should sort of be the same as if you for every new

input let's say the input is you know allies and then the other 23 words that to figure out the output it should be equivalent to just making up a random output and then that output should be tied to that input so that each new input will have a completely random output but that if you put in the same input you should get out what you got previously and that's why you can also recover your account your secret key your public key from that list of words because the list of words they just put it through a hash function and get out the number that they had before and one of the reasons why they want to use words kind of 24 words it's

a bit easier to look after if you got a long string 0x 358 whatever if there's any damage or some bad writing or things like that to figure out what the word um the whole number was it's very hard to figure out what changes should be made but if you've got like jump um and it's a bit you can probably tell that it's jump It's like a lot easier um I I don't know the size of this list of words I'm pretty sure it's massive um because it's it you know it's sort of like a dictionary attack but the fact that you put 24 of them together that makes it un like un brute forceable you know if it's going to be if this list is two to the 10 and

then you do it to 24 like 2 to the 224 you know it becomes a a very huge number very quickly that's why some of them use like 12 words I think maybe metam Mas does and that's like a lot less secure if you have a cold wallet sometimes they'll have like separate accounts inside them where you'll enter a pass phrase and if you do that's actually what it's doing here it it knows your 24 words and your past phrase is kind of a 25th word that's added pass phrase and in that way you can get a

different like account on the same C wallet yeah can I mean because the words are you know short it sort of feels like you can but if you check the probability you put 24 of them in a string together that's suddenly like a very very huge probability space to to ch um look through again because if it if it wasn't we would just double the number of words and if it still wasn't um sufficient we' double it again and it turns out that 24 is actually sufficient for for most of us I mean basically everybody like 12 is you should be more cautious okay just another 30 seconds or so

break if okay I think we

can get on with the second half and here we we're no longer going to be introducing new mathematical objects from here on now we we've built all of those we're now going to look at a kind of more complex system through which to work with them and then next session we'll see briefly how to use that that system to kind of do plon in a bit more detail and then we'll explore just some other proof systems at a very high level so first thing we got to cover is that we can EV we can sort of evaluate polinomial not at normal numbers but at uh curve points instead it's that's a

little bit not entirely true but that's the easiest way to think about evaluating evaluating poly nomials at EC points let's take a polinomial fairly straightforward let's do F ofx = 3x^2 + 4x +

2 now we've seen before and you probably did Lots at school you can evaluate this at a normal number if we do F of 2 we got 3 * 2^ 2 + 4 * 2 + 2 which is 6 * 3 um 18 sorry that's 4 * 3 is 12 + 8 + 2 just gives us 22 right it's a fairly straightforward we've seen before but we can also evaluate it you know if we've got elliptic curve and all its points you know if for our actual elliptic

curves there's you billions like huge two to the 256 points on there and this one here is G our generator because if we add G to itself nonstop we'll actually go through every point in the curve before getting back to G so that's why we call it a generator it kind of generates the the set if we to instead do F of we we still kind of write F of two and then instead we just let me do this in a different color we

append we append G to everything CU F of 2 3 * 2^ 2 G + 4 * 2 G + 2G equals well it's 22 before so it's going to be 22 G this time around so it looks the same except that we just Chuck a g on at the at the end and and the reason why we can't we don't put in like f of 2G you might if you had some time to think about it you hopefully go down this this logic group but an elliptic curve is it's a group I mean we can make a group from it and

it's a group but not a field so what does that mean it means that we only have one binary operation but so it's either additional multiplication so if we tried to do this we' get 3 * 2 g^ 2 plus and here you'll see that we've got to do 2 g^ 2 that's 2G multiplied 2G but then we need to add afterwards so we'll be trying to do multiplication and addition so we're not exactly putting a curve point in um because yeah it would uh Define the kind

of rules we made but there's another way we can do it so that we don't put in 2G we put in two and there's kind of a g g there for us and you might be noticing now and thinking about well if you have if you get out 22g well we don't know it's 22g like if you give it to me I don't know that it's 22g I just know that it's some curve Point p and you can sort of see that we're hiding a number there but the point here is just that you can evaluate an elliptic curve sort of at an sorry evaluate a polinomial at an elliptic curve point and then we're about to connect this in because if you

remember you got to sketch out but we made pols during our proof system so I think next SL I'm just going to do a sketch of where those are okay I'm sorry before that we want to talk about something called a point of unknown order and again this is because of the dlog Assumption it kind of be in lots of places if we're given a point p and we know it's NG we don't know what n is and this you know allows us to hide a number there but this is also sort of a a form of of Randomness which I'm going show yeah I mean we we've seen this if

if I give you P it's 22 G but you don't know it's 22 it's it's hidden so if we can find a way what we want to do is find a way to make something like that where nobody is going to know that it's 22 or whatever number it is yes this is what you might see this name around this is called a trusted setup ceremony or a powers of towel ceremony is another name for it what we want to

is we want to get out um T which equals call it s G where nobody knows s we want everybody to know T we want everyone to know G we don't want anybody to know s in the online content we didn't want to dig into it we just said imagine somebody you just really trust does give this to you so for example David atra

he makes T from s he gets an S he multiplies it by G gives you T and then he just deletes s from his computer and I trust David atra I trust that he's given me a real thing and that he doesn't know the number um in in real life in the trusted setup ceremony it's a very effective design in that if 10 people take place take take part only one of them has to be honest for the whole for the number in the end to be secure and so if it's not 10 but it's 100 or a thousand people one them be honest you can you

know if you can't trust that one in a thousand people a single person out of a thousand is going to be honest then I don't know if there's a basis for online communication or or systems but we don't it's not actually just tea that we want we want more than just T we also want t^2 which is s s g we also want T cubed which is s cubed G okay and then we're just going to go and then we want up to some large number like T to the N which equals s to the n g um okay so we want actually tons of

these um up to some maximum number for ZK friendly your question why can't we do why can't we do 2g^ squ well because that equals 2G multip by 2G now I know what 2G plus 2G is because in our curve draw here this is this is 2G here right so I know I can draw a line through it and then that's going to help

me find uh 4G because we defined addition but we didn't Define multiplication we only have one binary operation and we said that it's addition but then we go and say that we want to multiply an elliptic curve Point by an elliptic curve point we didn't Define a multiplication right there's no there's no concept of multiplication here you know in addition we draw a line between two points and an intersect somewhere else that's how we do do addition how do we do multiplication we don't have an equivalent so we're not allowed to do

multiplication there's no definition of what multiplication is um but that's actually a good point to bring up something else um notation wise going forwards if you're going to be looking at elliptic curve stuff because we have only one operation one binary operation sometimes it's written like you know here I'm saying we have G Plus G and that gives us 2G but in a lot of places instead of doing additive notation we do more multiplicative where it's kind of G * g = g ^2 and sorry if that's a little confusing but it there's only one biner

operation but sometimes it's written like this and and sometimes like that so that scares you a little bit just kind of ignore it for now but then if you see inconsistent notation later I'm trying to think back to this but going back to this set up setup ceremony we want to get out these power powers of T and the reason why we want these powers of T is that if if we have our if you remember that we drew our circuits this circuit here has three gates in order for us to make a proof about this

circuit we're going to need T and t^2 and T cubed okay so what you might see here is this value n is going to represent the largest circuit we can make so if n equals a million our largest gate circuit can have a million Gates this is the issue of uh I think this it's not very often that this will be a problem because I think they make a million or 10 million of these numbers um but once it's made and you only got 10 million if you suddenly need a

circuit that's 12 million or 20 million or whatever you can't make that circuit unfortunately you'll have to do another trusted setup ceremony and get a larger number you can't just have a million and add more on top the only way you can do that is by knowing the secret number from beforehand so doesn't doesn't quite work um right but it's kind of elliptic curve cryptography here that makes us need this trusted setup ceremony like there are some proof systems out there some of the non postquantum secure ones they don't need this trusted setup ceremony but plon does and lots of lots of them

do grth 16 actually needs a setup ceremony for every single circuit you make you don't know what growth 16 is don't worry but for those of you who do you've got to do a setup ceremony every single circuit and I just want to Res sketch how we made our polinomial so that this next part will be become a bit clearer so this is kind of this is actually just recap recap um how how bigger can M can n be in a trust ceremony are you asking like how big it can be because it um you have to decide

its value and then you just work with that so we might say hey guys let's make n 10 million and then we run our setup ceremony and then when it's finished we're going to have 10 million of these points but we can't add more of them later we can update the 10 million we have and you know add in another thousand people to contribute to them but we can't uh we can't add more of them if we want to go from 10 million to 100 million we've got to do an actually new setup ceremony and it will take a long time so recap in previously when we when we made a circuit remember here we had oops those are not actually

connected do an addition right so we had we had this oops to do Mo this a little bit further away let's put in some numbers three and four so this is our base circuit this is the this is the let's call it the starting circuit and then we again just recapping from last time

when we went over this then we're going to add it oops we going to add in the witness yeah let's just do two and two again 3 * 2 is 6 and two sorry that's 3 + 2 3 + 2 is 5 and 2 * 4 is 8 8 + 5 is 13 and and to to question plon is universal but what Universal means is that you only have to do one trusted setup ceremony and then you can reuse the um the secret numbers the points of unknown order is what we call

them we can reuse them again and again uh Groth 16 is not Universal so it has to do one for each circuit it makes like if you know if this is the circuit it's got to do one for this circuit and then it can reuse this circuit but if you make a different circuit you got to do a trusted setup ceremony and hopefully you remember here we turn this into pols poly nomials I say we I mean the prover only the prover can do this because they're the ones who know the witness polinomial we're going to have

do a few different colors colors we're going to do L of X and this is going to be left for the for the left y so this is 3 2 and five why do that why does it change these lines sometimes two and five so we're going to do 3 + 2x + 5x^2 I'm going to do R of X and that's the right wire right wire right y so that's 2 + 4x + 8 X2 and then we're going to do the last one we do o for out of output Y for the out um for the output y so this is an

output yre um this is an output yre 5 and 8 and 13 5 + 8 x + 13 x² okay so this is just recap that's how we made pols before and now maybe you're beginning to see how we can use some of this stuff if we have t and t^2 and T cubed now we can we can commit to L of X we can do L of T that's going to equal 3 G + 2 t + 5 t

squ okay what's that equal to well we got 3 G and remember that we said that t equals SG right is it s what we used uh yeah we did s so 3 = 3 G + 2 SG + 5 s² G if we add that all up together we're going to get 3 + 2 s + 5 s and then G okay so that's what that's what it evaluates to but for for me or you or whoever receives this curve point this just equals like P I don't know how many

G's are in there I just know that it's it's p and this is our commitment what commitment to levx because it you know we made it from levx and it kind of collapsed that information from in this case from three points into one point but if our circuit had a million Gates then we would collapse a million values into a single value right and you know if you give that to me I can't go back and work out

tell what polinomial you had if I could I would you know be able to figure out your witness but I I can't like you just can't do that and then we can go on we can do R of T = 2 G + 4 t + 8 T ^2 and again that's 2 G + 4 S G + 8 s² G and then that's 2 oops that G2 + 4 S + 8 s^2 G and then we can call that P Prime just to distinguish it and then of course we can do the O of

T but one really interesting thing to notice here is that L of X was evaluated at a random Point okay everybody knows T but nobody knows s so what what this is actually equal to is uh sorry not F it's equal to l of s multiplied G but nobody knows s so even though we're evaluating this polom add a at a known curve point the

polinomial itself is being evaluated at an unknown points and a way to help you understand that is that if we're going to evaluate L at a random point then we'll evaluate L and we'll come up with a random number let's say seven and then we'll evaluate it but then when we evaluate R we can't use seven now I know that it's going to be seven I can modify modify my polinomial to give a certain value at seven because I know it's going to be evaluated at seven so then I would need kind of a different random number if we

want to make it random each time but in in this scenario we all know to you but it's still random so we can reuse it for r because even though we know T we don't know s okay which you know it's a very strange idea and that's very helpful for a couple reasons because then we don't have to make as many random numbers but also in the in the start in the very beginning the first for the first bit of Randomness we need we already have it

if the prover made If instead the prover made L of X the first polinomial where would they get a random number from to evaluate to an um they could you use their polinomial levx and like hash it or do something to derive a random number but then to check that they'd have to reveal that polinomial and then they'd be revealing their witness so it it doesn't work or you know maybe there's some online place you can get a random number but then that's not trustworthy we have some issues there but in this scenario we got everybody together to make a random number that we all trust is random and then once we use it we can

actually keep reusing it okay so we and then we get out P we get out P Prime and then we get our P prime prime as well for for the third commitment o o of t and that's the start of our polinomial commitment scheme we've now committed to polinomial but we want to do something afterwards because if the Prov just commits to them like you know then what what what's the point What's going to just go return to slides commitments on on an

order what's going to happen is that the verifier I mean what's the point of committing the point of committing is that once we make the commitment the Prov can't now change the pols they started with right they can't change their starting if they do we're going to be able to tell we're going to see that their commitment doesn't match the polinomial that they're now claiming that they have in in the online material what I say um is that the prover will reveal their

polinomial later to check their value that that the commitment was was valid that's not what we actually do for for two reasons the first as you can probably tell if you reveal the polinomial you reveal your secret information your witness and it wouldn't be zero knowledge secondly if you had to reveal polinomial and these polinomial can to have a million points you've got to communicate a million points to each other so you know really not ideal very slow and reveals a knowledge but instead we have something called um uh an opening

proof and the opening proof is a part of the polinomial commitment scheme it's going to allow the verifier or us to check that any new value that the prover gives us we can then see if it came from the same polinomial so what's going to happen here we've got the three commitments the Prov knows of course their polinomial uh what's going to happen is verifier is going to create um a random

well another well I guess it's not another because they've not created one before but they they create another random number Alpha okay let's not use Alpha let's just do a or R small R okay and request L of R and R of R okay bit of abusive notation but okay and o of R so then the prover Prov

gives uh Q Prime not not prime q q Prime and Q prime prime which is's claiming that Q equals L of R and Q Prime equals R of R and Q prime prime equals o of R now that the Prov is giving us these new evaluations how do I know how does the verifier know that these equalities are actually true and that's what we're going to use in our polinomial commitment scheme does the verifier know the form of the polinomial or only the result the

only thing the PO the verifier knows is the degree the size of the polinomial the the highest power of X because the highest power of X is the the number of uh gate in the circuit but aside from that they they don't know they they will actually know a couple of the values like in this example here you see that three and four are actually pre-known values they were already decided so the the verifier might know there small bits but they don't know much about the polinomial so now the Prov has given new

evaluations that he's saying are from polinomial um we can actually check whether they're from the same polinomial because the pro not will not just send Q and Q Prime and Q prime prime it will send a proof little this is not the zero knowledge proof this is like an opening proof opening proof and uh P Prime and sorry pinee Pi prime prime

and there's a way for us to check in a polinomial commitment scheme we're going check that uh we're going to put in uh P which you remember was the commitment the original commitment uh Q which is the new claim value and Pi for the proof and this going to do one of two things we're either going to be happy or we're going to be sad and if we're happy it means it checks out it means that P Q are from the polom and we're going to be sad if it

turns out it doesn't pass p and not from the polom it doesn't matter how this check works all that matters is that we can do it um but this this happiness is actually uh occasionally there'll be a passing proof that shouldn't pass but this is actually where the Schwarz zipple Lema comes in that if if the Prov was honest the thing will pass because remember that

the polinomial will evaluate the same value but occasionally you can have two different pols and evaluate the same value so that's we got Schwarz Schwarz zipple going on here in fact the the final check in in plunk is basically uh a ton of these checks all mush together you got like tons of them but you can actually squish them all together into one and then we check that and that's actually why the plk proof comes out was probabilistic because there's some small chance that it was

fate but why does the why does the verifier actually like want another another ver um another evaluation from these pols it um the these pols are designed in such a way that we can actually predict how they're going to behave and more specifically we we can we have understanding how q and Q Prime and Q prime prime relate to each other we have expectations about how they're going to relate to each other you know not if we evaluate evaluate them at random number we don't

know what we're going to get out but we know that if we evaluate them all at the same random number because of the way we designed these Pol pols or chose them we can have expectations about how they'll they'll work together okay so that's why the verifier um wants more evaluations so the prover is going to represent their filled in Circuit by polinomial they then commit to them so rep

resent they then commit to them and then again the point of the commitment is so that the approver can't change them and then the verifier can start to kind of question question or query their pols so this is kind of the query SL question the pols and then the verifier with these results can kind of um play around with them and see if they behave as as they're expected and that's what we're going to see in the brief overview of plonk next session

so just a recap polinomial commitment schemes they take in a polinomial and they compute a commitment to the polinomial they don't stop there though because if you just commit to polinomial it's sort of like what's the point unless you reveal the whole polinomial later um but that's not ideal we have much better techniques the ones we're interested in they allow for something called an opening proof which is just another uh field element or or or curve Point actually it's just a single curve point and that can be used so that was this little Pi that I drew the opening proof that that curve Point can be used to

check whether the commitment and a new evaluation from that polinomial are actually from the same same so it's quite a big complex system there's a lot more to it in terms of the details and and how it works and why it works and how you might implement it there's a lot going on there but a lot of what happens in elliptic curve based snarks is polinomial we use discret log for a lot of the security to make sure we can't so that we can have random

numbers and also have an identity because the public is is um protected by the dlog Assumption and then the polinomial commitment scheme is going to allow us to after representing a circuit in um as polinomial will then allow us to evaluate those polinomial and query because if the circuit was filled in correctly we know how these polinomial should behave that's one of like the Crux that's like the Crux of what's going on because of how we chose or design these polinomial we know that if the circuit was filled incorrectly because the polinomial are a representation of the circuit we know how they'll behave with respect to each

other and okay that's the end of this session so in the first half we kind of we we introduce another object elliptic curves we show the elliptic curve we can get a group from it where the set is the elliptic curve over a finite field we introduced this kind of strange new binary operation that we call elliptic curve addition and we have this identity element which is this point at Infinity that just allows us to draw vertical lines we have the inverse Elements which are the reflection on the x-axis of points because our curve is symmetric and then we introduced the discrete log problem

which is a security assumption that is not Quantum secure that is how a lot of our wallets represent our identity and then we've seen in a polinomial commitment scheme that allows us to uh commit to polinomial and then and then show that new evaluations came from the same polinomial there's a bit of like a whiz tour through a lot of the maths that's here and for right now it's it's really the best thing to do is kind of make as as many of these black boxes as possible and just say like this does that other thing like a functional understanding like I mentioned about Wi-Fi or or the

internet you know you know even getting water out of a tap like I don't know where the water's coming from I don't know the whole system behind it I don't know how the internet works well I kind of do a little bit but but not very well but it doesn't matter I don't need to know all these different protocols I just know need to know how to use it and a lot of what you can do with these tools is is use them as black boxes if you know um what's allowed and what's not allowed that's perfectly fine because when you make snars when we make snars because these because these numbers these y values they're they're elements of a of

a finite field so when you're cing if you're going to be a programmer if you're coding there's no such thing as an or a u64 or a string everything is just a finite field number all right so there's a maximum number and there's only certain things you can do you can only do addition to multiplication so if you want to represent a string you've got to have like a more complex system in logic inside uh that will tell you how to represent a number sorry a letter has numbers this isn't full this is like we call it vanilla plonk or very basic plunk there are different types of gates as well we can have like a lookup gate

that will uh you you can check if something's in a table and a variety of others that that give a bit more diversity but because of this setting it will determine in large part how you're allowed to code stuff you know another thing is that uh there's no you can't really have an if condition in a in a in a circuit because in a zero knowledge circuit it's just a set circuit and if you have like a you know if yes and if no and this is an and and this is an or or whatever it's going to be you can't like occasionally have the left side and occasionally have the right side you can only have both of

them so any any branches that you'd have in a normal computer program here if you have them your circuit is bigger which slows it down a lot you know you're going to have to have you're going to have to evaluate both of these even though you actually want one so if possible you want to avoid having a branch and try and represent it in a single thing okay but that's a bit off topic for homework I mean I recommend an Anie cards for like what is an elliptic curve an elliptic curve group why can we hide numbers which is really important and

then how can we commit to them and what else is a PCS polinomial commitment scheme allow so of course I'll Stick Around for for questions but like a big well done to everybody for getting through all all that I know it's not really very nice and sometimes you listen and it's kind of very tough because it's these are dense topics and this is really a whirlwind tour to show you as much as possible um a broad basis but a little bit everywhere so that if you so that you can have a basic you know you can have a conversation about a lot of this stuff and that you can enter a more advanced course and be much more productive there so I'll stick on for questions can

a question maybe not directly to this and kind of not fundamental question since right so if you want to think about modularity of a of a proof system we going back to the image from kind of the first you have your idea and then you have a um an idealized circuit but we're can just skip that part and go straight to the the circuit arithmetization so what's allowed we've got long

Kish arithmetization that's the arithmetization we do here with the addition Gates the multiplications Gates or they can be something called rank one constraint system which is doesn't matter how it works but it's just another option or there might be something called an air an algebraic intermediate representation um and there's some other ones out there there's like versions of this like relaxed R1 CS or or uh yeah can't remember the names of others right now so there's some of those that you can choose from um and I say that we go from the I mean w w

witness with the witness we might go to pooms so the way we' represent stuff as a polinomial is kind of standard but um we don't it doesn't just have to be a polinomial that other systems can use different different things but they kind of want to represent stuff some how and then we sort of like check pooms behave uh so to do this to check that they behave we we're sort of using our poal commitment scheme it's actually like a it's actually something called elliptic

curve pairing that we do at the end but this is where like a IPA might happen instead and there's different types of things that could happen here and even if you're going to choose even if there is a polinomial commitment scheme you can change which polinomial commitment scheme there are different options so the these parts this you can choose stuff here there's stuff here that can be chosen the the pols that we make in plun uh there's actually you actually have a choice as to which polinomial you have you can you can change the polinomial so that you can add different types of gates I mentioned that you can

do like a lookup gate and some other types of gates like up here so the choice of polinomial will will affect the kind of um Gates that you can make so you can like use Halo 2 and just and or like use plun and and change which polinomial you the specific polinomial you want to work with here or you can have a bigger change and try and change the arithmetization or change the argument at the end a lot of these changes like this choice and and and this choice these are more by like snark experts who are making proof systems but this choice is you like if in your ecosystem you can

be like we well we want this type of gate as well because because of the type of computation we do it's going to be particularly effective and we're going to get rid of this other gate because we barely ever use it and all it will do is slow down the system um yeah there was one other thing I wanted to mention butly slipped my mind uh yeah but all right so you also have a choice of like which elliptic curve to use be BLS 12 381 is a popular curve it's it's got 381 bits is the size and but this curve has certain

properties and in general it's a very good curve because it's very popular there's a lot of like tools for and implementations in different places but you can change which curve you use you don't have to use this one I think this is the one that ethereum uses as well um so they got another Choice there and a lot of these are really just swap in swap out um you know you just you can use a different curve if you want and the elliptic curve was defined over FP and you can choose FP I mean in bls2 31's actually already chosen FP but U you know that part is separate cipic equation at next session we'll see like

a little a couple other things you can choose from as well because more properties CU you can have something called recursion as well and some other stuff yeah for for a lot of cryptographers the elliptic curve stuff is is just a black box like uh some people understand and coded how elliptic curves work and how to do addition how to do it efficiently and how to do this pairing operation at the end but I mean like you don't need to dig into the details you just need to know that if you're working in f11 that 7 plus 8 is not 15 but it's four like that's the only part you really need to know okay so next session is not going

to be there's not going to be much like uh Theory we'll do a little bit of plon just to sew all this together into that large idea but that's really quite short first half and then we'll explore just about some other systems out there um we're not intending to code a proof system together and there quite like a big undertaken if you want to do it I it would be a very very good learning um a good very good way to learn like I mean a fair amount of the logic is when you break it down to the separate pieces of like how the logic works is it's very doable by by yourself um ideally in groups though um but then

when it comes to like how do you write code for like how to make these circuits because how do you like put Gates down how do you write code for that and then how do you connect the wires together is uh just that I mean that's like a lot more like Logistics annoying where like you know visually we can imagine we just plunk down Gates but then codewise is a bit more annoying I mean if you don't want it to be a generalized system you can just have it be a very basic ineffective way to put down Gates um and then just check if it works it'll be very cool to learn but really plonk by hand is like a very very nice way to see what's going on from start to finish similar to some of the stuff I've done here or the star tutorial at the end of

the online content I've not done that one but I'm pretty sure I think he kind of goes through the the theory behind it and also coding some of it in in Python so yeah the rust is very popular it's I mean of people who use programming languages rust Community is like the most Hy like we we really like coding in Rust it's really nice but it's also you can make it very efficient and for things like cryptography which if you're not careful would be very slow it's particularly um appreciated and valuable to have there but you don't have to if you just want to do it for learning purposes you don't have to use rust you can use like a python instead CU again it's for your understanding of

like how the system works and things like that um and some of the tools like uh the repositories libraries um cargo packages in Rust like for cryptography they're you know they're good but some of the apis aren't as nice they're a bit more restrictive Now by Design because then it helps prevent errors but if you're playing around then python might just be a lot quicker and a lot more frustration free my

pleasure so I'll stick around a bit longer but if there's no questions I'll just hop off had more sketches this session the last two thanks Charlie I hope there was a successful recording it's appreciated take that stress off as