Ethereum Foundation DevCon 6 - Developer Infrastructure Track, 12 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: The Right Way to Hash a Merkle Tree by Potuz | Devcon Bogotá

Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/the-right-way-to-hash-a-merkle-tree/

We shill an assembly SHA256 library that is optimized to compute the hash tree root of a Merkle tree. It consists of reusing two publicly available methods:
1. Hardcoding padding block. This method is used in Bitcoin's core client hashing algo.
2. Use CPU-vectorization to hash different branches in parallell. This is Intel's "multi-buffer" method.

Initial benchmarks show up to 1200% improvement on hashing of large lists on AVX512.

A GoAssembly version is used by prysm.

Speaker(s): Potuz
Skill level: Advanced
Track: Developer Infrastructure
Keywords: Assembly,sha256,vectorization

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers.
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

A

A

Library is something that generically just takes any message: any a narratory length message, as in a sequence of bits of any length and It just fits out out of that 32 bytes. The digest of this thing is 256 bits the procedure to go through those consists of three parts, so I'll just go over the three parts. The first part is breaking your message into multiples of 64 bytes, so those are the chunks 512 bits.

A

The second part consists on scheduling words, Computing a bunch of double Words, which are four bytes each and the third part consists on performing a bunch of rounds which is just the function that actually does the hashing itself the function. That is not invertible. Here's just a brief description of this. This slide I just stole from somewhere in the internet, but I want to go in some detail in each one of the three parts. So, let's start with the easiest one, which is scheduling words, so scheduling words, as you see here, you're, given a message.

A

Let's suppose that we've already broken the message in pieces, each one of them is 64 bytes. So the first thing you do is you compute, 48, double words, four bytes, each the first you need 64 in total. The first 16 are your your message. Are the 64 bytes that you're giving these are 16 words with those 16 words?

A

You can compute the next 16 words and with those 16 words that you just compare to come to the next ones and the next one, and you compare the 64 that you needed, and the important thing that you need to remember from this slide is that to compute those scheduled words. The only thing that you need is the previous words, nothing else. That means that, when you're scheduling, words well I think the consensus people are starting to come in anyways I've already started guys.

A

uh So when you're scheduling words, the important thing is that you don't need to know the previous state of the Hashi. You only need to know what were the previous scheduled words in particular, it only depends on the chunk that you're hashing now and it doesn't depend on the other chunks that you're going to hatch. So if your message consists of 10 000 chunks, you can compute the scheduled words for the ten times and challenge without caring about how you attach each one of them and without caring about the rounds.

A

Part so scheduling words only requires the previously scheduled words, so the diagram there is taken out of an Angel paper describing what were two new instructions that do this scheduling of four words at a time with only two instructions. This can be done now on Modern CPUs, and this is just a sketch that how diagram diagrammatically you compute four words at a time, but it's irrelevant the method that you use to compute those scheduled words. What I want you to remember is that to compute them.

A

You need to know the previous words and nothing else rounds. We don't care about what rounds. Is we only care that it's a function? That is not invertible? That is hard that is computationally hard to invert. But the important thing that we need to remember is this: we already we were given the message. We broke it into pieces of 64 bytes that I haven't told you how we computed those scheduled words that we need and then what we do is we pass an incoming Digest?

A

If it's the very first chunk that you're slash that you're hashing, we pass a constant digest that the method has. If it's the third chunk, you're gonna pass the past that the second chunk produced. The point is that you have a status which is your current hash and you pass it through this function that takes this status, the hash, the 32 bytes. It takes one of the scheduled words that you computed and it takes another constant word that the protocol has so it takes this data and it produces for you a new hash.

A

So what do you need to remember from this is that you need to have computed at least that scheduled word before passing through the rounds, and you cannot do this in parallel to pass through the round. You need to have computer already in hash before so. This is something that you cannot do in paragraph okay, so the padding block. So this is the first part of the three uh process which is breaking the message into multiples of 64 bytes. How do you do this? Well, you just break your message into multiple of 64 bytes.

A

You add one bit at the very end of the message just to Signal. This message has ended so here the message is less than 64. Bytes is 24 bits these three bytes there, a b and c this one. There is showing that we added that extra bit to show the message has finished and then you pad with zero bits up to a multiple of 64, bytes minus eight, because you're going to use the last eight bytes or 64 bits to encode the length of the whole message, as is there in binary.

A

That's the number 24, which is the actual length of this message. Okay, so this is the procedure to pad uh your message, which was arbitrary length into a multiple of 64 bytes vectorization, which is the main topic of this. Talk is vectorization, so the first thing to notice is that you're not going to beat any of the hazards out there.

A

Every implementation that I've reviewed before according to this and I'm, not an expert at role on this I I, come from a completely different subjects, but every implementation I've seen is equivalent to Intel's original paper white paper on this and it's equivalent to what opens the cell, for example, does all of them implement the following? You can compute your scheduled words as I told you without knowing what the previously hashed, uh what the previous, what the current status of the hashing is.

A

So all of them use Vector instructions to compute several words at a time if your CPU supports uh 128 bits registers like these ones and almost every CPU now does then you're gonna compute four words at a time: four double words. At a time. You start with your 16 double Words, which is your message and you can put those 16 double words in only four registers.

A

If your computer supports uh avx2 that you can do our genetic and registers that are 256 bits, then you're gonna, compute, eight you're gonna use only two registers and you're gonna compute.

A

Eight words at a time if your computer supports AVX, 512, you're, gonna compute, all of them the 16 of them at a time, 1024 does not exist yet, but it's already in the books there's two options into Computing: This Modern implementations either do this this vectorization or if your CPU implements cryptographic extensions like what's there in a picture, then they will use 128 bits registers regardless. If your computer has larger registers, because cryptographic extensions can compute forwards at a time much faster than vectorized computations.

A

But the point I want to make is that this vectorization is there in every current implementation. This is since Intel's, uh since that's white paper, also Computing. The words like this is useful because since you can compute the words and at the same time uh pass through some rounds. So let's say that you computed the fifth word. Then you can pass up to the fifth round. Then you can mix scalar operations with Vector operations and the CPU would perform this in parallel.

A

This views can take, has several ports and can take different types of operations at the same time, so you can't be Computing the fifth round. That is a computation that it has to be done on the scalar part of the CPU because it has to be, uh it cannot be in parallel and at the same time, you're Computing. The sixth word, in parallel on on Vector registers, okay, so I've covered.

A

What is what is a typical uh implementation of hashing, and this is the the thing to remember from the whole part from the whole purpose of the dot. Is that the hasher signature is this in either? Language is something like this? It's something that takes an arbitrary length, bite slice and it gives you back 32 bytes, which is the hash.

A

So it takes an arbitrary linked message and it gives you one. It gives you a digest, and this is something that you're not gonna, beat you're not going to implement this better than open SSL. No one is going to do you perhaps can do it for one CPU you're not going to write an implementation faster than what is already there.

A

However, we use hashing in a very restricted scenario. We use hashing to Hash Merkle traits a miracle. Trees are not arbitrary length. Merkel trees are in the case of the consensus layer, for example, where the nodes are 32. Bytes, there's something like this: each one of these nodes represent 32 bytes and each parent node has only two children and these two children are hashed together. So the two children are 64 bytes in concatenated, you hash them and you get the hash of the part. You get the what what goes in the part.

A

So this is what we we hash typically and we observe two things. Well, actually the execution layer has something completely different, but still the same technique is going to apply. What we observe immediately is the following thing: first of all, we're not hashing arbitrary length, we're hashing every single time, 64 bytes and second of all, we can hash this in parallel. You don't need to you. Can hash the blue one by knowing the entire left subtree and hash the yellow one completely in parallel in the other side? Of course you can do this in parallel.

A

If you have a CPU that, if you have two CPUs, you can just use two threads to Hash this, and this is exploited in the consensus layer. I don't know if any other besides Lighthouse uses this, but I want to use this I want to say to talk about a different kind of parallelization. You can parallelize this in different threads, but the point I want to make is that you can do this by using Vector instructions.

A

This is the the typical this is the one that is in the specs in the consensus layer specs. This is the implementation. I think this is vitalik's implementation. This is a flat array approach to having a miracle tree. I highlighted the line where you're Computing, the hash of the parent by hashing, the two children that are concatenated, the top one is uh different memory layout. This is Proto lambda's implementation on remarkable. The point is that it's the same kind of hashing.

A

You take the two children and you hash them and you hash two blocks at a time. This is fairly fairly inefficient. This is a goal implementation. This is also Jim's. uh This is James implementation, it's a production, a production, implementation and then again the same thing is slightly more complicated because it takes into account other things, but the highlighted line is the point is the point where you're hashing and you hash one node as the hash of the two children- and you do this on a loop for each pair of children.

A

You have once you call the hasher and you get one touch. Okay, so I want to tell you what is the right way of hash in a miracle tree and it's fairly fairly simple. So there's two things that we want to exploit. We want to exploit the fact that our hash is exactly 64 bytes. That's the thing that we want to hatch so remember. How is it that we patted our message into a multiple of 64 bytes?

A

Well, our message is already 64 bytes, but unfortunately, unfortunately we need to add one bit to tell the message: I send it. So that's the first bit there. The problem is that since we added that bit now, we need an entire block and the entire block is all made of zeros, except this little bit one here and that bit. One here is saying the message was 64 bytes so that bit there is a 512 bits that uh that the message was.

A

But the point is that this block is known. It's known before we started hashing, the whole block is known and in order to compute the scheduled words, we only need to know the message. We don't need to know the hash of the previous block. So whenever we hash 64 bytes, we can already compute the scheduled words for this entire block, and we can do this now we have them, so we can cardboard it in the in the in the hasher itself.

A

This is something that the Bitcoin Community learned and they have it in their standard node. So the the I don't know. How is it called I think it's Bitcoin core the client and it has it there and no no ethereum client used this. So I was surprised when I found this out, so we can stop. We can steal this from the Bitcoin community and indeed uh so, prism uses this Library loads that are all to implemented this, and just by implementing this, you get at least 20 gain on your hashing speed.

A

Just this no changes on your code just include this uh hardcode words. The second one is vectorization itself and vectorization. uh This is also something that is implemented already. If you have several messages that you need to Hash. At the same time, there are libraries to do this.

A

Intel has a very good library, and all I need is just change the signature of that library, but the point is that you can be hashing several buffers at the same time, if you have so, this is a way of like encoding the words again uh you're gonna take. This is the message that you want to. You want to hash, uh so these are the 16 words corresponding to this node.

A

Here the zeroth note, then you're gonna have 16 words corresponding to this one that you want to Hash 16 words for these two and 16 words. For these two and what you're going to do is collect the first double word from this one. The first double word from this one. The first one will work from this one and the first double word from this one into one register: that's if you have registers that are 128 bits.

A

If you had avx12, you would collect eight of them at the same time and again, if you're, a AVX 512, you can do 16 at a time. The point is that you can hash in one pass. You can hash up to 16 blocks on AVX 512 and you could do the same thing for the words themselves. So the the digest consists of eight double words.

A

If you have registers that are 128 bits, you can put this. You can put four of them in one register and then you use eight such registers for the eight words of the digest, and you can hash four blocks at a time. So this is again. This is a library that exists, so all I'm selling. You is something that already exists. It's not that we're rolling out our own crypto is I need to brag about something.

A

I was told as a student that, if you're given a talk, you need to brag about something that you did yourself and I guess. This is something I did, uh of course, the the assembly for Intel and AMD Intel's libraries I'm, not gonna, beat it uh unfortunately, Intel or reasonably Intel does not produce assembly for arm and there's something interesting here uh arm assembly I told you that every Library out there uses vectorization to compute the scheduled words.

A

That's not true on arm on arm open SSL had a library uh using neon instructions, Vector instructions to compute the the hashing and it turned out to be slower than than scalar. So most libraries for arm do not use scalar instructions.

A

However, if you're gonna Hash a miracle tree, you can hash several blocks at the same time and that's very very much much faster than hashing them on scale, so the pipelining for arm I think is purely mine. Let's say that you want to use this library and you want to implement it. So there are changes to your code.

A

So the changes the following since, let me go back a few slides. Perhaps ah it did had a pointer, oh I'm, just technology at first, okay, anyways, let's see this is the the so as I told you I'm gonna hash. With this kind of registers, we can hash ah now. I have a point of course, since with this kind of register, I can hash four blocks at a time. That means that I can compute this entire layer in one pass of the Russia.

A

So, instead of passing on a loop and hash this to Hash these two hashes to and so forth, what I'll do is- and this is a requirement you cannot use Proto's implementation, that has pointers everywhere and the data can be anywhere. If you want to use this library, then you need to have, at the very least this entire layer, consecutively memory and this entire layer consecutively in memory and so forth.

A

uh Vitalik's flat array would work fantastic for this. For this thing you would I would if I were to implement this I would just put everything on one array. The point is that what you're going to pass the hasher is a pointer to this or this whole slides, whatever equivalent signature for this is, and the hasher is going to give you back all of this at the same time. So this is something that you need to change the hasher signature for this. Has this form so in go. This takes an arbitrary by its life.

A

So this is the layer that you want to hash and it gives you back and a slice of hashes of 32 bites these hatches all of them at the same time, uh I think I might have gotten this correctly in Rust after several iterations. uh This would be in Python.

A

uh We have a library, uh we have two libraries, we have one in go assembly and we have one in user assembly with C bindings. If you are going to use that, let me know because crypto extensions on arm is still not implemented. It's going to take like 10 minutes to add this, but this is the signature that the library is going to use if you're using a c bindings all right. So that's all I want to tell you and that's that's it.

B

Okay, sure I'll, just repeat that, for the sake of the recording I was just asking if um uh the the ability to process multiple different hashes in parallel was already implemented in libraries. That was the question to the answer.

B

um So so that so there's two things that you have here right, one is to like pre-compute the padding block and then the second is the ability to to, in parallel process, multiple different hash values and then produce multiple different hash values right, correct, and so there are already implementations that do multiple different hash values at once, and you just modified them to deal with the padding block. Is that right? Yes,.

A

And yes, so so there are two modifications here: one is uh the thing that you're going to use the padding block. uh The padding block has this constants hardcoded and then there's other modification, which is the fact that you're expected to get a list of 64 bytes chunks, and then you pipeline this. So what this Library does. Is it grabs all of the blocks consecutively memory? It gets a matrix on the vector on the vector registers. It transposes this Matrix and now you have on all of your registers, the different, the different messages.

A

So then, you can use Intel's Machinery to Hash those messages. In parallel, you print the you output, these hashes and then you just Loop it back.

B

So that's cool, so you you have so the result is basically like. So it's inco assembly what you have right. Sorry, your your implementation is in go assembly, I.

A

Yeah, so the original implementation was just purely assembly. This is there, it has C bindings, but it the C go. Overhead is horrible, so it ended up being slower than using the go implementation, the standard library and go. So we needed to write a Google assembly library to use ourselves yeah.

B

Okay, cool well done very good, very impressive thanks.

C

uh So I was curious. You've shown that there are always optimizations you have to do to get around the general purpose. Nature of these General perfect hash functions. Do you think it would be possible to design a hash function that was like a special hash function only for like oh.

A

Oh, that's a good question: I'm, not sure if you can do better than the current implementations like uh you can take the sponge type implementations, shot, 3 and Company, and you can try to adapt this for this I. Don't know I I, think yeah. Your question is completely open. It's it's! A very good question. I think we should think about this.

A

So if I understood your question, as can there be a method that is designed for Merkle trades uh instead of like a generic one and.

B

Your implementation does, it so say: there's some really big miracle trades in in the beacon state right yeah. um Is it the job of the implementation, to kind of split that Merkle tree up into smaller subtrees that fit the size of your CPU? No.

A

No, so the the so you're saying if you have this large tree, if, if it's the job of the implementation in splitting into smaller trees, no no, this this is. This is completely orthogonal to that. So what you guys are doing in Lighthouse is splitting this into smaller trees, and you send this on different threads to to compute them in parallel. This is completely different. You just pass the entire slot, so big Trace is the big gain for this you're going to be at least hashing four times faster than the standard Library.

A

You just pass the entire slice, like all of the slides that you of the bottom slice and the what what this thing is going to do is not split into subterris. What the thing is going to do is grab have as many blocks as possible. It can fit in your registers and then just go to the next chunk and the next chunk and the next chunk like this, so it doesn't split in sub trees. Okay,.

B

And so you faded all of the leaves and then it then it produces the intermediate level.

A

Next layer and then you just feed it the next layer entirely and it produces the next one: oh yeah, okay, so for the state, so you're thinking in the beacon State for the state. This is incredibly fast, but this is not how we hash the state, because we have it in cashier typically, and you just have a few, a few nodes that you're you're you're you're changing. So when you hash the dirty trees, the dirty leaves then well there's two things that happen. So sometimes you have several vendor consecutive and then you can.

A

You can be smart and pass this consecutive layer to this hash or you can just use whatever you're using now just crash two blocks at a time: you're not going to get the factorization impact, but you're going to get at least the 20 of the hard quality. The the padding block.

B

Yeah Okay cool, so I guess there's maybe like an argument for maybe it's quite useful for small trades. um You don't get a lot from caching.

A

Yeah, it's it's not really useful for small trees. You only get the 20 of the padding block yeah, it's very, very useful on large trees, and here large means more than eight blocks, so anything that has depth more than two. This is already four times faster.