Circle STARKs - Ulrich Habock

Transcript

hi everyone uh very nice to have you this week we are very excited to have Irish hok from polygon Labs presenting his work on cish has been working uh in the domain of DK for quite a while he has worked on mtiv lups on Fry on uh a bit on JK on richon K and he just publish with his Coors a really interesting qu C STS I'm not going to give any spoilers but it's definitely worse being here today so thanks a lot sir for giving this presentation and the floor is yours thanks Rafael so uh as Rafael said so we're going to talk about joint work

uh with David levit and Jaa papini from starware Circle starts so uh before I start with circle starts let's let's just uh go through let's say the path that led does in the end to Circle Starks so regular Starks so I mean most Starks is what what I understand a regular Stark is just a classical fft based Stark so you have you have a uh fft friendly field uh so it's depicted here as the line the multiplicative group without the zero that's uh smooth and you so you have you

have sort of fast encoding and and the objects uh you so I mean everybody knows regular your witness data is is encoded into Univar polom and then you have the classical polinomial IOP constructions on top of it so that's that that's what I say consider a regular Stark and then there is the elliptic curve Stark or E ffd Stark from benas d swasti and davit uh which just applies actually to any arbitrarily even nons smooth Prime P so

what they do is uh they just consider different underlying space of the star not the line or the multiplicative subgroup you just consider a curved uh an elliptic curve as the basis considering that this elliptic curve in group structure is sufficiently smooth you place your tra you choose your smooth subgroup of the curve you place your data on it uh and encode into well in this case it's not polom uh they are more rational functions here over that curve so the thing is uh at least from my team and I also saw other team that there seems to be a misconception about the EC fft Stark so it's it's as efficient so you can run it over any p

in terms of operations even from the the way that the ffd works is as efficient as a classical regular Stark uh it just unlocks for NP the problem with maybe that's the reason why there is some misconceptions about the EC star in the in the CK Community it's I mean a they're huge 80 Pages it's very complicated to go through them I personally have to admit he do it yet in all details so the thing is always like can we do a simpler constructions construction and that leads us exactly to a circle uh so the point is a circle start is exactly it's like pulling over the strategy we have

over the elliptic curve over a much simpler curve uh and that's the unit circle so the unit circle uh the so the unit circle was already used back then by if I remember correctly uh by Yeah by by the M read Solomon CES over a circle group paper by Danielle Jackie and me and uh but this construction was already quite simple but it has some caveats so the point of the circle star is to to have really direct translation of the EC fft Stark to a much simpler curve a curve that everybody can understand because it's the quadratic uh

it's a quadratic curve it's the unit circle it's a group as you can see so uh so so the unit is here you just have angular addition or or if you want to consider it in the spirit of complex numbers uh you just multiply complex numbers of the Moon Unit Circle that's the grou here and the reason for why this curve is interesting is the or the p+1 smooth case is interesting is that it applies to the msen 31 uh which is probably amongst this Prime Fields one of the best choices for efficient arithmetics on standard CPU architectures okay so that's the circus

star and how it's built it's like a regular St so actually there's not so much different on High level is you could you could say it's the same you know you you have your uh you have your circle you place the circle turns out to be smooth uh so and and you uh you you place your Trace domain as a essentially as a subgroup of the circle then uh you you you use you use the circle ffd which I will discuss in more detail later to encode this data you place on the trace the trace columns into and again that's the nice thing and it's a difference to the to the elliptic curve situation now what you obtain are

polinomial again they B varat and they're over the circle that's depicted here I cannot highlight on the slide uh sorry that the the so so there this is depicted here by the relation given by the circuit so x s + y^ S is one so so you encode trace the trace columns into B vared pols uh and yeah then the usual IOP construction so so you cons simple so you take you sample a random uh a random point the underlying VAR is is the circle curve you simple random point and test your polinomial ident is at the random Point uh for soundness of course you typically need to move

over to that curve that uh over an extension field instead of over the base field but that's that's not a problem here so okay so the main ingredients as already indicated are Circle fft that's needed for efficient encoding for Pol efficient polinomial arithmetics and the second thing and very much related because if typically if you have one uh concept like in fast encoder uh fast fft tree so to speak then it's also clear how to build from it uh a a loic r test which is circle fry in this in this situation so uh because they are so much

related and I would say the core and most important construction is the fft anyway I will now Focus only on the Circ fft so just to recall the picture we have the circle we have some smooth subgroup o over it Place some data on it and now we want to have a fast interpolation by B by bed pols okay so first of all and that's probably the most one of the subtle things at least for me that was when I was approaching a circle fft because I'm coming rather from the classical fft

theories so harmonic ffds uh so it it's an algebraic fft like the additive fft uh that works on on subspaces over binary fields and so it's not an harmonic fft nevertheless uh it's a it's it's the way it's built is very much relies very much on group structure of the underlying domain and uh so I will come back to that uh later so so and and there's another thing which makes it actually quite different to the additive fft the other fft can be seen the

general construction I'm just now hand waving because I can't edit on the slide so you so so typically the short story is you just need a chain of two to one projections 2: one mappings you start with a first domain and they have 2 to one mapping to domain half the size and so on and on top of it you just need something that distinguishes points along the fibers once you have it and the whole additive ffd can be seen as this construction then uh you can bootstrap an FD algorithm from it can and uh difference of the circle ffd and the EES ffd is that it's just these 2: one mappings are not s they're more let's

say they're more subtle to be constructed so maybe better if I rewind here this was already far to complicated expect so so let's let's go back uh and consider the classical regular fft uh you can consider it as the old and even decomposition fft so the the main a core a core uh the core element of it is that you have the the group doubling map or the squaring map in the multiplicative lingo which lets the end the trace to start with the sub group collapse to one of half the size and then again collapse one of qu the size so that's that's the same also for the Su ffd uh but you need

to work not just with uh the the group squaring map this endomorphism also with another endomorphism which is not 2 to one on in the in the in in in its proper it doesn't collapse so uh and okay so so that that's the main difference algebraic F oft it's uh nevertheless it uses a lot of group structure behind it uh and it works with two endomorphisms the group squaring and the inverse map these two commute actually because both are power maps and the domains you choose here there what we call standard position coets so that

are these are coets of the subgroup which are invariant under the invers man moreover there's no fix point you could also choose the group itself the group position itself as something that is invariant but then you would have exactly the two fixed points of the inverse map which is like the identity element or the curses now and its opposite point on the circle so that wouldn't be a standard position CA it so standard position CA it you have exactly this picture so each of these involution orbits are consist of two points or in other words if you consider the quotient Space by the

action of the involution you get uh you get uh you get here something that is consist exactly of half the points you have we have okay so we have exactly one two three four different orbits instead of eight points of of the initial domains okay uh so and already hand W indicated the general principle you have typically for ALB you have a chain of 2 to1 maps so here the chain goes as follows uh so you start with your indust standard position CET

and then you you you consider its quotient with respect to the to the inverse map which is exactly of half the size points and the funny thing is because quotient I mean because uh the group doubling map the endomorphism and the inverse map the commute therefore you can you have a unique understanding unique definition of the group doubling also on the quotient here uh so so that's the same I used I misuse the same uh P for door here above it's the group doubling here it's something like projection of the group doubling onto the question so but uh and yeah so so

now so you first consider the qution space half the size and then uh repeatedly apply the the group doubling map which again halves these caution spaces until you end up with a trible space so that's that's essentially chain of two to one maps to get here so uh and and what you do is like the classical uh General concept you decompose into OD and even function with respect in a proper notion similar like we used to uh so let me let me try to explain that a bit better here so so so given this standard position CET here yeah so the first step is is

actually you can consider you know because that already was indicated in the picture before uh that a good you can consider a model of the quotient space with respect to the involution being in on the x- axis itself so in the first step you decompose sorry you decompose the function into odd and even with respect to uh to the involution what's odd what's even it's better start it's invariant with respect to Evolution so you take the even part of f which is f of XY plus F at some point and its involuted Point its inverse Point half

that's invariant under the involution because you took the average over the orbit and uh for for the odd part you just take the difference uh and then if you take as your standard uh representative of the function the the function y itself you again get because this is odd this alternates under the action of the involution Y also alternates so this quotient is again uh something that is uh constant over orbits of the involution and uh so in other words it only depends on X so so the first step you just deom you actually decompose the b variate polom or or say you would

decompose a b variate polinomial two univarate pols F0 of X and FS1 of X okay and the other steps they are quite uh with respect to uh to the group doubling me on the quotient space so and group doubling on the quotient space actually reads like this it's the 2x^ s time minus one so it's easy to see that so I'm I'm not going through it so so so and that means means again group doubling plus uh like in a non projected domains p and its opposite points they are really

mapped to the same value here it's like uh GX and minus X we are mapped to the same value still you know and and what you do is again you decompose into an even part here this is even with respect to to uh the RO the the with respect to multiplication by minus one which really Maps one point to its partner uh in the fiber with the same value and and here in an odd one and uh you you X itself is also alternating it's odd with respect to J with the plus minus map here uh so so you just take

the quotient of it so the decomposition is very much the same as we are used to in in in in in the regular fft in the multiplicative fft it's just a bit more uh different here that that that it's not x squ that you have here as as the projection mapping so these are the other steps so so so essentially it's it's very much very close to the regular fft and and the point is in code it's it's it's really essentially the same one could say it's a bit too simplified but you can really do an inplace modification butterfly network uh that is very very similar to

koui uh the the in in terms of arithmetic costs uh uh it's the same like in regular fft and uh and uh there is some there are some extra technicalities because in Starks one often likes to have a coret fft also circle fft is restricted to standard position coret so what would be the other coret I mean there are possibilities to extrapolate to other cets and to maintain the usual uh way of thinking here like like we used to in regular Starks but uh it's

more efficient that from from point of efficiency the better choic is here to to generalize from standard position caet domains to something which is here the left here to something which which is then twin caet a twin coet domain so twin coet domain are now two orbits or two subgroups of half the size nevertheless one is mapped to they're mapped on one one onto each other by uh uh by by the involution by the investment you know so uh you can see a standard position calls it also as a special case of a twin coet here we have the two coets half the size the blue coet is is mapped on the

red coet under Evolution but more generally you can now uh break the groups the the large group structure uh so and it can be so the point is what I want to say here is there is an analog of the coet ffd it's a bit more abstract in the way domains look like in practice when you write everything down in codee it's very much uh very similar because it's all just about how you how you index the domains so okay so Circ FD essentially like the regular fft there are some technicalities about the in indexing to to get a generalized cor Set uh

fft okay uh oh this a quite old benchmark marks uh I I would have needed to ask Shaka he already optimized uh his fft for the St for the St for Star Pro uh we polygon a bit slower in development here so we don't have yet uh uh really optimized the circuit ffd but this was from back then so typically one would expect this so so baby bear is a quite cool is a quite cool 32-bit uh uh Prime over which you can run all the classical reg regular Starks so uh M31 is just faster in field arithmetics and the and it depends a bit

little bit on which uh which uh which CPU you architecture you take so so you see uh so here here we've taken Intel and if you if if you consider abx2 uh Vector instruction set there you essentially see the same ratio of improvement you you see on the multiplication uh so that's just a rough uh picture here what to expect and I think uh maybe Shaka did even improve on that not sure but uh that's something what to expect so you unlock M31 for which is per se not ffd friendly to do the whole

Stark over it uh you enjoy the benefits of M31 it's not like you you enter a different League baby bear Stark is fast but this Stark is like at least you know ffd is like 1.4 larger the whole Trace computations whenever use multiplication you're like 1.4 but faster so uh it should pay off in the end in particular if you use hash function for commit which are arithmetic ones not a different leak yet still still uh an improvement you want to have uh in particular given the fact that the Implement implementation of the circle star it's not like a completely

different Paradigm in in the way the code structure looks like than a regular star okay so not sure if this quick uh going over it was a bit too fast and helped something so a lot of details I was just not mentioning so uh if you're interested the the paper itself I hope it's readable uh at least for me uh you it is much simpler than the ecfd because you don't need any algebraic geometry that's the fine thing so so you you understand the circle the circle uh you can even learn terms of algebraic geometry it can

be even for me it's like was like a learning step towards ECF understanding the cfd because the circle is is very easy to understand not like an elliptic curve and even you can practice all the Notions the elementary Notions of algebraic geometry on that circum much easier like like as an exercise okay so that was it probably a bit fast faster than expected thanks for this presentation um I don't see any questions yet on the chat so I will I will ask a couple and if anyone wants please feel free to ask uh so in the

bench B that you just showed uh it was single threading and so you say that you had uh better benchmarks and more recent benchmarks I was just wondering because you're saying that U the CFT algorithm is close to K whether they sorry I wanted to confirm rather than ask actually that you can paralyze the algorithm and so you could have much better results to begin with yeah yeah I mean uh Shaka has already implemented a memory efficient uh a cash friendly version of it so that it you just didn't have it back then time so the timings we have in the in in in in the appending of the Circle St paper back then these timings were just that

they show you know uh for versus baby bear in in the multi-threaded setting uh they were equal because memory in both mation that we used to compare the both memory bottleneck so but it's absolutely no problem you know it's it's very much the same the same structure you have even in the in place modification butterfly networ so so you can make it cash friendly yeah and and you see the simil then you see again M31 the benefit of M31 over baby bear yeah yeah uh my other question was actually a bit about uh M31 uh so in snar and stack recently we've seen uh conversions in research for

using smaller and smaller Fields uh and so CLE stack is contributing to that uh do you think that we're going to do you think that M Prime is going to be the field that everyone is going to converge to uh why I'm seeing that is because being part of uh a couple of projects um I can see that uh changing of of uh of protocol changing of prime is a discussion that often uh that often uh happens but is quite difficult for engineers because it mean that you have to change uh big chunk of your back end you have to reoptimize everything and seeing so many papers going through

small primes it could be a uh a God bless uh it could be great uh for engineering for crypto Engineers uh for maintenance but also for for the evolution of the ZK stack yeah I'm probably one wrong person to ask here uh because as I understood you know because there are also smaller massen primes just as an example I'm I'm I'm returning to the completely different approach by ulana in a second but if it's just about prime field Starks uh they're smaller Prime uh m Prime also like

m17 uh it's more really I think it very much depends on the platform you want to optimize for it seems like at least on on on on standard CPU architectures like uh uh Apple M1 uh as well I'm not even sure if I Nam the right thing here and Intel you know on CPU architectures and possibly a lot of it also carries over to gpus uh seems like these M3 31 seems somehow to be a sweet spot uh to hit the sweet spot here uh so m17 arithmetic As I understood our Engineers wouldn't be better so even though you would have uh less embedding overhead so don't know uh

where the future will move there maybe it will in small primes maybe maybe we will stop with baby bear M31 here in Prime field uh the the question is how how how how fast in the end binary provs will be on standard CPU architectures because on Hardware given that all everything is on chip binary circuits are superior you know that's a clearcut thing uh when it comes to fpgas I think that the answer is not that easy as understood to give here uh so will be very interesting so I'm I'm I'm very excited of the work also of

like revisiting binary field Starks having Ser beding overhead which is the unique uh let's say the unique feature that the ulana guys uh brought into binary start so so that's I'm quite excited so don't know uh on software which one will be better yeah I really can't say so we will see here and uh called engineering uh or my feeling is for standardization uh Pro we probably it's it's it's a too much weid field it's probably far too early to to to hope for

standardization and therefore helping the developers not to go through the same process again and again yeah know I agree with you and thanks L for your insights uh I've worked in the past on ZK rollups I'm working on ZK VM and while before uh problems were mostly having the main problem was having a faster fire recently for the past year to I think most people have been working on Fast provs and memory efficient provs and so there two main theme at least in my mind that I can um why I see the research conversion which is a huge the use of small Prime fields and uh trying

to abandon ffts for snacks because the PO the uh L uh and yeah uh because STS have been uh using smallfield for longer uh I thought that it could be interesting to to have some insight on on this question uh but I I agree with you anization uh is not there yet so so it's it's quite nous game to predict what's going to happen in the future um I don't know much about the stack space but I know that on the stack basis uh the Z proof organization uh which is trying to standardize uh I think they started the

process about a year ago and uh it it is difficult because you you want to standardize quite different things and the research is evolving so quickly that you you have to always adapt your model to take uh the new optimizations and new schemes into account uh so yeah I I agree with you thanks a lot for answering my questions um you're welcome yeah so uh I'll give a some moments in case anyone wants to ask another questions otherwise uh I think that we can leave hello I have a question perfect hello sir thank you for the

presentation my name is Logan I'm a third year computer science student and I'm looking into trying to implement this and I was curious what your thoughts are on the biggest differences between Circle Stark and um normal Stark in terms of writing F or FR for um Circle start better question would be the better question uh for who really did implement it like uh Eliah from our team and and Shaka and others from from stock but my feeling is that the most Supple thing you have to gr here

is the indexing of uh o of twin coet domains because or non the right indexing also of which covers also right indexing for what I called standard position CET fry itself goes very much once you have the indexing it looks very much the same uh not saying it is exactly the same because in the end you have uh still you know like like with the circle FD and therefore also Circle fry the first the first step is like uh for fry would be a combination down two domains which are which are over X

alone and then uh you do something quite similar as you used to so I think in implementing the most the most Co let's the the biggest effort to be done is understanding the C ffd uh F getting getting the circle fft code done once you understood the circle fft code you understand also how to do fry and the rest is essentially quite quite the same um a bit more problematic when it come let's say a bit you you have to think in every single detail you know the H St is about much more than just encoding pooms uh and doing fry it's it's like uh

suing select the polinomial for the air uh or even the Deep the Deep single point quotients they're like like extra though though it's a simpler curve you you you have to spend some extra thoughts uh about how how how you do single point quotients de quotients uh which you probably wouldn't over the elliptic curve but I'm talking too much so long story short main different I would recommend study the ecfd understand the ecfd and then you have 80% up to 90% or you know

how to what to change in in the what to do in the implementation second thing is selectop pooms are a bit a little bit more different and the Deep quotient itself got it thank you you're welcome well uh thanks again L for this presentation and thanks everyone for attending uh I hope that you had a good time and that everyone's going to have a look

through the papers uh yeah uh thanks again Rich for for coming and uh have a good day everyone thanks for having me