Soundness with Collisions?

Transcript

Okay, this is joint work. Well, it's it's still under like a development and the slides are also under development and the ideas are also under development. So, I'm going to give this talk but this is kind of also part of the workshop so feel free to kind of discuss and and shout in ideas. This is a general work with my student Michael Sabat. And okay, the title is 5 with collisions but in general I want to talk about collisions and what can we do with collisions?

And I just want to start so I already added the slide and thanks for this one sending me from the previous talk which was was very very nice. So, here is this is not my slide. This is from Okay, the talk we just saw. So, this is like a very short summary of what I'm going to show. Many people talked about IOPs and I want to want to improve them that would reduce fine. The talk we saw said okay this login Merkel path. What can you do with it?

How how can we decrease it? What left? Okay. Okay, hash size exactly. So, nobody talked about this so it's like the the last Okay, so they just came actually from sky. Okay, excellent. Okay, so it's the same so this is like this work. Okay, I I want to decrease the hash size. Okay. And so like the intro beginning we kind of saw it. I'm going to go over it extremely quickly. Okay, like hash IOPs Merkel trees. Okay, fine.

Um Okay, so we have an IOP. We all know it. I'm really going to skip these slides. Oh, that went a lot. old Uh Okay. Okay. So, we commit, we do Fiat-Shamir, we open, you know this paradigm. Okay. And yeah, so these examples are just what my I put there. Okay, it's not a complete example of IOPs.

It's just going by itself. Okay. And these are just for some parameters here. Okay, just showing that the proof is mostly contained of just hashes. Okay, you have field elements, you have hashes, but in many settings most of the proof is is hashes. This is actually not always correct. Okay, so it depends kind of your folding parameters and a lot of things. There for some lit This is like 85% of of your proof is hashes. So, this is what we want to kind of compress.

Okay. So, the idea is just use a shorter hash. That's it. That's all. I don't understand what all these fancy things. Just use a shorter hash. No, so really like up to some small optimizations, okay, this is the construction. Just use a small shorter hash. Okay, that that's it. Okay, there's some like optimization you can do, but for now let's just assume this is a construction. So, instead of 256 bits, let's use 200 bits. Okay.

Okay. I I don't know how to prove security, okay. But on the other hand, I don't have an attack. >> Okay. Um So, uh >> But this is not the last slide, right? It's not >> It's Okay, it's Damgård-Jurik signatures and VM 2008 digital signatures are second pre-image resistant hash functions. It says how to do this. >> It says what? >> It says how to make um Merkle trees that are um only dependent on second pre-image resistant hash.

In in the context of signatures I haven't looked at the details, but >> Okay. So, in the context of signatures, yeah, you can do it because the signer is honest. Okay? But here the the signer is a malicious prover, so you cannot you cannot do it. Yeah. So, for Sphinx, you can do it. Yeah. >> This is actually good for like publishing the proof to Ethereum, but for recursion, it doesn't make any difference because the number of hashes is unaltered. So, I think that yeah, we should take this into account not for the

base proof, but rather when we recurse for the final, it makes sense. >> So, look, this is the first general idea could be applied in many places, okay? But yeah, it makes sense to do this for the final proof. Alternatively, uh you can actually do other stuff. Like once you have 200 bits, then you can maybe uh take three elements in the Merkle tree, and then actually you have, let's say, it's slightly less than 200, you can compress like three, and then you actually have less hashes. And so, you have a lot of trade-offs here, and so, you can use some trade-offs for the first level of recursion and some for the last.

>> No. >> Uh following up on what you just said, so you said that with 200, you don't know an attack. For 128, do you have an attack? >> Uh yeah, so the the best you can hope for is 128, right? Below 128, [clears throat] I have an attack. >> Right. Yeah, me too. But um with 128, you don't. >> With 128, uh uh uh >> You don't be chicken. You don't want to >> So, I I think the parameters there become so bad that you have an attack. So, it's like a trade-off, right? You make this smaller, you're going to pay somewhere. Okay? And you kind of paying the round around there.

And uh and hopefully what you pay is kind of additive, so it's as long as it's as the MCA level, you kind of don't pay anything. Maybe one bit if they're the same. But if you make the hash bigger then this becomes smaller, this becomes bigger, and then you start paying. >> Yeah, I mean >> depends on the field size and other things. >> Really, uh read the paper that I referenced because it's not just a digital signature scheme. It's a Merkle tree. >> Okay, is it a Merkle tree with uh like shorter openings than that, you know?

Uh I'm a bit skeptical, but if that's true then this applies everywhere, right? >> But But the delta is the honest case versus the malicious case, right? >> Yeah, it did it needs some serious analysis. >> Right. Okay. So, I'll continue and just say that we're actually uh now trying to push like a auto research project for vector commitments.

So, anybody can put their own like modification of a vector scheme and then we'll get the best one. Okay. Good. So, what happens when you let's say use a 200 bits or something like that, we'll see the numbers, is that suddenly the adversary you cannot prove that he cannot find a collision, okay? Like he has a good probability of finding a collision. And actually he has a good probability of finding many collisions, not just one, okay? Or not just a few. He can actually find a fair amount of them uh depending on the run time, of course.

Uh but a three-way collision becomes now hard task, okay? A three-way collision goes back to 128 bits of security. Collision, I'm kind of thinking here that I just give him for free. Okay, kind of just any collision that he wants he can find. Okay, it doesn't have to be a random collision. It's an arbitrary collision like uh not using any properties of that. Mhm? >> That would be the key. >> right? So not that >> Two? >> So you you can give him like a something give some >> So I'm not giving him a an over killer or something. I'm doing the analysis. I really analysis is the random oracle model. Okay, but I'm just saying think of of that that when you have a random oracle with 200 bits and you run in time

more than two to the 100, okay, you can actually find a fair amount of collisions. So like you're limited by you know a few collisions. Yeah. >> You can generate as many random collisions as you like essentially. But you can't like invert stuff like that. >> invert. You cannot even find arbitrary collisions. You have to numerate something. So something would be slightly random, but the other thing like the other half would not be. So he can actually kind of program the the collisions a bit. So like one idea that I had at the beginning is like okay, let us assume he can find random collisions and then you know, it doesn't help a lot, but actually he can find the like specific collisions.

>> By three-way collisions you mean three things that hash to the same >> Three-way collision means three distinct elements X1, X2, X3 all hash to the same value. >> Is is this true of real hash functions? I remember there was a paper about like finding many-way collisions not being that much harder than finding a single collision for some types of hash functions. >> The devil is in Yeah, the devil is in the detail. I think for three-way collisions it's it's um what it says on the slide is correct. >> Uh no, so let's see the analysis of the three-way collision and you know, I'm doing the analysis in the random oracle model and I don't think we have any evidence that like

Blake or SHA doesn't satisfy what we think. Um So Okay. Why do we have the birthday bound? Because the probability of finding a collision Okay, [snorts] here T is the number of queries not Q. I hope you kind of can get used to that. Okay, so it's like T squared over two to the two times two to the lambda. Okay? Here lambda is the output size of the hash. Okay? Not the security that I get, okay? It's the output size of the hash. Uh, and so, you solve this and you you get lambda to be two times kappa. Kappa is the security that I want. Kappa is 128, okay?

So, this is why we we choose 256, okay? Because of this equation, this is easy easy to prove this inequality in the random oracle. Okay. What about a a three-way collision? Then, you in the random oracle, it's very easy, kind of union bounding over the tuples, and you can show that you get this expression. This expression is I think tight, like very tight up to the constant. Um, and then you get that lambda only needs to be bigger than three halves times kappa, okay? Not two times kappa.

Okay? So, this is where we get the improvement. Okay? And I'm going to show this calculation for every K, but, you know, let let's think of just one step, okay? Just collision, three collision, that's kind of don't don't uh go too too far. Okay. So, once the adversary the collision, what do to the Merkle tree, okay? So, it it looks kind of devastating. It don't not working.

Okay. Can you hear me? Okay. So, it looks kind of devastating in terms of the Merkle tree, but actually you can show that it's not too devastating. So, he can find a collision, what happens he can find a collision, let's say, in the root, okay? And he can have find a collision here in this layer and in all the layers, okay? And in the leaves. And what happens is he's not to committed to a string, actually the number of strings that he can open is like exponential in N. Okay? So, it's a huge number of strings, so he's like barely committed to the string.

The property that you can show is that if you look at a single location in the string, like you look at a single leaf. For that, he still has many options cuz he can kind of choose which collision on the leaf and choose like along the path. Okay? So, he has exponential in the depth of the tree many options to open a single leaf. Okay? So, he commits to a string of S of length N. And then every index of this string or yeah, every symbol, he has N elements two to the depth is going to be exactly the number of leaves. So, he has N options for every leaf.

So, for the total string, he has like exponentially many options. But for every leaf, he has like only polynomially many options. Okay? Uh so, good. Uh this is bad if your PCP is binary. >> [snorts] >> Okay? Uh but if your PCP like or IOP is over a large field, then fine. We have a large field and he's like committed to small lists uh of symbols from the field per location. Okay?

>> Can you say anything about the dependencies between the collision in the leaves? >> Dependencies >> between collision that is like product set or what are the depends definitely not I mean what are the dependencies? >> So, if if [snorts] I understand correctly the question, so yeah, like he has many constraints. Like yeah, this he want this leaf he wants to open, so he has to use these collisions. >> But once he use them, he cannot like open a different leaf. >> Yeah. So, it's kind of hard to exploit this in the proof. >> [snorts] >> Uh I'll I'll talk if I have time at the end on how to slightly exploit this.

Okay? Maybe I you know what I'll say now shortly that yeah, if if you only look at a single leaf, then yeah, he optimizes things to a single leaf. But usually kind of he wants to open this leaf this way and another leaf another way. And that becomes hard. Okay? What I can say is that yeah, a single leaf he can open in N N different ways. Okay? He cannot open all of them in N different ways. Uh so, what we care in the analysis is actually kind of the average. Okay? So if you if he has L options in general, okay? So it's it's depends on the collision everything. I don't care about the So let's say LI is the number of options he has to for leaf I. I don't care about the max of LI.

I care about the sum of squares of LI actually in the analysis. And this kind of gives you a lot of optimizations. But that is for later. Uh okay. >> [snorts] >> Uh, good. So you see I will Justin is very optimistic. I use the word potential gains, okay? This is like what we can potentially gain from this, okay? I'm not claiming we we we we gain it. But if you go from 256 to 192 bits, okay? This is exactly the same sort of going from a a collision to a three-way collision.

Uh, then you save 25% if it's 25% from 90% of the pool. You get like 22% and uh and you can get this gain, okay? Um, but we didn't get it yet. We we don't have analysis, okay? We just We have now a weaker commitment. It's not a vector commitment scheme. It's some weakly binding scheme that kind of slightly binds you, not totally. Okay. Uh, and for general K, then this is the the formula, okay?

Uh, and then you can see as K goes bigger, all right? The lambda is approaching kappa, okay? So if K is a hundred, then you're like close to the 128 one that you wanted. Okay? But if K is a hundred, then you can find a hundred collision. And then if you do it, then then the number of openings is not two to the depth, but it's K to the depth, okay? So you kind of pay pay a you pay a price. Okay? But then your savings can go up, but again there's a diminishing return. Okay? So kind of you can go up, but uh uh, but it should reach 50% right, then.

Okay. Uh, okay, good. Worst case, I I kind of talked about this. I'm going to skip it for now. This is like L is the number of options you can you can do. The worst case is two to the D. But kind of we care about the average case, not the worst case. And there are like other optimizations to to make L smaller. You know what? Maybe I'll say one. In related to what you said talk. So, what they kind of kept the tree in the middle or somewhere in the middle, okay? And then the depth of the tree is actually much smaller.

Right? So, if I use that in their construction, then this L is actually very is going to be much smaller. Okay. Well, you have two trees. So, it depends if I do it in in both. But at least if I do it in the first three, then then this is a yeah. Um okay. Uh good. Um, so uh Uh, okay. So, you you need to prove that a Merkle tree is a kind of a is correct.

So, we have this lemma, a general for Merkle tree that oh, if you committed to something, then I have an extractor that can extract the thing that you committed to. Okay, just looks at your queries and extracts this, okay? Uh, so now you have to write kind of a new version of this of this extractor because you have collisions. So, when you look at the trace, kind of the trace there's no nice tree, but you have collisions, okay? But you can still go over the collisions and you can extract every possible symbol for a leaf, okay? And then you call it like a list extractor because he extracts lists, okay? For every candidate location and not like a single symbol.

And you do the same bound and kind of this is what you pay. You can forget about this formula. This this part is is fine okay? You can extract. Um, okay. Good. So, we have this weak commitment, but uh you know, the paradigm doesn't work anymore. We cannot say that if my IOP is sound and I use a weak commitment scheme, then the compiled SNARK is sound. Okay? So, we need a stronger soundness notion that you know, suffices exactly for for this case.

And uh we call it ambivalent soundness. Okay? Why? Because the prover is is ambivalent by what he's sending. Okay? Like he's not committed to stuff. There's ambivalence in every location. Okay? But small ambivalence, like not too big. Okay. So, now we're going to have Okay, so I have F1 up to FL here. These are not different functions or rounds of the IOP. This is a single message. The prover sends a message. Now, a message itself is a ambivalent message.

Okay? Which means a message itself is like a matrix, a table. Okay? So, it's like L functions that he sends or L messages. And the point is that whenever the verifier wants to read a location, the prover can adaptively, okay? Like after seeing what the verifier wants to read, he can he can say, "Okay, you wanted to read uh this Okay, I'm not going to use this. You wanted to to read this location, I'm going to use this three. You wanted to read this location, I'm going to use F1.

Okay? Because when he opens, he has many possibili- ways to open. Okay? So, it's not like he has to choose which FI he's using. Okay? He can every query he can choose it, and he does it adaptively. Okay? Like after seeing the verifier queries, he he he >> Yeah. You're not thinking like like if that was the same, can you not think of that he's sort of committed to a product set? Like a set for every location and kind of has to answer. >> No, no, sorry. Repeat the question. >> So, isn't he sort of committed to a product set? So, instead >> Yeah, he's committed to a product set.

Yeah. Combinatorial rectangle. >> Yeah. >> Yeah. Okay? >> And so that's why list recovery codes you kind of need to buzz in your in your head. I just say looking forward. I I think that list recovery codes are a very good answer. I think that you can do with like a weaker property than list recovery code, but I think list recovery will will kind of solve it. >> It's more of a product set than a a list of words, right? Because this list of word is exponential. >> No, this is L.

This is L. This is the number of opening the apps per leaf. >> Mhm. >> So this is like N. This is fine. This is like 2 to the 20. >> But you can create exponentially many then. >> You can create many openings. >> Yes. >> Yeah. But the the ambivalent message is just L times N. >> Okay. >> Okay, or N squared in general. And N times N. >> Okay. >> Um uh good. So now when we have ambivalent messages, we can divide define what is ambivalent soundness. And I already say you have to define ambivalent soundness, ambivalent under unsoundness, ambivalent state installation soundness. You kind of need the ambivalent version of everything.

Okay. Uh but it's it's the same definition just with ambivalent messages. So ambivalent soundness means that I have this execution against the prover. The prover can send ambivalent message, the verifier sends randomness, the prover sends ambivalent like oracles, okay? Uh and so on. And at the end the verifier says, "Oh, I want to read this location." And the prover can adaptively say how to open. Uh I'll say a small thing. Uh there is an important optimization here that I call blocks. So uh think of a fry or something like that where you always read you know X and minus X together, okay? So usually you'll put these two in a single leaf in the Merkle tree.

Okay? So this means that the prover kind of Okay, he can commit to many options in the Merkle tree. So he can commit to many options of X minus X. but he cannot he doesn't commit to many options of x and many options of minus x. He cannot like cause he has to he opens a pair together. They're like one symbol. It's like a new alphabet of one symbol. Okay? So So the ambivalency should be defined with respect to some like partition of of uh uh of the symbols. Good. So now we want a new template instead of IOP Merkle tree SNARK, we want the ambivalent IOP plus Merkle tree with

you know smaller hashes. Okay? Uh and and and getting a SNARK. Okay? I see like puzzled faces uh for some reason. Okay. Uh I will say that this is not the first kind of paper going through these directions. I won't go through the history, but I'll say like all the history talking about these collisions are very nice, but like you cannot use them for practical gains in in our setting. Okay? There's a lot of differences, but just you know they don't apply.

Um Okay. So uh I'm going to move to prove prove ambivalent soundness of phi. I'll just say before I go into this uh like talking about the later part, it seems that if I I'm done with this then we're kind of done. And it actually turns out that this is not the case. There's like a big issue that you need to solve. This thing we did solve, but it's it's a it's a big issue. We'll get to it. Uh but the main part now I'll talk about just let's prove ambivalency soundness of phi.

Okay? Um Uh okay. So I'm not going to kind of I'm going to do a very high level of this. I'm not going to like do the analysis of phi. It kind of takes some time. Um So just uh uh, overview. Um Okay. So before I start, I want to just show you why it's slightly hard to prove ambivalent soundness. Okay? Um, and uh, and just a second, when I say ambivalent soundness of phi, okay? Let's just fix a a model.

The function in the sky that I want to prove low degree test, that function is committed. Okay? That it's not ambivalent function. Only the prover message is doing the protocol there ambivalent. Okay? Cuz that's function it's ambivalent whatever I'm proving like, it's it's not it cannot even define like what I'm proving. Okay? But maybe you can, but uh, Okay so in general, we have kind of a a toy folding protocol where we have some function of zero that we want to test, and like all the protocols somehow reduce it to some function of one that has smaller degree or smaller number of variables or something like that, okay?

And they continue doing it, and eventually you get to something that's trivial, you just check by yourself. And what does the verifier need to do? It just needs to check that, oh yes, F1 is somehow related to F0, right? Like there's some consistency check that you need to do, and if the consistency is fine, then we rely on the low degree test of the last one, which is kind of trivial. Okay? Good. So, this is like how many protocols work. If I still aware and and in others. Okay.

Um, >> [snorts] >> Okay. Now, we have some ambivalence, okay? So, like we have two things in the second uh, okay? Let's let's even say L equals two, okay? Just has two options. Okay? And so, he's like not fully committed here. Okay? And uh, what he can do, he can say, "Okay, you know what? This G1 is going to be the honest folding of F0." Okay? And the second function I'm going to commit to is some P1, which is a a real polynomial.

Okay? But F0 is like very far from from low degree. And P1 is just an arbitrary I don't care polynomial. Okay? And then he's kind of continuous with the P1. Okay? Um and my point is is that if your protocol works in a way that, you know, I'm very high level, you have some verifier that kind of, you know, tosses randomness and checks that every two consecutive rounds are consistent. Okay? Then he'll check that these are consistent. And yeah, F0 and G1 are like perfectly consistent. Okay? Fine. Now he he'll throw fresh randomness and check that these two are consistent. Yeah, P1

and F2 are consistent. Okay? And so on. And the adversary is going to win with probability one. Okay? This is like, okay, like there are very natural protocols where if you allow me slight ambivalence, then it completely breaks. Okay? It's not that every sound protocol is also ambivalent sound. Okay? So, [snorts] how am I going to fit like where where does the hope come from to to to get ambivalent soundness? Uh and this is why you could ask why am I talking about Fry, right? I'm kind of the author of Stær and Weir. I'm not you know, promoting my own protocols. I know I'm promoting Fry in this in this

talk. So, what is the difference between Fry and Stær and Weir, somebody? Trivia? Okay. Fry has correlated queries. Okay? So, Fry does this consistency check without sampling fresh randomness per per layer per round. He kind of samples one query. Okay, wait. He does a repetition of this. But it's like one query and he checks them in all the in the like correlated locations. Okay? So, this kind of means that if I do a check here on some locations in G1 and then the check here, I read different locations from P1, then the the verifier is not going to see that

there's any inconsistency. But, if you use the same randomness, okay, and you check them at the same location, then the prover okay, PLF here has to decide am I opening G1 or P1, and then he's good, okay? At least hopefully he's he's good. >> So, where is not in the sound of FRI is >> So, I'm saying that Weir and Steer both have independent randomness, and so kind of proving equivalence soundness for them might be challenging, okay? Or maybe there's an attack, or maybe you you slightly modify the protocol so it satisfies equivalence soundness.

But, FRI, at least the version of FRI that we're using, has correlated queries, and this is actually powerful for for equivalence soundness. Yeah. Okay. Uh I still think you can kind of do a lot of stuff with Steer and Weir and and still get the the same gains, but uh Yeah. Okay. Um Okay. So, yeah, we talked about this. I'm I'm going to I'm going to >> Uh by the way, Misra has explained to me why I was wrong about SPM Merkle trees.

Um it Yeah, you can't use them in the honest case. Um I thought it could maybe be combined with grinding, but it can't. >> Okay. Thanks. Um Okay. So, FRI uses this framework, right? It kind of starts with some function F0 on some bigger domain L0, and then it kind of folds to F1 over L1, and and and so on. Um And okay, so this is uh used to be a theorem, but uh uh okay, it wasn't correct, so now it's a an idea.

Uh so so this is a conjecture that I think uh we're going to see that FRI is going to have round by round soundness epsilon where exactly so the ambivalent round by round soundness so the ambivalent round the soundness the round by round soundness of Fry is just the epsilon MCA, okay? It's the MCA error of the protocol and the last the last epsilon is just 1 minus delta, okay? This is just the the distance that we have. Um and uh kind of hopefully I'm going to try to convince you that there's a generalization of MCA, okay? Which I call list MCA, which you can imagine it's kind of similar to MCA only for

ambivalent message instead of like a concrete functions. Uh and once you have a bound on that kind of this would follow, okay? Like the the round by round soundness of Fry should follow. I don't have a bound on this, okay? But I kind of think that the same techniques or assuming list recoverability should give you a bound on this. Okay? Um so so this is like the the conjecture let's say theorem, okay? Conjecture theorem and conjecture definition also.

Uh I'll try to be slightly more concrete with what this definition should be. Um so we're going to rely uh uh Are all authors here? I think all the authors. Okay. So Albert, Nico, and Ben-Sasson they had this very nice paper where they give us fresh, simple, clean analysis of the round by round soundness analysis of Fry using MCA. It won the best paper award in TCC so a round of applause for them.

And uh if >> came from last year's Cambridge workshop. >> And yes, right. And it really what kind of so I had these ideas back then but kind of I never were able to kind of understand Fry and now that I have this, I can understand phi, and uh and and we can kind of improve on it. Um so, [clears throat] this is from from the paper of the MW paper. Essentially, they show that the MCA implies this definition. This is kind of almost equivalent to MCA, okay? So, so this is kind of what we want. We're saying there is a function f, and we need to define the bad event, what can bad happen, and

say that this bad event will not happen with high probability. This is the MCA error. Um and we're saying there's a function f, and what is the bad event? That there is some uh large set, okay? Set that's larger than 1 - delta times the the size of the domain L, okay? And [clears throat] what is the bad event? It's kind of that when you do folding, MCA didn't happen, okay? So um you folded the function f, okay, with respect to some randomness alpha.

Okay? And uh um uh the folding, okay, on S agrees with this U prime, so agrees with the polynomial. So, you folded f, and the folding agrees uh with Reed-Solomon on uh on this domain. However, the function on S did not agree okay? So, S is the domain, S to the K is like the domain after you fold, okay? Uh so, think of K to be two, and this is like a half of the size of the of this.

And this is something we don't want to happen, right? We don't want a function that does not agree on some big set, and after you fold it, somehow it does agree okay? So, probability that there exists some uh set S is is like is exactly the MCA error. Okay, is this fine? And uh uh so, they show that you can prove that this is the probability that this happens exactly the MCA error, and once you have this, kind of phi follows, okay? This is kind of the bad event in phi. They have nice drawings in the in the paper uh to show that this suffices.

And it's it's uh like proof by drawing. Okay. So, what is the So, instead of generalization MCA, directly, okay, I'm just going to generalize this. Okay? So, what is the generalization of this? Okay. So, now I have F1 up to FL. Okay? So, I have like ambivalent function, which is like just a uh a list of L functions. And now I want to say, okay, the bad event is that there exist a big set S. Okay, but this big set S actually is just a union of small sets SI.

So, I have the big set S is this thing, okay, to be big. Okay? But, I somehow can be decomposed to to many small sets. And then I wanted, okay, what is the bad event that the folding agrees on S, right? But, now what does it mean that after I folded again S, it could be that you have different functions that agree with a with a polynomial, okay, on every location of of SI. Okay? So, this is the bad event.

However, there's no single polynomial okay that agrees with the list with the ambivalent function. Okay? So, I cannot kind of explain this with a single polynomial. Okay. So uh what is left to make everything work is just give a bound on this. Okay? Give Give a bound to the probability that that this happen. And it's not just you could think that you just union bound maybe and pay L times the MCA or but kind of it's it's more complicated than that.

Okay. So, this is like for uh I don't know, auto research and AI to prove and uh like we want this up to capacity right and not just the one and a half Johnson or something. Okay, so this is the the definition we want. And now we're going to prove this after my talk. Yeah. >> I'm confused. Isn't L like at least two to the end? I mean if there's at least two values for that >> of the tree.

>> But F like the L is the number of different functions I can open to >> no, no, not completely different functions. Okay, the L is the number of options he has per leaf. Okay, so if you have F functions, think how many if I have two functions, just think of L equals two. L equals two is enough. Like if you can prove L equals two, everything like there's not a big difference. So just think of L equals two. You have two options for every leaf. This means that you have two to the end many options for the total function, but only two options per location.

>> Okay, so here F1 to FL they're they're different functions, but but they're not all the different functions you can open to. >> I never want to enumerate all the functions you can open to. I never want to do it and because it's a lot of functions and they're very close to each other, right? Like many of them are going to be very close. >> What what is FI then if it's not a function? >> FI is a function. Like a message a function, yeah. >> Why there's only Why are you not enumerating over all of them then?

Over all all the functions you can open to. >> Just think of FI, okay? The prover in the in the first message he sends a function, right? I don't know, it's not a polynomial, I don't know. He sends a function, right? And I'm testing and I'm doing correlation. Now instead of saying one function, he sends two. He just sends two. So this is F1, F2. This is what he sends. But now when the verifier queries, he has the option to choose. Okay? That's what's going on. And now when the verifier is going to fold in the next round, okay, he can you can fold the first function, you can fold the second function, but you also think of you need to think of the combinations.

But I'm not like folding all the possible to to the end functions and >> In in the second condition, don't you want just for one J? Can If if the second condition happens for one J, can't the prover win? Because >> This is the bad event. >> Yeah. So, the bad bad event is that the second condition happens for one J or or maybe I'm confused. >> is is exactly one two three happens. >> Yes, but so if three happens, it means that all functions or all of the all F J's are far.

Um so if one of them becomes close, it's it's good for the malicious prover. So, why is there a for a for all in the second condition? >> yeah. >> What? >> No, no, okay, I understand the question. Uh let me see if I can answer, but uh uh no, no, so okay, you're defining a different event. I'm saying this is a positive. Your event has bigger probability of happening. >> Mhm. >> Okay? So, I'm saying this smaller event suffices for the analysis. >> Line number two, if I have one combination of >> Just a second. Let me let me just say.

One S I might be tiny. Right? Like a single S I might be very tiny. The union of them will be is big, but one S I might be tiny. It cannot guarantee anything about like one S I. Like it could be beyond the capacity bound and just >> Okay. >> Is it a different U prime for each J or is it the same U prime for all J? In which case, why can't you just look at the U only? Or is it different if you can get new product for each day. >> [clears throat] [clears throat]

>> Maybe I'm now confused. I'll open the right up in a second and make sure that if I have a typo here or not. Okay? Uh I'm online. But okay, let let me continue and we'll go back to to this definition >> No wait, the J's are the blocks, right? So we do need the for all J cuz we need to have it across all blocks that there is equality of the fold. For our number two. Okay.

>> Uh okay. Again, as I said, this is still a like a uh another element. Um How am I on the timing? Okay. So uh I'm not going to redo this proof, okay? Kind of slightly takes time. I'm just going to uh say okay, this is kind of the figure from the GMW paper. Okay? So these are like This is like what happens in fly. This is the first function, okay? F0. And then you fold it and this is the second function and so on.

And then it's kind of green and red where you have a consistency of folding, okay? And uh the verifier's like trying to he he he picks something randomly. He's trying to find something red, okay? Or he's trying to make sure that most of them are green. Okay? You kind of do this path. And then they show, okay, L3 must be green, okay? And because L3 is green, then kind of L2 must be green. L3 is the last one, so you just check it, you know, natively. Uh and kind of you deduce back all the way up to L0.

Um And here maybe you can like think of it like this, okay? So, this graph changes, okay? So, it's not like a simple modification just uh because now this is how this graph looks like. Okay? In this graph, I kind of did a weak commitment only for one round of the protocol, okay? So, everything is with Merkle trees except like this round. And then you have two options. And then you kind of need to talk about you know this graph, but it take too much time to kind of do this formally.

Okay. Um Okay. So, I want to like jump to assume we have this ambivalent soundness of of phi and and say why aren't we done? Okay? Like we have a Merkle tree with a small hash. Phi supports this leaks the extractability. We have ambivalent round-by-round soundness of phi, so kind of we we have what we want even for Fiat-Shamir. Uh and and now I want to claim that we're actually not not done. Uh I will say that we are done if you're fine with interactive protocol.

Okay? But if you want to do Fiat-Shamir actually, this this is not enough. Okay? Uh maybe anybody wants already to say maybe except for Amber that >> [snorts] >> But uh Okay. So, uh Okay. Yeah, so we're not done. Um So, we talked about collision and we said okay, he can do collisions, but not three-way collisions. But what about inversions?

Is anybody scared about the adversary inverting of the the random oracle? Uh you're not scared. Like what is what is the security of inverting? It's you know, if we have 200 bits, we have 200 bits of security for inverting. Okay? So, that that's not a problem. So, kind of when he does a Merkle tree, maybe he finds collisions, but he cannot like it's very dangerous to invert, right? Cuz inverting means that I already saw the Fiat Shamir random is okay and I'm inverting the tree and putting leaves. Okay, that's like okay, I can obviously, you know, put elements on the leaves that satisfy whatever it wants to see.

Okay, so this is like very dangerous like suddenly after I have a tree suddenly attaching to it. Okay, after I have a tree I cannot like do another query and attach to the tree. This is very dangerous. But it's not going to happen. What's the probability of it happening? To 2 to the minus 200, right? So so there's no problem. Okay. Good. So preimages have negligible probability, collisions we take care of. So so not a problem. Now I want to say there is a big problem. Okay.

So if I have one target that I want to invert, then sure, my probability is just T over 2 to the lambda, which is fine. Okay. But who says I have one target that I want to invert? How many targets do they have? Well, I create the targets. Okay, I create. I can create many Merkle trees. Okay. I can invest, let's say, half of my budget to create Merkle trees. Okay. Or I don't know, play with the parameters. Don't you know And then the second half of my budget I can invest to try to invert these Merkle trees.

And then what is the probability of inverting any one of the targets? Okay, so I have a pool of targets that I want to invert. We're back to T squared over 2 to the lambda. Can we afford T squared over 2 to the lambda? We cannot. Okay. So we have a problem. Okay, so not only that the adversary will be able to find collisions, he will be able to do inversions. Okay, so how can we prove security? What property can we extract from here that will allow us to We know inversions, that's it. If you do inversion, that's it. So, there is some hidden property here that we're using

that allows us to kind of prove security. Okay, and it's even written in bold. Okay. So, when he has this pool of targets and he inverts, which element does he invert? A random one. Like he cannot know in advance which one he's inverting. So, think of it before I go forward, think of it. Yeah, he sees the future mirror randomness. Okay? He sees a lot, like T over two future mirror randomnesses.

For each one, you can come up with a satisfying string, but you cannot come up with a satisfying string for all of them simultaneously. Okay? And since like he has random inversions, this is what we exploit to make the proof work. Okay? Uh so, this is the intuition. Proving this formally is actually like uh not easy, and we we show that if you have random on soundness, you actually like then it's fine. Like we're not exploiting Here, we're not exploiting like a specific properties of phi.

This is generic from random on soundness. Uh uh I have this nice figure, yeah. So, he has many trees, okay? For each tree, he kind of already queried the root to get the future mirror randomness. And now he says, "Oh, I'll prepare some leaves or some part of the tree, okay?" He doesn't have to kind of replace the entire tree. He can always also only replace small parts. And then he tries to invert, and he will succeed in inverting and actually succeed many times in inverting, exactly like he's going to succeed many times doing inversions.

Uh but it's going to be for a random tree. So, kind of he it's very hard for him to plan for this. He's like, "Oh, let's take the majority of things and prepare something for that." But you kind of can show that like if there was one string that satisfies everything then the malicious prover would choose that in advance and kind of it would contradict standard soundness that that that we know. >> Are any inversions strictly worse than collisions? If I'm a malicious prover I I prefer to put collisions in the leaves than to get random inversions >> good. What is the optimal attack?

>> Yeah. >> Right? I think that yeah, don't invest time in collision. Okay, depends on the parameters but I think this is a bigger problem than collisions. >> But collisions allow you to open more give you more options on what you can open. >> Okay, they say yeah, but you have assuming you already proved ambivalent soundness. Okay? So yeah, it depends like on the parameters of the ambivalent soundness but assume this is already secure and here you actually can get like some gains. So I would go here and obviously you can mix and match, right? I can find collisions. These I I draw them as trees but these are not actual trees. These are like trees with collisions. And then then I can reverse and add more to the

collisions. So he can actually like mix the strategies and and gain at once. Okay. So now we have to define this new soundness notion. Okay? It has many words in the title. So let me try to just explain what this soundness notion is. It's the ambivalent reverse state restoration soundness game. >> [snorts] >> Okay? So what is this? Let me just kind of define. So we have state restoration soundness. State restoration soundness is a kind of let's say similar to run around soundness but like more directly emulates what the future real prover can

do. He can you know go one round, go two rounds then he can go back, right? Because he's simulating the entire protocol in his head. So he can kind of go back to wherever he wants. He can go back just one step and then go a different direction like send a different second message, but the same first. So, he actually is he's building like a tree of transcripts, okay? Not a Merkle tree, don't confuse with the Merkle. This is like a tree of transcripts okay? And the stateful solution game just says that, okay, he cannot win after he has T steps, you know what's the probability of him winning in this game, okay? And you can show that a round-by-round soundness implies stateful solution soundness okay?

Good. Here, we have two modifications. First, it's a stateful solution game, but the messages are not messages, they're ambivalent messages. So, he plays the stateful solution game, but every time he sends a message, he's not committed to a single message, it's an ambivalent message, okay? And then he can open and and so on. And second, we're allowing him to invert, okay? And this is kind of tricky, it makes things very messy, uh because what do you mean I allow him to invert, okay? So, I allow him to invert, but he said, okay, he cannot choose where he's inverting to, he kind of it's it's he he gets something random okay?

But this is also tricky, like okay, what if he has like a one message, okay? He just started the ambivalent soundness game, he has one message and says, I want to invert. I choose random from the messages, there's one, and this is a target inversion okay? But in reality, he's not going to succeed to do it, right? So, we kind of have to to bridge this gap. And where So, when he inverts, he's going to say, okay, uh so, you can think of a lot of domain separation. So, he's going to say say which round he wants to invert, fine. He's also going to say like which block he wants to invert, because when he does a query like it's domain separated in the Merkle tree, we know exactly which subtree of the Merkle tree he's like aiming for, okay?

Fine, you can even let's say ignore about that for for now. So, now we're going to the game is going to look at all the candidates that he can invert to, but it's kind of going to normalize the probability that he even succeeds in inverting. So, when he says, I want to invert, he's not going to invert with probability one. He's going to invert with some probability that normalizes like here. So, if he has a small number of candidates, the success probability is going to be big. If he has a huge number of candidates, then yeah, he's going to be able to invert, but from a random one from the list of candidates.

Okay? Uh so, you So, this is why it's called reverse state restoration soundness, but all of this is with ambivalent messages. So, even when he inverts, he's going to invert ambivalent message that's going to be be appended to the actual message. Okay? Um Yeah. And what we do prove is that uh Uh so, the error of this of this game, you can kind of bound it. Okay? And you kind of get this error of finding a three collision.

You kind of get the error of our standard ambivalent soundness, and you have an additional error of this reverse game. Okay? And the reverse game uh kind of becomes like a complicated formula. Okay, if I write the precise notion, but under you know uh reasonable assumptions on the parameters, it's kind of this thing. So, this is going to be the size of the domain, the number of openings, log the size of the alphabet. Okay, cuz there's some union bound there.

And over two to the lambda. Okay? Uh so, this is also like a term that in general can be big, and so that lambda cannot be like too small. Um Uh so, this might be like a L squared, which is maybe not so nice, right? Uh we would want this to be smaller. Um Log lambda is uh log sigma is I guess you know a another few bits. Uh I think you can shave something here. You can kind of uh put some something here. And then as we talked, this L is not really L. It's some other expression. It's the average of the LIs, then you can make this smaller and kind of start gaining a a

bit here. Okay? But this is this can become like a the bottleneck. Okay, like your soundness. At At the end you have a you know many errors and you're looking at the worst one. Okay? Um Okay. So uh one optimization that I can do, okay? And this actually helps a lot in in practice is and this is why I said at the beginning it's not exactly just a Merkle tree.

You do the following. So I'm also going to cap, okay, the tree. I'm going to cap in the reverse direction. I'm going to cap kind of close to the root, okay? Not close to the leaves. Um so why can I cap close to the leaves, okay? Cap close to leaves, I mean I'm going to choose a layer and just send all the hashes of this layer instead of sending the root. Okay? And this is fine because if you have a Q Q queries for the IOP, then anyway you're sending Q authentication paths. So anyway the the the SNARK is going to contain a on the log Q level that has Q layers, okay?

You're going to send with high probability all of them anyway. Okay? So it kind of makes a lot of sense just sending them and that's it. Okay, like I don't lose anything by sending this in terms of proof size. Okay? Once I do that, I can think of the Merkle tree to be a 122 192 bits, okay, in all layers up to the cap layer. Once I have this cap layer, I'm telling the verifier, "Oh, continue to compute the tree, okay? But do it with 256 bits." Why? It's never written in the proof. It's just virtually what we do in our minds, okay? So I don't mind this part to to be a thousand bits, okay?

Uh that's also fine. Okay. Once I do that, what do I have? I have that the number of openings per leaf is not to to the depth of the tree, it's just to the the depth up to the cap. Okay? And so if I have 2 to the 20 leaves, okay? And I have 128 queries, so my cap is going to have like seven layers. So instead of 2 to the 20, I'm now paying only 2 to the 13. Okay? So in practice, this is like saves a lot.

Okay? Also, if your leaves are actually have a big folding parameter, then actually the number of leaves is going to go down and this also. So you win a a few bits near the root, you win a few bits near the leaves, and only the middle. Also, just the last thing, let's say it's too big, okay? Fine. Then just say that half of the layers I'm going to use 192 bits, half of the layers I'm going to use 256, and there's kind of like a lot of trade-offs you can do here. Okay? Yeah, I >> [laughter] >> uh Okay? And yeah, so you can play You can add grinding to the round by round to the like you can If you're missing three, four bits, you can add grinding to compensate on this and kind of There's a lot of trade-offs to make.

Uh and domain separation we talked about Actually, domain separation helps a lot with the analysis. Okay? Like this very tight analysis, if you have domain separation, then kind of you're in a much, much better situation. Um Okay. I think we talked about this. Yeah. So potentially, uh this will give us some gains. Um Uh yeah, okay. I guess I'm done. Thanks. >> [applause] >> Thank you, Elan, for the talk. Um you started by saying the idea was not fully

baked and some part didn't work. But from this talk, it sounds like you have a full end-to-end thing, and by the end you get 80% sort of savings. Um what did you mean by not baked and like what's what's left to cook? >> Okay, so First the right up is not done. I need to review all parts. We need to kind of massage the the proofs. So and this reverse sound is the game. Kind of we had to change it. It's so difficult. We kind of had to change it a million times and I think now we have the right sound is game in the bound but I don't want to commit yet here. This is still like in progress. Okay. The numbers that you saw on the slides are

kind of estimates. Okay, we didn't kind of run actually a script to uh Okay, once we're done we have the precise bounds and optimizations. We can kind of see what the number of these are like estimates that I put. And third, the five part. So like we don't have a proof. Okay, I thought I had a proof. It's not correct. I asked the AI to to give me a proof. He gave something. Okay. Which had a not so much bound but like exponentials. Okay, like it's not the first bound he gave me like exponential bound. Okay, no, it's not what I mean.

Yeah, okay. However, the proof seemed to me I couldn't read it but the proof seemed to me to kind of recover the MCA proofs. Okay, first it's like a open you have to open the MCA proofs and prove it. And I can barely understand the CA and MCA proofs and so kind of this was like too much. So I cannot say that I have a valid proof or anything. Okay, but at least I have some indication that this is not reasonable. I think what I didn't check yet but I think should work if you assume list recoverability of Reed-Solomon codes.

Uh then potentially this could help have bounds for for this. Again, this Huh? List recoverability. What is It's not binary, right? It's known with poly and it's not known with concrete good parameters. Okay? And remember, if you don't have here good bounds, we're talking about 20, 30% savings. Like, it's not uh Okay. Yeah, the idea is general, but like I I want to have good bounds. Unless Yeah.

>> You want to say it's impossible to say to do free way collision and then one wayness is exponentially hard, like tight hard. It suffices to use any other properties that it's random oracle. >> No, what do you mean? I I use >> Only these two properties? >> No, using the fact that he when he inverts, it it happens to a random target. >> this can be reduced to some standard properties of some oracle. >> By adding some >> It's very hard. I couldn't even like in the book that we have, we have a chapter on you know, Merkle trees and commitment schemes.

And then you kind of put this chapter aside, you have only a interface of vector commitment, and then you go to prove there, you know, Micali BCS. Okay? It's very like when I'm proving a BCS, I don't want to talk about Merkle trees. I just have a vector commitment. Okay? I want the same thing here. I want, you know, some interface of standard model assumption saying I have some weak vector commitment Okay? And then strong IOP soundness. Okay. Actually, I don't know how to really do this well because this weak commitment, how do you define it? Yeah, I can open every leaf in a small number of locations, but then there's this reverse thing that actually he can Okay, you're running the extractor right? In the proof, like when you do

these [snorts] reductions, you have an adversary in the compiled scheme, and you run the extractor to kind of reduce it to the the IOP. Okay? But after you run the the extractor, he's going to connect an edge and he's going to fool you. But you need to say, "Oh, yeah, he can do it but it's not going to help him because it's for a random location and he kind of cannot control where it goes. And so I don't have like nice interfaces to do it and you just need to say here's the random oracle. And the best interface I have is this reverse sound this game.

That it kind of doesn't talk about miracle trees. And somehow talks about inversions to random locations. But that game I need to kind of just form random oracle to this game. Uh cool. Yes, I don't like how it's modeled out currently like this. >> Does the bad event where the the conjecture in the bad event depend on the number of K way collisions or How how does three way collisions versus four way collision >> Yeah, so you have in the conjecture in the bad event You have the parameter L.

Okay, the parameter L what is it? It's the number of openings per leaf. If he can only find a three way if he cannot find a three way collision, then the number of openings is like two to the depth. But if you can find a three way collision but not a four way collision, the number of openings is three to the depth. >> So it affects the error I guess. >> So it increases L and then the error depends on L and would would increase. Yeah. >> So so if you combine this with the previous talk right then um you would be

reducing the size of the hashes below the the layer that is going into the code. um Does it still help or would you just use one or the other? >> Okay, so first I know about the previous talk only from like 2 hours ago. Okay? So uh Uh yeah. Uh but, my first intuition is yeah, the combination of the both might be beneficial. So, you're cutting the tree in the middle.

And then, the depth is just half the depth. So, this parameter L is going to be much smaller. And in the other tree, right? Like now we have two trees. The other tree, let's say I also do the same trick. Also, my L is half. Okay? And uh and that's fine. I pay twice 2 to the L over 2. That is much better than 2 to the L. Okay? So, it seems that might that might help. However, I want to remind everyone like we have this reverse thing and everything. And now we have to somehow do this with the additional constraints.

Like uh I uh I don't know. I This is like a beyond AI capabilities. >> Most of the cost comes from the uh Most of the cost comes from the first capped tree. So, you can keep the second tree also just a Merkle tree. >> Maybe that's a good first-order optimization. Forget about the second tree. Don't optimize there. And it's like easier, right? That part I'm not touching. Only touching the first part. >> And you can set the cap height to be like log log n or something. >> Yeah.

Maybe. Or maybe the other way around. And it helps more cuz then you can move the cap. Like uh Yeah. And [clears throat] now we have two caps. We have uh >> [snorts] >> Iddo, thank you so much for this really intriguing talk. >> [applause]