ZK13: Laurent STARKs - Ulrich Haböck (StarkWare Industries) & Yuval Domb (Ingonyama)

Transcript

[Music] Today you and I will talk about ongoing work uh hope to have it public soon like in two week or three weeks on ISCR. Uh it's the Lauron Stark sister of the circus stark. Uh and that's what this talk going to be about. So uh yeah it's about M31 again another stark over M31 we know it beautiful for CPU fast CPU arithmetics but what's the main caveat not FFTD friendly and there's a line of work that uh makes it useful for starts though it's not FFTD

friendly the first one was the early paper of uh Daniel Lubberov uh Jacqueline Bagler and I uh which I will describe in the following slide in detail. It had its caveats. Uh mainly for those who are familiar with it, it was constraint evaluation that was not really satisfying. Uh but uh it laid the path to the circle stock. So uh that was like last summer when when when Shakabini was approaching me and say hey look we can do the ECFD circle can we? And uh yeah we investigated it and that uh accumulated in the circus dark which has

native performance though it's not an FFD friendly field thanks to this kind of novel uh or let's say this type of algebraic FFT you run over the circle which is similar to the uh to the uh elliptic curve FFT. And the third thing. Oh, nice. That's nice. I think we do it without tong go now. Nice. We can talk about identifying your keyboard. Okay.

Oh, thanks. Okay. And uh yeah, next one. uh in the row of works over M31 was actually the RC Stark, the really complex Stark of U. I I'm not sure how many are familiar with that piece of work. I to be frank largely ignored it uh for reasons because I knew that you can use harmonic FFTDs to do the circa FFTD. So I thought and I was in contact with you, well he will run into the same troubles as we did in the first work. the the the problem of constraint evaluation. So I didn't take it fully serious. Turns out finally we met at CK proof and I promised, oh it's on my list. It's on my

list. I will look at it. I will look at it this time. Really? And I did. And finally uh it's a solution. It patches the gap the first work had. Is there something like Yes. The first work had. So this one patches can be seen as the completion. It completes the path that was taken in the very first publication. uh it does so in a very elegant way and we will see that this RC stark which is yeah content of the dark surprise surprise uh with u is a nice sister of the circus stark useful so uh concretely the write up

that we're going to publish uh we formalize the tark we give it a better name we we'll call it laostark for reasons we will see in a second and more importantly describes the relation the geometry what does the lar have to do what does the RC stark have to do with the circus stark and the takeaway of it was quite surprising for me though it's not difficult I'm not saying anything is difficult here but surprising that actually it brings not just insight to see both starks working over the same manifold but it also gives practical insights in particular I will talk about two improvements ments for a that gives a circle stock more flexibility

flexibility if you learn from the la stark okay so let's start with the early approach of Jackie Daniel and my paper the rit solomman code over the circle curve so what we'd observed and I'm sure probably we were not probably the only ones but you know uh m31 q minus one is worst is two addic there's only one factor two in not even a second one one power of two but that means that uh it there does not exist a square root of runity of minus one so what you can do is introduce it like stepping from the real to the complex

numbers in calculus in define define your element that uh that that is the square root of minus one and construct the gausian inte integers and over this quadratic extension What's nice is if you look at the unit circle in the complex plane that this is exactly first of all it's a cyclic subgroup cyclic multiplicative subgroup and its order is exactly q + 1 m prime + one which is a power of two and that's nice so what you can do about that is then okay uh it's we are in the complex we can do the complex ffd but in order not to pay the price for the complex

extension we do packing uh and that leads to reasonable performance in FFTD as if it was native over the base field FQ. Uh moreover uh yeah use the FFD you interpolate by polomials. These polomials as we will see later on in further slides they will have conjugate the spectrum their list of coefficients will have certain symmetries and these symmetries are useful to further improve because FFTD is just one part you pay when you go to an extension field the other part is commit. So uh the key observation in early work was although let me step back

for a second. So we interpolate by polomials which have complex coefficients but they have certain symmetry uh that if we evaluate over a co set of the subgroup h where we started from then these values are almost real again. So this is the coet evaluation. Uh we just need one factor one normalization which depends on the shift factor of the coet to make it real. That means over the base field again and uh we called that back then to rectify the values the coet values one coet 8 * 8 just one factor to rectify

the entire vector of coet evaluation we called it rectified three solomon codes and we were happy with set green lights for M31 let's do the start that way but when thinking about implementation there was a caveat This kind of representation, this rectified representation, you can see P of a Z is if you just bring this to the other side, you can say this is something like the angle and this is uh the radius. It's something like uh polar coordinates in the complex plane. And uh that's good polar coordinates for multiplication. It's also okay for addition if they have the same angle.

But if not then you leave uh you leave uh the realm of rectifiable representation. That means if you do constraint evaluation uh you sooner or later end up with complex representation because you cannot uh efficiently uh represent it anymore over an entire cause in a rectified manner. And that's a caveat which is nasty. Maybe not a showstopper but in the end uh it let's say it uh the enthusiasm about this approach declined. Okay. But then there was the circus stock and so on. you know this

story. Uh and then comes you last autumn and you say wait I mean this rectification thing look at this just view it as the nature when you evaluate a Lo polomial what's a polomial it's just like a polomial but now we we we have also negative powers of c and let's say uh a lower polomial degree n goes from z to the n minus n / 2 which is the highest negative power to c to the n + n / 2. Yeah, just view it view it as la

polomials and that uh that's what's the lauron or a sea is about and it's now time for your show. Thanks Ol. Um, okay. So, quickly I'll show you uh what the Lauron Starks are. Um, I'll try and tell a story a bit of of how I got to it. Um, so they're actually a simpler stack over M31. They've got the regular FFT. Um IOP is nearly the same as you will see um just with with these uh new Lauron polomials and then fry and all you know uh new types of fry

stir and we're um they're very very similar to uh what you're already uh used to and it's nearly as performant um we will see that as well. So if we look at uh I mean these two polomials they're the same that the first one is is basically just a luron polomial uh of degree n okay and uh we take coefficients that are conjugate symmetric the middle coefficient is real um if we take that over the circle so we set z to be um right um exponent of of i theta then we see that this polomial.

It's the same polomial. We can uh actually just manipulate it a bit and then we get to these trigonometric functions um where all the coefficients here are just the real parts of the uh complex coefficients and that's why the valuations are always real. It's an n plus1 dimensions polomial. Um it's real valued over the unit circle. when you get off the unit circle it's defined but it's not real valued um and this will skip for now um now that that uh space of of luron polomials of the real ones we call ln the n plus dimens n plus1 dimensional

space and we want to look at another space a subspace of that space an n- dimensional subspace where the edge coefficient right the n /2 are actually equal n /2 and minus n /2 and obviously if they're equal and conjugate symmetric then you realize that they need to be real as well um and and this is how this was my initial thinking so so this is the story you take um just a sequence of of of length n and you do the fft of it or or the the discrete 4year transform of it here I took n equals Um, and you straight away see this

symmetry, right? But, but there is like one annoying uh coefficient, the first one that that seems to be out of place. So, what do you actually do with it? And I was thinking, how do you actually do like a lowderee extension of this thing so that it stays real? Um well when you think about it because this is a FIA transform you're over the unit circle you can actually just uh do these periodic extensions and actually um right it doesn't matter if I take like z to the power 4 it's the same as z to the power minus 4 and then we just define a different set of the same coefficients that are equivalent over

the unit circle and notice Notice that we take also the middle coefficient and we split it into two. Now we get this nice symmetry and that's actually the Lauren polomial. Okay. So you see that it spans n plus one coefficients but it's actually an n dimensional space. The the coefficient um the edge coefficient is really uh um like the same degree of freedom. Um and this straight away leads to the way that we do lowderee extension. So if you look at the top uh within this dotted square that's the result that you will get from an inverse uh dft. And

then if you look at the solid lines that's how you would look at it as a lower polomial. And then that strays away straight away says how do we uh zero pet it? We actually um push everything apart. the zeros go on the two edges of the um the rain polomial and then we can straight away do a a DFT and we'll get the new uh uh real evaluations of the extended uh uh code. Okay. Now quickly everything from now works the same just with our own polomials. So um if we look at the n plus1 space, the n plus1 space is is uh has closure for

addition and also for multiplication with the the the usual uh times 2 uh uh length extension but that also works for the n dimensional space. Um vanishing polomial we have the usual z to the n minus one but we need to actually shift it. And if you note we also uh need to multiply it by it's actually imaginary. So that it's it's actually in the n plus one space. It's not in the in the in the subspace. Um selector polomials are simple. Uh all different types of air constraints uh uh like uh single point ones uh out of domain rep it all works

out of the box the same as you're used to. um fry, stir, were uh it really depends on how many coefficients we have. If if we're doing quotients, then all we need to do is just shift the polomial uh by n /2. So now we have a usual univariate polomial and that's the reduction. Now we can do the usual fry. If we have n plus1 coefficients then we do this trick where we uh shift it and then get rid of the constant uh uh uh coefficient. So in practice uh for the fiery transform right to get it fast we

do packing and we do this split radics uh uh implementation uh and then the cost is nearly the same as what we're used to. It's actually n /2 uh login multiplications and instead of uh uh n log two additions it's 1 and a half uh n log two additions. So it's very close to the circle f and it's close actually to to the usual entity that you're used to. Um so now I'm going to hand it back to give you the geometric view. Okay.

So we saw I mean for those who are familiar with the circle stock uh they probably noticed already some similarities in the lauron stock like the FFT space the image of the FFT is n dimensional as large as the domain but the entire space the natural space uh of LA poloms of the same degree is one more right that happens also in the circle start and uh also the removal of that one coefficient that we had uh in order to apply were uh that's also something that occurs in the in in the quotient decomposition of the circle st and so on but okay forget about this for a second

the geometric view so let's let's go back to the circle that's how it looks like over M31 you know in the plane it's it's a planner it's a planner uh a fine curve we can Yeah, we can touch it. We know it how it works. Yeah. But the better view on the circle is actually to that that's like always in algebraic geometry. You go to from the real numbers in in analysis to the complex number to to the algebraic completion. And uh there you see the true characteristic of the manifold. And when you go when you step over to the quadratic uh the to the complex extension actually the circle curve

looks like like this. It's a bit a cheat of that picture because you know the formula is x^2 + y^2 equal to 1. So we are still in in the two-dimensional complex or fourdimensional real space. We have a surface two-dimensional surface in the fourdimensional real space. But it turns out that actually you can isomorphically map it to really the unit sphere in the three-dimensional space. So the point is uh whereas the ordinary circle there are no points at infinity. But if you go over if you see the complete picture of a complex numbers there are two points at infinity. uh one is that pole and the

other one will be that pole in that let's say in that model okay uh and the way you typically achieve it the canonical way that's also used in the in the circus stock paper it's not in the invention of the circus stock just used the canonical way to achieve that image is uh look just first of all look just at the circle in the plane fix one center of your stereographic projection. Then take any other point, take the line that uh is spent by the two and uh see where it intersects a fixed plane that you choose for the projection. And in

that way, if you move now that second point along the circle, you see that you will end up you you will re you will get the real line, right? you will get a line in the plane and also if you take now uh if you if you now move out oh let's say let's let's rewind so so that's that's actually it looks like this in a formula if if you choose specific normalization it looks like a very simple fractional expression for that stereographic projection and that's that that expression makes sense in the extension of the four in the fourdimensional real space even if you don't understand can't think about four dimensions, you know,

and the and the thing is if you look at the image then uh you you will see that the two points at infinity they will be mapped to plus and minus imaginary unit and if what's not in that picture if you think about the orbits of a point on on on the under under rotation under the rotation group that keeps the two points at infinity fixed uh you will see also circles here. They're not concentric but they're circles. And the thing is you just see that parameterization that complex the one-dimensional description of the curve and it reminds you on the stereographic projection of a classical 3 in the 3D

space that surface. So that is how you obtain that picture that I was said in the beginning is a bit cheating right. So but that's a good way to think about the circle curve. That is where the circle stark happens. And okay, funny thing is there are different ways to parameterize the circle curve. And it turns out actually if you if you use the trivial embedding that use the very first work that means uh you just have the real description of the complex unit circle. You take two points of the real real real unit circle uh and map it to x plus minus i y.

That's not a complex unit circle. that this this just as as an algebraic mapping extends also to the full circle curve and in that view it's just a different stereographic projection. You choose the center to be not something that is on the real curve as before. You now choose it here one of the poles. And what happens then? Fix that as a center. Choose one point of the real circle curve that stays fixed because it's already if you choose now the XY plane as the projection plane. So that stays fixed.

uh and everything that is in the lower half of of of that uh what's the right word of the sphere is mapped at the inner of the curve that the other pole is mapped to zero and the more you the the other the upper half of it is mapped to the outside in extreme value if you approach now the center you get infinity of the projective line here we get the infinity. So the funny thing is here the two points of the circle curve the two exceptional points at infinity are mapped now to zero and this is a different infinity.

This is now the projective complex plane. Okay. So why is that interesting to look at where these exceptional points at infinity go to? uh because zero and infinity let's just go to the LA polomial powers of one over C and powers of ordinary Z to the one where do they have poles C to the one has only pole at infinity one over C only pole at zero so zero and infinity that's the defining pole set for those from algebraic geometry that's the that's the support of the divisor for the reman rock space so that's the defining pole set for la polomials likewise is the regular circle

polomials. They only have poles at infinity at the two points of infinity. This is the defining set for the reg for the circle polomials. And that means that this specific identification this other type of stereographic projection this maps the laural poly on the circle polies. It's even degree per serving that means lor polomial of degree n are mapped to a circle polomial of degree n / two and uh the fft space which was named I think still ln plus in in inub's part uh that corresponds to what is that's why we

named it ln plus there because in the circle in the circle uh uh over the circle curve we deal with two spaces essentially ln plus ln plus and ln minus one is ln minus is the circle fd image and ln plus is just the rotated part of it. So the thing is the fft space of the harmonic regular fft equals a rotated circle fft space. Okay let's wrap it up. So first of all, Lar Stark is a circus stark just with a different FFT and therefore a different fry. So what's what's what's the

takeaway here? We see that we can I mean beside it's a simpler and has a stark and has reasonable performance. We can improve uh that caveat of the harmonic FFTD that overhead in addition by just implementing using the sock for faster lower coding. So it can be improved costs of course a bit of work. the on the other hand and that's the surprising thing to me uh is that the lon representation is very interesting for the circle stock itself uh in particular these their blackbox reduction you just make a lauron polomial into a regular polomial and

then you run fry or you run stir or you run were it doesn't matter that means you can use blackbox the security analysis of it you don't have to p pull it over to the circle which is which is possible. We know it works but it's it still works well it done. So you have it you can immediately apply sternware out of the box. That's nice. Uh the other thing is that uh stew is a flat uh uses flat airs that means no transitional constraints from row to row. It's it's the design principle most modern CKVM uh implementation go along like OpenVM or binius. So uh so over the circle it's surprisingly difficult to come up with

the analog on the uni varied sum check that doesn't work with running sums but with polinomial it's easy again so you can pull it over to the circle or arbitrary set interpolation. So like in data availability sample you have a non group structured set you want to have the interpolating polomial over it. That's to be fast here. You need something like the monomial basis which behaves nicely under under the derivative with the circle basis doesn't. Again the lauron representation of circle polies is a good solution here. Okay, that's essentially it.