Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow Proposers To Force Transaction Inclusion in Payloads #52

Open
nisdas opened this issue Sep 30, 2022 · 23 comments
Open

Allow Proposers To Force Transaction Inclusion in Payloads #52

nisdas opened this issue Sep 30, 2022 · 23 comments

Comments

@nisdas
Copy link

nisdas commented Sep 30, 2022

Currently block proposers outsource block building to remote builders via relays to maximize block proposal income. While this makes sense for both solo stakers and pooled stakers as they want to have access to MEV income, it comes at a great cost as it provides relays/builders full control over what transactions can be included in a payload. Block builders might choose to censor certain types of transactions even if they are perfectly valid and economically attractive. The end result would be that block proposers would inadvertently also censor these transactions as full control over transaction inclusion has been handed over to builders as the current APIs currently stand.

Proposal

The current state of the builder apis can be improved to allow for stronger censorship resistance guarantees along with still allowing validators to access MEV income. Instead of the block proposer allowing the builder to build the whole payload, the block proposer now submits a list of full transactions that it wants added to the payload by the builder when requesting the execution payload header in GET /eth​/v2​/builder​/header​/{slot}​/{parent_hash}​/{pubkey}. This would be a new endpoint as the expected request/response from this is different(even if it is easily extendable from the current data structures)

The builder now has to include these transactions into the payload and is a constraint in the block building process. Once the builder has built the execution payload, it returns the execution payload header along with a multiproof that verifies the existence of the desired transactions for the provided transactions field root.

Once the block proposer receives the response back it verifies that the transactions were all included by the builder:

  • Provided multiproof verifies for the desired transaction list.

Once this is verified, the block proposer can then sign the blinded block and request the full block from the builder and then broadcast it. This proposal accomplishes a few things:

  • Adds stronger censorship resistance guarantees for honest validators who want access to mev income.
  • Allow the builder to prove inclusion of specific transactions without revealing the contents of them.
  • Prevents relays/builders from being handed unilateral power to censor txs/entities from ethereum.

The transactions to be force included can simply be retrieved from the local node's mempool. Ex: Top N most valuable transactions seen. In the event that the relay/builder attempts to censor, the proposer simply falls back to local block building. This allows honest validators to detect when relays attempt to censor and fall back to building locally.

An advantage of this proposal is that it is pretty straightforward for consensus clients to implement on top of the existing builder api.

@mcdee
Copy link

mcdee commented Sep 30, 2022

Once the builder has built the execution payload, it returns the execution payload header along with the list of transaction roots that was used to derive the transaction field root in the payload header.

Why this rather than a (multi-)proof? The proof would be smaller on the wire and require less computation on the part of the beacon node.

@metachris
Copy link
Contributor

metachris commented Sep 30, 2022

Brainsync ⚡ At Flashbots we're also thinking along these lines and a more complete proposal is in the works and will be out shortly (hopefully today, perhaps early next week).

The problem with the approach presented here is that (a) relays have no way to send transactions to the builders, and (b) at the time of the getHeader call it's already late in the process.

What we're thinking about is is a must-include transaction-hash list as part of getHeader, and merkle proofs of inclusion as part of the response:

  1. The BN provides a must-include list of transaction hashes (rather than full transactions) to mev-boost
  2. mev-boost remembers it and sends it along with the getHeader call to the relays
  3. relays only sends bids that contain the must-include transactions, with merkle proofs of inclusion for each one
  4. mev-boost can verify these proofs and only present a bid to the BN if it satisfies the requirements

We think this simple change gives validators more choice and can be expanded to include extra utility in the future, e.g. to meet other kinds of preferences that validators have over block contents.

@mcdee
Copy link

mcdee commented Sep 30, 2022

Including the tx hashes in getHeader seems too late in the process, I think there needs to be an earlier message so that the list of tx hashes can be sent from the relays to the builders (although this will cause issues with slot 0 of an epoch, and won't work with SSLE if it arrives, but better than nothing).

Re: 3) you can send a single multiproof, which would be more efficient.

I would also want to see MEV-boost return the full multiproof to the beacon node so that it can verify it independently. MEV-boost shouldn't be more than a transparent multiplexer, with no difference to the beacon node's operation if it is talking to MEV-boost or to a relay directly.

@nisdas
Copy link
Author

nisdas commented Sep 30, 2022

Why this rather than a (multi-)proof? The proof would be smaller on the wire and require less computation on the part of the beacon node.

If N is large it might be simpler to simply send the transaction root list rather than multiple proofs. You would simply need to compute it once rather than multiple times per proof. But I don't feel too strongly, multiproofs are fine too.

@nisdas
Copy link
Author

nisdas commented Sep 30, 2022

What we're thinking about is is a must-include transaction-hash list as part of getHeader, and merkle proofs of inclusion as part of the response:

How would a builder build a block if it can't find the provided tx hashes in its mempool ? I dont think nodes have a global view of all transactions in ethereum, unless we want that to be a builder requirement. The side effect would be you might simply have a lot more builders failing to build blocks because of this.

Including the tx hashes in getHeader seems too late in the process, I think there needs to be an earlier message so that the list of tx hashes can be sent from the relays to the builders (although this will cause issues with slot 0 of an epoch, and won't work with SSLE if it arrives, but better than nothing).

This is probably going to be a requirement, otherwise it is way too short a time to build a valuable block. Possibly we could have a prepareTxs call or something after the last block has been seen.

@mcdee
Copy link

mcdee commented Sep 30, 2022

If N is large it might be simpler to simply send the transaction root list rather than multiple proofs. You would simply need to compute it once rather than multiple times per proof. But I don't feel too strongly, multiproofs are fine too.

It's an efficiency thing more than anything else, but given that we're burning so much time with the back-and-forth already I feel that we should reduce the impact of any additions as much as possible. Note that a single sparse multiproof should be a fair bit smaller than multiple proofs, and they can all be proven in a single pass. A bit old, but https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/ talked about them.

@nisdas
Copy link
Author

nisdas commented Sep 30, 2022

Alright I have updated it to use multiproofs rather than the whole transaction list in the payload.

@metachris
Copy link
Contributor

metachris commented Sep 30, 2022

Including the tx hashes in getHeader seems too late in the process, I think there needs to be an earlier message so that the list of tx hashes can be sent from the relays to the builders (although this will cause issues with slot 0 of an epoch, and won't work with SSLE if it arrives, but better than nothing).

The list doesn't need to be sent to the builder.

The relay can just check if it has any bids that fit the proposer preferences (must-include list). If it has them, add the proofs and return the signed bid. Otherwise, return no bid.

I would also want to see MEV-boost return the full multiproof to the beacon node so that it can verify it independently. MEV-boost shouldn't be more than a transparent multiplexer, with no difference to the beacon node's operation if it is talking to MEV-boost or to a relay directly.

Certainly!

It will be part of the builder specs. The nice thing is that this is fully backwards compatible with the current v1 API, since it just adds non-mandatory fields (i.e. the must-include list in the request, and the proof(s) in the response).

@mcdee
Copy link

mcdee commented Sep 30, 2022

The list doesn't need to be sent to the builder.

That would make it potentially very difficulty for any given builder to get lucky and have the required txs in the block. This would result in one of two situations:

  • beacon nodes end up proposing local blocks themselves more often
  • beacon nodes end up sending much smaller lists of txs to relays in an attempt to hope that there are pre-built blocks that have these transactions in them

Neither of these seem optimal. Being able to send the list to the builder would be a significant improvement on the list being a simple filter for both builder and proposer.

@metachris
Copy link
Contributor

metachris commented Sep 30, 2022

Being able to send the list to the builder would be a significant improvement on the list being a simple filter for both builder and proposer.

Thinking this through, it would require a new, separate setMustIncludeList request (or more general setProposerPreferences?) from BN to mev-boost, which communicates the must-include list ahead of time (i.e. a few slots before the proposer duty). (The validator-registration API call seems too infrequent to be reusable for this purpose 🤔 )

This call would need to be signed by the validator, in order to avoid spamming the relays and builders with must-include lists that don't originate from the actual future proposer.

@nisdas
Copy link
Author

nisdas commented Sep 30, 2022

Just to add to @mcdee 's comment, I dont think it is possible to make this work without providing the builders full transactions that we have to include in the payload. Otherwise it basically requires all builders to have total information on all transactions in the network which isn't feasible. Providing just the transaction roots instead via the relay would lead to a very fragile block building system and also remove the possibility of proposers submitting private transactions directly.

Thinking this through, it would require a new, separate setMustIncludeList request (or more general setProposerPreferences?) from BN to mev-boost, which communicates the must-include list ahead of time (i.e. a few slots before the proposer duty). (The validator-registration API call seems too infrequent to be reusable for this purpose thinking )

It has to be the previous slot, or after the last block ( parent) was received and processed. Otherwise you risk submitting stale transactions, which the builder can't build the block with anyway.

@terencechain
Copy link
Contributor

A poor man's thought. Maybe we can bundle the CR tx list or CR tx hash list with ValidatorRegistrationV1. The beacon client will send registration at every EPOCHS_PER_VALIDATOR_REGISTRATION_SUBMISSION interval. I think it's essential for censored tx to eventually be included but not asap. This is not the perfect solution, but it will simplify things a lot

@mcdee
Copy link

mcdee commented Oct 1, 2022

Trouble with bundling that far in advance is that the tx hashes will become stale. It's possible to change the tx list semantics to mean "must be included in or before my proposed block", which would partially address the issue, but that still leaves a couple of areas where I think the system would be weak:

  • base fee rises above that in a required tx. Seems easy enough to say "ignore", but not sure how much work it would be for the beacon node to then have to check if this is the cause of the lack of inclusion
  • tx is now invalid (i.e. doesn't have enough Ether in its account to pay for gas). Again, seems reasonable to ignore but this seems to be impossible to confirm without having the full execution payload

@metachris
Copy link
Contributor

metachris commented Oct 1, 2022

Re reusing registerValidator - agree with the points of @mcdee and that the low frequency of these calls (once ever 6.4 minutes) make it hard to have effective must-include lists.

Also the mev-boost service itself wouldn't be able to know if a must-include transaction isn't part of the bid because it was already included in slots before, at least in the current architecture. It could just verify the proofs of inclusion in that block. Or maybe it's possible to construct additional proofs for the other cases too.


The most effective approach seems to be a new API call:

  1. signed by the proposer
  2. includes the full must-include transactions (not just the hash)
  3. is sent to the relay (and forwarded to builders) in advance of the validator’s slot, say after receiving the previous block or assuming the slot will be missed (~6s)

@metachris
Copy link
Contributor

@nisdas
Copy link
Author

nisdas commented Oct 2, 2022

is sent to the relay (and forwarded to builders) in advance of the validator’s slot, say after receiving the previous block or assuming the slot will be missed (~6s)

4 seconds is the spec defined time, so we can stick to that. We can couple the transaction list call to the relay with the FCU for the local execution node. This would set off the block building process in parallel locally and for remote builders.

@metachris
Copy link
Contributor

metachris commented Oct 12, 2022

FCU is sent out too late in the process, builders have already started building before they would receive that call. The inclusion list must be sent out earlier, like a slot in advance. (i.e. for a duty at slot 20, send the inclusion list latest at when payload for slot 18 is received).

@metachris
Copy link
Contributor

Tried to distill the conversations and open questions into a single draft document: https://hackmd.io/@metachris/mev-boost-inclusion-list-implementation-draft/edit

@nisdas
Copy link
Author

nisdas commented Oct 18, 2022

@metachris How would this handle stale transactions ? The reason I mentioned, right after the previous slot's block is received
is to prevent a situation where a builder has to prove inclusion of an already included transaction(ex: in your example, slot 19). Builders are constantly adding in new transactions to their payload, do we know for sure that providing the constraint one slot before is not feasible ?

@metachris
Copy link
Contributor

metachris commented Oct 19, 2022

How to handle stałe transactions is a key open question.

Providing the list just when builders start building seems too late because:

  1. List needs to go from proposer to relay (network delay)
  2. List needs to go from relay to builder (builder wants to query this list at latest at start of the slot so he can start building asap, but then 1. wouldn't have arrived)
  3. Builder can start building according to proposer preferences.

Maybe it would be feasible to send the list that late, it's something to consider. Cc @Ruteri. There's seems to be a few seconds window. Might require to push the IL from relay to builder though, rather than builder polling.

Another way to deal with these could be mev-boost having a connection to the EL client and being able to figure out more details about a IL tx.

We should also consider the other transaction edge cases, like base fee too high, not enough eth to pay fees, or even reverts 🤔

@nisdas
Copy link
Author

nisdas commented Oct 19, 2022

- List needs to go from proposer to relay (network delay)
- List needs to go from relay to builder (builder wants to query this list at latest at start of the slot so he can start building asap, but then 1. wouldn't have arrived)

How long this might take depends on the relay/builder's network infra, but I am assuming both of these actor's are running in locations with satisfactory network uplinks. If we assume that worst case, that this takes 1 second , how would 7 - 11 seconds be for the builder to prepare these transactions ?

I think we shouldn't be thinking of this:

We should also consider the other transaction edge cases, like base fee too high, not enough eth to pay fees, or even reverts thinking

We can assume the proposer is providing valid transactions as these are retrieved from their local el's mempool. Trying to further filter them is going to complicate the protocol.

@Ruteri
Copy link

Ruteri commented Oct 19, 2022

If we assume that worst case, that this takes 1 second , how would 7 - 11 seconds be for the builder to prepare these transactions ?

The problem is not with the delay per se, it's with the inability to predict when exactly this happens. Changing to a relay-pushes-to-builders instead of builders polling could actually resolve this issue.
If the proposer sends the IL as soon as the previous block is either known or expected to be missing (>6s), that would give the relays and builders at least 6s to build the block which is more than enough time.
Having said that, this will result in lower profits for proposers that will look to provide censorship resistance to the network, which will be exploited. I could imagine a situation where a builder or relay adversarially puts transactions that are expected to make select relays not provide a block in advance of expected high profit blocks (say a mint) to basically lower the competition for those blocks.
With that in mind, it still is beneficial to provide such an option to proposers willing to take that gamble.
Proposer-built suffixes would not have such problems, but it's not clear how to do those without worsening the guarantees to either proposers or builders. Maybe we should spend some more time thinking whether a solution in which for example the relay does not reveal the signed header to allow the proposer to extend the block would be acceptable.

@nisdas
Copy link
Author

nisdas commented Oct 19, 2022

The problem is not with the delay per se, it's with the inability to predict when exactly this happens. Changing to a relay-pushes-to-builders instead of builders polling could actually resolve this issue.

This seems preferable to a polling approach, as it is dependant on the proposer feeding the transactions.

Having said that, this will result in lower profits for proposers that will look to provide censorship resistance to the network, which will be exploited. I could imagine a situation where a builder or relay adversarially puts transactions that are expected to make select relays not provide a block in advance of expected high profit blocks (say a mint) to basically lower the competition for those blocks.

This would also favour builders who aren't censoring, as now these builders have a chance to build and submit a block with these transactions included. In the event this happens in a period of high economic activity(liquidation, mint, etc), these builders eventually will win out. The ultimate goal is to have this as the default for all proposers via the builder api and also attach a tangible cost to censoring out valid transactions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants