Caulk: zkStudyClub: Caulk - Lookup Arguments in Sublinear Time (Arantxa Zapico)

Transcript

Hello everyone and welcome to this week's edition of ZK Study Club. This week we're excited to welcome Arantxa Zapico who is presenting new work that she has co-authored with Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Mark Simkin and oh, I'm not even going to try and pronounce that. Arantxa, can you Who is the last co-author? Oh, sorry, she muted it. So, anyway, with that we'll pass it over to we'll pass it over to Arantxa to go ahead and present her work on Coloque. Arantxa, over to you.

Thank you. The other co-author is Anghelina Tulescu. Thanks. Okay. Can you see my slides? Yes. Yeah, they look great. Perfect. So, as I like to mention, I'm going to present Coloque and we will start with a little motivation. Coloque was born to be a a protocol for membership proof. So, let's say we have a set, a public set with some information. In this case there will be like public keys and we want to isolate one element in zero knowledge.

So, we want we have this element that we don't want to reveal, but we want to prove that it belongs to some public set. Why? Because for instance, in this setting later we may prove in a protocol that is not covered by Coloque that we know the secret key tied to this hidden element. Right? So, by proving the knowledge of the secret key linked to some of the public keys of the set, we can prove for instance that we are authorized members for posting in a blog or for voting or whatever setting.

Another nice applications applications, sorry, a range proof. In a range proof it's quite I mean, I like to think it's quite the opposite. You have a hidden element that has been used for instance a snark and then you need to prove that this element belongs to some public set that is actually the set of all the elements in a range. So, again, we don't reveal our element, we don't reveal the position, but we want The only thing we want to prove is hey, whatever is hidden with this yellow cape of zero knowledge has been taken from this public set.

Then we can go a bit further and apply this to like bigger sets. Sets that have more than one element. Again, all the elements in these sets are hidden, are covered by the with their zero knowledge cape and we want to prove that they belong to a public set. For Coloque we don't care about the order of these elements, we don't care about them being repeated or not. And this is what we usually call lookup sets. Well, we don't usually call they are called lookup sets.

So, these kind of protocols have a lot of applications and then have been like widely studied and we have a lot of constructions that can do this isolation in zero knowledge of element of an element of a public set. And so far we have like, I would say, four main groups of constructions. We have constructions based in the discrete log problem. We like them, very nice and well-studied problem. And we also like them because they have transparent setup.

The problem is that usually the amount of work that both prover and verifier have to do is linear. I hear I say usually and I would say probably that in all the constructions because there are some trade-off and lot of improvements, but this will be like the general rule for those kind of constructions. Then we have RSA accumulators which have a constant prover and here when I say constant or linear, I mean of the big one. The problem with RSA accumulators is that they need RSA um groups. They need the RSA parameters to be computed by a trusted party.

We don't quite know how to do this in a better way and we don't want to trust anyone. Then we have Merkle tree-based constructions where we can prove that one element belongs to a vector by by storing the vector in the Merkle tree and giving the path from the from the element to the root. It is nice they have transparent setup, but to add zero knowledge we need to use a snark so far. And snarks are heavy machinery that probably we don't need to use in these more like specific languages.

Last but not least, we have pairing-based constructions. They can achieve constant prover proof size, sorry, and verifier. But the prover is usually the one pairing-based constructions don't take care of. Coloque falls here. We don't care about the prover, we achieve a logarithmic prover in the size of the bigger set of the public one and we keep the constant proof. We just like sacrifice a bit the verifier, but I promise you it's not too much, still very competitive with previous constructions.

So, first contribution of Coloque is like giving a definition for this kind of arguments where the prover wants to convince the verifier that some hidden commitment has only elements taken from some public set. We call this position linkability. We use vector commitments to commit to this set, so we put them in vectors and we commit. The orange is the big one, the public, and the one that is covered with the with the red cape is the hidden one.

So position hidden linkability is the ability of the prover to convince the verifier that everything that is in the hidden commitment is also in the public one. Now, a starting point for Coloque as any pairing-based commitment that we want to do, basically is based in KCG. That's That's where we start. So, as I mentioned before, we take our set, we order it, we put it in a vector. And then to construct the commitment to to this set we use a set of roots of unity as interpolation set and use its Lagrange polynomials.

So, the Lagrange polynomials of a set of size n are polynomials of degree n minus one such that they take value one in only one element of the set. So, we will make the index of the Lagrangian match the the power of of omega that we are using and it takes value zero in any other element of the set. Outside the set take some value that we don't care about. We care what happens inside H. So, vanishes at everything but one point.

What is nice about encoding vectors in this way, encoding vectors with Lagrange polynomials is that we can recover easily the different positions. So, we will encode the this vector as a polynomial where the coefficients in the Lagrange basis corresponding to H are the elements of the vector. Now, why roots of unity? In cryptography we usually use roots of unity for a matter of efficiency.

The sparse sorry, the Lagrange and vanishing polynomials corresponding to a set of roots of unity are sparse. So, even though they have degree n and n minus one respectively they are very sparse. I will denote the vanishing polynomial with set H and is the polynomial that basically vanishes at all the elements in the set. But in Coloque we also care about another thing of roots of unity which is the fact that we can prove that any element is an nth root of unity by proving that its power its nth power is one.

So, if I take an element and prove that that element to the n is one, then that element is some of the powers of omega. Doesn't matter which one. And this is something that doesn't happen with just random set H as we used to use before in cryptography. Now, a quick reminder of KCG. As as I said before, the encoding of this vector is public, the vector, the big one is is public. And the prover has to send to the verifier commitments.

I'm not going to specify the groups, but this this works in a bilinear groups with pairings. It was just too much notation, but the prover has to send a commitment to the element that it wants that it's claiming that it's in position i, for instance. A commitment to the vanishing polynomial of omega to the i minus one and a quotient polynomial. For now, we care about soundness. We are not talking about zero knowledge yet. That is something we will take care of at the end of the talk.

So, the prover sends these commitments such that this equation is satisfied. So, what is in two brackets is evaluated at some secret point small x and what is outside the brackets are are polynomials that the prover has access to in in the field. So, this equation proves that CX takes value VI in the position I. And the verifier checks it through a pairing. Now, uh there is this nice work by Thomas Cot that says, "Okay, we can do this also with a bunch of of elements." Because KZG was created as a polynomial commitment, we like realized it can be interpolated to

vector commitment. And now Thomas Cot gave this construction for opening to stacked vectors. So, what they say is prover will send instead of one element in this case an encoding of all the elements you want to open, the vanishing polynomial of the corresponding positions, and one quotient, one quotient polynomial Q. But, this uh encoding CI is not creating and it's not created using the Lagrange polynomials that we saw before corresponding to a set of size N, but these are the interpolation polynomials of the subset of H that the prover is using.

For example, if the prover wants to open positions two, three, and four, this subset will be uh will be formed by only three powers of W of omega, sorry. And this polynomial style will have degree two instead of N minus one. The reasons why we care about this are not the same as uh the ones for Thomas Cot. We'll see that uh in a second. But the important part is that the prover um send commitment to these polynomials that uh make this equation to be satisfied. And again, this means that C and CI are the same in the corresponding

positions. Oh. In the corresponding positions, sorry. Again, the verifier checks this with a pairing. Now, we care about two things in Colt. We care about zero knowledge, hiding the positions and the values that we are opening, but also we care about the prover to stay logarithmic. And if you have pay attention, you will see that the QIs, both of them, Q small I and Q big I, are linear in N. Because the polynomial in the left has degree N, the polynomial in the in the right has degree either one or some constant, potentially small constant.

So, working with this, like asking the prover to compute this these polynomials will break our our ideals. Here is what the also the the work by Thomas Cot cites us. They say, "Okay, you can precompute all the individual proofs of openings for this big set N. These individual proofs of opening can be public. They can be stored somewhere. And whenever you want to open one position, you just take the proof of opening that you are using.

You can blind it, of course, because you don't want to leak information about this quotient, but the quotient uh committed in the group is available for any prover. Now, what happens when it comes to to subsets? So, the same. They say, "You can just take the ones that you are using, the ones you are going to use, and compute this Q big I by performing a linear combination of the precomputed proofs of individual positions."

Uh this linear combination uh needs to use some constants that are again public and available. At at the end, the prover of uh the the work of the prover depends only on the size of the subset that it's opening. So, if the prover is opening just one position, takes the corresponding quotient polynomial, blinds it or not, and sends it. And for a subset of size M, it performs M group operations to compute QI. So, we have already like um solved succinctness for for the construction of KZG.

Well, not we, Thomas Cot. And now we go to the part of zero knowledge. So, these are the proofs for one position or for many positions. The commitment to to the big vector is public. The prover sends the claimed values, the vanishing polynomial, and some quotient. Now, we need to start like blinding this stuff. For the for the elements, for the claimed values of the elements that it's opening, we use standard zero knowledge techniques.

And the verifier sees something that doesn't leak any information. We do the same for the polynomials Qs, also blind them, and they become something with no information for the verifier. And we do the same with the vanishing polynomials. Now, the verifier doesn't quite care about the shape of the these elements A or these quotients Q. They can be anything. Whatever is in A, you will prove me that has elements that were taken from the from the big set, and Q is just there to prove in divisibility. So, whatever is in Q, we

are okay. But, that's not the case for the for these C's. Because the verifier needs to check that these polynomials are actually vanishing polynomials of these of a subset of this set of roots of unity. And this is uh the let's say the the main challenge and the main contribution of Colt. How to prove well formation of these uh committed polynomials. We start with M equal one. Uh as I say, we first add a blinder, and then there are four steps to prove uh its well formation.

The first one is to prove that set is a polynomial of of degree one. This is our starting point. So, it's A times X, this secret X that is in the SRS, plus some constant term that for an honest prover will be A times one of the roots of the unity that corresponds to the position that we are open. Then, the prover will construct a polynomial of degree log of N plus six that we call F.

And for that, we will use a new set of roots of unity that we call B that has its own Lagrange interpolation polynomials that are the mus. And this part is very important because if we keep working with the lambdas, the polynomials that we have from before, we'll keep working with things of size N minus one. And even though those polynomials can be precomputed, the Lagrangians, everything that becomes out of like computations will have size linear. So, we just stay in a smaller polynomial.

And with this F, we first construct recover what is supposed to be the power of omega. So, if B was a constant term, B over A should be a power of omega. So, we use the first like five uh coefficients of F to recover this element. And then we use the rest log N uh coefficients to calculate the two powers of this element. So, F five should be omega to something.

And all the other coefficients are going to be the two the two powers. And at the end, we have to prove that the last one, not the last one, but the first one, F sub log N plus five is equal. What does it mean? It means that B two A uh B over A, sorry, to the two to log N, so to N, equals one. And as I said before, this means this is a Nth root of unity. So, this is omega to something. Then we have well formation of set. Set is a polynomial of degree one that vanishes at one of the Nth root of unities.

Then, when we compare the big commitment to to our small parallel set commitment, we know we are comparing the evaluation of the first one at some of the roots of unity, so one of its coefficients, one of the elements of the big set. Now, for M bigger than one, for our lookup tables, things get a bit more complicated, or at least larger. Let's see if I I can do it without losing you.

So, first of all, first problem is that this CI, as I mentioned, that the prover builds using Thomas Cot approximation approach sorry uh is constructed with Lagrange polynomials that correspond to a subset of H. But to the subset of H, the verifier doesn't know, and actually we don't want the verifier to ever know which is this subset. And if we think of Colt as a protocol that is meant to use as a sub protocol in other in other protocols. So, a lookup table is usually inside a bigger protocol. What we want is to the

verifier to or both prover and verifier to be able to work with the commitment to this element. But also, the problem with this CI is that it cannot repeat elements. We say that in lookup tables, we are okay with repeating elements. And here we kind of when we compare with the equation of Thomas et al., we are comparing one position at time and only one position. So, these both things are solved by having actually a commitment not to CI the sub vector of C, but to the actual set that we want to to prove that has been constructing using the public one.

So, what I I haven't called it A, no, but I will call that vector A. So, A is a vector such that all its elements have been taken from B, but without any specific order and with possible repetitions. So, we still have another problem here, apart from proving well formation of set, apart from comparing C and CI, we need to link this this polynomial fee to the CI. So, let's see how can we do it.

First step, prove well formation of a randomized vanishing polynomial. For that, this is what we call it uh the proof uh for the relation unity, and it's an entire chapter. The idea is that we construct a vector that has all the positions of omega corresponding to the positions that we are taking, all the powers of omega corresponding to positions that we are using. But if we are repeating any, we have to include it in this vector U.

So, if I'm I'm doing a lookup table for range proofs and I have two elements that equal five, I have to take the power of omega that corresponds to the element five in the public set twice. So, this vector we will encode it as a polynomial. Again, a polynomial that has as coefficients roots of unity if the prover is honest. Then, well yeah. Then, we will compute the Hadamard product. I forgot to put uh the the dot for Hadamard product there, but the Hadamard product of this vector with itself.

So, what we will get is a vector whose coefficients are the coefficients of U uh whose elements, sorry, are the elements of U, but to the two power. We do the Hadamard product of these vectors then through the encodings uh with the with a normal protocol for these things, multiplying both polynomials and taking modulus set P. Again, I'm working with a smaller uh set of roots of unity.

Yes, we don't need to take N uh I mean, we assume we are not going to take N positions, N elements, but something smaller. Something smaller that doesn't need to be specifically smaller than logarithmic. I'm just doing that for uh simplicity of the presentation. You can use a bigger set, bigger than than log N, but smaller, considerably smaller than N. So, we are computing all the powers of these coefficients. So, at the step S, I will have an encoding of a vector whose position whose elements are the elements of U but to two to the S.

Once more, after log steps, I should arrive to a the encoding of a vector whose whose elements are one. So, this would mean that all the N powers of the U's are one. So, let's recap a bit. I construct a vector that has all the roots of set, repeated if needed, and then I take this and I find their N powers, prove those are one, and then I have proven that this polynomial U is an encoding of a polynomial whose coefficients in

this new base uh of Lagrange polynomials are roots of unity, N roots of unity. So, I haven't quite proven well formation of set right. I just created this new polynomial. And to link them, we do the nested polynomial trick. We prove that set evaluate set I evaluated in U vanishes for in all the elements of this new set B.

Why? Because if I evaluate this equation in in any element of B, what I have in the right side is zero. And what I have in U is omega to something. I don't know what, but the coefficients of U in the Lagrange basis mu J are omegas to something. So, set evaluated at omegas to the something is zero. This means that set has as roots roots of unity.

Set can have other roots. That's contemplated in the soundness proof. For us, it's enough because we are not saying how many positions, we are not saying which positions. We are just saying some positions of B have been taken to construct A. But we we don't need to specify anything about them. So, now yes, we have well formation of set. Now that we have well formation of set, we have solved our zero knowledge problem in KC G.

So, we can compare CX with CI with and know that they are equal at some positions. But again, so again, C C in omega to the something will be some uh elements of B. And what we have proven is that CI is an encoding of a sub vector of B. But what we are missing is A. So, what is left to to prove is that everything in A is also in CI.

We use the nested polynomial trick again. And we prove that CI evaluated in U takes the same values as fee if both polynomials are evaluated in some element of B. Once more, when we use elements of B, what we get in the right is zero. What we get in the left is some position of CI minus the coefficients. And because this holds for all the elements in B, we are taking all the elements in A.

And then everything that is in A is also in B. Meaning, we have position hidden linkability between two KC G commitments, where one is public and the other is hidden. Nice. This might be a good spot to just to check to see if anyone has any questions. So, the I just jumping in here to see open it up for the group of if anyone has questions, you can type them in the chat, you can voice them aloud, um but do you have questions for Arantxa at this point in the talk?

Okay. Uh I guess feel free to continue. Okay, I'm I mean, I'm I'm almost done. Um I will finish with some numbers. We have uh an implementation by Mary and Dimitri. So, this is a plot for uh the case when we are opening just one element. So, it could be an individual range proof or membership proof. Uh can you see my mouse? Yeah, we can see it. Perfect. So, this is the prover work, the the the time that the prover takes to compute the proof, and this is the size, the logarithmic of the of the of the size of

the element of the set we are open. The big one. Uh so, as I said before, RSA accumulators have constant prover. So, if I'm opening one element in a set of size two to the six or two to the 22 or two to the 50, the prover does the same work. Uh this green line is Merkle trees uh with Poseidon hashes, and as uh Groth16 SNARK on top. And this is for uh Merkle trees with SHA hashes.

For us, we are the orange, this orange line that is very below. And the thing is that I mean, for for this scheme, we can assume uh Coq will perform better than than Harissa, which is this uh RSA accumulator by Campanelli et al. At, let's say, every practical uh practical set, it may become worse for very, very, very big sets. But for now, uh I think this is a very competitive um performance.

And then, when we move to look-up tables, so to opening many uh elements of of the big set, in this in this uh plot, we have again prover work here. I here we have the size of the smallest set, the one that we uh have in in zero knowledge, the hidden one. And the thing is, this is RSA accumulators. So, their the prover time doesn't depend on the size of the set, but it does depend on the amount of positions that you are opening.

Um this is again Harissa. We have Merkle trees with Poseidon hashes, SHA hashes are just too slow to So, we just throw them for this comparison. Um this is uh how a uh how this protocol performs for uh big big sets of size 2 to the 8, and this is 2 to the 20. And here we have Caulk for uh big sets of size 2 to the 8 and 2 to the 20 in the orange one.

Uh we are I mean, clearly we are going to get worse than Harissa. I'm not sure where, maybe in sets of size 2 to the 28 or so. Um well, just to clarify, this is opening 32 positions in a set of size 2 to the 8. With Caulk, this is opening 32 positions in a set of size 2 to the 20. With Caulk, in a set of any size, this is the time that Harissa takes to open 32 sub-positions.

And the same for the Merkle tree approach. Um yep, that's all from me. Thank you very much. Awesome. Uh thank you, Arantxa. This is great. Um I guess we can open it back up to questions. Um if Well, maybe I'll actually just start with a question. Um can you talk a little bit about uh what, if anything, uh in terms of applications motivated this work for you and and kind of what how you potentially would be excited to see it applied?

Okay, I'm not the best author to speak on this. Probably I'm I'm the one that worked with real world less. But um I was also not the one that had the initial idea. But yeah, what motivated Caulk uh was, if I'm not mistaken by from history, uh it was membership proofs. Like exactly the kind of uh application where the public set is a set of private keys. And the uh what we uh what you want to isolate is your public key, so you can prove knowledge of the linked secret SK without leaking any information on your

identity. Um one of the applications of Caulk that excites us the most uh is uh zero-knowledge SNARKs. We know that's still a I mean, we are far from there yet, but using like most of zero zero-knowledge SNARKs use uh look-up tables that are linear for the prover. And I say most because I'm not sure enough to say all of them, but I think all of them are. So, that's actually what excites me the most SNARKs.

Cool. Um thanks. And I guess Mary and I think Vitalik dropped off, but um if any of the other authors who are on this call, co-authors, uh have anything to say or add to the presentation, feel free uh to jump in. Yeah, I would sort of just say with the SNARK application that Arantxa was talking about, really we're thinking specifically of the type of look-up arguments which people have been sort of discussing using in terms of look-ups. So, this is the Plonk look-up argument and also the Halo look-up argument. Like uh lots of people have been designing circuits that use these look-up arguments in order to try and reduce prover time. And what Caulk can do is it can give an alternative way of

generating those look-up arguments to get down your prover time, which might have different trade-offs which could be really beneficial for certain applications, assuming you're okay with working with pairings. Cool. And we have a lot of uh people from the Plonk universe on here, so um yeah, I I I'm assuming that'll be of interest to uh to them. Um I'll open it up to the group in case anyone else has questions. So, yeah, I have a couple of questions. But first, I'm kind of interested in applications like Zcash and anonymous credentials, proving on a blockchain that I own that I have something without showing what where it came from.

Yes, this could absolutely be used for those types of applications. Um it will have much faster prover time, um but it does have a cap on the number of um people in the system. I mean, the cap is large, it's like 2 to the 28, but it's not unbounded. So, assuming 2 to the 28 is large enough for you, we can cover those sorts of applications. Yeah, I don't know how many active Ethereum addresses there are, but I I'm assuming for the use case that you're

kind of referring to, Alistair, that would 2 to the 28 probably would be sufficient at least today. You think it would cover it? Yes. Yes, it's not running into trouble with the Zcash approach uh at some point. Uh I'm I'm going to read a question from Luke Pearson. So, uh Luke is from Polychain Capital and also works on ZK Garage, which does works a lot of teams implementing Plonk or implementing different flavors of Plonk. So, this Luke's question is, "What does the combination of Caulk plus these other schemes look like? Perhaps Plonk? I'm not sure. I guess that's not a question, it's maybe a comment. Will there be a means of having them operate

over the same pairing curve?" I think that was the question. And if that's uh if I'm not being clearer than Luke, feel free to just jump in if you can or try and retype it and I can reread it. Yeah, perhaps it wasn't a form too well. It was um when looking at combining these, whether they can or can't be done over the uh the same pairing curve. It affect my my subsequent question. I am actually going to ask a question here. Like which do you think would be the problem for them to be in the same to be operating the same curve? Well, it wasn't it was I trying to combine them from a protocol uh

level, but I haven't uh I haven't finished it yet. And I did it with someone from a Noma and he said he he can't Oh, it Yeah, so it Um actually I'm I'm not very knowledgeable on uh the kind of curves that you use. Maybe Mary wants to take this one. I mean, if you have pairings, then you could write if there's a pairing curve, then you can run Caulk over that same pairing curve, it shouldn't be a problem. And then you can put them both in the same proof then? Yes. Okay. Well, I'll keep trying. Thank you.

Maybe ping me on that after cuz I'm not sure where you're getting stuck and it sounds like something that should be doable. So, yeah. Ping me with where you're getting stuck and I'll answer in more detail. Okay, thank you very much. Yeah, I was looking at whether you would need Well, I ended up not being able to do it and trying to look at saving efficiency with like half pairing cycles and then not knowing the most efficient curve to um place the Caulk versus the the Plonk over, especially with this the like the multi-opening mode for the logos, but I'll ping you afterwards. Okay, sounds great. Thanks.

I think related to to to to that uh very much is I I couldn't see a way of doing like Merkle trees with Caulk except with doing uh chains of pairings and the curves. Yeah, I don't know a way to do that either. That's a that's a harder question. Awesome. Uh So, I do have yeah, other questions. I'm just waiting for the people. Jump in. Well, other So, so one of one of the things I I wondered about the about this this paper. So, you give this this log n uh the prover has to do log n stuff for

it to prove this relation of unity. Yes. And one of my observations would that if the prover had access to an opening for of x to the n minus 1 at uh at omega to the i minus 1, whatever it was, would it be possible to get uh it seems to me like it would be likely that there would be a constant uh number of operations way of are it, if you could assume that. Not uh specifically constant. Uh that will still depend on the size of the set that the prover is opening. So, yeah, for m = 1, it will be constant. Otherwise, I think it will be m squared + m.

If if you make the our unity proof constant. Okay. Yeah, so I was kind of puzzled why you were doing this log n size thing. Yeah, I I we we strongly believe it's possible to remove it. Okay. Yeah. I would have thought that yeah, for the for the single case, it should be simple for the I don't didn't look into the higher m case. It shouldn't be. We think it should be. Yes. Um And the other thing I got wrong reading the paper is a bit nitpicky that uh I'm not sure if your first our unity is zero knowledge, but the overall

protocol is. What do you mean that is not zero knowledge? So so so Okay, so so so the simulator, if they know z, they can uh produce something indistinguishable from from from an honest prover, but it seems to do that they have to know z and not having a commitment to z, which is the actual input, doesn't allow them to do that. It might be useful to go back to the slide. complex. Yeah, anyway, it doesn't affect but the overall protocol, which I'm pretty certain it is zero knowledge.

Just the sub protocol, which isn't because you Yeah. For the unity proof of m = 1. Yes, the unity proof of m = 1. Uh but you're talking about the the details in the paper, right? Not nothing that isn't The details, yeah. Uh I I I don't have the paper here, but I'm pretty sure it's zero knowledge. Can I ping you about this later? kind of pretty certain it's not. The reason for that was basically because the input was a G2 element and the proof elements, which are G1 elements, and we didn't seem to be an easy way to get the G1 elements to depend on the G2 element. But, fair enough.

Okay, I will Yeah, sure. Yeah, this is not something to do online. Yeah. I will write to you for sure. Okay. Uh cool. Does anyone else have any questions for Arantxa or Mary um or about Plonk or comments about it? Okay. Um well, awesome. Arantxa, thank you so much for presenting this work.

Mary, thank you for joining as well. And uh thank you to everyone who uh attended today.