# How to Implement FOCIL in the EL

This article covers the changes that FOCIL would introduce to the EL. Additionally, it examines the compatibility between FOCIL and BALs, as the EL client teams primarily support BALs as the EL headliner for Glamsterdam. It concludes with the author sharing the experience of developing FOCIL in Geth.

FOCIL adds or modifies three engine APIs. The following sections examine each API individually, describing the changes and example implementations.

## New `GetInclusionList`

The CL calls the [`GetInclusionList` engine API](https://github.com/jihoonsong/execution-apis/blob/1c22e31fb7ffab128e48ba2b0b6da9d469382bbe/src/engine/experimental/eip7805.md#engine_getinclusionlistv1) to retrieve an inclusion list (IL). An honest validator constructs an IL using transactions from the public mempool.

The input is `parentHash`, upon which the returned IL should be built, and the output is a list of transactions. Although it’s recommended to build the IL based on the head to produce the freshest IL, this is not strictly required. In this regard, it may later change to receive no parameter.

Furthermore, the EL may or may not execute transactions during the IL building process. The [Geth prototype currently executes IL transactions against the `parentHash`](https://github.com/jihoonsong/go-ethereum/blob/focil/miner/inclusion_list_building.go#L16). However, the EL may choose to include transactions in the IL without executing them.

## Modified `NewPayload`

When attesters call [`NewPayload` engine API](https://github.com/jihoonsong/execution-apis/blob/1c22e31fb7ffab128e48ba2b0b6da9d469382bbe/src/engine/experimental/eip7805.md#engine_newpayloadv5), they now pass a unique set of IL transactions to validate the IL constraints. Using the post-execution state, the EL examines each IL transaction not present in the payload according to the following criteria:

- The transaction is intrinsically valid.
- There is sufficient gas available to include the transaction.
- The transaction has correct nonce with respect to the transaction sender.
- The transaction sender can afford the transaction.

If all of these conditions hold for any missing IL transaction, the EL responds that the payload fails to meet the IL constraints.

Here is the execution spec that specifies the [validation logic](https://github.com/jihoonsong/execution-specs/blob/8da74852cfeec95daeef00f94d75fba492b6668e/src/ethereum/osaka/fork.py#L1075) and [where it should be invoked](https://github.com/jihoonsong/execution-specs/blob/8da74852cfeec95daeef00f94d75fba492b6668e/src/ethereum/osaka/fork.py#L782-L787).

def state_transition(
    chain: BlockChain,
    block: Block,
    inclusion_list_transactions: Tuple[LegacyTransaction | Bytes, ...],
) -> None:
    ...
    
    for i, tx in enumerate(map(decode_transaction, transactions)):
        process_transaction(block_env, block_output, tx, Uint(i))

    validate_inclusion_list_transactions(
        block_env=block_env,
        block_output=block_output,
        transactions=transactions,
        inclusion_list_transactions=inclusion_list_transactions,
    )

    process_withdrawals(block_env, block_output, withdrawals)
    
    ...


def validate_inclusion_list_transactions(
    block_env: vm.BlockEnvironment,
    block_output: vm.BlockOutput,
    transactions: Tuple[LegacyTransaction | Bytes, ...],
    inclusion_list_transactions: Tuple[LegacyTransaction | Bytes, ...],
) -> None:
    for inclusion_list_transaction in inclusion_list_transactions:
        # Skip if an inclusion list transaction is present in the block.
        if inclusion_list_transaction in transactions:
            continue

        tx = decode_transaction(inclusion_list_transaction)

        # Ignore blob transactions.
        if isinstance(tx, BlobTransaction):
            continue

        try:
            # Run the tests of intrinsic validity.
            validate_transaction(tx)
            check_transaction(block_env, block_output, tx)
        except EthereumException:
            # This inclusion list transaction could not be included.
            continue
        else:
            # This inclusion list transaction could have been included.
            # Mark the block as not satisfying inclusion list constraints.
            block_output.is_inclusion_list_satisfied = False
            break

Here is the prototype code that [tests intrinsic validities](https://github.com/jihoonsong/go-ethereum/blob/6126686891e3fc95e665c806f7d3a8044f794cdc/eth/catalyst/api.go#L1088),
[checks if it could have been included](https://github.com/jihoonsong/go-ethereum/blob/6126686891e3fc95e665c806f7d3a8044f794cdc/core/state_processor.go#L321) and [calls it](https://github.com/jihoonsong/go-ethereum/blob/6126686891e3fc95e665c806f7d3a8044f794cdc/core/state_processor.go#L108).

func ValidateInclusionListTransactions(evm *vm.EVM, block *types.Block, statedb *state.StateDB, inclusionListTxs []*types.Transaction) bool {
	// Create a map of transaction hashes present in the block.
	isIncludedTx := make(map[common.Hash]bool)
	for _, tx := range block.Transactions() {
		isIncludedTx[tx.Hash()] = true
	}

	// Get the block's gas limit and gas left.
	gasLimit := block.GasLimit()
	gasLeft := gasLimit - block.GasUsed()

	// Make a singer to get transaction senders.
	signer := types.MakeSigner(evm.ChainConfig(), block.Number(), block.Time())

	// Iterate over each transaction in the inclusion list and check if it is either included in the block or cannot be placed at the end of the block.
	for _, tx := range inclusionListTxs {
		// Check if the transaction is included in the block.
		if isIncludedTx[tx.Hash()] {
			continue
		}

		// Check if there is not enough gas left to execute the transaction.
		if tx.Gas() > gasLeft {
			continue
		}

		// Get the transaction sender.
		from, err := types.Sender(signer, tx)
		if err != nil {
			continue
		}

		// Check if the sender has not enough balance to cover the transaction cost.
		balance := statedb.GetBalance(from).ToBig()
		cost := tx.Cost()
		if balance.Cmp(cost) < 0 {
			continue
		}

		// Check if the sender has a nonce that doesn't match with the transaction nonce.
		nonce := statedb.GetNonce(from)
		if nonce != tx.Nonce() {
			continue
		}

		// This transaction could have been appended at the end of the block. The block fails to satisfy the inclusion list constraints.
		return false
	}

	return true
}

## Modified `ForkchoiceUpdated`

When calling [`ForkchoiceUpdated` engine API](https://github.com/jihoonsong/execution-apis/blob/1c22e31fb7ffab128e48ba2b0b6da9d469382bbe/src/engine/experimental/eip7805.md#engine_updatepayloadwithinclusionlistv1), builders can pass IL transactions to make sure their payload is IL compliant. It receives `payloadId` and IL transactions, and newly builds or updates the payload so that it satisfies the IL constraints with respect to the IL transactions.

Previously, `UpdatePayloadWithInclusionList` was used but has been replaced with `ForkchoiceUpdated` because the IL is now part of the payload building process and hence `ForkchoiceUpdated` is semantically more appropriate.

## FOCIL and BALs

FOCIL and BALs can be implemented independently. The EL can invoke the IL validation logic after executing transactions in parallel using BALs. For example, in the BALs prototype in Geth, the IL validation logic could be invoked at [this point](https://github.com/jwasinger/go-ethereum/blob/98becd7c575c9726009448db5b25a1587be4de52/core/state_processor.go#L217).

Furthermore, the IL validation logic can be executed in parallel, which is in line with BALs’ optimization. Each IL transaction takes the same inputs (block environment and post-execution state) and produces the same output type (boolean).

## Closing Remarks

The [Geth prototype](https://github.com/ethereum/go-ethereum/pull/30914) took approximately three weeks in total for the PR author to implement and refine. It is expected that the EL would remain agnostic as to whether FOCIL is introduced together with ePBS or not.

When it comes to testing complexity, it would be more appropriate to consider both the CL and the EL. We are currently in contact with testing teams and the upcoming writeup will address this topic.

[*Next: How to Implement FOCIL in the CL*](https://hackmd.io/@jihoonsong/rJX-fxADxl)

## Links
* [EIP-7805](https://eips.ethereum.org/EIPS/eip-7805)
* [Execution Specs](https://github.com/ethereum/execution-specs/pull/1349)
* [Execution APIs](https://github.com/ethereum/execution-apis/pull/609)
* [Geth Prototype](https://github.com/ethereum/go-ethereum/pull/30914)
* [A One-pager for Implementors](https://github.com/jihoonsong/focil-for-implementors/wiki/FOCIL-for-Implementors)