ZK13: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems

Transcript

[Music] Hello everyone, my name is Bing Chen. I'm a researcher at Stanford. Today I'll present Lasso Plus which is an upgrade version of Lassfold that enables fast and memory efficient proof system for large scale computation. And this is a joint work with professor Damon. Okay. So in the snark world we have three main approaches to build efficient proof system. The first one is this ellip curve based ones such as grossing or plunk. So they have really small proof sizes and very fast verification time and it's also much very simple to build a phoning scheme

out of its such as nova and protostar and hypernova. Unfortunately, this kind of scheme rely on this discrete log assumption that is um vulnerable to quantum attacks such as sher attack and moreover the prover time is slightly less efficient because of the use of large arithmetics over ellip curves. Now in the postcontum word we have two other categories. We have hashbased uh proof system that is widely used in practice and pretty popular now because of this fast verification and efficient uh fast proving time and efficient verification. Unfortunately, when it comes to build a recursive proof system or folding scheme, even though we've witnessed great progress recently,

it's still very challenging to build a concrete efficient scheme because of the really large recursive verified circuit. Finally, we have this last space ranch proof uh less space based snarks which can potentially achieve even better proof sizes than hashbased ones because they rely on this more structured algebraic lattice assumptions. However, the downside of this kind of scheme is that verification usually is much slower. This limits it usage in blockchain space. But today I want to mention that lattice is actually great fit and great tool for building folding schemes and leads to a really fast folding scheme such as last 4 plus I mentioned today and also it's possibly postcon secure as well as a

motivation I want to mention why one very interesting exciting application of last plus which is a beam chain so beamchain is a proposal by ethereum ethereum for long-term security against a quantum attacks and also scalable consensus. So the idea is that after proposing a block in consensus there will be a bunch of validators who will ver read verify and design these blocks using some postcom signatures such as the standardized lattice space signatures and then will be aggregator who collect these signatures and build a succinct proof showing that these signatures are valids are correctly verified. Okay. And

after publishing this short proof, this blog can be confirmed. So this boils down to this research question of bu of building a much more efficient proof system that's able to fold many signature verification statements into much smaller one and finally compress the statements into much smaller snark proof. And I claim that lat space folding is a great fit for such application. For example, as plus exactly address this problem for two main reasons. First is a fast and postconquing scheme and second it natively supports proving algebraic lice operations. So B basically this constraint system is particularly fit for just proving lice operation. You don't have to do this arithmetization to

translate this lattice ring operation into some uh constraints in RNCs over snark friendly field. So this makes a great fit for doing um like for this kind of application where you want to verify stuff such as um signature verification for latises or uh verifiable FH. Beyond that I believe there are can be more advanced application as well such as ZKVM, ZK machine learning and data provenence. All this kind of advanced application involve proving large scale computation and our goal is to achieve that using small of amounts of time as well as small amounts of memory. So to do that I think like the the direction could be using lastbased

folding combined with hashbased nark in the end for example and then I want to mention that for lasso plus it has three really nice features here. The first is that the system itself the proving complexity is not much more complicated than just committing to the weakness and this is like a great features for uh folding scheme in lefth words such as nova and second the commitment scheme itself is highly parallel hardware friendly and supports more field arithmetics this something that can be even better than this pattern commitments and finally is plausibly postcom secure as well compared to the predecessor circle last fold. We believe it can achieve much faster prover as well as much

shorter and simpler verified circuits which is uh affecting the folding statement size which also indirectly apply um affect prover time. So we really believe that this can be a promising direction and hope that can be more and more research onto the lad space proof system and following scheme and this won't be the last scheme I think there will be more uh advancements in the future I hope. Okay. So in the following I will quickly go around like go with go through some quick background about phoning scheme and let's see how last 4 plus will work. Okay. So in the literature we have one generic approach to build memory efficient and fast proof system for large scale computation. The idea is

simple and this is also uh this called a pism snark and also known as IVC or PCD. The idea is to like you have some computation you want to prove and you just split these large computation statements into many small chunks and then you stream the proving of each chunk statements and combine them together or fold them together into much smaller statements and further compress it into a small proof and this small proof will serve as a snark for this large scale computation. So the qu research question is then how to fold these statements efficiently. And this is where folding schemes come into play.

But before that I want to mention a more general notion called reduction knowledge. And reduction knowledge is a proto code that allows you to reduce the checking of some input statements in some relation R1 into the checking of some output statements like update statements in output relation R2. where R2 is usually much much simpler to check than the input relation. So you can reduce some harder problem to some simple problem and snarks exactly one such example where output relation is just this trivial language which always output one and fing scheme is another special example. So in fing scheme the input consists of two statements. The one is this online chunk statement you want to absorb. The other one is this

accumulated statement. You want to keep absorbing this online statement and finally get one statement for it. So the following protocol basically what he does is to combine these two statements into one updated merge statements in this accumulated relation and you can keep absorbing these online chunk statements one by one and finally you can absorb all their online chunk statements and you finally just need to compute or prove this final smaller statements. So as you can see this operation is no longer trivial even though it's still simple it's no longer trivial. So the task for folding protocol is slightly more easier. Okay.

And that that is the reason why usually fing scheme is much more lightweight and more efficient than monolithic snarks. For example, according to PSC's benchmark, Nova is like 100 times faster than this ellip curve counterparting snark words like Halo 2 or Plunky 2. On the other hand, they are also powerful enough to support this peace meal proof system as I mentioned before by combining with snarks in the end that like prove a much smaller statement. So in this landscape folding scheme we also have similar categories. First we have this like classical elliptic curve based folding scheme such as protoar and nova and hypernova.

They're pretty simple, pretty elegant and leads to some uh really simple verified circuits and proving time is also not much more complicated than just committing to witness using pedest commitments. Unfortunately, the they're not um postum secure and also the commitments is slightly less efficient because of the large field arithmetics over ellip curves. Now in the postcontum world, we also have this hashbased and lastbased folding scheme such as arc and lastfold. They have much faster commitments. They are also possibly postconom secure.

However, the end to end system now is much more complicated than just committing to the witness and just do some random combination of commitments and witness. This ma make this kind of scheme finally like less concretely efficient than this ellip curve based folio schemes. So in this work we want to strike a balance and achieve the best of both world. We want to inherit the fast commitments and postcom security. But also we want this proving proving system to be not much more complicated than just committing to witness and randomly combine the corresponding commitments and for that I would need to um provide a quick framework describe quick framework for building lattice place folding schemes. This is already

inspired by hypernova and also already implicitly described in laz fold but I think it's nice to have this generic framework so you can have the high level picture and after that I will touch upon the core technical part which is a new ranch proof in the algebraic lab setting okay so our starting point is hypernova which is a following scheme that's uh uses homorphic nearly homorphic commitments and sack the idea is that you start by convert this high degree committed MP relation into some linear relation that only checks some linear statements and then you randomly combine two linear statement into one by just using some random combination of the homorphic commitments and the

witness and also sometimes you need some sack protocol out of it. So this is pretty simple and they instantiate using pattern commitments. Unfortunately, as I mentioned before, passive commitments is vulnerable to quantum attacks and also is slightly less efficient because of this ellip curve operations. So, we instead use less space commitments or at hashing functions instead. Uh is actually very elegant and simple scheme and there are also some variant of it that's much more comp uh optimized and efficient than that. So but at a high level the idea is as follows. To commit a long weakness vector what you do is just to left multiply a random matrix which is a narrow and long and then you get a

narrow column which serve as short commitments. And a nice feature about this is that this matrix A which is public parameter can be generated on the fly. You don't have to store it in the memory when you commit it. You can just generate it locally every entry using PRG or PRF. And this makes it extremely hardware friendly and GPU friendly. Uh and also we have some variant of this kind of scheme using polinomial ring or module that leads to much more efficient scheme. And according to Nethermind's benchmark even on a single threaded CPU this can be much faster like three times faster than pattern hashes for committing to the same amount of data.

And I hope that this kind of gap and advantage can be even larger if you use GPU or hardware. and other on the other hand is also plausibly postquantum secure because he relies on this well-known shortest integer solution assumption that's widely believed to be quantum secure but there's a trade-off there's no free launch the trade-off here is that we require this witness to be no norm otherwise this assumption will be broken it will longer be true and the security will be broken so that implies that every element of this witness should have a relatively small absolute values and that also means when we do the folding when we do the random combination we always need to control this norm to never exceed some fixed

threshold otherwise you can no longer fold afterwards and you won't have security so to address this issue uh we adapt this u relation we want to fold to include this nom check statements which further check that indeed this witness are indeed no norm which is parameterized by this integer bound B here and then after converting this uh high degree committed empty relation into a linear relation. We define this accumulate relation as a product two statements which is our two linear statements that parameterized by this integer bound B prime and B prime is a globally fixed uh parameter that never changes. We always want to make sure that we never increase this kind of non bound. And now we have three input

statements and we can do something similar but the different here is that we use some non-normomial ring scaler to com to combine these three statements into a new statement where the weakness now is slightly larger. The norm is slightly larger but not much larger. But as we said before I need to correct norm right but this is easy to do. We just split these statements into two using the so-called decomposition technique. Basically when you have a number when integer you can decompose into two integer where the two values become smaller. And this is some technique used last fold. But why is special about last fold plus is that in last plus we only do this once uh in decomposition and we only split one statement into two. While

in last for uh last fold for some technical reason we have to decompose them into many small decomposed commitments which makes the efficiency of the phone scheme much worse. Okay. So all this sounds pretty natural and uh uh simple and also quite nice. But there is one challenge here in the sense that you also need to further prove that in this folding step this input statement are indeed having no nom witness. So in some sense you have to provide a proof of knowledge that these inputs witness are no norm and this is always the hardest part for building a last fall foring scheme and that's why it's like no notoriously hard to build a very efficient last space proof system of fing

schemes and this is where our key contributions comes in. We obtain a much more efficient range proof that is fits into this algebraic life setting uh and which I think is of independent interest. So to illustrate the idea our first step is to uh represent a ranch statement as as an algebraic operation. Why do we want to do that? Because algebraic operation or statements much easier to prove because we can use this polinomial and all kinds of tricks related to polinomial and algebra. And what you do typically is that suppose you have the statements about proving a is inside half minus half d and half d. What you do is decompose this value into a binary

vector. Prove this a binary vector is consistent with this value and prove that binary vector is indeed binary that leads to um many different cq multiplication. Basically prove that ai * ai minus one equals zero modal q. So in some sense given the one ranch statement you translate into multiple algebraic statements over zq. And this kind of kind of laws we don't want to do this. want to translate one ranch check of this form to a single algebraic operation. And the nice thing about lad space folding is that we work instead of a zq we work over polinomial ring and this is rq here which we want to exploit. So pretty simply very simply uh the every elements of rq is just a

polinomial of degree less than d. So you can add two polomials and you can also multiply two polinomials and modul this polinomial x to the d + one to obtain another polinomial of degree less than d. So in some sense it is a ring that supports addition and multiplication. And another nice feature here is that you can also shift the coefficients of the polinomial onto the constant term by multiplying this x to the a monomial monomials uh here which is is a great feature because you can now do shifting very efficiently to the coefficient. So this is where we want to exploit and our goal is to represent the ranch into just a single

ring multiplication. The idea is following. First, we define this table polinomial TX which embeds the value of this range inside coefficients of this polinomial to the corresponding uh different monomial terms. And then we introduce some helper values which is this delta a which looks like some x to the a monomial term even though um like more formally it is not exactly like that but let's just assume for simplicity is uh almost x to the a and now we are ready to represent the ranch check statement just as one remlication. The idea is just to check that the constant term of data a times multiply this tx equals a. Why is it work? Because essentially this delta a

is working as to shift the value you want to check onto the constant term. You can basically extract this terms this coefficient onto the constant by multiply x to the a or something x to the minus a. And then if the constant term equals a that means a is inside the table right because like is is equal to some value inside table. So this is why we can represent a ring uh a ranch check as a ring multiplication. And this idea easily extends to arbitrary table lookup or even larger ranges by just embedding different values in this table polinomial and using this decomposition technique from lasso or something uh like that. So this is a high level idea.

We're now ready to represent uh ranch check as some algebra operations. Um and now let's come to our main tech me task. We want to prove knowledge of opening vector such that this opening vector is opening to the commitments and moreover every elements of this integer vector is within the range. So as I said before given this insights it's basically just checking that this vector f uh element wise is equal to the constant terms of tx scalar multiply this delta vector right so basically we want to prove knowledge of t and delta s this equation host this basically a headmar check and for some reason we want to transform this into a

single room multiplication check using the schwazi polma let f tilda and delta tilda to be the margin extension of this vector and and let R to be a random sampled uh point over ZQ to log N. Now it's suffice to just check that F_sub_R equals to the constant term of TX times delta to the R. Okay, like this we can preserve the soundness using shripy polma and this is high level idea. Basically we convert this kind of a range check for long ve vector into a ring multiplication. But proof more formally this leads to the following reduction knowledge protocol where the prover just send this helper commitments which consists of commitment to this delta vector which consists of many

monomials. Okay, which is lifting the values to the x to the a from a and the verifier will after receiving this sample is random challenge and the prover will give the corresponding clam evaluation and the verify assume this valuation is only computed just check this single replication and if it holds true then after that it is suffice to just check that we know the some relaxed opening of f and delta to the these two commitments such that the corresponding evaluation claim holds. I want to highlight here that this relaxed commitum opening relation is much easier to prove. It's basically very similar to a statement to be proved in hypernova which requires no strict ranch check as we said before and is much easier to

fold using random combination. So this protocol kind of work as a ranch proof for uh as a reduction knowledge for this uh vector f here. And also we can see this scheme is extremely lightweight. The prover needs to commit these monomial vectors. And because this monomial vector is really sparse, right? And also very structured. When you instantiate ringbased atta commitments, this can be really efficiently computed leads to just linear number of ring additions for example rather than ring application which is much more expensive. So this is pretty good and the verify is also pretty simple. It just sample a single challenge and check one application. So the corresponding

verified circuit will hope that can also be really small. However, I'm cheating a little bit here. Okay. Uh this works when the prover is honest. But what if prover is malicious? What if he send some commitment that is not monomial vectors? Why you send some arbitrary polinomials instead and full verify? So we need to further enforce that the malicious approver is always committing to some monomial vectors so that these previous algebraic statements will will make sense. Okay, but fortunately we can do that and we do it very efficiently. We come up with a new monomial set proof which is a proof of knowledge of this uh monomial vector under the line commitments which is super efficient. Uh I don't have time to cover this here but

I think it's really cute technique and catch me offline if you're interested but one thing I want to highlight is that the underlying protocol is just a sum check over field rather than RQ. So the sum check is actually pretty efficient and insignificant compared to committing to this ring vector. Okay. So for now we know how to prove knowledge of committing integer vector which is within the range. But in practice for efficiency usually we are directly proving relation over latis space rings like algebraic polomial rings and that means the weakness we have is actually some ring elements or polomials. So it's a vector polinomials rather than a vector of integers. So actually we want to want to uh prove is

to prove a knowledge that all the coefficients of these polinomials are within the range. So that leads to a much harder problem which is to prove d different integer vector are within the range. But naively you can just run this ranch check protocol we had before for integer vector for d times in parallel. Right? And the proof of time is not too bad. The monomial vector commitment is pretty efficient. And this monomial set check proof can also be batched using randomly combination. So it's not big deal. But there are some other subtleties in the sense that communication will increase a lot. Okay.

And the prover has to send more more and more commitments one per commitments per vector. And as you know that we need folding verify circuit to be really small. But when you instantiate you need to do fe shamir to sample this random challenge which needs to take all this input as input to generate this random challenge. If it's too large, fear shamia circuit can be quite large. And our approach to dealing with it is to use so-called double commitments which allows us to compress a matrix of n by d into much smaller commitments rather than d commitments. The idea is simple.

So after getting this d different commitments, you just decompose it as a as a scaler. Decompose it and we should a long slightly longer vector. And now we can use this at hash function I mentioned before again to obtain a much smaller commitments. So as you can see we can compress a one megabytes commitments into a 10 kilobyt commitments and much shorter and the verifier will only receive this double commitments before example this random challenge. So f shame will be much more efficient after that. But this there's still one subtle challenge here is in that after doing the reduction knowledge we obtain some statements that's related to double commitments but double commitment is not linearly homorphic. So we cannot easily using randomly

combination of the commitments to fold the statements. So that's why we need one more technique to translate a statement relating to double commitments into a statement related to this folded version of lattice space commitments and this is also of independent interest. And after that we can continue folding without problem. Okay. So that's basically the idea of rent track protocol. In summary we have three main components. The first one is this table polinomic extraction technique plus this monomial proof that makes the prover much faster than before because we remove the need of computing many decomposed uh vector commitments using attack commitments. And second, we use this rand uh double commitment trick to

compress the folding proof so that we can have a much smaller F shamia verified circuit which makes the uh folding statements slight um much smaller. And finally we use this commitment transform trick to translate double commitments into linear commitments which allows us to do polomial unbounded unfolding afterwards. So you can fold many many online statement as you want and if you plug in this ranch checker protocol into the framework I mentioned before this leads to a much more efficient lastbased proof system uh or folding schemes because this ranch checker protocol itself is no longer a bottleneck of efficiency. So we claim that the actual complexity will become uh like a bottleneck will become

just to committing this witness ring vectors. Okay. So that's basically I want to cover. Uh how many minutes I do I have? Okay. So I go quickly. One thing I want to convey here is that this lises is uh like mathematically it's a really deep topic. It's really interesting and it involves a lot of deep mathematics but I don't think it's that scary. It's not that fancy. Also I saw Craig here which is like OG in the in the last word. Um and I hope that more people can use it because it's really powerful and helpful to use for example in folding schemes. And according to Netamine's rough estimates, we believe that Lasso Plus can even beat the state-of-the-art of ellip curve for scheme such as hypernova even just on a single thread

CPU. And we believe this advantage can be even higher if we use GPUs or hardwares. And moreover, it's plausible postcon secure. And one thing I want to mention here is that also it can natively support proving lattice operations without like diving into like some indirect translation into RNCS constraint over fields. This all makes it a great feat for those applications that you need to prove operations such as beam chan or verifiable FHE. Uh I think I'll just stop here and like there's many open question but one thing I'm think most relevant for investors and company engineers is whether you can have faster software and hardware implementation for the monomial vector

commitment I mentioned before. If you can do that you can accelerate this last even further and you can get get even better uh performance. Okay I think stop here and thanks for listening and I'm taking more questions now. Thank you very much, Bini. Um, we'll take one question and then I think the rest we'll take offline. Um, because Oh, sorry. Go for it. Thank you for the talk. It's super awesome and interesting work. Thank you. Um, with folding scheme more generally, what you have is great memory efficiency. So, you can choose the step size to match machines. Uh, so if you have a bigger machine, you can do run bigger step sizes, smaller screen, smaller step sizes. But in the hyperver

paper they actually added folding for zk as in you can fold something and add privacy to it. I thought that was a very interesting technique. Do you know in the lattice space setting if you can add privacy via folding in the same way? That's a good question. So you question can we add CK or privacy property for these kind of schemes? I don't see a inherent obstacle. Um but we haven't thought much about it. I I think it should be possible. For example, I think in the in the li curve setting, we do have some kind of rel this kind of work. But in the last setting, maybe you can also do that. But probably we need to have some rejection sampling stuff which is more complicated in last word. I haven't thought about this. I think a very interesting questions. Yeah. Thank

you. Thank you very much, Bingy. [Applause]