# Transaction invalidation complexity in FOCIL

*Thanks to Jacob, Jihoon, Thomas and Julian for the feedback*

This post documents transaction invalidation scenarios in FOCIL and raises questions on how they may impact block producers or verifiers.

Prerequisite reading: https://ethresear.ch/t/focil-cl-el-workflow/20526

## Block producer

Block producer receives a list of txs to be included for its execution payload. Here is a given constraint:
- Block producer can include txs in the block in any ordering
- Block producer must include txs as long as the block is not full
- Block producer must include txs if it can be executed at the end of the block

Now assume the following transactions:
1. $Tx_1=$`{From: Alice, Balance:..., GasLimit:...}`
2. $Tx_2=$`{From: Bob, Balance:..., GasLimit:...}`
3. $Tx_3=$`{From: Charlie, Balance:..., GasLimit:...}`

The three transactions are interdependent, and all three can only be included in the specific order: $Tx2 <= Tx3 <= Tx1$. A proposer would need to simulate all possible combinations, calculated as $1C3 + 2C3 * 2! + 3C3 * 3! = 15$, to find valid orderings. However, not all transactions need to be included, as some combinations may result in exclusion. For instance, if $Tx1$ is selected first, it may not be possible to include $Tx2$ and $Tx3$, as they would violate the interdependencies. The following three cases are considered acceptable:

- $Tx2 <= Tx3 <= Tx1$, where $Tx2$ must come before Tx3, and both must be included before $Tx1$.
- $Tx3 <= Tx1$, where $Tx3$ comes before $Tx1$.
- $Tx1$, where $Tx1$ alone is valid.

This complexity arises because the proposer must explore all these cases while deciding whether to include or exclude transactions based on their dependencies. As a result, the proposer faces an $O(2^n)$ complexity in the worst case, where n represents the number of transactions. This exponential complexity stems from the need to evaluate all subsets of transactions while ensuring that each chosen subset respects the constraints between them.

In the latest FOCIL light design, with $delta$ set to $0$, any member of the IL committee could trigger this worst-case scenario of $O(n!)$. If the IL committee consists of $x$ members, the absolute worst-case complexity becomes $O(x * n!)$.

## Block verifier

Block verifier first verifies that the execution payload is valid, then tries to append the leftover IL transactions that are not included in the execution payload to the end of the payload with the same post state after executing the execution payload. If any of the remaining transactions that are not in the payload can be appended to the end of the block, then the block cannot be attested to the head. The complexity here is $O(n)$ as it scales with the number of leftover IL transactions.