Wanseob: Open questions in the ZK Space |14th Oct 2023 | Sunway University | ETHKL 2023

another round of applause for one so please okay um thank you so actually this talk is about the open questions in the recent Z World and this might be a little bit theoretical but I will try to explain it as much simple as possible um so the first question is about what else are Primitives uh that we can Implement without arithmetic circuit I'm going to explain what is using the arithmetic circuit and also the second question is about um maybe what kind of a PR primitive alate we can ciz so yeah let's try to go so the first question The Primitives without arithmatic circuits um this is something about actually some of a Primitives can be achieved without going through arithmetic circuit um the easiest example is the ecdsa that that I just mentioned because ecds is also a zero knowledge proof which is also succin also non- interactive but actually it's proving some relationship that you have a private key and also you have a public key which is drived from the private key um actually if there there are exist some um other primitive some gget and if we if we Implement those uh ZK CET using only the um primitive polinomial iops without arithmetic circuit and actually we can make it much suc and much faster uh I will give you more detailed explanation about what this means so here is I have a good example which is a algeb uh rate limiting nullifier and uh would like to explain what is rate limiting n Fire and to understand this we should visit about the shary secet sharing and the polom commment schema a little bit uh first of all rate limiting n Fire is a tool uh to protect ourselves from the DS attacks Pam attacks when we have a network level privacy which means um imagine that we have a network level privacy which means the server does not know who is requesting the information in this case the server is very has some uh there exist attack point for the the those attack because people just can Rec say thousands millions of times for some information and to prevent this thing uh we can have some spam prot C layer which is called rate limiting nullifier in this case let's say a requestor has a priv key which is small s and then uh requestor will create a polinomial f ofx uh which degree is less than D and then also the relationship here the F of zero equals your private key and then uh when the requestor uh request some something to the server let's make the requestor submit uh F of M where m is the message maybe hash of message every time then what will happen if the requestor shares more than and d f of M then actually the server can interpolate the polinomial and sare can just compute the polinomial for example you can if you have two points you can compute a line and if you have three points you can compute it parab so if you have a d point you can compute a D minus one polinomial because we can interpolate so um this is something that how we can prevent the requestor spam too much because if the requestor shares too much then uh it will leak the privacy because we can compute the polinomial and we can just compute F of zero and it will become the private key this is what is actually this is what is charming secr sharing and also what is r living L ifier works so r limiting LF fire is currently using zero knowledge proof to make sure that the relationship is true which means actually you don't need to take care of this uh equations that the the the requestor share the PO F of M and we need to make sure that that F of M is computed correctly from a given polom and also the given polom evaluation evaluation at zero equals the private key of a given public key these are the relationship that we would like to prove and currently rate liing LF fire is using a ZK circuit to prove this uh yeah I mean the ZK circuit is a kind of a plus a minus of arthamatic circuits to prove this relationship but actually we can implement this relationship without going through the arithmetic circuit because we can Define the relationship between those informations using only the Pol nomial identities which is something like left hand side equals the right hand side and we can evaluate that at a random point and if the evaluation values are equal then actually we can think like the polom of left hand side equals the polom of the right hand side so actually we can call this as a algebraic rate limiting nullifier that requester shares an oracle actually which is a you can think this Oracle f is a hash of your polinomial app and also requestor Shar is a public key and also uh in in this case reest shares a nullifier and for each message M and then we can carry to that Oracle F that F of zero equals to the private key and also which means G to the f of0 equals the public key and also we can qu approv to the oracle that is nullifier n equals F of M this is all about the polom relationships and we can prove this using a kgj polomia commitment scheme that um Pro this is something when we use a prover wants to prove that uh you have have a polom and its evaluation value at X1 equals to y1 how to prove that is that verifier picks some random number R and makes some powers of that random R and compute a eptic curve point which is hiding the exact random number and this is a set of the elect curve points and actually after verifier shares the set of electri curve points then actually the request approver can compute the F of R using the set of a letic curve point and the result will be also something eliptic curve point and uh also after that the prover shares a quotient polom Q of x uh which is a uh f ofx - y1 divided by x - X1 because actually uh if you just put X1 evaluate the both side using X1 then actually left hand side should equal to zero and right hand side should equal to zero and we are evaluating this polom identity at a random value R actually this is all about the journalist proofs and what we are doing in zkp we are evaluating the polinomial identities at a random R and if the both side equals then actually we can assure that this polinomial identity holds true then actually we are and the next part is adding a zero knowledge part so because we don't want to share uh the these whole values so we are sharing those values into a hidden form which is called homomorphic hiding and which is also in the form of the tical point and we can check that using some special techniques uh which is called pairings um so here the takeaway is that polinomial commment scheme allows us to create some relationship without revealing some its detail and ALS also uh what what implies to us is that we can actually build some special types of polom identities for some Primitives for example this rate limiting lafier because we could achieve a same thing using only these polinomial identities without writing some ZK program because ZK program is having a a lot of some some uh extra computations to prove that and this is much much suing and much much faster and this sub question its subsequent question is that okay we could do the algebraic rate limiting LF fire then maybe we could we can do also we can also implement the algebre semaphor and I think I also need to explain what is semaphor here that SEMA for is a Anonymous voting protocol so first you construct a group mostly it should be something like Merle tree group of identities using the public keys and then from the public key committed public key that you have committed we create an a some informal identity actually exactly same from your private key we should drive a informal identity for each poll so and after creating an inform identity you sign uh something with your choice for that Paul then the signature can become a nullifier actually it's something becomes a proof and also becomes a nullifier that prevents you to vote twice and also we can keep the Privacy here that we are creating an informal identity and we also prove that that informal identity is derived from the membership group without revealing uh what kind of public key or private key used to create the that informal identity this is what the semaphor is doing and uh the key ideas to make this semap for actually we are doing everything we we are proving every this relationship that I explain in inside of a arithmetic ZK Circuit by writing a program and our mission is here is that okay let's try to Define some polom identities relationship equations rather than writing a program circuit and key ideas to implement some for without circuit is using a polom identity I mean polinomial commitment as an identity and making the evaluation of the polom at a poll ID becomes a the nullifier for that poll because you already committed your polinomial for example F Lis F sub Lis of X and if Lis uh wants to make a uh wants to vote to a Paul then should make a formal identity which is something like f subis of M or may Paul ID so after that we construct a membership group using the polinomial commitments and then after that uh actually to hide some information there we can use Peterson commitments uh which is say something the COA approach or we can also use inner product inner pairing products here uh to make sure that you are trying to use the same polom commitments also you are evaluating that uh but what we like to do here is that we would like to hide which polom commitment you are using to make that a formal identity uh is what we' like to do so actually yeah there is a uh potentials that we can reimplement those kind of things using only polinomial equations identities without circuits um yeah so just recap of the the first question uh The Primitives with arithmetic circuits that actually we have a many primitive polinomial iops which is something like polom I is something like you are proving some relationship between polinomial and uh the polinomial iops that we have is a every uh the polinomial is zero for every point or the sum of the polom evaluations of the polinomial equals to something or we can do some batch opening or product check permutation check uh lookup argument also we have some inner Pro argument like this and the question is that okay then uh what kind of thing what kind of cryptographic uh primitive ZK gadgets we can replace using this uh polom IOP only approach so this is the first question and the second question is about the customized algebra chap it's related to the uh recent improvements in the look up argument first of all there I as I mentioned at the panel discussion there was a huge paradigm shift for the polinomial iops from the univ various setup to a multivarious setup the univ the most most uh difficult thing for the Univar setup is that if you have a very very big relationship then you have a you need to have a very very high degree of polom and also as I just told you that when you share something that through the kg polom commment scheme you needed to compute some quotient polom so dividing a high degree polinomial using some maybe L degree polinomial is also a pretty difficult work and it takes time and most of the proving time uh spent uh Computing the coefficient using the fast free transformation and that is the most a pain point for the univ setup but actually we can we could convert that into a multivariate uh with a very low degrees and then actually we don't need any kind of some computations for the coefficients and actually we can express everything into a linear combinations which is a much much faster than Computing the uh fft and there was also a big Improvement in the recent lookup argument using the logarithmic derivatives and I'm going to explain what the log up is and also there was another Improvement that adding gkr into the log up and actually what does adding Gare into the log up means was something like okay maybe we can design a some customized algebraic shape just like we have GPU or AC for special purpose computations I will show what this means a little bit in more detail so uh the I need to explain the recent improvements in lookup arguments that lookup arguments is something that you are proving a set is subset of some predescribed table and most most effective way is okay we have some values and adding some uh random values there and multiply everything and then actually it should equal to the multiplying everything in the table something so this is a basic technique that we are uh trying to prove something is a subset of a predescribed stuffs and L what log up did is uh transformed this kind of a product check into a summation so actually uh we can if you just log uh a grand product then actually it just becomes the summation of the log of each term right and then after that actually it is it uh they did the derivatives uh one more time and converted that into a fractional uh polom and gkr what gkr did is there is that actually uh in multivariate polom settings it is pretty difficult to compute a rational polom so it is not possible so because of that we Define another multi-linear polinomial and compute that using the inter interpolation so actually we need to compute a auxiliary polom uh many pols and actually it's it was also kind of pain pain point for the computations and um actually this is what I explained that log up did just uh transform the grand product into the summation of of the rational pols and gkr actually did the expressed the rational polom into the form of a polom identities uh what does this mean here is that there's a P1 and q1 and it it actually it's a notation to express it's a P1 over q1 and its parent node is the summation of its left child and the right child and also it can be expressed as a P1 Q2 plus P2 q1 comma q1 Q2 and we can express this all the uh relationship into a simple polom identities using the gqr approach and with this actually uh this is something what we have designed design a spec specific Electro electronic chip only for the fractional some Tex stuffs and it can be used for the lookup arguments and uh using that actually we can achieve a much faster proving time relatively doing the grand product check using the multivariate uh Grand product check approach so the summary of these questions is that CPUs are also the general purpose for general purpose computations and zal proof circuits the arithmatic circuits are also for the general purpose computations and we have we have seen the very two good examples for about how to replace the circuit using the algebraic formation formulas in ter in in the case of the rate limiting nullifier and also the sema4 and also for the Primitive iops for example look up AR argument iops actually we could design a specific uh gget uh only for the lookup arguments which is something like designing a special GPU so my question is that okay why what kind of other primitive ZK gget or what kind of other primitive polinomial iops that we can design for the future is the open questions that I wanted to share today yep thank you so much do you have any questions hi once so uh thanks for the great talk it's very Technical and I believe I couldn't understand 90% of it but I'm try to ask I mean I'm try to understand uh some parts of it I think regarding the um the semap for example that you gave at the at the end you mentioned about um pison commitment scheme or also the in pairing product so I was wondering or what's the difference between this um the different commment schemes like can I also use kdg in that sense and if yes then or which one is better or how do I compare it if no then what's the reason yeah okay so uh Peterson commitment in the uh algebraic Semora is something like you are already sharing a uh polinomial commitment and actually that is a eptic curve uh point and what you would like to do is that hiding this polom commment is a exist in a set of group this is actually what the lcup argument does and the the C uh used uh is adding a zer your knowledge for about its index inside of this given table using a Peterson commitment so uh which is something like you have a polom commitment and Peterson commitment is you are adding another points here random point and then actually if this uh pet and commitment is computed correctly if you do something a uh using the root of unity that actually it should equal to the uh equal to when you have exponentiated end times so using that factor uh C could achieve the zero knowledge of the position uh so actually we are calling that a position uh hiding linkability and this is one technique that we can do some membership proof with uh while hiding its exact position so it can be used for sem4 approach definitely because it's a something a uh Anonymous membership proof stuffs and also inner pairing product is something inner parent argument for the um pairings uh and inner product argument itself actually has a Zer knowledge uh characteristic inside of it because we can adding some random and fold it and fold it and Fold It Again So eventually we're going to have a uh one instance which is folded using the random linear combinations so actually the verifier cannot know what exists inside of the the vector of it so this is the ideas that we can use for the algebraic semap for but I guess there actually this is still in the working progress so there might be some um mistakes yeah thank you I'm Victor thank you for the talk so my question is this polinomial equation can repress arithmetic circuits in terms of general knowledge calculation can we use polom equation to to design a g GK [Music] evm I that's yeah that's something my question what kind of a maybe in this ZK evm we we have a multiple up codes and actually look up arguments is replacing something there and maybe what other op code that we can replace using those kind of the polinomial identities is my question so there this what I really would like to explore more um we have another two minutes for maybe the last question if anyone have burning question to ask hello what's up uh thank you very much for the talk I would like to ask you two questions the first one could you please help me to understand more the example that you give in the previous talk about putting a game in a PlayStation F and to make it provable maybe you can perhaps expand on it and secondly please correct me if I'm wrong because from what I understood from the previous talk and from this one is that by usage of the pols your avoiding the usage of some like a ZK circuits so that is what makes the pro the process faster perhaps you can also explain on that thank you very much yeah so let me uh start from your second question that I mentioned that our final goal is something like we are we would like to build a provable computer itself the which means like you have a uh CPU and what you like to do is okay the uh State transition of your CPU and the memory is correct actually this is the kind of a final goal if we can do that actually we can prove everything but actually this is a little bit difficult for right now so we are trying to uh Implement that using only a subset of some up cuts for uh for for some VM for example like not VM uh for exactly uh especially for risk five this is some our approach that we would like to do and if we can do is actually any kind of program you write is provable so this is the operation that we would like to do and we are pretty confident that proving time is getting improved a lot so it might be pretty feasible in a few years uh and the my question actually what I shared here is that maybe when we when when we go into the implementing those kind of some provable computer there might exist some primitive up codes stuffs and maybe we can try to design some polom uh identity structures for those things was my uh uh some in uh intention here and the first question you ask about the uh what about writing a game uh then actually what I expect from writing a provable game is that the programmers uh should not take care of the ZK part not at all is is something my uh what I what I expect from the programmers in the future so I think uh did it answer your question enough actually not because when you make the game provable what is the benefits that's given to the gamer for example to the gamer so let's say you have have a uh competition or contest that uh everyone should just participate in the contest uh and we are just um finding who is the fastest racing driver in the world in in the Sim racing wor then maybe you can just try that in your home and you can just submit your proof so so you don't need to actually play the game you just need to show the proof that you can be the winner right because yeah it's proving that you recorded that lap time all right I think we don't have any more time so uh Round of Applause for one so for the beautiful talk