ZK11: Circle STARKs - Ulrich Haböck & Shahar Papini

Transcript

[Music] I'm going to me let's say Shaka and me we're going to talk about uh at least from my point of view quite exciting piece of work uh for me personally exciting because when I initially approached the subject I didn't have any clue about algebraic geometry and elliptic curves and isogenies all this abstract math was like a book with Seven Seals on it I didn't want to open Pandora's Box and actually it turned out that for that piece of work one can study these Notions if one wants by

something that is very easy to understand and very Elementary and that's the circle and that's what's the presentation will be about uh but first let me just for completeness talk a little bit about the history the line of research I mean when I talk about regular Starks uh I mean Univar Stars so not something like pus or frus yeah so it's nothing like multivar s uh I'm staying today just in the realm of uh of univarate stars so and and typically what do you need for an univ st you need a finite field often

you choose a prime field uh but there is one specific property that makes the prime useful and it's called Uh FD friendliness and uh so classical Starks you could say the space where you place everything where you place your domain where you place your trays on the domain uh is the line just depicted F the prime field as line line uh you have some action on it of symmetry that's the multiplicative group it's a smooth group considering that P minus one is z that means it's fft friendly so that's the key ingredient

you need to build a stark to have a smooth group acting on something in this case it's not even worth to think it's a it's a curve no it's a line yeah so uh and the object you obtain so you have witness data you place it on your favorite domain and uh you encode it into pols so this is the algebraic objects you work for once you have pols you know polinomial IOP Schwartz simple it's always the same then quite recently actually uh there was the seminar work of benas D Caron

sasti kti and David leit uh about the EC fft the EC Stark uh so so what they do is cu often in many applications you you would like to work with a prime field where P minus one is not smooth which is not ffd friendly so what can you do here um and what they do is here just change the space just move from the straight line to something that is well studied it's a curve it's an elliptic curve that's well studied it's abstract even for me still though uh but they say okay work on an elliptic curve because if you know from geometry that's a

group and you even can s there's a rich v a rich manifold of Curves you can construct sample and if you do it in a right way you sample your curve on which you have a subgroup that is exactly that smooth as you wish it should be and so so the whole Stark works over an elliptic curve it gets a bit abstract what are the algebraic objects here you encode witness data into it they become rational functions over that curve that's essentially what you get but you can argue similar Sipple there

is an ecfd and there's a big misconception in the CK Community about the EC ffd it's really as efficient as the ordinary Koolaid 2K totic fft so but anyway why is there is this misconception I suppose for the same reason as I also thought or we at polygon we thought oh no e FD it's not as efficient uh because it's an H it's two 0 pages of UPS math was too much for me so the question started at least when I was thinking about in this direction is can we do with something simpler and

there was even some preliminary work that we published last year it was called something like read Solomon Cotes over the Circle Group but that already was Pathway to the circle and then I metaka I fell in love with him with this guy and would you like to marry me so Applause [Laughter] please no unfortunately he he's almost married already so so no no luck for me here so okay so but uh the full thing was can we carry the whole abstract math the whole Machinery almost nobody is

willing to understand to the simple simple curve the the circle curve and that uh that brings us to the circle stock so it's a simpler construction over everybody knows what's the unit circle is I mean you can grab it you can turn it around you can play frisbey with it or whatever you like you know uh so that's a very simple thing and uh if now it's not P minus one if p + one is smooth it's a power of two or it decomposes sufficiently into small factors then this is a good choice because the number of points we are find at Fields I'm hiding here the details the number of points is of of a

quadratic curve is p+ 1 that's not obvious look in the paper if you want to see a proof of it it's Elementary self-contained it's not difficult but it's it's yeah it's it's not obvious if you never seen it before okay so uh in particular p+ one smooth the prime that we have in mind the polygon also at starware uh is our favorite Prime which makes which is Heaven for us it's the menen prime M31 why it's heaven for us look at this it's 2 to 31 minus one and H it's even better than two if it would

be something like 2 the 3 2 minus 1 which isn't Prime by the way uh because if you talk to the people that know how to optimize field arithmetics with uh AVX or neon instruction Vector instruction set on standard CPU architectures like he knows better he will talk about it probably so this is extremely fast I mean there is from risk zero just a attribution to here they really move to a very cool 32-bit field it's a baby bear Prime which is already quite fast and we were thinking a lot about should we choose baby bear but we manag to do it with something that is even faster and that's the reason for that work so it means for for

mm 31 p+1 is smooth so the circle curve is a rich curve it's a good curve it's a group you just rotate by rotation you know take one point consider its angle just think of it of you compute don't compute it that way uh and Q is another angle so you make the multipli the additions of the angles that's give that gives you the new Point here that's the group operation it's the same group operation you know from a complex unit circle if people still have some calculus uh background so okay so how does it work it's a regular star like a regular star there's almost no

difference I already already said everything that but let just for clarity let me recap so your Trace domain that's where you put your data on uh is is a subgroup on the curve or a CET of it witness data which is placed on the trace domain is encoded into polom again and that's nice feature of the Circle Group versus the E elliptic curve F fft so uh you get still B vared pols uh but

uh at least polinomial and you can argue simple like the usual concept you sample a random Point whole Space is the Cur the circle curve you sample it on the circle curve I have to say here over a sufficiently large extension for soundness and then you test the constraints at this point so this is the circle so this is how it works like and it has two main ingredients one is the so-call circle is simplification of the EC fft for efficient encoding and polinomial Artic and then tightly related by concept of so fry low degree test so this again on the circle uh this for just the matter of time will be only about the circle fft and now I hand over

to Shaka he will explain you the circle fft by means of a very Elementary explicit example thank you hi there um yeah no when I started working with like I really enjoyed working with this guy he's obviously a genius and when he started he didn't know a lot of algebraic geometry as opposed to him I still don't know any algebraic geometry and Okay so

I want to show you guys a concrete example to of the circle fft just to show you that it's really it's similar to regular fft it doesn't use any group operations just simple field operations and uh if you want to implement or do something about it maybe this could help you all right so uh we are at the Circle uh over the field the domains we are working on unlike regular fft which is a cyclic group it's CLE Group H and this is a generator H it's two points this time two uh two

coordinates X and Y and this is how the domain of size 8 looks like and you can think about it as as if it's the unit circle in a complex values like a plus I B and it's turning around but it's on the group circle group all right so I want to try to interpolate these values which means to find some polinomial of total degree this case at most four because I have eight values that's how it works in circle FD H so how do I start with a finding a polinomial that variates to these

points all right h the idea is to do a decomposition almost exactly like in regular fft in regular fft you're taking your polinomial and you're splitting it to even and odd Powers with a very similar formula H well this is almost the same we spling it into two pooms of X and we have this multiply of [Music] Y this formula is really uh is very simple for for the circle because if you put X XY and another point xus Y into the first uh equation you can extract the values of the

decomposed polinomial as you can see there F0 is just the average as you can see for example we have the point two and the pointed vales to eight the symmetric one their average is is five so this is going to be an evaluation of the first po F0 so we do kind of a an fft butterfly on these two uh symmetric points and and the blue poal the blue decomposed will be the difference the the an anti average divided by the y coordinate which is a all right so we started with this these eight eight values and we decomposed them into

h two po the F0 and F1 which is the averages and the anti anti averages and and the pooms on the right actually they are symmetric so I only need to specify them on on the four points is and they po only in X so if we look at the operations we did it's just basic field operations there was no Circle operation involved anywhere it's just taking the average of the values and taking the difference and dividing by this field element a okay I I just would like at least for me

to clarify something uh if you step back here uh you know even or not look look at this first function you take a point you take its opposite points with the same x coordinate that's the reason why we need to locate the domain it was slightly shifted what the identity was not sitting here here where you would expect it so you just take have have the action of the conjugation map let's call it that way the involution which just switches the sign of Y and this involution gives you the first one doesn't change under Evolution it's even the second one changes the sign under Evolution it's

odd so in this case it's really fully analog sorry to interrupt here maybe he's you said it before but I love you it's it's great thank you thank you for the uh notes and clarification a okay so this is how uh we start the fft with a de decomposition to even and odd pooms and these polinomial are now just the PO in single variable which is nice we can continue from here on only in single varable so we do this again another de composition again I'll just show F0 but fub1 is will go the same decomposition

so in F0 we have a similar decomposition this time we need to take a point and it's antipodal point if if as you can see above we decompose it into decompose F0 into two. with F0 and f01 which is again the same as even and odd parts so this time it's almost exactly the yeah it's the same even all parts only in a bit different basis we show later but it's taking even odd coefficients and splitting them so again we will take these two points and their we take their average and anti average and split it to left and right like this their average is a six as you

can see and the ENT average is- one over the the point B so this way we can decompose it and now it's a bit weird to see but this polinomial is a has a symmetry so we only need two to represent as two points in a smaller domain the details are details but uh basically once we take out the domain we get two small pols on twice less points start with one polinomial with four values get the composition decomposed

pols each on two values and we can continue with this decomposition again to uh take this polinomial that we have two values on it and going to compose it into two pols of size one which is a just a constants so let's go over the en DEC composition and see what we actually did we started with the fxy we decomposed it in two pols f ofx plus yf1 decomposed each one into again even and odd and each one of these decomposed again H so what have we got this kind of a polinomial if we expand the terms a

bit basically get this representation as a polinomial with a different bases this is the free term this uh multiplies 2x^2 - 1 instead of x2 in the uh line case but this is still a polinomial of degree at most 3 in X and and one at y h yeah and substituting the values you just got and this is the start of the polinomial so again simple fft barlies the same bar flies as in a regular fft TW factors are different the Y and X values and we got the this value so this is the fft and

Fry is almost the same in Fry you just take the even all parts and actually combine them and with a random L combination all right so that was the example uh okay I think unless you have some ending notes it's time for a Q&A do you love me too uh great presentation thank you I was wondering when breaking down the uh I think it was the third decomposition

there was an operation where the six moved 90° I think on that slide if you go back next SL next slide yeah a couple more yeah here to here right I'm sorry the last slide here so where I'm I think it's 25 over two and six how do we make it so that the de composition makes six and 25 over2 opposite it's 15 over two 15 how do we make what can you repeat so in the next slide uh the decomposition shows yeah six on the opposite side of ccle yeah I mean if you take this polom and you put inside you know you take F0

at 2x^2 - 1 what 2x^2 - 1 actually does is does a doubling of the point so this poal when I put in a this point it actually first doubles and Dev on the next polinomial and this one it doubles and goes to the same point and and get this polinomial so This doubling actually does the repetition basically again so so if we had this point we start with this point and then doubled we got this or if we started with h this this point and then doubled we got this again okay gotcha thank you very much sure hey pass the

microphone hi good talk thanks um how does it compare to doing EC fft over M31 um you can also do e fft over M31 there are curves for that H the difference is a lot of things become a lot simpler here first you use pooms and not rational functions and also the it's easier to uh choose your domains I think and do you want to add something yeah I mean you're right efficiency is the same there are some features uh just the way how the ecfd does proves for sake of Suess I suppose

though it's even an a pager uh so we can do something it's just a very subtle technical feature that uh the circle is globally Isom more fre to the projective line I know that you understand that so and uh and therefore you can carry over a lot of explicit wrestles for read Solomon codes over to the circuit and that helps that we can do batch step fry directly over the curve itself so the way we commit here is even much more we used in the Univar regular case so so so we

extrapolate to some CET domain double the size say and we commit to it and we do the by value in the ECF if did have a workaround not to work explicitly on that elliptic curve because the elliptic curve is not isomorphic has not a global parameterization and things would get much more difficult just technically I believe it's the wrel are still valid and possible but technically it becomes much more difficult over the elliptic curve so this is one extra feature and this exra feature helps us to even work in some configuration of the Starks which don't Target zero knowledge where we take the trace domain and just extrapolate to another

call set of it which is just let's say the complimenting caret so the both together are a subgroup of double the size and this especially this situation would be hard to prove over the EC fft so short story a slight technical Advantage um so so these points are making a subgroup right they what like like the point that you're doing fft over them like the domain points yeah yeah are there the a minus A and B this one yeah what about so so and this 2x² minus one is the basically parel to

addition formula ontic careas right yeah it comes from the doubling formula you can think about it as a complex element if you take a plus IB squar you get like a a a s minus a something which is also like it's the same as cosine of double angle get cosine double angle is 2 cosine s - one so it's the same here you get the same thing um okay so so I'm just wondering like what what is what what is the fundamental that the C is not eliptic a basically why is is genus why this genus zero right and eptic is genus one like um what is the

fundamental different between the groups like um the coordinate ring that was on the on the last slide you talk about the where the polinomial actually come from before the quotient ring where the the quotient of the so so the the the place the polinomial pxy come from fxy FX y divided by the like mod the equation of the circle before before before in the previous slides in slides oh okay the slid are not there are not here yeah this is like the poal space take just by Pol and quotient by x² + y^ 2 -

1 the formula you will have to take a pol modules the the the EC curve on EC and you have there another group operation which is the so so this is the ring or that that was it yeah okay backward I think that one no no after after yeah here here okay so this is a ring right it's not a field right it's a poal ring and then and and then if you take the C the you add the denominator then you get the field but but you say you never hit a you never hit a rational function right yeah yeah I mean uh one thing just the classical regular case you know you get

only get pols up to some degree pound bound some strict degree bound it's with Solomon code right it's already also not a field so the thing here is looking at the Circle in the most natural way involves two coordinates X and Y and therefore just if you write down pols there there are in two variables but it's still univariate in some because it's a it's it's a linear one-dimensional thing and the relation imposed on a circle it's that so algebraically it means you take the unrestricted polinomial ring in two variables of arbitrary High degree and so on and then uh you you you factor by the relation given over the circle

that's the ideal the round brackets so it's still a ring it's a ring of uh the ffd produces An Elegant Subspace of that of of these pols also with some degree bound and therefore we can argue simple like so this degree bound is very important to have a good a code with good distance yeah yeah I understand um the problem comes with the cfd is that when you apply the group operation on the point of the fft Point like the doubling exactly but here you never get into that right the point is exactly so you could the short answer is given the

representation of the circle as an aine curve in the plane the rotation group is an aine group therefore everything you get by it is polom the complete picture would be look at the projective closure and that means you have only PS at the points at Infinity the funny thing is I had a picture here uh but I'm not going to find it cuz I'm going to lose time and I don't want to make delays here but if you look at this circle curve in a projective closure over the even a degree 2 extension is good enough uh it looks like the Ron sphere you have two

poles actually two points at Infinity this was in the beginning very much Contra inuitive uh and these are fixed points under the rotation action these are the good points to choose your PO this is thank you very much if you have more question I guess you guys will still be around but thank you very much [Applause]