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 (overview of the EIP).

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

- Implemented test.
- Pending to implement
- 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 MCBs. 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:

• [EOA]
• [Contract]
• [EOA, EOA]
• [EOA, Contract]
• [Contract, EOA]
• [Contract, Contract]

Partial account conversion

These test cases cover situations in which at least one account in a XCB block is partially converted:

• [Contract] where finishes two storage slots before the last one.
• [Contract] where finishes one storage slot before the last one.
• [Contract] where finishes exactly at the last storage slot (i.e., perfect fit before account data conversion).
• 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:

• [Contract] with number of chunks bigger than stride, must be converted in a single block.
• [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.

Special accounts

In an XCB block:

• An account with non-empty storage slots and empty code
  • Conversion done in a single block.
  • Conversion spanning more than one block.
• Upcoming [EIP161Account, EOA]:
  • 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:

• LCB that migrates less than stride conversion units finishing the conversion.
• LCB that migrates exactly stride conversion units finishing the conversion, i.e., perfect stride fit in the last block.
• 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
  • Previous tx updated balance/nonce.
• Contracts
  • Previous tx writes only modified balance/nonce but no storage-slots.
  • Previous tx writes to a storage-slot not present in the MPT.
    • Storage slot in the account header.
    • Storage slot outside the account header.
  • Previous tx writes to a storage-slot present in the MPT.
    • Storage slot in the account header.
    • Storage slot outside the account header.
  • Previous two bullets but with also modified balance/nonce.
• Conversion units accounting (stale values count as consumed conversion units)
  • [stale EOA]**stride ++ [EOA] should span two blocks
  • 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:

• XCB and LCB, where a block tx writes the balance/nonce of an account converted in this block.
• XCB and LCB, where a block tx writes to a storage slot converted in this block.
• Both cases above, but with the tx failing/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 SS1 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":

• BD2+SS4
• BD2+SS7

Reorgs ()

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.