HackMD******# 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.
- 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
- 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
- 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.
- \(tx_{S,\max}\): The most profitable transaction in \(S\)
- \(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.
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_feefee_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);
}
}
