ZK12: Nova-style folding over lattices: from Mova to folding STARKs - Albert Garreta

Transcript

[Music] okay so thank you for the introduction it's a pleasure to be here and uh present the research we've been doing at nethermind research so I will talk about folding so let's start with some context so let's take a relation R and let's see what folding is about so R consists of pairs xw and X is an instant W is a we and a folding scheme is an interactive protocol between a prover and a verifier where the prover has two instance witness Pur X1 W1 X2 W2 and the verifier has the instances all right and then the

pr and verifier interacts so as to create a new instance witness per X3 W3 with the following key property if the new instance witness pair is in the relation then the initial two instance witness pairs are in the relation except with NE negligible probability okay so basically take away folding in an N shell is folding is a an interactive method that allows to reduce the task of proving two instance witness pairs to proving one instance uh one instance witness pair and yeah so in all folding schemes commitments are crucial and actually we only consider relations where the

instance contains a commitment to the witness so really here when I write XI wi I really mean that XI the instance has two parts which is the real instance and then a commitment to the witness okay so we always deal with this type of relations and you can always given any relation transform it into this type of relation so really a folding scheme takes two instance witness pair where the witness is committed and gives you a new instance witness pair with a commitment to the witness and usually in most cases the commitment has to be homomorphic which means that the commitment to a sum of witnesses is the sum of the commitments all right so for those of

you who have never seen a folding scheme here is how it works if you look at it from 5,000 kilom uh distance so take two instance witness purs that we want to fold so as I said the prover knows everything knows the w NES and the instances the verifier only knows the the instances and now Pro and verifier exchange messages for a while eventually the verifier samples a random message a random challenge Alpha and then the new instance winess per is output and it has the following form the new instance is a linear combination of the initial two instances using the randomness Alpha and the new witness is a linear combination

of the previous two witnesses and yeah okay so but the verifier has to obtain the commitment to the to the witness and here here is where the amorphicity of the commitment comes into play for the verifier to compute the commitment to the new witness we use the property of homomorphic we use this formula in here and this this allows the verifier to to compute this commitment because the verifier knows these two commitments so this is folding from 5,000 km away almost all folding commitments work this way and this is all you need to know for this talk except in the end in the end

it gets a bit more technical but it's only in the end okay so usually the commitment scheme is the is a p and or GG scheme for example Nova hypernova protostar Proto Galaxy and along Etc use um Pon based scheme this scheme has some inconveniences one is that you are required to live in a big field so your your Witnesses have to be have to live in big fields uh of at least two and 250 250 bits and commitment can become really expensive especially if the vector has large entries if the vector has arbitrarily sized entries commitments

are are these commitments are extremely expensive and it's also a headache and conceptually very complicated and also comput Al complicated to recurse over so it is hard that proving that for example a folding was done correctly because you have to arithmetization were were performed correctly and yeah so this is kind an engineering headache and a computational problem also and also one something that happens if you are using commitments that are better or kcg scheme uh kcg the kcg PCS is that you are then kind of bound to

use a kcg based Nar like the the original plon but how about folding and using Starks so first of all let's describe what I mean by Stark Loosely I by Star by Stark I mean a a snar that uses a code that is code based so uses some kind of code for its commitments and then it commits to these codes with Merkel trees and maybe it's easier to just give an example so you can think of e Stark which is by E Stark I mean the original Stark where Stark protocol plunky to three bu RIS zero

Etc and a very good property of this uh schemes is that you can configure them on small fields for example goldilux which has 64 bits baby bear 32 M31 which has 32 maybe 31 bits 32 bits but roughly this number of bits uh this is really good because first these primes have certain properties that allow to Pro to to build smaller arithmetization of computations and second computations overall are cheaper because field elements are never very large here if you take the inverse of a field element the inverse in baby bear for example will have 32 bits instead of 250 bits if

you are working on a large field because you you are bound to use electric curves so that's very nice but if we want to use the scheme the folding scheme from SE from 5,000 kilm away I described previously we run into problems the first problem is that Merkel trees are not homomorphic and we cannot just change it for some homomorphic scheme that works on elliptic curves because there's no secure elliptic curves that use small fields and also depending on how you do folding on Starks it might not be worth it so now I will explore this last point and I will come to the other points

later so let's see what first let's see an anatomy of a FR based star which is uh all of the examples I mentioned before so a FR Bas tar proceeds as follows so first you compute the trace or if you want the values the wire values of the circuit then you encode the trace which means that you take the trace columns you interpolate them to create pols via an inverse fft and then you evaluate those pols on a larger domain via an fft this is called Computing the low degree extension of the trace and then you commit to the low degree extension with a Merkle tree commitment and then there's some extra

things that happen there's you compute some quotients commit to the quotients and then apply for so and um in a talk at SBC this summer alason gave a breakdown of this cost the TR force2 uh still proving uh Blake has computations the trace generation cost 46% of the whole process Computing the low degree extension cost 28% Merkel tree around 13% and the rest 133% okay and yeah so here there's a there's a remark the Merkel Tre uses the Blake hash in this case if you are

interested in using recursion or folding and if you want to use folding you you are in a setting where you are probably interested in recursion if you cannot do folding so a reasonable assumption then step three becomes more expensive because you don't you probably don't want to have Blake in the whole Merle Tre you probably want uh at least to use posidon in the first level and so yeah so this is an this is one of the points I wanted to make which is that even if mer trees were homomorphic you don't want to fall here right because you don't want to compute the trace compute the low degree extension to it the Merkle tree and then fold right because what are you saving

you are saving 133% of the proof cost so what we want to do is to commit to the trace so we commit at the first step and besides removing the the cost of the second step we are also reducing a lot by a lot the the cost of the Merle Tre commitment because the Merkle three you are committing to has a larger size than your original Trace because there's this blow up factor that appears in the low degree extension computation so in the most uh in the best case well worst case for this saving is you save 50% of

the cost but if your rate is lower then you save even more and this is a difference that um our the approach I'm discussing today has with the the protocol accumulation without homomorphism where you are forced to fold at this step you are forced to encode the trace to um for for some these reasons you have you are forced to use the code the code properties um you are just forced to use read Solomon code properties okay so let's recap what what we want to do we want to commit to the trace not the low degree extension we want the scheme the folding scheme to be

compatible with Starks and this means that we want to work on over small fields we want the folded instance to be efficiently provable with a Stark and since we are working with Starks we want we want our instances to be airs or or blish instances and I'll come back to this CCS later okay so here's a framework uh take R to be the air or the blanish relation and take two instance witness paars in the in this relation so the framework abstractly is as follows the Prov commits to the trace which is the witness in this case with a

homomorphic commitment scheme we'll talk about which later then we fold somehow in a way that the folded instance belongs to r or some similar some relaxed version of R so this is the folded instance witness pair and then say we want to prove a folded instance uh then we would proceed as follows the pr would compute the low degreee extension of of W3 the folded witness and it would commit to it as usual in a stark based proof it would it computes the low degree extension and commits to it with a Merkle tree and then you prove that the commitment to W3 that's in the folded

instance and this merry commitment come from the same witness and then you finish the proof that X3 W3 is in the relation with a star you just do the fry quotienting and the Whole Fry thing so this is the the framework speaking abstractly and now how do we instantiate it so as we saw we needed a commitment scheme that is homomorphic and that it is compatible with a St field because when proving the folded instance we want to use planky to say so the candidate commitment here is the it commitment following the lead of the ltis for ltis fall paper by uh Bon and

Chen and then we need a folding scheme that folds pairs of air or blony instances into roughly air or Plage instances to deal with this we look at erors as ccss and we restrict to degree two which is it is a reasonable restriction I think that the KIRO VM uses degree two or three uh Earth and yeah then if you are in to then air or plish is roughly a relaxed R1 CS it's not exactly a relaxed R1 CS it's a relaxed R1 CS with more summons and there's the Nova scheme that folds relaxed R1 CS into relaxed R1 CS so we choose this one this way when we

are done folding we have something that's similar to an air the problem here is that there's no Nova type scheme that works over latices so our work uh the the result the work I'm presenting today is a concerns this is a design of this scheme the scheme that doesn't exist well didn't exist okay so now cry scores on latices so uh now it exists it didn't exist before okay so a catomic ring has this form it's you can if you know what a field extension is a c ring is a an

extension of a field but you don't use an irreducible polinomial you use any polinomial so you take the the the Ring of ration of the Ring of polinomial over with coefficient on a field and you cooti it by the idea Al generated by a polom this is the set of all pols of some degree and if FX is irreducible then this is just a field extension otherwise the this ring is a direct product of field extensions so a cyclotomic ring you can think of it as a direct product of field extensions and we show that it is possible to properly configure um R whatever this means so that fq is a

stark Prime field we have goldilux baby bear and the big star Prime uh from years ago M31 is work in progress but I'm pretty sure we we will deal with it and the IT commitment scheme works as follows so the parameters is just a matrix which is sample uniform yet random here we want to commit to vectors of length M and K is just a parameter that we can choose it you can think of this Kappa as being five for example so it's like five times the SI the length of the vectors the input is the vector we want

to to commit to so a vector of length M of ring elements and the the output is a commitment to the the the output is a commitment which is the Matrix multiplied by this vector and so the result is a a vector of Capa elements so think of think of five elements so before I give I go into technical details some some words about the efficiency of of this commitment scheme so let's say that fq is the goldilux field and we configure R so that R is the direct product of eight field extension of the goldilock field of the G

3 and we configure it like this because we need to guarantee that there's 128 bits of security from the module sis uh assumption and important observation is that then a vector of size to to the N can potentially be used to store eight times to to the end cells because the ring is this direct product and direct products have additions and multiplications that are component wise so they are very easy to control so you can take your trace and put cell elements in each entry here so if we commit to a V committing to a vector to

to to the N is in some sense like committing to to to the M plus three three cells and we have this bench that we run so I commitment for a vector of size 2 to the 16 which would be 2 to the 19 if we if we exploit this decomposition cost 65 milliseconds Merkel 3 for a vector of size to6 cost 14 milliseconds but Rec but here we can only commit to to to the 16 3 cells so if we compare it to committing to to the 19 Trace cells with Merkle tree with Blake we get 50

milliseconds so we got we get comparable speeds between I commitments and Merkle trees with Blake for the same number of TR cells and Blake is the fastest or one of the fastest hash functions you can choose for meral Tre Commitment if you have algebraic hashes which you might need to do if you are doing recursion then you are um the time times are much worse already in 2 to the6 you have 2 2.5 seconds commitment cost with a POS on Merkel tree okay this is just a recap of I commitment so a huge caveat of I

commitment is that it is only binding when the vector you are committing to has small norm and Norm me is the largest coefficient of an entry of the vector if you look at the entry as a polinomial uh so this introduces lots of several headaches when you want to to fold one is that recall that the folded witness is a linear combination of the initial Witnesses so there's two issues here one is that even if W1 and W2 have small Norm W3 might have might have large Norm right because you take the linear combination Norm might grow and then the commitment to W3 might not be

binding and there's another issue that is even if one doesn't happen you in your relations you want to have that the the witnesses have bounded Norm because you want to make sure that the the pro is using a binding commitment so after you do folding and you Pro you want to prove knowledge soundness your extract you should prove that the extractor gets W1 and W2 with with small norm and this is uh tricky to do and ltis fault is a scheme that okay so ltis fold is a scheme that builds a latis based version of hypernova that deals with these two

issues so ltis fold works is it's like hypernova but it extend it has extensions to deal with these two two problems okay so the way latis approaches one is the following so first the ccss are linearized as in hypernova with a S Check okay um if you don't know what a CCs is here you can just replace CCS by relaxed R1 CS hopefully you know what relax one has is and then uh what the pro what what this does is the Witnesses are decomposed into say um base two so which

wi is decomposed into W JS and the Ws have tiny norm and then they show that H WJ is a witness to a linearized CCS instance so now you have 2K linearized CCS but each in in each witness has tiny norm and now in ltis f they fold these two k linearized ccss together and you don't have this problem because you are guaranteed well you know that the Ws are have tiny norm and you choose parameters and challenges in a way that you are guaranteed that if if the pr is honest then uh when you fold

these 2K instances at these 2K Witnesses the result has a sufficiently small Norm so that's how ltis fold approaches one this is just a recap of the last slide and our approach to to one is the following so we want to do Nova style folding we don't want to linearize because if we linearize we get out of air or plony constraints and also we don't want to use Sam check because Sam Che has several issues one it can be very expensive unless you are very unless you optimize it heavily and second it is hard it it introduces overhead for when you want to do IBC

uh so what we do we is we decompose W as as in ltis F and again we can show that the new WS are witnesses for relaxed r1s relations but the problem here is that we cannot control what happens with the error terms with the norm the Norms of the error terms and we cannot commit to those because we don't know that we cannot guarantee that their Norms will be bounded we have small Norm so what we what we've realized is that in Nova you don't really need to commit to the error term because the error term is kind of implied by the witness by the the rest of the witness um so yeah we realize this while while dealing with this

problem and this summer we put a paper called MOA where we just explain this trick but on on a normal setting with elliptic curves which is called MOA later on we realized that MOA is kind of a particular case A variation of Proto Galaxy so here we could also say we follow A variation of Proto Galaxy and yeah so obstacle two yeah obstacle two I will not explain it because of time constraints but we do not in ltis fault they also approach obstacle to with um with a s check we don't use S check we we use some other

tricks uh so we end up with with a scheme that doesn't have S Check and has a constant number of rounds thanks right thank you Albert we have a couple minutes for questions so if anyone has anything thanks for the presentation um in terms of performance how do you compare against normal free recursion we haven't checked okay because even like the conversion from air and plish to CCS uh it's quite expensive as far as I well you can

always use some you you you don't really need to turn it into a CCS necessarily you can also work with a directly and introduce no overhead in in conversion thanks no more questions small questions very open question so uh what would be so you mentioned that one difference with the another work by BNS and I forgot the second course yeah exactly was that um you guys are so the difference was that the yeah your folding happens uh before the Mer tree phase before phas is there anything

else that you would like to highlight are this works similar no they they are completely different works uh so conceptually the techniques used they have nothing to do with each other and in terms of performance the difference is the the one I explained okay was that only performance remark that was only a performance remark yeah okay yeah conceptually they have nothing to do okay all right I think that's all thanks again Albert