## The goal

Propose a trustless way for Native Rollups (NRs) execution to get real-time "view" of the L1 state during parallel EXECUTE precompile calls.

Ideally something like this should be possible on the NR side:

contract NativeRollupContract {
    
    
    function executeIfL1ConditionMet() external returns (bool success) {
        // pseudo-syntax    
        if L1State(maybePrefix, address).conditionMet() {
            
            doSomething();
            return true;
        
        }
        
        return false;
    }
}

Note that `conditionMet()` output may vary during L1 block execution and rollup block executor should expect that. Conflicts resolution will be based on transactions ordering and will be described later.

*Elaboration on state access interface/addressing from application level perspective is not the goal of this writing.

## Assumptions

Initial proposal version is based on such assumptions:

- Only UNIDIRECTIONAL READ ONLY state access expected
__NR <--(read)-- L1__
- Both L2 and L1 blocks built by the same entity

## Current NR Blocks Execution Design

ref: https://github.com/native-rollups/go-ethereum/pull/1

In current design proposed L1 block header contains field with precompile outputs for all NR blocks corresponding to EXECUTE call transactions order.

EL client than spins up parallel reexecution for every NR witness days and optimisitically use provided outputs from block header during L1 execution (to achieve parallelism):


Note that current design expects separated client to perform precompile execution (i.e NR STFs verification). This will require communication between Execution Client and NR Verifier.
More accurate scheme will roughtly be:


Such scheme itself solves some open problems in popular Cross-layer communication proposals:

- https://github.com/ethereum/RIPs/blob/master/RIPS/rip-7728.md#implementation
- https://ethresear.ch/t/cross-layer-communication-trivially-provable-and-efficient-read-access-to-the-parent-chain/15396#disadvantages-4

## L1 State Access

ref: https://en.wikipedia.org/wiki/Software_transactional_memory
ref_2: https://arxiv.org/abs/2203.06871

### Software Transactional Memory

TL;DR

Log all state writes and optimistically execute parallel work. Than every executed transaction goes through validation to determine if shared state was overwritten by higher order worker (In our case order is defined by transactions order). If state was changed we have to reexecute conflicting branch. Determinisitic output is expected due to strict transactions ordering in a block.

See `ref_2` for detailed explanation of Blcok-STM algo.
__In our case we should track L1 storage slots changes.__

### Hight Level Scheme

Lets return to the desired goal. We want to execute NR block and be able to have access to the L1 state during parallel execution in real time. More precisely this line:

if L1State(maybePrefix, address).conditionMet() {

Getting value at specific L1 storage slot should be trivial since NR Verifier attached to Execution Client and they established some communication during execution. More complicated part is about tracking state overwrites.

Ideally we want to make Execution Client aware of all slots/accounts that we want to track at the very start of the execution.

Think like having L1 access list for NR block.

Imagine transactions sequence where:

- Tx number 101 writes to slot 0x123 and It changes `conditionMet()` output
- Tx number 102 calls EXECUTE precompile to verify our NR block
- Tx number 103 do the same as 101

Note that NR block verification going on in parallel with L1 block execution but `EXECUTE call` Tx itself have strict order in L1 block:


Since execution of NR block depends on L1 slot 0x123, NR STF Verfifier sidecar notified Execution Client that it wants to track writes to this slot.

e.g. Execution Client can expose __versionded map__ akin to data structure described in Block-STM paper that contains changes to requested list of slots/accounts and information about writers order.
The optimal ways to communicate this information is the area for exploration.

__*TODO:__ elaborate on communication

Simplified map entry may ~look like:

{
    address+slot: [
        (writer_tx_order, value),
        (writer_tx_order, value)
    ]
}

If `latest_writer_tx_order > EXECUTE_tx_order` condition met, NR transaction with L1 state access have to be reexecuted:


## L1 State Exposure

Its preferrable to make EL client aware of required tracking list as early as possible.

### Naive approaches:

### A

Add L1 state __Access List__ to the EXECUTE call transaction or execution witness.
This will make EL client aware of required information from very start of the execution.

### B

Make NR verifier request necessary data and lazily populate tracking list on EL side.

### C

???

## Concerns
- L1 state tracking lists may make communication via RPC very intensive
- Increases the complexity of EXECUTE precompile/NR STFs execution, we will not be able to just reuse EL execution engine
- Rough worst case execution time where:
- L1 block execution time = $t$
- Time for parallel reexecution of NRs STFs = $t_{nr}$

__Is $t + t_{nr}$__

Case example: last L1 tx invalidate all execution of NR STF

## Benefits

- Crosslayer state access within the same block
- Dont care about reorgs since NR execution tied to L1 block

## Open Questions

- How much changes on EL side it requires?
- Do we actually need real time access? What if we allow only reads from parent L1 block? This will simplify protocol very much
- How networking-heavy this may be?
- PRICING
- How to sync NR chain with historicall calls to L1?
https://github.com/NethermindEth/rollup-geth/pull/11#issuecomment-2432747628
- Compare with other cross-layer proposals:
- https://github.com/ethereum/RIPs/blob/master/RIPS/rip-7728.md
- https://ethresear.ch/t/cross-layer-communication-trivially-provable-and-efficient-read-access-to-the-parent-chain/15396
- https://github.com/ethereum-optimism/ecosystem-contributions/issues/76