Folding STARKs with the Mova folding scheme

[Music] this Friday morning so yeah I will talk about how to folding in the context of starks so let's start with the basics wait one second all right so what is folding so in folding we have a relation R relation of Interest which consists of pairs x w x is an instance or a statement of a problem and W is a witness or a solution to the problem and a folding scheme for this relation R is an interactive protocol between aover and a verifier where the prover and the verifier have two instances X1 and X2 and the prover also has two witnesses W1 W2 and they are valid Witnesses for the instances and then the pr and the verifier interact and at the end of this interaction they out they output a new instance witness per X3 W3 with this key property so this output instance witness pair is valid so it is in the relation if it is the if it is in the relation then the original two instance witness pairs are in the relation as well except with negligible probability so this is the key prop property of um of a folding scheme so basically what's going on on here is that we have two tasks we have to prove one instance witness perir and another one and we have applied an interactive argument that reduce these two tasks to a single task uh so if this folding step is very cheap then you are basically gaining um you are gaining work right you have to do less work because now you only have to prove one instance witness pair okay so commitments play a crucial role in this type of schemes at least in the modern ones and in reality in practice all instances include a commitment to the witnesses so in reality in practice we we have the instance witness Pur look like this so the instance is a true instance XI Prime and then it also includes a commitment to the witness okay so a folding and then a folding scheme looks like this we have two instance witness pair where the instance contains a commitment to the witness you fault you get a new instance WI SP okay and the commitment most of the time is homomorphic and this is a crucial point and homomorphic means that the commitment to the sum of two vectors is the sum of the commitments to the vectors okay so if you've never seen folding this is everything you need to know to follow this talk let's look at how folding looks from 5,000 kilom away so as I said in folding you have two instance witness pair of this form there's a prover and a verifier the prover knows know the instance and the witnesses the verifier knows the instances and now the exchange messages doesn't really matter what's going on here for the purposes of this talk and at the end the verifier sends a uniformly sampled Challenge and then the pr and verifier output new instance witness pair the witness is only known to the prover and crucially the new instance and the new witness is a linear combination of the initial two using the last challenge sent by the verifier so we have these formulas in here X3 equals X1 plus Alpha X2 and so on and the verifier computes the so the verifier needs to get the the whole instance right at the end of folding so it's easy for the verifier to get X3 because it knows X1 and X2 but how does the verifier get the commitment to W3 well here you can use the homomorphic property of the commitment scheme the verifier knows the commitments to W1 and W2 and because of the linear prop theomorphic property of the commitment scheme it can obtain a commitment to W3 without any interaction with the approver just by performing this this uh linear combination of the commitments so this is how folding looks from 5,000 kilm away many many folding schemes look like this okay let's discuss Comm commitments in folding schemes in more depth so usually the commitment scheme is a Pon commitment or a kcg commitment so it's a elliptic curve based commitment or some variation of p on kcg for example in Nova hypernova protostar Proto Galaxy Etc this is the commitment of choice and this commitment scheme has some inconveniences one is that here you are forced to to live in large Fields so you need fields of at least 200 than 50 bits because otherwise you don't have if you want to go lower than 250 bits there's no secure uh elliptic curves with pairings if if you need them and committing this these type of commitments can be extremely expensive if the vector has large entries and it is expensive to recurse over so usually in folding you you apply fold you do folding and then you do IVC and then you have to prove that the folding is done correctly and so on so you have to prove statements about elliptic curve operations which are quite a headache and yeah because of this setting you are kind of bound to using a kcg based Nar when to prove a folded instance right because you you are you are using large Fields you you have uh elliptic curve based commitments and so on but maybe you want to use a different proof system right so that would be that's an inconvenience okay so yeah let's say we want to use Starks to prove our folded instance our folded instance witness Pur so by Stark I loly mean a snark that uses codes and Merkel tree based commitments for example the Stark protocol from starware plun it through two on three buum R zero and so on these Protocols are configured on small fields and they are getting smaller and and smaller for example goldilux for plunky 2 baby beer for plunky 3 and M31 one for Circle Stark this is a the the attractiveness of small Fields is that well the attractive attractiveness of this field is that you you get to you get smaller arithmetization due to special properties of the primes of these fields uh you also get cheaper computations because field elements never get very large if you invert a a 32bit fi element the inverse has at most 32 bits uh um but there are some problems in the context of folding the first problem is that Merkel trees are not homomorphic so if you want to do folding you cannot you you you don't have the homomorphic commitment right away and since we are working on small fields we cannot rely on elliptic curves here and also depending on how you are going to do folding even if Merkle trees were homomorphic it might not be worth it in the context of starks and I will explain why now so let's look at the at let's look at a cost breakdown of creating St proofs and yeah let's look first at how a fry Bas star works so yeah all the proving proving systems I mentioned before work as follows so first the Prov computes the trace or the circuit values the the values in the wires of the circuit then it encodes a trace using a Nar correcting code pols and for this it interpolates The Columns of the trace and then it evaluates the tra the the polinomial on a larger domain using inverse ffts and ffts this is called Computing the low degree extension of the trace then the prover commits to this low degree extension using a Merle tree and finally there's some quotient the Prov takes some quotients and applies fry and so on okay what's the cost of all the what's the cost breakdown of all these steps I'm citing elenson from a talking at SBC this summer so the trace generation in the case of St costs 46% of the proof of the total proof cost Computing the low degree extension cost 28% Merkel trees cost about 133% and the rest also cost 13% so yeah and if we are in the context of folding if we are thinking of using folding it means that somehow we want to use raron so we are probably not using Merkel trees full of kcks or uh Shad 256 or classic hashes we are probably using Merkel trees that include some some type of uh algebraic hash in which case the third step would be much more expensive uh yeah so here here's an important observation even if the Merkel trees were homomorphic you don't want to to to do the folding with the commitments to the low degree extension of the trace because you would at each folding step you would perform this step this step and this step and you would save this this part in here and you would still need to do folding so in the absolute best case scenario you would save 13% of the total proof cost at each folding step which is not a lot so what we are trying to do here is to just commit to this Trace in here we don't want to commit to the low degree extension with Merc R we are just going to commit to the trace in the most cheap uh way possible uh yeah so this is a key difference with approaches like accumulation without homomorphism or the arc protocol from these researchers that uh from papers of these uh from this year Okay so let's recap what we want to do we want Comm we want to commit to the trace instead of the low degree extension we want the scheme to be compatible with Starks and this means that we have to work over a small field we want the folded instance to be provable in a reasonable manner with a stark and yeah so in since we want an instance to be provable with a stark here we think of instances as being erors or plish instances and we look at this as ccss R CCs is basically an R1 CS constraint um but generalized with more terms okay so here is the general framework of what we could try to do if we want to fold Starks and afterward I will talk about actual instantiations so let's say we have two instance witness pairs two two airs the framework is as follows the pro would commit to the trace not to the low degree extension of the trace so the trace the witness with a homomorphic commitment scheme okay so now we have these two instance witness pair and then somehow we would fold in a way that the folded instance is in still in an error or somewhat similar to an eror and now say that we want to prove a folded instance so we have done folding and now we want to prove the instance the folded instance witness pair so what would the pro and the verier do the pr computes the low degree extension so so we want to use Starks right to prove the folded instance and for star in if you are using star you have to encode the witness because you are going to use error correcting codes so the Prov computes the low degree extension of the folded witness W3 and commits to it with a Merkle tree like if as if it was just using a St the star protocol then the the prover proves that the commitment from the folding scheme to the folded witness is consistent with the mercal tree commitment of the low degree extension of the folded uh witness and then once this is proved the Prov can just finish the proof that the folded instance witness per is in the relation with the his favorite Stark okay so we have to keep in mind that we'll have to do this this steping here when we want to prove a folded um instance witness pair so this will inform how we choose the commitment scheme to not um make this this parting here too expensive okay so let's instantiate the framework now we need a commitment scheme that is homomorphic that is compatible with a stark field so it work it it somehow works over small fields and the candidate here is the itai commitment scheme following getting inspiration from the latis fault paper from B Chen and Dan Bonet and we need a folding scheme that folds pairs of air or blish instances into roughly erors and blish instances and the candidate approach here is if we look at as I said if we look at eror plish instances as ccss so let's say R1 CSS or relaxed R1 CSS then we can the first thing that comes to mind is Nova because Nova Falls relaxed R1 CS is into relaxed R1 CSS so this is the our candidate Nova however there's no Nova type folding scheme that works over laes so there's when it when it comes to folding over laes the only work available right now is ltis fold as far as far as I know and latis fold is a hyper hyper nova analog that works over laes but there's no Nova analog over latices so one of our main results is designing such a such such a folding scheme okay so a bit on latices and and latis fold so latis fold and many latis based schemes work over so-called cyclotomic Rings which are cyclotomic rings are basically they look like field extensions right you take a a ring of pols over a a field a finite field and quo it by an ideal generated by a polinomial however here the quotient polinomial may not be irreducible and in this Cas this means that if the polinomial is not irreducible it means that this ring splits as a direct product of several field extensions if f is irreducible then here there's just one factor and you have a g extension uh the standard field extension but if f is not irreducible then you have this direct product but in any case these rings are quite are quite nice because they are just direct products of field extensions so you could in principle and we show that you can configure R in a nice way and at the same time choosing F to be a stark Prime field so we we can choose F to be goldilux baby bear the big St St Prime and probably M31 though this is work in progress uh yeah and the I commitment scheme works on vectors of length M for elements of R and the parameters of this commitment scheme are as follows it's just a matrix sampled uniformly at random from the ring with with ring elements it commits to vectors of length M from of ring elements and the commitment is simply the The Matrix Matrix Vector multiplication a times the vector so let's discuss the efficiency of this commitment scheme first so say and this is an example configuration we can deal with we we can choose the base field to be the goldilux field which has 64 bits and we can configure R so that R splits as eight um factors and each factor is a degree 3 extension of the gold Delux field here there's an important remark on um how to work with cic rings and this is that because of this isomorphism in here this is the number theoretic trans form because of this isomorphism you can potentially store eight Trace cells in a single ring element so if you have if you want to store eight eight Trace Elements which are in the which and each element is in the field you can put each element in one of these components and then these eight elements become just one ring element so a vector of size 2 to the N with ring elements can store 2 to the N plus C Trace cells and this is this is quite relevant for performance and this is a some some benchmarks of our implementation of the I commitment scheme using this configuration so say we want to com to commit to a vector of size to6 fi ring elements and this means two to the 19 fied elements so this costs 65 milliseconds this should be the commitment time I don't know why it says fi and this is for comparison what you would get if you commit um if you do merry commitments to the vectors so if you commit to to to the 16 field elements the with a Blake function so classic classic has this is 14 milliseconds but as I said this is just to the 16 field elements this is to the 19 field elements also if you are using CLE trees you probably have encoded the witness which means that here you have an extra one in the exponent which is not not uh not giving you anything uh when you want to encode the witness maybe it's the the overhead is even larger if the rate of the code is less than2 yeah so if we compare 2019 and 2019 we get similar performance and if we put algebraic hes in the Merk trees which you we Pro you we probably have to if we are in the context of folding because it means we are interested in using some kind of recursion then the difference of course is dramatic how much time do I have five minutes okay so yeah we are almost there's one or two slides left so recall um and I take commitment is just Matrix Vector multiplication of ring elements there's a big issue with this commitment scheme I I said what is good about it and now what what's bad about it this commitment scheme is only binding when the vector you are committing to has small norm and the the norm of a vector is the largest coefficient of an entry of the vector when you look at the elements of the ring as polinomial and yeah remember that the the folded witness in our folding schemes are a linear combination of the two initial Witnesses so there's two issues here because of this caveat one is that even if W1 and W2 have small Norm because W3 is a random linear combination of W1 and W2 it is possible that W3 has large Norm in general W3 might have arbitrary large Norm in which case the commitment to W3 with the I commitment would not be binding and there's another issue that is even if one does not happen even if W3 has low Norm for some reason when you prove knowledge soundness of the folding scheme you need to make sure that the extractor gets uh Witnesses of small Norm because we because because of this caveat we only commit to Witnesses of small Norm so we end up requiring that the Prov commits to Witnesses of small Norm so when you prove knowledge soundness you need the ex to show that the extractor only gets Witnesses of small norm and this is quite difficult to enforce okay so since um there's 5 minutes less than I had planned for I will skip how ltis F and how we address these two issues and just jump to the Q&A part thank you yeah thank you very much so we have one question so why M31 is uh WP and because of the to adicity or yeah the thing is that there's a lot of uh factors coming into play when configuring these Rings we have to configure them in a way that when they split as field extensions they have at least 128 bits to ensure soundness during S Check and at the same time we have to ensure that there's a subset of small Norm elements that is large enough for the soundness in another other part of the protocol and this places a lot of constraints on how you can choose the cyclotomic um polinomial yes but the the the composition of P minus one is completely different uh it the the way you can choose the the way you can configure the ring is strict is is highly um constrained on the factorization of P minus one on how it factors do we have any other questions