Optimising Block Building with Genetic Algorithms

Transcript

Okay, so today I'm going to be talking about how we can optimize block building using genetic algorithms. All right, so let's start off with the the basics. What even is block building? So builders are these specialized entities that construct blocks. And what this basically means is they they try to pack transactions in a way that maximizes the block value. And these blocks that they construct they then send them over to proposers who have a very simple job of just proposing that block and broadcasting it to the network.

And so we have the separation, right? The the the block building computation is done by the builders and then validators have this simple job. And so we call this proposer-builder separation. And it was added to to add more decentralization to the validator set. Importantly, block building is a competitive auction where bidders try to outbid each other and so whoever manages to bid the most um gets to get their block proposed. And so before we go any further, this concept of MEV is actually important.

I'm sure many of you have heard of it. And it's the additional value that a block proposer or builder or sequencer can extract by controlling which transactions get included in the block and how they're ordered. And there's different forms of of MEV, some that can be harmful like sandwich attacks. But then there's also beneficial forms like arbitrage and liquidations. And so during block building we aim to maximize the beneficial kind. So following on from this, what makes a block valuable?

Well, first of all, every transaction pays priority fees. So if we have a block where the transactions are paying higher in priority fees than than another block where the priority fees are lower, then that block is going to be more valuable. But we have these searchers who are separate entities that scan public and my and private mempools and scan for MEV opportunities. And they craft bundles to extract this MEV. And then they submit these bundles over to the builders and pass on some share of the MEV that they extracted over to the builder.

And so you can see in this diagram we've got a searcher that finds some transaction they want to backrun. They then form a bundle with that user transaction plus their their backrun transaction and then submit it over to the builder. And so you can think of block value as the sum of the priority fees plus this additional MEV. And block builders are going to be trying to to maximize this by selecting and ordering transactions and bundles in a certain way. All right, so this is kind of like a very high-level overview of block building.

So the first step is this intake of order flow and order flow here is just the flow of these transactions and bundles. And once a builder has this order flow, what they do is they try to individually simulate every transaction and every bundle they've received. And this is useful first of all to immediately discard certain bundles or transactions maybe they're invalid. But also we want to know for every transaction bundle how profitable it is at the top of the block how much gas it consumes. And the reason why we want this is because in the next stage in the ordering logic phase we're going to use these metrics to order the transactions.

So yeah, that's the the next stage. And then once we have a block then we can move to the final stage which which is the bidding. But we're going to be focusing more on this ordering logic side of things for this presentation. All right, so what's like the simplest form of block building? So in Flashbots open source implementation this is called the ordering builder. And so the idea is very simple. We're basically just going to try to greedily commit whichever transaction is either most profitable or most profitable but uses less gas.

And so if we take this example, let's say we receive these five transactions. What we're going to do is we want to see for every transaction how much profit does each one generate individually. And then the simplest form is just okay, let's pack the block first including the most profitable one which in this case transaction three >> [snorts] >> and then so on. However, this is ignoring one important protocol constraint which is transactions have nonces. So what are these nonces? Well, they're basically for every EOA there's a counter that increments every time a new transaction is sent.

And so the the key protocol constraint is that transactions from the same account must be executed in increasing nonce order. And this is relevant for block building because we might receive multiple transactions that try to consume the same nonce and in that case we can only include one of them. But also we need to make sure that this increasing nonce order is being satisfied and so this restricts the the number or the valid set of orderings that we have. So if we go back to the previous example we add on this dimension of nonces.

If we look at transactions coming just from account A we can see that the bottom transaction transaction five has the lowest nonce. So even though it pays a bit less than transaction three, we we have to include that one before transaction three. If we try to include transaction three first, it would revert. So yeah. So the final [snorts] block we we get is slightly different. And yeah, so the the whole idea of the ordering builder is to try to do it greedily, but still we have to maintain this nonce order. All right.

So this is a more interesting approach to block building which is which was work done by Robert Miller from Flashbots. And so the previous approach is very sequential, right? We take all of the transactions, all of the bundles and we just sort them by some metric and then commit them to the block. The parallel builder tries to do things a little bit differently. It tries to parallelize as much as possible. And so yeah, let's see how it works. So the first step is we want to form independent groups of transactions and bundles. And so what we do is we look at what transactions bundles are conflicting.

What this means is they have overlapping state accesses. So a more concrete example for for this top conflict group would be maybe we have two users that are trying to swap on the same pool. >> [clears throat] >> And so the exact ordering of these two transactions might affect their execution and so within these conflict groups is where ordering matters. So yeah, so for each conflict group what we're going to do is we're going to try different heuristics. So and what this means is different ways to order the transactions in these groups.

We're then going to run these heuristics in parallel. Keep track of for every conflict group what was the ordering that extracted the most value. And then with these best results we can we can build the final block. Okay, but you might have noticed that some of the heuristics that we're using are are pretty simple, right? Most of it [clears throat] is sorting greedily by some metric. In the case of the parallel parallel builder, we try to run permutations as well. But the key thing is that the parallel builder did show that when you try to some non-trivial ways to order transactions, so not in a greedy fashion, but maybe try some random permutations

you can actually extract more value particularly in settings where there's a lot of MEV activity. And why do we want better MEV extraction? Well, there's plenty of reasons. Here are a couple. If we have if we extract more MEV, we can bid higher to validators and so they're going to internalize some of this MEV. If you're familiar with MEV share if we find orderings where the backruns on user transactions extract more value then those users also going to get higher refunds. But just in general, if there's MEV there and we're not extracting it that means that there there are market inefficiencies that remain.

And so the question we want to answer with this presentation is can we try to find better ways to explore the search space, find better orderings? But we don't want to do what parallel builder currently does which is just try some random permutations. So for that, we introduce genetic algorithms. The [clears throat] idea with a genetic algorithm is to follow biology and is inspired by natural selection. And in this context, we're going to be applying genetic algorithms to these conflict groups. So as a reminder, conflict groups are groups of transactions and bundles which are conflicting with each other and where ordering is going to matter.

So what we do is we start off with a population of candidate sequences or possible ways to order within a conflict group. And we want to combine these possible candidates with each other in the hopes that the ones that we produce are better than the ones that we started off with. And we're going to be applying this to conflict groups where the search space is too large to to explore exhaustively. Okay, so I mentioned that we want to combine possible orderings for these conflict groups. How do we do that? The main form is with this this crossover operator.

And so if you look at this, we've got two parents. So these are this is the input to the crossover function and the output's going to be some new child. And you can see that so these are two possible ways to order these transactions and bundles which in this case conflict with each other. And the the two parents make different selections of where they want to place these bundles and transactions. And yeah, so how do we produce a child? Well, what we do is we take uh a random slice from parent A and copy it over directly to a uh to the child where we're forming.

And then for the remaining transactions, uh we take them from the other parents and try to keep the same relative order. I'll just let it play one more time. And another operator which is important is this mutation operator, >> [snorts] >> which let lets us add a little bit of diversity into the sequences. Um yeah, this one's a little bit more straightforward. Um yeah, but I was talking about nonces before um and how, you know, transactions have this inherent ordering constraints. And if we just were to apply uh crossover mutation uh without taking this into account, we could be producing invalid sequences that violate these dependencies.

And the issue with this is that if you try to simulate invalid sequences, this turns out to be quite inefficient, right? Because you're going to be um simulating transactions that revert. Um and so yeah, that's not ideal. On the other hand, if we try to actually constrain uh these operators to enforce and preserve nonce validity at all times, this also turns out to be like extremely complicated. And so that's not what we're going to do. Instead, the solution we have is for every individual. So this is like every candidate ordering that we have for this conflict group, we have two representations.

So the first one is this raw sequence which we were just looking at. That's just some permutation of these transactions and bundles. And we're actually going to let crossover and mutation operate freely uh on these raw sequences. But then we apply a post-processing step to this raw sequence. Um and this is to make it nonce valid. And these nonce valid sequences are where we're going to be using to actually simulate them to see how how um profitable they are. Um and it also lets us compare more accurately um how similar two individuals in the population are.

Which is an important part of of the genetic algorithm. Yep. So how do we go from this raw sequence that I was talking about to this nonce valid one? Um the goal is to do something a little bit like this, where we have uh the raw sequence where we might have a bunch of transactions or bundles that are trying to use up the same nonces, but for every nonce, only one uh transaction can can use it. And so that's why the nonce valid sequence uh is typically a subset of the raw sequence. And so the first step is uh we iterate over the raw sequence.

And every transaction bundle is going to try to claim certain nonces. Um but if a transaction um tries to use a um a nonce that's already been claimed, then we just discard it. So very simple. Um but this lets us have like this active set of transactions and bundles which we're going to be using. Um once we have that, we we construct a dependency DAG. And so this is going to encode what the uh nonce dependencies between the transactions that we have are. In this case, we've got nonce dependencies uh between the three top transactions and so that's why we have directed edges.

And what we want is to pick some topological sort of this DAG uh that is as similar to the raw sequence as possible. Um topological sort here means that we we pick some ordering of these nodes in the DAG where the directed edges are never broken. Um so here I'm illustrating a couple of ways that we could sort uh this DAG. But the way that we end up sorting it is uh is in this case this one here. All right. So just a quick recap cuz that was a lot of information.

So >> [clears throat] >> the idea here is we have a population of possible ways to order transactions and bundles in a conflict group. We want to combine these possible orderings together, cross and mutate them uh with the hopes of of finding better uh ways to order the transactions and bundles. We let mutation crossover happen over the raw sequences, but simulation always over the nonce valid ones. So we tested on >> [clears throat] >> a thousand blocks on a high MEV day using the the parallel builder. So the parallel builder was forming these conflict groups and then we ran the genetic algorithm along with the existing algorithms that the parallel builder has on these conflict groups.

And yeah, you can see some of the other algorithms that we were comparing it to. Uh they're pretty simple. And we had a one-minute time time budget uh for the genetic algorithm. He- Here are some of the results. So it extracted more value uh compared to the other algorithms in around 45% of the blocks. The total additional ETH was 54, more or less. Um and so this was just in this 1,000 block window, which so this is pretty significant. Um and yeah, these are some other other results here, which we can also see in these plots here.

So the plot on the left is showing uh the additional MEV that the genetic algorithm captured compared to the second best algorithm in the parallel builder. Um and so you can see that there's actually a small number of blocks where this outperformed uh by a lot, but uh yeah, it's a considerable improvement in those cases. Then on the on the right, we have the percentage improvement over the second best algorithm. Um and yeah, so you can kind of see what the distribution looks like. >> [snorts] >> Uh for the left plot, if we just remove the two outliers, we can have a better uh view of what it looks like as well.

Then um another observation is that the genetic algorithm performs best in small to medium-size conflict groups. Um so that's what this table shows. It typically ties, so it finds some ordering which extracts as much value as some other algorithm um when the group sizes are quite small. When the conflict groups are in the lower hundreds, that's when it usually uh wins more. Um and then it sometimes well, not sometimes, but the the cases where it uh doesn't find the best uh ordering compared to the other algorithms is when the group sizes are very uh very large.

And the reason is because this genetic algorithm approach is very simulation-heavy, right? We need to be simulating these possible ways uh to order the transactions across the many generations. But the nice thing is that the genetic algorithm scales with compute. And so I ran these this experiments on a machine which, you know, wasn't super powerful. Um and so even though we had that one-minute time uh budget, you could probably optimize this quite a lot and get it down to a couple of seconds. And so yeah, um the main takeaways are number one that better algorithms like genetic algorithms can extract significantly more MEV um especially in these long-tail blocks.

But um there's still lots of room to explore new MEV extraction algorithms. Um yep. Yeah, thanks for listening. >> [applause] >> Are there any questions? Yeah, that was really interesting. Um I wonder uh how how how long did you kind of like dabble with algorithms to find the mutation rate and uh uh because that's always critical because then you don't know how many generations you should do and uh I mean, fitting those parameters, I mean, is this some something

straightforward? And also you mentioned that you had um less performance with uh longer sets longer longer genes. Is is that something you can overcome or Yeah, so for the first one, um there was very little hyperparameter tuning actually. Um like I didn't try to, you know, uh try different loads of different parameters to see which ones were the best. Um I just kind of chose some which made sense and um made some small changes. So again, this kind of shows that these are very good results and we weren't even like tuning the parameters um to the extent uh to which they they they maybe could have um led to better

performance. Um for the second question, the reason why uh when we have very large groups, they the genetic algorithm doesn't perform as well is because simulating just one sequence takes a very long time. And because I only had the one-minute time budget, you can't uh have many generations. Um so the genetic algorithm just doesn't perform very well because you haven't given it enough time to to find better sequences. We uh the the implement- it is parallel paralyzed, um but still like these uh it takes very long to simulate them. So even with parallelization, yeah, it's too slow.

You baseline this against very simple uh implementations. Um is there a like almost provably optimal or near optimal uh implementation that you can actually work the other way and see how far below optimality you are? That's extremely hard to to know because I mean, for some of these conflict groups, there are, you know, thousands of bundles, thousands of transactions, and there's really like no way of knowing like what is the true optimal way to order these transactions um cuz obviously if you try to exhaust all the permutations, you'd be here forever. Um but I mean, there are definitely stronger algorithms that we could we could go for and the idea with this

genetic algorithm is more to show that if you just try to sort um by some like greedy metric that's not always optimal in in certain cases because the sequential algorithms are are pretty pretty strong for most blocks. Uh but yeah, and these long tail blocks there are more interesting ways to order. You mentioned the 1-minute limit on a compute. What's the in production what's the usual limit?

What is how long does it take for the greedy algorithm? And is there a trade-off to using something more complicated or is it just something where you can just throw compute at and get better performance? So, on the machine that I was testing on the greedy algorithms were also very slow for for the very long sequences. I think some of them took around like 15 seconds to just simulate one single sequence. That's how large these sequences were. In terms of like live block building, usually you want to build a block in 100 milliseconds some or even less than that 50 milliseconds.

Um but that's also on much more powerful machines. But like you said, we could just like throw more computes and we'd probably see see better results on this genetic algorithm yeah. Thank you.