feat(fill): support stateless block validation testing

[jsign]

This issue requests that EEST support testing stateless block validation. The main goal is to propose something that we think is reasonable and start the conversation since this probably requires some organization within the STEEL team.

Context and history

This section explains in more detail the motivation for the ask and a bit of history in previous attempts to do this in EEST. If you already know where this ask is coming from, feel free to skip this section — I’m targeting someone that don’t know much about how this ask fits Ethereum's needs.

Today, EEST targets stateful EL clients — the EEST fixtures provide the genesis block with the alloc, and a set of blocks to execute, allowing the client to verify the block validation of those blocks. The reason I call them “stateful clients” is that whenever it executes a block, the fixture assumes the EL has all the network state. This is okay since this is actually how all nodes in the network work today (i.e., we assume every node has the full Ethereum state).

Ethereum is shifting to another reality where the majority of nodes in the network doing validation won’t have all the state. They receive the new block, and “magically” they can verify this block is valid without requiring the full state.

There are two main ways in which a node can statelessly verify a block:

• State proof-based: the new block comes with all the state required to execute the block and add proof that this provided data is correct (we call this witness). This was the main approach that Verkle Trees had in the past. The client would receive the block + witness, and re-execute the block using the provided witness.
• zkEVMs: the new block comes with a cryptographic proof that “a stateless execution of this block is valid”. Note that the block does not come with the required state, and thenode only verifies a cryptographic proof (i.e., there’s no re-execution).

Said differently, the zkEVM approach is something like proving the “state proof” based approach, providing the extra benefit of not requiring re-execution, nor providing the witness data.

In the case of “state proof based” approaches, this is the kind of EL client that nodes in the networks would execute. In the case of the “zkEVM” approach, this is the client that the prover uses to prove that a block is valid (i.e., not the nodes in the network!). For EEST interests, it is completely irrelevant if this is used for “state proof based” or “zkEVM based” approaches — the work to be done is roughly the same.

In both approaches, if the stateless client has a bug, this means that a claim that the block is valid could be wrong. For example, imagine that for whatever reason, the stateless client has a bug where if there are exactly 42 tx in the block, it returns “true” (i.e., the block is valid). The zkEVM proof will prove that this stateless client returned “true” — anyone verifying the zkEVM proof will see that the “proof is correct”, but what is being proven is wrong (i.e., it doesn’t correctly satisfy the protocol rules). (This is an extreme example).

Ultimately, what we need to test using EEST properly is that stateless client behaves correctly. Usually, 99% of the stateless client implementation is the same as the full node (e.g., all the EVM implementation is the same). What usually changes is that some tasks have to be done before the block execution (e.g., the provided data is correct, the ancestor blocks are correctly linked together, etc).

What is needed?

Testing stateless clients in EEST isn’t a novel ask, since we did some work in the past for Verkle Trees, so what I’ll describe here might not surprise many STEEL members.

Including stateless block validation in EEST requires two main buckets of work:

• EEST framework support
• Specially crafted tests are only relevant for stateless clients.

In this issue, I’m focusing on the former since we can work on the latter once the former is complete.

Each block in the fixture should have the same information as today, plus the witness. The witness is an additional data structure that provides minimal information about the Ethereum state to execute the block.

Instead of re-inventing the wheel with a new witness format, we propose using the same format in the debug_executionWitness RPC. This RPC is already supported by Reth, and Geth is also close to supporting it — so it seems like already a good de facto format to use for tests (i.e., zkEVMs already use this RPC as witnesses for blocks being proven).

You can also see a sample output here. The reth team has a public RPC node that you can use to experiment with how this looks:

curl https://reth-ethereum.ithaca.xyz/rpc \
  -X POST -H "Accept-Encoding: gzip, deflate, br" \
  --compressed \
  -H "Content-Type: application/json" \
  --data '{"jsonrpc":"2.0","method":"debug_executionWitness","params":["0x<hex block number>"],"id":1}'  | jq

Note: always target blocks very close to the tip, since the RPC has degraded performance the further you’re from it.

Here’s a sketch of what the output looks like:

{
	"state": [...],
	"codes": [...],
	"keys": [...],
	"headers": [...]
}

The goal of this issue isn’t to get into fine-grained details on how this is implemented, but to give you an idea:

• state: is a list of strings of RLP encoded MPT nodes. It contains a partial view of the MPT tree containing all the state to execute the block.
• codes: is a list of strings with all the bytecodes used in the block. Recall that the protocol doesn’t have chunkified code, so code isn’t part of the state so it is provided in this field.
• keys: this is a list of all the keys present in the state. It is particularly ordered first by address and then storage slot keys. e.g., <address1><address2><slot-1-address2><slot-2-address2><address3><sloat-1-address3>... etc.
• headers contains parent headers of the current blocks, up to 256 ancestors. This is required for any BLOCKHASH execution that was present in the block.

Some quick notes:

• keys isn’t strictly needed for block validation, but today it is present in the RPC and it should be easy to include, since the way state construction involves calculating it indirectly, so I think it shouldn’t require extra effort. If for any reason it feels complicated, we could consider removing it.
• codes is required until some form of code-chunking EIP gets implemented. When that happens, this field could be removed since it would automatically be part of state.
• headers is required until EIP-7709 is done. When that happens, this field could be removed since it would be automatically part of state.

Ideally, I think this witness generation should happen in the native Python implementation of the Ethereum spec, so it doesn’t rely on Reth or Geth for filling. I think this should be quite doable since nothing here is assuming a state tree change with new hash functions or similar.

So, for this first “EEST framework support” milestone, I would say the first two steps are:

1. Implement the witness generator (i.e., debug_executionWitness) for a block in the Python spec implementation.
2. In EEST, use this feature to include the generated witness in the block fixture.

The good part is that when doing 1., the implementors could validate if the output matches with the currently working Reth/Geth implementation, as to have a quick feedback loop to “validate” it. This is how Geth might be double-checking their RPC implementation against Reth in the current draft.

For the "custom stateless block validation tests" that I mentioned before, we will probably want to generate some invalid witnesses and assert that the block validation fails. As a quick example, if the headers field contains an ancestor that doesn't match the parentHash of the block being validated, then clearly the block validation must fail. I don't think it is worth diving too much into how EEST can support this "custom tunning of witnesses" for these special tests, but I just wanted to quickly mention it.

I’ll stop here since I think this is more than enough to get the discussion rolling. I think it would be helpful to start marinating this line of work, since we will require doing this in the near future.

[s1na]

What should be the format for headers?

[jsign]

What should be the format for headers?

RLP encoded headers