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:

$T x_{1} =$ {From: Alice, Balance:..., GasLimit:...}
$T x_{2} =$ {From: Bob, Balance:..., GasLimit:...}
$T x_{3} =$ {From: Charlie, Balance:..., GasLimit:...}

The three transactions are interdependent, and all three can only be included in the specific order:

T x 2 <= T x 3 <= T x 1

. A proposer would need to simulate all possible combinations, calculated as

1 C 3 + 2 C 3 * 2! + 3 C 3 * 3! = 15

, to find valid orderings. However, not all transactions need to be included, as some combinations may result in exclusion. For instance, if

T x 1

is selected first, it may not be possible to include

T x 2

and

T x 3

, as they would violate the interdependencies. The following three cases are considered acceptable:

$T x 2 <= T x 3 <= T x 1$ , where
$T x 2$ must come before Tx3, and both must be included before
$T x 1$ .
$T x 3 <= T x 1$ , where
$T x 3$ comes before
$T x 1$ .
$T x 1$ , where
$T x 1$ 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

d e l t a

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.

jacobkaufmann

2024/10/01 22:02:39

then tries to append the leftover IL transactions that are not included in the execution payload to the end of the payload

we may need to specify that the post-state needs to be reset after each attempt to append a transaction. for example, suppose we have 2 transactions in the IL. let S denote the post state after the executing the execution payload. let S1 denote the post state after appending the first transaction to the execution payload. then, if the first transaction succeeds, we need to reset to S before we try to execute the second transaction. we would not try to execute the second transaction on top of S1.

Thomas Thiery

2024/10/02 06:47:03

I agree, the state needs to reset to S every time you append a new txn

2024/10/01 22:03:14

would it be "O((x * n)!)" ?

2024/10/02 06:45:53

I think O(x×n!) was correct here, the complexity scales linearly with the number of IL committee members, but factorially with the number of transactions?

2024/10/02 16:06:32

actually, would it depend on the number of IL committee members at all? or would it just depend on the number of unique transactions in the union of all local ILs?

jihoonsong

2024/10/02 07:03:14

A proposer would need to simulate all possible combinations, which is , to find this order.

In this specific scenario, all possible combinations would be 1C3 + 2C3 * 2! + 3C3 * 3! = 3 + 6 + 6 = 15 and the following three cases are acceptable: 1) Tx2 <= Tx3 <= Tx1, 2) Tx3 <= Tx1, 3) Tx1. A builder can just ignore transactions if they are not includable e.g., if they pick Tx1 first, Tx2 and Tx3 are not gonna get included in the block and verifiers will accept this. The premise of this analysis that all Tx1, Tx2, Tx3 should be included doesn't seem to hold due to the first and third constraints. (Edited)

Julian Ma

2024/10/02 13:13:23

Yes, I agree here. The proposer does not need to do this work. It is also unclear whether we would want the proposer to do this work because it means that in exceptional cases, the protocol enforces an ordering rule. The protocol enforcing an ordering rule would be a huge deal, and I don't think we should try to go this way.

Terence Tsao

2024/10/02 14:11:04

I think the builder/proposer still need time to simulate this and it's not clear to me how long this would take

2024/10/02 19:03:20

My two cents is that ordering IL transactions boils down to making more profit so it's not going to be a problem. The trivial solution would be building a block without IL transactions first and then appending them one by one until you can't. This can be done in linear time and if a builder wants more sophisticated algorithm to earn more profit, which probably they will, it's where their expertise comes into play.