# BALs change Proposal - Introduce protocol native support for Partial Statefulness

## Partial Statefulness

### Prerequisites

Research papers:
- [Future of stare part 1](https://ethresear.ch/t/the-future-of-state-part-1-oopsie-a-new-type-of-snap-sync-based-wallet-lightclient/23395/1)
- [Future of state part 2](https://ethresear.ch/t/the-future-of-state-part-2-beyond-the-myth-of-partial-statefulness-the-reality-of-zkevms/23396/1)

### Introduction

State growth and the lack of decentralized RPC access are well known issues in Ethereum's roadmap. With the advent of zero-knowledge proofs, we risk that these two bottlenecks will have a compounded down-side effect, because ZK-nodes will not need to store and serve state while verifying or attesting the chain.

It's expected that the incentive to actually hold Ethereum's ever-growing state will diminish, leaving the network ever more dependent on centralized entities that still have an incentive to run full nodes, since full state will still be needed for block-building, even with ZKEVMs in place. Due to the rational behavior of network participants, builders might be the only entities that will continue to serve state or answer RPC requests in the future.

In the scope of mitigating this ZK Era dependency, we reiterate the concept of PARTIAL STATEFULNESS, allowing nodes to keep and update only the range sets of their choosing (plus the minimum overhead required for functionality), while keeping full attesting capabilities.

The key design point behind Partial Statefulness is that state is not monolithic, and can be approached as a graph. Partial Statefulness does not require every node to store complex datasets (the entire tree), instead, it makes use of selective persistence , i.e. **storing domain-separated subtrees**, while a widely affordable “simple” dataset of global commitments, keeps willing participants coherent.

## Ethereum World State - refresher

- The EL world state is essentially a mapping of all 160-bits Ethereum addresses to their corresponding account states (a data structure serialised as RLP). It is not stored on the blockchain, but the implementation maintains this mapping in a Merkle-Patricia Trie (MPT).
- The accounts state in the Ethereum world state trie consists of the following 4 fields:
- `nonce` a scalar value equal to the number of transactions successfully sent from this account if it is an EOA or the number of contracts created by it if it is a contract account.
- `balance` a scalar value equal to the number of Wei owned by the account.
- `storageRoot` the account's storage trie Merkle root - a 256-bit hash of the root node of a Merkle Patricia Trie that encodes the storage contents of the account (which is a permanent data store in the state, used only by smart contracts). Data chunks are contained in the state database under their corresponding hashes for later retrieval.
- `codeHash` the account's program code trie Merkle root. Code is contract runtime bytecode executed by the EVM. It is logically state, but topologically external to the trie, i.e. it's referenced by its state-stored hash, but is stored in a flat, content-addressed database, outside the state.

**Code vs. Storage**

| Parameter | Storage | Code |
| ---------------------- | ------------------- | ------------------------- |
| Mutability | Mutable | Immutable |
| Committed via | `storageRoot` (MPT) | `codeHash` (hash pointer) |
| Inside Merkle trie | Yes | No |
| Requires Merkle paths | Yes | No |
| Shared across accounts | No | Yes |
| Affects trie shape | Yes | No |

Ethereum account leafs in the Merkle-Patricia Trie already commit to the above four fields:
`accountHash = keccak256(RLP([nonce, balance, storageRoot, codeHash]))`

These commitments are hashed up towards `stateRoot`, which is stored on-chain, in the block headers.

## How make partial statefulness technically possible?

## A. Node side

In order for partial nodes to be able to correctly store and offer verified slices of state, as wellas proofs, they must check two main conditions:

### A.1 They must be coherent

Partial nodes must maintain the tip of the trie and ensure that their stored state sits under the canonical chain.

#### Coherence in partially stateful nodes

#### Minimal local state for coherence

In order to be coherent, partially stateful nodes MUST, at least:

- Store `accountHash` for all accounts. Nodes could store it as an `address` → `accountHash` mapping (~ 10 GB).
This dataset is small enough for modest machines, yet complete enough to verify any account’s correct inclusion under the state root, and verify any account or contract changes.

### A.2 They must be Merkle-proof capable

In order to be proof-capable, partial nodes will need to prove that a specific account state (nonce, balance or codeHash) or storage (key - value pair) is correctly included in the account or storage tries, without persisting the entire state. For that it is mandatory to pass all the siblings of a particular node along the path to state root (the authentication path), otherwise the hash of their local storage would not make sense.

#### Minimal local state for proof capabilities

To provide inclusion proofs for any account or contract the nodes MUST locally persist the Merkle path of that account /contract alongside the minimal data set required for coherence.

Locally persisting the MPT structures indispensable to nodes for inclusion proofs capabilities, mainly means:
- keeping accounts trie paths (for contract account inclusion proofs), and
- keeping storage trie paths (for contract slots).

### A.3 Syncing via block enforced diffs

Today, a node needs full state in order to execute state transition (by executing transactions). The scope of the state diffs is to unlock partial state storage, in a coherent, persistent and consistent way, without re-execution.

Two types of diffs are needed to **unlock basic partial statefulness functionality**:

1. **Full-state diffs** - a list of all nonce, balance, storage and code changes that the current block induces to a certain account. These block-enforced state full diffs allow partial nodes to update the stored state values and keep local state persistent.

2. **Account-hash diffs** - the hashes of the account state for the addresses touched by the current block ->`old_accountHash` and their updated correspondent hash after executing the block's txs -> `new_accountHash`. These block-enforced state hash diffs allow partial nodes to be synchronized with the global state-root.
More detail on how nodes can update the `address` → `accountHash` mapping, can be found [here](https://ethresear.ch/t/the-future-of-state-part-2-beyond-the-myth-of-partial-statefulness-the-reality-of-zkevms/23396#p-56833-h-512-per-block-sidecars-compact-account-hash-diffs-19).

### A.4. Partial Statefulness capability ladder

The complexity of locally stored data sets, unlock different levels of partial statefulness functionality, that can be presented as a ladder of capabilities. The richer the locally stored dataset, the more Partial Statefulness becomes less dependent on third-party RPC/state providers, while still staying far below “full node” requirements:

### A.4.1 Minimal dataset: global `address → accountHash` (plus Merkle path nodes)

#### What nodes store

- For every address: the 32-byte leaf value committed under the world-state MPT`accountHash`.
- For any accounts nodes want to prove: the required Merkle nodes on the path to `stateRoot`, to recompute roots and produce inclusion proofs.

This corresponds to the above minimal local state for coherence and proof capabilities requirements.

#### What this unlocks

- **Coherence without re-execution:** nodes can structurally keep pace with the chain by ingesting the block-provided account-hash diffs, applying them locally `old → new accountHash` and re-hashing upward to confirm matching the header root.
- **Inclusion proofs for tracked accounts** that nodes store the path for.

### A.4.2 Add account metadata: `nonce, balance, storageRoot, codeHash` for selected accounts

#### What nodes store

For accounts of interest e.g. wallet addresses, frequently accessed contracts, etc., nodes store the account's data not just the hash commitment. Partially stateful nodes can optionally store metadata for all accounts (a data set of ~14 GB).
Nodes could keep no code and no storage at all, and still be coherent with persisting codeHash and storageRoot.

#### What this adds to functionality

- **Authenticated RPC for tracked accounts:** wallet can stop trusting third-party RPC queries and can serve `eth_getBalance`, `eth_getTransactionCount`, and account existence queries locally, returning value plus the Merkle proof.

- **Mempool / tx pre-validation capability:** nodes can do the checks that require actual nonce /balance knowledge instead of asking an RPC node.

- **Local verification of state changes for those accounts:** if the block provides post-state values ([full diffs](#A4-Syncing-via-block-enforced-diffs)) partially stateful nodes can check if state changes are consistent with locally stored pre-state.

### A.4.3 Add contract datasets: storage and bytecode (selective)

#### What nodes store

- Contracts that are of interest to the node, and some afferent storage slots (some ERC‑20s, allowances, and protocol slots), plus their storage-trie path under `storageRoot`. A more indepth analysis of what a partial node would need to keep storage-wise, can be found [here](https://ethresear.ch/t/the-future-of-state-part-1-oopsie-a-new-type-of-snap-sync-based-wallet-lightclient/23395).
- Optionally, they can store bytecode blobs under `codeHash`.

#### What this adds extra to functionality

- **Authenticated storage reads** with proofs; nodes could also provide the code needed for others to execute calls (serve verified inputs).
- **Proof serving:** nodes can produce inclusion proofs for account existence/balance/nonce, and also for specific storage slots e.g. ERC-20 balances and allowances.
- **Stronger local change verification:** if a block provides post-execution storage values ([full diffs](#A4-Syncing-via-block-enforced-diffs)), partially stateful nodes can check if their tracked storage slots changed as claimed, and that `storageRoot`/`accountHash` transitions are consistent.

### A.4.4. Datasets any consumer-hardware can handle

An important practicality aspect regarding Partial Statefulness is that, the minimal dataset needed to achieve functionality can be kept small enough to be widely replicated. Once many nodes can afford the coherence dataset, the network gets a base of nodes that can:
- independently track canonical roots,
- serve proofs and authenticated reads for accounts or contract they choose to track (and store Merkle paths for), and
- reduce reliance on a small set of full-state RPC providers.

### A.4.5 Node-side Diagram
A graphical view of the Partial Statefulness capability ladder:
Diagram #1
Diagram #2

### A.5. Maintaining **"The Path"**

### A.5.1 Datasets any consumer-hardware can handle

Partial Statefulness claims an important practicality aspect: the minimal dataset needed to achieve functionality can be kept small enough to be widely replicated. Once many nodes can afford the coherence dataset, the network gets a base of nodes that can:
- independently **track canonical roots**,
- **serve proofs** and **authenticated reads** for accounts or contracts they choose to track (and store Merkle paths for), and
- **reduce reliance on** a small set of full-state **RPC providers**.

### A.5.2 The Path

Keeping accounts /storage trie paths updated implies that nodes pull, when necessary, stale trie ranges from peers that offer those ranges on-demand, or [via Snap Sync](https://ethresear.ch/t/the-future-of-state-part-1-oopsie-a-new-type-of-snap-sync-based-wallet-lightclient/23395#p-56832-snap-sync-pull-what-we-care-about-with-proofs-without-rpcs-15) + proofs, OR they can avoid Merkle path "healing" altogether, by [storing the full accounts trie](#A42-Add-account-metadata-nonce-balance-storageRoot-codeHash-for-selected-accounts), thus persisting the trie structure, and only needing to apply the leaf and values updates locally.

#### The decision matrix of what to persist locally, Merkle path-wise

- For proof-serving at scale with minimal trust in external providers, nodes store full accounts trie (no MPT path fetching) + selective storage.
- For minimal disk requirements (only a few contracts to prove), nodes store global `accountHash` map + on-demand MPT path fetching per tracked contract.
- For many tracked addresses, without persisting the entire trie, nodes can do bulk Merkle path healing via Snap Sync for tracked sets, refreshing periodically.

## B. Protocol side

EIP-7928 (Block-Level Access Lists) already adds the first part of the block-enforced diffs, the full-state diffs.

## B.1 BAL existing structure

BlockAccessList
└── AccountChanges[]
    ├── address: Address (20 bytes)
    ├── storage_changes: SlotChanges[]
    │   ├── slot: StorageKey (32 bytes)
    │   └── changes: StorageChange[]
    │       ├── tx_index: uint16
    │       └── new_value: StorageValue (32 bytes)
    ├── storage_reads: SlotRead[]
    │   └── slot: StorageKey (32 bytes)
    ├── balance_changes: BalanceChange[]
    │   ├── tx_index: uint16
    │   └── post_balance: Balance (12 bytes)
    ├── nonce_changes: NonceChange[]
    │   ├── tx_index: uint16
    │   └── new_nonce: uint64
    └── code_changes: CodeChange[]
        ├── tx_index: uint16
        └── new_code: CodeData (variable)

AccountChanges = [
    Address,  # address
    List[SlotChanges],  # storage_changes (slot -> [block_access_index -> new_value])
    List[StorageKey],  # storage_reads (read-only storage keys)
    List[BalanceChange],  # balance_changes ([block_access_index -> post_balance])
    List[NonceChange],  # nonce_changes ([block_access_index -> new_nonce])
    List[CodeChange]  # code_changes ([block_access_index -> new_code])
]

**We propose to extend BAL with the account-hash diffs**, so that the protocol supports partial statefulness functionality. Partial nodes will need to minimally keep the hashes of the accounts. The hashes can be made available via a sidecar / payload, and BAL are (currently) the best option to get this feature.

## B.2 Proposed changes to BAL
Add block hash diffs as a RLP list of the addresses touched by the block accompanied by the account's pre-state hash and its post-state hash.

### B.2.1 High-level pseudocode:

# Define old account hash -> pre_nonce, pre_balance, pre_storage, pre_code are the account's pre-values. 
# Pre-state captures use first-write-wins semantics and are stored at the transaction frame level. 
# Pre-values are captured at transaction level BEFORE executing build_bal().

## Pre balance
pre_balance = StateChanges.pre_balances[Address]

## Pre nonce
## pre_nonces to be added to src/ethereum/forks/amsterdam/state_tracker.py 
## (https://github.com/gorondan/execution-specs/commit/fdb6b4f57f4b914b447a3f79fd24de414995564f)
pre_nonce = StateChanges.pre_nounces[Address] 

## Pre storage root
pre_storageRoot = keccak256(StateChanges.pre_storage[(Address, Key)])

## Pre code hash
pre_codeHash = keccak256(StateChanges.pre_code[Address])

old_accountHash = keccak256(rlp.encode(pre_balance, pre_nonce, pre_storageRoot, pre_codeHash))

# Define new account hash -> nonce_changes, balance_changes, storage_writes, code_changes as they are defined in EIP-7928. The BAL Builder captures the most recent changes for each address, using last-write-wins semantics.

## Define new nonce
new_nonce = NonceChange[-1][1] # the last new nonce value for the account

## Define new balance
post_balance = BalanceChange[-1][1] # the last new balance value for the account

## Define new storage root
new_storageRoot = keccak256(SlotChanges[-1]) # hash the last slot value change for the account, by accessed slot

## Define new code hash
new_codeHash = keccak256(CodeChange[-1][1]) # hash the last new code for the account

new_accountHash = keccak256(rlp.encode(new_nonce, post_balance, new_storageRoot, new_codeHash))

# Define block-level account hashes inside BAL

## AccountChanges: [address, storage_changes, storage_reads, balance_changes, nonce_changes, code_changes]
## All changes for a single account, grouped by field type
AccountChanges = [
    Address,                    # address
    old_accountHash,            # account hash prior to changes - New in bal-change-feature
    List[SlotChanges],          # storage_changes (slot -> [block_access_index -> new_value])
    List[StorageKey],           # storage_reads (read-only storage keys)
    List[BalanceChange],        # balance_changes ([block_access_index -> post_balance])
    List[NonceChange],          # nonce_changes ([block_access_index -> new_nonce])
    List[CodeChange],           # code_changes ([block_access_index -> new_code])
    new_accountHash             # account hash post changes - New in bal-change-feature
]

# BlockAccessList: List of AccountChanges containing pre/post account hash - Modiffied in bal-change-feature
BlockAccessList = List[AccountChange]