Bid cancellations considered harmful

mikeneuder · May 5, 2023, 10:25am

Bid cancellations considered harmful^*

mike neuder & thomas thiery in collaboration with chris hager – May 5, 2023

tl;dr; Under the current implementation of mev-boost block auctions, builders can cancel bids by submitting a later bid with a lower value. While relays facilitate bid cancellations, they cannot guarantee their effectiveness because proposers can end the auction at any given time by asking the relay for the highest bid. In this post, we explore the usage and implications of bid cancellations. We present the case that they are harmful because they (i) incentivize validators to behave dishonestly, (ii) increase the “gameability” of the auction, (iii) waste relay resources, and (iv) are incompatible with current enshrined-PBS designs.

Thanks to Barnabé, Julian, and Jolene for the helpful comments on the draft! Additional thanks to Xin, Davide, Francesco, Justin, the Flashbots team, relay operators, and block builders for discussions around cancellations.

Block proposals using `mev-boost`

Ethereum validators run mev-boost to interact with the external block-building market. Builders submit blocks and their associated bids to relays in hopes of winning the opportunity to produce the next block. The relay executes a first-price auction based on the builders’ submissions and provides the proposer with the header associated with the highest-paying bid. The figure below shows the flow of messages between the proposer, the relay, and the p2p layer.

Figure 1. Builders compete to have the highest bid by the time the proposer calls getHeader, which fetches an ExecutionPayloadHeader from the relay. The relay returns the header corresponding to the highest-paying bid among the builders’ submissions. The proposer then signs the header and returns it to the relay by calling getPayload, which causes the relay to publish the block to the p2p network.

Let n denote the proposer’s slot. The block auction mostly takes place during slot n-1. The figure below shows an example auction with hypothetical timestamps where t=0 represents the beginning of slot n.

Figure 2. An example timeline of the auction for slot n. At t=-8 (the attestation deadline of slot n-1 – see Time, slots, and the ordering of events in Ethereum Proof-of-Stake), a canonical block will generally be observed by the network. Builders immediately begin building blocks for slot n, and compete by submitting bids relative to the extractable value from transactions. The proposer calls getHeader at t=0.3, right after the slot boundary. Note that the auction is effectively over at this point, but neither the builders nor the relay know because getHeader doesn’t check the identity of the caller. After signing the header, the proposer initiates a getPayload request to the relay at t=1.7. Once the signature is verified, the relay knows the auction is over, and stops accepting bids for slot n. At t=2.3, the relay beacon nodes publish the new beacon block, and the builders immediately begin building for slot n+1. Units are displayed in seconds.

During the auction, new MEV-producing transactions are created. Builders compete by using these new transactions to construct higher-paying blocks thereby increasing the value of their bids; the winning bid typically arrives very near to or right after the start of slot n. In Figure 3, we show increasing bids being submitted by builders and collected by the relay over the duration of a single slot.

Figure 3. The value of builder bids as time passes. The green circle denotes the winning bid for this slot. A majority of builder bids arrive around t=0, which marks the beginning of the proposer’s slot. Bids generally increase as time passes, because new MEV opportunities arise.

NOTE: builder bid data is public via the Data API as specified in the relay spec.

Bid cancellations

A lesser-known feature in the relay architecture allows builders to decrease the value of their bid by submitting a subsequent bid with a lower value (and the cancellations argument in the request). The cancelling bid has to arrive at the relay later then the cancelled bid; the relay only tracks the latest bid received from each builder pubkey. The cancellation property is applied to the incoming bid, and the relay determines what to do with this bid according to the following logic:

if the bid is higher than the existing bid from that builder, update the builder’s bid

if the bid is lower than the existing bid from that builder

if cancellations are enabled, update the builder’s bid

if cancellations are not enabled, do not update the builder’s bid

For example, consider a builder who currently has a bid of 0.1 ETH. If they submit a bid with 0.2 ETH, that bid will become the builder’s bid no matter what. If they submit a bid with 0.05 ETH, it will become the builder’s bid only if cancellations are enabled.

Builder cancellations are used to provisionally allow searchers to cancel bundles sent to builders. One of the prominent use cases for searcher cancellations is CEX ↔ DEX arbitrage, where the bundles are non-atomic with on-chain transactions. Centralized exchanges typically have ticker data and price updates on a much higher frequency than the 12 second slot duration. Thus a CEX<->DEX arb opportunity that is available at the beginning of the slot might not be available by the end and searchers would like to cancel the bundle to avoid a non-profitable trade. If we decide to keep cancellations, further research around the searcher cancellation strategies should be done.

Cancellations impacting the outcome of the auction

Effective cancellations change the outcome of the auction. Given a winning bid, we define a bid as an effective cancellation if (a) its value is larger than the winning bid, and (b) it was eligible in the auction before the winning bid.

We need (b) because the relay cannot always know when the proposer called getHeader. From the winning bid, we know the getHeader call came after that bid became eligible (otherwise it wouldn’t have won the auction), thus any bids that were eligible before the winning bid must also have arrived before getHeader.

This subset of bids is relevant as each could have won the auction had cancellations not been allowed. We found that effective cancellations are quite common; from a sample of data from ultra sound relay over a 24-hour period on April 27-28th (slot 6316941 to 6324141), 269/2846 (9.5%) of the slots relayed had at least 1 effective cancellation. Similarly, a sample from Flashbots’ relay over the same time showed 256/2110 (12.1%) slots with effective cancellations. Figure 3 shows that most cancellations are submitted around t=0 (median = -510 ms), as well as the distributions of cancellation bid values (median = 0.07 ETH), and the percentage of cancellation value increase relative to winning bids (median = 0.97%).

Figure 4. (left) The distribution of cancellation times for various builders, where 0 denotes the beginning of slot n. (middle) The distribution of the value of the canceled bids. (right) The percentage increase of canceled bids. For example, a value of 10% means the canceled bid was 10% larger than the bid that replaced it.

Why are bid cancellations considered harmful?

We highlight four issues:

cancellations are not incentive compatible for validators
cancellations increase the “gameability” of the block auction
cancellations are wasteful of relay resources
cancellations are not compatible with existing enshrined-PBS designs

Cancellations and validator behavior

Validators control when they call getHeader and thus can effectively end the auction at any arbitrary time. The honest behavior as implemented in mev-boost is to call getHeader a single time at the beginning of the proposer’s slot (t=0).

Figure 5. (left) The distribution of timings for getHeader and getPayload from a sample of blocks from ultra sound relay. (right) The distribution of the difference between the call timestamps. This represents the time it takes for the proposer to sign and return the header.

We collected this data by matching the IP address of the getPayload and getHeader calls, which limits the sample to proposers who make the call from the same IP address. The vast majority of getHeader calls arrive right after the slot begins (at t=0). However, with cancellations, rational validators are incentivized to call getHeader multiple times, and only sign the header of the highest bid that they received. This is demonstrated in the example below.

Figure 6. Honest vs optimal validator behavior for calling getHeader. Each circle represents a builder bid, where the builder has cancellations enabled. If the validator behaves honestly and calls getHeader at t=0, the relay will return the latest builder bid, which has a value v=1 (in red). However, if the proposer calls getHeader at t=-1 (one second before their slot begins), they will receive a higher bid with a value v=4 (in blue).

Validators can effectively remove cancellations by calling getHeader repeatedly, and only signing the highest response. Furthermore, there exists an incentive for them to do this because it can only increase the bid value of the header they end up signing.

Cancellations increase the “gameability” of the auction

By allowing builders to cancel bids, the action space in the auction increases dramatically. We focus on two strategies enabled through cancellations (though there are likely many more!):

bid erosion – where a winning builder reduces their bid near the end of the slot.
bid shielding – where a builder “hides” the true value of the highest bid with an artificially high bid that they know they will cancel.

Bid erosion

This strategy is quite simple: if the builder knows that they have the highest bid on the relay, they can simply reduce the value of the bid gradually so long as they maintain a lead over the other bids, thus increasing their profits as a direct consequence of paying less to the proposer. Another heuristic of bid erosion is the winning-builder bids decreasing in value as other builders bids continue increasing in value. Figure 7 shows this strategy playing out.

|

Figure 7. In both plots, the green circle represents the winning bid and the red x’s are effective cancellations. (left) We see that the winning builder continually reduces their bid, but still wins the auction. (right) The builder submits a set of high bids and quickly erodes it down to a reduced value.

Bid shielding

As described in Undesirable and Fraudulent Behaviour in Online Auctions, a bid shielding strategy places an artificially high bid to obfuscate the true value of the auction, only to cancel the bid before the auction concludes. Applied to the block auction, a builder can hide the true value for a slot by posting a high bid and canceling it before the proposer calls getHeader. This strategy takes on some risk because it is possible that the builder must pay out the high bid if it wins the auction, but cancelling the bid a few seconds before the start of the slot makes the strategy quite safe. Additionally, this strategy could be used to grief other builders who have an advantage during a slot into bidding higher than they would have if the shielding bid was not present.

|

Figure 8. Potential bid shielding examples. (left) We see multiple builders bidding high between t=-4 and t=-1.5, which may be an attempt to cause other builders to bid higher than they would have otherwise. As the slot boundary approaches, the shielding bids are cancelled, leaving the winning bid to a different builder. (right) A builder setting a cluster of high bids at t=-2 only to reduce their bid closer to t=0, while still winning the auction.

Cancellations are wasteful of relay resources

With cancellations, relays must process each incoming bid from the builders, regardless of the bid value. This results in the unnecessary simulation of many blocks that have a very low probability of winning the auction. Without cancellations, the relay would only need to accept bids that were greater than the current highest value. On a sample of 252 recent slots, ultra sound relay had an average of 400 submissions per slot. Of those 400, on average only 60 (15%) were greater than the top bid of the time. This implies an 85% reduction in simulation load on the relay infrastructure by removing cancellations. To illustrate this, consider the example of slot 6249130 below; of the 1014 bids received, only 59 (6%) incrementally improve the highest bid, and the remaining 955 bids could safely be ignored without cancellations.

Figure 9. The value of bids as time evolves over a single slot. With cancellations, every bid (in gray) must be processed by the relays. Without cancellations, only bids that incrementally increase the highest bid (in purple) would need to be processed.

Cancellations conflict with enshrined-PBS

Lastly, cancellations are not compatible with current designs of enshrined-PBS. For example, if we examine proposer behavior in the two-slot mechanism presented by Vitalik, we see that just like in mev-boost, there exists an incentive for the validator to ignore builder cancellations.

Figure 10. A builder submits two headers as bids. The first has val=2 and the second (a cancelling bid) val=1. The proposer observes the headers in the order that they were published. With cancellations, the proposer should include h2 in their beacon block, because it was the later bid from the builder. However, this is not rational behavior and if they include h1 instead, they earn a higher reward.

Without the relay serving as an intermediary, builder bids will be gossiped through the p2p network. Similar to the rational validator behavior of calling getHeader and only signing the highest-paying bid, any validator can listen to the gossip network and only sign the highest bid they observe. Without an additional mechanism to enforce ordering on builder bids, there is no way to prove that a validator observed the canceling bid on-time or in any specific order.

Additionally, if the final ePBS design implements mev-burn or mev-smoothing, where consensus bids from the attesting committee enforce that the highest-paying bid is selected by the proposer, bid cancellations are again incompatible without significant design modifications (e.g., block validity conditions are modified to (i) the block captures the maximal MEV as seen by attesters listening to bids (ii) attesters have not seen a timely cancellation message for the bid). This would increase the complexity of the change and require extensive study to understand the new potential attack vectors it exposes.

Future directions

Below are some short & medium-term changes we encourage the community to consider:

Remove cancellations from the relays.
- This is the simplest approach, but would require a coordinated effort from the relays and generally is not favorable for builders. The relays would enter a prisoner’s dilemma, where defecting is a competitive advantage (i.e., there exists an incentive to allow cancellations because it may grant the relay exclusive access to valuable builder blockflow).
Implement SSE stream for top bids from relays.
- An SSE stream of top bids would eliminate the need for builders to continually poll getHeader; on ultra sound relay, around 1 million calls to getHeader are received every hour. The biggest challenge here is ensuring fair ordering of the message delivery from the SSE. Perhaps by using builder collateral or reputation as an anti-sybil mechanism, the relays can limit the number of connections and randomize the ordering. As implemented today, builders are already incentivized to colocate with relays and call getHeader as often as possible to get the value of the highest bid, so the SSE could also simplify the builder-side logic.
Require proposer signature for getHeader.
- With (2) above, we could limit getHeader to just the current proposer by using a signature to check the identity of the caller. We use the same mechanism to ensure that getPayload is only called by the proposer. This change would alter the builder spec because the request would need a signature. Note that this could further incentivize relay-builder or builder-proposer collusion, as builders will want to access bidding information.
Encourage proposer-side polling of getHeader.
- On the mev-boost (proposer side) software, we could implement the highest-bid logic. This is accomplished either by polling getHeader throughout the slot (e.g., one request every 100ms) or by listening to the SSE stream if we implement (2). This effectively removes cancellations using the validator, so would not require a coordinated relay effort. Validators could opt-in to the new software and would earn more rewards if they updated. This change could cause builders to decrease the value of their bids they cannot cancel, which could also incentivize proposer-builder trusted relationships where the proposer gets access to higher bids if they allow cancellations and ignore the relay all together. Before implementing this, more discussion is needed to avoid this scenario.
Research the role of cancellations in auctions.
- We hope this post can lead to more research into exploring the nuanced spectrum between simply enabling and disabling cancellations. While we argue cancellations are considered harmful, examining the motivations behind their use by auction participants (e.g., builders, searchers) and assessing their impact on auction revenue and MEV distribution between proposers and builders remain open questions.

Please reach out with any comments, suggestions, or critiques! Thanks for reading

quintuskilbourn · May 7, 2023, 5:33pm

Great article!

One thing that might be an implicit consideration, but which wasn’t discussed explicitly is the issue that removing cancellations might increase the incentive for builder<>proposer direct channels. As you pointed out, taking the max over all bids submitted in the slot thus far, would likely mean that stat-arbers would shade their bids as they don’t know how out-of-date their bids will be when chosen. If they integrated with the proposer they would know when a block was being called for and be able to bid higher without the risk of stale bids.

A signed getHeader (assuming there was only one per slot) might be enough to alleviate this pressure if it gave teams enough time to submit a block when it was called.

soispoke · May 9, 2023, 4:26pm

Thanks a lot for your comment @quintuskilbourn!

This is a great point, and we had this in mind when mentioning that more thorough research should be done to understand why auction participants use cancellations in the first place. I agree removing cancellations might lead to bid shading, but in my mental model (1) searchers (not builders) would be the ones shading their bids, which would lead to a less efficient market, and (2) with cancellations enabled, searchers are also incentivized to collude with proposers to know when a block is being called for so they can time their cancellations accordingly.

On a broader note, I think there are more arguments in favor of disabling cancellations as an initial, significant mitigation of their negative effects. But I do hope this opens up the research space for more nuanced designs informed by thorough evaluations of centralization risks (e.g., requesting a getHeader signature might incentivize relay-builder or builder-proposer collusion), and market efficiency benefits.

M1kuW1ll · June 18, 2023, 2:38pm

Thank you very much for your post.
I am a little bit confused with the part about cancellation and validator behavior.

Why is the proposer incentivized to call getHeader multiple times with cancellation enabled, and it can only increase the bid value? I guess you are saying the value of the block increases as time passes because more MEV opportunities accumulate. But if a builder is using bid erosion strategy to gradually decrease the bid but still maintain the highest, calling getHeader multiple times will cause the proposer to lose profits because the bid is decreasing. Am I understanding it correctly?
So if a proposer calls getHeader multiple times, it seems to be not accurate to say that the auction is effectively over when the proposer calls getHeader. As long as the proposer hasn’t signed the header, he can still call getHeader and see if there is another higher bid. So the auction is effectively terminated at the moment the proposer signs the header?
Why is this proposer incentive of calling getHeader multiple times related to cancellation? Even if cancellation is not enabled, as time passes, more MEV opportunities will be available, builders can still raise their bids or submit new higher bids. As long as the proposer hasn’t signed, he can still call getHeader to see if there is a higher one. Is it correct?
Can you pls give me some hints on these points? Thank you!

mikeneuder · June 21, 2023, 12:26pm

thanks for your response @M1kuW1ll

Why is the proposer incentivized to call getHeader multiple times with cancellation enabled, and it can only increase the bid value? I guess you are saying the value of the block increases as time passes because more MEV opportunities accumulate. But if a builder is using bid erosion strategy to gradually decrease the bid but still maintain the highest, calling getHeader multiple times will cause the proposer to lose profits because the bid is decreasing. Am I understanding it correctly?

The key here is that calling getHeader multiple times doesn’t imply the validator has to use the lower valued bids. If they call it 5x, they just choose the highest one, even if it came from much earlier in the slot (in the case of eroding bids). In the general case, the latter calls will probably have higher value and they will just sign one of those in that case.

So if a proposer calls getHeader multiple times, it seems to be not accurate to say that the auction is effectively over when the proposer calls getHeader. As long as the proposer hasn’t signed the header, he can still call getHeader and see if there is another higher bid. So the auction is effectively terminated at the moment the proposer signs the header?

Yes! This is a more accurate description I would say.

Why is this proposer incentive of calling getHeader multiple times related to cancellation? Even if cancellation is not enabled, as time passes, more MEV opportunities will be available, builders can still raise their bids or submit new higher bids. As long as the proposer hasn’t signed, he can still call getHeader to see if there is a higher one. Is it correct?

Right! The generalization here is that the validator should sign the highest bid they hear about, no matter when they heard about it. We have discussed making a SSE stream of bids from the relays that just convey the highest bid being updated, but there are some implementation considerations there too.

M1kuW1ll · June 21, 2023, 12:44pm

Thank you very much for your response!

Now I understand that cancellations are not effective against a rational proposer who can call getHeader multiple times to try to make more profit.

alextes · July 28, 2023, 8:50am

I imagine bid shielding doesn’t have many fans, but bid erosion seems more painful to cut for builders. What if relays supported builders in not overbidding without cancellations? Builders could communicate along with their bid what their view of the next highest bid is and whether they’d like the relay to erode. The moment the proposer asks for the bids, the relay could use this information to low-ball the proposer.

An interesting side-effect would be that builders would be disincentivized from submitting on the p2p layer.

I might be missing something here, but it’s fun to think along .

markodayan · August 8, 2023, 7:49am

Is it viable for relays to implement logical clock logic to effectively hold a proposer accountable to committing to their final getHeader bid? Relay here will check scalar value of clock against that of header to ensure to corresponds, or would such lead to grievances to proposer made ny builders trying to underbid leading up to whenever a proposer sends their final getHeader request to relay?

mikeneuder · August 24, 2023, 9:48pm

absolutely. this is a huge part of the issues we are surfacing around ePBS (Relays in a post-ePBS world). Basically, the bypassability of the protocol is a key weakness that we don’t have a clear answer for right now.

mikeneuder · August 24, 2023, 9:52pm

I think it’s not really needed. The relay can just offer better builder cancellations as a service if they want to (Relays in a post-ePBS world). Basically they could enforce that only a single getHeader payment is made each slot. Then they have strong cancellation guarantees, which may be quite valuable to the builders. And if the builders end up only sending blocks to that relay, then the validators have no choice but to connect.