Simulation & local block building

[mempirate]

Context

Simulation

Some simulation & validation is required to consider a preconfirmation. At minimum, they need to be valid according to the protocol rules:

• Enough balance to pay for gas usage + specified gas price
• Correct basefee (> block basefee)
• Correct nonce

This is simple enough for a standalone transaction: we just request all necessary values from the execution client over JSON-RPC and match those against the received transaction.

Once we commit to a transaction, we need to keep track of any relevant variable state: the nonce and the balance. This is because essentially we've already executed the transaction, and any subsequent transactions need to be valid given the modified nonce and balance. This means that the sidecar should build some sort of proto-block template that keeps track of nonce and balance per account, and should check each new transaction against the post-state of that proto-block.

⚠️ Note on type 3 transactions: for type 3 transaction preconfs there is the additional requirement that there can only be an absolute maximum of 6 blobs per block.

Local building

For non-PBS proposers or in the case mev-boost fails, we need a way to fall back to a locally built block that adheres to any commitments given.

We can point our beacon node builder API to the sidecar instead of mev-boost, and the sidecar will act like a proxy for mev-boost (if configured) and a local block builder. Non-mev-boost users can configure the sidecar to not proxy requests to mev-boost.

Minimum viable block (easy)

Since the sidecar always keeps a (valid) block template, we can just use that when a payload is requested in a local block building situation. If there were no commitments made, we just don't return a block which will force the beacon node to get one from the execution client over the engine API.¹

What's important here is that we respond in time with a payload so that the beacon node won't fall back to the execution client, which would break commitments. This delay is defined in the specs as BUILDER_PROPOSAL_DELAY_TOLERANCE=1s.²

Better block (hard)

Another potential option would be to have our sidecar communicate with the execution client through the engine API to request a block (this already is hard because it requires access to the payloadId which is something that only the beacon node has AFAIK).³

Once we have that block, we can modify it to include our commitments with some naive algorithm that takes into consideration the block value and block validity. We then derive the header once more and send it to the beacon node, who will take care of the rest.

The second option would obviously be much better for local builders but is much more complex.

Footnotes

1. https://github.com/ethereum/builder-specs/blob/main/specs/bellatrix/validator.md#relation-to-local-block-building ↩

2. https://github.com/ethereum/builder-specs/blob/982af908707113de373e62babee113782e6bb6cd/specs/bellatrix/validator.md#constants ↩

3. https://github.com/ethereum/execution-apis/blob/main/src/engine/cancun.md#request-2 ↩

[merklefruit]

Note on deriving the header for a new block

Only 1 field in the ExecutionPayloadHeader requires access to state: state_root calculation.
All other fields can be calculated by simply taking the post-state bundle simulation results, and some block context data.

In particular, as we see in Reth's implementation this calculation also uses the intermediate merkle branches to recompute the state root. We need some way of accessing this!

[thedevbirb]

On calculating the new state root

As noted by @merklefruit in order to produce a valid ExecutionPayloadHeader for the fallback block we need the state_root calculation, which requires a read-access to the state database.
This is possible on Reth since the MDBX database allows multiple readers from independent processes, but this is not the same for LevelDB (see here) and PebbleDB (see here), which means we could not be able to do access the state from the EL if it's running Geth for example.

We're currently exploring an alternative approach leveraging partial Merkle Patricia Tries as done in this PoC https://github.com/zemse/partial-mpt. It consists in the following steps:

• Get latest block state root
• Create partial MPT from block state root
• Simulate fallback block transactions using trace_callMany RPC endpoint (or multiple debug_traceCall with state overrides in Geth)
• Get state diffs of touched accounts
• Get account proofs for touched accounts (at the previous block) from local EL node, using eth_getProof
• Load account proofs into partial MPT
• Apply state diffs to partial MPT
• Build new state root from partial MPT
• Build new valid header with new state root
• ?
• Profit

On the implementation side, the following changes will made to the sidecar components:

1. Add new methods to RpcClient: eth_getProof, debug_traceCall, trace_callMany
2. Import, fork or re-implement an MPT library (such as https://github.com/zemse/partial-mpt) with "manual enough" access
3. Implement "state root calculator" using RpcClient and MPT library above

[zemse]

I'd like to mention an unhandled edge case in the partial-mpt implementation. If we have two nodes on a branch and attempt to delete one (by setting its value to nullish), this results in the branch having only a single node. Geth's implementation of the MPT rearranges the trie: the branch is removed, and the remaining node is moved to the branch's position. This changes the key of the remaining node, which also exists in the preimage, thus altering its hash. Unfortunately, without the preimage of this remaining node, we cannot calculate its updated hash.

Currently, my implementation would throw an error stating "node not present, please add a proof." Though it would work if the preimage of the mysterious node were provided, its key cannot be determined through available simulation APIs that give state access.

There are some approaches to resolve this issue:

1. Brute Forcing on Keccak: This involves finding a key whose keyhash matches the initial nibbles of the mysterious node, then using the eth_getProof API to retrieve the preimage. Given that the mainnet MPT typically has a depth of about 10, this is akin to vanity mining an address with approximately 10 leading zeros. The downside of this approach is its performance cost.
2. Adding a Custom RPC to the Ethereum Node: This custom RPC would directly expose the MPT, allowing us to get a node by its MPT keyhash. The partial MPT can provide the exact keyhash of the node whose preimage is required for branch rearrangement. Using the custom RPC, we can immediately obtain the raw node. The downside is that this requires a full node to implement the custom RPC. While the eth_getProof API was designed to assist light clients, it doesn't adequately address this edge case. (I wish the described custom RPC becomes a standard RPC to aid use-cases involving partial MPTs, as such RPC is trivial to implement).
3. Updating state access APIs in ethereum nodes to also include keys for nodes that were rearranged. I think this approach is not right because the purpose of state access APIs is to fill the EIP-2930 access list and including entries that do not get warmed is undesirable.

Addressing this issue was on my to-do list, but I opted for a different approach (without partial-MPT) in my original project. However, if it is helpful, I am more than happy to help implement the fix :)

[thedevbirb]

Thanks a lot @zemse for the feedback here and the support you provided in our Telegram chat. We really appreciated it.

For reference, I’ll report a more concrete example of this interesting edge case we didn’t know about, along with new possible workarounds.

Edge case example

Consider the following state trie:

Assume this is a storage trie of a certain account, since account nodes can't be deleted anymore after the Dencun hard-fork due to the change of the SELFDESTRUCT opcode behaviour.

Suppose we made just one pre-confirmation for this block that only resets the storage slot with key a77d337 (on the bottom left). Using the algorithm defined above, when making the eth_getProof call we will get the proof of the associated account along with the proof of such storage slot. Note that these proofs return just the hash of the children of branch nodes, not the whole RLP-encoded data.

The node associated with such storage slot will be deleted to save on space along with its parent branch node (since it has just one children) and the extension node (with shared nibbles d3 ). The sibling a77d397 will be placed under the only remaining branch node with a different key-end field. As @zemse noted, such information is in the hash digest, which means we should re-compute the hash of the node but we don’t have its pre-image.

Proposed solutions

In the context of our simulation unfortunately it is not feasible to use brute-force on Keccak due to latency reasons. At the same time forks of EL clients will slow the development significantly, unless they’re really minor changes.

debug_dbGet

As @merklefruit noticed, Geth offers the debug_dbGet RPC endpoint in its debug namespace that allows to retrieve the raw value of a key stored in the state database. This would essentially solve our problem because we could retrieve missing trie node pre-images on demand.

Unfortunately, this seems to be available only on Geth, thus client diversity would not be enhanced by proposers running Bolt in the first place.

Using JavaScript tracers

An alternative path could be leveraging the flexible JavaScript tracer available in all execution clients in the debug_traceCall RPC endpoint to fetch the storage root of accounts after a transaction, in the Result event.

The new flow would look as follows:

• From the latest block, simulate all pre-confirmed transactions using debug_traceCall and get all touched accounts.
• Since we know all touched accounts, we call eth_getProof for every one of them to fill the partial MPT.
• Call debug_traceCall again for the last pre-confirmed transaction using the JS custom tracer that on Result returns the new account fields (balance, nonce, code, storage_root*) for each touched account
• Update the partial MPT with these new roots, and calculate the new MPT root

*Obtaining the storage root is currently not possible but would be easy to implement in Geth.

The JS tracer method exposes access to the StateDB interface in Geth. This interface doesn’t support the GetStorageRoot method, even though the concrete DB type (also called StateDB) that implements this interface actually has it.

• Without this function, the alternative is to use db.GetState for each touched storage slot and compute the storage root manually for each touched account in the trie.

Implementing this in Geth would be quite easy. First, we need to extend the StateDB interface with the GetStorageRoot . Then, we need to write the wrapper method to the dbObj type https://github.com/ethereum/go-ethereum/blob/a71f6f91fdb2fcccdd0c1e336267951d45932f26/eth/tracers/js/goja.go#L722-L728.

Alternatively, a GetStateRoot could also be easily implemented for the StateDB type:

func (s *StateDB) GetStateRoot() common.Hash {
	return s.trie.Hash()
}

For now we’ll leave this approach aside as forking execution clients should be our last resort, even if it is not a big change.

Stateless witness

• all: stateless witness builder and (self-)cross validator ethereum/go-ethereum#29719 would be useful

Essentially, with Geth you could provide a block execution "witness", in which all the necessary state inputs are included, and use these to build the post-execution state root. However, this functionally is not exposed in an RPC endpoint.

engine_NewPayloadV* error messages

Another interesting approach is relying on EL client error messages when processing a new payload using the engine_NewPayloadV* RPC endpoint. We’ve checked Geth and Reth for now and they both provide the expected and actual value in case of state_root mismatch. This could be exploited to skip the state root calculation entirely, however we don’t feel is a robust final solution.
Lastly, this could be also be leverage to get other data needed to create a valid fallback block as outlined in the next section

Other data needed for a local block

Actually, in order to produce a valid fallback block other than the state_root we also need the receipts_root , the logs bloom filter and the gas used.

It’s possible to obtain these using tracers. To recap:

• receipts_root , gas_used and logs_bloom: use CallTracer with state overrides. This will also require looping through all logs emitted by each individual call frame
• state_root: use PreStateTracer with state overrides as described above + some mechanism to retrieve nodes pre-images in case they’re missing

This is starting to become a lot, very manual and with some flaky dependencies, such as the fact that not all ELs support state overrides.

Lastly, we also need to handle withdrawals. Luckily, these can retrieved from the PayloadAttributes beacon client event stream.

Local EVM execution with generic state fetcher

Since a local simulation would be the ideal solution, let’s try to outline the required steps:

1. Create an in-memory partial MPT implementation that supports REVM’s Database trait
2. Start simulating transactions locally on top of a basic EVM context set to the next block
3. Whenever some account info or storage slot is needed from the trie, fetch it “on the fly” by calling eth_getProof
4. When done, the resulting execution context will already contain all necessary info to calculate the receipts root, logs bloom, transactions root.
5. For the state root, the trie might need some extra pre-images (just as an edge case). In this case they can still be fetched “on the fly” by calling debug_dbGet on Geth.
6. We’ve successfully built an entire payload locally LFG!

The beauty of this approach is that it abstracts the “state fetcher” away from the payload creation. We can use eth_getProof+ debug_dbGet , but we could also use:

• Reth’s local DB file, which allows read-access from independent processes
• a more specialized indexer service (e.g. a Reth ExEx or RPC extension)
• a future trie-by-hash endpoint like debug_dbGet but with wider support on other clients
• some future stateless witness tracer, like all: stateless witness builder and (self-)cross validator ethereum/go-ethereum#29719

This also has the benefit of actually building the block locally instead of simulating it in the execution client via debug_traceCall with state overrides.

Cons: this is significantly more work than anticipated, especially point (1) and (2)