# Folding STARKs with the Mova folding scheme

- Speakers: [Albert Garreta](https://streameth.org/speakers/albert-garreta)
- Channel: [Devcon 7 SEA](https://streameth.org/devcon_7_sea)
- Date: 2024-11-16
- Duration: 23:06
- Watch: https://streameth.org/watch/673833811b0f83434dc2c6ef

## Description

We will present a new folding scheme that is 5 to 10 times more efficient than Nova, and 2.5 to 4 times more efficient than Hypernova. We will then explain how to use the scheme so as to construct a folding scheme for STARK proofs.

## About the speakers

### Albert Garreta

Albert Garreta is leading the cryptography research team at Nethermind. Formerly he was a postdoctoral fellow at the Basque Center of Applied Mathematics (Spain). He received his PhD in mathematics from Stevens Institute of Technology (NJ, USA). His main research areas revolve around all types of zk-related topics such as code-based SNARKs, lookup and folding schemes, soundness aspects of interactive proofs, etc.


## Transcript

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 a prover 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 prover and the verifier interact, and at the end of this interaction they output a new instance witness pair, XC CW3 with this key property. So this output instance witness pair is valid so it is in the relation. If it is there, 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 property of a folding scheme. So basically what is going on here is that we have two tasks. We have to prove one instance witness pair and another one. And we have applied an interactive argument that reduce these two tasks to a single task. So if this folding step is very cheap, then you are basically gaining, 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 is the same as the instance witness pair, but it's a different instance, it's a different instance, it's a different instance from other ones. And in reality, in practice, all instances include a commitment to the witnesses. So in reality, in practice, we have the instance witness pairs 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 scheme looks like this. We have two instance witness pair where the instance contains a commitment to the witness. You fold, you get a new instance witness pair. 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 kilometers 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 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 prover 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 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, the homomorphic property of the commitment scheme. The verifier knows the commitments to W1 and W2 and because of the linear property of the commitment scheme it can obtain a commitment to W3 without any interaction with the prover just by performing this linear combination of the commitments. So this is how folding looks from 5,000 kilometers away. Many folding schemes look like this. OK, let's discuss commitments in folding schemes in more depth. So usually, the commitment scheme is a Pedersen commitment or a KZG commitment. So it's an elliptic curve-based commitment, or some variation of Pedersen and KZG. For example, in nova, hypernova, protostar, protogalaxy, et cetera, this is the commitment of choice. the of the of the of the of the of the of the of the of the of the the vector has large entries, so you have to prove statements about elliptic curves. So you have to prove statements about elliptic curves. You have to prove that the vector has large entries. So you have to prove that the vector has large entries. So you have to prove that the vector has large entries. So you have to prove that the vector has large entries. 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 NARC to prove a folded instance, right? Because you are using large fields, you have elliptic curve-based commitments, and so on. So, let's say we want to use a starg to prove a folded instance. So, we want to use a starg to prove a DCG based NARC to prove a folded instance, right? Because you are using large fields, you have 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 to prove our folded instance win spurs. So by Stark, I loosely mean a snark that uses codes and Merkle tree-based commitments. For example, the Stark protocol from Starkware, Plonky 2 on 3, Boojum, RIS0, and so on. These protocols are configured on small fields, and they are getting smaller and smaller. For example, Goldilocks for Plancky 2, Baby Bear for Plancky 3 and M31 for CircleStark. This is the attractiveness of small fields is that, well, the attractiveness of these fields is that you get smaller arithmetization due to special properties of the primes of these fields is that you get smaller arithmetization due to spatial properties of the primes of these fields. You also get cheaper computations because field elements never get very large. If you invert a 32-bit field element, the inverse has at most 32 bits. 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 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 cost breakdown of creating Stark proofs. And yeah, let's look first at how a fry-based Stark works. So yeah, all these proving systems I mentioned before work as follows. So first the prover computes the trace or the circuit values, the values in the wires of the circuit. Then it encodes the trace using a narrow correcting code polynomials and for this it interpolates the columns of the trace and then it evaluates the polynomials 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 Merkle tree. And finally there's some quotient, the prover takes some quotients and applies fry and so on. Okay, what's the cost breakdown of all these steps? I'm citing Elie van Sasson from a talk at SBC this summer. So the trace generation, in the case of stool, costs 46% of the total proof cost. Computing the low-degree extension costs 28%, Merkle trees cost about 13%, 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 recursion. So we are probably not using Merkle trees full of K-chucks or SHA-256 or classic hashes. We are probably using Merkle trees that include some type of algebraic hash, in which case the third step would be much more expensive. Yeah, so here's an important observation. Even if the Merkel trees were homomorphic, you don't want to do the folding with the commitments to the low-degree extension of the trees. Because you would, at each folding step, you would perform this step, this step, and this step, and you would save this part in here. And you would still need to do folding. So in the absolute best-case scenario, the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of the value of We don't want to commit to the low degree extension with Merkle trees. We are just going to commit to the trace in the most cheap way possible. Yeah, so this is a key difference with approaches like accumulation with automomorphism or the ARC protocol from these researchers from papers from this year. Okay, so let's recap what we want to do. 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 since we want an instance to be provable with a stark, here we think of instances as being errors or plonkish instances. And we look at this as CCSs. A CCS is basically an R1CS constraint, 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 errors. The framework is as follows. The prover 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 still in an error or somewhat similar to an error. And now say that we want to prove a folded instance. So we have done folding, and now we want to prove the folded instance with this pair. So what would the prover and the verifier do? The prover computes the low-degree extension. So we want to use starts, right, to prove the folded instance. And for start, if you are using start, you have to encode the witness because you are going to use error-correcting codes. So the prover computes the low-degree extension of the folded witness, W3, and commits to it with a Merkle tree, as if it was just using the start protocol. the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the instance witness pair is in the relation with his favorite start. Okay, so we have to keep in mind that we'll have to do this step in here when we want to prove a folded instance witness pair. So this will inform how we choose the commitment scheme to not make 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 somehow works over small fields. And the candidate here is the ITAI commitment scheme, getting inspiration from the So we have a lot of data, but we have a lot of data. So we have a lot of data. So we have a lot of data. So we have a lot of data. So we have a lot of data. So we have a lot of data. So we have a lot of data. If we look at error or Plunkish instances as CCSs, so let's say R1Css or relaxed R1Css, then the first thing that comes to mind is Nova, because Nova folds relaxed R1Css into relaxed R1Css. So this is our candidate, Nova. However, there's no Nova-type folding scheme that works over lattices. So, we have a very good model for this. So, we have a very good model for this. However, there's no NOVA type folding scheme that works over lattices. When it comes to folding over lattices, the only work available right now is lattice fold. lattice but there's no nova analog over lattices so one of our main results is designing such a such as a folding scheme okay so a bit on lattices and and lattice fold so lattice fold and many lattice based schemes work over so-called cyclotomic rings which are cyclotomic rings are basically, they look like field extensions, right? You take a ring of polynomials over a field, a finite field, and quotient it by an ideal generated by a polynomial. However, here, the quotient polynomial may not be irreducible. And in this case, this means that if the polynomial 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 Galois extension, the standard field extension. But if F is not irreducible, then you have this direct product. But in any case, these rings 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 start prime field. So we can choose F to be Goldil the first one, the first one is the first one, the first one is the first one, the second one is the first one, the third one is the first one, the fourth one is the first one, the fifth one is the first one, the And the parameters of this commitment scheme are as follows. It's just a matrix sampled uniformly at random from the ring with ring elements. It commits to vectors of length m of ring elements. And the commitment is simply the 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 can choose the base field to be the Goldilocks field, which has 64 bits, and we can configure R so that R splits as eight factors, and each factor is a degree three extension of the Goldilocks field. Here there's an important remark on how to work with cyclotomic rings, and this is that because of this isomorphism in here, this is the number theoretic transform, because of this isomorphism, you can potentially store eight trace cells in a single ring element. So if you want to store eight trace elements, 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 3 trace cells. And this is quite relevant for performance. And this is some benchmarks of our implementation of the ITAI commitment scheme using this configuration. So say we want to commit to a vector of size 2 to the 16 field ring elements, and this means 2 to the 19 field elements. So this costs 65 milliseconds. This should be the commitment time I don't know why it says field and this is for comparison what you would get if you commit if you do Merkle tree commitments to the vectors so if you commit to the to the 16 field elements the code with a Blake function so classic classic hash this is 14 milliseconds but as I said this is just to do a 16 field elements, this is to do the 19 field elements. Also, if you are using Merkle trees, you probably have encoded the witness, which means that here you have an extra one in the exponent, which is not giving you anything when you want to encode the witness. Maybe the overhead is even larger if the rate of the code is less than one half. Yeah, so if we compare 2019 and 2019, we get similar performance. And if we put algebraic hatches in the Merkle trees, which 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, I take commitment is just matrix vector multiplication of ring elements. There's a big issue with this commitment scheme. I said what is good about it, and now what's bad about it. This commitment scheme is only binding when the vector you're vector is the largest coefficient of an entry of the vector when you look at the elements of the ring as polynomials. And yeah, remember that the folded witness in our folding schemes are a linear combination of the two initial witnesses. So there's two issues here. Because of the 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 arbitrarily large norm, in which case the commitment to W3 with the I-type 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 witnesses of small norm. Because we, because of this caveat, we only commit to witnesses of small norm, so we end up requiring that the prover commits to witnesses of small norm. So when you prove knowledge soundness, you need to show that the extractor only gets witnesses of small norm, and this is quite difficult to enforce. Okay, so since there's five minutes less than I had planned I will skip how LatticeFold and how we address these two issues and just jump to the Q&A part. Thank you. . . Thank you very much. We have one question. Why M31 is WIP and because of the ? The thing is that there's a lot of 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 sound 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 part of the protocol. And this places a lot of constraints on how you can choose the cyclotomic polynomial. Yes, but the composition of P minus one is completely different. The way you can choose the, the way you can configure the ring is highly constrained on the factorization of p minus one, on how it factors. Do we have any other questions?