ZK14 - ZOOK: Zero-Knowledge IOPPs for Constrained Interleaved Codes - Giacomo Fenzi (EPFL)

Transcript

Yeah. There we go. Okay, perfect. Like look, so this is a specially uncrafted slide that I personally did with my graphic design skills. So, you can see it's really funny like The AI was extremely consistent choosing which symbol different people were. So, Ali is apparently a horse. Guy is a bottom and I'm some sort of like weird square, but anyways. So, this is Zook.

This is our work that we did with Ali and Guy and is about constructing zero knowledge Sorry? Uh much Yeah, okay. That makes more sense. I thought that just being Italian would be enough, but Okay, so this is our work on zero overhead. This is the Z O and the second one is supposed to be a zero, but the AI is not that good at it for zero knowledge. So, this is our work in which we want to construct real zero knowledge IOPs. And I'm going to tell you a bit of motivation like, you know, look we're at a zero knowledge conference, so you probably know why we care about zero knowledge, but I'm going to give you like a motivating non-blockchain example of why zero knowledge is important.

And Okay. And what I want to talk about and the reason why we started this work in the first place is that we wanted to do anonymous credentials. So, you probably are somewhat familiar with the concept. This is something that's been getting a lot of traction in in practice and let me just refresh on what it is. So, you have this this situation in which you have like some uh some uh entity, say a government or like maybe your DMV or whatever organization you feel comfortable with and you are an user which has a mobile device, and you want to like perform some action which requires some

authentication and some permission. Maybe for example, you have to, you know, go to some spicy website, and you have to prove your age. We can discuss whether this is a right or morally wrong thing to do, but this is another point. So, suppose that I want to do this. One flow is that what can happen is that the uh government can issue you a credential of something that the authority believes about you. For example, it might be like your passport, your information, and all of this. So, in this case, they might send you like this credential together with a signature that this credential has been authenticated in the uh as something that the government believes in.

Then, once you have that, as the user, you can store this credential and the signature pair on the device. And then, when you want to interact with like some store, what will happen is that the store will want to know something about you. So, it will issue some sort of challenge to you. And then, the user on the device can prove that the credential that he possesses is both valid, so that the verifies under the the signature scheme that the that the government is using, and that it satisfies some property, which since I'm a theoretical guy, I'm just going to say that things belong in some sort of relation and not say what they are. But, you can think of these like

for example, I am not in a list of banned countries, for example. And then, the store can verify this uh can verify this uh proof, and it will guarantee that the credential satisfies some property that the store might care about, maybe for regulations or for other things. So, in a setting like this, it's very crucial that this proof does not leak information on pi on on both the signature and the credential. Because if I'm able to get this pair, then one can replay and pretend to be this user, or I can start linking the the user to the action that is performed, which is terrible for privacy in many reasons.

Uh the question that we ask in this talk is you know, which proof system to choose, and suppose that we really want to minimize the bandwidth and the communication complexity, what should you want to do in this case? So, this is not just a theoretical uh a theoretical problem. Like there's been like a very like large line of work of people in practice and in theory trying to figure out how to do this efficiently. Famously, there's been the long fellow decay by by Google. There's the European digital identity wallet, which is supposed to use similar type of cryptography under the wood.

And then there's like been a few like different like companies and efforts that have been trying to like do anonymous credentials properly. So now I'm going to tell you about our approach in like choosing which is the proof system to do, and you know, I'm going to let the cat out of the bag. Like I like hash-based SNARKs. I spend a lot of time working on them, and they have like a lot of very positive very positive features. So, this slide I've recycled for the past like 10 talks I've given, so you know, bear with me, but they're When I talk about hash-based SNARKs, or I call them SHARKs sometimes, there's SNARKs secure in the pure random oracle model. So, the only cryptography which I'm assuming that I can use the random oracle. I don't want to use

elliptic curve, lattices, or anything like that. Just the ROM. And why am I constraining myself this much? It's because I want to have the properties that this SNARK gives me, which are the fact that I don't need to have any kind of of private coin setup, so I can have like a transparent setup, which is universal. I can have very highly efficient implementation in that I don't have to do any large field operations. Just to give you an example, if I am committing to 226 field elements in an ash-based SNARK, I can do this in around 300 ms. While if I were working to a group-based MSM like in a growth 16 bit, this would be on my laptop this

were around 3 minutes. And this is not a fair comparison. A benchmark are lies. This is one of the first lie I'll give in this talk. You have like a very well-understood security for this kind of SNARKs in that you have tight security bounds in the ROM. So, we are somewhat confident about their security apart from Fiat-Shamir which I don't know if Ron will touch upon later on. And you get plausible post-quantum security. You can give strong guarantees that these things are post-quantum secure and they're secure in the quantum random oracle model. Uh all these have made these ash-based SNARKs be very widely deployed. So, for example, in blockchains like a lot of companies have been doing this work and the Longfellow ZK that Google has been

using relies on this kind of cryptography. And to give you some example, you get like a very configurable system where you can play around with a lot of parameters, but you can get like prover time between, you know, uh 100 ms and 10 seconds on consumer hardware, which is pretty good. You can get a proof size can be as small as 100 KB or as large as 200 KB. And you can get verification which is really quick on the order of like under the microseconds. So, this is a um for something like an anonymous credential system where you have to like have things running on like a a client-side prover, these are like some numbers from which

you can have hope of actually getting a system which is deployable in practice. And what the Longfellow work showed among other things that this is something that's already possible right now on mobile devices. And there's been like all of these numbers they come from like a very like recent and very nice line of work in which like you know, we broke some of the broke some of the barriers that we had in hash-based NARKs. So, these are just not a fully representative list of works. Um uh but if you look at these very in the screen quickly, there's a big problem about all of these works for the anonymous credential case.

And the thing is that none of these things they they do zero knowledge. So, the recent progress in hash-based NARKs is mostly and almost entirely focused on succinctness, so getting proofs that are shorter to getting prover that are faster. And we haven't really looked at the zero knowledge that much. And this is in part because in the IOP world like um getting like zero knowledge, there's somewhat generic ways you can get to it. You can either use recursion with a ZK system or you can uh do some this trivial protocol that we'll see later on to get to get zero knowledge, but you pay like an overhead.

So, the question that we ask in this work is like uh can we get zero knowledge hash-based NARKs with the same efficiency as existing uh non-zero knowledge um uh hash-based NARKs up to low order terms. So, we call this property having zero overhead over the over the the non-zero knowledge variant. And uh uh you know, one reason why there's hope is that like when we're using more structured assumption like group-based or lattices, this is something that we already know to do. For group-based, for example, adding zero knowledge in uh in proof system is a very small overhead. It's not something that you pay. While in hash-based, the typical uh ways to do it which we'll see later on, they pay

around a 2x overhead. And you know, both uh us and Ron will talk about it later, they show ways to actually significantly reduce this overhead. So, let me tell you a bit about what we proved. So, what are our results? So, this is going to be the theoretical statement. Uh I'm going to skip all the part about arithmetization, all of it. I'm just going to tell you about the PCS that we construct. Uh which is a Zook, and I'm going to give you one particular instantiation of the of the of Zook, which is in a certain sense a dual knowledge version of the Warp protocol.

So, So, okay. Uh I'm going to uh tell you a few things. So, you have like a a claim where you want to prove with security to the minus lambda. And I'm going to assume I'm encoding this with some interleave code. You don't need to know exactly what it is at the moment. Uh it turns out it will be just a nice code to work with. But, this uh this is sufficient for a PCS, and I'll tell you a bit more about how this translate later on to PC to a PCS. But, what I can get and the resulting SNARK when I compute it will have essentially parameters depending on these parameters almost directly.

It's that I can get like a proof length, which is linear in in the rate of the uh sorry, in the size of the of the code word that I'm encoding. So, this is similar to things like Fry and Warp, for example. Uh and in this slide, I'm putting in red the overhead that we're getting over the non-decay version. So, the red part is the overhead, like the the black part is what we know to get with non-decay systems. So, we get queries where are exactly the same as in the in the non-decay version.

And both the prover time and the verifier time also pay like a tiny overhead over the non-decay version. All of these while getting perfect honest verifier zero knowledge. So, in particular the zero knowledge error is really zero. There's like the it it is like and you might ask him why wait Giacomo, why do we care about honest verifier zero knowledge? Well, turns out turns out oh, uh the transition will come later that in hash-based NARCs like honest verifier zero knowledge uh in the IOP will give you a malicious verifier zero knowledge in the SNARC once you compile it. So, this is sufficient for what we need for anonymous credential for example.

So, the the the highlight is that this is a uh you you see the like the overhead is like a quasi-linear in security parameter and think of the security parameter as being like, you know, 128 while m is on the order to the 20. So, this is like a really a tiny overhead over the over the existing um non-ZK version and in our instantiation we get like things which you can think of like as the ZK version of breakdown and work. Uh there's this this is the Okay.

Plus we also do when we go back to this work like breakdown, we give guarantees in terms of like some of the newer things that we know about coding theory. So, in particular, we uh show the breakdown as least is at least secure in the list decoding regime which reduces the proof size and a straight line on a soundness which is good for things like UC security. Uh further, the techniques that we use in this protocol are fully code agnostic. So, you can use whatever code you want and this will give you a protocol.

With caveats, the code needs to have a property which is called being a zero knowledge code for which we will talk later but I place this work in kind of like this new line of work in like uh code agnostic SNARKs of which if you want to know a little bit more about, Ali will give a talk about at IOP Fest which is on on Which you should also come because it's a great event and not because I'm organizing it. Okay, and different code will affect the things that depending on some properties that we call the code switchability of the code, which I'm not going to touch about in this talk. For this you will talk about later.

And to do this we do like a framework for ZK, so we show that there's a toolkit of zero knowledge interactive oracle reductions that when you compose them, you allow you to um get this overall protocol. So you have like a very modular way in which you can build these uh state-of-the-art zero knowledge protocols. And if you want to learn about IORs, we also have a talk for that by William at Iopi Fest. Okay, good. So this is what we want to get. We're going to get like a system if if you take away the red part, this is exactly like in war.

And we're going to do it with perfect completeness zero knowledge. And I'm going to tell you, you know, but you know, look, I think at least some people in the room there are practitioners so what about concrete efficiency? Like we're very like we uh you know, we enjoy asymptotics as the next guy, but if the you know, the big O notation hides a lot of things. So I'm going to do something a bit different. I haven't seen this in the slide doing before, but modern hash-based protocols they're extremely configurable. There's a lot of things that people can do. There's parameters you can tweak, proof of work, Merkle capping, and all of it.

And typically you see like a lot of trade-off between prover time and verifier time, and it's hard to capture really how to compare protocols between each other if you're just looking at asymptotics of some of the metrics. So what I'm doing in the next slide, I've I've decided to do something a bit different, which is to plot the Pareto frontier of like different protocols. So let me remind you what a Pareto frontier is. Uh so a Pareto frontier is basically a graph of a trade-off in which you have on one side you have a proof size and on the other side you have an argument size.

For Okay, you can have other different thing, but for this particular case, and the proof size think of it as a proxy of the prover time. Like, the prover time is almost entirely determined by the proof size. Not exactly true, but a large part of it. And the argument size is the determined the verifier run time. And these are quantity that we can exactly determine from the parameters of an IOP. Now, the frontier will be the curve where like there are like m- where there are no configuration which are better in both of them. So, these are kind of like the there there's the this concept of design which are dominated. So, these are the For example, there's no reason why I should choose this point because there's always a point which has as like a smaller

argument size at like a smaller prover time. So, these are like a the these orange dot is worse than the things which are on the green comparable sense. So, if you're doing a protocol, you should just always choose something on this Pareto frontier. Okay? So, good. Now, what I'm going to do, I'm going to do look at some protocols. I'm going to look at the in particular Aurora and Zcash. I'm going to look at the Pareto frontier and then see how this compare and what is the overhead. And this is what the uh Pareto frontier of uh Aurora looks like. So, again, this is the IOP proof length.

Think of it, the higher it goes, the lower the prover is. And this is the BCS argument size, which uh the smaller it is, the the smaller the proof is. So, you want to be as close to zero zero as you can. Of course, you cannot, but uh you can go want to go as close. And you can see that like as the proof size goes up, the the argument size shrinks. Right? And each of these dots is a different like configuration of WAR. In this case I've chosen like the the initial rate of the use for the protocol to call to color code them. So, but yeah, so this is kind of like what this looks like.

So, okay, good. This is one Pareto frontier that doesn't tell us anything in isolation apart that you can either a good parameterization for WAR. And this is what Okay, I'm a theoretical guy. I have no idea how to make this graph. GPT 5.5 law amazing at these things. You know, honestly I'm yeah, really surprised. And this is for Zook. So, this is the Zook graph. So, you might have asked Jaco, why isn't there too many more dots? It's just because there's more configurations to to be done.

And you also cannot understand anything from this graph. So, I've just taken away all the clouds and this is the comparison of the two protocols. So, the black is a WAR while the blue is a Zook. So, what is zero overhead the theoretical zero overhead we're talking about? It's just this lever between the two Pareto frontier. And I'm going to zoom in a little bit for you as well. This is the kind of area that we typically care about. And you can see that the overhead is kind of like I don't know, in this case here is basically 5 kilobytes.

Here you get get basically the same sizes. So, what I'm saying this is a kind of nice because we're in a very blessed field in which asymptotics don't lie too much. And the asymptotic improvement that we that we get actually show concretely in like a very tiny overhead in argument size. So, overall like the really what we can show with this graph is that I mean, the proof length which is a proxy for prover time and the argument size which is a proxy for verifier time are really zero overhead.

So, this is what what we can show with this graph. Okay? Good. Now, let me tell you a bit about actually we go around and to to getting these things. So, this should not have come up here. I'm sorry. But, we're going to have two protocols. So, one of them is going to be a sublinear protocol. And this is kind of you can think of it as the Wow, the transitions are really awesome on this one. On the Uh this is going to You should think about it about the zero-knowledge version of breakdown.

And how does this look like? So, we're going to have like a few reductions. So, we're going to have a first one which takes our original problem, we say it's in R1CS, and in a zero knowledge it will reduce it to some problem about interleave codes. And we'll see what this is about in the later talks. This problem of interleave codes will be then reduced by uh these zero-knowledge sum-check protocol that we're going to see see later. And you should think of it is that this problem will take the the the thing which the original problem which is of size n and reduce it to something of size n over k in few queries over like the alphabet F to the k.

Once we've reduced by this amount, and you should think of k to be around square root of n. So, I'm going to like reduce by square root of n. Then, I'm going to apply this uh ZK trivial protocol, which has a linear communication with the prover and verifier. And the idea is that once the problem size has been reduced enough, you don't really care about paying twice or red or paying like linear prover length. So, I'm happy to pay like a square root at the end. Then, this is the ZK breakdown version. You And once we want to do a succinct protocol, it's going to be extremely simple similar in that we're going to do the same steps, only that in the middle we're going to

throw in a ZK code switch. And so, the strategy is going to be the same. Now, I'm going to reduce by instead of square root by a logarithmic factor or a constant factor if that makes it easier. Then, I'm going to I'm going to start with an interleave code. And the interleaving property is what allows me to fold and reduce the problem size. But now, you know, if I go from C to the K to C, I don't have any structure to deal with anymore. So, if I want to fold again, I need to go back to an interleave code. And this is where we're going to use the code switch protocol to do this.

Then, after I can code switch, I can fold again. So, I'm going to reduce by log n. And I'm going to just apply this this thing a few time like around log n times. And this And then at the very end, I'm going to again apply the trivial protocol. Okay? So, for today for this talk, we're going to be focusing on a sublinear protocol, and we're going to be looking at the ZK sum check and the ZK trivial protocol. And at ZK proof on Sunday, I'm giving like another version of these talks in which we're going to be focusing about the missing parts to get to the succinct protocol, which are the ZK codes, the code switch, and the composition of like IORs.

Okay? So, this is the road map. We're going to go to We're going to show how to do ZK sum check and ZK trivial. Okay. Good. So, first, let me Okay, they both work. Great. Um okay. Yeah, I'm happy with that. So, we're going to be like looking at one particular type of relation which is sufficient for PCS, and this is going to be constraint codes.

So, this is happening in a bunch of previous works, but roughly, we realized that for a linear code C, what we really care is about checking proximity to the following relation or the following language, which is the language of like codewords, which have a certain value under a dot product. So, in particular, I'm saying like the for convention, so you have a constraint and a value of constraint. So, constraint, think of this as like basically being polynomial evaluation, but it can be whatever.

And then you want it to have some certain value. And this bold at F, by convention, is the message underlying the codeword. Okay, so what I want to check is that some some F, which I have oracle access to, satisfy the property of being close to a being close to a codeword whose decoding satisfies certain constraint. I'm ignoring a lot of things. This only works very well if via some succinct description, but I'm going to ignore just verify efficiency for this talk. You You can use these which are good enough.

Um and this basically is the soundness guarantee that you want to get. So, if if they an instance is delta far from this um language, it means that for every codeword which is close to the to the to F, the message does not satisfy the constraint. Okay? Good. And these are enough to build a PCS. So, I'm going to first show you the most stupid protocol that you can think about about checking something like this.

And I'm calling it ZK trivial for now. So, what's the setting? You have like some F, and this F is claimed to satisfy some constraints. And you have a prover and verifier that want to check this. Okay, what's the most stupid protocol you can do this? Um just going to send the the the uh the decoding of F and then the verifier just going to query the original thing a few times and see whether it is actually is consistent with the encoding of it. Of course, this doesn't work because we want to do the knowledge. So, I'm going to just you know, just mask it.

So, I'm going to just say like I'm going to sample a random codeword G. I'm going to tell the verifier what is the value of G on the constraint. And then I'm just going to take a random combination of of them. So, what will happen is that the prover will send you the random G, the decoding of the sample G, plus gamma times F. And the intuition that you should have is that G is perfectly masking the value of F. So, it's kind of like a one-time pad of F. And then I'm going to just check consistency of F with the encoding of these two things. So, in particular, like I'm checking that the encoding of the the witness message C, when checking at

these spot checks, matches with the encoding that I've the prover has sent to to me. And also I'm going to check that this HV satisfies the constraint that I care about. So, this is not I'm not doing any slight of hand for now. Uh you can also check more complex things, but we're going to see this why this is useful later. So, good thing is that the soundness of this protocol is very good. We know how to analyze it now, even in list decoding. And if you want to know about more about this, you can come to Dan's talk at IOP Fest. Then the protocol is perfectly honest verifier zero knowledge in that the random G completely masks F.

Then on the part of the overhead is terrible. Like I'm sending this G, which is as large as F. So, I'm like my proof's length is doubling. And so, I'm not to as overhead. So, and the number of queries now I have to query GNF. So, this is going to be complicated. So, it's fine. I said it before, we can pay this overhead, but we just have to shrink the problem size first. And the way we're going to shrink about the problem size is via interleave codes. Okay, what are interleave codes? So, code interleaving is uh this property is a thing where I take like the a code and operate a code and then I define the code where you should think about it is like uh you

you take a message, which is in K times L, so K is the interleaving factor, and L is the message size. I reshaping it into a matrix. And then I encode each row of the matrix. This property this interleaving has got like good properties in the sense that like it preserve the minimum distance of the code, even though you change the alphabet size. It preserve the rate of the code, so you're not doing much work more work than before. And the encoding times actually somewhat improved because you are uh you can perform each of the encoding in parallel.

So, this is a actually significantly faster, for example, for Reed-Solomon codes than encoding with a Reed-Solomon of the same of the same size. The more important important thing of interleaving, to me at least, is that interleaving make give you a generic way to take any code and make it shrinkable. So, as make any code and just make sure that you can apply sum check like protocols to reduce the problem size. Originally for RS in like FRI, it was done by like the the what I call FRI folding, which was about this move code and interpolation, but in reality you don't need it. You can take uh interleaving and just uh take Reed-Solomon and interleave them and get protocol which have like very

similar features. So, yeah, interleaving is like a generic way to to a code uh shrinkable. Okay, how I'm going to use this? I'm going to do this thing which is going to be interleaving folding. By the way, I don't know how I'm doing on time, so just uh shout if I am uh yeah. So, I'm going to show you how to actually use this to shrink a problem size for this case, I'm just going to reduce something without constraints. Uh I have my codeword which might be corrupted. This is an interleaved code.

And my prover and verifier. Okay, how I'm going to shout you we only have one trick in proof system is that I'm going to take a random linear combination. Like the I'm going to take a combination of the first row with the second row. And this is going to be a virtual function this fold. So, if I want to query the fold at any location, I can just query the corresponding uh position in the in the original codeword. So, fold as F at gamma at Z is just going to be the fold of F0, this is first row, with F1.

And I'm going to just choose this particular type of interleaving because it will play very well with sum check later on. And I can iterate this more, but it's not too important. The The two important thing the properties of this folding is that first of it is local. So, if I want to compute a value of the of fold, oop, I don't know what that was about. Is that me? I don't know if this is me. Uh no, there were like some weird ends going on. Okay. Um I don't know what that was about, but So, if I want to compute things of fold, I can just query the corresponding codewords and it is fine.

But the most important and more crucial thing is that you have a distance preservation property. So, if F is actually far from an interleaved code, then the fold will also be delta far from the interleaved code. So, the you should think about it the fraction of corrupted entries in these uh in these um uh will not decrease once you apply this folding operation. I mean okay, I won a minute. So, I'm just going to show you very quickly the DK sum check which is a very Okay, so what I'm going to do I'm going to apply this folding operation interleave with a sum check.

So, the first step is going to take my claim which is a dot product and of course do the only thing I know to do which is rewrite it as a sum check. Okay, I want to do sum checks so I want to send this H of X which is the sum check polynomial. The issue that H leaks so H will leak information about what's the what are the values there? So, what should I do? I should mask it. And I'm going to consider this particular mask sum. So, this might look a bit weird but I'm going to tell you why I chose it. I chose it because this is a technique that was used in Libra.

Roughly you if you look at what the sum check polynomial looks like once you do this this particular operation you end up having like a perfect one of the the sound factors out so this perfectly mask the old subject polynomial. And you can compute this extremely easily because you this is like computing the original subject polynomial plus some work which is very structured and very dense. Now, the problem is that now you have to figure out you know, you have this mask so you have some new things to send so you have to somehow commit to them.

How you going to do them? Well, you going to use another code. You're going to use a DK code to commit to the this smaller mask. And then I'm just going to use the trivial protocol in a certain sense on this mask so the protocol is going to say I'm going to send a commitment to the mask. I'm going to send the new updated sum. I'm going to take a random combination of the two. I'm going to send the mask subject polynomial. And then I'm going to like get the subject randomness. And if you look at the sum, this is what roughly the verification looks like. And I can replace this particular thing with a claim on the folded sum.

And I can repeat this as many times as I want. And this is now just now a joint claim on the on both the finger encoding on F and the and the ZKA code in encoding. And uh Yes, the ZK trivial protocol can be adapted to to to uh adapt to this. Okay, I'm going to put all these things together. I'm just going to show you the last slide as I promised, which I'm going to kind of like tell you how I put all of these things together to get to the thing. So, let me actually just go all the way through it.

Very quickly. But basically, I'm just combining first I'm applying this ZK sum check K times to define a new fold with the you have the K mask to mask all of it. Then I'm I'm going to apply this ZK trivial protocol. And if you look at the overhead, basically you can look at query and proof length of this protocol. You basically already steal the overhead. So, when I query, the queries all to the original oracle are the same. Now, I'm going to have to query this G as well, but this G as well will be uh I can commit at the top of the at the top of the protocol, so I don't actually pay much in queries.

And I have to now query the ZK codes, which I think now I'm going to come with this is the biggest overhead. But since these codes are so small, they're going to be encoding like a constant amount of coefficients, I'm just going to set them so that their distance is really large. So, this part here just kind of vanishes in the asymptotics. Similarly, for the proof length uh if I with typical parameters, roughly this part here, the black one here, dominates the entire the entire uh uh protocol, while the additional things that I'm sending just don't really deal with anything.

So, this is the old protocol. Sorry, I had to rush a bit at the end, but yes, come talk to me later on if you want more details and about the rest.