ZK Whiteboard Sessions - S3M4: LatticeFold, w/ Binyi Chen

Transcript

All right, well, welcome back to ZK  Whiteboard Sessions Season 3. Today you'll have me, Guillermo, I guess I'm the  Chief Scientist at Bain Capital Crypto, that doesn't really mean anything, I just do  math, but we'll actually have someone much more important, which is Binyi Chen. Binyi  is a postdoc at Stanford under Dan Boneh. He was the Chief Cryptographer  at Espresso prior to that, and has done a bunch of work you probably have  heard about, things like Blaze, things like LatticeFold, which we'll be talking about  today, and things like BaseFold. So Binyi, feel free to take us away, I know we're going  to discuss some different parts of this, so feel free to outline what we're going to  talk about today, and then let's get rolling.

Sounds good. Yeah, thank you so much, Guillermo,  for the introduction, and it's a great pleasure to be here. Today I'll talk about LatticeFold,  which is a folding scheme based on lattices. And folding scheme is a very useful primitive  to help proving large-scale statements in a memory-efficient way. So the outline today  will be, I'll categorise the part into three sections. So at first, I'll give some  background about polynomial rings, and I'll use these polynomial rings  to build some Ajtai-based commitments.

Yeah, and it's Ajtai, not ‘Ahjtai’,  as I always keep on referring to. Yeah, and after that, after equipping this with  these tools, we'll touch upon our primitive to build folding schemes. So we'll talk about folding  and especially folding in the lattice setting. Along the way, we'll see many challenges, so we'll  go over some main techniques to build folding schemes in the lattice setting, such as using  decomposition technique, and more importantly, we'll cover another very important topic,  which is range proof in the lattice setting. I mean, yeah, LatticeFold is interesting,  right, because normally we're either working over finite fields, or we're working  over some sort of commutative group,

in the case of, you know, elliptic curve,  or things like that. Here we're actually going to be discussing a generalisation of  groups, but specifically polynomial rings, which will have some interesting  properties in themselves. Exactly. Yeah. So, okay. Cool. I think  we're ready to get started. That sounds great to me. Great. Maybe we can get started for the first  section now. So maybe I'll just erase this, and let's start with polynomial rings. Sounds great. So in the lattice setting,  actually, these polynomial rings are very useful, not only because, as you said, it gives better  security, actually also gives better efficiency.

So polynomial ring, you can understand  this as a generalisation of integers. So in the SNARK setting, usually we're  working over finite fields or integers, but actually in the lattice setting, for  efficiency construction, we'll do polynomial rings. So we'll consider mostly about this kind  of cyclotomic rings, which is defined to be the integer polynomial divided by this ideal of  x ^ d +1 , where d typically is a power of 2. So, yeah, can you, I mean, I  think I know what this means, but let's actually carefully define what this is.

So maybe give you some intuition what exactly this  means. So you can understand at first, this can be understood as a set. You can understand this  as a set of polynomials with degree < d, right? Because every time you will do  this, if you do some modular, and you will get some polynomial less degree  less than d, and all more vertical efficiency will be integers. Okay, so this is  a kind of infinite set. But we also, the nice thing here is that this also is a ring,  because we can endorse arithmetic over the set. For example, if you want to do addition,  you have two polynomials of degree < d, you can add them up to get a new polynomial  of degree < d by just adding the corresponding coefficients of every degree. So that is a  simple one. But how to do multiplication, right?

So the multiplication is slightly less trivial,  but still we can define how to do multiplication over rings. So if you have two polynomials, a(x)  and b(x), both of them are integer polynomials, integer coefficients, and degree < d, and what we  do is that we first multiply these two polynomials over zx, and we'll get a polynomial of  degree > d now, right? But that's fine. What we can do is that we  can do polynomial division, if you know that this polynomial can do  division using this. So we can write down this polynomial in the form of f(x) times  (x^d + 1) + another polynomial g(x), okay?

And this gx is called the remainder polynomial,  which indeed have degree less than d, right? And this will be the result of  multiplication. And that's another element inside R again. So this endorses  the arithmetic for multiplication as well. So another way of seeing this, maybe of  rephrasing this, is if I have 2 polynomials each of degree < d, when I multiply them, of  course I'm going to get a polynomial potentially of degree > d, but of degree < 2d. And what we're  going to do is we're going to essentially take every power of, you know, we're going to get a  bunch of powers. Some of them are going to be > d.

Let's call it d’. Then each of those  powers, x ^ d’, gets mapped to x ^ d‘ - d, right? That's what we're saying here,  or negative that, I guess, with this. +1. Yeah. Yeah. So roughly every power, every time you go above x ^ d, every term that  contains x ^ d gets mapped to - 1. Exactly. Right. So that's what we're saying here, and  that's what this result gives you right here. Yeah. That's also a valid  understanding as well. Yeah. Cool. Right. And so we always end up, of course, once we multiply 2 polynomials, the  resulting operation as you've defined it always ends up with a polynomial of degree < d. Yes. Okay. So this is a ring, and also, as I said, this is an analogue of integer, so we  can also define a really useful metric,

distance metric for R as well, similar as we did  for z. So we can define a norm for R as well. And today I'll focus on a special  example of infinite norm. So for example, we can define infinite norm of elements in R  as the following. So given a polynomial a(x), which is a0 + a d -1, x ^ d - 1, the  infinite norm of this is defined to be just the maximal value, i from 0  to d - 1, the absolute value of ai.

And you can trust me that this  satisfies all the properties of norm, such as triangle inequality and so on. And  this will be very useful later when you want to analyse the hardness of some problem  and reduce this problem into some lattice problem. And this is something that I think  Vadim has mentioned in last week as well. So very quickly, right? Yeah. So norm  satisfies whatever triangle inequality. For rings, do they need to satisfy  anything more for it to be a norm, right? We have homogeneity. So if you scale, so we can think of a0 to ad - 1 as a big list  of elements, a vector in other words, of size d. The norm is the max norm, which is a common  norm. Certainly it satisfies triangle inequality, homogeneity, and self-reflectiveness.  In other words, if a thing = 0,

then the thing itself must be 0. Does it need to satisfy anything else in the case of a ring or is that enough? I think it's just the same definition. It's the same definition as for vector. And also there  are many ways to define norm for a ring as well. You don't need to consider infinite  norm, you can consider L2 norm, Lp norm, L1 norm as well. So just for simplicity,  we consider infinite norm today. Okay. Perfect. Okay, so this is about a polynomial ring.  And similar to in the integer setting, usually we are not doing integer  arithmetic in SNARKs. We're doing finite field arithmetics by modulating  some prime q there or like a power of 2. We can do exactly the same thing in the ring  setting to make arithmetic more efficient.

So that's why usually typically in CPU or  in GPU, we are doing arithmetic over RQ, which is defined to be this quotient rings or  residue rings, which is R divided by qR. So we can understand this as very similar to R, except  that these are those polynomials with degree d for which the coefficients are mapping to this  small interval or at least represented as Zq, which is defined to be this interval  - q/2 and q/2 intersect integer. So that means that every coefficient  now is mapped to this small interval or this Zq arithmetics rather than  integer arithmetics. And that makes

it much easier to storm, much  easier to do arithmetics. Got it. So, okay. So yeah, we  have like four things here. So we start with the polynomials. So this  is like any polynomial which has integer coefficients. We essentially now do  this modulo right over this ideal. In other words, it's just claiming that any  term x ^ d becomes -1 or another definition is this. And then what we're going  to do is we're going to take this R, right, and we're going to take a second modulo, which is modulo q times R, which essentially  says, in other words, every time... Yeah. So we need to carefully define what  addition means here. I'm not 100% sure.

Oh, yeah. So you can understand this as 2 times, like sequential. First you can define arithmetic  of R, and after that you can do another modular. And what do you mean modular? It's just modular  every coefficient with q and that's done. Okay. Yeah. So yeah, so exactly. So we're just essentially now performing not  just, you know, polynomial multiplication. When we multiply polynomials, we get modulo  this, but now every time you also, you know, add coefficients together or multiply coefficients  together, you also take that modulo q. Exactly. Right. And q here, very  importantly, is not a prime. Yeah. It doesn't have to be a prime.

Right. And however, in some of construction, in order to make some property  host, you have to make it a prime. Right. Yeah. Right. Right. So in our case, q will be a  power of 2, which is decidedly not prime. And so this, you know... So d with a power of 2, but q... Oh, sorry. q is distinct from d. q is a modulus. Got it. Got it. In our construction  today, it will be a prime. Okay. Okay. But in general, it can be  anything. Interesting. Okay. Okay. So that's about polynomial ring.  And I want to mention another thing that we have a very efficient,  good efficiency property for Rq. So maybe I can erase the R part.

Sure. Go for it. Okay. Yes. So there's a nice property  about Rq in the sense that first we can pack multiple Zq elements into  one Rq element. That's pretty natural. Like one natural in packing is just that  you have d Zq elements, you map them to the of polynomial. And second is that we have really  fast multiplication. Fast multiplication over Rq.

So given 2 polynomial, we can compute the  multiplication of 2 polynomial in a much faster way. And essentially the complexity  is only O(d) log d Zq operations. Right. And that's just the observation. I  assume that polynomial multiplication is the same as convolution. So you  can take the Fourier transform, get pointwise multiplication  and the Fourier transform back. And another way to view it is that you  can understand that for every polynomial, you can define the coefficient vector of a  polynomial, right? So coefficient vector of A is in Zq^d. And you can understand, as you said,  the polynomial multiplication is just convolution.

And essentially the coefficient vector  of a times b is just the convolution matrix of a times the coefficient  vector of b. And this convolution matrix looks like something like  this. So it's a circular matrix. Yeah, it's anti-cyclic matrix, which is a_0 to  ad _- 1, and - ad_ - 1, a0 to ad _ - 2, so on, minus a1 to a0. So this is a matrix  of d by d. So naively it takes d square operation to compute this  matrix vector multiplication.

But because this is so structured, you can  use some like FFT or other algorithms to make this matrix vector multiplication  much more efficient in log d time. So yeah, quickly speaking maybe a little bit  more about this is the observation here is, of course, you can treat much in the  same way that we were talking earlier, right? You can treat the coefficients of this  thing as a vector. These are equivalent views. And certainly now we actually  can really say what this means, right? This also means not only when we  take the L infinity norm of polynomial, we are actually taking the same exact thing  as the L infinity norm of the coefficients.

Yes. Yes. But here when we do Zq, we cannot  define the norm, but when it's Z, we can. Yes. We have, yeah, Zq is like, this norm  is like in some sense depends on exactly how we choose these, I don't know what to call,  representative elements or something like that. Okay. Okay, cool. So that's  all the background I want to talk about polynomial ring, but the  question is why it's useful, right? So I will then give you an example  on commitments. So last time Vadim has talked about how to compute a, construct an  Ajtai commitment in integers, and it turns out there's a variance that's much more efficient  than that using polynomial rings. Interesting.

Also, by the way, feel free to write also here if you'd like or anything of the like,  you know, the board is all yours. So I can, maybe I can write up there. Yeah, I'll give it to you. Okay. Cool. Okay. So let me quickly remind you what Ajtai  commitment is, since Vadim has already explained this in the last episode. So in  Ajtai commitments, we have a data vector, which I write it as a long vector f,  which is integer vector of length m. Okay.

And moreover, in this added commitment  setting, we have some extra constraints that norm of f should be less than some bound. For  example, we set it to be the bound B here. Okay. And our goal is to commit this string and  compare this long string to a short string. And the Ajtai commitment's idea is that  we can randomly sample a public matrix A, which is a uniform example from Zq ^ n times m, where n is some parameters that you can choose  depending on the security level you want. And then you do this arithmetic and mod q, and this  will give you a commitment, which is in Zq ^ n.

Okay. And typically, n is much smaller  than m, and typically in practise, n can be 500 or 1,000. So it has many nice  properties, such as compressing and binding. Binding is hard to find the two different  vectors that map to the same commitments. And third is kind of homomorphic, because  these are linear operations. But this is not widely used in practise, mainly because the  complexity of computing this is not very good. It takes about n, m, Zq operations, right?  Because there's a matrix vector multiplication, which takes n times m. And n, as I said before,  in practise is like 500, which is pretty large.

So actually, it turns out that we have a  better way to do it. This is called SWIFFT, SWI-FFT. And the idea is  actually very similar to this. So let me explain to you  how does it work. So first, you can understand this is the same kind  of data f here, okay, which is the integer of length m. But another way to understand  this is to partition it into many chunks. Well, every chunk consists of d, c, the  integer s. And with these c integers, you can understand it as a single ring  element. So the other way to look at this,

to understand this as a vector of ring elements  of length l, where l is m divided by d. And now we want to commit this ring vector,  and we do something exactly very similar as before. By this time, we sample a random  matrix over Rq with dimension kappa times l, where kappa now is defined to be n /  d. Okay, and I do arithmetic modulo q, and I get another commitment over Rq  kappa, which is of the same length.

Are there any differences in security between  SWIFFT and the standard Ajtai commitment? Because here, obviously, this is uniformly random. This  is obviously much more structured here, right? This is much structured. Exactly.  That's a very good point. So you can understand this  as a special case of this, where this is a more structured random matrix  rather than fully random. But it turns out both of them can be reduced to some kind of  lattice problems. But this can be reduced to some kind of more structural lattice  problem, for the ideal lattice problems. But those kind of problems are also  believed to be quite hard. At least for now, we don't see any better attacks than  attacking these more general lattices. I see.

So people believe this is still post-quantum secure. But it gives us a  lot of advantages in terms of efficiency. So just really quickly, this problem is hard.  In other words, finding two different things that hash the same thing is hard because  it reduces... Small norm, by the way. Sorry, very importantly, small norm.  Because it reduces to the... What is it? SIS. That's right. Shortest  Integer Solution assumption. Okay. Which are finding some short vector  such that it lies into this lattice, which is a lattice that makes sure that this vector, A  times this vector equals 0. And here it's similar, but the only difference is that A is a  ring matrix rather than integer matrix.

All right. Okay. Yeah. So that's it. And why we care about this? Because  the complexity of computing is much faster. It takes about n kappa l ring operations.  And if you look at it, one ring operations is only take d log d Zq operations. So  this is n, d, m, d, d log d, Zq operations. And this is much faster than this. For example,  if you set d to be n, and this will cancel out, and this will cancel out, and this will be m log  n. So this will be about m log n Zq operations.

Right. And this is much smaller than n. If we go 1,000,  this go to 10. It's like hundreds speed up. Right. All right. So yeah, one thing here, right, is obviously this is the case  where d equals 1 is this up here. Yes. So my guess is as you make d larger, you end up with kind of slightly weaker  security guarantees would be mine. Yes. Yes. There's a trade off, right?  There's tuning parameters. Sure. And in the middle is called a module  lattice problem, and the extreme is called a ring lattice problem. Sure. The  most general case is integer lattice problem.

Sure sure sure sure. And yes. So, and another way to understand this  matrix multiplication is that we can understand it as convolution matrix of A, like rot (A) times  f, where f becomes integer. So we are right here. It's like, yeah, maybe just f equals cm.  Well, now this rotation matrix A is just a dimension of CQ and m. Well, it  consists of several sub-matrix, right, where every sub-matrix is  the rotation matrix of AIJ there.

So there's another view, way to  view this kind of multiplication in the language of Zq as well. So  that's something I just want to mention, that later we might be, this kind  of view can also be useful later. Okay. I think that's all I want to cover in this  commitment setting. And next we'll see something that's more exciting, that how to build  folding scheme using this kind of commitments. Right. Yeah. Very, very cool. So let me start by recapping the notion  of following scheme very quickly, because I think in the season two, Albert  has mentioned this as well. So what is folding? Folding is a primitive that has been  introduced by Nova and another paper in 2021.

So this is Nova and there's another  concurrent work by a group from Berkeley and Stanford. So they are defining  these following schemes. So intuitively, the idea is to, we want to check  the correctness of 2 statements. And we run a protocol to reduce the checking  into a single, simpler statements. So slightly more formally, suppose you have some statements  you want to check, which involves an instance x, x_1 and w_1, for which you want to  check that it's in some relation, say R, which we'll define later.  And you have another statement, x_2, w_2, and you want to check it  is in another relation, say R star.

And your goal here is to run some kind of  protocol between a prover and a verifier, or in a non-interactive case, it's  just a proof. So in this protocol, the prover and the verifier will run some  public coin protocol, means that verifier will only send some random coins in every  round. And they both know the instance, x_1 and x_2, and the prover additionally  knows the corresponding witness, w_1 and w_2. And at the end of this protocol, if the  verifier accepts, then the verifier will convert two instances into a new  instance, x. And at this point, now it suffices for the verifier later to  check that the prover knows a witness for this instance, x, which is w, that is in  the relation R star. And how do you get w?

The prover will just convert these 2  witnesses before into a new witness here. The idea essentially is you have a bidirectional  here, right, where it's this new instance essentially fits here, roughly, if and  only if, with some probability of error, each of the original instances must  have been satisfied in the relation. They satisfy some property very similar to  SNARKs, for example, completeness. If the inputs are correct, then output will be correct.  And soundness or knowledge soundness, if either one of these is incorrect or prover doesn't know  the witness for the corresponding statements, then either verifier will reject or the prover will not  be able to prove knowledge for this new instance.

So that's called soundness or knowledge soundness.  And moreover, it satisfies succinct property, meaning that its verifier complexity should  be very small. So the verifier complexity should be sublinear in the size of the sum  of the witness in the input statements. So these are some properties we need  for folding. And it turns out to be a very powerful primitive for us to build  some memory efficient and scalable SNARKs. But I won't talk too much about application, but our goal today is to build such a really  powerful primitive for us in a lattice setting. So also, I want to mention one more thing.  In general, typically, this R should be an NP-complete relation so that we can fold  for arbitrary kind of computation we want to

prove. So typically, what you do  is that you have some computation, it translates into a statement R, and  you absorb it using folding scheme. And such kind of example, including Plonk-ish  constraint system, or CCS, or R1CS, and so on. Right. Yeah, sorry. Let's  just even take a step back. R being NP-complete essentially means you can  reduce any verification of like a NP-complete problem, therefore all of them, into a checking  that the instance R, like something is within this instance R, right? Or satisfies this  like particular inclusion constraint. Okay. Okay. Yeah. And this R star is called an  Accumulated relation, or I call ACC relation.

And how to define this really depends on  what kind of scheme you are using. It's different for every different kind  of scheme you are using. And today, however, we are not build a  full-fledged folding scheme. For simplicity, we'll focus on the toy example.  Well, we'll just set R to be very simple relation, which is called a commitment opening  relation, which I denote by R_ cm,B. Okay. Okay. So this is a relation for which the instance  is just a commitment, a SWIFFT commitment. Okay.

Rq kappa. And the witness is the corresponding  opening, or a vector, f in R^l. And it is in the relation if first we have some public  matrix where we have the input, right? So A times f mod q equals cm. This  is the first check we want to, this first statement we want to check. Sure. And second- Yeah. It's indeed like  hashes or Ajtai commitments to the commitments. I don't actually know what to call that.

Yes. It's a valid opening. Sure. Yeah. And additionally, you also want  to make sure the norm of f is not too large. That's right. And it's  parameterized by this value B here. Okay. And our ideal goal would be to build a  folding scheme that's given two statements, cm_1, f_1, and cm_2, f_2. And we want  to reduce the checking of they are in this R_cmB to the checking of a  single new statement in R_cmB. So a new cm and f in R_cmB.

Potentially, we might want to have some  additional information, not just this, right? Yeah. So in the final scheme, we are not  actually, this will be slightly different. Okay. Okay. But I will get that later. Okay. So for now, let's assume that the dream goal is to  merge 2 statements into 1 statement. Okay. Sounds good. Okay. So when it comes to do a folding,  the first idea that comes to mind is always random combination. Yes.  It's always a random combination. Here, feel free to... So let's consider a  naive attempt, like kind of a variance of this elliptic curve-based folding scheme into  a live setting and see how it works. Okay.

So let's try to build a protocol. The instance  consists of two commitments, cm_1 and cm_2, right? And additionally, the prover also knows a witness,  which is corresponding opening f_1and f_2. So the prover knows instance and  witness, and the verifier knows the instance. And the verifier wants to check  the prover knows corresponding witness. Mm-hmm. And the very natural way to do this is to let the verifier sample a random challenge. Mm-hmm. So  for example, we can sample a challenge from the interval Zq, which is -q/2, q/2, and which is  also a subset of integer, you can understand.

Mm-hmm. And also, as integer, you can understand as a constant polynomial in R as well. Right? Mm-hmm. So you can also understand this, map  this as a ring element, no problem. Okay? So the verifier will send this challenge,  and after that, the verifier will immediately try to merge these two statements into one. Oh. Mm-hmm. You can just compute cm  equals cm_1 plus R_cm_2, mod q. Okay? Mm-hmm. And correspondingly, the prover  might just compute the corresponding opening, which is f_1+ r_f_2. And  our hope is that after this, we can reduce to the problem to checking  that cm, f is again in the relation.

Okay? That's our hope.  However, it doesn't make sense. Right? Why? Why? Because the key reason is that after this  folding, this f will have higher nulls. So we have two points here. The first  is that in practise, q has to be large. Okay? Usually, for example, if you want to  have lambda security, lambda B security, it should be a really large number so that  its interval is large enough so that you will have small soundness error. So it  will be very hard for prover to cheat. But that also means that this number can be  quite large. And that means in the worst case, the norm of f can be as large as, say, 2  ^ lambda times the norm of f_2. And f_2, it is bounded by B, but it might be approaching B.

So in the worst case, this can be  as large as 2 ^ lambda times B, which is super large. And this even exceeds the  threshold for making these commitments being binding or secure. Because as I said, usually, if  you want to make sure the commitment is secure, you have to make sure that this norm  bound never exceeds some threshold. Yeah, it's pretty good. So I'm just going to  rephrase. Fundamentally, the problem is when you take this random linear combination,  so one of the important things here is the commitment is binding only when the function  has, in our case, infinity norm less than B.

The problem here is not even in the worst case.  Like R could be very large in the worst case, but even in the average case, this  is pretty large. Because in fact, this is not just worst case,  it's an average case bound. And the size of this new vector, roughly  speaking, will be roughly the average size of q, which is exponential insecurity parameter,  which in the case that you have 2 instances that are of size B, if you take a random  linear combination of those two things, then the norm of that new thing, this  aggregated thing, will be at least the average size of q times B. That's  pretty bad. Yeah, that's quite bad indeed.

And usually in lattice cryptography, we don't  like this kind of set. We choose another set. So the first idea here is that we can replace  this chance set into a new set, which I call S. Okay, so this S is a subset of R,  which I define as follows. There's many ways to define S. I just choose one example. So you can choose S to be the set of  polynomial in R for which the infinite norm of g is less or equal than 1.  Essentially, these are the set of polynomial whose coefficient are just 0, 1,  or -1. So it has two really nice features.

First, the size of S can be as large as 3 ^ d  because every coefficient has three options and they have d choices for coefficients. So this  is large enough as long as d is linear to the security parameter. And another nice property  is that now the norm of f is much better. So first, the norm of f, by triangle  inequality, this is less than the norm of f_1plus rf_2. And on the other hand,  because r is chosen from these sets, it has only -1 or 1 or 0 coefficients and I can  actually prove that this norm is never larger than the degree of the polynomial times the  norm of f_2. Okay, this will be less than...

Right, and that's because you could  imagine you get all 1s or something and then all of the coefficients are the same sign so there is some term in the expression  where all of these terms get added together if they're all in the same direction you end  up with d times norm of f_2 - norm of f_2. Exactly, yeah, it's a very good example.  Cool, and also we have a bound for f_1and f_2. Right, naturally from the commitments. So that means this bound is  less than about d + 1 times B, right? And this is much better than  before which is an exponential blow-up.

Yes certainly. And also, actually, if you set B to be small  enough it's fine to do a one-time folding d+ 1 times B is still relatively small and still we  can make the commitments secure. But, however, in the folding setting we really don't want  this. We really want even better because if you have this, that means after each time  of folding the norm will keep growing and some step will exceed the threshold of  security and that means you have to reset a large modulus q in order to tolerate enough  number of folding steps which is pretty bad.

So our dream goal is that whether we can have a  folding scheme for which we never need to increase the norm can we just end up with a witness for  which finally the witness still has a norm less than B. So that's our goal and that comes to our  first technique called decomposition. So maybe I'll erase that part. All you. So just really quickly actually just for  my own sake roughly how large in practise, we know m and n in the commitment, how large  is q and d roughly? Because d ^ 2, right?

You want to have some concrete parameters. Yeah, just out of curiosity what  do you even use in the paper? In the paper, typically d in the  practise is either 64 or 128. Okay, so it's pretty small. 128, something like that. It's  not like 1000. And B is about, like you can support 2 to 16 or something. And q, because we want to make q to be  not too large so that we can support really fast arithmetic. So usually  we are using 64-bit primes. Got it. Got it.

In some settings you can even use 32-bits but in  our setting for certain reasons we cannot support 32-bit primes. Okay, so now the first technique  is called decomposition. And actually this is a very simple technique and it's also widely  used in the field of homomorphic encryption. But it turns out it's also very helpful  and useful in the proof setting as well. And let me give you some very quick intuition of  what it means. So say we have a number like 8. I feel it's too large. I want  to make it even smaller. So one way to do that is to set up some base.

For example, base is equal to 3.  Then you can represent 8 using base decomposition. You can represent it as  a pair of values which is 2 plus 3 (2). So tuple , or this pair of 2 and 2 can be used  to represent this number 8 as well on this base. But now this pair of values are much smaller.  And similar thing holds for polynomial as well. For example, if you have 8 plus 7x plus  6x ^ 2 plus 5x ^ 3 you can write it as 2 plus 1x plus 0x squared plus 2x  ^ 3 plus b which is 3 of 2 plus 2x plus 2x ^ 2 plus 1x ^ 3. So you can  split this single polynomial using

this algorithm into two polynomials for which  the coefficients of these two polynomials are much lower than before. And you can extend  this idea to even a vector of ring elements. You just do this decomposition for every  polynomial without problem. So that's the high level idea and with this in mind now let's  see how we can improve this scheme and make it better. Again we have this let me just write  it down again we have cm_1 cm_2 W equals f_1, f_2and verifier has instance the  prover has instance and witness.

And before we do random combination, the  prover now will do some preparation. It will decompose this vector i equals 1 to 2, it will  decompose fi into two vectors such that f_i,l equals square root b f_i,h, where square root  B is let's assume square root B is an integer. And after that, it will commit these two  vectors, the two decomposed vectors and you have four decomposed vectors now, and it will  send these four commitments to the verifier.

And the verifier will first check that these  four commitments are consistent with these two commitments by just checking that cmi equals  cm_i,l plus square root B cm_i,h This is good because the commitment satisfies linear  homomorphic property and now if this check holds true then it's reduced to a new problem  for checking that the prover knows some really known non-vector decomposed vector for these four  commitments However, this is four statements what we want is one statement so at this point a very  natural idea is now let's go back to the original idea for random recombination and to verify our  example ri,l and r_i,h from this change of stats,

S and after that, you just do the same trick and  the verifier will combine all the four commitments into one using this random combiner which  gives you a new commitment cm and the verifier will do something similar but at this  point, given these four decomposed vectors, you also use this random combiner to combine them  together into a new vector f. And now I claim that after that we do have this new instance and this  new witness is inside the relation of R_cm,B Why? Because I claim the norm of f now is  much smaller So first, it satisfies this

matrix-vector multiplication relation which is  simpler to check the key point is that I also can check that f is having much lower norm Why?  Because we have that the norm of f - f is the random linear combination of f_i,l and f_i,h So  by triangle inequality this is less than 4 of the maximal value where i is in 1 or 2. j is in low  and high of r_i,j times f_i,j Right? So we have four decomposed vectors and we have four randomly  combined terms which gives you f and we want to

check the norm of f And as the argument we had  before r_i,j times f_i,j is always smaller than d times f_i,j norm This is the same argument we  had before And finally, we also know that f_i,j is less than less than less than square root of  B So that means if you sum them up you get that the norm of f is less than 4 times d 4 times d  times square root of B And then if you choose B to be large enough for example 16d ^2 4d ^2  then this is less than B, less or equal than B

That's right So you end up with a witness that's lower  than norm B Very interesting So that's pretty nice. It gives you a protocol that satisfies the  completeness. Given two correct input statements you output one correct input statement However the  bad thing here is that we don't know how to prove it's secure. And I'm not saying that actually I  have concrete attack to this protocol For now we don't have any concrete attack It's just that  we don't know how to prove it's secure The key reason that we don't know how to prove it's  secure is because in this case the malicious prover might be might not bind his input witness  to the commitment We have no way to guarantee that the prover is enforced to bind to some  known witness f_1of 2 to cm_1 of cm_2 So that

makes it necessary to add something more to ask  the prover to show that they do know some f_1,2 The problem is this we are currently  violating a condition that indeed we have no idea if f i or these f i l and f i h  are the correct decompositions corresponding to this thing Certainly if they are the  correct decompositions then you have this you get the result But we have no idea if  f _i,h and f_i,h are actually small norm Yes Norm smaller than square root of B That's the problem So that's why we need some  extra tools for enforcing or actually to prove to extract some witness f _i,h f _i,h and  f_1,f_2out from the prover that satisfy

the input relation So that is something we  call range proof And we'll cover that soon So range proofs So before I start explaining how  LatticeFold do range proof I want to, for those audience who are already familiar  with background I want to help them ask one question So do we need to reinvent the  wheel? Can we just use existing techniques?

So in the literature we do have many range proof  or lookup arguments and I would categorise them into two parts that are most relevant The first  one is those lattice-based range proof such as lattice-based BulletproofThere's an extension of  Bulletproof to lattice setting and we also have Labrador which is a proof system in the lattice  setting that gives you some range proof using random projection However, they are not quite fit  for the folding setting If you remember, in the folding setting we need a verify to be sublinear,  have really nice complexity but all those kind of construction needs linear time verify They do need  linear time verify so we cannot use that kind of solutions And the second category are those more  SNARK-based, like poly-IoP-based like plookup,

CQ and so on And all these kind of techniques  will be not that fit for lattice setting, however, unfortunately The reason is that those kind of  construction needs the prover to provide some auxiliary vector, which are actually high norm So  in the lattice setting, if you want to send the commitment to them, you have to do decomposition  again and send the lattice commitment to it and proof there are no norm So you start with some  problem that you want to do range proof, you end up with the problem that's as hard as before,  and you have some circularity issue, so that's why those kind of solutions are also not very fit  for this setting So that's why we need to come up with some new solution, and the first solution  I want to mention is called LatticeFold Okay

So finally the title of the paper  shows up in the movie, you know The title shows up, and actually I will call it  LatticeFold range proof because it's an end-to-end system So at a very high level, our goal is  the following, so we start with some statements We do have some strict norm range check in the  statements, such as our definition of R_cmB In this statement we do have some strict check that  the norm of f is lower than B And our goal is to come up with some protocol that finally after this  protocol we can reduce these statements into much simpler statements That will be something like x  equals cm commitments by something extra auxiliary

information, and W is still f or something else  But anyway, in the output we need to check some new relation R Well this new relation is much  simpler than before and does not require any range proof anymore Okay, so that's our goal So now  the question is how to do that, and LatticeFold provides one way to do that and let's see how  it works So at a very high level, it consists of two main steps The first step is to use the  decomposition trick we had before So let's say we start with some norm bound B that is actually  pretty large and I denote it by 2 ^ t So the first step is that the prover will decompose this vector  f into t vector Okay? So it will decompose and use

some algorithm to generate f_1to ft such that f  equals f_1plus 2 f_2plus 2 ^ 2 f3 to f 2 ^ t - 1 ft And all of these factors are now matched to the  norm So their coefficient is only 1 or 0 or - 1 And they will send commitments to the verifier,  and the verified check is consistent with the input And then after that it now suffices to check  these t different statements Check cm_1 which is the commitment to f_1. f_1is in this new relation  which is Rcm_2 Okay? Because now we only need to check f_1's norm is less than 2 And similarly  for all the commitments and the vectors Okay?

So the reason we want to do the decomposition  is because this relation is much easier to prove Because we go from some large B into smaller  2 And I claim that there is a very efficient way to Batch-Prove all these statements  and reduce them into new statements which is of the form I said before So it's of the  form of something like a new commitment cm, and some other values like there's an r which  is a vector, and a v which is a value And w is some new vector f such that this xw is in some new  relation called R_LIN B Or maybe not B right now.

So there's a linear relation And this relation is  just checking this matrix-vector multiplication relation and some other evaluation statements  like f evaluated at some point r equals v Not that important And also some other very relaxed  norm check rather than some strict norm check So after that you end up being able to reduce  this statement into a new statement that's much simpler to fold But how to plug in this  So next I need to do two steps First, I explain how to go from this to here  That's the Batch-Prove step And second, given these kind of tools I want to mention how do  you plug in into the framework we had before and

obtain a folding scheme So let me do the second  step first. So the idea is very similar to this So sorry, just really quickly, the second  step here is going to be we already have some way of Batch-Proving this How do we use this to construct a folding scheme Exactly So the idea  is actually pretty similar to this framework The only difference is that we have two inputs  rather than one input So what we need to do is actually we go from cm_1 f_1in R_cm,B  and cm_2f_2R_cm,B and we want to go to this So actually because we want to have a folding  scheme, so actually this relation has to be the

same as this but this is just some modification  which is not that important And how to do this? You just do this like twice or in parallel So  you go from cm_1,f_1 cm_2,f_2and decompose them separately and this goes to 2t statements  which is cm_1,1, f_1,1 to cm_1,t, f_1,t And then similar for cm_2,t Yeah, and similar for cm_2 and finally cm_2,t  f_2,t And then this is no difference Here I have t statements Here I have 2t statements You  just use the same trick to merge them back into

a single statement in R_LIN And this gives us  a way to do the folding And the only difference here is that you have to make this to be R_LIN as  well, but that turns out to be fine It's not that complicated So now the rest of the question is how  to come up with this Batch-Prove protocol Right? Okay So I guess I erase this part Okay, so our  goal is to Batch-Prove t statements in R_cm,2 Right, that's our goal But let me start with some  simpler problem Let's just focus on proving one

statement in R_cm,2 Okay, at the moment So we want  to prove that cm,f is in R_cm,2 And let's recall the definition of R_cm,2 If you still remember  This is a set of relation where the instance is a commitment in Rq kappa and witness is a vector in  R^l And we want to check that Af mod q equals cm and the norm of f is less or equal than 1 or less  than 2 is the same as less or equal than 1 Okay And there's another way to view it in the language  of integer and Zq As I said in the very beginning

of the talk It's equivalent to view it as another  relation Well, we can view this instance with a commitment as an integer vector or non-integer  vector, Zq vector which is Zq ^ n And also w That's because n you have defined as  being k times B or something, right? Just consider the coefficient vector And f  can be understood as an integer vector of length m And we want to prove that the rotation  matrix or the convolution matrix of A times the vector f mod q equals cm And similarly instead  of checking the norm of polynomial less than 1,

just checking the norm of vector is less or  equal than 1 Okay And then we use this very simple trick that this just means that every  element of this vector is inside a set of - 1, 1, and 0 So we can rewrite this as checking  for every i in m, f_i times f_i- 1 times fi_1 equals 0 mod q And it turns out this I think  is definitely holds true when q is a prime.

It's less clear because there's some zero divisors  that make it less clear when q is not a prime Yes, for sure If q is not a prime, you  have other problems When q is prime, this is a field So you're totally good Okay, so given this, this so-called  zero-check relation Unfortunately, I won't have time to dive into the details I want  to tell you that given this zero-check relation there exists a very efficient reduction to reduce  this into a much simpler relation using sum-check Okay, so sum-check is another  rabbit hole that I won't cover But if you want to know more about the  details of sum-check, check season 2 I think season 2 has it, we might  have an episode coming as well

I think Justin Taylor has an episode for that  You can check Justin's episode there By running this very efficient sum-check protocol you  can reduce this relation into a much simpler relation for which the relation now has become a  linear relation that has some kind of evaluation statement So there's r and v and W is the same  as f and you check the same rotation relation and some other relaxed constraints, but moreover you  only need to check that some kind of evaluation of f like you can understand f as a vector but  also some polynomial and its evaluation at point R equals v something like this and this turns out to  be much easier to fold and that's our target as I

said before, our goal is to reduce them to a much  simpler relation that has no strict norm check anymore and it turns out it's very easy to extend  this idea to the batch setting because I have to mention that sum-check is a very nice protocol  that is also very batching friendly what it can do is it can combine all the sum-check instances into  one instances and run a sum-check and get a single statement so that's basically the idea actually  this is the idea I think is more similar to the follow up work of Neo so both Neo and LatticeFold  are using some kind of similar framework for doing this range proof and actually using their kind  of language because I think it's much easier to explain so LatticeFold initially they are  using a more advanced Chinese remainder theorem

that's more complicated but this is much easier to  understand so this is the first idea however if you look at it carefully you find that this is  actually not that good because if you look at this the prover needs to generate many commitments  beyond this single commitment so actually the prover complexity of LatticeFold is roughly  about 2t commitments you have to additionally generate 2t commitments which is actually pretty  expensive and beyond that you also need to run some sum-check which is also not negligible  but even just consider this this is already

much more complex than just computing one single  SWIFFT commitment right so this is not very good when t is large so for large norm ranges this is  actually not that efficient even though it's still very practical but it supports better when t is  extremely small and that means this is a perfect solution for this application where you want to  capture Boolean arithmetics or something like that but okay so the fundamental problem  here is like look we've reduced the problem into like 2t instances of  this problem which is obviously certainly substantially harder than the  original statement I mean we now have the

constraint for this less than B now  which we can guarantee for each of these yeah but the point is this is much easier to  prove but the prover needs to first provide this commitment between 1 and 3t even just  computing them takes a lot of time yeah and you have to do that because otherwise you  have to really high degree relation that makes sum-checks really expensive you want to  make sure sum-checks are not that expensive so it turns out there's an even better idea  recently there's a new paper called LatticeFold+ okay so even in LatticeFold+ actually the idea is quite different so what it has is that the  main contribution of this paper is that it gives a new direct range proof  so it's a more direct range proof

I assume right because here we're not using any  properties of rings right here we're just kind of fully saying look you can certainly take a  thing decompose it into bits or +/- 1 and 0 I guess so like trites? I don't know what they're  called … ternary representations right and sure yeah fine you can take a hammer like sum-check  and reduce it to a linear relation but look we have a lot of structure going on here right  we're working over a ring we have a bunch of nice properties of that ring which we did not  have previously so okay and so the observation about LatticeFold+ is you can actually use that  structure to construct a range proof for these folded instances. Exactly very good observation  and let me give you a little bit more intuition

about that what kind of algebraic structure we  are using for Rq to enable us to get a better range proof so for that I need to compare a  little bit in the setting of Zq and Rq so in the setting of Zq if you want to represent  a range proof statement like something like I want to check the x is in some range for  example a set of 0, 1, 2 to d-1 let's say okay this is not ternary this is a larger set where  d is usually much larger then what I can do if I don't want to do decomposition the only thing  I can do usually is just to check this degree d formula are holding true over Zq which is checking  x times x-1 times x-d plus 1 equals 0 mod q right

this is what you can do you can translate this  statement into algebraic statements but this algebraic statement is really high degree so  that means if you run a sum-check you really run a sum-check over a high degree polynomial  which is actually pretty expensive so that's why we need to do decomposition but if you are doing  things in Rq for representing the same statements you can do much better so let's say your goal  is to still represent x is in 0, 1 to d - 1 I won't go into details but I claim that you only  need some kind of degree 2 formula formula over Rq to represent this that's something I won't  cover you can look at the paper if you want to

take a look but nice thing here is that even for  checking some larger ranges we only need to do something very simple low degree and sum-check can  be much much low degree and much more efficient and there's even more optimisation in the sense  naively this will translate to a sum-check over Rq because this is an equation over Rq but  turns out that this formula is so structured we can actually reduce this to a sum-check over  Fq over Zq but in our case it's actually fq q is a prime and this cost is actually minimal it's very  small so actually the cost will be something else finally the approval time is about  one so called double commitments

plus several sum-check over fq and this part is  actually pretty small and this part is also pretty fast the cost is approximately just one or two  SWIFFT commitments which is way better than 2T commitments so that's why it can lead to an even  more efficient range for a large range B here. Do you have any intuition here for why this  is true? Just like at a very high level even? Okay sure. Maybe I can go here a little bit so this kind of a bonus I'm just curious, it's also fine if  not, it's a very magical statement so to check this, you can understand this as  a lookup argument where the table is this, 0,

1 and d - 1 so given this you can embed this  table inside one ring elements for example you can define Tx to be something like 0 plus 1x  plus 2 d- 1 x d - 1 and let's for simplicity let's assume the Rq is slightly different to  make my explanation much easier so this is Zx actually the ideal here is x^ d-1 so x d  is the same as 1 and now you have a number, I shouldn't use x but let's say we have  a number a, I want to check a is in the

table here I want to check a is in 0, 1  to d- 1 how to check that? it's the same as saying that a equals the constant term  this is constant terms meaning constant term of a multiplication which is Tx times  something else what should be something else? if you want to extract a how to multiply a table  polynomial T with another polynomial to extract a the idea is just multiply x ^ d - a so you  only need to check this single equation and this is actually even not degree 2, it's actually  linear because T is some kind of constant stuff,

but beyond that you also need to  prove that this one is a monomial so first before we get to that, the observation  here is like look the constant term so take Tx whatever this is, multiply by x times d-a  everything is going to get shifted by x ^ d - a and specifically the term a is going to become  the constant term because every d order term gets mapped to 1 and so this is exactly  this is expressing that relationship here so that means it suffices for you to prove  that I know some other polynomial of value which I say delta x such that constant  term of Tx times delta x equals a and

also I want to prove that this delta x is  of some special form which is inside 1,x, x ^3, to x ^ d - 1 and how to check that, you  need to do some other checks which is degree 2 that's why you need some proof and that's it cool, very, very cool okay, so  that's about the range proof so in summary we've covered how to build up some commitment from  polynomial rings which is more efficient and we've touched upon how to build a folding  scheme using decomposition technique and finally we fixed the proof, we make the scheme  secure by coming up with some new range proof very, very cool yeah, well, thank you  Binyi it's been a lovely time learning

about LatticeFold and everything relating  ideally and building up to it but yeah, it's been a lot of fun thanks again for  having me and thank you all for watching. Yeah, it's my pleasure yeah, thank you so much