zkStudyClub - LatticeFold: Lattice Folding Schemes (Binyi Chen)

Transcript

Hello everyone. Welcome back to another week's edition of ZK study club. This week we're excited to welcome back Ben Yi Chen who's been a repeat guest here on the channel. Thank you Ben Yi for coming back. Thank you Alex. Yeah, and this is joint work that he's done with Professor Dan Boneh of Stanford University. I guess both both Ben Yi and Dan are associated with Stanford here. And this is about lattice fold and its applications to succinct proof systems. Thank you Ben Yi, take it away. Thank you. Thank you Alex. Thanks for the introduction. It's great pleasure to be here again. And today we will have a deep dive in this lattice fold which is new folding scheme that allows you to have a efficient proof system for really large statements but also with post

quantum security. So let me start with some background about ZK-SNARKs. I think uh most of the audience of ZK study club are quite familiar with this so I will maybe go over rather quickly for this. So what is a ZK-SNARK? It's basically a given some circuit C, given some public input X, a ZK-SNARK is a succinct zero knowledge proof showing that you know some secret witnesses that makes this circuit satisfy statement satisfiable. For example, a typical example is that you want to prove that you know the pre-image of hash. And in this case this hash is the public input and this SHA-3 hash function is the circuit. And this pre-image is your the secret witness that only you know. And you want to prove that you know it.

And usually a ZK-SNARK will consist of several algorithms. The first one is this setup or preprocessing algorithm that takes the description of the circuit and generates some proving parameters and verification parameters for the circuit. And later a prover there's a prover algorithm that takes the some public input and some secret witnesses and will be able to generate a proof. And there's also a verification algorithm that takes this proof, takes the public input and check whether proof is valid or not.

So, it also needs to satisfy several properties. First, for an honest prover that does know some secret witnesses for this public input, it should be able to generate a correct proof that passes verification. And this is called completeness. And second, for a malicious prover, suppose he's able to pass verification and let verification like accept, then that would implies that he actually knows some secret witnesses for this particular statement. Here by knowing it, I mean more formally there means that there exists some algorithm extractor algorithm that can extract this witness from a black box access to this malicious prover.

Sometimes you also need the property called zero knowledge, meaning that its proof shouldn't should not reveal information of secret witness. But in this talk, my main focus is another very very nice feature of SNARKs, which is saying that its proof should be really short and easy to verify. And this is also the key feature that makes this SNARK super useful in practice and which is enables a lot of really nice application for scaling blockchain and like obtaining verifiable machine learning of homomorphic encryption and other very exciting applications.

But for these many sophisticated and exciting applications, there's a key challenge here in the sense that prover needs to generate a proof for some really computational expensive computation statements. For example, machine learning inference or ZK-EVM transactions, those are really some complicated task that you want to prove. And the goal here is to enable this proving as fast as possible, which is actually not that easy. So, let me start with some background about SNARKs and in the literature there are many really nice and elegant schemes for SNARKs both in the pre-quantum setting and in the post-quantum setting.

And I would call them all as a monolithic SNARKs, which means that you can generate a proof all at once given certain statements. And they all follow these kind of patterns here. So, you will start with some MP computation statements you want to prove. And what you do is that we are re-execute this kind of computation to obtain some computation trace. And then you translate this computation trace using some algebraic transform like FFT to to transform them into some polynomial representation, for example.

And that will lead to some extended witness, which basically is a very long vector of field elements. And only after that, the prover has to do some global computation over this large extended witness. And this includes, for example, FFTs or multi-scalar applications or error-correcting encoding and so on. And the issue here is that when it comes to prove some computationally expensive statements, and this extended witness will be super super large because the computation trace can be very long. And then this will make this global computation really really expensive.

And moreover, because this witness has to take as a input as a whole, usually the prover also needs to have really large memory and it can be easily run out of memory if this statement is large. And also because of this kind of, yeah, need to do some global computation over the entire witness and this algorithm like FFTs, they are actually not that easy to be paralyzed parallelization friendly. So, it makes also harder to for engineer to make it more parallelization friendly and a streaming friendly. So, these are some limitations for these kind of schemes for those really really computationally expensive statements.

But given that, an alternative strategy is to build a piecemeal SNARK, which is based on this IVC and PCD uh scheme strategies. So, at a very high level, the idea is to slice this large computation into many pieces. Okay? For example, if you want to prove that you know 10,000 pre-image of 10,000 hashes, you might chunk them into 1,000 chunks, and each chunk statement is just responsible for proving 10 um 10 pre-image separately. But, in general, this is not quite trivial. Like, how do you transform any general circuit statement computation statement into many small chunk of statements? But, that's not the goal of this talk, and I will like to refer it

to our recent work Mangrove and some other work, and to tell you that this is doable and can actually do um be achieved very in a very efficient way. But, in this call, let's just assume that that's that's possible, and we can slice this large computation into many small pieces. And now, the goal is to prove that all these small pieces are satisfiable. All right? So, now in this case, we have this many many shaded rectangles here, which are the splitted statements we want to prove. And how do you do that? The idea is to prove the the correctness of these chunk statements using SNARK recursion strategy.

So, for example, given these many statements, you can build a binary tree out of it. And you start from the leaf layer, and for every leaf statements, you will generate a proof for these leaf statements. For example, for chunk statement one and chunk statement two, you'll get some proof pi1, pi2 for that. And then later, for their parent nodes, you'll generate another recursive proof for that. And this recursive proof is this pi2 star here, which which will check two things. So, the first is that this chunk statement three located at this node is satisfiable.

But, additionally, it will also this SNARK circuit will also check that its proof of its children are correctly verified. So, this implies that all the statements in this small sub tree are correctly verified and is satisfiable. And you can do this uh one more time and go layer by layer and finally obtain a single small proof that implies all the statements inside this large tree are satisfiable. So, this is how it works and it has has this obvious advantage for having much smaller memory overhead because the memory requirement is only proportional to the single chunk statements rather than the entire large statements.

And second, it's also more streaming and parallelization friendly because you can compute proofs along each path of the tree without affecting other uh non-overlapping uh paths. However, this kind of strategy is actually not widely used in practice because um until very recently, this recursion is actually pretty expensive. Why? Because first, every node here we would have to generate a recursive SNARK proof, right? And SNARK proof generation is not cheap and you have to do it for so many times. So, it's expensive.

And second, for every recursive proof you generated, the corresponding recursive statements not only includes these chunk statements but also needs to embed a SNARK verification logic inside. But usually, the SNARK verification um the circuits for SNARK verification is usually quite concretely expensive. So, that makes things much more um complicated and expensive. So, given this, many recent work trying to build a primitive called folding scheme to reduce the recursion overhead. But before I explain what a folding scheme is, let me um like give some backgrounds about committed MP relation, which will be very useful in folding schemes.

So, say we have some MP relation R and here the goal for us is transformed to somewhat equivalent relation R prime here. And in R', the instance is um slightly different. Well, we will insert a small commitment C inside this public input. And we say that this tuple X' W is in this transform relation if and only if the original XW is in this relation R, but moreover, the witness is a correct opening to the commitments. So, whenever you want to prove XW in R is equivalent that you can just It is sufficient for you to just prove that X' W is in R'.

Okay? So, you will know you you'll be clear why we need this very soon, but for now, for simplicity of notation in the following slides, I will omit this public input part just for simplicity, but you should bear in mind that usually when I say CW, I actually also there should be a public input inside this instance part. Okay, so after knowing this background about committed NP relation, let's see what exactly a folding scheme is. So, in a folding scheme, the folding prover has access to two committed NP relation statements.

And his goal is to convince the verifier that I know the correct witness of these two NP statements. For example, here it would be this W1 W2 here. Okay? And to do that, they will run some lightweight and usually public coin interactive protocols. And at the end of this protocol, if the verifier accepts, then he will be able to obtain and output a single folded instance, which is CFD here. And the corresponding prover should be able to output a corresponding correct witness for that.

So, in some sense, you can see that this kind of interactive protocol allows us to reduce the checking of these two initial NP committed NP statements into the checking of this one last folded instance with spare checking. And that's what the name of folding scheme comes from. And it also needs to satisfy some similar completeness and knowledge soundness notions, which means that in an honest execution, for an honest prover who does know to a correct witness for the input instance, then after running this protocol, he should be able to output WFD that's in the relation in output statements like output relation here.

And knowledge soundness is saying that even if the prover is malicious, okay, he can do anything he wants. And if he supposes able to pass verification and finally output some correct witness, then that implies he actually also knows correct witness for this two input instance here. So, he should actually know some correct W1, W2. So, this is somewhat similar to SNARKs, but you can see this kind of weaker notion of SNARKs. And that's also the reason finally you can obtain some more efficient schemes for folding rather than for SNARK.

And you can even generalize this notion further to to get this notion of reduction knowledge protocol, which says that this basically is a protocol that allows you to reduce the checking of any input statements in this relation R1 into the checking of some output statements in relation R2. So, if you look more closely, you can find that folding scheme is just a special case where R1 is defined to be R * R and R2 is R. And the goal is to reduce the checking of two statements in R into the checking of one statement in R.

So, that's some background about folding scheme. And after knowing that, let's see why we can build a more efficient piece of SNARK from folding scheme. And let's still assume that we are able to slice this really large computation into many small pieces, and now our goal is to prove that all these pieces are uh satisfiable. And here, let's for simplicity just consider a chain. And now, what the stock prover will do is the following. So, he will initialize some statements uh or instance with spare. Uh he will use usually it's just commitment to some um like zero vector or something.

And then at each step, what he will do is that he will run this folding prover algorithm. Usually, this is is some algorithm that's uh make this protocol pi we said before to be non-interactive using Fiat-Shamir. And he will run this protocol uh run this proving algorithm and obtain a updated folded instance with spare that's merged these first chunk statements um inside. And he will do this again for the second step, which involves the second chunk statements. And he'll do this again and again for n times. Finally, obtain a final folded instance with spare here.

And that will be served as a proof here and send to the verifier. And the verifier now only should check that its last statements or instance with spare is inside these chunk statements. And by the property of folding scheme, this implies that prover actually should know all the correct witnesses for all the n chunks, which implies that he actually know the witnesses for the original large computation. But there is a one minor issue here in the sense that uh how does verifier guarantee that prover is giving you the correct folded commitments or folded instance here, right? What if he just choose some other arbitrary um folded instance that's unrelated to c1 to cn, right?

But this is actually easy to fix. What we do is that we would define some public input, which is some trusted public input, which is the chain hash of these um instances here. And then the prover will additionally send all these uh instances that he wants to prove, c1 to cn. And the verifier now only is to check that C1 to CN are consistent with this trusted public input and recompute this folding commitments herself by calling this folding verify algorithms. Okay? So, that's will ensure that CFD N is the that's the verify finally check is always the correct one.

But it has some caveat here in the sense that the verify complexity is at least linear to the number of chunks here, right? So, when the number of chunks is large, this actually amounts to a large and complex like expensive verify. By turns out we can do much better and remove the dependence on the number of chunks. The idea is just to delegate this iterative computation done by the verify into the relation we want to fold. So, that means that after you fold this relation, if you check the last relation hold true, then you can also make make sure that this this kind of computation is done correctly and CFD N is computed correctly.

So, more precisely, what we do is that as same as before, the SNARK prover at each each folding step will fold two instance with its pair into one new folded instance with its pair. And then at the next folding step, he'll generate another instance with its pair for a new statement. And this new statement is slightly different from before. Well, beyond checking that its chunk statement at I step is correct, he'll additionally check that this public input hash check is correct and this folding verification was done correctly. Meaning that the newly outputted folded commitment is correctly computed from the previous one and the previous

like online commitments. And this ensures that after you check the last folding step, all the all the computation were done correctly, including this folding verification, and that implies the CFD N is always the correct one we want. Okay, so that is about correctness, but why is much much faster and much more efficient than a SNARK recursion, right? The TLDR is because the folding scheme usually can be much simpler than a SNARK. If you look at more closely, you can find that folding verifier usually just involves a linear combination of some small commitments.

Okay? And this is much simpler than a SNARK verifier, and that means this folding uh this statements we want to fold is much simpler than this recursive statements you want to prove previously. And beyond that, you see that at each step, the folding prover, what he does is just to do a linear combination over witness vector, which is far more uh like far faster than the SNARK prover algorithms. So, that also is the main reason that why folding can be much much faster than a recursive uh SNARKs.

Okay, so that's the reason why we why we prefer folding scheme, and now the question is why uh whether we can have a really efficient folding scheme. And the folding scheme usually uh we are involved with a committed empty statements. Usually, they are commit they're folding these committed empty statements. So, we have to instantiate the commitments, and there are two key properties you want from these commitments. First is that they are allows you to compress a long witness into a short string. And second is also nearly homomorphic in a sense uh in the sense that the addition, for example, additional commitments is a commitments of the addition of the witness. And that allows the folding verifier to do very simple uh check over the commitment space rather than the

expensive message space. So, prior to our work, all the schemes are using Pedersen commitments, and because they are nearly homomorphic, they're transparent. However, they also have some limitations here in the sense that first, they are based on this discrete log assumption that's vulnerable to some quantum attack. So, it's not post-quantum secure. And moreover, in terms of efficiency, they also have some kind of limitations. So, usually if you want to build an IVC or PCD, if you want this scheme to be relatively efficient, you have to use a cycle of like a cycle of pair of curves.

And these kind of curves are usually harder to find and also less efficient than regular curves. And second, because of the use of pairing commitments, that means that prover also needs to do some elliptic curve scalar multiplication over really large scalar fields. Right? Usually like two two 256-bit fields. And that can also be quite expensive. And it's also very wasteful because usually what you do is that we embed this data, the real like program execution data, into this scalar field. But usually the real world data is only like some small integers like 32-bit integers. So, it's kind of wasteful as well.

And finally, in terms of these folding verifier circuits, it's definitely more efficient than a SNARK verifier circuit. However, it still has some kind of overhead here. First, it needs to embed like a few elliptic curve scalar multiplication inside, which is expensive. But moreover, because you have to embed this elliptic curve scalar multiplication, that means the circuit is over the base field of the curve. But this verifier also involves some field operation over the scalar field of the curve. That means you have to implement some arithmetic over scalar fields as a circuit over this different base field that can blow up the circuit sizes.

So, you may wonder, like an acute reader or audience may wonder, why not just use a hash-based proof system, right? And do do SNARK recursion. So, the in that sense, all the things are over a single field, like this really nice FRI-based schemes are only over work over a single field. But however, that would require you to do a full SNARK recursion which as I mentioned before full SNARK recursion usually is more expensive than this folding based piecewise SNARK because folding scheme usually is much more efficient than a full SNARK.

So given this my question is whether we can achieve the best of both worlds, right? Whether we can still use this folding based piecewise SNARK construction and build a sum folding scheme, but can we get rid of these kind of issues that we have like for now? So whether we can have folding scheme that has post-quantum security, has ultra-fast prover, and moreover has this succinct verifiable circuit that removes the need of doing any non-native field emulations. And the answer is yes and this is our work LatticeFold which is the first lattice-based folding scheme that is based on this MPC assumption which is believed to be quantum resistant.

And moreover even compared to those pre-quantum folding schemes it has very competitive efficiency and I'll explain why this case in the end of the talk. Okay, one thing to note here is that moreover it also supports this kind of relatively small fields compared to Pedersen schemes that we you all can only use this really large field. Okay. And finally I want to mention that our scheme is like the constraint system corresponding constraint system or the circuit is actually over a ring like polynomial ring. And that means it can natively simulate those operations that's done over rings for example fully homomorphic encryptions or some machine learning task and that makes this more

friendly for this for simulating these applications which is another nice feature for this schemes. Okay, so from this I have already explained what are background about folding scheme and now I want to go to more technical part and see how we can actually build a folding scheme for this emulation that allows you to do IBC. Uh any questions so far? Uh no questions in the chat. Thanks, Biny. This is great so far.

Nice. Okay, so let's go to the technical part. Now I want to build the folding scheme. And for simplicity in this talk, I'll just focus on a slightly simpler fashion where I'll just focus on uh folding this commitment opening relation which is checking that the witness is a correct opening to a corresponding commitments. Okay? To do that, the first question uh we ask at the first question we need to answer is what kind of commitments you want to use now, right? Remember we want to use nationally some commitments that allows that has these two really really nice property. First, it allows you to compress a long witness string into a short string, which is commitment. And second, it should be non-homomorphic.

And in the last word, this will be a tie uh binding commitments or a tie collision resistant hash functions. And what is the a tie uh binding commitments? Oh, by the way, I'll I'll focus on the binding property and ignore the hiding property of commitment schemes, but you can extend that easily. So, what is a tie binding commitments? The message space of the a tie binding commitments is slightly different from this Peterson construction. So, the message space is actually uh a a integer vector such that every entry has some constraints. It's a subset of this ZQ to the N space where every entry has to be have very small absolute values. For example, inside this range of minus beta to beta where beta is some small parameters.

An extreme example is just we consider message space as just a binary string, okay? And you go to commit this uh long string into a short vector. And what you do is to multiply this uh vector by some public random matrix A here over ZQ where Q is a prime modulus. And that will lead to a really short string because this matrix is quite narrow. And so it satisfies compressing property which allows you to compress a long vector into short string. And it's also binding. Well, what is binding? Binding is saying that it's infeasible to find the two openings of the same commitments, okay?

And this is comes from this SIS assumption which says that given a public random matrix A, it should be hard to find a non-null vector X such that AX = 0. And why it leads to binding property? Suppose for contradiction we have two vector U and W that maps to the same commitments, then U - W will satisfy that A * (U - W) is 0, right? And moreover, U - W is some non-null vector because both U and W are non-null vector. So this will break the SIS assumption and that's why it is binding.

Are there any question in the chat? I I was just posting the the Ashai papers. Oh, I see. Thank you. Cool. And moreover, it satisfies this linear homomorphic property which is quite straightforward by the this linearity of matrix multiplication. But one thing to mention here is that only support those small efficient linear combinations. So you need to make sure that this coefficient is small and also the message in this linear combination is very small.

So you see here this is kind of somewhat strict, right? Well, you have to make sure that this witness is actually non-null. So by the way, I also want to mention that in practice this is actually not going to be efficient, but there's a efficient instantiation where you replace this integer or in ZQ with some cyclotomic polynomial ring so that you can pack more elements inside ring elements and you can replace this expensive matrix multiplication with some ring multiplications which can be very efficient using NTT. And that's why in practice this additive collision resistant hash function is actually can be really really fast given some correct optimization and implementations.

Okay, so one thing to note here is that this uh we have some constraint here that the witness should have no norm. But you might want ask, right? Usually in an NP relation, the witness should be arbitrary, right? It should be some arbitrary elements in the ring or arbitrary to elements in the field. So, how do you actually commit this witness with large norms? So, I will give a word about how we deal with in our final solution. So, the idea here is we we will slightly change this commitment opening relation for that. So, in this in this relation, the instance is still includes these short commitments, but the witness will have two parts. The first part is the original witness that have no norm constraint. The second part is

this V here, which is like the gadget decomposition of the original witness that will have low norm. For example, you consider an element seven, it can be represented as 111, right? Which is this binary decomposition of this seven. We using this gadget vector of 123. So, given that, you can what we do is that we want to check that the commitment C is a commitment to this no norm vector V that has small norms. But moreover, the original witness W have this kind of gadget matrix relation with the this decomposed vector. And that's enough.

And in our final solution, we will build a phone scheme for some NP complete relation that involves like that includes this kind of relation. And the reason that is easy to fold is mostly because this gadget matrix multiplication relation is also linear. So, it's very easy to fold. But for now, let's uh consider a simple case well which always assume that witness is always no norm even in the beginning just for simplicity of our discussion. Okay? And now we can simplify this relation to be the following, we want to check that this uh like this witness is a vector that has a correct opening to this commitment that satisfies this matrix multiplication relation and also have no norms. And here by no norm, I mean that every entry of this vector is in the range of minus

beta and beta. Okay. So, we figure out what kind of relation we want to fold, we figure out what kind of commitment scheme we want to use. Now, the question is how to build a folding scheme. And let's assume that we have two instances with the sparseness in this particular uh relation. And now, the question is can we reduce the checking of these two statements into one statement of the same relation? And the natural idea is just do a linear random linear combination, right? Which is used in all this Nova scheme, Polestar Hypernova. However, this becomes much more complicated in lattice world, and this will no longer be in the same relation.

Why? Because after this random combination, this folded witness cannot have much larger norms. Even if you just consider an addition, then the norm can go from beta to two beta. And this can get even worse if you just use some arbitrary random scalar. And that means after very few number of steps, this the norm of this uh folded witness can like quickly blow up and exceed some security thresholds for SIS assumption. Remember the SIS assumption, it holds true for only if this if this solution you found is low norm. But now, it is no longer low norm, so it will never have the binding property again.

And actually, we also have some concrete attacks for this, meaning that if you fold for many steps, there is actually no longer secure. So, now we want something stronger, meaning that after this folding protocol, we want to make sure that this folded witness will still uh in the exactly the same relation with non-bound beta. And our first idea to achieve it is to uh massage or refresh this input witness a bit and to make their norm even lower before we do this randomly combination. Okay? And I will make that more formal, but we need to use some nice property about this reduction knowledge protocol which it says that allows you to do sequential composition.

So, say we have a reduction knowledge protocol that reduce R1 to R2 and another protocol reduce R2 to R3. And this theorem is saying that if you compose these two protocol together, that will give you a reduction protocol from relation R1 to R3. And now recall what is our original goal. Our original goal is to build a reduction knowledge protocol of folding scheme that reduce the checking of two statements in R type beta into one statement in R type beta. And given this sequential composition theorem, we can split the construction of pi into two parts. When in first parts, what we do is that we'll split these two instance with a spare into more instance with pair like 2K and here for simplicity let's just consider four.

And why we want to do that is it because that after this splitting I can make sure that witness of each statements is now having even lower norms like which should be this P which is smaller than beta. And after that we'll design another like carefully designed protocol that merge these four statements back to the one statements then now we'll be still in the same relation R type beta. And then if we compose them together, we'll obtain what we want. So, now the question is how to instantiate these two reduction knowledge protocols. And I will start with this um um this splitting protocol or decomposition protocol first which allows you split two instance with a spare into 2K or four instance with a

spares. And for simplicity let's just consider a simple case where just split one to two and let's assume this parameter B is a square root beta. And our goal is to split a some input witness vector such that every entry of this vector is in the range of minus beta into two vector for which each of the vector will have even lower norm. And the idea is quite simple, which is quite similar to this gadget decomposition trick in FTT. And the idea is to write this big vector into two using this uh base uh base value B here.

More precisely, for every entry of W, we'll do a division by B, which will give you some remainder and the quotient, right? And this vector of remainders and this vector of quotient will be exactly the vector we want that satisfy that every entry is in the range of minus B and B because B is uh B is like square root of beta. And even better, if you multiply A by both sides, this equality will still hold by linearity matrix multiplication, which means that we can also check this combination relations easily on the commitment space.

So, that leads to the following protocol. When the prover is given his input witness, we'll run this particular splitting algorithm to obtain W1 W2. And he obtain the corresponding commitments of C1 C2 and send it to the verifier. And the verifier will check that C1 C2 is consistent with this input commitment C. And if that holds true, he'll accept and output C1 C2. So, it's easy to see that satisfy completeness because W1 W2 by honest prover is indeed a correct opening of C1 C2 with norm lower than B here. Uh okay, yeah. Uh there.

Does the verifier also have to check that the decomposition has been done correctly? Uh no. He only needs to check that it's this uh this particular uh commitment relation. And you'll see why Oh, yes. Yeah. I see one. Yeah. Carry on. Yeah. So, yeah. I I'll explain that. For knowledge soundness, I guess that's related to their question. So, I want to prove this knowledge soundness, right? For any arbitrarily uh generated W1 W2 that's in the output relation, meaning that there are correct openings of C1 C2 that have lower norm B.

What we do is that the extractor can just uh uh output W1 + BW2. And um note that extractor actually knows like half access of this of this beliefs of prover, so he actually knows W1 W2, right? And you can make sure that this uh W star is actually a correct opening for C because it satisfies matrix multiplication relation, which is explained here. And moreover, the norm of W star is uh also lower than beta. So, this W star will be in this input relation. Okay? So, that will finish our proof that this is actually knowledge sound.

Okay. Uh there is you are Are you having a new question or No, I saw you like uh raise your hand. sorry, I didn't Oh okay. I should lower my And uh okay, yeah. That's good. Yeah, I think I've seen Okay, cool. So, that's about the decomposition part. And the second part now is like now we want to carefully design this fold protocol that turns back this uh initial witness into a single witness that's in the wrist relation of R type beta. Okay? And uh still for simplicity, let's just assume that we are focused on the 2 2 1 folding case.

And now the the nice thing about this new problem is that this input witness now is having even a lower norm. Okay? The norm is now B rather than beta, where B is much smaller than beta. I still need to need need to be careful because if you do arbitrary random combination, this is still not going to work. So, what we do is we actually we are choose a small random scalar over a over a subset of this uh chance space. Uh and then if you choose R to be small enough, then after folding you can still control the norm of this folded witness so that it will still be smaller than beta so the completeness will hold true.

However, the issue is that whether knowledge soundness will hold true and that's actually very hard questions. And to illustrate why it's hard, let's consider a typical way to do extraction and let's for simplicity let's assume this prover this malicious prover is actually very nice. Like for any folded commitment he you give him, he will obtain a return a nice witness for you which is in this upper relation that have a norm no lower than beta. In this case we can rewind this algorithm and feed it into two folded commitments which use the two different random scalar.

And and he will return us two nice witness. And recall our goal is to recover the W1 W2 here for the input statement, right? And to do that a naive way to do that is to build this system of linear equations and to try to recover W1 W2. So we'll solve this system of linear equations for for W1 W2 and that would actually give some us some unique and close form formula for W1 W2 which is pretty nice and our hope is that this will be the W1 W2 we want. Okay? But however, this will not work.

The reason is that after this like this solution, this solution will actually have possibly have large norm. Why? Because if you see this close formula, even just consider the left hand side, the bracket is the difference of two vectors whose norm is can be as large as beta and the difference can be as large two beta which is already much larger than the bound you want to achieve which is B. So it's not going to work. Okay, so that means this naive random combination will not give us security and our way to fix it is to add something more on top of it. To run some range proof protocol on top of this random linear combination and the goal of this range proof protocol is to make sure that after the

extraction we can actually argue that the prover can never use some large witness. This extract witness will actually have low norms. Otherwise, the prover will not be able to pass the verification easily. So, to recap, like to rephrase a bit, the question we want to do is the following. We have a prover, they were given some like multiple input commitments like C1, C2, and the goal is to prove that I know some committed vector corresponding to these two commitments, that they satisfy this matrix multiplication relation, but moreover, this committed vector is having low norms. Meaning that every entry of the vector is in the range of minus B and B here.

And one way to achieve that is just to send like completely open this this commitment, right? You just send this all the vector to of the commitments to the verifier, but that will work, but that will not be efficient. So, that will violate our last requirement here, in the sense that we want to be make sure that in the corresponding folding protocol, the verifier circuit will be very, very efficient, so that we can never afford to have an immediate size verifier. And our solution is to combine our previous idea, which is do this random linear combination plus rewind extraction, and also add a range protocol.

So, the first requirement is very easy to achieve using random linear combination and rewind extraction, but the key functionality of range proof is that it enables you to also prove the second property, meaning that committed vector will have low norms. And now the question is how to instantiate this range proof protocol, and our idea is to do it through sum check. So, what is sum check? Sum check is a problem for which there is a verifier, he wants to be convinced that given some committed polynomial, like committed multi-variable polynomial We've here, which have multiple formal variables, one X and X1 to XM. We want to check that the evaluation of G inside the

Boolean hypercube, the sum of the evaluation of this of this evaluation in the Boolean hypercube equals some claimed value. And there's one naive way to achieve that, right? Given this some black box given this oracle access to this committed polynomial, we just query the evaluation of G at every point inside this Boolean hypercube of 0 1 to the M, and then you compute the sum yourself and check if if equal S or not. But this definitely is not very efficient, which is has two to the M complexity. But it turns out with the help of some possibly malicious prover, the verifier can be like much much cheaper. So this is exactly the sumcheck protocol, which is a multi-round protocol between a possibly malicious

prover and an honest verifier. And in each round of this protocol, the verifier need to send and sample small random elements and send it to the verifier and do some basic and really really cheap computation. And that means the sumcheck protocol will have really efficient verifier. And at the end of this protocol, it now suffices for the verifier to just query this polynomial G at every single random point. And if that's evaluation holds some kind of equality, then he can be convinced that his initial sumcheck uh statement will hold true as well, even if the malicious prover is even if the prover is malicious.

So in some sense, you can see here that this sumcheck protocol can be understood as some reduction protocol, right? Well, we want initially we want to check some sumcheck statements, but after running this protocol, now it suffices to just check some random evaluation statements. So it's a reduction protocol from sumcheck statements to evaluation statements. So that's the background about what sumcheck is and what sumcheck protocol is. And now the question is like get back to our initial questions, how to obtain a range proof statement from sum check. And we achieve this in two steps. The first step to to rephrase this range proof statement as a sum check statement.

And the second step is to build a proof knowledge or efficient folding protocol for this particular sum check statement. Okay? So, what is a range proof statement? A range proof statement is saying that given some commitments which will commit some corresponding committed vector. I will want to check for this committed vector every entry of this vector is in the range of this minus B and B. Okay? So, that's what a range proof statement is. And our first step is to retranslate this in into algebraic check. The idea is to introduce this polynomial H, which is the product of this many terms X as plus one X minus one so on.

And you can see here that H of X will be zero if and only if X is integer input I X is in the range of minus B and B. Because if it's in the range, one of the term will be zero, so the product will be zero. Otherwise, the product will not be zero. So, now that this statement is the same as the following. We want to check for every entry of this committed vector H of FI equals zero. Right? And then this is for arithmetic over integer, but it's fine to replace it with arithmetic over a prime field for efficiency.

And now what we do in the next step is just some syntactical change. Okay, yeah. Dara? Oh, you're muted. Sorry. I You don't need to answer this right now, but I was wondering um how the security depends on Q. Oh, yeah. Um How how big does Q need to be? Q usually like as long as because B is really small, right? And here you see here that as long as the Q here um can be small, but the when in our initial our final solution will use a polynomial ring.

So Q actually 32-bit Q is enough, usually. 32-bit prime for Q or 64-bit for prime is is enough. And you might wonder you might wonder why it gives you security and soundness, but I'll explain more later because Q like like in short it's because we use a polynomial polynomial ring and we do a sumcheck over a ring and this ring itself is large enough to give you to give you enough number of securities. I see. So so Q itself doesn't need to be Yeah, Q itself doesn't need to be large.

Okay. So yeah, so from this our next step is just to have a syntactic change where we view this statement over vector as a statement over a multilinear polynomial. This is because for every vector there's a there there's a map between a vector with a multilinear polynomial of a log n variables. Basically, you just map the first entry to the first evaluation of this multilinear polynomial in in the Boolean hypercube and map the second entry to the second evaluation inside this Boolean hypercube and so on. So now we can re like understood this vector statements like differently to see it as a zero check statement for some multivariable polynomial. So what does mean? So it

means that now instead of checking hf1, hf2 are zero, we just need to check that for this composed multivariable polynomial h(x) the evaluation of it inside this Boolean hypercube are zero everywhere, right? Then that's equivalent to the initial statement we want to prove. And we have some classical trick to transform this a zero check over multivariable polynomial into the sumcheck statements over multivariable polynomial. Um and that finally we get some sumcheck statements. And if this sumcheck statement holds true if and only if like informally say the subject holds holds true if and only the initial range proof statement holds true.

So this will finish our first step and we translate this range proof statement as subject statements. Now the question is how do you build a proof knowledge or folding protocol for this particular subject statement? And of course our starting point is exactly this subject protocol I mentioned earlier, which is super efficient. And as I mentioned before it's also reduction protocol from the subject statements to evaluation statements for this polynomial G here. Let G is defined as follows. And we can make it even simpler here in the sense that we only need to check some evaluation statement for this multi-linear polynomial F here, which embeds this initial committed vector F1 to Fn.

The reason why that's sufficient is because the structure of G is really nice. Suppose we have the evaluation of F at some point R, then we can recover the evaluation of G very easily at a point R by just compute this H of T times EQ of R. Both of them are really efficient to compute that can be computed by verifier or self. So finally we reduce the last problem. How we can check that for this committed vector or this committed multi-linear polynomial F the evaluation statement at some random point R is correct.

Okay? And one naive thing is again just to open like completely open this multi-linear polynomial or this vector F and send to the verifier and the verifier to check it. But that's not going to be efficient because this complexity at least linear to the size of the vector. Because even one evaluation of multi-linear polynomial has linear complexity. And our key observation is that you actually don't need to check it right away. The idea is to fold this kind of evaluation statements and only delay the checking till the very end.

So the question is why we can fold this evaluation statement for multilinear polynomial. So, say we have two committed polynomial F1, F2 and two points random points R1, R2 and want to check these two evaluation statements. And now we're going to reduce the checking of these two statements into one. The idea is to is following. Well, for each evaluation statements, we can actually understand it as a sum check statements. This is by this famous multilinear extension theorem, which is like similar to the like round theorem in the univariate case, which is saying that for any arbitrary evaluation of multilinear polynomial, this evaluation can actually be interpolated given the evaluation over the Boolean hypercube using this EQ polynomial here, which is

analog of Lagrange polynomial in the multivar case. So, now you have two sum check statements and you can now run the sum check protocol again and that will reduce you to a randomly evaluation statements on some multivar polynomial that's related to F1, F2 and EQR1 and EQR2, right? But you can see this EQR1 and EQR2 are something very efficiently computable. So, actually what you need to check finally is just these two statements for F1, F2 at the same random points uh oh, where R is this the sum check challenge vector.

And now we are doing something like doing something meaningful here. We reduce the checking of two points evaluation of two points into checking of two polynomial at the same point. And then finally, because this committed polynomial is homomorphic, we can do a randomly combination and translate it into a single evaluation statement for the folded committed polynomial FFD here. So, this is how you do the folding for two evaluation statements. So, now we'll get back to the initial questions. How does it help with you to check that this multilinear evaluation statements hold true, right?

And as I said before, the idea is not checking it at all. We just fold these statements, fold these two evaluation statements into one, and only like fold this again and again and only at the very last step we're checking it naively in a linear time, but in a the amortized complexity is much smaller. Okay, so that's the way how you do folding for evaluation statements, and now let get back I'll get back to the original questions on how to obtain a folding for this uh commitment opening relation. To do that, we actually need to do slight change on this uh folding statement we want to uh define. So, we actually will at every step will maintain some accumulated statements or folding statements, which not only

includes a folding commitment opening relation statements, but the one more evaluation statements for the corresponding committed polynomial. And at each folding step, whenever you have some online statements you want to uh fold, and then the now the question is how to fold these two statements in the relation in these two relation into one uh statements in this uh eval B relation. And as I mentioned before, basically these two statements are just a bunch of matrix multiplication statements, range proof statements, and evaluation statements.

And as I mentioned before, you can definitely use a randomly combination trick plus the sumcheck protocol to finally reduce all the statements into check of a single commitment opening relation statements for a folded polynomial, and one last evaluation statements. That's basically the last evaluation statement you need to check in this uh in this batch sumcheck. And that will be in our updated accumulate statements that will be used for the next folding step. And the highlight here is that this folding verifier complexity is actually concretely very efficient. It's only logarithmic to the length of the witness vector, and it's actually the all the operation is native and it is very very uh simple, just basically some like multiplication and additions.

And uh one thing I want to note here is the actual knowledge proof is not that simple. It's more subtle than this intuition. The reason is because in the folding scheme, we know that for malicious prover, the small moments that he output this folded openings, right? Folded witness, is after he knows these sum check challenges. But when we do this rewinding base extraction, we are extracting from these outputs, right? So basically that means the extracted witness we get is actually depends on the sum check and challenges. But sum check soundness soundness usually saying that given some fixed polynomial over the randomness of sum check challenges, some sum check statements should not hold true or something like that.

So by the here like the the the input witness are actually correlated to sum check challenges. So it's more subtle to give a proof for that. But actually we can do do that given thanks for the binding property of the commitment schemes. But I will refer to more like details in our paper though. By the way, we will have a update for our paper very soon. So we will keep everyone posted. Okay, so that's basically the general idea. But as I mentioned before, it's very very simple scheme and in a very very simple setting. First, we are only dealing with prime field and integer before. But actually in practice, what we will do is that we will instantiate this add a commitment over a ring,

which is the cyclotomic rings of dimension D. Where D is usually power of two to make it more efficient. And also, you remember we need to do this random combination, right? And we need this this random scalar to be really small of low norms. And that means we have to chosen that from a large set over the polynomial ring in order to make sure that we have enough soundness errors here. Like soundness security here. So the subset should be very large and this is impossible to do it if you just sample it from ZQ. So that all means that the sum check should be over rings rather than over fields.

And then we can instantiate that over rings without too much more complexity. And that also answers there was questions before on that we can actually support small Q, but still have enough number of security for sum check using rings. And the second part is also quite related. So, basically in practice we want a smaller choice Q, right? Because we want to obtain like enable efficient CPU and GPU in operations and avoid number arithmetics. We can actually achieve that. And I think both like 32-bit Q or prime Q or 64-bit prime Q should work. And another byproduct is that the now a field allows you to do more efficient packing of a real world data. We just pack this data into the

this each slots of this polynomial ring. And then every every slot is just 32-bit rather than 256-bit. Okay. And one final thing is that I mentioned before you actually have to do a folding for this MP complete relation, which allows you represent this computation for chance statement and folding verification. And we actually support that and this MP complete relation is a generalization of this customizable constraint system introduced by Srinath, Riad, and Justin Thaler.

And we extend that to the ring setting. So, basically this in this constraint system all the constraint can be represented over operations over ring operations rather than field operations. And this makes it very also very nice for applications like verifiable machine learning and fully homomorphic encryption, for which the operation we want to prove is done over a ring rather than over a field. Okay. So, one last word about the efficiency of our scheme. To compare to those existing Peterson base schemes, what we have done is that we replace this Peterson commitments with Otter commitments.

And what that means we remove this many elliptic curve scalar multiplication over a large field, which is quite expensive, with this ring operations over quotient polynomial rings. Usually it's cyclotomic power of two cyclotomic rings, which can actually be super fast. And even better, we have so many really nice and sophisticated FHE libraries and have hardware optimizations. And we can migrate some of the those uh tricks there and to make this for improver even more blazing fast. And for the folding verifier, the key metric Oh, yeah, there.

Yeah, so um you have the So, is the B here the same as the B earlier that was the um the the small abundant beta? Yes, small abundant of beta, and B is some dynamic parameter you can choose. And in our Usually, what you choose you just choose B equals two or four. I think that's the that's the nice Uh I see. You had on the the previous slide um that uh beta was of the order of B squared. Does that Yeah, that's just for example. Like uh Oh, I see. Right. Yeah.

Because you In that case, you split It can be much smaller. Yeah, you just split one to two, but you can split one to K, right? And then you can make the make the B even smaller. Oh, I see. Yeah yeah. Got it. Yeah. For example, if beta is a two to the sixth uh 16, and if you for example, if B is uh say four, and then the is the split one to four, right? Because Oh, because uh four to the four is um 16. Because Uh right. Okay.

Yeah. I think Okay yeah. I think either four eight, but yeah. I think it's probably eight. Yeah probably. Because B to the K is I think B to the K is B Yeah, is I think it's the A. Yeah, so it's the A to the S is 2016. Yeah. Yeah, yeah, yeah. But this something you can you can like tune yourself. You just find that the sweet spot you want. Yeah. Okay so um for the verifier for the folding verifier, the key metric is the circuit complexity of this folding verifier, right? And the really nice property about our scheme is that the sum check verifier basically they only do every operations doing here is only over a

single quotient ring here. Okay? So that means the corresponding circuit does not need to do anything like any non-native field operations. And this is a great advantage compared to those Peterson base schemes, which needs to do non-native field accumulations, and that's also the key reason why we can actually obtain some really competitive circuit sizes for the folding verifier as well. So that's why last vote even though it I like I like you you really when you see this is post-quantum secure is lattice-based you might think that's not very efficient, but it turns out in this case can actually be very efficient.

And one last thing about this piece of business now construction is that which is actually some folklore trick here is that if you if you do this uh do the techniques I mentioned before, finally the prover needs to send some folding a folding instance with a pair to the verifier, and verifier needs to check it. And what if you this folded instance with a pair is still large, right? Which is possible for some kind of really large computations. Say you have a computation that's involves 2 to 40 gates, and even if you split them into 2 to 20 chunks, each chunk can still be large as large as 2 to 20. So in that case it's still pretty large, but you can use some very classical trick to compress it further.

Finally, what you do is just use another more realistic SNARK proof to generate a one single proof for these chunk statements for these folding chunk statements to prove that it will be correctly verified by the verifier. And then you can instead of sending the folding instance with spare, you can just send a corresponding proof. Proof that this folding with spare will be checked correctly. And this folding witness will be just secret witness for this snap proof. And the reason why this is still very efficient is because now you only to generate one single monolithic snap proof for one single chunk statement. So it's basically it's nothing. I think it's a negligible overhead compared to the all other works where you need to deal with a really really large statement initially.

And that means finally you can get some proof that's concise that's only like 100 kilobytes if you use the constant based fry based proofs. And it is also very efficient to verify. And if you don't care about post quantum security, okay, then you can even do better. You just use some other like pre-quantum snap scheme like Plonk or Hyper Plonk. And that gives you it can gives you something like 1 to 5 kilobytes proof sizes and very easy to verify. So in some uh the key takeaway here is we introduce this first last base folding scheme based on other commitments.

And finally it gives you some very memory efficient and post quantum secure snaps with ultra fast prover, small proof sizes, and really cheap verifier. Uh and before talking about open problems, I want to mention a concurrent work here. I think uh like Benedict and Pratyush, William, and Wilson they also mentioned they also presented this talk before in ZK Study Club. So what they do is they introduce a new accumulation scheme of folding scheme that's purely from hashing. And it's not based on this homomorphic commitments. Uh which is pretty nice because that means even you don't even need large crypto here. Even though in our case this large crypto is pretty lightweight, it's also pretty efficient.

But I think uh that's also not that's not going to be uh be more efficient than just doing hashing because hashing usually is a pretty efficient. Like SHA-3 is pretty fast. And they also mentioned some general optimization techniques for building piecewise marks that can equally well apply to Lex 4 to make it even more efficient. Um but there's one trade-off here. Uh in a sense that they will involve much larger folding verification circuits because they need to perform many, many hash operations because they are coding based. And that's where it needs to real large verification circuits. And the second, they only support bonding number of folding steps.

And if you give to fold more than bounded number of steps, there will actually exist some concrete attacks for that. While in this when this concrete attack will never work for for Nova, for Protostar, for Lex 4, or for Hypernova, for those homomorphic based um folding schemes. Yeah, there are Yeah um there's another relevant um concurrent work, I think, which is um I sent to the chat. That's um ePrint 2024 306. Um by Oh, I see.

Is it By I I sorry, I um I see. So, you are saying I I it's a Byang uh sorry, I I sorry, I won't butcher the the Korean names, but um I think what they're constructing is a homomorphic um lattice space commitment. Um I think they are PCS, right? Is that they are PCS? Uh sorry, can you expand uh PCS? Uh polynomial commitments. Um Are they Yes yes. Yeah, actually there are there are several concurrent work for that. Like, uh for example, I think Cothay they also have a a new paper uh in this crypto that build a more efficient polynomial commitment scheme from lattice. And this

is another one. I think you they also get accepted from by crypto. But there's a key key difference from their work with this work. Because they are mostly related like uh their their work is mainly for building a polynomial commitment schemes, which use some techniques from folding, but ours our scenario is more strict, like we need to build a folding scheme for this general MP statements. Okay? So, like you can use Ah, I see. Yeah, you can use polynomial commitment scheme to build a SNARKs, but like starting from polynomial commitment scheme from lattice is not pre-trivial that you can build a folding scheme for arbitrary MP statements. And the one key difference why it's harder is because you need to make sure after folding, the

folded witness is exactly in the same relation, has the same bound. There's no no slack, no blow blow up in in the in the witness norm here. But in their works and in both of works, they actually allow some kind of blow up in every round, because in a in a PCS, the number of rounds number of folding rounds usually is only logarithmic. Like Oh, I see. Yeah. So, so in that case it's fine to have some blow up. And as long as this blow up is small, then you can make sure this scheme is still quite efficient. And their their main contribution exactly they control this non-blow up in a better way than all the pre-pre-pre-state-of-the-art work, which makes this PCS um it more efficient than previous

lattice-based PCS. I think I would I would consider this some orthogonal work, which is not comparable. Yeah. Right, because that Yeah, the goal is different. Yeah. Oh. Okay. Um yeah, so also there are many nice open problems. And one thing I want to mention is like it would be great to have like some very efficient implementation for this and to justify its efficiency. I think like in terms of efficiency, I think it's quite promising. I guess the key question is whether we have enough number expertise for software engineer to know this very very deep knowledge about the lattice and FHE and to actually instantiate very efficient way. And then what I'm hoping

to see more implementation for that and make sure I finally see some really nice implementation for last vote, which I think is quite promising. And another question is whether we can do a folding for wider class of relation. So we already consider MP-complete relation. So like zero In theory, this is already sufficient. It can represent arbitrary computation. But for concrete efficiency, this is there's still some gap here. It would be nice you can directly folding this table look up relation, for example, very directly and very efficiently. That would be very useful for many applications like proving sha sha circuits or something like that. And I think this actually very promising because recently there's

a work called Lasso, which is really nice work that allows you to do a look up arguments from sum check. And actually their framework is quite compatible with our framework. Well, we both rely on sum check. And I I I totally believe that can be instantiated to last full setting as well. And finally the this question whether we can have a commitment scheme that satisfies these two key properties I mentioned before. First is compressing, which means you can compress long string to short string. And second, linear homomorphic. And in the last work, we have this one, right? We have a tie to satisfy these both properties. But the issue here is we have some norm constraints as mentioned before. And that's also the main reason why we need to go through

this like complicated route for doing splitting and doing range proof, right? But what if we have some really nice lattice-based commitments that has no norm constraint at all, but also satisfies these two properties? If that's the case, we can just like replace Peterson commitments with this lattice commitments and do nothing change on Nova or Protostar or Hypernova. And that would be great because you don't need to do any extra work, but uh you can already enjoy the advantage of using lattice commitments which have really lost a fast prover and the native uh ring operations, like uh really really nice circuits. And that can If that's the case, we can uh we can just replace like Nova with

this kind of a lattice low Nova. And the the the engineering work is minimal. You just You just replace these uh uh Pison commitments with these commitments, and you can just reuse the Nova implementation. That would be a dream goal, and in that case, I guess lattice low would be just useless, okay? Uh but I'm I'm I'm happy to see that happens because that would be making this scheme even better. Um but I think this is a really challenging question though, and that would be a great breakthrough if you can find we can find such a lattice-based commitment scheme. Yeah there.

I I mean, my my experience is that um it it's um what am I trying to say? It's always useful to to bear in mind um the ideas that have been used in previous work. Um so, it's not that it would be um useless because you can probably combine some of the ideas here Yeah sure. with the um the instantiation of um say Nova or HyperNova um with another lattice commitment um get something even better still.

Yeah. Yeah, thank you for saying that. Yeah definitely. But I think you This would be a really nice question, but I think it's a really really challenging questions because uh usually in the last word, if you consider this a CCA assumption, like you you have to consider some non-constraints somewhere. Like how to get rid of that is really really a a challenging Okay, yeah, I think that's it. Uh I'm happy to take a more questions now. And really thank you for for listening, and all I wanted to mention is that we are expecting to be update our ePrint draft very soon and I will keep everyone updated on Twitter. Yeah.

Uh what are the updates? Uh update means like uh previously we only give a sketch proof for for this folding which I only consider two to one setting, but now I give a more formal like more full proof for the two to one setting. It turns out to be actually not that uh not that trivial. Uh actually needs some care. And beyond that I also have some like fix some typos and add some other remarks for for details. Yeah. Yeah, and I would I would explain what other changes in the Twitter later. But uh I think that's a big major changes.

Yeah. Yeah, it's it's interesting to think about what the trade-off um say adaptive K is. Um So what? I think in our instantiation usually um there's a trade-off of K, but uh in our own instantiation usually um like you just make K you just make B to be small enough. I think that's fine because uh the bottom line as mentioned here is just sum check verify complexity. So So what's controlling the size of of beta?

Uh beta is related to the SIS hardness. This lattice hardness. So beta is Ah okay. Yeah, you cannot make beta too large because if make beta too large we will no longer have the binding property for the commitments. Yeah. Do you Do you know what that is um asymptotically compared to say the ring size? Or Uh you mean what's the ring size of uh Yeah. Oh, I see. I I guess I guess that's getting into too much detail about the the concrete hardness of um uh Yeah, so the SIS Uh we we do have some instantiation in our paper. I think we consider a 64-bit primes and uh the point of the ring has dimension about 64, I guess. Yeah.

So, you can understand the polynomial ring just as a vector space or module over a over a field, right? Over multiple field elements. And it's basically a vector field elements. You can understand as a ring using the NTT transform. And in our case, every elements field elements is some 60-bit 64-bit primes and there are 64 of them. And the actually, I think there if you like if you calculate more carefully, there can be more aggressive uh uh instantiation. For example, you can use just 32-bit primes with uh maybe 64-bit dimension. Yeah.

That's That's some kind of NTT instantiations. And one thing I do want to note here is that all our paper is only working over power of two cyclotomic rings. And this is usually the the case for most of the applications. For example, in FHE because they're super efficient. No, like power two like cyclotomic rings make the NTT to be really really efficient. And actually, I think this kind of scheme can be extended to more general case. Like you can use other prime fields and you can use non-power two cyclotomic rings. But I think it's just that we haven't formally proved it, but I think it should be work as well. Yeah.

Yeah, I I guess the other optimization parameter is the degree of the um constraints that you're supporting in CCS. Uh the the So, so dagger in the paper? Uh degree d g d g in the paper, that's that's the degree of the constant system. Uh, here what I mean is the d. So, you can see here, like this rq here, rq here, this is the quotient ring we care about, for example.

This would be a zqx divide divide modular x to 64 + 1, and this is isomorphic to fq to the 416. So, it's basically like uh it's like a uh dimension 16 vector to space with uh with the extension field of q to the 4. So, that's So, this 64 is the dimension of this of this ring here. Yeah, basically. Oh, I see. Yeah. Yes. And then actually, you might wonder Actually, this is a much hot larger than a single field elements, right? But uh but actually, this uh this is fine because one single ring elements can actually pack multiple field constraints.

Like you can pack multiple field elements. For example, here, you can it's basically one one ring elements corresponds to 16 16 field elements, and you can put 16 field elements inside, and you can represent 16 field constraints inside a one single ring constraint. So, it's actually uh pretty pretty efficient. The The reason you can So, So, how does the um the number of CCS So, the CCS constraint system is over which ring again?

It's over over rq. It's over rq. I see. Okay. Yeah. And one CCS constraint over rq can be used to represent 16 CCS constraint over a field. Right. Yeah. Yeah, I got it. Yeah. Um So, so is that basically doing a kind of a SIMD operation over the field elements? Exactly. Yeah. Huh. So, that is interesting how to optimize circuits in that model.

Um Yeah. Yeah, I guess you use similar techniques that you use in SIMD um outside circuits. Yes, yes. Exactly. Yeah. I guess that's uh like maybe creates a new word for for engineers to explore. It can be interesting, I think. Yeah. Yeah, I'm just looking at um the efficiency comparison with HyperNova processor in the paper. Uh I I very much appreciate that you've given um exact number of constraints here um because um that's the information that um the engineers need to uh um

ask, do I think I can do better than this on Yeah, and that's the in a given amount of work. Yeah, yeah. Yeah, thank you. And that that's some rough estimate, but I think can be some guidance for engineers. Yeah thanks. Yeah. Any uh any more questions from anybody? All right, awesome. Uh well, thank you very much everyone for joining today. Uh Dara, thank you for all of your thoughtful questions, as always. And you, thank you very much for this work and um yeah, really appreciate you

presenting today. Thank you, Alex. Looking forward to having you back. You you've become pretty prolific with these papers, so I guess we'll be having you back here without without too much delay. Um Thank you, thank you so much. Yeah, yeah, cool. Thank you guys all very much.