Feature request: update bundle selection algorithm to avoid bundle stuffing

[thegostep]

The current bundle selection algorithm has a known limitation which allows the inclusion of regular transactions from the mempool to artificially increase the priority of a bundle.

A new algorithm should be conceived to avoid this issue.

[thegostep]

v0.2 Proposal

Bundles in 0.1 were sorted according to the following score:

This led some searchers to "stuff" their bundles with unrelated transactions, in order to inflate the summation term, rising in priority. For v0.2, we adopt instead the following score for ranking the bundles:

This simpler formula is insensitive to the gas price set by transactions in the bundle, effectively preventing bundle stuffing. Accordingly, searchers can no longer rely on gas price for inclusion, so payment to miners should be done exclusively via direct coinbase transfers.

Ref:

[jparyani]

We are tweaking this to be:

g_max will be provided over rpc with the bundles and controlled by the relay for now. It will start with being set to 0, which will put us back to the formula:

[sbarratt]

One potential issue with the current formula is that it penalizes complex bundles that use a lot of gas. For example, liquidator bundles, which will use gas in the millions. If Bundle A pays the miner 1 ETH and uses 100k gas, but bundle B pays the miner 2ETH and uses 210k gas, the current system will prefer bundle A. But clearly bundle B is much more profitable for the miners given the real economic tradeoff. The issue of using the implied gas price is that only one flashbot bundle is allowed per block, so thinking in marginal terms is not the right idea.

How about the following:

$P-C$,

where $P$ is the direct ether payment to the miner and $C$ is an estimate of the opportunity cost.
(As you said in the zoom call it's impossible to simulate all possible bundles against real blocks.)
One option is to estimate $C$ by using a generic estimate for the marginal gas price of inclusion in a block.
One option would be the the qth-percentile (say 30%th) over the past, say 10, blocks.
This is very easy to calculate using a standard geth node and could even expose an API for it.
Call this estimate $\hat g$, \eg, 100 gwei.
Then the opportunity cost for each txn is the max of the one plus actual gas price and the estimate of gas.
(This discourages people from submitting irrelevant txns because that will only strictly hurt their chance of inclusion.)
This charges an arb or liquidation txn in the opportunity cost the approximate marginal gas price of inclusion, which is the correct calculus.

Then the formulas for $P$ and $C$ are:

$P = V_direct + \sum_T g_T s_T$
$C = \sum \max(g_T + 1, \hat g) s_T$

@thegostep

[thegostep]

The biggest challenge we are facing is coming up with an estimate for $C$ which doesn't open up edge cases leading to exploit

cc @jparyani @epheph wdyt of this proposal?

[jparyani]

My major concern with something like this is finding the correct value for g_hat. If it were too low, it would be easy to fill up a whole block with chi minting at a price below a normal average block price. If it's too high, then we're back to the previous problem of overly punishing bundles that use more gas.

[fiiiu]

@sbarratt thanks for your thoughts. I share your wish to have bundles priced with the (approximate) economic benefit to miners. In my mind, that would be quantified by:

$P=\sum s_T.(g_T-g_0) + V_direct$

using your notation, where $g_0$ is a function (of $g_T$) doing the approximation work (see formula (8) here: https://hackmd.io/IGlkjRDrTmSJf_MM_f2Bcg).

Your \max formulation stems from a particular choice of function that besides approximation carries the load of filtering or penalizing bundles with unnecessary gas. Ideally, I think we should strive to ultimately separate these two: pricing according to approximate true value (and a "stuffed" bundle IS more valuable for the miner than an unstuffed one, provided it is stuffed "smartly" with the best vanilla txs), and restricting stuffing on other grounds (we don't want to process full blocks, etc.).

As @jparyani pointed out, the tricky part here is getting an approximation that isn't either too restrictive (leading to too little profit) or too lenient (resulting ultimately in more unprofitable blocks as compared to the vanilla ones). I ran some quick experiments to see if a parameterized version of the gas price as a function of block position, calibrated with two points taken from 9 blocks prior, would work fine and found promising results using a power-law function: https://github.com/flashbots/curve-based-bundle-pricing/blob/main/src/gas-curve-fitter.ipynb.

Still, it's not clear how this approximation would fare in practice. We also discussed the possibility of keeping a free parameter to skew it one way or the other in order to keep some level of control as we see real activity taking place. We would also still need to filter for stuffing elsewhere, and the criterion there is not clear.

I'd appreciate your further thoughts here, in particular about the choice of \max and doing pricing+filtering together--do you see it that way? Otherwise: why is the \max just an approximation?

[sbarratt]

(Sorry in advance I abuse a ton of notation...)
Honestly the proposal isn't well fleshed out, so I'll try to here. I guess the ideal solution is for each miner to try every bundle against a block from just the mempool, but that's obviously too computationally expensive. The alternative is to try to build a heuristic that selects the best bundle without too much computation. We'll focus on the case of one bundle. The heuristic is "safe" in the sense that because of the profit guarantee a miner will never choose to include the bundle if the vanilla block has higher profit. So it can be a bit aggressive - its main goal is to be accurate though.

The real score is the miner profit of flashbots bundle - miner profit of vanilla geth block. Since the profit of the vanilla geth block is constant, we're really trying to maximize the profit of the flashbots bundle. The profit of the flashbots bundle is: (coinbase transfer) + (gas payment of the flashbot bundle) + (gas payment of other transactions). We know coinbase transfer, and the gas payment of the bundle, but don't know the gas payment of all transactions, because a flashbots bundle might displace some transactions depending on its size.

Consider the vanilla geth block. It has transactions with gas price p_T and gas usage g_T. What the flashbots bundle really does is displace a number of those lower priced transactions, since the best thing to do is to displace the ones that have the lowest gas price. So you take the total gas payment of the lowest price transactions up to the gas usage of the bundle. The formula for that is sum{T | sum_tau g_tau <= g_bundle} p_T g_T, assuming sorted in ascending order. So the gas payment of the other transactions is equal to the (gas payment of vanilla geth bundle) - (gas payment of transactions displaced by the bundle). Since (gas payment of vanilla geth bundle) is constant, we can ignore it.

So the important term is - (gas payment of transactions displaced by the bundle), which we know to be -sum{T | sum_tau g_tau <= g_bundle} p_T g_T. But we don't really know this term a priori. We need to approximate it. Here's a good approximation: \sum_{transactions in bundle} p_bound * g_T, where p_bound is some approximate gas price of the lower transactions in a vanilla geth block. Ideally, p_bound is actually a function of g_bundle, since if you displace more transactions, this comes at higher cost. But to keep it simple, p_bound could be set to something conservative, eg the 70%-th quantile of nonzero gas prices over the past 10 or so blocks.

There is an issue though - people might just include expensive transactions from the mempool to advantage themselves.
Therefore, here's a solution. The approximation of the gas displaced by the bundle becomes \sum_{transactions in bundle} \max(p_bound, p_T) * g_T. Therefore, there is no benefit for a searcher to include random transactions from the mempool, since they are netted out by this term. As further discouragement, we can add a small constant to p_T that discourages them even more: \sum_{transactions in bundle} \max(p_bound, p_T+c) * g_T

So the final metric is
(coinbase transfer) + (gas payment of flashbots bundle) - (approximate gas payment displaced by flashbots bundle),
where
(approximate gas payment displaced by flashbots bundle)
is \sum_{transactions in bundle} \max(p_bound, p_T+c) * g_T,
where
g_hat is a conservative gas price to be included in the block, and c is a small constant (eg 1 gwei) to discourage including random high-price transactions from the mempool.

The formula can actually be simplified to
(delta coinbase) + \sum min(-c,p_T-p_bound) g_T

When p_T is 0 (eg in a searcher txn), this formula gives -p_bound, which is supposed to price that transaction vs an alternative in the mempool.
When p_T is nonzero but less than p_bound, eg a random txn from the mempool with low gas price, this also prices that transaction versus an alternative in the mempool. Therefore, you are docked a little bit for including a mempool transaction that has 50 gwei gas price when p_bound is 100 gwei.
When p_T is greater than p_bound, the formula gives -c. In this case, you include a transaction that is more attractive than the mempool. You are docked c here, just so that you can't include random high price transactions for free.

Two example bundles:

A liquidator bundle, with one transaction that has 0 gas price:

• It uses 2m gas, and pays the miner 0.5 ETH.

An arb bundle, with two transactions:

• the router transaction that they're trying to arb, 100 gwei gas price, 130k gas used
• the arb transaction, 0 gas price, 160k gas used, which pays the miner 0.1 ETH

Under the current formulas, the first bundle has the score 2.5e-7, and the second has the score 3.44e-7. The second would be chosen under the current mechanism. However, consider this mechanism and if p_bound is 100 gwei and c is 1 gwei. Then the calculus looks like:

For the first bundle: 0.5 ETH - (2 million gas) * (100 gwei) = 0.3 ETH
For the second bundle: 0.1 ETH - (130k gas) * (1 gwei) - (160k gas) * (100 gwei) = 0.08387.

It's not even close which one the miner should include. The breakeven point for p_bound is 217 gwei, where the advantage becomes 0.066 ETH.

Here's another one, with two arb bundles.

An arb bundle, with two transactions:

• the router transaction that they're trying to arb, 500 gwei gas price, 130k gas used
• the arb transaction, 0 gas price, 160k gas used, which pays the miner 0.1 ETH

An arb bundle, with two transactions:

• the router transaction that they're trying to arb, 50 gwei gas price, 130k gas used
• the arb transaction, 0 gas price, 160k gas used, which pays the miner 0.105 ETH

Under the current score mechanism the second bundle will clearly win, since they use the same gas. However, under this metric it looks like:

For the first bundle: 0.1 ETH - (130k gas) * (1 gwei) - (160k gas) * (100 gwei) = 0.08387 ETH
For the second bundle: 0.105 ETH - (130k gas) * (50 gwei) - (160k gas) * (100 gwei) = 0.0825 ETH

So under this mechanism the first bundle wins.