hi my name is Michael Sproul I work at
Sigma Prime in Australia all that
distance away on the lighthouse f2
client and today I'm gonna be talking
about optimizing aetherium - so with
aetherium - we have the benefit of
having a nice executable specification
it's written in Python and it's written
with a focus on being very clear very
readable
now with lighthouse our implementation
is in rust and we have a focus on being
fast and secure which you know we also
want to be readable but most of all we
want to be secure and performance also
helps with security because it helps us
avoid denial of service attacks so we're
the spec might prioritize readability
and use some quadratic time algorithms
in lighthouse and in most death to
clients you really want to make sure
that you're running quickly and using
linear time algorithms are pretty close
to that particularly over the set of
validators which could be you know up to
4 million validators you know in a list
so first of all one example of where the
spec is slightly inefficient in how it
phrases things is the shuffling of
validators so we use this one at a time
sort of shuffling in the spec to swap or
not shuffling and the spec says you know
for each index which index does this get
shuffled to and it does H index one at a
time and it also does this thing where
it will extract committees on demand so
if you get an attestation from the
network and you need to know well who
the validate is in this committee for
this attestation it'll compute the
shuffling and then extract the Committee
on demand and then throw it away and
recompute it when you get another
attestation for the same committee which
is not so efficient so why not just
shuffle all the validators once at the
beginning of the epoch cash that
shuffling and then read the committees
off that on demand as you need to and
that's exactly what we do and we use an
algorithm that proto lambda came up with
I think proto's probably here somewhere
and it ends up being 250 times faster
than shuffling the list one at a time so
250 times speed up is not bad and then
there's also the benefit of not redoing
the computation
each time you get an attestation so it's
250 times or better in lighthouse what
this looks like is we have three caches
of shuffled validators one for the
previous epoch the current epoch and for
the next epoch and when we hit an epoch
transition so when we move from one
epoch to the next we update these caches
by shifting them along by one and then
computing from scratch the shuffling for
the next epoch and this works perfectly
so long as you do know the seed for the
next epoch and by design in a stew we
are meant to know the seed for the next
epoch so when we're transitioning from B
to C into the current epoch we already
know the round our mix and the seed for
the next epoch and we're able to compute
that shuffling at least that's the case
with the spec today when we were
implementing V 0.8 of the spec we
noticed that our next epoch cache
actually broke and we were going oh this
is weird like maybe you know maybe the
spec isn't meant to be like this and we
went digging through some Docs and we
were going oh this is really strange you
know the random mix is updating right
till the red arrow just before the start
of the next epoch which means that the
block proposer at the start of the
current epoch here has less than once
lot of notice that they are the block
proposer so you know they're kind of
doing their epoch transition and then
they going oh crap I'm the I'm the block
proposed that I better get on this and
propose a block so we clarified this
with the spec and found out that
actually no it's not meant to be like
this and really we should be looking at
the the read a mix from to epochs back
so where the green arrow is there and
that was fixed in V 0.8 0.3 of the spec
so something surprising here is that by
implementing an optimization it actually
allowed us to discover a bug in the spec
and I think this speaks to something
more general in the etherium space which
is that by having a diversity of
implementations in different languages
and with different optimizations
phrasing the same thing in different
ways that can actually lead to clarity
of the specification and I think that's
something that's really important and
it's a good way to design so
we're let's talk a bit more about epoch
processing because there's a few more
optimizations that we do around this
maybe less important than the shuffling
one which is such a massive speed up
with the epoch processing the the spec
occasionally will iterate over lists of
added stations and validators kind of
redundantly and one example of this is
when you're calculating the reward for a
proposer based on the other stations
that they've included in their blocks it
uses time o V times a so it's kind of a
quadratic u time where V is the
validators and a is the pending out of
stations and really that validators
because that list is so large we really
don't want any sort of quadratic factor
in there with that this is the code from
the spec where you can see the nested
for-loops giving you the quadratic time
thing so there's the the loop over the
validators and then the loop over the
other stations within that so rather
than doing that quadratic time thing in
light house what we do is just a linear
pass over the over the validators and
the attestation so we do it in three
parts we first go over the validators
get some basic info like whether they're
active in the current epoch things like
that then we iterate over the other
stations to find out how people voted in
things whether they voted on the correct
Kaspar FFG targets and sources and then
we do one final pass to sum up some
balances so different types of total
balances for validators and in total
that's order V plus a time and the sum
of the total balances just as an example
these are the totals we compute so the
total balance of all the people who were
active in the current epoch all the
validators who attested in the current
epoch who were tested to the correct
target etc so on and so forth as I said
before usually when you implement an
optimization you run the risk of
breaking your your client and and you
know running afoul of what the spec says
you should be doing so what we what we
really need to do is when we implement
an optimization we need to guarantee
that it has the correct behavior and
isn't going to break out by it so
in roughly increasing order of strength
we've got you know looking at the code
looking at the spec looking at the
optimized version and just kind of
rockin that they're the same that's the
weakest guarantee you can do because
people are pretty terrible and then
moving into like unit tests the etherium
foundations test vectors which have been
super useful and then into fuzzing so
we've been doing quite a bit of fuzzing
on lighthouse both crash fuzzing to see
you know make sure functions never crash
- regardless of what inputs you give
them and differential fuzzing comparing
two different implementations and midis
doing more work along those lines in the
next couple of months and also similar
to that randomized testing property
testing similar to quick check and
because I've got a bit of a formal
verification background I've got this
itch that I haven't scratched yet for
formal verification and that you know
we'll see if I get around to scratching
that yeah I think I've got time so I'm
gonna do this section as well as well as
optimizing for performance another thing
we can optimize for when we're making an
F to client is the profit that the that
the validator will bring in for being a
validator and there's one interesting
problem here that caught my eye a few
months ago and I'm maybe a bit obsessed
with it if if you talk to anyone around
CP and that is the attestation inclusion
problem so this problem is kind of
leading on from what we were talking
about before with aggregating out of
stations is if you've got a whole bunch
of aggregation if you've got a whole
bunch of other stations from the network
and you've got more than you can fit in
a single block deciding which ones to
include in the block such that you
maximize the profit that you get from
the rewards is actually an np-hard
problem and it's an instance of this
classical computer science problem
called maximum coverage and just to show
you exactly what that looks like
so attestation inclusion says something
like we have a whole bunch of other
stations n data stations and we need to
find a subset of these of some maximum
size such that the sum of the rewards we
get for all the validators that we've
covered with those outer stations is
maximal
and the abstract version of this problem
weighted maximum coverage says we have
some set of sets and we need to find a
subset of those sets of the maximum size
so that when we Union all the sets in
that subset together the combined weight
of all those elements is maximal
the problem with np-hard problems is
that they're hard and usually solving
them exactly requires a sort of
exponential or semi exponential time
algorithm so for now we're using a
greedy algorithm that works quite simply
by just starting with an empty solution
looking at the the list of other
stations that you've got and greedily
choosing the best adder stations
repeatedly and adding them to your
solution and so the best data stations
are going to be the ones that cover new
validators that are not yet covered by
other stations included on chain or
adder stations already in your solution
and that include of those validators the
ones that include the most high balanced
validators because the reward that you
get paid is proportional to the balance
of the validator who's at a station you
include this greedy algorithm performs
quite well within a factor of one minus
one on a of optimality so it's always
going to get you at least 63 percent of
the maximum reward that you could get
and in a lot of cases it will do better
than that
there's the sort of pathological cases
that hit this lower bound a kind of
unusual but nonetheless I would like to
look into doing some exact solving using
integer linear programming at some point
in the future I think that could be fun
but it might require kind of scheduling
your block production well in advance of
when you actually need to produce the
block which could be not so good yeah so
in conclusion optimizing s 2 is a lot of
fun and all the clients should
definitely be doing it and I'm sure they
are there's a link between performance
and security so avoiding denial of
service optimization is important and if
we are all optimizing and writing things
in different ways there's a chance we
might find some more spec bugs which you
lots of fun sir thank you very much
[Applause]
you