# Optimizing Eth2 by Michael Sproul (Devcon5)

- Speakers: Michael Sproul
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2020-10-09
- Duration: 11:54
- Topics: blockchain, smart contracts, distributed ledger, ethereum
- Watch: https://streameth.org/watch/yt-68s_hdM4fHY
- YouTube: https://www.youtube.com/watch?v=68s_hdM4fHY

## 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 IPFS and more.
https://archive.devcon.org/archive/watch/5/optimizing-eth2

Michael Sproul from Sigma Prime discusses Optimizing Eth2.

Speaker(s): Michael Sproul
Skill level: Advanced
Track: Consensus layer
Keywords: eth2, technical

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 5 was held in Osaka, Japan on Oct 8 - 11, 2019.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

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