zk-SNARKs Math Foundations: Polynomials, Pairings, and More

[00:00:04]all right i'll stop so um hi everyone i'm going to talk briefly on secret snacks and some of the mathematical uh foundations of it um we'll also start by talking about uh what zika songs are and and sort of how they work and then we'll talk about sort of focus on the mathematical underpinnings of them so things like polynomial properties um homographic encryption knowledge of exponent assumption cryptographic pairings and so on um and there's lots of sort of great experiences out there and this is this is logic based on previous work especially one called why and how secret works by maxim petkas and also great explainers by vitalik and gabazon that i i definitely recommend people check out if they want to learn more and we'll focus on sort of the key mathematical tools and insights and less on sort of mechanical aspects so first of all um seeker snarks stands for like i'm sure most of you are familiar but i'll be brief here but um stands for knowledge succinct non-interactive arguments of knowledge and we'll break that down as we go um but essentially it allows us to prove something without revealing any other information other than that it's true uh but first of all like what are you useful for so let's do many things so we can do anonymous anonymous authorization so you can prove that you're accessing some system without revealing who you are keeps it for anonymous payments so kind of making digital money fundable like we saw with tony cash and the previous presentation um you can also use it for outsourcing computation so in peer-to-peer systems uh maybe a one node that's doing some expensive computation and then other nodes can can verify that um so a great example for building intuition uh especially for lay people is this game of where's waldo that some of you might be fully with familiar with essentially you have this sort of it's map and it's kind of messy a lot of things going on and you're trying to find where waldo is um so waldo is this guy with a red and white striped shirt and a hat and in this illustration um and the secret sauce in general i could prove a peggy wants to prove to verify victor that they know where walder is without revealing where where he actually is uh so you can imagine that you sort of have this this waldo map it's like a postcard and then you take sort of a bigger piece of paper like a cardboard for example and you sort of put it in front of this postcard and then you make a tiny hole in the big piece of paper um and then you position the sort of the postcard with waldo so only waldo himself is visible um and then the verified victor can sort of see that you you indeed know where waldo is because you can see waldo but he doesn't actually know where on the postcard wall is um obviously this is just like a toy example to build intuition and it doesn't tell us anything about the actual math behind it um which is what we'll dive into of this presentation so uh first off some sort of um yeah some uh protocol properties uh so completeness um so if a statement is true then the prover can convince a verifier of it and then sums so a malicious approver can't convince a verifier of a false statement and then finally see your knowledge uh where proof only sort of reveals if a statement is true and nothing else as it turns out even those of the serial knowledge property seems like the most magical one and in some sort of sense it is it kind of falls naturally from this verifiable computing soundness aspect oops so you might have heard that we sort of use uh polynomials in case not but but why is that so sample polynomial is an example polynomial of degree two and sort of the more general form here and it turns out like polynomials since they have some very nice properties um so to sort of show this we're gonna like have a kind of a straw man simple proof here where oh i think it's not updating is it taller oh anyway uh imagine you have sort of a a bit array of of ten elements uh and then prover uh peggy they wanna sort of prove that all interests in this since area are set to one and then verify victor in order to check this they have to verify each entry one by one either sequentially or randomly or something and so to get 95 confidence they would essentially have to take all entries this is obviously very inefficient and just looking at polynomials so so you have this fundamental theorem of algebra which says that the degree the polynomial has the most these solutions so we have an example polynomial here um you can see it has solutions at x equals one two and three and it's of degree three um and if you change sort of polynomial tiny bit we get a completely different solution um and if you subset two polynomials um equal to each other uh you get another polynomial uh so two different polynomials intersect at at most d points so let's say we want a piggy they want to prove that they they know a polynomial and they want to prove this uh in this case let's also assume that the victor the verifier also knows this polynomial so we have this very simple protocol um where victor verify sort of choosing a random value for x so say seven and then evaluates this polynomial at that point uh which gives us 120 and then it gives sort of this random value to a pegi and peggy also evaluates pfx locally and gives the result back to vector so 120.

[00:05:44]um and if the results are the same which they are in this case 120 um it's very likely that pig is or notes the same polynomial as vector and to see what is the case you can sort of imagine if you have a range of x values that's from one to two to the 250 second power and so the probability that peggy would accidentally pick a point where there's a evaluation of the polynomial will be the same as is the degree of the polynomial divided by 2 to 252 which is very unlikely so polymers are very sort of easy to work with um when it comes to operations like addition and multiplication and so on and hopefully this gives us some illustration of why seekers rely on on polymers um in terms of sort of contrasting with the naive proof whistle initially but it's also likely that there are other forms of proof mediums that exist so in a better world uh where peggy was trying to prove that they know pfx uh in a better world victor wouldn't actually know pfx on its own only peggy would and then peggy would prove that they know this polynomial and because of fundamental theorem of algebra you can so factor polynomial into a product of linear factors so we can express p of x as such so you have these factors that correspond to solutions so x minus 1 times x minus 2 times x minus 3.

[00:07:09]and then instead of victor sort of knowing this polynomial p of x it would know a target polynomial called t of x which also cofactors in in p of x so in this case say t of x is x minus one and x minus two and then p of x is essentially just a multiplication of t of x and then some arbitrary polynomial which you call h of x which in this case is the factor x minus three so in this sort of slightly modified example uh instead you would have vector they would evaluate uh the target polynomial at the at random point r and then give this r to peggy and then peggy would calculate the arbitrary polynomial and then also evaluate the polynomial at point point r and ends of the arbitrary column at point h and they would get sort of these p h evaluated numbers and and then give them to victor uh the verifier uh who would then check that sort of uh this verification check this consistency holds up so that p is equal to t times h which what that means is that t of x is a cofactor to p of x uh so in in the previous example peggy knows the value r that victor chose and it's kind of a problem because it means that peggy might not actually know p of x at all so p peggy can instead cheat and it can choose a random number h and so set the polynomial to uh p equals t the total polynomial evaluated at r times this random number h and then the sort of victor would accept this because the verification consistency check would would um pass despite and this is the case uh despite that uh peggy um doesn't know p of x so it kind of breaks soundness so what we're going to do is we essentially want to hide r and and t of r from peggy so they can't cheat and break this soundness property and this leads to this concept of homomorphic encryption uh what idea is that we encrypt some number x with some function e of x so it's harder to find out what x is um and different inputs they have different outputs and if we know sort of the encrypted value of x and y then we can compute sort of basic arithmetic expressions such as addition um and uh you can kind of think of just like hash but with basic math functions um and on the certain assumptions we can think of the modal operation as a form of encryption so let's see why so as a starting point uh imagine we need to choose a base g and then we we encrypt the number by exponentiating g to it so for example we have a base 5 and then we want to encrypt the value free 5 to the power of 3 is 125. then it can in this case it's very trivial to find the number um just you just divide by 5 until you get one and the number of steps is the encrypted value so that's not very useful um but if you use model arithmetic it's kind of over a finite field so it's a subject of all natural numbers and it's essentially like clock informatics so it's a three o'clock and then plus two 12 hours it's the same it's three o'clock again so we have this sort of new encryption function um where you to encrypt the value is the same as taking this g to the power of v mod m so what's kind of neat with this is that you have different values they end up with the same results so it's hard to figure out what the encrypted value is especially if the order what you're taking model off is high enough this is this is called the discrete logarithm problem and essentially says that if we choose this base g and order n right then it's very hard to figure out what v is in this expression in this case we're using this group so the multiplicative group of integers modulo p where p is a prime number and a group here is just some set of vibrations some set of elements integers up to p minus one in this case and some operation multiplication in this case um and since p is a prime it's what's called a cyclic group and that means that there's a generator and standard you have a generator that can generate every element so you can stuff with this generator uh you can get every element in this group and you also have equivalent groups that exist for elliptic curve cryptography uh which we'll touch on later so now we have a way to compute sort of uh yeah the the x plus y encrypted from the crypto values separately um [Music] but we can't exponentiate encrypted values yet uh which is what we'll look at next and we also can't multiply two encrypted values uh which leads to the concept of cryptographic pairings which we'll touch on later and this is a very basic form of homomorphic homomorphic encryption uh and and with something called uh holy homomorphic encryption we can sort of do arbitrary computation on encrypted values which is like a separate field right so we we can't exponentiate encrypted values so instead what we do is we essentially encrypt polynomial by doing each power separately uh and if you think about it to know a polynomial is really you you know its coefficients and its degrees uh so in this case we have this polynomial the coefficients are one minus three and two and has degree three so what we do is we encrypt each of these terms so x to the power of one x to the power of two uh x cubed and then we equip this power these powers um and then we the proof result given these encrypted values so we have all these encrypted powers and when you apply this encryption function with the coefficients and sort of add them together uh the result is that our polynomial is encrypted at some x um so with that how does that change our proof procedure so as before you sample some some random value here we call it s and then we encrypt s for three so these terms each power uh evaluate the unencrypted target polynomial at tfs so target polynomial at point the secret point s and then we provide these encrypted powers to uh prove or peggy so similar to before uh use so peggy calculates um this arbitrary polynomial h of x and it's using these encrypted powers that was given by vector and applies a sort of coefficient for the p of x uh polynomial and we do the same thing for the arbitrary arbitrary polynomial h of s and then we provide these sort of p and h values like we did before but this time in sort of encrypted space so now vector is is checking that p is equal to our polynomial evaluated at s times h in encrypted space so that means that t of x is a coefficient of p of x um and it's going to progress right because now peggy doesn't know s or or the target polynomial evaluated to this but it can sort of use the encrypted evaluation um but we have a problem because it's still possible for peggy to not use these encrypted powers as intended so in sequest we can also think of the coefficients as representing knowledge uh but for that to be either the case we have a requirement we need the proof to be based on the exponentiation of these encryption powers so a parlorman has to be on the right form um and and if it isn't then piggy can essentially cheat breaking soundness um so as an example uh pay can set you some random r set g h to g to power of r and then set uh the p to to express them there uh and then the verification check and sort of checks out despite peggy not knowing pfx which breaks uh sounds soundness so cheating is possible here because piggy can sort of exponentiate to some value other than s and what we're going to do is we'll ensure that we always use the incredible powers of s that's provided to us um and only sort of add coefficients to it and this can can be done with something called the knowledge of exponent assumption and the basic idea is essentially that um victor the verifier is choosing some random alpha and then he calculates alpha prime which is a to the power of alpha mode n and then it provides this tuple a and a prime to peggy who then has to sort of take each element and exponent in this tuple and exponentiate them to a random value uh and reply with the corresponding tuple b and b and b prime and here as we saw before p a console for reasonably extract alpha from a prime this kind of secret parameter and the assumption in this key kea is that the only way for peggy to produce this valid bb prime tuple is the following so two some random c and then calculate b and b prime by taking a and a prime respectively um exponentiating it to c and then replying with the b b prime tuple and then vector sort of verifies that this holds with some variable substitution and you'll see that it's the same expression and the exponent c must be the same and this kind of alpha shift this is a useful tool uh in terms of restricting polynomials and sort of maintaining the invariant invariant that we only applying coefficients to the encrypted powers of s so so t to the power of the coefficient times s for each uh term and if you have a for polynomials with multiple terms you simply do the same thing and then use some morphic encryption to add them together and this adds one more uh called like a polynomial restriction verification check for the verifier so previously uh peggy was plotting g to the power of p and g through power of h to vector but now it's also providing this t to the um power of p prime uh so vector can check that the polynomial is on the right form cool so with this we have a what's called a computationally sound protocol so essentially a prover can't convince a verifier of a false statement and we call it we call it computational because it's still a it's called small like a soundness error but it's kind of an arbitrarily small possibility that peggy can provide a false proof but we can be very rigorous about this sentence error sort of quantifying it and minimizing it so in practice it's not something we worry about but it's still not zero knowledge because for to be serious knowledge we don't want to leak anything about the original uh polynomial p of x um to vector so so peggy just wants to prove that they notice the polynomial they don't want to leak anything about what the polynomial actually is let's look at the state of things right now so if if p of x is simple so let's say the coefficients are range from 0 to 10 and then degree 2 or something then it's very attributable to brute force and find out p of x and what we want is kind of a secure protocol that's regardless of the number of coefficients or values and if you recall uh the actual verification checks that that victory verifier is performing it's checking that p of x has the target polynomial as roots in this encrypted space and also checking the polynomial restriction so what we saw before with the alpha shift making sure the polynomial is in the right form and we're going to essentially use the same idea as we did with alpha shift where essentially pig is choosing a random delta and then exponentiating sort of her proof values to it and that's kind of introducing some some randomness um and the verification check they they still hold uh but p of x can't be easily be brute forced uh with this additional term so one pretty neat thing here is that once if we had sold out foundness then we got the same knowledge for free essentially so that's neat um but so far the the proof is still interactive so non-interactivity so this is the end in siquesnocks and sometimes it's called non-interactive knowledge uh so the current state is that a proof is only valid once and then if some other verifier vena wants to verify they have to start over um and victor can kind of cheat and share their secret parameters with peggy or something this leads to this sort of idea of publicly verifiable proofs that you only prove something once and then anyone can verify it after and this is especially attractive with public blockchains like theorem because you can sort of write the proof once and have it the chain and then other people can verify it whenever they want to so the general idea uh essentially that we want to keep the secret parameters public secure and reusable and we had a setup phase before uh where we sort of compute the target polynomial evaluated at s secret and then alpha um to sort of compute them securely so you might think well before didn't we have this from morphing encryption can't we use that the problem is that we can't uh multiply encrypted values which is necessary for the verification check so you see here that the secret stays off as a multiplication term so that doesn't work that leads us to the concept of cryptographic pairings but first let's talk briefly about elliptic curve cryptography so elliptic curve cryptography it's used for public key cryptography and it actually allows for uh smaller keys uh with similar security rsa so a 256 bit is a z key ecc okay uh corresponds to a 3072 bit rsa key so it has a 10x impact on performance which is why a lot of products are using them now and previously we had sort of well it's based on elliptic curves over a finite field where there's you have this points a and b that's satisfying this this equation as well as a it's called a point of infinity which is kind of like sierra in in normal arithmetic so kind of additive identity um and only we sort of had this multiplicative group of integer integers modulus and prime or sort of over some finite field model of p more generally we have a kind of similar discrete logarithm problem for elliptic curves over a final field and sometimes it's called sort of the elliptic curve uh discrete logarithm problem is a dlp and so how to choose these curves and making them peri-friendly and so on is a whole thing or field of its own or subfield um and if you're interested in that i recommend checking out dgb's daniel bernstein's work on safe curves as a starting point so cryptographic pairings pairing-based cryptography is used a lot in modern cryptography um it allows us to multiply encrypted values using bi-linear maps uh it's kind of a mapping between these two cyclic groups and then some other group and gft and this output group is kind of in a different space in our case what we care about this is mapping of elliptic curves over find fields so if you if you read this this sort of equality you can you can sort of think of it as very sloppy that you you just focus on the exponent and you sort of swap place of the exponents um so in this case we'll see a b is equal to ba [Music] e is also should also be efficient to compute and non non-degenerate so kind of illustration of this um output group is isn't a different space and and we can't sort of take the output and use it as input in another pairing so we're kind of teleporting ourselves into different dimension and so unlike rick and morty we can't just easily go back and finding pairing friendly curves here is a bit of a problem where we kind of want to balance uh the e being efficient to compute with the discrete logarithm problem being hard in the output group so that's as a brief aside the first cryptographic pairing was defined by andrew weil who was part of the burbank group and to find it when he was in jail during world war two and he had pen and paper and he was very productive and he suggested mathematicians go to jail in order to be productive so maybe co-workers six and so on so bad after all so very basic example of pairings um is in bls signatures and it's kind of elegant as well so bts signatures are very short signatures that allow for aggregation so you can have multiple parties that are signing some result and it results in one sensor and it's used in the firm two um and essentially so you have this key generation uh function where you have some secret like private key kind of um and then you take a g that's like a generator to the power of alpha to get the public key and to design a message you take the hazard message and then exponentiate it to your private key your secret key and to verify it you should check this pairing quality and if you remember you can sort of basically uh if you do the variable substitution here um with the public key and sigma the signature you can essentially um sort of swap the place of alpha so in in in the word two we have the left side uh the right term on the left side you have an alpha exponent and then on the right term left side where you have sigma you also you get an alpha exponent um and so both sides equal to the same thing uh so if the signature is valid um it's all good and you can sort of think of the output as a new generator uh g2 that allows us to add encrypted power i think encrypted products of multiple pairings and as a kind of an aside so this is like a we looked at by linear maps but this is concept of multi-linear maps which is a very hard sort of research problem um so in this case just having a free linear map it's hard uh and if you solve it then famous cryptographer dampone will be your friend for life there's that um right so with this cryptography pairing essentially we can do a trusted setup so the idea is that you have a setup face before you do proving and verification and as a kind of starting point we can assume that we trust a single entity and then the proof is done once and and then can be verified many times after and we have this concept of a common reference string uh where all of these secrets are we generate the secret s and alpha as well as the encrypted powers of s with this alpha shift um and then once we are done we should delete the raw values and sometimes this is called toxic waste and it's called that way because it's waste you don't need it anymore and it's toxic because if you get a hold of it then you can create fake proofs and stuff so how does this work with cryptographic pairings so you have this um common reference string you generate these parameters and we can split it up into two parts you have sort of a proving key part and then a verification key part and essentially you do the verification check as before but now with with pairings so we're simply still checking that p is equal to t times h uh in encrypted space so that the g of x is a cofactor of the polynomial that we are peg is proving that they they know uh and if you sort of squint then just focus on exponents you'll see that it holds and then we do sort of the same sort of pairing uh because this is check for polynomial restrictions so making sure that it's on the right form like we saw with the alpha shift and knowledge of exponent assumption earlier so we can extend this to trusting one out of m parties with a composite common reference string it's very sort of similar to some tools i use to do this um there's some things you have to be careful if you have to be careful that you're doing it sequentially where the output of one step is used as input to the next one uh make sure each step is used uh as well as some additional checks to make sure this of no toxic waste is leaked when also um sometimes it's called a ceremony and it's elaborated on in the study of multi-party computation and you can join one yourself and participate for example is the perpetual powers of tao as well as others so if you don't trust other people maybe you trust yourself and then you can be part of this ceremony so uh looking sort of beyond polymol so so far we've been focused on proving that peg has been proven that they know a polynomial but how do we actually use it for computation so the idea in brief is that we convert a some computer program into math formula and then we sort of turn this into a set of simple constraints and we express these constraints as a polynomial relationship between polynomials and then we find a polynomial that represents these constraints so pig essentially proving that they know the result of some secret computation and then victor checks that the constraints hold so the goal in the first episode if you're converting a program into some set of uh constraints uh you can use variables and constants and and binary operations so for example let's say you have a function with some binary argument w it's a it's a binary number uh then we might have the following constraint so one times w times one times w equals one times w which is only valid uh for w zero or w is one it's a binary number and essentially we we can get these uh called arithmetic circuits and it's kind of similar to making a computer with logic kids logical gates uh so you start with a name gate and then eventually you get minecraft so if you have multiple constraints you can sort of chain them together with intermediate variables so here you have a times b equals r1 and then r1 is used in the following constraint and if you have some more concrete example you have multiplication of these numbers uh then it takes three constraints sort of expressed that so you have two times one you get output two and then use that as input so two times three six and six times two is twelve um and in the real world uh sort of you have a lot of constraints that have to hold the same time so we saw in the in the previous presentation there were a lot of i thought exactly how many but yeah it's a lot of constraints to have to hold the same time um and this type of constraint system is called a rank rank one uh constraint system uh so and rank one is referring to the resulting matrix if you use a kind of linear algebra representation so we want to express the constraints as what's called a operational polynomial which is this equation here so you have some left and right operand polynomial and some binary operation and then you get an output polynomial and that sum at some x equals a the corresponding value in the constraint represents the evaluation of that polynomial so l of x and similarly for r of x and of x so a more concrete example here uh so going back to the previous numerical example we have a sort of left operand uh operation right operand and output and we can look at these constraints as kind of rows um so the first row has as two in the left position the second row has also has two and the third was six and we're looking for a polynomial l that represents the left operand at each row so for example here l of one is two because uh the first row has the value two in in the left position uh and we do this for for sort of each row and then this gives us three points and these are the three points that the polynomial they were looking for muscular through so we have some set of points then we want the polynomial what do we do we do polynomial interpolation and allows us to so all polymers can be expressed in this general form and we use interpolation to to find the sort of a b and c uh that goes through these points um in this example it's a very basic set of equations with some unknowns um so um if you remember the fundamental theorem of algebra in this case we have sort of m plus one point so three uh that means there exists a polynomial of at most m so two in this case degrees that that that polynomial exists that expresses this then we solve for a b and c uh and we get sort of the operant polynomial uh what is the what's what's there l of x equals 2 2 times x to the power 2 minus 6 x plus x 6. uh in practice because we have a lot of constraints and some speed and performance matters uh we might use lagrange polynomials or even better sort of fast fourier transforms uh and then also in practice it's a bit more involved uh there's some gotchas uh it's largely mechanical but you need to care of variables and constants and so on and basically the essentially the same and polynomials are very flexible so you can sort of scale them and compose them and so on and what we did for the left operand polynomial we we do for the right operand polynomial as well as the output polynomial so one thing that's pretty neat is that no matter how many constraints we have we'd end up with a single polynomial um and so the final proof that has a few more polynomials but but essentially we compressing down a program into some constant form that's independent of the size of computation and this is where the term succinctness comes from so the s and c is nox so just briefly also variable polynomials um so polynomial composition means that we can express many additions and constants in a single constraint so what we do is we split up the operand polynomial into individual variable polynomials and then we kind of get constants and the distance for free and sort of give you an illustration of this um how you get these three constants and free edition so here you have this um lfx polynomial the green big line that's composed of three curves where a times l of a l a of x that polynomial is a at x equals 1 and then zero at x equals two and x equals three so it means that we can just scale by some constant uh and then we can do the same in for b and c and then in order to do addition uh we can sort of take the a plus c at x equals one take those curves and sort of add them together uh to basically get this l of x uh polynomial so hopefully this this gives some intuition for for y constants and addition can be expressed in in a single constraint so uh all of this together the variable and target polynomials together they're called a quadratic arithmetic program and sort of allows us to turn computation into polynomials so what did we end up well previously peggy had to prove that they know a polynomial and instead now instead they they prove that they know the result of some computation and a vector essentially verifying that this constraint holds and the main difference is that we have to check a few few more polynomials uh add some verification checks when it comes to variable values and and value operations also this is concept of like private and public inputs so we have some computation c of x and w where x is the public input and w is the witness so that's the private input and then this allows them to verify to supply their own input so peggy proves that they know a witness w such that the compilation is true um so for example which we kind of saw in the previous presentation that so victor's supplying some hashtags from secret s and then peggy can prove that they have access to s which has us to it without actually revealing the secret so uh we looked at secret snacks uh what they are and what they're useful and then we looked at some of their mathematical fun foundations underlying them uh we looked at polynomials why they used in c k snarks uh their properties uh we looked at how to prove that we know polymol how to hide information with homomorphic encryption we looked at how we can use knowledge of exponent assumption to sort of ensure soundness and we also saw how we could get synology for free uh then we looked at how to make things non-interactive um as of the shape of a cluster setup we looked briefly at elliptic curve cryptography and sort of why we need cryptographic pairings and roughly how they work and then we looked at how sort of uh we to go from computation to constraints to polynomials and we also looked at sort of the how to achieve succinctness by compressing constraints down into polynomial expressions yes hopefully this was interesting to you um if you want to learn more um i highly recommend checking out petticoats y and housekeepers knocks as well as vitalik's writings on this and ariel gabson for gabazon for for more um yeah and the secret stocks is just one of many types of synonyms texas others that have different security assumptions if you need a setup or not as of what the underlying computational hardness problem is the street log problem or something else as well as performance of proof size and time and so on yeah that's it for me thank you um [Music] any questions you can find me here on twitter and back as well