Laurence Kirk - Essential Maths for Zero Knowledge Proofs

Transcript

thank you hey everyone hope you're all having a good day uh if You' brought your lunch in hope you're enjoying that uh so today's talk um oh it's gone blank uh well there will be a QR code um there we go so it's a QR code so you can get the slides for this uh one thing I've done this talk before uh so quite often I don't get to the end uh which is a shame because I do like to to share all this information if I uh if people if I to the end or if people want more uh I'm more than happy to set up another session online so uh I've got some contact details yeah there if you so if you want to know more please join our Discord server or DM me by some

means or other and if you want to see this again online uh I can set that up so just let me know so yeah there's contact details um so please use those uh if you would like to all right so what this talk is uh is aimed for is for people who are new to the idea or new to zero knowledge proofs new to their maths behind zero knowledge proofs uh it can be quite a daunting topic and there's a lot of terminology if you start to read articles about Zone o proofs there's lots of terminology that you may not be familiar with lots of areas that you may not have come across before and it can be quite daunting now my belief is that this area is accessible to people it can

be explained uh to to to people people people can understand it to some extent and can get some insight into how these things work and so that's that's what I'm going to try to help you with today by giving you some of the background math some of the background terminology so you can then read articles you can look at Zer knowledge proofs and get more insight into how they work uh some good quotes here um from some uh people working in the area uh this stuff is hard I I I accept that but it can be explained uh it to uh to some extent um please do ask questions if I'm not explaining this well I really do want you to be able to understand this

uh my advice though is don't try to understand everything at once there's lots to uh take in so take it at your own pace uh certainly get familiar with the terminology this is one of the things that I found uh perhaps confusing when I initially started looking in this area there suddenly all these new symbols and ter ology that I hadn't come across and when I actually dig dig into the area and look at what these means I found out sorry I looked at what these mean I found out that these weren't such difficult Concepts after all it was just that they were new to me at the time so what I hope I can do is by introducing you to these is to to give you an idea of what they're about and that will help you understand uh zero knowledge uh also a good idea is to try to chunk some of

these topics and some of these areas uh one of the problems I found with the the Articles and the literature in this area is that often they they sort of jump in and do a kind of a depth first approach they'll go in and go into a huge amount of detail uh straight away and that's really hard to follow what I find is easier to follow is if you take a look a sort of higher level look at the overall process and then gradually work your way down and and chunk areas and maybe if there's an area that is confusing or you you don't understand well accept that just to treat that as on its own as a little black box or something like that uh and then come back to that later okay so that's the approach so let's look at some of the terminology uh

we are going to cover so when people started uh developing Zer knowledge proofs and I mean this goes for cryptography as well I guess what we've tended to do is to restrict ourselves to very specific sets of numbers uh and the reason is that this these are easier to work with uh this this is this makes our life a lot easier and so pretty much when we're talking about zge proofs when we're doing the maths when we're doing the operations we're talking about operations being done on integers uh and for those you get this Zed symbol with the the double slash uh of course there are other types of numbers as well the ones that you uh will be using dayto day were going to be more like the the real

numbers um but with jge proofs we've restricted what we're working on and this gives us this makes our lives easier gives us uh easier um representations and in fact what we do as well is we we uh build our maths around things called finite fields and I'll explain what they are in a moment um and you will see some of these yeah these symbols like the the the Z with the asterisk in the P I'll explain what that means but you'll see this quite a lot and it's not difficult to understand but if you've not come across it before it's going to be uh a little confusing all right so another thing we do when we're doing operations is we use modular arithmetic uh and I'm guessing that a lot of you here are maybe developers and

so you've probably come across these kind of operations the idea that uh we uh we're more interested in the remainder when we do our operation um and yeah I'm sure you've used the mod operator in in various languages sometimes called clock arithmetic as well um it's just yeah we're we're interested in the remainder so we're interested here in the uh I guess that's the uh the minute hand or something rather than the hour hand um but yeah so we we use that because we work on uh sets of numbers that have a maximum number so we need the ability to wrap around uh and so be working within a fixed set okay now uh one topic of maths that you probably didn't do at school uh is

group Theory and uh it's not particularly conceptually that difficult I don't think but it's probably you just probably never come across this but this is we do need to understand this a little bit we do need to know some of the terminology that uh is involved here and the the way I like to approach this is to think well the mathematicians and the cryptographers have just they're you they're using this because it gives some useful properties to the the uh numbers that we have and what they've done is they've just they've just chosen some sets of numbers and some operations because that works because that makes their lives easier because it means we can do things with those and if you take this pretty much at face value then I think it's it's easier to follow what's going on so the idea behind a group is

you take some set of elements in our case we're going to be using numbers it doesn't have to be numbers I guess but we we are going to be taking numbers and we take some operation and in this case I've represented that as a DOT and then we say that uh given this particular set we've Chosen and this particular operation we've chosen we can regard this as a group if it follows certain properties if it has certain features and those are the features I've got here I'm not going to go through all of them because we don't have a great deal of time but some of the important ones the first one for example closure this makes sense because we we've chosen our set of elements that we're interested in that we're going to be using and we've got our operation and we're going to be

doing operations on these elements now we want closure so that every operation we do on any element is always going to give us a result that is in our set of elements we don't want something that is going to be outside the set of elements we want it all to be nicely self-contained so I think that makes sense it's it's uh it's sensible to be able to do that other things we need to know about the idea of an identity element so the easiest way to think of this is if you think about uh some operations that you're familiar with so for example if you think about addition an identity element uh for addition will be zero because if you add zero to an element you just get the same elements again so it's okay Sim simple Concepts

but just uh terminology you might not have seen and then the inverse element this is the idea that if you take one element in our set there's always going to be an inverse for that element when so that when you combine these using this operation we get back to the identity element so if we're talking about addition then uh and you're you're thinking of say some positive integer then a negative integer of the same value would be the inverse for that okay so um yeah and that's just more uh termin uh of course we've we've chosen this group of elements uh it could be that there's actually a smaller group within that set that or a smaller set of elements within that bigger set that is

also a group and that's called a subgroup and then we also have this idea that there's a possibility that this this group could be uh cyclic as well so this means that we can start with some uh element that we call a generator and then we can repeatedly do operations and this will take us through all of the elements within the group okay now if we extend that we get the idea of fields and uh the uh example I'm going to give here is to say that we're going to have two operations we're going to have addition and multiplication but again we start off with some set of numbers a set that uh is going to be useful for us but now we have two operations but again what we do is we

say well if we have this set of elements and we have these operations then it's going to be a field if certain uh properties apply if certain it has certain features and they're very similar to what we had before um you so you can see we've got things like the uh identity element and we've got things like inverses now uh let me see if it's on the next slide yeah one potential uh problem or difficulty I guess with this when you think about multiplication uh is that if we think of multiplication we tend to think well if we thinking about an inverse we would think be thinking about division because we typically s of see that as the the the opposite of multiplication but the the problem that

we find if we're using finite fields or if we using Fields uh and they are fields of integers we have to be careful with division because if you divide some integers you might get an integer but you might get something that is uh not an integer which is would be outside our set so the inverse under multiplication is a little bit more problematic it's more difficult to find but there is a way to find that uh and I'll explain how to do that uh in in a second um typically we talk about finite Fields so we're going to have a set of elements that has a maximum number uh and we use uh modular arithmetic so if we go past that number we're just going to start again at the

beginning um quite often this maximum number is going to be a prime and if you look at the the finite Fields underlying a lot of the uh the Zer knowledge proof technology and uh things like Tic curves you will see that these are they have a maximum number uh that is a prime and that uh you know these are relatively large numbers um and the other terminology might come across the order of the field that's just the number of elements that we have in our field okay um so uh again we have things like generators in finite field so really this is an extension of a group we we're

getting the same types of things happening that we have in a group uh and if we have a generator this means that we can do some operations such as if we if we using multiplication we can repeatedly multiply and then this will take us through all of the elements within our group so a useful a useful property to have and this is used in the way that zero knowledge proofs are constructed um there's an example there a nice simple example uh to show you so we have a a group we've decided just to take uh five elements so 0 1 2 3 4 uh so they are integers uh if you look at some of the operations you can see that the we can we use modular arithmetic so it

it gives the uh the answers there when you do multiplication um and then also we can work out some of the generators as well so if you start with two uh that can generate all of the elements within the group uh or within the field and similarly with three as well okay all right so that's just a little termin about groups and Fields uh but when we're doing they fi certainly finite Fields form the basis of when we're building Zer knowledge proving systems I'll just talk a little bit about complexity Theory uh because this is useful uh well it's it's really where Zer proofs came from or or part of it but also it's useful when we want to

look at different proving systems and to compare them and decide which ones uh are feasible or not uh we often use some ideas from complexity Theory I'm not going to go through all of this again because uh there's perhaps more than we need but I'll just mention it uh mention some aspects of it so complexity Theory itself is a very interesting area of uh computer science or maths and it's all about looking at problems and trying to get uh see if we can group problems together that are similar in some way and see seeing whether we can classify problems and the what we we typically do is we look at a a problem and we look at how easy it is to find a solution to

that problem particularly in terms of the size of the problem and so if we take the very famous example of the traveling salesman problem that is a problem where we're we're trying to we have a route that a Salesman is taking between various cities and we want to know whether that is the most efficient route that the salesman could take now when I'm when I talk about that example you could say that the size of the problem is determined by the number of cities that are involved and if you have a small number of cities then it is a relatively easy thing to solve it's a relatively easy to make a decision about whether you've got the optimal route or not so if you've only got three cities that's not going to be hard to solve but as you increase the number of cities as

you increase the size of the the input to this problem then it very quickly becomes much more difficult to find a solution and it will take you much more time to find a solution and in complexity Theory we uh measure things uh we usually talk about the time complexity but we could also talk about the space complexity which really relates to how much memory you would use in a computer if you were you were trying to solve this um but yeah we're usually talking about the time complexity and uh what we find when we look at these types of problems is they do indeed uh fall into a number of categories they have certain similarities and uh but really what the way we're going to use it is to be

thinking about how the the time taken to to solve a problem or actually often we're talking about given a solution how quickly can we verify that solution and we want to look at that in relation to the size of the problem so in relation to the input how how does the the time taken to verify a solution how quickly does that grow because that gives us an idea of the efficiency or the the feasibility of one of our proving systems and uh the it's not a great yeah so uh one uh classification of the these types of problems is called the pclass or polinomial class and what this means is that uh when we we have one of these

problems in the worst case uh it's going to increase According to some polinomial of n where n is the size of the input so if it was the uh we're talking about the number of cities then that's what n would be and even though that might sound like that is quite large actually this is seen as quite a feasible thing so we're talking about the the time taken to to uh well to solve or to verify a solution maybe is proportional to n to the K where K is probably some reasonably small value but some constant and that is the the polinomial class of problems and if your problem falls into that class that's seen as being tractable that's seen as being uh feasible to solve uh and we the this

what we would like these are the types of problems we want to work with um the way that we tend to uh talk about these problems is we we ter them in terms of a decision problem where we say it's going to be give it a yes or no answer that's just the the way they've decided to do things but the the classes that we get are shown here now the reason we've got two diagrams is there's an open problem in maths whether one of these classes p is equivalent to another one of these classes NP and this is an open problem if you know the answer there's a very large prize waiting for you uh and fame and fortune um but at the moment it seems that they are probably not equal I think the consensus is um but it is

still open um so our class of Problems P these are the ones that are uh solvable in polinomial time uh and then the other classes that we have these are shown here I don't not going to go through all of them the interesting one mainly is the NP class so these are seen as being more difficult but particularly what we are interested in is these class of problems are ones where it could take a long time for us to find a solution but to verify that solution we can do that in polinomial time so that's the solution can be verified in polinomial time and this uh oddly enough or maybe not oddly but this ties in very nicely with zero knowledge proofs because with

zero knowledge proofs one of the things or what we're trying to do is to we we start off with some computation for example we create a proof of that and then we want to verify that proof and we want to make this uh efficient we want to that to be feasible and so we like this idea that uh we have something that can be verified in a small amount of time and in fact there is a relationship between these types of problems the NP problems uh and zero knowledge proofs if you want an example uh of this type of problem uh you can think of this this one I was showing here where if you imagine you've got some encrypted piece of text if you try to decrypt that just by guessing the encryption key that

would take you a long time and uh you just have to just Brute Force the the key really and and guess at that but once you've got the key when you if you want to verify that you've got the correct key you can do that very quickly because you can just use that key to decrypt the text and it should come out as something sensible so the verification can be done in a short time even though the solution is going to take you much longer um I won't go through the the other ones they are interesting but uh we don't really need to know too much about those um one uh useful thing to know uh I don't know if I've got this here is that uh there is a relationship between uh n problems in NP and Zer knowledge proofs in that you can create

a zero knowledge proof from problems that are in the NP class uh the other oh there you go that's the the the article uh quoted there the other uh thing that I just mentioned at the bottom here another class we have the interactive uh the IP class the interactive proof class this is really the basis of where uh Zer knowledge proofs came from because they uh they were thinking about how we create mathematical proofs and typically that would be you would go through a number of steps and then at the final step you would have the the thing you were trying to prove and if you can get there correctly then you know there's your proof and what some people started to do was to say what if we make this interactive what if we say we we're

going to go through some steps we're going to have someone uh that's going to interact with us uh and maybe that person who's interact with us is going to have some going to be able to use Randomness as well and ask us questions about our proof and it's going to be uh more of an interactive process and that really is the basis of where we we started with Sero proofs and there's some very good uh videos explaining all of this so there's a link to that there okay how am I doing four okay so now why this uh why we need to know this uh particularly where it becomes particularly useful is we have some notation for representing the complexity and this is the bigo notation and so what you with the big unation what

you're doing is saying in the worst case how does the time taken either to solve the problem or to verify the problem how does that change according to the size of the input and the size of the input we're usually representing by n and so you will see things like this we will have Big O of n^2 that means that as n increases the time taken to find a solution or time taken to verify a solution will change according to n s and so this is the terminology this is the uh notation that we use to compare proving systems and to try to decide whether they are feasible or not and uh if you think about the way that n could change obviously if we' if

it's according to root that's going to be better than if it's changing according to say n cubed something like that and this table is is rather old I'm afraid but it is quite useful because it shows uh admittedly a few years ago the the complexity or that gives you a comparison of different types of proving systems so at the time there were really sort of three main families I guess of proving systems we had the snarks the Starks and bulletproofspeaking.com second row or sorry the third row down there if we look at the size of a proof when we're generating a zero LGE proof If you do that in one of the one of the original snar systems what this means

We've Got Big O of one which which means that no matter how big our input is the size of the proof is constant which is which is a great result uh that that's what we want we want our proof sizes to be as small as possible so that works very nicely for snarks but for Starks it doesn't work quite so well obviously it's it changes according to the the size of the input um and but that gives you an idea this is what we use this is the terminology we use when we're comparing different types of proving systems but this is a little bit out of dat so don't take it uh yeah uh perhaps look at a more updated version okay so that's a little bit about some notation and about complexity and how we can compare

systems uh another mathematical uh object that we use uh a lot is very useful are elliptic curves there's actually a talk about elliptic curves I think just after this one so uh that's going I'd advise you to to follow that uh but these are curves um they they follow a a kind of formula similar kind of formula um but what's nice about them is they actually have if you look at the points on these curves they can form a group uh so they have some very nice properties and elliptic curves have really been the have been the bis of lots of the types of uh cryptography and uh for example signature schemes uh that we have used and they are then quite nice uh in uh compared to other types uh

of signature schemes you get because they uh they can give they require uh much smaller keys for the same level of security Now um yeah the the I said they they form a group the points on the for on the curve form a group uh which means if you do an operation ation on the the points on the curve then the result of that will also be a point on the same curve but we are restricted on which operations we can do um now you will often see them represented like this uh now and this shows uh a sort of geometric representation of doing some operation on some points on the curve so you've got we're doing some operation on

P and Q and that is going to give us the point R um uh but the point is that whatever points we choose and whatever operation we do the result is always going to be on the curve and the cryptographers uh they will choose the equations for these curves to to uh to give them things uh to give them curves that are going to be useful are going to be quite efficient so they they choose them and different projects you will see they have different named curves uh as you can see here some of the the names of them uh these have just been chosen because they work quite well maybe they're they're quite efficient in uh when they're being used um I probably don't need to say much about this but the the scal of

multiplication this is just a way that we can um easily do s extend the operation because uh if we don't have the multiplication operation we can instead just do repeated additions and that will give us the same as doing a multiplication if you do that a certain number of times okay um roots of unity is something else you May another term you may come across and this is to do with a when we have the the points on our curve we also include a special Point uh which is this point at infinity and uh we just have this property that for for particular points on the curve if you

effectively multiply them doing that by repeated addition uh if you do that and you get the result one then these are called then a root of unity um so you'll you'll see this uh you'll see this terminology as well that's where it comes from okay uh so yeah this is visualization you often see actually if you this sorry this one is uh drawn over the real numbers okay and that gives a nice nice visualization if you actually do it in the kind of underlying fields that we are going to use if you do it in a finite field where we're doing modular arithmetic you actually get something like this so this one is in a field or

over a field uh mod 1 191 and if you uh and it's using integers only if you plot that that's what an elliptic curve looks like but you know it's not as nice to look at so people tend not to show that all right is that okay so far all right I'm getting some nods that's good okay so um other terminology you will see there's a a process called pairing and uh this is it can be I guess it's quite complex but it's is something that is useful when we are uh for some types of well proving systems or some aspects of uh systems called polinomial commitments we need to be able to do this process called pairing and it all

comes back to the ideas of being able to do things as groups uh and that this gives us some special property this gives us some kind of shortcuts when we can do them so if you've chosen your groups uh in a certain way if you've got the right types of elliptic curves then we can have this property where we can do uh this pairing which means that we have uh so here we've got G1 G2 and GT uh so these are three groups so these could be three groups Each of which is formed by the points on an elliptic curve and if we uh have if if we can do pairing on these these curves then uh what we we're doing is some operation

between groups G1 and G2 which are going to give us the the group GT uh the final group there and they there's a couple of properties they have which we don't really need to say much about but the well the the final one is useful because if we've got the correct elliptic curves uh if pairing is going to work for them then this gives us some useful properties uh so you get uh for the different points within the different groups we can then uh write out equations like this um and um things like at the end there where you've got where you're adding uh points but you can change from the the additions there into some multiplications and this again

is it's just some background information really that is useful if you see pairing people are doing this because they want to be able to do these sort of operations on the points on the group um because that's going to be useful okay now if you start looking up uh Zer knowledge proving systems what you will find is that pretty much everything is revolves around uh pols and which is good in a sense because polinomial are things that you've probably come across before you've probably had some experience with at school you've probably uh used polinomial you've tried to solve polinomial um and these are quite remarkable objects and one great thing about them is that they can oh

uh they can do they can hold a great deal of information and with with Zer knowledge proving systems what we're often what often we do is we will have a prover who is trying to make some claim and they uh this claim will get transformed it may be some computation uh or it may just be that they they're trying to say they know some number but that that claim will get transformed uh into different formats uh but what we do is we transform it into pols and the reason we do that is uh that polinomial have all sorts of useful properties which means we can manipulate them uh and draw all sorts of conclusions about them quite easily and they can hold a

great deal of information and um that's what this this quote from vitalic is talking about saying that yeah if you you have a polinomial even though they look simple uh with that kind of equation they can actually hold a great deal of information but of course when we're doing this with uh in you know real world zer proving systems we're having we have polinomial that are much bigger than that and maybe there would be a million terms or something like that so they can be quite large in that sense but still they are they can hold a lot of information and then particularly if we start to build up relations between polinomial so the the details we've got here these these capital A B and C here if we can write an equation down like that then that uh is an

incredibly powerful thing that we have because that means for any value of x that we choose we can uh you know this equation is going to hold and uh so you can you can say you can say things like that and uh what we'll see is that uh the the process of doing uh or verifying proofs often comes down to being able to easily evaluate polinomial but also to generalize about the pols that we have um it's also useful that polinomial manipulation is quite easy uh so multiplying them Etc is quite nice uh and we can divide them

quite easily um although when you get big polinomial there are special techniques that uh you can use as well uh one technique you will see is this process of breaking a polinomial down into smaller polinomial and this relies upon the fact that you have this thing called the root of a polinomial so you've probably come across this you've probably used these or done at school youve tried to find a root what it means is that the root of a polinomial is the value of of x if that's the the variable for your polinomial where the polinomial evaluates to zero and um if you can find that so here I'm saying the the particular point to which this polinomial P valuates to zero is r and if I know that then I can rewrite my

polinomial P in this term of uh I can bring out this extra term xus R and multiply that by another polinomial but it's a polinomial of smaller degree it's a slightly simpler polom and this technique is is used quite widely um and you can you can build up uh this quite a lot with inero proofs now uh one of the really fundamental parts of uh of proofs is this Lemma here which is saying that different polinomial are different at most points and this really goes to the heart of why polinomial are useful in that we can easily make we can easily check on them we can easily decide

whether two polinomial are equal and as a starting point for understanding zero knowledge proving systems you can think that uh maybe the prover is going to incode their claim in a polinomial and then they're going to give this to the the verifier and the verifier is going to check whether this matches a kind of an ideal polinomial now there's lots of that's accurate in all sorts of ways but it's a as a starting point we can think of something like that and why pols are useful is that the verifier can very easily check whether the the polinomial they've been given is in fact the one that they want this in fact correct or

not and because what we would like is a Prov to be to be passing their proof to the verifier and the verifier to be able to make a decision very quickly whether that proof is correct maybe just doing a few a handful of checks on the polinomial to see if this correct now and that's why the this Lemma is particularly useful um you can see it visually in this kind of thing so we've got two polinomial that are different uh and they intersect at one point but for most points you can choose they are different so if I gave you uh if I gave you the evaluations of the blue and the green polinomial at different points you you could see that they are different

different and if you want to do that with a minimum number of checks and you just started picking points at random well you probably would find there different the chance of you picking the point where they intersect is fairly low and this is particularly true when we talk about the types of fields that we use and the types of numbers the sets of numbers we use for zero knowledge proving systems because the the order of those is going to be things like 2 to the 250 so if I pick a a number at random and I evaluate uh polinomial there the chance of them intersecting if they are in fact different is very low and that gives us a bound when we're looking at our zerge proofs that gives

us a bound on How likely it is that we will accept an incorrect proof okay but I uh I have missed a lot of things out there um particularly when I when I say about the pro sending a polinomial to the verifier this is wrong in all sorts of ways it's wrong partly because of the zero knowledge aspect because the prover wouldn't actually want the verifier to have all this information they're wanting to keep some inputs to the proof secret so there's they really wouldn't want to send all of the information to the verifier in case the verifier could somehow reverse engineer that and find out the secret information also in terms of what is called succinctness we don't want that

because we want a very small amount of information to be passed to the verifier and when the verifier is checking something for example imagine I've done a computation this was a long running computation it took 10 years to run uh but at the end of it I create a proof that that computation is correct now if I pass that proof to a verifier I don't want the the verification time for that proof also to be 10 years because that would there would be no point in that they might as well just rerun the computation what I want and what we get is the fact that we can verify that within say milliseconds and so this concept of succinctness the idea that the work that the verifier has to do is going to be much smaller than uh the

original computation or that the uh the uh when we we're passing information to the verifier we don't want to pass too much that is very much of the heart of the types of proving systems we want to build so in fact the the approver doesn't really send the whole polinomial to the verifier what they do send uh are commitments to the the polinomial okay but before I go into that I'll just mention uh some points about representations of polinomial so when you look uh at something like that uh in fact if we go back uh here to the original equation we've got this is this is called the maybe the coefficient form of a polinomial we've got uh you know

the coefficients of various powers of X so that's one representation if you wanted to write out a polinomial that's one way you could write it uh the other way you can describe it though is by by giving the points where of the evaluations of that polom so these are the red dots on this diagram so either either of these is equivalent and we have means to move between the two representations so if we have our coefficient form and we want to move to the the point form we can evaluate the polinomial at various values of x if we want to go in the other direction if we have the points and we want to know the coefficients we do a process called interpolation uh and one way of doing

that excuse me is uh called uh is lonian interpolation um but it's a way we can move between those two representations okay which is what that says okay so uh how do we use these in in Z knowledge um so uh yeah this is the process I I I spoke about generally uh we we get the idea that the the prover is using polinomial in some way uh giving these to a verifier the verif yeah when you're thinking about these systems think about the motivations of theover and the verifier so theover wants their proof to be accepted and they don't want to give the verifier secret information the verifier is

suspicious and they think that the Prov may be cheating and so they want to satisfy themselves that that proof is is correct and the prover isn't actually cheating and so the the verifier they will get some information some representation of a polinomial maybe uh and they will want to check this and one of the the aspects of polinomial that is useful is that uh we can do checks what we do is we pick a random value from this big field that we're using this big finite field and we say to the Prov evaluate your polinomial at that point and then tell me the result and this makes it very difficult for the prover to cheat because uh they don't know in advance what the what value the the

verifier is going to choose for this so even if they craft their polinomial in a certain way that would work for a few points um but wouldn't be true in general then is they're they likely to be found out because the verifier is going to be giving them these random points from a massive range uh and so it's going to make difficult for the approver to to cheat that uh also I I spoke earlier of this idea that the the verifier has this idealized idea of what the answer should be actually I mean this this varies with different systems but it's more the case that they have an idea of relationships between polinomial they don't know exactly what the polinomial the the prover is uh going to send and they they that polinomial has

secret information in it so it makes sense that the the verifier couldn't know exactly what that is going to be but they would know certain properties of that polinomial or more specifically certain properties about some a group of polinomial that the theover is sending over and some relations between those polinomial and the verifier can then do these checks they can do evaluations on these polinomial and then see if the the properties that they're expecting still hold and from that they can make a decision about whether the the information the prover has sent is correct or not and so you get things like and I'm sorry this has gone over two slides uh but you get things like relationships of polinomial is like you

got to the bottom there where you've got two polinomial being multiplied together and so what the verifier can do is to check that that this is the case I can divide them and see when you divide these pols does this produce a polinomial itself or is there some remainder and if there's some remainder this is not an exact uh Division and therefore there is something wrong with what the approver has sent okay now I said that uh we don't send the whole polinomial uh with there's you know there's good reasons for that partly for to we don't want to send too much information to the verifier also because sorry we don't want to send secret information to the verifier uh

also because we don't want the information to be too large and so a better approach is to send a commitment to a polinomial now you you've probably come across the idea of commitment schemes more generally with things like hash functions where you can take uh some kind of input a message something like that and commit to that you put this through a hash function you get a result uh and because hash functions are Collision resistant that mean that gives you a commit to that specific value no other value would give you the same result and similarly with polinomial commitment schemes it's a way that we can commit to a polinomial and so when we have the process in zero knowledge proving systems with the prover and the verifier interacting what we can do at the start is to say to the prover okay I

want you to commit to a polinomial or a set of polinomial and once they've committed to that they can't then change their mind and when the interaction is going on and the verifier is saying okay verify sorry evaluate your polinomial at these points that I've chosen at random the prover can't then go back and take a different polinomial or craft their polinomial in a different way they've committed to a certain polinomial at that point the other uh useful thing uh is that uh with these these types of schemes um is that uh it gives a a compact representation of the polinomial as well um and it means we're not having to pass a huge amount of information if you had to pass a polinomial with 10 million terms that would be a lot to to

send to the verifier instead if we can if we can pass some commitment to it uh much smaller amount then uh that's that's going to help and because of the uh the properties of polinomial and the this idea that uh we can put them together and uh build these powerful relations um and equations with them that will be true for any value of x we can really generalize so if we have something like this equation here the P of Z * Q of Z Etc if we know that that holds for a particular value of Zed one that we've chosen at random then we can generalize that and say well it's overwhelmingly likely that's going to hold for any value that I can come up

with so this really helps the verifier when they're trying to make a decision about the correctness of what the prover is telling them okay uh and yeah generally the the schemes commitment schemes have two nice proper is there's the uh The Binding property which is making sure that we are committing to an exact thing because there's no uh there's it's Collision resistance so we know that they are committed to an exact polinomial uh and then also the hiding property there's some obfuscation going on so that when the the verifier interacts with this commitment scheme they're not finding out too many details about the polinomial itself maybe they're just getting the evaluations of that polinomial at certain points that

they're asking for there are different types of uh commitment schemes uh available and really these have very much shaped the the families of proving systems so uh as you can see here on the left hand side we've got things following the the fry uh scheme which is really the family of starks uh and uh then we've got on the other side we've got the the kzg uh which is plon and a lot of other snark based systems which rely on pairing so that's why we need to know about pairing uh and there are other ones as well um but these are the these are the basics and these these polinomial commitment schemes really form the the heart of our

uh our proving systems um these slides are from the uh study group which is uh quite useful um but they show how some of these different things uh relate to each other just just do this very quickly but uh so the the ones on the left there the hash function that is the fry sort of basis uh the fry based uh schemes um and you can see that they have all sorts of useful properties that some of the other types of polinomial commitment schemes don't necessarily have uh but then uh if you look at the this the proof size Etc the pairing groups so things like kzg they do give you better proof sizes so you can look at these different

comparisons and that may help you decide what types of proving systems you want um it also you can talk about the security but yeah I don't need go into that is that okay so far I've gone very quickly through that yeah go on have a question yeah go so this yeah this is really just saying according to the the size of the input if that's n then uh the time taken is going to rely on maybe the log of n which is better than n because that's

that's going to be smaller or maybe some polinomial involving the the log of n so that's what that's about go y thank you uh yeah so yeah thanks for the presentation by the way really good and I wanted to ask about the um you said that if the verifier picks a random point and evaluates a uh polinomial at that point gets the result and then asks the prover to verify that same polinomial at that same point and if and then the verifier compares the results and if they're true then most likely with a high degree of probability the polinomial are equal right um so the question is if that interaction can be then further is it

like as simple as taking that interaction and applying Fiat Shamir transformation and you get a snark that's it or there's it's more complex than that so yeah thanks for the question so yeah the idea is the interaction between the prover and the verifier the verifier is going to be asking the the approver some some questions about their their claim that whether that's represented by a polinomial or a polinomial commitment scheme but they they will have some way of then uh making a decision about that um and saying that you know we've evaluated this maybe this polinomial commitment scheme at certain points maybe this set of Pol omals and the relation between those when we divide these for example that works out as what to what I expect so I'm happy with that

and then you you mention the fistic and what that is about is uh the fact even though when we're understanding zero knowledge proofs it's useful to think of the interaction in the real world we don't want that interaction because what we really want is just the approver to send a proof to the verifier and the verifier to do a decision there and then maybe because it's a contract uh and so that's where we use f and what that does is a it's a verifiable mechanism by which we we take all that interaction we effectively squash it down and we actually get the prover to do it so we say okay what the verifier is doing is producing some random points now that's not really special um as long as those points really are random so what we can

do is we can get the pr to choose those points and then do the evaluations and do the whole thing and then send that to the verifier but of course you say well the Prov is going to cheat they're going to chose some different points which is why it needs to be verifiable so you need some scheme by which the prover will produce these points these random points which is verifiably random uh and which the verifier is going to accept and that's what F chir allows us to do it's we we start off with some effectively some seed or some starting point and then we we can do things like use a hash function to produce Randomness and the verifier can check that that's been done correctly they can check that given that starting point these random points were really random

uh and so they will be happy um but it means that the verifier doesn't have to do so much you know it's just a one-off thing uh and the the prover is actually picking the points and and creating the the the proof Etc from that it also is good for the prover because it means they are happy that the verifier isn't doing something malicious because they're really doing all the work so it has that Advantage as well is that okay all right cool okay um I'm going to skip this next bit uh these just uh oh sorry uh I had a question uh can verifier uh craft those points to try to extract uh the secret information from from the prover yeah good good point so

uh yeah this this is what the prover really wants to avoid it doesn't want the the verifier to be able to reverse engineer this thing and this is what uh this is helped by polinomial commitment schemes which act as a kind of a black box and so the the polinomial commitment scheme is there the the prover commits to some polinomial uh and then provides details of this this is built into this polinomial commitment scheme and then the verifier can ask for evaluations of the polinomial at certain points but that's all they get back they don't find out the coefficients of the polinomial or any other details there is this hiding aspect that means they'll get back some evaluations that point you know they say 099 what does this

evaluate to and it evaluates to 11 but that's all they find out so they they can't use that to then reverse engineer and also the number of queries they will do is relatively limited they will probably do a hand well if it was interaction they would only do a handful of queries so there wouldn't be enough to do any kind of statistical analysis either uh and then we have F so the pro is doing all this anyway uh and doing these picking these points so again it it makes it so the verifier can't do anything anything bad like that okay all right uh so I'm pretty much out of time I'm just going to see if there's anything um okay maybe I'll just finish here there's there's more I could go through

but I think it's just going to confuse if you've got any questions then please do ask here are some more uh resources if you would like them and as I say before if you want an extended version of this uh and you want me to do this online I'd be happy to do that so just let me know just DM me about that but if there's any more questions please do ask I think we've got a couple of minutes are sorry yes I am awesome thanks a lot Lawrence pleasure so do we have more questions in the audience yeah let me come over to you yeah yeah it's just for the recording actually I was told to uh what would be some Frameworks

which can be used to build on this math like for example uh we have circom znar Js right uh what all uh you would ask beginners to start with which Frameworks are better like socratis was one long ago so uh yeah there's lots of different Frameworks that you can use and if you're a developer you're going to be writing you're going to be using some DSL uh that you're then going to uh that's going to be turned into or transformed into polinomial as part of the scheme so you mentioned circom that's one of the the older ones it's very good because they have lots of libraries they've got lots of things gadgets already written for you what we're seeing more recently um is a lot of the proving systems are basing their

DSL on Rust like syntax and semantics so we've got Cairo we've got Noir coming out we've got risk zero which is uh Rost anyway uh so this makes if you already know Ros this is this really helps you with those so there's there's quite a choice I think if you're unsure uh and maybe you know Ross then I would go for one of those but there are other ones as well we've got Mina which is based on typescript um yeah there's quite a choice but that if if you're looking at the DSL um those those are the ones I would uh recommend all right thank you um can you just talk for a second about measuring space complexity space complexity because you said measure time complexity is pretty simple but yeah I don't know much about

that because people just tend to think in terms of of time um so I I don't have anything specific about I'm sorry about that yeah any more questions one more yeah so you mentioned that I forgot the number uh that elliptic curve number with 128 bits of security uh curve 20 5 519 and is it is it 120 how is that calculated is it like because it's of over the prime field of uh uh some prime

number to the 128 degree or so uh so this 128 business security is kind of a standard that that people use generally it just really is gives you an idea if you're brute forcing something how many operations you would need to do that um I don't know how they've come up with that for for this particular curve though I'm afraid yeah but like in general So when you say like the polinomial over a finite field of like certain finite field then you're you're referring to the coefficients of that polinomial being taken from the finance it's really just uh just an estimation I think of how how much would how many

time how many operations you would need to do to try to Brute Force something um uh uh so for example with these types of operations if you try to go in the other direction uh which you shouldn't be able to do and this is the basis of the the public private keeper then how you know how many operations would you need to on average to do that but I don't I'm sorry I don't have the details of that thank you awesome so it doesn't seem like there's any further questions thanks so much Lawrence and we'll be back at 25 past um with the topic on uh static analysis in Ides thanks a lot everyone