Proposal: Delayed State Root for Sub-Second Block Times

[frisitano]

Describe the feature

In the context of sub-second block times, computing the state root at the end of the block introduces latency that is difficult to predict. This unpredictability forces us to be conservative during payload construction to ensure we can meet timing constraints, often resulting in fewer transactions per block to accommodate a buffer for state root computation.

To address this, we propose introducing a delayed state root mechanism. By decoupling state root computation from the critical path of payload building, we can improve performance and unlock more efficient transaction processing.

However, this change presents several downstream considerations, particularly with respect to zk proving. Specifically, we need a reliable mechanism to associate the state diff of a block’s execution with the state root declared in the subsequent block.

Proposal
Introduce a delayed state root model: The payload produced for block n will not include the state root directly. Instead, the state root will be computed after execution and only reflected in block n+1.

Use extra_data for linkage: We can leverage the extra_data field to encode a serial hash of the state diff from the prior block’s execution, creating a verifiable link between the state transition and the declared state root.

ZK Proving Considerations: This model would require that zk provers be able to verify that the state root claimed in block n+1 is the result of executing the state diff from block n. This may involve changes to the proof structure or witness format to incorporate such linkage.

Benefits
Enables more efficient payload building by removing a major source of latency from the critical path.

Improves stability of sub-second block times.

Potentially simplifies block building under high load conditions.

Open Questions
What are the trade-offs in terms of proof complexity and client implementation?

How do we ensure backward compatibility with existing consensus and execution APIs?

Are there more robust alternatives to using extra_data for linking state diffs?

Additional context

No response

[Thegaram]

I don't see much impact on the proving. State transition will be proven just like it is now. The only thing that needs to be changed is how the header fields are verified.

When proving block N, you'd need to prove

1. Executing this block results in state root R. (This will be in the header of block N + 1 but that's irrelevant for now.)
2. The state root field of block N includes the state root after executing block N - 1.

Use extra_data for linkage: We can leverage the extra_data field to encode a serial hash of the state diff from the prior block’s execution, creating a verifiable link between the state transition and the declared state root.

I don't really get this part, what is the issue that this aims to solve? Isn't the parent block hash enough of a link?

Or is the issue that in point (2) above, we might not have easy access to the state root after the previous block? That might be the case for instance for the first block in a chunk.

[frisitano]

Or is the issue that in point (2) above, we might not have easy access to the state root after the previous block? That might be the case for instance for the first block in a chunk.

Yes, exactly, this is the problem. Sorry, I should have focused on articulating the issue better instead of proposing a solution. I will attempt to do that now.

When we migrate to the delayed state root, we are removing the state root computation from the block state transition function. The state root computation is computed "out of band". The state root for block n (S_{n}) can be defined as S_{n} = f(S_{n-1}, SD_{n-1}), where SD_{x} is the state diff of block x, and f is the state root update function. As such, if we look at a block (n) in isolation (consider the first block in a chunk, as you mention), it has insufficient data to prove its state root because it needs both S_{n-1} and SD_{n-1}. You correctly mention that S_{n-1} is available via the parent hash, but SD_{n-1} will not be available in the proving context.

I withdraw my proposal to use extra_data; upon reflection, I think this is a bad design.

[Thegaram]

Got it.

The easiest solution would be to prove overlapping segments of blocks. I.e. if a chunk contains blocks A..=B, then we prove (A - 1)..=B. Though it is a bit wasteful, depending on how large chunks are.