Notes about FIRST / FINAL

[OlivierBBB]

Modules cannot be live traced for the following reasons:

• popping transactions
• traces are only known at the end of a block / conflation

The general approach is to accumulate information (tracing a) and build the matrices later (tracing b).

HUB has another reason for not live tracing it:

• instruction handling depends on future events (rollbacks / REVERTs)
• e.g. account warmth
• when you touch an account it will become warm
• but if you REVERT the current excution this change in warmth will be undone
• many such things: balance, nonces, storage keys, wamrhts, deployment status / number, selfdestructs .... that may later be reverted

The HUB isn't the only one that is revert sensitive, MMU/MMIO is too because of LOGs. In any case, the approach with the HUB as we can't know while tracing (a) what rows (i.e. fragments) we will need, in what number and what actions they should represent is to just accumulate sections (collections of rows i.e. fragments) and resolve ambiguities when they have been lifted. We therefore accumulate dozens of tiny changes that have to be undone in case of a rollback or other events (context entry, exit, ...)

The case of rollbacks is particularly complex as a single REVERT / exception may trigger a chain reaction where we undo hundreds of small changes at once. Our solution is:

SOLUTION: WHENEVER WE DO SOMETHING THAT MAY BE SUBJECT TO BEING REVERTED (any state change, accrued state changes, ...) WE RESERVE THE POSSIBILITY OF MODIFYING THE RELEVANT SECTION IN SUCH A WAY THAT THE FUTURE UNDOING IS WRITTEN IN THE TRACE AT THE PRESENT TIME IN SUCH A WAY THAT IT WILL ONLY TAKE EFFECT IN THE FUTURE.

This is the reason for defers: when we detect that something WILL be reverted (say) then we retroactively insert the correct rows all the relevant trace sections taht would be affected by this rollback.

This has an effect on state management: if you say touch storage, and a parent context reverts, then there will be, for every time you touch storage in the normal execution flow, a corresponding "undoing row" that undoes everything that current row did. Only from the point of view of the scp_ permutation (storage conssistency permutation) this is a future event. And it may have to be tagged as "FINAL"

There are several Besu hooks that we use to "act upon" the defers:

• tracePreExecution (pre-opcode)
• tracePostExectution (post-opcode)
• traceContextEnter
• traceContextExit
• traceContextReEnter
• traceTxEnd
• traceConflationEnd

...

So ther are many registries for stuff that needs to be deferred
Each defer registry is "resolved" at one of those Besu hooks (if other conditions are met: e.g. REVERT)

E.g. you act on a RETURN;
you create a ReturnSection;
if the RETURN doesn't fail for exception or so it (the ReturnSection) may need to be amended at a future time given future evnets
so it schedules itself for the various future envent that may affect it

hub.defers()
  .scheduleForContextReEntry(
      this, hub.callStack().parent()); // post deployment account snapshot
hub.defers().scheduleForPostRollback(this, currentFrame); // undo deployment
hub.defers().scheduleForPostTransaction(this); // inserting the final context row;

Then if the relevant Besu hook activates we RESOLVE these events.

E.G. for storage rows, what is there to do ?

• storage rows will need to implement the "traceBlockEnd" and to have a scheduleForBlockEnd(...) "I may need to modify this storage row in the future" and a resolveAtBlockEnd(...) "this is how I will modify that row"
• a map that keeps track of the first and currently final time that you touch a storage key
  • gets updated every time you produce a new storage row, either organically (prewarmning related to transaction access list or because of SLOAD/SSTORE) or because of rollbacks
  • the 2nd one means that the map in question has to implement the schedulePostRollback(...) and resovlePostRollBack(...) so taht you don't "miss" any time the zkevm "touches" a storage key
• need to

For storage keys and accounts you'll have to do something similar to what is being done wrt SELFDESCTRUCT:

• you produce maps as you go
• at the end of the block you do some post processing of that map
• you deduce "fist occurrence time " /"final occurrence time"
• then you use it to define an associated bit of that AccountFragment / StorageFragment

isFirstAccountOccurrenceInBlock = (dom, sub) == (bla, bla)
isFinalAccountOccurrenceInBlock = (dom, sub) == (bla', bla')

Taking inspiration from, e.g. AccountFragment.java's

  @Override
  public void resolvePostTransaction(
      Hub hub, WorldView state, Transaction tx, boolean isSuccessful) {
    final Map<TransactionProcessingMetadata.EphemeralAccount, Integer> effectiveSelfDestructMap =
        transactionProcessingMetadata.getEffectiveSelfDestructMap();
    final TransactionProcessingMetadata.EphemeralAccount ephemeralAccount =
        new TransactionProcessingMetadata.EphemeralAccount(
            oldState.address(), oldState.deploymentNumber());
    if (effectiveSelfDestructMap.containsKey(ephemeralAccount)) {
      final int selfDestructTime = effectiveSelfDestructMap.get(ephemeralAccount);
      markedForSelfDestruct = hubStamp > selfDestructTime;
      markedForSelfDestructNew = hubStamp >= selfDestructTime;
    } else {
      markedForSelfDestruct = false;
      markedForSelfDestructNew = false;
    }
  }

Note: there is a preliminary "conflation level" version of this map in State.java:

// initialized here
public ArrayList<HashMap<StorageSlotIdentifier, StorageFragmentPair>>
firstAndLastStorageSlotOccurrences = new ArrayList<>();

The corresponding HashMap / Array, whatever, may have to be written for account data

Very similar for ACCOUNTs (just swap storage rows for account rows)

[bogdanbear]

Meeting notes 06.09

For storage: just the block level
storage: two level, transactions and the block
Dom, sub: dominant timestamp secondary timestamp

Ex Many events revert at timestamp t
All events encountered in the past: dominant timestamp will remain t
And the current one where we revert will be the secondary timestamp.

Secondary timestamp will have a smaller value.
The sub gets recorded in reverse order

first_in_Tx/last happen in the permuted domain
We can already do it in the unpermutted

Whenever we create an account fragment, we update the relevant map.

AccountSection is a section for an instruction in the AccountFamily (related to a specific family of opcodes—like BALANCE, SELFBALANACE…)
So we will work at AccountFragment
(
Map: <AccAddr, block>- > AccountSection
Add sections, they get populated afterwards
Disregard this for that reason)

Map -> Pair(AccountFragment, AccountFragment) // (First, Las, Dom, Subt)

(First, Last, Dom, Sub)

Ordered list of sections, and inside each section there is an ordered list of fragments.

(Dom, Sub) —— First/Last in Tx: start a new map with every transaction.
transactAccMap Map Pair(AccountFragment, AccountFragment) // (First, Last, Dom, Sub)
Every time we create an account fragment:

1. Is the address an existing key in the map, if no we add it to the map with first=last=currentAccountFragment, Dom, Sub= currentVals
2. If the address does exist in the map, retrieve its dom, sub (D, S) and lexicographically compare it to the new (D’, S’)
   If it is greater in the lexicographic ordering, we replace Last, D,S with Last, D’, S’ with Last= CurrentAccountFragment
   Condition: (D<D’) or [(D=D’) and (S>S’)]

Example given by Olivier on (Dom, Sub) on a call:
If you have for instance the following

transfer A -> B:
balA = b,  balAnew = b - v:  dom = tau * h + 0, sub = 0
balB = b', balBnew = b' + v: dom = tau * h + 1, sub = 0

undoing of this added in the resolvePostRollback:

balA = b - v,  balAnew = b:  dom = tau * rev_stamp + epsilon_rev, sub = tau * h + 0
balB = b' + v, balBnew = b': dom = tau * rev_stamp + epsilon_rev, sub = tau * h + 1

When you reorder it you will get

transfer A -> B:
balA = b,  balAnew = b - v:  dom = tau * h + 0, sub = 0
balB = b', balBnew = b' + v: dom = tau * h + 1, sub = 0
balB = b' + v, balBnew = b': dom = tau * rev_stamp + epsilon_rev, sub = tau * h + 1
balA = b - v,  balAnew = b:  dom = tau * rev_stamp + epsilon_rev, sub = tau * h + 0

Here tau is a fixed constant (I think it's actually 16 in the spec) and epsilon_rev also is a fixed constant. h represents the HUB_STAMP

In the permutation domain we order (Dom, Sub) according to the (+,-) lex ordering.

——————
We will modify the trace() of the AccountFragment class.
———
Using the tx level maps, we will reconstruct the block and conflation level ones.

For us:
Testing note: 2 smart contracts
1. One can only modify its own storage and has the option to revert
2. Second one can modify itself + do a call to the first one + option to revert itself.
3. Down the line, same as the second one + several calls to smart contracts that are carbon copies of the first (so that we have more than just two accounts) + self reverting. Note: in Solidity pass it as CallData.

These will be the base transactions, that get bundled into blocks—test inputs.

[OlivierBBB]

This issue is now solved in go-corset.