Ethena Cryptanalysis, BLAKE3 Tweak

Transcript

Hi everybody. I'm Adrian. I work at Miden and I'm going to be bringing things much down to the much more concrete world. I'm going to talk about the new hash function that we developed at Miden which we call Idos. It's based on Blake 3, so I'll be showing a bit differences and comparing it. I know that the schedule said that I would be talking about the Athena project. This is something that we helped coordinate at Honeybit at the beginning. It's a project led by Leo Perrault and with the goal of analyzing a bunch of arithmetic hash functions, the security, the balance and stuff like that. It's not yet ready, so I don't want to steal their thunder or anything, so I'll be focusing on this instead.

So yes. So, for Miden we need a native hash. This is not just a hash that we use in our proof system, but it's at the application layer and at the blockchain level overall. And we're going to be launching very soon. So, the problem is that a while ago we were using Rescue Prime optimized. This was really nice. We co-designed it because it was it had really nice arithmetization. Once we went to Plonky2, we decided to go with the hash function everybody was using, so we went with Poseidon2. Couple of weeks later some news came out and so that made us re-question

our decision. And so we started looking around. This is also why we started looking at different algebraic hash functions with the Athena project. But just like a lot of other projects, we also looked at Blake 3. Blake 3 is really nice in native hardware. It's super fast. It's got a well-studied core, etc. So, that's what we sort of sort of ended up going with. When we were evaluating this, obviously we care about performance, but we were looking at it from the very practical mindset of like we are a blockchain. We want fast client-side proofs. We Our proofs need to be smallish.

And we care about aggregation because that leads to the total transactions per second you can do. So, these are all things we kept in mind. Uh oh yeah, and the other good thing about Blake 3 is it's because it's binary, it's forward-looking. We might be able to use that if ever we change proof systems. So, one of the We started looking into this like a 2 months ago. And the problem is that like most of the blockchain was already designed. So, the language and everything. So, we really had to like shoehorn in Blake into this. So, before this we were using the VM expose a native permutation call for the sponge.

So, this takes the 12 state elements on the stack, just permutes them, and returns them. So, this allowed us to build a lot of cryptographic primitives on top of it, but um we didn't want to change that too much. We wanted to stay ABI compatible. Uh and we also didn't want the rest of our company to be mad at us because we made breaking changes this close to the end. So, instead uh so, Ido's at its core is really just a compression function. It takes an input block of eight felts. By the way, my use felts to mean a Goldilocks field element.

So, you can take eight field elements um and a chaining value. And then when you compress that, you get a chaining value. So, this is a bit different from like how a sponge works. Um but this was good enough to sort of keep all the interface was working and get us to uh allow us to upgrade. Now, if we focus on the real original Blake 3 compression, uh I'm talking specifically about the chaining mode where you just want to do essentially a linear hash or have one compression function to be able to do Merkle trees or stuff like that.

Uh you take a chaining value, you absorb a new block. You add with additional context, and then you continue like that until you take the final chaining value, and that becomes your digest. Um under the hood, you're maintaining a maintaining a 512-bit working state. You apply the Blake round function seven times. Um By the way, the seven rounds of this is from Blake 3. So, it's one of the improvements over Blake 2, which I think used 10 or 12 or something like that. Seven is better.

Um and so, you absorb the entire block, then you compress the 512-bit state into 256 bits, and that becomes your next chaining value. So, how do we do this with Goldilocks? Um this is the part where I make may make some of you cry. Um on the input level, it goes okay because we're just taking uh eight field elements, 64 bits, so that gives you the 512 message block. And you can just split each canonical field element into two 32 bits. So, this maps really neatly.

On the output, however, this is where things get a bit tricky. So, you have this output state of Sorry, I need to see the cos face. >> [laughter and gasps] >> Um you have the state of 256 uh bits, which encodes uh Goldilocks which are just raw U32 elements. But we want to treat that as Goldilocks elements. So, there's different ways we could have done that. We could have taken each pair of 32 bits, mapped them to U64, applied the modular reduction, but that's not really super nice. It has weird collisions, and that also means that now you're tied to the Goldilocks uh prime.

Instead, we just chose to ignore the problem literally, and so we mask the top bit every 64th bit. And that works really neatly, except for the fact that we lose four bits uh of the output, so our collision resistance goes down by two bits. Uh in the context of Maiden, we target real-world security, which is a bit lower. I don't remember exactly which ones, but uh this is something we're happy to accept, especially given how uh it allowed us to go with Blake 3-ish without having to um uh so with having to redesign the entire VM and API and stuff like that.

>> [gasps] >> So, this is how it basically I just a loop of when you're compress- compressing something, you you set up an initial chaining value, you pass it in along with the next message block. Uh if you're continuing if your message if you're hashing more stuff than you repeat with the same chaining value, uh even though you've masked the bits here, they are still feel element, so things match up neatly. And at the end, when you're done, you just squeeze the last chaining value as digest. Um oh yeah, another thing is this is the only like tree mode that we support, so we don't have like the nice tree hashing stuff, so it's not parallelizable, but for us it's good enough.

Um this is getting more into the weeds of like how we actually differ from Blake 3. So, we uh in the unkeyed um mode, uh you set the initial chaining value to some fixed IV, uh and then for every subsequent block, you initialize the state, you take the previous chaining value, and then you set some uh both some constants and some parameters. So, this includes like how far along the hash you have been uh you've hashed, how many bytes are in any additional flags.

Uh for us, we wanted the compression function to be stateless, so instead we include this the information like domain separation, uh any kind of uh like the length of the string, we put that in the initial chaining value. And so, this allows us to have this like nice loop where we don't need to keep track of any extra information as we're hashing. Um this uh all these fixed IV words, we have this mechanism where we try to domain separate every single thing from like the proof system to the API to the blockchain. So, these are sort of values that we derive like that.

Um I'm just going to go over very briefly of how Blake works, not because I don't think you know how it works, but also we could just to explain how essentially we've managed to encode this in the VM. So, you've got a bunch of uh you you have these columns which are 4 U32 values. You apply a bunch of additions, XORs, rotations, etc. Uh each time including part of the message. You do this over your entire uh input space or um yeah state.

Uh you apply this G function a bunch of times. You reorder the stuff. You apply it again. And so, that basically gives you one full round. So, essentially the entire thing you're doing is just like a bunch of U32 operations. >> [gasps] >> Um Now, this is relevant because this we had to arithmetize it. And this is one thing where I think we do things a bit differently in the way we arithmetize our STARK is that because we do care about small proofs and uh because they're being produced client-side etc.

Um we try to design our errors to have a more rectangular shape rather than everything on the same line. And so, what we've come up with is this design where we have essentially 108 columns uh spanning 32 rows. And each section of four rows uh applies one round function. And so, one of the ways we can do this is like we use these periodic columns which provide the schedule saying what happens in each row. Um and uh I didn't go into the details, but essentially each row does this with many optimizations.

Uh, we have so we also need a pre-process table obviously to do all these uh, byte byte byte operations. And uh, lookups obviously. Oh, and we also have like a footer row which is just um, connects to the main VM. So in terms of performance, I I know [clears throat] I've seen numbers claiming like changing that K into N. Uh, this is just running hashes in the normal Miden assembly. So this is with the all the overhead of um, of of um, uh, of the actually running the VM. So we were still able to improve throughput by twice as much by 50%.

Our proof size has got a little bit larger. They're now between 150 and 200 kilobytes. This is mainly because we increased the number of columns. Um and uh, but concretely the changes uh, going from a Poseidon 2 arithmetization to Blake to IDos uh, means that each hash consumes 13 times more witness cells. >> [laughter] >> Um, but overall so for client-side proving this actually became faster uh, and this this is actually really nice for us. However, on the aggregation times when you're doing recursive verification this can get uh, this got a bit worse. We're doing the aggregation server-side though so this is something

we can always throw more CPUs at. We can and there's going to be some stuff that we can improve on. Um, so yeah, one of the unfortunately [snorts] by going with this approach of masking bits etc. the that means that like we had to revisit a lot of [snorts] uh, like our security strategy basically. Uh, you lose two bits here and there. The other annoying thing is it's uh, you your arguments often rely on the fact that the output is a uniformly distributed field element which it's no longer is.

Um our VM has a encryption primitive built in, which uh was based on this really nice AEAD sponge abstraction, which had to be revisited. Um yeah, I mentioned the uniform field sampling. So, this happens when you're getting the queries from a STARK or when you're from the Fiat-Shamir uh transcript, stuff like that. And yeah, now your your maximum security is a bit lower. Uh all that work is reasonable. Or at least I'm not the one doing it, so it seems reasonable. Um one alternative though that I think is interesting is that we considered a version where in the very last step of the compression, you take the full 512-bit state and you treat these as these U32s as

Goldilocks elements, and you apply a randomly sampled uh 4 by 16 matrix, and this gives you a nearly uniform uh 4-bit uh 4 felt word. And so, this gives you a lot of the properties back. Um the performance impact on this was not too big. Um but we chose not to go with this uh because that means that now IDOS is again tied to the specific Goldilocks field. And one of the design goals is that we wanted this to be forward-looking.

And so, I think it's I I I I have to admit this is I'm just a messenger. Most of this work is by Al Kindy. Uh so, if you have [laughter] any comments please don't shoot me. Um but no, it's uh it's going to be it's been really good to be able to have these uh new numbers. We were surprised just like Jordi was when they changed uh their hash to Blake3 as well. Uh it was really important for us to have benchmarks all over across the stack to really make sure that this was right decision. Um and and uh yeah, like we're still doing a bunch of security analysis and stuff, but things are working out here and there and, yeah. I think I think it was it was a pretty fun challenge. Pissed a lot of people off at

the company, [laughter] but now we're here. So, thank you a lot. Let me know if you have any questions. >> [applause]