Optimised Merkle Caps

Transcript

[applause] >> Uh I My name is Anubhav. I'm a PhD student at the University of Pennsylvania. Uh and today I'm just going to be talking about uh this new primitive that we kind of came up with called vector commitment schemes and how we're trying to use it to reduce proof sizes for succinct arguments or hash based succinct arguments. Uh so this is a post quantum cryptography workshop. So I'm sure you have already heard a lot about the virtues of hash based succinct arguments. Uh you know that they have transparent setup. You know they have really fast provers. You know that they're plausibly post quantum secure with many constructions already like proven secure in the QROM. But you are

also probably very much aware of like their main limitation, which is that they have very large proof sizes. And to just belabor the point, uh if you look at for example WAR, which is Reed-Solomon based succinct argument, uh it can have 300 to 500 kilobyte proofs uh uh depending on some assumptions. And if you look at the fastest end of in terms of like prover time uh for these hash based succinct arguments and you look at succinct arguments based on the Bolt code, then those uh arguments have even larger proof sizes, like 6 to 12 megabytes in fact.

And uh for comparison, if you look at non-post quantum uh succinct arguments like Bulletproofs, they're only a few kilobytes. And Greyhound and other lattice based uh succinct arguments can give you proof sizes that are on the order of 50 kilobytes. So the situation for hash based succinct arguments in terms of proof size is less than ideal. Um so before we get on into I guess uh how we are going to actually solve this problem and like reduce proof sizes and uh while potentially not losing any of the existing positives of these hash based succinct arguments, we'll just recap some of like the basics

of how these things are constructed. So, the key information theoretic object that concerned us are interactive oracle proofs, IOPs, which consists of a prover and a verifier. The prover receives an instance X a witness W. The verifier only receives the witness X. And the prover and the verifier and what the prover wants to convince the verifier of is that this tuple X W is in some relation R. The prover and the verifier then engage in some rounds of interaction where in each round the prover sends an oracle to the verifier and then the verifier returns challenge back and this continue and this

happens for many rounds until the interaction ends and then the verifier makes queries to these oracles and learns whatever values were at those positions in those particular oracles. And then once it learns the values of those oracle positions, then it decides to either accept or reject. Great. The two standard properties of interactive oracle proofs that one should expect are completeness, which is that if X and W are in relation R, then we should accept. And if the prover is malicious and it's trying to convince the verifier of like some instance that doesn't even belong to the

language, then the verifier should reject with overwhelming probability. Okay. Another key ingredient of hash based succinct arguments are vector commitment schemes. And the vector commitment schemes are also something that I'm sure all of you are familiar with, but I'll just recap it very quickly. They involve a commitment protocol where you have a committer and a receiver C and R. The committer has a large vector with it a And what it does is it just compresses it potentially down to a commitment CM, which it sends to the receiver, which binds the committer to the entire vector V.

Once it has sent that commitment to the receiver and the receiver has CM, then the commitment then the committer can prove to the receiver that the underlying vector that of this commitment CM uh is consistent with uh the values S on the query set Q. So, the committer is therefore able to prove a claim of the form V at Q is equal to S via this proof pi, which is the output of its open protocol, and then the receiver takes as input this proof pi and the original commitment CM and outputs a decision bit zero or one, just checking

if this is consistent with the original or not. Uh and uh a malicious prover should not be able to cheat if the if the commitment CM was binding. Okay. So, and how do you get from IOPs to hash-based SNARKs? You first start with your IOP. You take every single oracle that the prover sends in this protocol, and you compile it with what's called the interactive BCS transform, which essentially just involves replacing every single oracle with a commitment and the at the end of the interaction, the prover then simulates the IOR IOP verifier

and figures out what queries the IOP verifier would have been making to these oracles, and then in addition to sending these like query sets to the interactive argument verifier, it also sends a proof of opening of all of these different query sets on their respective oracles. So, after this transformation, you still end up with an interactive argument you still end up with an interactive It's just not a proof anymore, it's an argument, and its soundness is computational or information theoretic. And but once you obtain this interactive argument, you ultimately you want something that's non-interactive. So, all you have to do is you have to apply Fiat-Shamir, and then this entire transcript gets boiled down into a

single proof pi, which the prover can send to the verifier, and the verifier can just check in one shot. Okay. And the overall uh prover time uh of the resulting non-interactive argument is usually on the order of the prover time of the IOP, and not too much more than that. Particularly because the vector commitment schemes that we tend to use uh for these hash-based SNARKs, like Merkle commitments, are like reasonably fast.

And so, therefore, even though this is like a slight uh oversimplification, the prover time is roughly on the order of the prover time of the IOP uh prover, and the proof size, however, involves Q times log n many uh hashes. Q is the total number of queries that the verifier would be making that the IOP verifier would be making to all the oracles, and the log n factor comes from the height of like the Merkle trees that uh every oracle has been committed with.

And the verifier time is accordingly the computation of all of all of these Q log n hashes and the IOP verifier time. And so, okay, what is the cost of like really authenticating these queries in terms of proof size? So, as uh we mentioned on the last slide, uh the number of queries by that are made by the IOP verifier, which is Q, the Merkle path length, which is log n, and then that we have a hash size, which is typically 2 lambda many bits, where lambda is the security parameter that uh you're working with.

And uh in terms of trying to optimize this So, our goal here is to in some ways like bring down these different variables, right? And, there has been like a lot of work in optimizing the first component here. And, I'm just going to give you like a comically large list of things that people have worked on on both the IOP of proximity front and on the side of improving different codes and getting better proximity gap results.

And, in general, yeah, people and yeah, including myself have like been obsessed with just optimizing the number of queries that the IOP verifier would make in order to bring down the proof size of the of the resulting non-interactive argument. Uh, but not too much work has been done on optimizing the second component, which is the Merkle path length. Uh, because essentially like all of these different uh uh SNARKs that people obtain from compiling these IOPs all just use Merkle trees, right?

And, there really isn't a good alternative, at least in the random oracle model, if you're not going to make any extra assumptions like that, other assumptions, uh to using Merkle trees. And, so that is the part that I think has the most potential for improvement, and that is the part that we are going to focus on in stock, uh which is to optimize this log component of that comes from the vector commitment scheme. Okay. And, how do we I guess like go about it?

Uh, so as mentioned on the last slide, there has been an absurd amount of work on IOPs, IOPPs, and codes, and on the vector commitment side, there's only Merkle trees. But, because of this absurd amount of work, we we are kind of spoiled with all of these different techniques that have sprung up in the last 10 years or so, which are related to sum-check, proximity gaps, other domain sampling codes, switching, yada yada and all of these techniques are useful for improving the prover time and proof size, prover time and query complexity of the IOPPs but we want to ask if we can use all of these techniques in order to improve the vector commitment part without

sacrificing prover time too much. And fortunately, the answer is yes, but we need some work and by work I mean we kind of have to almost like the reinvent like the wheel in a few places. So, the road map for this talk is going to be in the following order. First, we're going to talk about Canopy, which is what we call the resulting construction, which is kind of like a vector commitment scheme where we are able to use these proximity and code related ideas to get smaller vector commitment openings.

Unfortunately, Canopy is not a VC scheme, so it's not like we can just drop it and use it as a black box replacement for Merkle commitments and use previous work on like compiling these things into a non-interactive argument. We kind of have to do that work on our own because what Canopy really is is a VCR, which is a vector commitment reduce scheme and we will later see what VCRs really are and how the definition of Canopy itself motivates the definition of this more abstract object in VCRs.

And then, once we have nailed down this definition, we will discuss how we can generalize the BCS compiler to use arbitrary VCRs instead of Merkle trees. And then, once we are through with all of this theoretical nonsense, we we finally get to some cool applications, uh, which just means that we'll use Canopy and our new compiler to create better SNARKs and better accumulation schemes with smaller proof sizes, where we are able to get some not too bad concrete improvement improvements for both of, uh, for both of them.

And we also get this, I guess, uh, somewhat interesting asymptotic result for accumulation schemes, where instead of requiring lambda log n hashes in order to accumulate like a constant number of incoming instances, you actually only need lambda square root log n hashes. Uh, this is a result that we won't have time to discuss today, I believe, but, uh, uh, yeah, Partition I will be happy to talk about it later. Okay. So, let's start with Canopy and how we optimize these proof sizes using ideas from the IOPP literature.

Okay. So, let's just start with what Merkle trees are. So, more everyone is here is, I'm I'm sure familiar with Merkle trees. You have a vector, and you just hash every single, uh, element of that vector, and then you create a binary tree on top of it, where the every where every single node in the Merkle tree is the hash of the concatenation of its two children. And the commitment is the root of the Merkle tree, and that's it, and you're done. And what does the opening protocol look like? If, uh, the prover wants to prove to the verifier that V0 is indeed the correct value that was in the vector that it committed to, then it will just return the co-path of V0, which includes

the sibling hashes of, uh, all the nodes from which are on the path from V0 to the root. And using these, uh, sibling hashes, the verifier is able to check, uh, that the value V0 is indeed the thing that was committed to in the with it in position zero. So, in terms of efficiency, it's uh, commitment size is tiny. It's only 256 bits, which is pretty good. I mean, it's basically the best you can do or almost the best you can do.

Um and the main issue with this is that the opening proof is quite big, right? Even for one query, you would require log and many hashes. And typically in these IOPs, uh you often want to make lambda many different random queries. And therefore, the number of hashes in your IOP blows up to lambda log n. And if each hash is like lambda bits, then you're already looking at lambda squared log n many bits, which is uh not great and it is one of the and it is like the main reason for why hash-based SNARKs have such a large proof sizes.

Okay. So, what is a naive solution to this? What you can do is you can just chop the top of the Merkle tree. You can look at a Merkle cap, and you can compute the partial Merkle tree from like the leaf layer to some height D. And instead of just sending one root, you just send this entire cap, which is the a vector of roots of the different subtrees. Okay, which we are going to refer to as H in the next few slides.

So, for each of So, so, so, so, now, when you want to open any index in here, all you have to again do is return the co-path, and you have to check it against the appropriate root in the cap layer, and that's it. The obvious problem with this construction is that the commitment is now way too big, especially if you're going to be using D that is any non-trivial value, then your commitment is going to be extremely large. So, the only values of D that you can really use here, but practically speaking, look like log n minus five, log n minus six, something like that. If you try to even

let D be equal to log n over two, for example here, then the length of your uh Merkle cap layer is going to become square root n, which is already horrible. You don't want that. Uh but the main advantage of I guess just thinking about Merkle cap in the first place is that you do get a smaller opening proof if your D is uh smaller. In that instead of lambda log n many hashes, you end up with lambda D many hashes. Okay. But of course, we haven't made like a lot of progress here because the commitment is way too big.

Okay. So, what is the solution? And the solution is uh I guess our construction, which we are calling Canopy. And in some ways, it is maybe the most natural thing you can do once you are looking at the idea of a Merkle cap, and you're looking at codes, and what you just do is you just combine them, right? You compute this partial Merkle tree over your input vector, and then you encode this layer, this I guess Merkle cap layer, under an error-correcting code C.

Uh after you have taken every single element of this layer and converted it to a field element uh so that you can I guess define a code over it. And then once you have this code, you just commit to this code word C with a Merkle tree, and you send the root of this tree. So now, the commitment of our construction is the root of the Merkle tree that's on top of this code that is an encoding of the Merkle cap of the original vector. And that is the entire commitment construction for Canopy.

That's it. Okay. Uh what Okay. But uh now, how do we really open this? So, earlier in the in the Merkle cap case, the verifier already did have access to every single thing in the Merkle cap layer, right? Um but, now it doesn't. So, even if the prover sends the verifier this entire co-path from P0 to H0, uh the verifier doesn't even know what H0 is, right? Because all it received as a commitment was RT, the root of this code, and nothing else. It doesn't know what H0 is. So, what does it even do? Okay.

Um and yeah, so how does it check that H0 is the correct root? And the answer is that right now, it doesn't even necessarily have to do that. And I'll explain what that means, but uh what it uh uh what at a high level at least means is that it just defers it and just emits a new claim. And it is something that it leaves to be proven later on, and it's not something that it immediately wants to uh prove.

Okay. So, what does that look like? In particular, if your query set is just the singleton set zero, and the corresponding value is B0, then okay. First of all, you would just compute the co-path up to the uh this Merkle cap layer. You would send the co-path, and then the the claim that you would emit is that the zeroth evaluation of the polynomial underlying this code word C is H0. If the prover can somehow prove this evaluation claim about H, the polynomial interpolation of uh the Merkle cap, then you would indeed have uh proven that okay, V0 is indeed like

the correct value that corresponded to the vector that we committed to. Okay, but this is a little bit uh vague and uh not super formal, but we can formalize this like a little bit by saying that the claim is just that the root commits to vector that is close to the encoding of H such that the multilinear extension of H evaluated at zero is equal equal to H0. So, now we're looking So, so now this is starting to look a little bit more like the kinds of claims that you find in IOPP literature.

Right? Okay. So, that's good well and good, but this is only for one single I guess leaf query, and usually, like I mentioned, you don't get one single leaf query, you get lambda many leaf queries. So, what happens if you have like a an arbitrary query set? Uh what happens is that you would do this check for every single uh J in your query set. So, for every single index in your query set, there is you just define BJ to be its block number, which essentially refers to what root it corresponds to in the Merkel cap.

And then from and and then for each of those indices in Q, it sends the co-path from the leaf to its to HJ. And it then emits a claim that root commits to a vector that's close to the encoding of H, and that the evaluation of the multilinear extension at BJ is equal to HBJ, and it would do this for every single J that's in the query set Q.

Okay. So, now we have like these size of Q many different evaluation claims over the multilinear polynomial H, uh which is not great, but the nice thing is that these are polynomial evaluation claims, right? And polynomial and claims are extremely batchable. In particular, the way you would batch it is you can essentially reduce all of these size of few evaluation claims into one single evaluation claim via sumcheck.

And so therefore, instead of emitting these size of few many different evaluation claims, what you can just in fact say is that it emits a sumcheck claim which is of this form. Where f of x here just represents some set some vector of coefficients that can also be materialized by the verifier succinctly. Okay. Now, we have established what the open protocol is well as and we now know what the commitment protocol of Canapé looks like.

But we there's still I have been using this phrase emits a claim emits a claim. I've said that like four or five times. And it it's still unclear what that even means. And to formalize that, we first have to take a small detour and talk about interactive reductions. So what interactive reductions do is that you have a prover and a verifier who are engaging in some interactive protocol where the prover wants to prove to verifier that some x comma w tuple is in the relation R.

And instead of the verifier at the end just then accept reject, what happens is that the prover emits a new witness w prime and the verifier emits a new instance x prime. And then you have essentially reduced the claim that x comma w is in the relation R to a potentially simpler claim which is x prime comma w prime is in R prime. So R prime is in some ways a relation you can think of that you is easier to prove and therefore if you can develop a way of uh uh finding an interactive argument for R prime,

then you will be able to find an interactive argument for R by composing this interactive reduction with the interactive argument for R prime. Okay. And similar to the completeness and soundness properties of IOPs, these also have uh completeness and soundness properties uh defined in the natural way, which is that if X and W are in the relation, then the verifier accepts, and additionally, this emitted tuple X prime W prime is in R prime. And you also have a version of knowledge soundness, which is that if V accepts and X prime men W prime is in R, then there exists an efficient polynomial time extractor that can look at this W

prime and can look at the transcript and output a W such that X {comma} W is in the relation. Which is a strengthening of uh what the natural definition of soundness for interactive reductions would be. So, you can kind of already maybe see where we're going with this, that uh once we have this notion of interactive reductions we have the language to define what Canopy is doing, and uh to now then say it formally, firstly, the commitment protocol is this uh potentially interactive protocol between uh the committer and the receiver, and it for Canopy, it involves sending uh

the root, which is the root of the encoded uh Merkle cap, and the receiver returns uh an alpha, which is an evaluation point, uh and the ca- committer then returns the evaluation of the Merkle cap polynomial evaluated at uh alpha. And this alpha and H hat alpha are uh outer domain samples. We won't dwell on it too much, but uh the idea behind outer domain sampling, this is an idea that goes back to deep fry and stir and many other works have used it since then. And the idea is that they allow you to achieve binding to a single

polynomial in the list decoding regime, which decreases the query complexity of your IOP. And uh this the way it manifests in canopy is that instead of is that it helps the committed to bind itself to only one single Merkle cap polynomial in the list decoding regime. Okay. And then as mentioned in the last slide, when we define interactive reductions, now we have like the language to define the opening protocol as an opening reduction where the claim of the committed is that this P evaluated at Q is equal to S, the

committed and the receiver engage in an interactive protocol, and then instead of just saying the receiver saying accept or reject, uh the two of them emit a new claim, and the new claim is the claim that we were discussing, which is pertains to the proximity of this uh purported word to the error correcting code defined over the Merkle cap. In addition to the sum check claim defined over the polynomial corresponding to the Merkle cap.

Okay. And now we can also discuss like what the efficiency of canopy looks like. So, the commitment is still small, it's just one hash, and additionally there's one field element, and really nothing else. And then the opening proof is smaller. If you only If you're only looking looking at the opening proof for this opening reduction, then of course it's smaller, right? Because instead of lambda log n, like we discussed for Merkle trees, it's going to be this it's going to be what we get for Merkle caps.

It's going to be lambda times D because there are D many hashes per query and you get lambda times D many total hashes. So now the question is that haven't we just like kind of kicked the can? I mean, we're just saying that oh, we have reduced this claim down to the sum check claim and the cost of doing this reduction is smaller than the cost of doing Merkle trees where and on the contrary, Merkle trees prove the claim, but we are yet to prove the claim. So, what if proving itself is like proving this output sum check claim is also expensive

and then you go above what you would do for Merkle trees, right? And the idea is that when you are looking at this output relation R prime for Canopy, which is that root commitment to a vector that's close to encoding of H and then we have a sum check claim over H prime. The key thing to notice is that H is very small. So, the input vector had length N, but the Canopy but the Merkle cap has length N over 2 to the D, where D is the height of this partial Merkle tree.

And because the length of this vector this shorter vector is N over 2 to the D, and which can be much much shorter even if D is like five or six, right? It that's you're looking at N equal you're looking at a message length of N over 32, N over 64. That means you can use codes of very very small rate and therefore very very good distance. So, in particular, you can use rate 1 over 4 to get this thing and ultimately, the idea is because you're able to get very very good distances for the code word in this Merkle caps layer, therefore, the number of queries that you would make in order to prove this

output claim R prime would be very, very small. So, you might be making the the same number of lambda many queries to the original oracle, but to this canopy oracle, you will potentially make like lambda over four queries, lambda over eight queries. You get this like huge constant reduction in the number of queries that you will be making to this canopy layer depending on what your height is and because the height of your partial Merkle tree is what dictates what block length you can use.

And remember, you you might now also want to say that, "Okay, why couldn't we have just like done it like on the uh like the base layer? Why are we doing it like in this middle layer and doing all of this like complicated stuff?" And the main idea is that we do want to keep the prover time uh as low as possible. We don't want to incur huge overhead in prover time. And if you had just used this high distance code on uh your input oracle, then that would have drastically increased your prover time, but because the message length of this

intermediate layer is so much smaller, the encoding time for the canopy layer is only a small fraction of the total commitment time and therefore you don't get a huge overhead in prover time and you are still able to get a boost in terms of proof size. And the uh there are a couple of other nice features about doing about you about canopy in particular is that even if you had like different commitments, uh once you create their canopy once you obtain their respective canopy claims, then you can batch those canopy claims together, which can then further

help you reduce your proof size. And this will be relevant later when we discuss how to get better proof sizes for SNARKs. And same goes for accumulation, but we won't have a lot of time to discuss that. Okay. How are we doing on time, by the way? >> We're doing very well. Thank you so much Anoop. We have about 20 minutes left including Q&A.

>> Oh, including Q&A 20. Okay, sounds good. So, I think I have uh yeah, about maybe 10 to 15 minutes of content. Uh so, now now that we have discussed what canopy is, we do want to talk about what a more abstract notion for the object that we have created is because we are discussing this very specific thing where the interaction is where the commitment is interactive, where the opening is interactive, and then you output a sum check claim, and you're doing all sorts of stuff. And it makes sense to not talk about the our specific construction, uh but if we indeed want to compile an arbitrary IOP with canopy, it makes more sense to

kind of abstract away whatever we're doing with canopy and generalize it to a definition like a VCR scheme. So, VCR schemes involve first commitment chain. >> check with the with the audience if there's any questions on the first part of the talk? Is that okay with you? >> Oh, yeah, sure. Okay. Yeah. >> Any questions on the the first part of the Okay. >> [clears throat] >> Uh I I'm not sure if I got it right. So, if you have the canopy oracle, right? It's the encoding of the Merkle caps.

>> Mhm. >> So, so, so how do you you know the relation between the leaves, the actually data want to commit the vector and the Merkle caps. I mean, that's a quite highly non-linear relation you want need to prove. So, uh so what kind of >> so so that particular thing is proven in the open protocol itself. That is not a claim that you necessarily emit. And that is uh just proven just the way Merkle claims are proven by sending like the sibling hashes and uh proving that this uh root of your specific subtree is indeed the value that you get from

uh using the given value and the sibling hashes. And that is that is not out that is not part of the output claim emitted by Canopy. That is proven immediately. >> So, I can interject. Maybe I can also explain. So, >> [clears throat] >> these hashes, they're not proven via Merkle anything. They're just like sent in the clear. So, the verifier receives these hashes and checks like a normal Merkle tree. It checks these. >> Okay. >> But now it doesn't know what to do with the roots, right? So, that's where we emit claims about the the Canopy protocol.

>> Got it. Thanks. >> Yeah. >> Hi. Um what led you to think of this? Um because I obviously the motivation of reducing proof size is is obvious. Everyone's thinking about that. But what was the sequence of kind of can reconstruct what led you to think of it? >> Uh mostly desperation, I would say, but uh I I I think So, for the longest time before we got to this project, we were I guess uh yeah, trying to just decrease proof sizes in any way possible. And uh we had uh I guess some ideas on, for example, how to, for example, not even

necessarily use vector articles to compa uh so so right now we work with interactive article proofs where articles correspond to essentially things that you can do vector queries on or like position queries on. And we had like this initial idea of maybe potentially reducing proof sizes by instead of not using vector Oracles, but using set Oracles. Um and in in some ways, I think some of the ideas that we were discussing while pursuing that idea kind of led to this.

And uh Yeah, I don't exactly remember what the chain of thought was. I I suppose. >> Okay, thanks anyway. I was walking my dog and then we were on a call and I had this throwaway idea and then Anubhav went off and said, "Oh, yeah, actually this works really well." And kind of that's how it came about. >> Is there a dog on the paper >> Yeah, maybe she should be, [laughter] yeah. >> Okay, can I ask um so >> Um >> Oh. >> Let me ask more questions, Anubhav. >> Oh, yeah, okay, of course.

>> Um okay, I'm I'm thinking I'm trying to think about the the the cost profile and savings. So, first of all, I guess what is the optimal uh cap height? Is it half? I guess it it's kind of a trade-off. Um >> Yeah, it really depends on So, usually you would want to apply Okay, so say you want to compile an IOP into a SNARK. And your input Oracle, so in that case you're even your input Oracles are using some error-correcting code, right?

In that case, what distance of that input error-correcting code is kind of dictates how many queries you're going to make to this V layer, right? If you're using Reed-Solomon, then the number of queries, assuming like capacity bound or something, then it's going to be 128. If you're using a code that has extremely fast prover time, but a really bad distance like Bolt, then it would require 20,000 queries or something like that. So, the rough intuition is that the larger the number of queries that you would have to this input article, the shorter your smaller your D will be.

>> add to the question? So, I'm wondering whether um What Let's say I'm willing to add a constant overhead to my prover time. Let's say I'm willing to double it. Would it then make sense to use to expand my cap so much that the encoding became as long as my original codeword? Um and then I I would affect What What would What would the resulting effect be on proof size? Would it basically have >> So, we'll get to we'll get to numbers, but you have to be a little bit careful because for example, with Reed-Solomon, you could go from rate half to rate 1/4 and that would also reduce your queries, and you would be in effect doubling your prover time. And um moving to rate 1/4

>> [clears throat] >> then there's not then Yeah, and also but Canopy also does not give you that much benefit in in that It's like as we'll see, it's better for um like low to middling distance. >> Well, so would that configuration make sense? In other words, how long does How long do you want the the new encoding to be? As long as your >> we'll discuss in the evaluation section. Maybe we can probably also jump to it like pretty soon if you're short on time, but yeah, I mean, some of the block lengths that we use for the Merkle cap layer was like, "Oh, it's equal to the input

article or it's half of the input article or it's 1/4 of the input article." Like those are the different things that we played around with. >> So, you can use a a huge huge um rate and get In other words, you have so much wiggle room to get back to your original length that the distance should be extremely high of of the >> Exactly. And your queries are nothing. >> If you make the distance really, really good, you're not going to have that much >> Like going from let's say n to the 1/4 to square root >> Yeah.

>> uh message like size or whatever, right? Or inverse distance is not going to give you that much savings. >> Well, wouldn't Wait. I >> Yeah, it it it's like kind of an empirical calculation that you have to like essentially figure out what the costs will be and how much savings you have. >> It seems like you would then be adding very few queries because your rate is so low um [clears throat] that you would >> Exactly. >> We can we can postpone. >> Sorry, one more question. You've mentioned these um claims can be proven with an IOPP or accumulated with like facts, for example.

Do Like at what point in the SNARK do you eventually prove these? And do these claims ever get batched into the claim we care about in our SNARK? >> Yes, it is. >> Uh yeah, that's a that's a great question. Uh it is something that we will answer, I guess, in a few slides. >> Okay, cool. Thanks. >> Cool. >> Have you considered applying this trick recursively to its own Merkle tree? >> Uh we have. Uh it can potentially give you asymptotic improvements, it it but for concrete improvements, it's harder to get any benefit from doing it more than once because we really benefit in the case

where the concrete number of queries is very high. And if you do this trick once, then the number of queries to your oracle is already low. So, doing it a second time doesn't get you too much. Like, I think if you do it twice, maybe you can get like an extra like 5% improvement or something, but uh the you get extremely diminishing returns. >> Makes sense. Thank you so much. I know, feel free to continue. >> All right. Okay. Um yeah, so we're discussing what this abstract generalization for uh canopy would look like and we're calling it a PCR scheme.

So, the commitment protocol involves this interaction between a committer and a receiver. And then we have this opening reduction where the committer wants to prove to the receiver that V evaluated at Q is equal to S. And then at the end of the reduction, the committer outputs a new witness W prime and receiver outputs a new instance X prime and they emit a new claim that X prime and W prime are in this new relation prime. And essentially, this is the exact shape that canopy takes. And this is I guess it's a mild abstraction. And knowledge soundness because the opening phase is itself an

interactive reduction, we can use the definition of knowledge soundness for the for interactive reductions to say that to get the appropriate security notion for VCR schemes, which is that if V accepts and the output claim is the output claim is valid, then a polynomial time extractor can extract a valid vector V such that it is equal to S at the query index Q. Okay.

So, we will very briefly discuss how VC schemes compare to VCR schemes. First of all, every VC scheme is a VCR scheme. In VC schemes, open is just a reduction to the trivial relation and in our case, it's a reduction to some arbitrary relation. And every VCR scheme can be made into a VC by just applying an argument for the output claim R prime to get an interactive argument for the opening claim.

And once you have an interactive argument for the opening claim, of course, you can apply Fiat-Shamir to get a non-interactive argument to obtain a vector commitment scheme as you all know and love. Okay. And finally, one thing that we I have been I guess alluding to all of throughout all of this talk is how do we then finally compile an arbitrary IOP using an arbitrary VCR because we don't necessarily just want to compile a given IOP like with canopy. We want this to be more useful and therefore we have a generic compiler that takes an arbitrary IOP,

arbitrary VCR, outputs an interactive reduction. So, how does the interactive BCS transform works work? Just to recap, you take an IOP, you instantiate every single commitment with a Merkle tree, the prover sends a commitment the the corresponding commitment to each oracle during the interactive phase. And once the interactive phase is done, the prover simulates the IOR verifier, the IOP verifier, and sends the verifier the query sets Q and additionally sends the appropriate proofs and their answers.

Great. Now, our compiler, again, starts over with the same IOP, but instead of applying Merkle commitments, it applies arbitrary VCRs. So, you replace every single oracle with a commitment to the oracle. And once the interactive phase of the IOP is done, then again, the prover figures out what the query sets are. And then the prover and the verifier engage in the opening reduction for each of the committed oracles. And here, let's assume that there's like only one oracle and therefore the output

fitness for that opening reduction is W prime and the output instance is X prime. And the output claim is therefore that X prime and W prime are in this output relation R prime. Okay. And we want to generalize our compiler just a little bit. We want to say that we don't want to just begin with the an IOP. We want to begin with an IOR, which is why I've been accidentally saying IOR many different times when I when meant to say that IOP initially because the actual thing that we have in a paper is an IOR to IR compiler where the the information theoretic object that you compile from is also

itself a reduction, is itself something that outputs a claim R prime prime in R prime prime. And the only change that we have to make to the compiler is that now instead of outputting one claim about R prime, which was a result of applying the opening reduction for the commitment, we now additionally have the original claim about R prime prime. And finally, once we have this interactive reduction, of course, we want to finally get an interactive argument for the original claim that we wanted to prove. And what is the missing ingredient for doing this? It is to use an interactive argument for this output relation that the interactive reduction

outputs. Great. And finally, we will get to discuss some numbers, which is that Oh, I guess before we discuss the numbers, we will first of all discuss what our SNARK compilation specifically looks like. So, first of all, if you have an IOP for this relation F, then usually you can write it as a composition of an IOR and then you compose it with an IOPP for R prime, which is the output relation for this particular IOR.

Where the IOPP just tests the articles that are exchanged during the IOR for proximity. Great. Then, how do we I guess compile this is that we take the IOR component of our overall IOP and we instantiate every single article with canopy to obtain this interactive reduction to our prime comma cross our prime. And then we take the IOPP of each article and we compile it with simple Merkle trees and we obtain an interactive argument for our prime

cross our prime. Great. So, just just to clarify, we only use canopy for the articles that are part of the IOR. So, for example, these would be the articles that the prover has to send to the verifier if you're the standard prover in R1CS relation, but these are not the articles that the prover would send to the verifier to prove a proximity claim about some other sent article. For those articles, you we would use Merkle trees. Of course, you don't have to use Merkle trees. You could again just use canopy.

It doesn't matter, but for the best empirical results, this is the setup that we ended up on. But, of course, you can mix and match. You can do whatever you want. Maybe there is a way to get better numbers that we can figure out. Anyway, so finally, we have this interactive reduction to our prime comma our prime and this interactive argument for the output claim our prime cross our prime. And to the earlier question, generally, we would prove the IOPs and so, for example, if you consider an IOP like FRI or WAR, all of these are IOPP like

FRI or WAR, all of these different things have different proximity claims that they want to prove. And now we additionally have these proximity claims that are being generated from Canopy itself. So one thing that we can do is we can batch these claims together as well. So these would be the claims that are part of the original IOP and these are also claims that are being output as a result of us using Canopy and you can also batch these claims together to get better proof sizes and save queries.

And so finally, we have some numbers for you for our first I guess not comparison. The numbers maybe yeah, for this one maybe they aren't like complete very very impressive in some ways if you're looking at Vor with rate half and rate 1/4. Canopy is some ways gives you a smooth trade-off between the two. So if you use rate 1/4 Vor, then you have a large overhead improver time. Your improver time almost doubles compared to the rate 1/2 baseline. But Canopy is like close much closer to the rate 1/2 baseline sitting at like a 1.2 overhead and its proof size kind of lands right in the middle for of like

rate half and rate 1/4. And if you look at just a verifier hashes, then it actually ends up being like almost the same as rate 1/4. So in terms of hashes, you get you get almost like a plain win compared to using rate 1/4 Vor. But as we said earlier, our biggest advantage appears when the distance of the code is bad and therefore the number of queries that you have to make to the articles is very large. Reed-Solomon codes are MDS codes. So in some ways this is the worst possible performance of Canopy and for the best possible performance of Canopy, we have to look at codes that have poor distance, but extremely fast

prover time. And for that, we look at Bolt. Uh and in particular for Bolt Max, which is their fastest prover time implementation of their code, which incurs the largest proof sizes, you can clearly see that for only like a 10% to 15% uh I guess uh slowdown in terms of prover time, you can substantially decrease the proof size. So, you can get uh for instances of size 2 to the 30, you can get down from 12 MB to only like 5 MB, and the verifier hashes go down by like a factor of like 3.5.

And uh so, for codes which have really, really, really large distances, also bad distances uh Canopy gives you in some ways the best of both worlds. It gives you their extremely fast prover time, and it also somewhat, at least, decreases their proof size. Now, of course, you would want uh proof sizes that are closer to the proof size for Reed-Solomon, but uh I guess yeah, you can you can only do so much. And uh I think with that, I will end my talk, and I will thank you all for listening.

>> [applause] >> I'll take some questions. >> Uh great talk. Really interesting. So, I I think my my humble opinion is that in modern um hash-based SNARKs, like proof size is is a really painful metric, more so than prover time. So, I I think I'd be interested in in in configurations that are more aggressive uh in throwing prover time under the bus. Let's say we double it. Uh then the the question is, what then gains can we get in proof size? Uh yeah?

>> Yeah. Okay, so, uh if I'm being honest, if you really don't care about prover time, then you really are just best off using Reed-Solomon codes with really bad rate. I >> And Merkel >> don't think that we would you would be able to find a parametrization that quite beats that. But this is really for the regime where you want fast provers, but you are suffering with the large proof sizes because of the choice of code you're using, but you don't have to now because you can apply this optimization for those codes.

>> Did you try where with rate 1/4 plus canopy? >> Uh yeah, so in in in that we yeah, don't get like a huge benefit over the rate 1/4 baseline. Partly because again, the initial distance of rate 1/4 Reed-Solomon I mean the the distance is 3/4 and therefore it's proximity parameter you can set it to be like extremely high, therefore the number of queries just to begin with is like pretty small. Even if you are I think looking at Johnson bound, um I think the number of queries that you would make to the first oracle is already like about like 150 or something.

So that's not that big, but for that I think yeah, I don't I doubt that I mean I think you can still get like a 10% improvement in proof size, but nothing too significant. >> So >> Quick question about the evaluation section. What do >> you mean when you say RS codes or bolt IOP with one oracle? >> So it's just like I don't know, like something like Spartan for example. You're just sending one oracle which is the witness. >> Oh, cool. >> So that's what it means. >> Okay. And then the follow-up is are these numbers including the sort of batching the canopy claim into the work claim?

>> Yeah. >> Yes. >> Thanks. >> This is including that optimization. >> Cool. So just to you know, help me out here. I I must be missing something. I don't see why you can't get basically a half savings half plus epsilon if you use a a cap halfway up and then basically extend the intermediate thing back to a >> The trade-off there is that now you're cap paths, they're longer. So, you want to be There's like a trade-off between going up high, but then you pay longer and like more in terms of proof size for the cap paths.

>> Wouldn't the rate be so good in the cap that you have very few queries >> That is I think a fallacy that I think I used to also fall for, which is to assume that like once your rate gets really good, the number of queries is basically zero. Uh the the kind of the one oddity about where and like these rate reduction style IOPPs is that they don't have like geometrically decreasing queries with every single round. Their queries decrease like harmonically and they've and like they have these fat tails. And therefore, even though you end up with the like a reasonably small query complexity that you're starting

with, you still have to do all the rounds and those rounds still add up. >> Uh I have a quick question. Um I'd be interested in seeing the results for uh RS codes parameterized using the UDR bounds. Um specifically in implementation, there's a trade-off where you could get away with 128-bit field usually using the uh proximity gaps up to the UDR. Um but obviously, you have more queries, but maybe there's some architectural configuration where you do the UDR for where, but then do something else for this uh cap code.

>> Wait, wait. So, why do you want to restrict to the unique decoding regime? >> Uh the basically, in order to achieve something like 120-bit soundness, uh you can't use the list decoding results, at least that are currently known with 128-bit field. And so, you need to go through some gymnastics to you know, be able to apply those results. >> Uh but I guess you can Yeah, yeah, I I I I agree. Okay, that's fair. Um Yeah, I think uh I I can try to like run those numbers. I I that's not an experiment that we >> The savings will be larger because there'll be more queries.

>> Yeah, um if that were the case, if there If there was some configuration where that's competitive, that's a pretty interesting architecture. >> Yeah. Yeah. I mean, yeah, in general, like anytime your queries are increasing in your baseline, the better Canopy is going to do. >> The relationship between rate and number of queries is is kind of worse in a sense. Like it >> I mean, yeah, if you're looking at small smaller rates imply high distances implies less queries imply bad for Canopy.

Wait, uh wait, is someone I I can't hear. >> Um so, does it make sense to use different parameters for different rounds? >> Oh, yeah, great question. Um Yeah, but Okay, so the challenge with that is um again, with with like Word, um the rate has already decreased so much and the distance has increased so much by just the second round if you're using like a folding parameter is like eight or 16, that uh the number of queries that you would be making to the second oracle in Word are already quite small, and therefore

for those oracles, you would anyway just use Merkle trees, and using Canopy is not super beneficial there. >> Yeah, so so the answer is yes, but what matters is the parameters and for the first >> I know yeah. It's the answer is yes but and it's like more like a binary rather than like a smooth trade-off as I suppose. >> I see. >> Which is what you would hope but it's not what you get I guess. >> And and is that under a global optimization of all the parameters of what is now a doubly recursive where implementation because there's so many knobs to play with now?

>> Yeah, I mean truth be told I mean I was I I could not optimize all of these variables but Codex can so you know, just kind of trusting it that it picked the best set of parameters. I don't know. >> So sometimes it's better to just do a brute force search. >> I mean that's I think I'm pretty sure that that is what it did because it did run for like several hours. >> Any further questions for Anoop? If not, let's say thank you so much to the speakers. Fantastic talk.

>> Thank you so much. [applause] Uh yeah, I I do have to head out though. Bye-bye. >> [applause]