******# EIP-1559 Transaction Pool for Fast Sorting

TL;DL

• The idea of an EIP-1559 transaction pool for fast sorting.
• Computational complexity
  • Add a transaction in
    $O(\log n)$
  • Sort transactions when basefee changes in
    $O(k\log n)$
  • Pop the most profitable transaction in
    $O(\log n)$
  • Produce a block in
    $O(m\log n)$
  • $n$: The number of transactions in a txpool
  • $k$: The number of transactions where the miner bribe varies with basefee
  • $m$: The number of transactions in a block
• Implementation: https://github.com/minaminao/eip1559txpool

Background

Transaction Pool in First-price Auction

In the current fee market, which is a first-price auction mechanism, one strategy to optimize the miner's fee revenue is to put transactions into a block in a gas_price order.

NOTE: Strictly speaking, although nonce also needs to be considered, it is not be considered in the following sections because it does not affect the computational complexity.

Vector Implementation

If a txpool is implemented as a vector, it must be sorted in gas_price order before creating a block. The computational complexity of sorting is

$O(n\log n)$, that of adding a transaction is

$O(1)$, and that of deleting a transaction is

$O(n)$. However, transaction deletion can be done to

$O(1)$ by lazy evaluation.

Heap Implementation

If a txpool is implemented as a heap, there will be no need to sort. Adding a transaction takes

$O(\log n)$, and deleting a transaction takes

$O(n\log n)$. However, transaction deletion can be done to

$O(\log n)$ by lazy evaluation.

Self-balancing Binary Search Tree (SBST) Implementation

If a txpool is implemented as an SBST, there will be no need to sort as well as a heap implementation. Adding a transaction takes

$O(\log n)$, and deleting a transaction takes

$O(\log n)$.

Summary of Computational Complexity in First-price Auction

Operation	Vector	Heap	SBST
Add a transaction	$O(1)$	$O(\log n)$	$O(\log n)$
Delete a transaction	$O(1)$ by lazy evalutaion	$O(\log n)$ by lazy evalutaion	$O(\log n)$
Pop the most profitable transaction	$O(1)$ after sorting	$O(\log n)$	$O(\log n)$
Sort transactions	$O(n\log n)$	-	-

The space complexity is

$O(n)$.

Transaction Pool in EIP-1559

An EIP-1559 transaction has the parameters base_fee and fee_cap. The miner_bribe is min(fee_cap - base_fee, max_miner_bribe), and it is optimal to put transactions into a block in the order of miner_bribe.
However, miner_bribe depends on base_fee. A fast transaction pool is non-trivial.

According to https://hackmd.io/@adietrichs/1559-transaction-sorting , when base_fee changes, there are two transaction sets: one in which miner_bribe changes and one in which miner_bribe does not change. Let us denote these sets as

$D$ and

$S$, respectively. It is known that the order of transactions belonging to

$D$ and that to

$S$ does not change before and after the base_fee change.

By using this property well, an efficient transaction pool can be constructed.

Proposed Txpool

Architecture

The txpool is consists of three SBSTs.

1. Static state transactions SBST (sbst_static)
   • Include all
     $S$ transactions.
   • Include condition: fee_cap - max_miner_bribe >= base_fee
   • Key: (max_miner_bribe, transaction_hash)
   • Value: transaction
2. Dynamic state transactions SBST (sbst_dynamic)
   • Include all
     $D$ transactions.
   • Include condition: fee_cap - max_miner_bribe < base_fee
   • Key: (fee_cap, transaction_hash)
   • Value: transaction
3. State decision SBST (sbst_decision)
   • Include all transactions.
   • Key: fee_cap - max_miner_bribe
   • Value: transaction

NOTE: I have included the implementations below, but they are implemented in C++ because Python does not have SBST in the standard library. Other language implementations such as Python and Rust are WIP.

Computational Complexity of Proposed Txpool

|Operation|Vector|SBST (Proposed)|
|-|-|-|-|
|Add a transaction|

$O(1)$|

$O(\log n)$|
|Delete a transaction|

$O(1)$ by lazy evalutaion|

$O(\log n)$|
|Pop the most profitable transaction|

$O(1)$ after sorting|

$O(\log n)$|
|Sort transactions when basefee changes |

$O(n\log n)$|

$O(k\log n)$|

The space complexity is

$O(n)$.

Pop The Most Profitable Transaction:

$O(\log n)$

The most profitable transaction is either of the following two.

1. $t{x}_{S,max}$: The most profitable transaction in
   $S$
2. $t{x}_{D,max}$: The most profitable transaction in
   $D$

$t{x}_{S,max}$ is the one with the highest max_miner_bribe in

$S$. sbst_static is sorted in order of max_miner_bribe because its key is (max_miner_bribe, transaction_hash). Hence, finding and deleting

$t{x}_{S,max}$ is possible with

$O(\log n)$ due to the property of SBST.

$t{x}_{D,max}$ is the one with the highest fee_cap in

$D$. sbst_dynamic is sorted in order of fee_cap because its key is (fee_cap, transaction_hash). Hence, finding and deleting

$t{x}_{D,max}$ is possible with

$O(\log n)$ due to the property of SBST.

By comparing the revenue of

$t{x}_{S,max}$ and

$t{x}_{D,max}$, we can select the most profitable transaction out of the entire transaction set.

Also, we have to delete the transaction from sbst_decision (explained later) in

$O(\log n)$.

Therefore, the overall computational complexity is

$O(\log n)$.

Implementation
I left it out of the explanation, but I inserted a -fee_cap between the first and second elements of the key. The reason is that when there are transactions with the same max_miner_bribe, it is better to take the one with the smaller fee_cap. When the next base_fee is high, transactions with a small fee_cap may have a smaller revenue.

Tx pop_most_profitable_tx() {
    Tx tx;
    assert(sbst_decision.size() > 0);
    if(sbst_static.size() == 0) {
        tx = sbst_dynamic.rbegin()->second;
        sbst_dynamic.erase(prev(sbst_dynamic.end()));
    } else if(sbst_dynamic.size() == 0) {
        tx = sbst_static.rbegin()->second;
        sbst_static.erase(prev(sbst_static.end()));
    } else {
        Tx tx_static = sbst_static.rbegin()->second;
        Tx tx_dynamic = sbst_dynamic.rbegin()->second;

        if(tx_static.miner_bribe(base_fee) >
            tx_dynamic.miner_bribe(base_fee)) {
            tx = tx_static;
            sbst_static.erase(prev(sbst_static.end()));
        } else {
            tx = tx_dynamic;
            sbst_dynamic.erase(prev(sbst_dynamic.end()));
        }
    }

    sbst_decision.erase(sbst_decision.find(
        Key(tx.fee_cap - tx.max_miner_bribe, -tx.fee_cap, tx.hash)));
    return tx;
}

Produce Block:

$O(m\log n)$

Suppose we select the

$m$ most profitable transactions to create a block. Since selecting the most profitable transaction runs in

$O(\log n)$, the block production runs in

$O(m\log n)$.

Add Transaction:

$O(\log n)$

If fee_cap - base_fee >= max_miner_bribe, we add the transaction to sbst_static in

$O(\log n)$.
If fee_cap - base_fee < max_miner_bribe, we add the transaction to sbst_dynamic in

$O(\log n)$.

It is also added to sbst_decision (explained later) in

$O(\log n)$.

Therefore, the overall computational complexity is

$O(\log n)$.

Implementation

void add_tx(Tx tx) {
    if(tx.fee_cap - base_fee >= tx.max_miner_bribe) {
        sbst_static.emplace(Key(tx.max_miner_bribe, -tx.fee_cap, tx.hash),
                            tx);
    } else {
        sbst_dynamic.emplace(Key(tx.fee_cap, -tx.fee_cap, tx.hash), tx);
    }
    sbst_decision.emplace(
        Key(tx.fee_cap - tx.max_miner_bribe, -tx.fee_cap, tx.hash), tx);
}

Sort Transactions When Basefee Changes:

$O(k\log n)$

When the base_fee changes, do the following.
Let us denote the previous basefee by prev_base_fee.

If prev_base_fee < base_fee

We need to move the transaction that moves from

$S$ to

$D$ from sbst_static to sbst_dynamic.

The conditions of the transactions are as follows.

• fee_cap - max_miner_bribe >= prev_base_fee
• fee_cap - max_miner_bribe < base_fee

To check the conditions, sbst_decision is used. The key of sbst_decision is fee_cap - max_miner_bribe. Thus, by performing a binary search by prev_base_fee and then by base_fee, the transaction set to be moved can be determined in

$O(\log n)$.

The move takes

$O(\log n)$ to delete a transaction from sbst_static and add the transaction to sbst_dynamic.

If the number of its moving transactions is

$k$, then the total complexity is

$O(k\log n)$. k is small if the change of basefee is small.

Implementation

auto left_tx =
    sbst_decision.lower_bound(Key(prev_base_fee, -INT32_MAX, 0));
auto right_tx =
    sbst_decision.lower_bound(Key(base_fee, -INT32_MAX, 0));
for(auto pointer = left_tx; pointer != right_tx; pointer++) {
    Tx tx = pointer->second;
    if(tx.fee_cap - tx.max_miner_bribe >= prev_base_fee) {
        sbst_static.erase(sbst_static.find(
            Key(tx.max_miner_bribe, -tx.fee_cap, tx.hash)));
        add_tx(tx);
    }
}

If base_fee < prev_base_fee

We need to move the transaction that moves from

$D$ to

$S$ from sbst_dynamic to sbst_static. The computational complexity is

$O(k\log n)$ as above.

Implementation

auto left_tx =
    sbst_decision.lower_bound(Key(base_fee, -INT32_MAX, 0));
auto right_tx =
    sbst_decision.lower_bound(Key(prev_base_fee, -INT32_MAX, 0));
for(auto pointer = left_tx; pointer != right_tx; pointer++) {
    Tx tx = pointer->second;
    if(tx.fee_cap - tx.max_miner_bribe < prev_base_fee) {
        sbst_dynamic.erase(sbst_dynamic.find(
            Key(tx.fee_cap, -tx.fee_cap, tx.hash)));
        add_tx(tx);
    }
}

References

• https://hackmd.io/@timbeiko/1559-tx-pool-mgmt