# EIP- 7748 Tests (Tree conversion)
*Note: if you spot any missing case, feel free to get in touch!*

This document describes at a high-level test scenarios for [EIP-7748](https://eips.ethereum.org/EIPS/eip-7748) ([overview of the EIP](https://stateless.fyi/state-conversion/eip-7748.html)).

The following are main drivers for potential bugs:
- The `stride` allows account partial-migrations i.e., an account is not fully migrated in a single block, so proper resuming of an account migration in multiple blocks should be done.
- The MPT key values might be stale since previously executed txs i.e., MPT values are stale and must not be moved.
- The block where an MPT key is moved can have also a tx that writes the state (i.e., both in the _same_ block). Tx revertions in this scenario add a further dimension to cover.
- EIP-161 accounts are not migrated, thus must not count to the `stride` quota.
- Chain reorgs will make tree conversion have "back-and-forth" scenarios that must be covered.
- Tx execution can access partially migrated accounts (i.e., not fully converted in the new tree).

Note that this document describes the test cases at a medium-level of detail to not miss important things that can go wrong. The implemented fixtures might cover more ground than described here.

## Big picture plan

Rough suggestion on a plan:
1. Build & run `execution-spec-test` tests described in this document. Allows to create fine-grained corner cases, fast to run, doesn't require coordination between EL clients or infra support.
2. Run a devnet with a much bigger MPT as genesis data:
a. Phase 1: create random synthetic data
b. Phase 2: copy existing data from testnets
c. Phase 3: copy mainnet data (or randomly sampled set)
3. Shadow fork existing testnets.
4. Shadow fork mainnet.

The above is just an idea. If after 1. EL clients feel confident, we jump directly to 4.

## Progress status

:heavy_check_mark: - Implemented test.
:hammer_and_wrench: - Pending to implement
:construction: - Requires testing-framework changes.

## Terminology

To describe the test vectors, we use the following terminology:

- *First-conversion block (FCB)*: first block in the conversion process i.e., fork activation block.
- *Mid-conversion block (MCB)*: a block in the middle of the conversion process. i.e., a subsequent block will continue the conversion from where it was left.
- *Last-conversion block (LCB)*: the last block that would finish the conversion.
- *EIP161Account:* an account that EIP-161 would delete. i.e., not migrated during the conversion.

*FCB* test cases are relevant since the EL client might have uninitialized/empty internal variables that track the conversion process. *MCB* are more common since most of converting blocks are *MCB*s. *LCB* situations are special since in this block the conversion process stops (e.g., what if the last account is an *EIP161Account*).

## Test-vectors

Here are high-level descriptions of all the cases. We might refer to block *XCB* in them, meaning we should run each case with *XCB* as the *FCB* or *MCB*. The required *stride* is implicit under the test-case description.

### Non-partial account conversion

Given an XCB block, run the following scenarios which convert all mentioned accounts *fully* in the block:
- :heavy_check_mark: `[EOA]`
- :heavy_check_mark: `[Contract]`
- :heavy_check_mark: `[EOA, EOA]`
- :heavy_check_mark: `[EOA, Contract]`
- :heavy_check_mark:`[Contract, EOA]`
- :heavy_check_mark:`[Contract, Contract]`

### Partial account conversion

These test cases cover situations in which at least one account in a XCB block is partially converted:
- :heavy_check_mark: `[Contract]` where finishes two storage slots before the last one.
- :heavy_check_mark: `[Contract]` where finishes one storage slot before the last one.
- :heavy_check_mark: `[Contract]` where finishes exactly at the last storage slot (i.e., perfect fit before account data conversion).
- :heavy_check_mark: All three cases above, but with a prefixed EOA or a separate Contract i.e., `[(EOA | Contract_A), Contract_B]`.

The cases above press on the fact that the conversion for an account needs to walk the account and storage tries. The boundary where the "partial conversion" happens is the main focus of these tests.

### Code-chunk stride correct accounting

These test cover if implementations do proper accounting of code-chunks stride overflow:
- :heavy_check_mark: `[Contract]` with number of chunks bigger than stride, must be converted in a single block.
- :heavy_check_mark: `[Contract, EOA]` where the contract #code-chunks is bigger than the stride. `Contract` is fully migrated in the block, and `EOA` must be converted in the next block.

The EIP tries to push hard on simplifying code-chunk migration, and always do it in one go. See this [EIP rationale for more details](https://eips.ethereum.org/EIPS/eip-7748#account-code-chunking-done-in-a-single-step).

### Special accounts

In an XCB block:
- An account with non-empty storage slots and empty code
- :heavy_check_mark: Conversion done in a single block.
- :heavy_check_mark: Conversion spanning more than one block.
- Upcoming `[EIP161Account, EOA]`:
- :construction: Run with `stride=1`, must skip `EIP161Account` and migrate `EOA` in this block.

### Conversion ending

These test cases cover special situations that can happen in the last block that migrates state:
- :heavy_check_mark: LCB that migrates less than *stride* conversion units finishing the conversion.
- :heavy_check_mark: LCB that migrates exactly *stride* conversion units finishing the conversion, i.e., perfect *stride* fit in the last block.
- :hammer_and_wrench: LCB with remaining account being only an *EIP161Account*. i.e: LCB doesn’t actually migrate anything, finishing the conversion.

### Modified accounts

When an account is converted it could have been modified since previously executed txs forced writes for the account in the new tree.

- EOAs
- :heavy_check_mark: Previous tx updated balance/nonce.
- Contracts
- :heavy_check_mark: Previous tx writes only modified balance/nonce but no storage-slots.
- Previous tx writes to a storage-slot **not present** in the MPT.
- :heavy_check_mark: Storage slot in the account header.
- :heavy_check_mark: Storage slot outside the account header.
- Previous tx writes to a storage-slot **present** in the MPT.
- :heavy_check_mark: Storage slot in the account header.
- :heavy_check_mark: Storage slot outside the account header.
- :heavy_check_mark: Previous two bullets but with also modified balance/nonce.
- Conversion units accounting (stale values count as consumed conversion units)
- :heavy_check_mark: `[stale EOA]**stride ++ [EOA]` should span two blocks
- :heavy_check_mark: Contract with _stride_ stale storage-slots should span two blocks

Note that the contract code can’t become stale.

### Block txs execution writes overlap with conversion units

There is a situation where a key that is converted in a block, also matches with a transaction **in that same block** which writes to the same key.

This is a special case of the section above, but with the tx exactly matching the block where the key is converted. Both writes happen in the same block, and it is useful to test that EL clients _pending writes_ to be flushed at the end of the block are handeled properly.

Test cases:
- :heavy_check_mark: Tx writes the balance/nonce of an account converted in the same block.
- :heavy_check_mark: Tx writes to a storage slot converted in the same block.
- :heavy_check_mark: Both cases above, but with the tx reverting.

### Access partially converted contracts

An EOA can't be partially converted since it spans a single conversion unit. A contract can be in the following partially converted under the following matrix of combinations:
- Basic data (balance/nonce/etc)
- **BD1**: Not converted.
- **BD2**: Converted
- By previously executed value bearing tx.
- Or, indirectly by previous non-value bearing tx which wrote in some storage slot.
- Storage slots
- **SS1**: No storage slot was converted.
- Located in account header
- **SS2**: Non-MPT storage slot write by previously executed tx.
- **SS3**: MPT storage slot write by previously executed tx.
- **SS4**: MPT storage slot by the conversion process.
- Located outside account header
- **SS5**: Non-MPT storage slot write by previously executed tx.
- **SS6**: MPT storage slot write by previously executed tx.
- **SS7**: MPT storage slot by the conversion process.

Not all combinations of `BD*` and `SS*` correspond to this EIP-7748 testing scope:
- Already covered:
- BD1+SS1: this a case covered in the _Non-partial account conversion_ section.
- Combinations that can't happen in mainnet:
- BD1+SS(2|3|4|5|6|7): the only way to generate a `SS*` case is by by sending a tx to the contract, which means violating the BD1 constraint.
- Combinations that do not correspond to testing this EIP but EIP-7612:
- BD2+SS2
- BD2+SS3
- BD2+SS5
- BD2+SS6

This means that, for each of the following setup combinations, execute a tx which access converted & unconverted state for the contract, to verify it isn't read "from the wrong tree":
- :hammer_and_wrench: BD2+SS4
- :hammer_and_wrench: BD2+SS7

### Reorgs (:construction:)
_**Important**: Test that produce reorgs aren't currently supported without hive. The testing team is planning to add support in the near term._

The tree conversion logic should be reorg aware as any other logic within a block execution. Note that since the tree conversion keys to be migrated in a block are deterministic, a rollback will do the tree conversion for the same set of keys that was already done. The main difference is that the txs in these new blcoks might cause a different interference i.e., converted keys being stale.

To cover these situations we can run all test-vectors from _Partial account migration_ section with a reorg happening in the process. More concretely:
- Let's imagine one of those test-vectors spans 2 blocks (Block _X_ and _X+1_).
- Apart from running that base case, we should also configure one extra reorg per block:
- Reorg _X_: after block _X_ is executed, pipe new blocks _X'_ and _X'+1_ which would reorg _X_.
- Reorg _X+1_: after block _X+1_ is executed, pipe a block _X'+1_ which reorgs _X+1_.
- _X'_ and _X'+1_ are just reorged blocks with same block numbers of _X_ and _X+1_ respectively.
- _X'_ and _X'+1_ must contain at least some extra tx that will make the state root different from the reorged _X_ and _X'+1_.

Usually the test-vectors spans 2 blocks since they're trying to cover very specific scenarios, so the _blow up_ factor wouldn't be that much. Also, we don't necessarly need to do this for all tests since we're interested in covering the rewind of internal variables that track the conversion process -- but the reorg setup could be generic enough to make it easy to cover all of them if found useful.