An engineering perspective to zero-knowledge proofs and optimization

Transcript

Uh hi everyone. Um so my name is Jing and uh first a disclaimer that uh this talk is on my personal capacity should not come be construed to any uh relevance with any entity or company. Um so yeah today my talk is about it's about the engineering perspective on zero knowledge and its optimization and this is manual for the talk. So first I would say a clichi the optimization is important in zero knowledge and and by the way it was originally 35 minutes talk but shrink to 20 minutes so it may I may pretty rush um but okay so zero knowledge so to understand why zero knowledge proving optimization is important we need to

view zero knowledge as a computing paradigm and what it means is if we want to run a computer on cluster of n plus1 machines we have two ways one is we want to run it using banana in a way which we pay the n plus one multiply execution cost or we can using zero knowledge to run and then we we can choose a prover and then verify it on another machine and to rearrange equation uh we basically get this inequality uh only if this equation holds uh zero knowledge will be computational efficient right so basically uh the if the ver so the red part is verification saving the uh they gave us and the blue part is the provers And so basically from the equation it

basically give us a very simple result. The proverheads is a key to make ZK computational efficient because usually when we choose zero knowledge as a solution to our problem assution cost usually is already greater than the verification cost by definition. So then the question is how do we optimize it? A generally correct answer for any programming problem is understanding what you are programming. But there is a key difference between zero knowledge and vanilla programming which is in vanilla programming we can the the strategy is simple. We directly control the hardware the memory access control the memory management of VRM or any other uh direct hardware optimizations uh and which leads to the

success of the machine learning is a great example of this. But in zero knowledge in most cases at this moment is there's a proof system sitting between the application and the hardware and that imposes new challenges and opportunities and this talk um focus on opportunity opportunities and to understand that we need to first understand a key point randomness is the key as a core of this efficiency source for any zero knowledge portal. So and specifically in this talk I'm going to focus on a technique that is very pre prevalently used in many protocol called random linear combination and to illustrate this point I'm going

to review some two very basic building block of zero knowledge protocols as probably already very familiar but I'm still going to review it the first is bulletproof specifically I'm going to talk about the inner product arguments that is used in a bulletproof and specifically The claim goes like this. We have some a group which is a cyclic group of prime order P and we have some generator GH and a element as a generator in the group U. And the claim is we we we have a Peterson commitment to this two vector A and B and we also know the dot product raising to the power of U. So this is basically the pedest commitment and we want to prove to the verifier we know this commitment

and then we the strategy is we want to use random line combination to fold the vector half by half to the base case so that we can get efficiency and the strategy here how we fold it is we get a randomness which is r and then we fold it to get a prime and b prime using the formula which is kind of crossing you know this is really massback construction by the way this is not interesting math so I want to go very deep it's really just construction so you know people ultimately we get what we want and so the idea is if we can build a verifiable reduction to this sub problem in form of the P prime equals the Peterson commitment of a new uh two new vector that is half the lens and also we can prove that we have this dot

product of the new new vector which is half the length and then uh then then we can prove the cor and then then this claim only hold if we know the original claimment then we can focus on so so a sub problem because if we have solved the sub problem auto automatically give us the result for the original problem and then we're done because we we're recursively solving the sub problems and then how do we do that? where we can let the prover compute some elements that only if it knows both side of the relationship. It can compute correctly and which can be also checked independently by the verifier and verifier can update a new commitment and new group base on its own based on the knowledge of the agreements of the

algorithm beforehand without trusting the prover. So the idea is we want to split the group base because uh the group base is widely known by verify and also the prover and then we want to and because we split the vector. So naturally you know we want to split the the group and then because also we in the random combination we kind of do a crossing. So the group is also crossing and it constructed like this. But this is RNR is computed by the prover because we want something that only if the prover knows the dot product of this uh two vector it can compute. So we give give it some some very pretty hard thing. If it doesn't know then it cannot compute and then the verifier would compute this equation L to the power. So I won't read

it but this equation basically is dependent on error r which is computed by prover and also randomness that is generated by verifier right because if is uh so the reason this formula involves a randomness generated by verify if it is is if if it is not using the randomness then they cannot check whether the prover actually use a correct randomness it it generates so that if this equation holds then the original claim is correct this is by the math construction and now we can just recursively prove This equation holds two but by folding by folding this uh and we get a very exactly same uh same equation as the previous one and the new new commitment is this the new commit this is a new commitment and this is a

new group base this is how does uh this is a pure wise product this is pure wise product of this two group elements and then so this is a group element this is a group elements of size of half of the size of the original group base and then and this is uh the dot product of the new uh vector of also half the length. So then we have this new commit we want to then the problem has been verifiably reduced to we have a new commitment and also uh new product arguments and then this argument and then we we can recursively prove this argument is correct by doing exactly similar process and this is yeah I mean this is just from the paper original paper uh and to show that actually this is what happens right this is a randomness that is

generated by verifier and then the prover use it to fold it and then we go to fry Okay, fast read resolment uh code interactive oracle proof and oh it's pretty small but the idea is we want to prove a polinomial of low degree and with over probability and then the idea is we want to commit to the polinomial uh using some like tree or whatever and then u the key is uh we have nth root of unity at this point this is kind of serving as a resultment encoding of this polinomial and then we use fast for transformation right basically here we are splitting a polinomial to the even to the even uh power and the odd power and then again using a very similar

process we are kind of uh we are having we are folding the degree to the half of the original degree and then we use a random linear combination to combine this two lower degree polinomial to uh the polinomial of of half of the degree so and then uh it's exactly same process we want to build a verifiable reduction now such that if proving f(x) is of low degree under new root of unity which I haven't figured out then we can proving the original polinomial is of low degree under the original root of unity and then we have recursively solve the problem and it turns out that we can because of the uh you know this new polinomial is of degree of half so we need a root of root of unity of

uh higher higher power right to basically to the power of two so basically we get rid of all the uh this like uh you know this uh like omega like this this lower degree thing we only keep the uh power of two uh power two um root of unity. So then how many of this root unity is is of the half of the length right here is n root of unity. If we get rid of all the uh you know like root a power of one three and five we get uh uh also root of unity of length of half. It's a very similar process right as we can see but here it's not a cryptography uh uh group it's just a root of unity. So and then we can using this uh uh then we need to find the new

committed relationship between the new committed value and the previous committed value so that the verifier can independently check this relationship and the way we can do that we have found relationship is through this like uh meth like deduction right for example uh so basically yeah so so basically uh this formula is is fairly like straightforward like yeah so basically expand this so uh this is you cancel out the term, right? For example, like uh you you plus this uh you plus omega to the i and then negative omega to the i. You plus them together for the even uh for the even power then it should be uh it should be kept but also you have a two before it.

So then you divide by two but for the uh for the odd uh power then you would cancel out. So this term is equal to the uh this one right f uh omega to the two to the power of i and then this this is very similar idea and then um this is a this is rearrangement. So this equation is rearrangement of this uh equation and then uh this and this equation is basically changing or the only thing that change is this. So negative omega i is exactly equal to w uh omega to the power of n / 2 plus i. And the reason for that is the property of root of unity. Uh yeah because you have a symmetric like the negative omega I is

literally just symmetric to uh exactly same position as omega to the power of n / 2 plus i. Can but okay. Um so then this is a relationship that we want to prove and then how do we check that? verifier check it by picking a random I in this range 0 to the^ of n / 2 minus one that identifies three points which is these three points and then uh this basically just a random checking right you know this is very commonly used any polinomial relationship checking or or but here we are checking these three points are colinear um so if you continue and then if if this is these points are colinear that means the

relationship holds that means the prover folds the polinomial correctly and then if we continue doing this log roughly log to uh to the d which d is a degree of the pol original polinomial times and prover we can uh and and if if prover folded correctly in each of the step and then the original committed polinomial is indeed of low degree it's not some degree that's fairly large like like n where n is the uh coding ratio then we end up with a base case where the polinomial becomes a constant polinomial and therefore I can simply request as a constant as the final stage as a proof for the final stage and if the base case is correct it can recursively understand everything before it. So what is the learning? Some of the basic zero

knowledge building blocks are just recursive randomized algorithm. They are just recursive randomized algorithm. And then the both in IPA and uh fry we are building a verifiable recurrence relationship. In IPA verify is keeping record of updated groups for each run. And in Fry we are checking random point and checking the colinearity. And in fact many other protocols follow the exact same idea like batch proving and uh like other commitment schemes but uh we don't have time to to cover today.

And so the idea is if you can reduce application level problem to this how this protocol uh this protocol already works then maybe you can find some more optimized way to write the application. So this is uh and I'll give you example of why this actually matters. uh so there there's many like machine learning transformers and know CN and RN this neuron right and then uh they involve a pro if we want to prove if we want to prove that then we need to prove a relationship r equals a b c d all these measures modifications and then uh you know instead of naively computing them in circuit the prover can instead prove a multiply by b= e multiply c= f multiply d equals r and then computing ef out circuits, right? And then

implement a randomized algorithm to check the measureification is indeed correct in the circuits and then we can reusing the randomness of the F that already the under protocol has been has already computed that exists for free. So that we can uh proving this uh so we have finished a proving of this series of large series of matrix multiplication in square time instead of o uh in naive maybe not to the square but you know still larger than to the power of two. So the conclusion uh it's important to uh if you want to write a optimizer algorithm for general applications it's important to understand lower low level building blocks of the proof systems uh plus some uh hardware automations that

everyone already talking about and then um also it's important to think of the argument that one is proving and the possibility to derive an equivalent argument to prove that can leverage underlying randomness and thus significantly uh uh make the application more efficient. Yeah, that's the end of the talk. If you have any questions, you mentioned Fredwell's algorithm. I was wondering whether you can also give us a couple of other examples where we can use the randomness from Yeah. So uh for example uh if we have a different

polinomial and then um yeah so for example um we have different commitment scheme right and then for example give simplest committed commitment scheme KCG and then um we want to batch proving uh uh like for many different polinomials they're evaluation uh at um many different points is equal to a value and the uh and I want to batch these polinomials together uh usually you to do um it's uh you know naive way is you have this KG proof for each of them and then you need a quotient polinomial and then do everything and then the pairing is costly and also the pairing would be equal to the number of polinomials uh you you're going to uh prove

have some points right but then if you want to do the um random linear combination you can random linear combine these polinomials and then um the idea is you would only need uh n plus one pairing actually. So basically because you combine this uh you request some randomness and then you combine this to a a single polinomial and then uh by computing the quotient. So basically and then compute uh computing the quotion for that and then uh you can send the question as a proof and then verify would randomly combine this polinomial and check whether the quotion is correct and if it's that cion is correct then it can also uh it basically can uh be convinced with hyperbility that the uh the previous um that you know uh the value at this different

points of the polinomial. Yeah. And as yeah I think other like there's al also um yeah because I think yeah like bully bully proof in later stage of the bully proof there's some optimations also using the random line combination um and uh yeah thank you all good anyone okay thank