Zhengxun Wu - When Zero Knowledge Becomes Useful and Optimization of Circuits

Uh hey everyone. Um yeah so first a disclaimer that this is uh conducted in my personal capacity and should not be construed to any have any having any relevance to any company or entity. Okay so just a normal disclaimer. Okay. So today I want to talk about engineering perspective to zero knowledge and uh its optimization.

And uh this is the menu for today's talk. Um so first I want to say uh uh a cliche that optimization is important in zero knowledge. And to see why optimization is important we need to view zero knowledge as a computing paradigm. So let's say we want to run a program on cluster of n plus1 machines. We have two ways to run that.

The first is the vanilla way which is mostly most people use uh in distributed system. uh we we need to pay N plus1 multiply the execution cost on this N plus1 machine or we can use zero knowledge to run uh to achieve the same result which we need to pay approver cost plus verification cost multiply N because another machine need to verify that and zero knowledge would only be computational efficient if the total cost of vanilla computing is small is greater than the total cost of the zero knowledge and so thus we get this inequality. So from this inequality we can see that only if uh the execution cost minus the verification cost is uh large and the prover cost minus execution cost um is low uh then this in inequality would host would hold. So which means we need to uh and and and by default when we choose zero knowledge for a computing problem execution cost is usually already greater than the verification cost by definition. So we need to optimize the prover cost.

So basically it's basically just point out that the optimizing prover is the key to make your knowledge practical and then we want to uh ask a question of how to optimize uh it and as everyone knows uh the key to optimize any program is understand what you are programming. However, there's a key difference between the vanilla programming which most engineers are familiar uh and zero knowledge which is in the cryptog uh cryptography world which in vanilla programming uh the general uh concept of optimization is we want to cater to the hardware. We want to deeply understand what's uh optimization uh tricks that has been implemented on the hardware layer and then leverage that and uh the recent success uh in in these years of machine learning is a great example of that. Uh uh for example the uh flash attention uh and all the other acceleration on the implementation of the transformer algorithm um leads to the success of or the VRM V RMM which is optimizing the inference is uh all follows this pattern which basically uh optimize the algorithm based on the hardware. However, in their knowledge, there's a uh difference.

Uh we need to consider the proof system because uh there's usually a proof system sitting between a software and a hardware and that imposes some new challenges and opportunities. In this talk, I'm going to focus on the opportunity. And to understand that we need to first understand a key point which is uh the randomness is the core of the efficiency for this type of algorithm for this type of zero knowledge algorithm and they almost the the full source of why zero knowledge is actually efficient compared with a normal computing and specifically I'm going to focus on a very commonly used technique called random linear combination um in the following session. So uh I'm going to review some very basic building block of zero knowledge protocol uh specifically uh talking about bully proof um fi uh fry and breakdown and then uh we we're going to draw some commonalities from this basic building block of the protocol and uh learn from it to have some optimization on the application layer. So uh yeah so bully poof uh supposedly I'm going to talk about the inner product argument that is used in a bullet proof.

So we have uh so it's probably going to be u uh yeah so it's a bit technical but uh it's target audience is engineer but also yeah um but but also probably is uh you know we also skip some proofs uh that is in the paper uh um thing so we focus on actually the the practical part. So we have a secular group of prime order P which is uh G and we have uh three generator G and H are vector generator inside a group u is the element a field element inside the cyclic group and then the argument we want to prove is uh the peters a commitment to a vector a and b and a dot product between them. So we want to prove that we have the knowledge of the dot product between two vector and um the idea of uh inner product argument is to fold the vectors by half recursively. So we want to uh say a1 and a2 are the split of the vector a b1 b2 are the split by half of the uh vector b and then c is the constant that we know we we claim that we know and then how it is folded is by crossing. So a the a prime is a new vector that is half the length of the original vector a a which is uh using a randomness r multiply the a1 which is the first half of the vector a plus the inverse of the randomness uh multiply the a2 and then b prime is done in a similar fashion but also causing the term.

Um and once we have this the goal would be build a verifiable reduction to the sub problem in the similar form which is the p the pet commitment to the new vector and the the uh the the dot product of the new vector and then uh if we can verifiably reduce the original problem to this problem which is half of lens then we can recursively solve the sub problem. Um so the idea is we like we want to design some problems that the the prover is very hard to compute if it does not have the knowledge of the dot product and uh so only if it knows the the both sides of the relation it can compute uh the formula correctly which can also be checked independently by the verifier and the verifier can also uh we also want to design a mechanism such that the verifier can update its own commitment and group based on its uh given a knowledge of the algorithm without trusting the prover so it can check independently. So the idea is uh we we also split the group base. Uh so because we previously already split the vector naturally we want to uh autosplit the group base that we use to commit to this vector and then this uh so and then by design of mass construction uh the prover needs to compute two thing the error and r which is uh kind of like also causing a term I won't uh go particular deep into that but uh by construction as long as this formula holds basically is um if the pro is honest then the uh this long formula should hold and then uh the original claim is we know that original claim is correct and then we can recursively prove this equation holds. So and then uh we we follow the exact same similar step to fold the vector uh to a single element uh to which is the base case and then uh the verifier can simply compute the constant equals to two field elements multiplication and then check the uh the the the the p which is uh which the verifier itself is computing to the end is equal to the peterson commitment of these two elements and uh the dot product of the elements which is simply migration.

Uh this is just uh from the original paper of uh of bully proof and u as we can see here is basically the verifier draw some randomness and uh send to the prover the prover use that randomness to fold the vector uh and uh in each round. Um this is just a full full algorithm for bully poof. And now uh we we talk briefly about fry the first read solment code interactive oracle proof. Uh the goal of fry is to prove a polinomial fx of low degree with overwhelming probability and uh the idea is uh roughly the similar uh so uh we have a mer hash of uh this of this polinomial and we want to have the red solment code of this polinomial by evaluating this polinomial on n root of unity. So basically one omega omega square to omega n minus one and the idea of splitting the polinomial is uh join or inspired by fast for transform fft.

So basically we split the polinomial by the even ter term and odd term by even term I mean the even power uh of the term and o uh odd is just uh the the power of the term is odd. And then we again use the rand use a randomness to combine to to to to combine the even term and odd term to a new new polinomial. So um so here we can express fx to f even x square plus x multiply f odd s² and then our new polomial is getting rid of this square term. So the new polinomial which is half of the length of the original polinomial is uh is f even x plus the randomness uh randomness term multiply the f odd x. So basically as we can see here the degree of the new polinomial is half of the original polinomial because we get rid of we basically divide the order term uh terms powered by half and this is the new uh polinomial that we want to prove loadness based on the uh original polinomial loadness.

And then very similarly we also uh want to build a verifiable reduction such that if we can prove frimex is of low degree under the new root of unity which we will figure out later then fx can be proven to be low degree under the original root of unity and then we will can apply the similar techniques to recursively prove this argument. So now how do we update the root of unity? where so first intuation is the root of unity should also be half of the length very similarly to the group base we have seen in the bully proof um because uh the the the the polinomial has also has been decreased to half of the length and we want to derive it by expanding the formula. So basically you want to derive a relationship between the u uh so basically uh as we can see here the power of the original polinomial is decreased by half. So we need to raise the root of unity to the power of original uh of polinomial original root of unity.

So based on that we get rid of all the um we get rid of all the root of unity that is uh the omega omega to the^ 3 omega to the power of five etc and only keep the uh the root of unity that has a power of two um um as the new root of unity for this fprime x. And then we need to find the relationship between the new committee value and the previous uh value so that verifier can check this relationship host through randomness. So um basically so this is actually a very basic uh expansion of of the of the formula. So the so basically frime omega 2 to the^ of 2i which is the evaluation of uh the new polinomial at root the the root of unity equals to the f even the even term plus the randomness multiply the odd term based on the definition of the new polinomial and then we expanded even term by sum uh sum the f omega i plus f uh negative omega guy divided by two. Uh that would cancel out the odd term only keep the even term but we uh add the even term twice.

So we need to divide it by two. And similarly we use f omega i minus f negative omega i divided by two omega two omega i as uh as the the order term because that would cancel out the even term because there's a subtraction between this uh polinomial and but but keep the order term. However the order term is divided the order term for example three divided by two is one. So we we actually get rid of the additional um additional number. So 3 divid by two is one.

So here we also need to divide any other omega 2 on the denominator. And then uh we rearrange the term. So basically the third uh the third equality is basically rearrangement of the second equality. And uh yeah so uh and then basically um and then the force uh the force uh the force equation is based on the property of the root of unity because of the the f uh negative omega i is exactly equal to f omega to the power of n / 2 plus i. This is based on the property of the root of unity.

So we get this relationship. This relationship is the new committed value of the new polinomial and the previous committed value of the old polinomial. And as we can see it is a linear relationship between the fprime and f uh and and two two value two evaluation point of the original value. So and the way the verifier just need to verify this relationship holds to to be convinced that the prover folds the original polinomial correctly to the new polinomial. And to check that the verify picks a random i between zero to the n / 2 minus i that identify the three points and check they are collinear and because this is a linear relationship.

Um so these are the three uh three points that uh the verifier check and then this is one round of this folding and we once this this this colinear colinearity check pass we uh we are convinced this specific round is correct so we continue to the next round and by folding the polinomial again each round the polinomial's degree uh would decrease by half and roughly around the log 2D D times where the D is the degree of the original polinomial then the prover if the prover folded correctly and original committed polinomial is indeed of low degree then we should get a constant because the polinomial each time the degree of uh decreased by half. So and then we get get a base case where the polinomial becomes constant polinomial verifier just simply requests this constant at the proof for the final stage so that it can uh understand and be convinced all the previous um claim is correct. Uh so that is f and here I want to also briefly talk about um uh breakdown and specifically so this is uh from a paper 2021 and uh which is based on a paper 2020 and uh so the so here I specifically talk about the polinomial commitment used in the breakdown protocol. So, so here basically we can view uh so in the fry as we previously we we view the polinomial as a long vector here we view the polinomial as a matrix. So basically uh m is the smallest uh square that is greater than or equal to the number of coefficient of the polinomial which is as simply a simpically to the o of a square root of d where d is the degree of the polinomial and then we divi we can rearrange the uh polinomial coefficient to a matrix which is the large matrix in the center of this equation and then the evaluation of u of is can be expressed in this vector matrix multiplication form.

This is a standard algebra and uh you can do on your own to verify it is actually correct but it's it's really standard uh algebra and uh then we conducted two tests. The first thing we want to know that and basically uh in the breakdown it a linear time uh linear time is not a linear code by the way. Linear time uh code algorithm was used to extend this each row to uh to commit to each to extend this each row to a code word which is of a length n. So extend this uh size m row to n and then we get this new matrix. Uh and then uh the verifier want to verify this committed part this committed matrix of the that should be composed of code word is indeed close or in in proximity to a actual code linear code.

So you basically want to verify this matrix is composed of rows that is actually linear code uh or at least in close proximity to the linear code. And the way it does that is to so basically uh so before that so the general idea of uh this algorithm uh this breakdown algorithm is we want to convince uh the verifier the vector matrix multiplication is correct efficiently and then the verify can just compute the result of this ve the first vector and matrix multiplication which is a vector and the dot product on its own which and then the verify can get a square root of d time capacity and message Nice. So basically the way it does that uh the first the first part how it can be done efficiently is first it does it so with approximate test where the prover computes this vector matrix product as a raw message. So it actually do the combination and then get a message of lens m then send it to the verifier. The verifier would encode use the linear time code algorithm and get a site a vector of size n and then need to check whether this size n vector is indeed the product of this vector and matrix multiplication.

The way it does that is to open random columns like a constant number of random columns based on the security requirements of the protocol that certain like the protocol designer needs to check the consistency between this uh this this vector this dot product between this vector and a specific column. So you just need to open random random number uh a fixed number of random columns in the matrix and then verify that. So that's proximity test and then uh and then uh so if there's a pro approximated test pass then the verifier can be convinced that u the matrix is indeed uh composed of rows of linear code uh that uh that in the same space subspace right so and then um the evaluation um then uh the ver then we can move to the evaluation test where we require uh very similar process but we require the approver to compute uh at at the point. So the prover claim is standard. It wants to prove the polinomial evaluates to the value v at point u.

So uh and here in the evaluation test the pro uh the verifier would request the prover to compute the uh like the the vector matrix the vector matrix multiplication but using the uh actual uh actual u as the vector. Then the verifier again encoded and then open random columns to check the consistency between a dot product and encoded vector. Um so after that it can be convinced the sub the the the the first vector and the matrix multiplic and the matrix indeed multiply to the correct message correct like correct uh code. Uh this is based on the property of a linear code. Basically the linear combination a random linear combination of uh linear code should also be linear code.

So then the developer can just compute the dot product the raw me raw message and any other half of the U which uh we previously see here which is rightmost column rightmost column which is any other half of U because we already uh very efficiently the verifier already very very efficiently understand and know that the the result of the first half the the the vector and matrix multiplication and then it and then the verifier just compute the dotproduct of these two vector and to get the value of the po uh of of the evaluation of the polinomial at point u. So and then so as we previously see that the we view the polinomial as a matrix which is a 2D tensor but in reality we want to be more efficient because if we only view this polinomial coefficient as a 2D matrix we only get square root of D. uh because we need to actually when you do this vector matrix multiplication you get a vector of size uh of size square root of d r roughly and then so the time complexity of the verifier is and also the message size is also a square root of d but if you we can view this polinomial in very different way we can view it as a rectangle but also a t- dimensional tensor for a different type of optimation and by view it as a t dimensional tensor we achieve the d to the power of t uh t 1 / t uh time and message size. Basic uh the way we do that is we can do a recursion on dimension. So uh the idea is uh we do very similar process as previously described but we check it dimension by dimension.

So we do the random linear combination of row on each dimension. Each time we reduce a dimension in each recursive uh call we we reduce a dimension until we get the base case which is the the matrix case. So what is uh the learning here? So we just go through three different uh basic basic building block of zero knowledge uh protocols and we realize they are all just recursive randomizing algorithm. So for engineers I think this is pretty engineering uh like uh terms right recur we usually we we're very familiar with is but zero knowledge basically it's a a recursive randomized algorithm on cryptography uh groups not not groups but cryptography primitives and then in IPA for example like in IPA and in in both IPA and FRI and also uh the breakdown we we both try to build a verifiable recurrence relationship in IPA We the verify is keep track of the updated group base for each round.

In FRI we we're checking on a random point and in breakdown we are trying to reduce a dimension by doing a random linear combination of each row of a matrix and in fact there are uh many other protocols actually follow exactly similar pattern um but uh which we won't cover today. And so uh if we can reduce the application level problem to this uh how this protocol fun uh like under the hood works then maybe we can find some optimized way to write the application. Um so here I want to talk a bit about implication on the application. So um in different um so basically uh this is a very general problem uh which is uh very commonly used in neuronet inference CN RN transformers you know classic machineing algorithms statistical methods all involve such operation so it's very it looks very specific but I think there is a a general lesson that can be learned here so imagine that we want to uh uh for machine learning training or or inference or um any type of application that can be reduced to matrix multiplication problem. Then on the application level we want to prove the relationship uh result matrix R equals A mult*ly B multiply C multiply D etc where A B CD are some matrix and the naive way of computing that is in the circuit would be uh would be implement that directly using using like 16 or whatever and then you can prove that in uh old N to the power cube O and cube Right?

Because or or using a stressing algorithm you can optimize it to uh uh uh like a smaller smaller power but actually we can but by understanding the underlying protocol we can actually interleing the application logic to the under underlying zero knowledge protocol logic to reduce the overheads and also optimize using the randomness to redesign the algorithm on top of it. So basically we can the prover can directly compute a multiply bals e out of circuit. E multiply c= f out of circuit fo uh multiply d equals r out of circuit. So and provide this out of circuit computation which would be extremely very fast as input to the circuits. Um so basically if you compute like ENF you already get that and then you you provide ENF as input to the circuits and then in inside the circuits we can implement uh free algorithm which basically using the randomness to check the metric meas to check the matri multiplication is correct in to the power of two.

So and also we don't need to recomp compute the randomness. We can reuse the randomness from anywhere like uh in the zero knowledge protocols we already compute the fame transformation to uh transform this interactor interactive proof to a non-intactive proof. So we can just reuse that randomness uh uh without additional computation to achieve the results which uh in this way we actually can uh compute the proof for a very large series of matrix medication in uh O to the quadratic quadratic time instead of like O to the cube or uh or a smaller term using some optimized algorithm but still larger than O to the power of two uh time complexity. Yeah. So, uh draw a conclusion.

So, first of all, I think it's important to understand. So, at at least for now, uh because there's this proof system that is immature and also sitting between the software and hardware and also for lots of the application we do we do not build this proof system from scratch for the specific application. Instead we usually draw some we usually just you know use other people's proof systems that is not as customized or uh specific to the application then it's very it's still important to understand deep on the lower level building block of zero proof system to optimize your knowledge application for now and also it's important to think of the argument one that actually is proving and the possibility to derive an equivalent argument to prove that can leverage the underlying properties of the protocol like randomness and thus significantly make make the application uh more efficient. Um yeah, that's it. Thanks.

A big round of applausees,