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]