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

foreign [Music] 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 okay cool well done very good very impressive thanks 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 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 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 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 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 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 and so you faded all of the leaves and then it then it produces the intermediate level 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 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 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 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 [Applause]