ZK13: Mercury: A Novel Constant Sized MLPCS - Liam Eagen

Transcript

[Music] I'm going to talk about Mercury um which is a new um KZGbased multilinear polomial commitment scheme joint work with Ariel. Um yeah so let's get into it. Um, so yeah, talk about why why you should care about this, what what we accomplished, um, and then kind of some background context. I expect people here are probably familiar with the sum protocol.

Um, and you know, like why we should care about this and then kind of like the existing landscape of KZG MLPCS. um you kind of have these constant size MLPCS that require linear sized FFTs and you have linear time I I so I will say time but uh all of this is KZG based so over elliptic curves so in some sense it's technically not linear time but just for convenience to avoid adding that caveat every time I talk about it uh what I mean by that is like a linear sized uh MSM And those those MLPCS are are log size. So that would be like

Gemini um which is what Aztec uses. And Mercury is able to kind of get the best of both worlds. It's constant size uh meaning it has a constant verifier complexity and also linear time. So yeah, the the sum check protocol has over the last you know few years become extremely popular in uh like high performance snark protocols for a couple of reasons. It uh so it it replaces linear or univariat polomials which things like plon were used or used um with multilinear polomials because we can avoid um ffts. So if you know how plon works um you have to do basically a

product of univariat polomials and uh division and that requires extending to domains and so FFT algorithms take quasylinear time and some check allows us to avoid this. Um uh subtle point about that is that um the benefit often isn't really the time it's like the memory to do an FFT. So sum check is also useful on constrained proving environments like phones and whatnot.

So if we replace our univariate um polomials in the IOP with multilinear polomials we need a different kind of polomial commitment scheme. Polinomial commitment scheme is just a way to prove that you evaluated a polinomial correctly. Um so this makes sense. uh there are really nice univariate polinomial commitment schemes like KCG um but multilinear is less more complicated so that's why we care about multilinear polinomial commitment schemes yeah so like I was saying before the existing MLPCS um require a trade-off and maybe maybe just like also

to say for motivation um uh we care about the um elliptic curve setting because they yield concretely smaller proofs and they can be efficiently checked onchain. Um so that's that's another maybe caveat but yeah so the the two ways you could do a multilinear polinomial commitment scheme with KZG are with a product basically uh which gives you O1 proof size but um like I said before requires an FFT in order to compute a quotient or as in Gemini you can do a kind of it it's it is itself reminiscent of the sum check protocol um there a

bunch of different snarks that have this kind of pattern where you shrink something down by factors to two log time. Uh and this this allows us to do linear MSM work. Um it is like I said not technically linear but mercury we can get both. Um also it's it's interesting to note that Mercury does like less overall prover work than existing linear uh time MLPCS like Gemini. um we do 2 n scaler multiplications instead of just uh 3N for Gemini. Um and this is with the standard KZG pairings. Um if you were to use an additional pairing, you could

actually get it to the same asmtoically as KCG, which is pretty cool. Um yeah, so just some definitions to when we talk about sum check. um multilinear function f has a degree 1 in each variable. So that means that the terms of f will look like one and x1 x1 * x2 and so on. Uh there are two two to the n terms um or two to the k. Multilinear extension is the unique multilinear function like polinomial that uh interpolates some values.

So we we usually talk about the domain like 01 of boolean hyper cube when talking about multilinear extensions. Um the sort of process of multilinear interpolation has a very nice structure. It uses these EQ functions which are kind of like the lrangee functions in univariat and they decompose as a product like this which will be important for how the MLPCS works and in fact is important for how other MLPCS work as well.

Um yeah, so this function if you kind of stare at it for a while probably convince yourself that when you evaluate it uh with the x's being all zero or one and the y's being all zero or one you get one if the two inputs are the same and zero if they are different. Uh and to see why like imagine they're different at some position then you'll have like in the first term 0 time 1 or 1* 0 and in the second term you'll have the opposite and so one of the factors will vanish. Uh and so by interpolation we mean we can write everything as like a linear combination of the values of the MLE by the EQ

functions. So yeah, this is all pretty standard some check stuff. So what is an MLPCS? It allows uh you know prover to convince a verifier that some committed multilinear extension when you evaluate it at any point u gives you a value v. Um there are lots of different types. Um uh so if you've heard of IPA or bulletproofs uh that yields essentially a multilinear polinomial commitment scheme baseold this is explicitly multilinear polinomial commitment scheme based on fry gemini linear time kcgbased etc. Um some of them have like a natural kind of MLPCS like I said before right

there's this way in which a lot of snarks fold things by half uh and like randomly combine the halves and this is very similar to what some check does and so like um if you want to do an MLPCS for bulletproofs it turns out to be like extremely natural or fries it's also very natural this is not the case for KZG G. So we have this trade-off. Mercury does sort of both things, right? Okay. So we'll talk about the two existing ways that people do it because Mercury sort of combines both of them. The constant size multilinear polinomial commitment schemes um work uh

by reduction to a univariate sum check basically. So like I said we have our uh MLE fhat and we can write the evaluation claim itself as a sum of products. So that is a sum check. In this case it's written over the boolean hyper cube. But you can imagine that the eqs and the fhat are actually given as vectors. So there are generic like there are other types of sum check protocols like in the beginning I said multilinear sumche but sumche can be defined for univariate polinomials as well. Uh this is like people call the aurora sum check where you evaluate at zero. Um in fact it can be defined for polomials over

like uh kind of arbitrary kind of shaped hyper cubes. Um so to get a constant size KCG MLPCS once we write it like this as a sum of products we can use like an inner product protocol or uh you just could interpolate the two vectors with polomials multiply them and then do a sum check lots of different ways you could do this we have a protocol in the paper that I think is interesting uh it's like compared to existing inner product protocols. It it commits to like half as many values um using an interesting symmetry of you

know the identity but won't get into it here. If you if you look at the paper it's there. Um also so the encoding that we use is pretty simple to describe. It's on the next slide. Um you you take your values and sort of imagine them as a vector and you multiply each one by a subsequent power monomial. Um so the the boolean hyper cube right it's bit strings it has a sort of canonical and ordering you know as integers and so if you do this it has lots of nice properties and in particular when you encode the eq function like this it factors this is the trick that like halo used and it's ubiquitous in these kinds of protocols um so that's what I mean by you can

avoid committing to the eqs okay so that's the constant size MLPCS. The linear time MLPCS uh work like I said kind of similarly to some check. Um there are sort of two I think that that we think about Gemini and also Zeromorph um that are fairly similar. Um for technical reasons Aztec uses a variant of Gemini.

Um, so again, we start with MLE and evaluation claim. And this is the encoding that I was talking about before where you take all of your evaluations and you sort of order them according to the canonical binary hyper cube uh ordering and you multiply each one by a subsequent power of x. Same encoding. So we want to relate like this encoded univariat to some kind of structure for the MLE. So I write f for the univariant and fhat for the MLE. We have the same evaluation claim as before but just written out

explicitly. Um we define a sequence of partial evaluations of the MLE. So notice that when you partially evaluate an MLE, you get a new MLE of like a domain of half the size. So you just plug in some use. You have the remaining variables. Then we can define a univariate for each of these smaller MLES. Notice the not having a hat. So this is the identity. I don't I don't work out all the algebra in the slides, but this is sort of the Gemini identity. And I don't I think that's the first place I saw it, but you um can take the even coefficients of each univariat and the odd coefficients

of each univariat. And this is the same thing as specializing the original MLE to zero or one. So if we take a linear combination of those, there's a slight error. I think it should say FI + one of X. Well, I guess it depends how you define it maybe. But in any case, you take the linear combination of the even and the odd coefficients and it's the same thing as specializing the first variable. So this allows us to relate the univariants like fi to fi plus one in the same way that we've related by evaluating in the first variable. So this is like a folding operation.

And the reason this is this is useful is because we have a univariate MLP piece or a univariate PCS. So if we had a commitment to FI, we could evaluate FI even from evaluations of FI. And so we can relate evaluations of each of the folded univariats uh in this way. In particular, we can link FIR and FI negative R with FI plus1 R 2. So this is this is essentially what Gemini does. Um from here it's not too hard to work out the rest of the protocol. You have these like subsequent folds and you want to check them all at different points and there's you know subtleties but proceeds

naturally. So this is the idea of mercury. Gemini were always folding by a factor of two. And you see here I say like fi r and fi negative r. You imagine that the prover sends evaluations for these to the verifier. So Gemini folds by a factor of two. It folds log times and it sends two values each time. So the transcript is log sized. Um if we could fold by a factor larger than two, we could use fewer rounds, right? If we could fold by a factor of three, we would send three values each time. we folded by a factor of square root n we'd send like square root n values in one time maybe um but like so for concretely if you

were to do this you might use flunk which is is a way to decompose a polomial into sort of pieces in like this sort of FFT decomposition um but you'd send one value per each piece so if you fold by a factor of k you'd send k values Um so if we wanted super like constant folding factors you would increase the proof size like like I said if you folded by a factor of square root n the proof size would then become square root n. So in in building a constant size mlpcs we don't want this.

Um the main trick I think that Mercury does is we can fold by a factor of K and only send O of one information like prover only sends a single or O of one commitments to polomials instead of setting K values and we can prove like construct this proof in linear time. Um, if we had that primitive, which we do, then we could fold once by a factor of square root n and then use the slow like FFTbased MLPCS to check that the folded thing like relates properly.

Um, so even though you know we're doing something that's n login, you're applying it to a vector of length square root n and it doesn't affect the overall running time. It's interesting to note that like we pick square root n because it's optimal for our use case, but you could fold by a factor as small as login and still get a linear time prover. Yeah. Yeah. Yeah. Exactly. So um yeah and and yeah but but in our case you know it's square root n so it makes sense uh okay so the way that we do this is is not not so complicated. Um, I think this slide

might be missing like one line. So, sorry if that's confusing, but we instead of sending K evaluations. So, we need to back up a little bit. In the the Gemini case, we're we send two evaluations at R and negative R, which you can think of as a co-et of the degree 2 roots of unity, like one and negative 1. This generalizes and flunk to a co-et of the K roots of unity. So you you'd send like an evaluation at R and evaluation at R * omega and R * omega squar up through K. If you think like some some simple like algebra um sending a bunch of evaluations is the same as sending like

a polomial reduced mod a polomial whose roots are the points evaluations that you care about and the polomial whose roots are the k like the k root of unity coset of r is x the k minus r the k. So like if you plug in omega * r into this equation it'll vanish. So instead of sending evaluations we can send the reduction mod this polomial and then from that you can evaluate it to the points that you care about because the modulus vanishes and so this is what we do. Um we have f we decompose it and this is the piece I'm missing. These f sub iis are like the

interleved k order coefficients of f. Um in the case of k equals 2, f0 would be like the even coefficients and f1 would be the odd coefficients. Um and so if you reduce mod x to the k minus r the k you replace all the x to the ks with rs to the k's and you get a polinomial of degree k minus one as g. So if we could check this congruence of polomials then uh we would be able to check that we sort of folded f by evaluating each piece at an element of the k coset determined by r.

Um that might sound more complicated than it actually is. And we can compute all of this in like well yeah we so uh another like technical point is in flunk you need to use r to be a kth residue. Uh this is not the case for mercury you can be any value in the field. Um and so yeah that's just the identity I was describing before. If you multiply r with power of k through unity um each of the so implicitly here you have this like a quotient which is multiplying the vanishing polomial and you also have g and in order for the

overall protocol to be linear time we have to show that you can compute both of these quantities in linear time and it turns out that you can um the intuition is if you take each of the interleaf chunks each of the f subis and you want to construct a quotient it's sufficient to consider it as a polomial of degree n over k and compute the quotient as you normally would and then interle the quotients so it's not not so bad that that would take n over k time and then times k is n time so this is the the overall protocol sketch of mercury. I I've found in the

past trying to describe it in words confuses people more than just writing it down first. So hopefully this this is clearer than it would have been. Um we have the same public input as before. We have like our commitment to f, our evaluation point u and our uh evaluated result v. And we let b be squared n. Um this is written sort of parametrically. Like I said, you could let B be login or any value from login up to N over login. So that's our FFT decomposition I was talking about. You split F into um B pieces and each one will be of degree N /B. This is the

like Gemini style univariate encoding of our MLE. Then you take the evaluation point and split it in half. U prime and U prime prime which are like the first log B coefficients and the second N over log B or log of N over B coefficients. If B is<unk> N, U prime is just the first half and U prime prime is the second half. So we commit to the result of the first folding. So a linear combination of the pieces by the EQ functions then pick a random challenge and commit to the folding of f by that

random challenge. So we have two sort of uh you could think of it kind of like a commutativity diagram or something. You like go in one way where we fold by the eqs and then you go in the other way where we fold by alpha. And we want to check that those two things agree. So if we take the folded polomial G and we do an inner product with the EQ functions, this should be the same as if we take H and evaluate it at alpha. And this is because if you were to so suppose we evaluate H at alpha, we get each FI to be at alpha* EQ. And if you look at the definition of folding by

alpha replaces the x to the b by alpha and then doing an inner product takes the inner product of those values. So it should be the same. This lets us check that h was correctly constructed and it runs in time like um square n log squar n or something. Then once we once we check h is correctly constructed we can do another inner product with the rest of the coefficients. This also runs in squared n log squared n time. So these final two steps are both sublinear and the only linear step is actually the folding.

Um concretely uh committing to Q and then committing to an evaluation of F in order to like reduce all these polomial identities to a single um KZG check are the most expensive parts of the protocol and that's where we get the factor of 2N like in the overall work that prover has to do. Um, everything else is basically like square root sized, so it's all very cheap. Um, yeah. Let's see. I think I think that's basically it. Um, it's worth mentioning there's uh another work that came out like a few

days after Mercury called Samaritan, which is like essentially the same um construction presented a little differently. And there is a way in which you can sort of think about this like a bariate sum check. um it's maybe not exactly the same, but I think it's an interesting thing to think about and uh kind of expand upon. But um yeah, I think if you if you're using a multi-linear polinomial commitment scheme that's based on KCG like Gemini or Zeromorph, you should probably uh consider or just switch to to Mercury or Samaritan because um the prover is

simpler, the verifier is simpler. Um it's constant size, less randomness. Yeah. So that's it. Any questions? Thank you very much, Liam. Do we have any questions? Okay, I'll start with one. Um, you mentioned sum has some nice memory efficiency properties. Are they preserved here with the commitment scheme? I think so. [Music] Um, so the sum check like memory efficiency properties that I was talking about come from not needing to compute a quotient.

[Music] Um, I'm not sure. I'd have to think about it more. I would I would assume probably, but I think there's usually a trade-off, especially in like the very low memory some check protocols of like increasing time. So, you like would reconstruct the witness if you did that. I think I think this would definitely be compatible with that. Thanks. Yeah. Yeah. Any other questions? No. In which case, thank you very much, Liam.

[Applause]