# ******# 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](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree), 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. $tx_{S,\max}$: The most profitable transaction in $S$
2. $tx_{D,\max}$: The most profitable transaction in $D$
$tx_{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 $tx_{S,\max}$ is possible with $O(\log n)$ due to the property of SBST.
$tx_{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 $tx_{D,\max}$ is possible with $O(\log n)$ due to the property of SBST.
By comparing the revenue of $tx_{S,\max}$ and $tx_{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.
```cpp
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**
```cpp
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**
```cpp
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**
```cpp
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