ZK13: EC Plonkish: Plonk-like proofs over the elliptic curve coordinate ring - Syed Hosseini

Transcript

[Music] Thank you very much for coming. Um I'm Seyad from Web3 Foundation and um this is a work with um Alistair. Um it's mostly Alistair's work. I I read it and I implemented it so I get to be here. But um um so let's let us start and um there's quite a lot of material that I packed here. Um because it's a workshop I didn't want to jump just you know to to to like conclusion and stuff. I I

thought I will explain the the the background but um I can't go slow on it because then we don't arrive to the end. So I I'll try to go over the background so you you you hear all the theory behind this stuff. Um on the other hand um we could uh you could stop me. So if if something that you have a question stop me you ask I'm happy it's a workshop right uh and I I I hope to get some to look at some of the code implementation of the stuff. So it's not only abstract object um that we are going through but um uh let's let's let's start okay uh so motivation so so yeah I hope uh

make you more excited about it um we'd like to do plunk like plunk is is very popular mostly um it's simple you know is is probably the simplest snark somebody can um explain uh to people like if I mean like in the courses like if you want to to teach a snug to somebody at the beginning I think a plank is the one that they can much easier than the other system get a hold on um is uh extendable you know you can do you can do plankish basically you can change the gate and then make it even better so so you learn the system so it's pretty good um and uh unfortunately we have this

this problem I mean a lot of the other system have the same problem right so um we only can work in fields that two to power there's a root of unity of a two to some big power um big power yeah that is is in that field and if you don't have it then you are doomed basically uh so people say so what like I'm going to choose a field that has this property why do we care sometimes you don't get to choose that's the problem the the field that you're going to work on it coming from the problem underneath and it you you have to deal with it. So um in those case um for example like we have this this this algorithm factory sum for um adding

uh uh verifying the the the um addition of the public keys together. um this public key is coming from an elliptic curve which are defined over a finite field already and uh you don't get to choose to do it in another finite field because already in that finite field and it might happen that that finite field is not doesn't have that property. Now if you want to do plunk then you have the same problem. uh or if you do recursive as snark uh you get the same problems because um you do it in the first field then it comes in the second field now the field the field is changed you don't have a lot of uh

freedom to choose these these um curves that that shows up there so there's there there is a lot of uh example of that that is why people write non-native snarks because their field doesn't work they may move it somewhere else but non-native not gives you 100 times uh more more more cost to the computation. So they are not the best uh solution if you can find another solution for it. Um oh sorry okay so to solve this problem we try to hack something that that works with it. This this is a work built on ECFT paper and then ECF2 paper which never got published but um so we took

those works and and then we adopted them to to plunk and we made it uh to solve this problem. Um and the fun part of it is it takes it touch so many branch of the math. So it's just an introduction to the math that is used in in um in ZK that that's that's actually just just an interesting problem for you to to go through it. Okay. Okay. Um I'm going to um just go over plunk because if you if you don't have it in your mind then then then I'm talking about I'm referring to stuff that's people don't have a touch but I will go very fast over it. But um I I I'm doing this because we want to see

what is plunk to see what um what problem we need to to address to to move it to another place because we are not going to use that field which is not good. We have to move it somewhere else. Going through the step of plunk we see this new place should should satisfy which criteria. Um then I will go fast over what is FFTD because we are going to talk about it a lot and then if you have if you have doesn't have it in the mind then then you will be lost. uh we talk a bit about elliptic care isogynies because these are being used in the ECF algorithm but not very deep into them but just just to mention them so they are not just foreign words um then we talk about EC FFT algorithm which um our work is based on and um we

have implementation of it to look like how how we work with this actual stuff that they're actually working because it get too many um complicated object but finally using sage you can implement it. I will show you this. And then finally, I'll talk about our solution which we basically we want to move plunk to the coordinate ring of elliptic curve instead of doing it in the field. And this is much more diverse uh uh object that you always can find something good in in uh in in uh in a form of an elliptic curve coordinate ring instead of a field that is dictated to you and then you don't have that uh good property and then you're doomed.

You you have no other choice. here you can change your elliptic curve and get a better object. So we are going to talk about that and then these are not nice these are not as nice as as fields right fields are very nice they're everything is invertible um and and and the the polinomial ring over the field then um uh is is a you know everything is facto factorizable everything you know this these lack some of those property but uh we still managed to do it but but we go through the thing that we have to hack basically to to make it work and at the end we go over one one small example just to for you to look how it works okay so I'm going fast over this

um uh so plunk okay so we start from the circuit then we look at the arithmetization uh of the you know gates and and the zero test uh then we we we look at the wiring wiring arithmetization this is the basically plunk part of the plunk the permitation of the P is coming from that and that is the complicated of the plunk and that makes the the problem part of the this this thing is mostly coming from there problematic part um and then basically we talk in abstract if I want a mathematical structure that I can run plunk on it what property that should have okay so so I'm taking this from uh plunk by hand um

um example uh so is is Pythagoras I want to prove that I have a solution to Pythagoras problem So I want to prove I have x1 x2 x3 that's uh satisfy the p pythagoras equation is not full right I can satisfy with 0 0 with 0 1 0 with 011 you know um so it's not real answer but I don't want to add more criteria I just want to have four criteria because the my u my big power is four so um I can't really go over that because in that example um so I go just with these four criteria and and and then I I I'll generate a polinomial which which will make the pro problem. So, so we start

with this problem. These are my criteria, right? Three of them are multiplication and one of them is addition. Uh, so that is how plunk works, right? This this is the this is the big equation of plunk that's uh encapsulate all the all the um the conditions except uh you can you can change it right that is the beauty of plunk. can take this off and you say my my gate is basically customized in a way that make my problem faster but the basic gate is there so it it allow you to add a and b right and and have a result and it also allow you to multiply them and have a constant so ql means that you're adding a QR means you're

adding b qo means that you have output the output is not zero qm means that you you're multiplying a a and b together and qc means you have a constant. So basically here I say in the first criteria I am not adding anything. So I put 0 0 right um and then here like um I have output and I have multiplication which they add together they should give me zero. So using that I can I can just translate this to the plank language. Right? So and then what I'm going to do here in normal plank you would use root of unity here but if you don't have it then what are you going to do right? So we are going to see what what we are going to do that for now I call them h1 h2 h3 h4 but

um abstractly this is this is the setting. So next step what I'm going to do I'm I'm I'm going to interpolate a lot of polinomials. I would say uh let me go to the next slide. Um I would say okay I will I want to find a polinomial QL which at this object h1 is zero which is root of unity in a classic uh pl first of is 0 0 0 and one and then I will interpolate and I get a polinomial which uh represent this this thing and I do that for every other column. So I interpolate all the columns and then I will add them together in the way that the the gate was and I get this huge polinomial which interpolation of all these together and then this polinomial

should be zero at all these right that is how the verifier will verify that you have actually the polinomial it says give me the polinomial as zero at all these places uh so basically that is the first thing I did here I did interpolation so if I don't have a good interpolation then I'm doomed So I need a good interpolation. The good interpolation is FFT, right? Um sorry uh so uh FFT is much faster. So so norm like you know naive interpolation takes n square time which is very slow. FFT is the best important interpolation we have is n log square. We can't have that then we don't have a system that is actually work in real life. Uh the other thing I need to

do is some kind of a zero test divisibility. Yeah, that's that is what I said here. um I I want I make f and then you are the verifier. You come to me and say prove for me that this f actually is zero at all those points and that that's in mathematic we do that by dividing this polinomial together. Now if I go to another ring and the division doesn't really work like that then then I'm doomed you know I need to be able to divide these two object together to be to verify that they are zero at that point. uh the other thing here you need to do the the verifier challenges the proven and a random point so they have to evaluate this problem at a random point and that also they use FFT to do it and if they don't have then your

verifier is very slow so FFT is essential the the last thing I'm going fast over this but after that you need to do the wiring test that's so I I verify that the equation is correct but I had some assumption that these two are equal to each other so if I don't check that the very the prover can cheat and choose two different number here, right? So the wiring test is here that these two numbers are um for example equal um so this is what what he needs to to check and that that is basically right. So I call this a polinomial as a trace polinomial. I can I can interpolate it and get a polinomial that at all these places is equal to that value. But then this polinomial should satisfy this like t of h1 which for example come here it

should be equal to t of h2 right. Um and to do that a naive way of doing it is basically have a permutation function w that say w h1 is equal h2 and then apply that to this polinomial and then the polinomial shouldn't move right if if place one at two is the same then if I move one to two and then apply a polinomial should be the same and then if I interpolate that and then prove that it's zero at all places then then I I'm done the problem is this is ns square power and we don't allow that right this is this is too too big the the polinomials of the of the approver should be of a degree n so a naive way of doing it doesn't work and like you know at least 50% of plank ingenuity was

to find a place find a way of doing it uh which doesn't doesn't require like you know this this blowoff degree here um and that is that is how it works um we we we we make this function which uh that polinomial that that's permutated my polinomial is at the top and then at the bottom I have a nonp non-permutated polinomial these obviously this is wrong sorry uh they are not one right when you permutate them they are not one but if the permutation works actually this will cancel with another one somewhere um so what are we going to do here is we

are going to to multiply the these one by one. I make the first first uh this animal for for the H1, H2, H3 and and I multiply them together and at the end when I multiply all of them together at least they finally should cancel each other and then um I should get one at the end when I multiply everything. So I multiply one by one I add it recursively and then you know this is a recursive uh equation for it. I add one, I multiply one at each step and at the end when I arrive um I should get one. Uh so to do that we do this polinomial right. So I say the polinomial I did was that I get H1

uh I um I multiply element with it. This should be HI I guess. Yeah. So this is HI. Sorry. Um so if if I take HI and and go to the next element by multiplying that uh um oh no that is H1 sorry um this is this X um yeah this is basically X Um so I multiply this and uh sorry Q. Um and basically I say the I make

this at at every step I just multiply uh one uh one H1 into this and I will get go to the next element. I multiply one H1 to this and get to the next element and I I satisfy this this uh recursive thing and every time I add new element I add that ratio to it. So plank says if you prove to me that you didn't cheat in constructing this and at the end it became one then uh the ratio is correct. Um so what what what will happen here? The only problem here is the thing that they used here is a cyclic group. I'm I'm uh if I don't have a cyclic group here I cannot multiply element with that. That is something that a lot of

other proof system doesn't have. They don't have a cyclic group. Here I'm using a cyclic group that is the uh next next thing that plunk need uh that's that not only using this this root of unity just as a root of unity it uses actually the the cyclic group property. Um so here basically I did that and and then I verify so I I will get a very small equation of degree n I can verify it but it should be a cyclic group. Okay, so for now we knew what what what we need requirement one we need something look like a polinomial right we evaluate at some point and then I can

get the whole function right some kind of a local global condition um I need divisibility I I need to divide one or another that is how I I actually verify that um um the the prover didn't cheat um I need FFT and FFT is working with the two big numbers Uh so I need to find a way to to simulate FFT if I don't have this here and uh I need um yeah so so I need FFT for all these I I have a polinomial I should be able to evaluate it at end points I need to be able to interpolate PX if I if it's

evaluated in endpoint I should be able to to go by basically I need FFT I'm like um and then you know I don't want to solve it in n square if I solve it in a square my my my my uh thing is very slow so I want to get to something like this and this is the last requirement which a lot of system don't need like you know even I think fry doesn't need this um I need a cyclic group because when I when I uh do the permutation then my permutation check is depending on the fact that I have a cyclic group which uh make my low degree polinomial check and you know if you have FFD algorithm doesn't mean that you have a

cyclic group so I need one one extra requirement okay so basically the first thing we are going to attack I'm going this is basically review of secft paper I'm going to find a way to get a good FFT that I that I don't have um so here what I'm going to do I'm just going to fastly talk about FFTD FFT is basically a trans trans uh function linear transform uh on a function space. uh this coming from the continuous level but now we all use it for the uh discrete version right and the discrete version is basically the same you have function from finite field to another finite field which is polinomial right uh and FFT ft which is transformed but

what it does is change the change the basis and when it's discrete then we call it DFT um so an example of this is interpolation right interpolation is just change of basis so I have this basis which is the log range basis. If I represent the polinomial lo basis, I'm represented with the evaluation of the polinomial. If I uh represent it um in coefficient basis then I'm I'm uh uh I'm I'm basically showing it in a normal way that people look at the polinomial. So DFT is basically you give at end point it gives a polinomial you give a polinomial gives you the evaluation at end point.

I said that so we want to solve it in a faster way. So let's see what how how FFT works. Um I'm going very fast over this but um it does some recursion. The big thing here is that every time it wants to evaluate this polinomial it breaks it into two polinomials which are strictly less degree evaluate them and then add them together. So in the the the traditional FFT does this right and that is where this the degree to um uh root of unity comes because every time we take it to power of two and then the uh you want to to to exhaust the the space with this power of two. So, so I break the polinomial even powers and odd power. I take one of the x out and then

again I have two polinomial of even power and then I'm I'm evaluating them. Then I break them again into degree two till um this is what the even and odd look um and then um now my space is smaller because I took everything to the power of two and and and so half of them be collapsed to the same range. your range become half size, your polinomial become half size, you try to evaluate there and you go to the next step. Um yeah, so till you get the constant polinomial, you go down to the degree one then everything is constant you evaluate uh trivially. Okay. So so what do we need for this to to happen? We need every

time that we we have a big we want to evaluate end point next time should be n half point and after n4th point um so like that right so when I take power two my my domain shrink in the half that is why we like this power of two um we need um yeah uh so so so that is why this should be two part of k because every time halfing it, right? Um and then I have a glue step. So after I evaluate this polinomial, so I broke them in a small polinomial, I should be have be able to uh glue them easily. And this is the easy glue here. But you

might change it and your glue will be different. But this is the naive glue in the in in um in FFT is this. Okay. So obviously the problem is this. If two power of k doesn't divide q then I don't have that that thing. So and we are not free to choose q. So what should we do here? So basically the pro the thing comes here for example you choose q for f efq be pairing friendly. So and then you don't have a lot of choice for q and they won't be f friendly. If you want to prove on that queue then you don't get that. That is basically what happened in this. And for example, if you want to prove something on on Bitcoin's keys, right, they aren't very very like they

are in prime field that has nothing like that. So you cannot use FFT there. Um so basically here I say when I want to do FFTD, do I really need this roots of unity? And that's that that is the ECF paper reply says I don't really need that that nice thing. I I only need uh a function that makes my uh at every step I can I need to apply a function that makes my domain half size. I don't even need my domain to become the same here. The nice thing about this power of unity is you take power of two you go back to the same set. But really you don't ECF paper says you don't need that right. So only I need this function be

easy to compute should be two to one. So it kills half of the domain. And then after you do that, you get this polinomial. You should be able to you should be able to um uh glue them back together. So that is really what we want. We we we have we have this fin this field Q which is a bad field, right? It doesn't have a good uh power of two. All I need bunch of two to one function and a set of that field that every time I apply it kills um half of the domain and then they don't the function even don't need to be the same it's and that these don't need to be the same right so um this is doesn't doesn't show that but it need to kill kill at

the end you get to one element and then you can survive so that is all you need right uh the only problem is um we don't have these functions like for free right like you look at a finite field nobody gives you this function but we at least we know one way of finding these functions and that way of making them is coming through elliptic curve though at this level you don't care about the elliptic curve you only use that function elliptic curve to find those function and then you come back to the finite field and then you just give you this function that kills half of D every time but that is a way of doing it because other you know mathematician had already work on it and they s find out how to compute isogyny that the

algorithm is there. So why not use it right instead of like finding another way of this finding this function so the isogen is giving us that. So I'm I'm going to give a crash three slide course on isogen just to know what it is. So um so I'm in FP right which is not a good field and I want to move to um elliptic curve that I make elliptic curve on FP. Okay, eloptic curve is it's something with this equation y square= xy of 3 and u the points basically xy uh they should satisfy this equation right there should be any point on the curve make this equation zero and then

they have this fancy addition law that makes them a group um we don't care what is the detail of addition law we know that we can add these points together like we add numbers but in a fancy way And that makes a billion group. Okay. Um so what is isogyny? Isogyny is basically a function from one this curve. So from the point of this curve that take it to the point of another curve. But this function should have some property. So it should take 0 to zero and it should uh it's it should be algebraic function right is is it should be expressed by polinomial divided by polinomial and it should be a group homorphism. So if you add something you

apply the function to it it should um keep the the the addition as you add it first and you apply the function or you you you apply function add after it should be the same. So these are the the isogynes. So there are function between elliptic curves but then we have some some good result here. The good result is if you find a subgroup in this this curve right I said the point making group if you take a subgroup there you apply the function uh you always have a function you always have a function that's kill all that subgroup so so that that is basically what we wanted we wanted at every level kill two elements kill one element two element one element so that that that

theorem in elliptic curve says every time if if you take any elements that's you can make a group then you can make find the function that kills that group. It is the kernel. So we are going to use this property to find that function. Um and this is the size of the degree of the function. Okay. So that what is cool about elliptic curves is that we knew that Q is bad and we are doomed for elliptic curve. There's always always a way of doing a finding elliptic curve that has a good value. So we have this theorem that says if Q is is the size of your field um if you're not very very far from from Q which is a square root of Q you always find elliptic with that

number of point and if you find a number of point that is divide two power of N then you're then you can use those you know points to do this to find uh basically to do FFT that we talk about so that is the cool thing about elliptic you have so many elliptic curve with over FQ you're not limited but on FQ you are just have no other choice so Now we we we can find a elliptic curve that has a good power uh it group divide a good number right so so now my Q wasn't good but I found the elliptic curve that it divide two^ of k divided okay and then so I found this elliptic curve with this number I will find that then I I find uh this this subgroup of it that has 2 to 5k and then

I kill one element at the Okay. And at each level that I kill the element. So I I I find the element of degree two in this group. I kill it. I get one one I get one um I I I go one step right. So I can find f1 f1 that kills gz g prime zero and um I get one. And then now now I have a group with two to^ of k minus one. Again I find the element that of of order order two and I repeat this and I find another function.

Um yeah so the the problem is this isogyny map a curve to another curve but actually what we needed we needed map between the fields right because we wanted to do FFT on the field. Uh the good the cool thing about the isogyny is the map actually is just you see so this is this is a map taking a point with x and y coordinate to the new x ycoordinate but the x coordinate is only depending on x. So when I find isogyny the first map only depends is basically a map between fq and fq. So so that that that is how we are lucky here.

Basically, I find is journey for free. I find the map between FQ, FQ, which we're looking for. Um, okay. So, let's see what algorithm works and then I will go to the code to to look actually this is actually not just I'm just saying nonsense actually works. Um, so I find I start with a Q FQ that doesn't have 2K through root of unity. Um I find the elliptic curve on FQ which has a good two to power of K root of the I mean element. Um I find the group of order two to power of K. I start um taking the coordinate. Yeah. So I I

I'll take the coordinate of those x coordinate of those point. These become element of fq and then half of uh and then I will find the isogyny. Right. um and then uh the isoggen will give me this two two to1 function. I starting killing them and uh as a result I will get this uh I break the polinomial into two and then there's a gluing a step that I glue them back together and I evaluate the polinomial. Okay. Um I'm going to put this here um and and just just look at the code for for for this FFT and all this stuff that I told you.

Um, okay. You can see it right. Uh so this is the code. Um okay. Yeah. Um we I should talk into this. Uh so I I I don't want to bore you very much but I go just to the setting at the bottom. So I did this right. um I I choose this is my field is 101 right so is a prime number minus one is 100 so the the the multiplicative group

is if degree 100 which only divide four right doesn't divide eight doesn't divide 16 so basically the biggest polinomial you can do is degree four three right because with four point you you you interpolate you get um uh degree degree degree 3 polinomial um I found this elliptic curve y^2 + x^ 3 + x + 2 and this one has actually 100 element so that one has only two identicities only divide by four two of four um then um I'm going into into this um let me uh look just just print the isogynes okay um so

basically with That is what I'm going to do. I'm going here. I found a cyclic generator and I kill it here. Um, isogen builder. So, so I'm using Sage, right? And I tell Sage, find me the kills this point. I find the isogeny. Let print it though. Every time we make it uh print next is okay. So, I'm going to start this sage.

Um no. PDB. Yeah. Okay. I forgot that we doing Fire Python. So, sorry. Um E CFF Next is I should put in the parenthesis, right? for now is power of four right so I kill once four become two and kill two become one so I I have two functions only so let's run that uh here uh pdb reload uh so I'm here you

know and I'm going to basically call a cftF which prints uh the The isogyn is you see. So this is the isogyny the first one and this is the second one which you see the 100 was got killed to 50 and then uh that you know then then it goes back to the same curve but still it kills the second to 50. So, so the the group of of of size four became two and then became one and then um I have my polinomial which is one one one right that is what I did.

Yes. No, no, it takes it to a different curve as you see. You see this a completely different curve. Yeah. Yeah. It says it here. So the first The first curve we knew was this x + 2, right? Right. And then it took it to 82x + 30. Yes. Okay. Um the third time I think went back no is another okay but I'm only caring about the map map to fq which always become over the same field right because this this all define the same field and then I'm looking only what x coordinate goes to what and x coordinate coming from the

field. So it give me even the maps are from different elliptic curve still give me the same map on each because the field is the same. I just look at the map over the field and I get the same map. So I'm going to run um this and now I'm I'm doing the ACF and basically you see I printed at every level that I was evaluating uh so uh the polinomial so it take it down to polinomial evaluate that the second one is I actually interpolate the polinomial using direct I'm using interpolation just to check that this gives the same result at the end I evaluated at four points that's because I had only four points right and it shows that they are the

um I can do from a bigger curve right so so I went to the code and and and did found bigger curves uh with a bigger addicity this is this has eight two to the^ of three right and the last one has two to power two^ 5 which is 32 so I can basically go through the code and you see this is a polinomial of degree 32 that evaluated on 32 points and each of them one of them is happening by ECFD and one of them with direct interpolation just to show that the interpolation has done correctly.

Okay. So, so that's that solves our FFT problem. Still we have a signific um so Q is fixed, right? So, how difficult or easy it is to find an elliptic curve defined over FQ given that Q is big like 256 bit. Yeah, I understand. Um is also K fix it like 2 to the K is also K fixed or not I think so I mean you have a lower limit if you find a C that is better than that then that's good and algorithmically speaking given Q and K how difficult so easy is to find an L yeah so uh it's not easy it's not easy uh the the small you know maybe you want 20 maybe it's easy to find two to^ of 10

but then the the higher you go to the^ of 20 then become harder so let's say Q is like the field characteristic of BLS 2381 and you want K to be 20. Yeah. Yeah. Um is it easy or difficult? So you at that level you cannot try an error, right? You cannot do random. Um there is a method it's called complex multiplication. I don't know if you know it. Um that's basically give you a way of finding elliptic curve exactly with a number that you like. Okay. And the complexity is like feasible I think. So it needs some Hbert's polinomial computation. So it takes time but um but it gives you that. I remember I tried that with BLS 1238 381 and I I I

think like I I got like I I left the computer to compute for 24 hours and I got to power like 18 but it I never got to 20. So the best I found was 18. But um I now I I have a hard time to see to remember what was the big uh complexity there that was was making it bigger the K the bigger the circuit you can prove with plunk I guess. Yeah exactly you have more criteria. So if you have 1 million criteria then you only need to 20 right? But if you if you have you know 20 million then you have to go higher.

Um so this is the toy example. Obviously for finding these I just went over all the elliptic existed there and I found the one that has better um higher think. Okay. So let me go back to the to the slide and talk about the last problem which is the group problem. Um so for now I I like to walk. It's good. Thank you.

Sorry just for the recording. Yeah. Yeah. Yeah. I know. It's good. Um so um that's it. So we got FFT. What else left? Could we do plunk? Which of obviously we cannot because I'm going back to the field and there's no cyclic group there. So I need to go um uh to do something else because plunk doesn't only need FFTD. It needs basically group to do the permutation check. So the solution we are going to do here is basically not work in the field anymore. move actually to the elliptic curve and work there. uh and so I said we need a polinomial so we have to go some kind of polinomial over

elliptic curve and that's basically called um polinomials that are defined over this you know points before we had a polinomial that unaric polinomials only get x now it gets points um okay so just just just to see what what is the equalian so when when I in the field a polinomial basically function from this field to itself Right. Um and then if I have x is identity function um in elliptic if if if you have by variant field like x and y then you you get from this field two variable and then you end up with the same you you you map it to the same field.

Um and then if you have elliptic curve actually you you want to take point from the elliptic curve and map it to the field. So, so I have this is the concept of my polinomial and elliptic curve. Um, so basically they are by vari polinomial but we assume that they only defined where elliptic curve is is zero. The elliptic curve when xy is satisfy elliptic equation. If if the point is not elliptic curve then my polinomial is not defined right. So basically I take the polinomial mod this pol this this this this polinomial. So I take a polinomial from from here but I assume uh no matter how much from this I add it together I get the same polinomial. So so this is

polinomial basically mod basically that so that's that's what we ended we we get this bariate polinomial but we mod it based on that one polinomial and we get this object with a ring and we call it coordinate rand of elliptic curve uh we call coordinate ring because that is how you define coordinate on the manifold. So they got the name because there first there were differential geometry and then people added algebraic geometry all the name coming from there. Um so there are polinomial in this but then we have this nice theorem. It says any polinomial in this field can be uh represented like that. A polinomial solely in x and then another polinomial be x that is multiply with degree one of

y which is obvious right if power of y is higher then you can use this to kill power of y more than two. So they only need to have one power of y here. So now instead of working making plunk in a field I'm going to do it in this ring that is a co question is this ring good enough for doing plunk. Uh so let's look at it first of all the degree. So before we had degree of polinomial was the highest power of x right but now is not anymore. So it it also makes so this is the definition of the degree maximum the two degree of this or two * degree of bx plus 3. And it's obvious because y is degree three and x is degree two.

That is the only thing makes sense because you always can take power of three of x and repair with it uh quadratic power of y. And then if if this action will change the degree then degree is not a invariant. So that's the only way you can define degree is that y has degree three and x has degree two. So we have a new definition of degree in this ring. Um so can we do interpolation? So in in this field we are interpolating I would give you s point and it would give me a degree s minus one polinomial. Here is different. If I give you s point then I will get a degree s polinomial. This comes because there is no degree one polinomial in the field.

There's degree zero and there's degree 2 3 four five. So there's no degree one. As a result when I need d elements it gives me degree d. Well in in a nor in this uh in this polinomial ring when I get d element it give me d minus one. So I have interpolation but gives me this um that the other thing was that the interpolation always works here sometimes it doesn't work here. So we have a theorem and if it doesn't work then we have to add one one more uh condition to get uh to get it work like I I need to add one more degree actually um and this is the condition that that that doesn't work it's actually the

place that we are using. So the naive interpolation doesn't work. Actually I have to add one more degree. So not only I get degree s I get degree s plus one because this this this string is not as nice as that ring. You know it gives me this but it's only one degree. So it's not that bad. Uh so naive interpolation how can I do it? You see I I so I want I give you value for fxy and I want to find me a polinomial with ax plus yb that does that. I mean the naive way of doing it is basically write it like this. So I need to find a z to a n and b 0 to b y and basically I can get a get a matrix right um so you have given me these values I get this matrix I want to find this and

these are the setup values you say at this point it should be equal this at this point should be equal that I solve this po this matrix right I get the polinomial it get interpolated the problem is here right this is a very bad efficiency I don't want to do that I want to do fft and now we want to see how can we do FD um this is from ACF2 paper and that is what they do. So as I said we have a we found a good curve right so I have this group in it of two power of n and I um how much I have um and and then I am I'm adding another point to that the problem is I cannot work in the group itself I have to move it away because

zero is in that field zero is point at infinity which uh is is not defined for polinomial you cannot put point infinity in a polinomial so I move the group a bit so I can I can give them finite value in instead of point at infinity because polinomial at point at infinity are infinity they don't give me normal values so I move it with this edge so I'm getting the element of the group but I double it the minus h and plus h so I get all these points and and I'm going to uh interpolate it uh I get the interpolation values right because they gave me what is the value of the polinomial and now I add these two together and if you look at that equation these two cancel each other and what's left is

A right so when I do that I know the value of A and then A is a univaried polinomial so I'm going to use ECFT to find uh the polinomial A. Then I use the same ECFT to find polinomial B and then I have find my polinomial. So I use ECFT over this doubled domain and then I get a polinomial. The only problem here that ECF paper doesn't address is that because you doubled the size of evaluation, your your degree of polinomial now is is doubled. So if you had a 1 million criteria like you have a degree 1 million, now you have a degree 2 million. Um and uh so so to improve that we basically do this. We tell we

tell the user just give me all the all the criteria on the one of the set and on the second set I evaluate only to zero. because I I don't know how to evaluate only one set because I need this this this criteria to to to be able to recover A and B but I say don't give me here I evaluate on zero and then after I evaluate it so this is now degree 2 million polinomial right then I will get this polinomial that I have evaluated no matter what you know I because I'm not using FFTD I can evaluate this like with the naive way that I told you but I have done it before and then this is this is a degree one million polinomial Now I evaluate it as zero at at the same point that is was zero. I also evaluated as zero and then

I divide this by this polinomial. So I make a interpolation of degree 2 million but then I kill one million of it at the end. So um the interpolation is is long but after that I get a good good polinomial. So that's that's one good thing there. Um do we have a zero test? There is an again complication here in in in in FP you could divide by any polinomial here you don't have it because this is not a unique factoriization domain. So uh not uh you can if I you know the only if you can divide then it says they have zero at the same places but you can't always divide. So the only way you can divide is to to make an element that actually

has those zeros. So, so in our case for example we want to know our polinomial is zero here but I don't have anything that's that's only zero here because I should the addition of thing that's I able to make a function should should add up to zero. So I'm basically adding one more point here to be able to do the zero test. So it's it's not as nice as before but still it's still do doable. So the only thing remaining is that I I I should be able to do the product check that before I did. So now I don't have a problem. I have a group in elliptic curve. So I have that group I can I can make a cyclic group and do all the plank stuff in that group. So so now because I got out of the field. Now I got the

group in on elliptic curve and I I write the same same equation you know on this um the only problem here is this is not a polinomial. Why? Because polinomials like this if this was a polinomial this this has a this if was a polinomial then it has a it has a at infinity is zero right as infinity is infinity if is a polinomial now when I move it with g it moved the point of infinity so if I put zero here in this uh like in this case let's look at this um if I put zero here zero has moved to g and at zero this was infinity if it

was a polinomial then it will be infinity at here uh at g and something that as G is infinity is not a polinomial polinomials are not they only have infinity at poles so basically this this because when I add this addition elliptic curve it get a denominator it's not a polinomial anymore I have to kill those denominators so my function will get bit bigger I um so this is basically what what is happening you get you get a pole you want to get rid of the pole the pole is where the function is equal to zero so I get all these poles all these places that this function gets to infinity which is all element of that group G. I mult them multiply together.

I get the denominator. I multiply the final result with that. Um let me go back here. Um I multiply the final result with that and I I I get rid of um this um I go five minute on this uh example. Okay. Um so so so this is an example I want to make plunk not on the field but actually on the elliptic curve coordinate ring right. So the the field that I start with is 37 um minus one um uh it gives you 36 which is only four

four so so you only have two to power four right uh then I want to change it to an elliptic curve that uh give me more more more more place for criteria so I get I start with the bad field which is 37 I find the elliptic curve um which is y^ Right. Uh y^2 + x is^ 3 + x + 1. Um right. This is my curve. Um right now it's 48. Now even the field only had four. Now this is 16 times three. Right? So I have now now I have degree to power four dividing my my

curve. Right? um I get the uh um the generator of the of the curve right and I look at the order is 48 I need just the degree 16 group that is my cyclic group so I kill I think the degree three uh so I will get uh degree 16 subgroup right this is the point and then this is the coet that you know I'm going to generate uh so these are the element of the group and I use at edge to get uh get rid of the infinity from this group so this become my point I'm going to interpolate over these points right

and I define my and I have 16 point as a result I I did a so these are the criteria for the um Pythagoras right I made the matrix and and then I I'm just going to solve the matrix to get interpolation I don't use a ECF so it gives me a polinomial there you see this is b and this is power of x is zero so I I interpolate each of the polinomial and then finally this is the polinomial I go out this is fx the gate of the plank that is defined over the curve as you see it some of them has y

and some of them doesn't have y Yes, for wiring test basically you get into this thing that I told you here I cannot do the wiring test because I don't get a polinomial uh as I said you see we have this this this thing from plunk we can still use it here except it gives doesn't give me a function so what I need to do I need to basically multiply with this denominator to to get rid of the get rid of the denominator and I get a polinomial Now then this is a polinomial. I can interpolate that and I can do the um uh the the the check. Yeah. So this is um the

references basically CFFT1 FFT2 but we extended it to plunk. Um here we have a Kusama ZK summit uh to invite people to do whatever the ZK they have just just import it to Kusama is is during the web3 summit in Berlin if you want to come uh we have a you know grant and stuff to do it and and discuss what what can we do there thank you very much any question. Okay. Okay.

You have a microphone. Yeah. So, maybe I missed it, but um you didn't define the function that goes from E of FQ to FQ. Is that implied? From E of FQ to FQ in in first case that I'm not doing plunk. Right. Right. um that I will show you. So in that case, but in the second case when I did plunk, I never came back to FQ, right? Oh, so you never go back to FQ. I mean somehow I I went in FFT just just because I don't know how to do otherwise. But in the first case, so let me show you um

11 10. So when I do ECFT I get lucky with isogyny. So I I I guess that the answer to your question is really this this thing that's this is my my bridge from EFQ to FQ is this theorem that says any isogyny that I'm going to write is of this shape. So phi is taking uh is working on elliptic curve but every time that I

compute it the first coordinate is actually function fq. So I I use the algorithm to find the isogeny and by default it gives me this. So every time I really want to go to FQ I I will use that. This this is this is how ECF work and uh that is what happened here. And then at the end when I did this I needed to do this um here I did another transformation here.

So I wanted to interpolate that which I don't really know how to do it. I use this criteria. So when because because the y-coordinate of this point and this point are negative of each other and both of them have the same. This will kill this uh this this part of it and then I get something only in FQ which I knew how to do a CFFD and I find a then I will do the the negative of that will kill this one and I divide by that and I interpolate this. So these are the two places that they go back to FQ. Sounds good. Thank you. Thank you. Thank you very much.

So the projection on the X line of an isogeny always depends on the X coordinates of the point. So not only that's it. There is no Y. Yeah that's it. So this is only for two isogynes or also for uh there for most of isogeny in degree two there might be like if your prime is a if if you define over fp2 then then it might get complicated but um I'm pretty sure it's more forization is like that and so if we cannot find a higher to addicity can we find a smooth field like powers of other three five and then mixed Yeah, definitely.

Definitely. Yeah. So, that's that's the point. You can use any power you want. You show then that that three isogenesis, five isogenes, the have the same same shape. Yeah, I'm pretty sure because I worked on another isogynes. Um, you know, when you want to do hash to curve, you actually um use isogynes. If your curve doesn't do a good good hash to curve, you use isogen, you make it to another curve and you bring it back. I did those on NBLS 12381. Talk about bonav paper. I guess I guess yeah that one and and that is like I said in degree 17 and it still was look like that. So I wrote the code in in arc work and and basically the first function was only the only if your prime is like looking crazy like two or three then which we don't work on I mean bius you

use as degree two but yeah you're welcome. Thank you very much.