Faster Merkleisation

Transcript

[applause] >> Um Uh okay, this is a joint work with uh Giacomo and Tomer. Um Uh this is a work I'm doing uh with my hat as advising at the the Pillar AI blockchain company. Um Uh I just want to say for starters that previous talk of Ron was very, very nice. This is going to be much simpler in terms of the deep math involved. And I think also as Ron said, this is kind of a uh project that I think wouldn't come to life without AI.

Okay? Uh there's a some coding here and like simply optimization and stuff like that and you get some improvement, I think. Even if we had everything, we kind of would never pursue it and this is another example of things that just come out. Um okay, so I want to talk about hash-based commitments and Merkle trees. Um so what are we looking at? Uh we have some hash function, okay? Or in the standard model, actually we choose a key for the for the the hash family. And then uh the the security requirement is kind of we run the adversary and he has to to find a collision, okay?

And in the ideal world, if this hash function is treated as a totally random function, I think every everybody here can agree the probability that the the adversary wins is this Q squared over 2 to the N, okay? So, Q is the number of queries the adversary does to this hash function or random oracle. N is the output size of the of the random oracle. Okay? Good. We have obviously practical implementations, the SHA Blake and and and so on for this.

Okay. So, we have this small building block, okay, one hash function. What we want to do is called a domain extension. We want to build a commitment scheme for some long string. Okay? So, there's a few ways to do this. Maybe the most popular ways is either Merkle Damgård and doing it in a chain, okay, or Merkle tree doing it in a tree tree-like manner. Okay? In both examples, if we want to hash n elements, we're doing n minus one hashes.

Okay? The Merkle tree also supports, obviously, local opening, okay? It's something we we use a lot. Okay. But, in both of these cases, what happens is that you can you have a security reduction. You want to show that your commitment scheme is secure, it satisfies position binding, like you cannot open any location in two different ways. And you do it by showing if an adversary can do it, then you can reduce this adversary to somebody that finds a collision in the underlying hash function.

Okay? So, this proof kind of works for a standard model collision-resistant hash, okay? And doesn't fully exploit the fact that we're treating the underlying hash function as a truly random function. So, the question is I want to ask, okay, if we assume something stronger, which we do, we assume that this hash function h looks very random, how can we make the commitment scheme more efficient? Okay? This is the question.

Okay? And the commitment scheme doesn't have to necessarily look random, okay? So, I'm starting with a very strong object, a random function, and I just want to end up with a commitment scheme that is collision-resistant. Okay. So, I'm going to show two ways of doing that, and then we're going to see how we get the better Merkle trees. And all the authors I think that I'm talking about are here in the room, which is uh uh also amazing. Well, at least one author for author from each paper.

Okay. Uh so, my first example is a paper that I like very much. This is by Iftach Haitner, who's sitting here et al. And they're saying, "Yes, one thing that I can get I can have a commitment scheme that is truly parallel." Okay? So, all the queries to the random oracle are going to be sent in one round, and I get the results. Okay? This is as opposed to a Merkle tree where we have log n rounds. Okay? Um so, to do that, they take the message m.

They use some code. This is called a list recoverable code. Okay? It is kind of Reed-Solomon that satisfies this with some parameters. Um but, let's forget about the code for now. And you encode it. Okay? So, you're going to get something slightly larger than the message. Then, you're going to break this long message to chunks. You're going to hash each one of them in parallel. And then, you just going to XOR everything together. Okay? And this I don't know, intuitively sounds very dangerous when you mean XOR like can find collisions. But, because of the code, they're actually they're able to show that this is secure.

Okay? You cannot You cannot open in two different ways. Okay. So, so this was about depth, which is actually surprising. Like, my first intuition would be that you cannot commit to something non-adaptively. Like, this is very not intuitive. Okay. Um So, the second question is, can we perform fewer hashes? Okay? So, I want to hash n elements, but I'm not willing to spend n minus one hashes.

Okay? I want to do less. Um Okay. Uh so, this is kind of a topic of research, and there is a what's called a Stamps bound, uh which tells us that whatever construction you have in mind, um if you want to hash t elements only using r hashes, okay? Then then t must satisfy uh this inequality, okay? So, we cannot like hash too many elements using a small amount.

Uh so, what you can see here, this is Merkle tree, okay? So, if I have uh three hashes, then I can compress four elements, okay? So, I can compress one and two, and then the hashes of the two, so this are three calls. Uh and Stamps bound is is this thing, so you see that we have a gap. Okay? And in this beautiful gap comes this construction T5 that I that I want to talk about. Okay. So uh T5 in this paper is actually from ITC 2021.

So, it's been around for a few years. Uh I just find it very surprising and and very nice, and Demetri is supposed to be here, so right? I think he's here. Okay. So, we have an author representative. Uh so, this is uh Demetri et al, okay? Um So, what they did is they're going to hash five elements, okay? But only using three hash codes. So, the construction you can see it's just a a simple Merkle tree of one two M1 M2 M3 M4.

But, the fifth element M5 is going to be going to be solved everywhere. Okay, so you just take the the fifth element, you solve it here, solve it here, and you solve it in the output. Okay, so this is the construction. And then what they proved, they proved that uh the probability of finding a collision is Q squared over 2 to the N. Okay, let's for now forget about the O tilde, forget about the tilde. Okay? Let's focus on the the big terms. Okay? There's also a pre-image and so on.

And this actually matches the stamps bound. Okay? So, very nice. You can kind of do slightly less hashes. Yeah. So, obviously for quantum you get a different bound. You're asking what is the bound for Right. For quantum? >> Yeah. >> Like for quantum I can find the collision just in H1, right? In uh uh in better. So, I'm not sure exactly what's the bound for quantum.

>> Right, because this is something that we've been sweeping under the rug uh just as an industry. Like we're always targeting 128 bits in the in the random oracle model, and you know, we're we're all here for one reason, which is quantum computers, and we just assume heuristically that we can get 64 bits in the quantum >> Yeah, we're not assuming it. We also giving proofs. >> You're right. There's also >> Okay, we have a many proofs in the Q room, but >> That's true, but not in Lean 4, for example. And I guess here are you are you just confident that it will just work out in the quantum random oracle model?

>> Uh so, what do you mean work Like we have trade offs for finding collisions. So you're asking if it will be the same trade offs as like in a standard Merkle tree? >> I'm asking this optimization to hash five elements with only three compression calls. Does that also apply in the quantum world? >> Yeah, it applies. Exactly what bounds we get like I'm not sure. We have to do a a quantum analysis of this. But yeah, of course that's a good question.

>> Uh, it all maybe misses from the beginning of your talk. Are you thinking now just of domain extension or also local properties and the vector commitments? Or would this be a building block within something like that? >> So um So we're going to talk about local openings also, but for now I'm I don't care about local opening. Okay, just domain extension. >> Got it. >> Okay, and in a second we'll we'll touch a a local opening. Um Okay. I also want to say that kind of you look at this construction and you say you know, why do I excel M5 here?

Maybe I don't need it. Okay, or maybe I don't need this one or or or also these functions you see that's H1, H2, H3. So I'm assuming that's three different oracles. Okay, so they're like domain separated. So like anything in this construction if you take out those are actually an attack. Okay, so you have to like have this construction. Okay. Um Good. Um Yeah, so this can remove like around 25% of the of the hashes and tomorrow we'll talk about the experiments soon.

Uh, I want to spend just a few minutes talking about the the proof. Okay, how do you prove that such a construction is is secure? Uh, so we have some notations. So once I hash this I call it A, okay, and I call this B. And then like whatever I put inside H3, I call C and D. Okay? And I'm going to solve the same thing here. So, the equation that should hold is this, A XOR B, okay, should be equal to C XOR D.

Okay? Just because I XOR the same message to both sides. Okay? And what I'm going to do for simplicity of the, you know, this talk, is going to assume that the adversary is kind of nice. So, he's going to do all his queries to H1, and then all his queries to H2, and then all his queries to H3. Okay? Just going to help me kind of present stuff. Okay. So, he does Q queries to H1. Okay? Let's assume he has Q queries for each each function. Okay? So, he does Q queries to H1, and we get Q candidates for A.

Okay? Now, every time he does a query to H2, we get a new candidate to be. And you can solve this B with all the A's that we have. Okay? And you get a different value for A XOR B. Okay? Good. Now, each time you do that, B is completely random, so A XOR B is completely random. So, even though he's going to do Q queries to H2, which means that he has Q squared potential values of A XOR B.

Okay? Since they all go to 2 to the N bins, and this is like a throwing balls and bins okay? Uh I even have a graph. Okay? So, I'm kind of the balls and bins. Um what you can show that every bin is going to have at most a K balls inside, okay? So, every possible value of N bits is going to have at most K values of X or B, where K is kind of a poly log of Q. Okay, so some small value.

Um Okay. So we have So we might have a lot of bins, but each one has a small number of X or B buckets. Okay? Good. Now essential eventually he needs to do a query to H3. What is a query to H3? It's choosing C and D. Okay, when he chooses C and D, so C X or D equals X or X or B. It's meaning that he has to choose a ball from here. So he has to find a collision by choosing two balls.

And now he can only do Q queries to H3. Okay? And every time he does it, so he gets for free all the elements inside the bucket, like he gets them for free. Okay? Um but that's not too much. It's only K. So in general you can show that his collision probability is this uh K squared times uh Q squared over 2 to the n. Okay? And K is kind of small, so it's kind of a smaller order term. Okay? Plus some negligible event that the bucket has more than K.

Okay? So this is roughly roughly uh the analysis. Uh you know, it's a hash function, it's random stuff, so this is a kind of no AG codes and and genius and stuff like that. Okay. >> I don't quick quick question. I'm more from a theoretical perspective. Is there Do you think there's hope to derandomize it like using pairwise independent hashing on top of collision resistant hashing to get these kind of properties? >> So using a pairwise or poly log >> Kind of not relying on random oracle. Do do it using collision resistant >> what? Like fewer the in every bucket?

>> Uh, showing that uh, domain extension using just a collision resistant hash function with fewer calls to the So, so not relying on the fact that it's a random oracle. Just on collision resistance. And to to get the random properties from some sort of derandomized hash. Like pairwise independent hash. >> So, it's going to still be in the uh, standard model, but maybe using slightly stronger properties than just collision resistant. >> Or or you compose the collision resistant >> Compose with uh, >> Yes. >> Uh, so I'm not sure this still will hold with only pairwise, but >> Um, so like max load will hold with poly log with log weight.

>> okay, maybe. Yeah. >> Okay. >> Yeah, sure. >> Um, may I ask also, so with this construction you have this Merkle tree style, but the is there strategy to open to >> Yeah, just a second. Let me get to the opening, okay? I'm not getting to the point that I want to. So, let me for a second then you can guys ask and I want to save time for tomorrow. So, Uh, so I'll just say that we kind of okay. So, this K squared that we pay is kind of in practice a lot and it really reduces the amount of bits of security that we have.

Justin talked about oh, not 128 and 127, okay? And this K squared can be like so for some particular numbers that I put could be like a 65,000. So, that's like a lot of bits. So, what I did is I'll get let you guess either manually or with AI did a refined analysis of this, okay? Um, it also has a uh, this lean proved, okay? Upstairs. Something is lean proved, okay? I don't know what exactly, but something is is lean proved. So, take that with a grain of salt.

Um, but it's kind of easy to see that the analysis is not like it's clear that it's not tight. It didn't work for constant. It's kind of it's not like a new theorem. It's It's a working on the Yeah. So, with the new analysis kind of the 65,000 was reduced to three. So, kind of now we have even very good constants for it. And in general, I would say that this hash function loses about five bits of security depending on the definition of bits of security, and we can open that parenthesis.

Um Okay. So, um Yeah. I'll skip this for now. Um So, what you can do with this T5, you can do a two things. You can put it inside a Merkle Damgård and kind of compose many T5s. Okay? You can put it inside a Merkle tree and have a Merkle tree of T5s. This is very nice cuz now your whole Merkle tree is much more efficient. However, to open a single location, you pay. Okay? So, now the number of hashes reduced uh okay to 0.75, but the local opening growth from log T, which in a standard Merkle tree, to to

this thing. Okay? So, we paid a lot in local opening. In some applications, actually, this is fine, but let's say for SNARKs, like we don't want to pay this. Okay? So, how do I get the best of both worlds? I want less hashes, and I'm not willing to pay like one bit for local opening. Okay? So, So, this is the question. Can we get the the best of both worlds? And the answer is yes. So, if you look at typical Merkle trees, especially for SNARKs, what we have is a Merkle tree where each leaf is some big blob of data.

Okay? Like you have some folding factor in five still wearing in in another protocols. So, you're hashing a lot in the leaf. Okay? And actually, 95% of the time of of the hashes is wasted on the leaves cuz this is the big chunk of data. Okay? And the rest after you hash the leaf, this is like an negligible fall compared to hashing the leaves. Good. Now, why is this important? Because the leaf, you're opening it completely, right? You're giving out when you open a query in IOP, you give the entire values in the in the leaf.

Um so, what we can do, we can uh Sorry. So, what we can do, we can use the T5 construction only on the leaves, and when we go to the Merkle tree, we just use a standard Merkle tree. Okay? So, for the leaves, we just need a commitment. We don't need the local opening, and we combine it with a Merkle tree to get the local opening. Uh this way, the opening size is just exactly the same, and the number of hashes actually uh is reduced.

Um Okay, so we just have a few minutes. I'm going to give Tomer uh time to to present some experiments. I'll just say that one last thing, we also do what's called a a T8 construction, not T5. So, we're using Blake 3 as a hash function that compresses 3n bits to n bits. Okay? And this is where you use the the chain also, not only the blocks. You have to assume for this that Blake 3 behaves randomly when you use it like this, okay, with all the inputs.

Uh and this allows us to get even additional gains. Uh so, this is going to be now the the T8 construction. Okay? So, now you see we have Z1 2 3 4 5 6 and 7 and 8. Um Okay. Uh so, this is Yeah, we hash it in the leaves, and I think we're a bit out of time so I'll let you uh >> I don't know what I'm doing. Okay. So, there's some other variants, but uh just tomorrow will anyway present the benchmarks for all of them.

Yes yes. Thanks. >> So, yeah, after the talk of Elon, uh um we're going to talk a bit more about about the benchmarks. The thing is that we have this Plonky3 framework that's is a way for us to benchmark quite quickly because we have a lot of hash functions already available. So, what we can do first is that we can predict a bit like from the math what we can expect in terms of gain, and then we will see how this behaves uh in the reality.

So, as mentioned by Elon before, so we have this classical way of doing things, so without any T optimization. So, if you go to an a record of 256 bytes, you go into four calls. So, as you can see, you have Z1, Z2 going into the first, Z3, Z4 going into the second, and all of this, so that is a classical way of doing things. But, as just mentioned by as at the end of the previous talk, we have this T8 way of doing things, so where you just reduce to three calls. So, thanks to this, you have like one call there, a second there, and you have a third there with a bunch of calls there and there that are completely mandatory for for security,

as mentioned. Um and so, we can expect some gains. So, if you hash one record, so you do three calls instead of four, so you can expect from the math 1.33 speedup. When you want to commit to a tree, since you just touch the leaves and not the rest of the tree at all, you can expect a 1. 25 speed up. And for the verification of one opening, this is a much more reduced speed up because the leaf just play a small part of the overall job of the verifier because the past takes the rest of the job.

We have different hash functions available in Plonky3 for us to benchmark. So, we have Blake, both Blake3 and Blake2, and we have also SHA-256 and some other stuff. Um we have T uh 253 that is another construction, uh another optimization with less um compression core specialized for SHA-256. And so, as you can see, we can always expect less core from than from standard, and we will see what it gives in reality.

So, in the next couple of slides, you will see some graphs like this. So, just for you to be familiar with those, uh the pink point always represents the measured speed up that we have. So, this is the speed up when uh compared to the reference. And in the blue the blue line is what we predict from the math, and the uh black line is uh the the reference. So, let us see the measurements. First, as you can see on the right, let us see what it gives when we want to hash one record and only one, and we just produce the leaf. So, as you can see, we for all of the hash functions that we measured, and even like for the for the like the special trick, let us

say, we have always a better speed up than what we expected. Why is that? It is for one principal reason is that since we hash just one thing, we have a lot of vector lanes available for us to compute things in parallel. So, as you can see on the first two uh lines in the pink region, we are able to perform the two first calls, so H1 and H2 in parallel, and we don't need for them to wait for the other. And the only reason why we didn't do that for Blake is that this is simple simply not really uh yet to the PR, but I I think that we can apply the same trick, and if you go back to the slide, this uh this is why we

have like this medium speed up there for Blake, why we are like a huge speed up for Blake three. Then, let us do something a bit different that is much more close to reality. So, we hash a bunch of records, so 65,000 of them. That is much more closer to what the prover should do. And we just hash each of them, and we obtain all of the leaves. In this case, as you can see, the speed ups are less good, or like much closer to what we expected.

And this is for some reason. One of them is that the previous trick that I mentioned, where we could compute in parallel different uh lanes and different different hash calls, is not available anymore in the case where we hash like a lot of records in parallel because everything is already full, and so we cannot entirely beneficiate from this. Um and then the second reason is that for SHA-256, the last call that we can see on the on the right in blue correspond to the padding call, and this is always the same for all of the records, and so you can prepare that in in advance and just call again and again. So, in reality, the standard case of SHA is closer to four call instead of

the five calls that I I put at the beginning. And also, I will not elaborate on this too much, but for Blake three, it was kind of various tricks uh in parallel. As you can see on the left, one principal inconvenient is that the records arrive in 64-byte rows. And as you can see, so the second rows need to be splitted into two, one going into the call one and the second going into the call two. So that was a bit of of a trick from a computational perspective. And also, at the beginning, we were doing three copies of the call for the three hash calls. And it was uh so it was um overflowing like the the processors and stales. And so the

processor was continuously fetching instruction again and again, losing time. And so at the end, what we put in place is as uh a shared copy of everything called three times. Now, let us see what it gives um with a complete Merkle tree. So you have the record, then you build the leaves. From the leaves, you build your node. And from your node, you build your root. So we have benchmarked that with two different uh size of um Merkle tree, a small one with um 65,000 records and a much bigger one with 1 million. As you can see, the results with the big tree are less satisfying than the one um with the smaller tree.

There is a first reason why the benchmark are much more moderate now is that for the rest of the tree, we don't change anything. And the leaves just now represent a smaller part of the entire job. And so we gain we have some gains on the leaves, but of course like the rest of the tree still the same. And so the final gain is smaller than when you do only the leaves. And uh the reason why with a much bigger um Merkle tree, we have less speed up is that when all of the 32 cores are busy, there is just the the the hashing is not anymore the slowest part and you have a lot of back and forth in memory and this

complexifies the task leading to less good results. Now, let us see what it gives for the verifier when we want to open one record. Again, we have like a small tree and a much bigger one. And in this case, as you can see, the speed up that we observe roughly are around 10%. Um of additional improvement when compared to the reference. And this is mostly because, as I was saying at the beginning of the talk, in the case of one opening, the leaves just represent a small part of the total part of the verifier because the rest is occupied by pass by the pass that the verifier must

construct with all of the hashes. And so, as you can see, the leaves just represent like a small the small colored part. That's why we just observe like the the 10% instead of much more. So now, let us talk about the limit. We found two cases where our T8 case is smaller, at least in the case of Plonky3. The first one is when we have long records with Blake3 because in the standard case, Plonky3 already allowed us to run 16 chunk at once in parallel in the standard case, while as you can see in the T8 case, we still have to wait for some steps to finish before going to the

next due to the XOR system and all of this. So in this case, the T8 was slower. And the second case where it was slower, it was for Keccak because in the standard case, we are already capable of handling 136 byte per call. So we just need two call in total and so the three calls of T8 is is just not a win. So, in summary, this is kind of a good fit for records with a few hundred bytes for 96-byte compression functions such as Blake3, Blake2s, or SHA-256. But, this is less of a gain when we have long records with Blake3, or when we have

Keccak, or if you expect huge speedup, this is less of a good fit when all of your cores are busy on big machines, and so memory is important in this case, probably more than the hashing. So, yeah, thank you. This is the end of our talk. >> The one I I think it it wouldn't work with the pairwise composition cuz it's adaptive that I'll show you. So, that that wouldn't work.

>> Uh yeah, so uh the first uh question comes to mind. So, we have XMSS signatures, we hash the what's public keys. Right now, we're hashing as a consecutive input. >> big leaves? There's no big leaves there. >> No, depends what you call. Here, you said an example with 256 bytes. We have 32 chains to compress the public key of the what's instance. We have 32 public keys, each 16 bytes. >> Yeah.

So, that's that's a good candidate for our application. Yeah. >> The only thing that changes there is that we don't need collision resistance there, but I think this should be fine. We need target collision resistance, but I I think it should be fine. And then, it will be faster to hash it, I guess. >> Um so, if you're working in the situation where you have very large leaves, doesn't that dominate the opening cost anyway? So, you should just use T5 all the way up.

>> Yes, so the leaves dominate the running time. Yeah. >> Yeah, so I mean like you don't need to use the tree, you can just keep using T5. There's sort of there's no need to switch out of T5. You can just >> No, but then you don't want to increase the size of the local opening. So, on the >> But the local opening is not >> itself, you want to keep it a standard Merkle tree. Only inside the leaves, you're going to use T5 for the entire leaf. >> But I mean, the net opening cost is dominated by the opening cost of the leaf, and you have to open a whole leaf either way. >> If you're like in a Ligero breakdown, where you like your basically the the the openings are all of the proof side, then maybe you don't care about increasing the

>> Look, it's a trade-off, okay? It's a trade-off between run time and opening size. I I my whole life I'm trying to make that proof shorter, so for me like making it bigger or like I just cannot do it. But sure, it's a trade-off. >> So, we care a lot about Merkle trees because of SNARKs, and if I think about the BCS transform, then you need more than position binding, right? You need some form of extractability. Did you look into this for this particular Merkle tree?

>> Yeah, I didn't, but I think it satisfies extractability kind of you see all the queries, you can extract everything. But yeah the what we showed is only position binding. You need extractability, and actually multi extractability. >> Yeah, right. >> I yeah, I just in the T5 construction, uh if you allow the adversary to do their H3 queries first, is there still an intuitive explanation why it's uh secure? >> If you allow the adversary to do >> their T3 other or have three H3 >> adversary is not nice. He's not a nice adversary.

>> Just it's still like still all H3 first, then H1, H2. Is there still an intuitive explanation of why it's >> The argument is kind of the same. It's just more complicated to kind of say it. But the main idea is that like it comes actually substantially more complicated than the actual proof. But but it's the same kind of argument just hidden now. >> Um so if I understand this T5 is just sort of saying you can hash five elements only three hashes. Is

there a general way of constructing sort of given n hashes like so this gives you upper bound is there is there a general way of finding a construction that achieves close to the upper bound? >> Yeah, so there's the ABR one that I showed that kind of matches Stem's bound. I'm not sure that the what is the current state now. I think like we have a security proof for specific numbers and not like infinitely often for if if you're thinking of like large numbers. But like for all the small numbers we kind of I think both holds.

Everything. But I don't know if you're talking about a hundred stuff then Yeah, but there's a small gap. It's not like too big, right? It's not there's no like big factor here missing because of Stem's bound. >> I guess in the snark context especially for recursion, we won't have all these SIMD and memory kind of considerations. So the the theoretical count will be much more relevant in terms of the actual cost. And another interesting thing is that um if you're doing internal recursion where you're not communicating the proof to any other party, it's just staying on your computer, it's actually okay if the the internal proof is bigger. Um so you

could maybe use >> different trade-offs for every level of the recursion. >> Yeah, basically. >> right? The first level you want the fastest and you kind of don't care about the proof size. >> Right. >> Okay, well, you care, but not too much. >> Well, you don't if you don't communicate it to anyone. >> Yeah, and then in the last one you want like small and you you'll find this small. Yeah. So this gives you options for for trade-offs, exactly. So maybe for the first occasion you can use T5 all the way in the entire tree. >> Right. >> Right? And then the last one you can kind of use T5 only for the leaves. >> Right.

Okay, thank you so much for this great talk.