{{ message }}

Instantly share code, notes, and snippets.

Xekyo/Candidate-Set-based-Block-Building.md Secret

Last active Jun 14, 2021
Improvement on the current block building algorithm

Improvement on the current block building algorithm

Mark Erhardt¹, Clara Shikhelman²

Abstract

We suggest an improvement to the block building algorithm currently used by Bitcoin Core. Bitcoin Core uses a straightforward greedy approach which evaluates each transaction’s effective fee rate in the context of its unconfirmed ancestors. This overlooks situations in which multiple descendant transactions could be grouped with their shared ancestors to form a more attractive transaction set for block inclusion.

Basics

The effective fee rate of a set of transactions is the sum of their fees divided by the sum of their weights.
A transitive closure of a transaction is defined as the set of transactions it depends on. This includes the transaction itself and all other unconfirmed transactions that it depends on. Bitcoin Core also refers to these sets of transactions as ancestor sets. This concept can also be applied more generally to a set of transactions.
A strongly connected component of a directed graph is defined as a set of vertices that are connected to each other with a path (regardless of the direction of the edges). We call a maximal strongly connected component a cluster.
A candidate set is a set of transactions that is both transitively closed, and a strongly connected component.

Example: Graph on six vertices composed of two clusters marked as green circles

Example: Graph on four vertices with five candidate sets {{A}, {B}, {A,C}, {A,B,D}, {A,B,C,D}}. Note that {A,D} is not a candidate set, since it is not transitively closed (the unconfirmed parent transaction B is not included), and {A,B} is not a candidate set, since it is not strongly connected.

Current approach

The current approach uses a greedy algorithm, which calculates all ancestry sets across the present transactions and iteratively selects the ancestor set with the highest effective fee rate for the block. The selection concludes when the block is full and none of the available ancestry sets can fit, or no more transactions are available.

This approach enables block building to consider Child Pays For Parent (CPFP) constellations. We will refer to this algorithm as “Ancestor Set Based (ASB)” in the following.

Suggested algorithm

We note that Bitcoin Core’s current approach fails to consider constellations in which multiple transactions descend from a shared ancestry. We suggest an approach that discovers situations in which multiple Descendants Pay For Ancestors (DPFA).
We propose a greedy algorithm, which evaluates candidate sets instead of only ancestor sets. In detail, we find all clusters and identify the candidate set with the highest effective fee rate for each cluster. We call this candidate set a cluster’s champion. We select iteratively the best champion from all clusters and reprocess the remaining transactions of the affected cluster. This can be efficiently implemented using some optimizations such as lazily evaluating clusters to identify champions only when the highest feerate in a cluster is of interest. Further details can be found in our example implementation.

We will refer to our algorithm as “Candidate Set Based (CSB)” in the following.

Benefits of the Candidate Set Based approach (CSB)

Consider the following graph:

Applying ASB, the best ancestor set is {A,B,C}, which has an effective fee rate of 10. In CSB, we also consider the candidate set {A,B,C,D}, which has an effective fee rate of 11.

For a real-world example, one can consider a large brokerage which generally batches withdrawals into transactions with over 200 payments. Frequently, there are at least a handful of receivers that wish to spend the withdrawn funds immediately. Let’s assume that several of the unconfirmed outputs are spent in transactions using higher fee rates than the batched withdrawal. Under ASB, these CPFP transactions would compete for inclusion separately. Only when any one of the ancestry sets achieves a sufficient effective feerate, the parent gets included. Under CSB, the descendant transactions would act jointly to increase the priority of the parent transaction.
A miner using CSB benefits as well, as the resulting block could collect more transaction fees than a block built using ASB (see Simulation Results).

The advantage of miners using CSB would shrink as it gets more widely adopted, but any miners not using it would remain at a disadvantage and earn less transaction fees.

Drawbacks

CSB is more complex and requires more computation. From the point of view of global blockspace demand, if miners generally became DPFA-sensitive, it could encourage creation of additional transactions for the sole purpose of bumping stuck ancestors.

Simulation Results

We ran our algorithm on past data from December 2017 (peak of a feerate event), and May 2020 (variety of feerates). In both cases, CSB did better than the `getblocktemplate` results (which uses ASB). Note that at times of low blockspace demand either approach will simply collect all waiting transactions into the next block.

December 2017 May 2020
% of blocks CSB fee > ASB fee 99.7% 94.7%
# of blocks CSB with higher fee than ASB/
total # of blocks
5186/
5203
4100/
4328
Average (CSB block fee - ASB block fee) 890,595 sats 85,078 sats
Median (CSB block fee - ASB block fee) 85,768 sats 12,877 sats
Range (CSB block fee - ASB block fee) [-358,980 sats,
38,679,358 sats]
[-472,692 sats,
3,767,673 sats]
Average difference in % from ASB to CSB 0.25% 0.11%
Median difference in % from ASB to CSB 0.02% 0.015%
Range of difference in % from ASB to CSB [-0.18%,
6.56%]
[-0.41%,
5.86%]

Discussion

It is important to note that our simulation results overstate the increased revenue. As we simulate on the basis of mempool snapshots for each block, transactions could be reused in results for multiple subsequent blocks if they were not collected by the actual historical block.

All ancestor sets are also candidate sets. Our approach identifies the champion (the best candidate set) for each cluster. In cases where an ancestor set is the best option, we will identify it as the champion as well. Therefore, there are few cases in which ASB could outperform our result.
Upon inspection, the few cases in which ASB performed better were explained by local behavior in the tail composition of the block. Our algorithm still uses a greedy approach. Picking a better candidate set earlier in the block will shift other transactions in comparison to ASB. Occasionally, this will cause a transaction with a slightly lower feerate to be included when a more valuable transaction set does not have enough space to fit in the block.

A future improvement could be to optimize the tail end of the block. We have run some initial trials with Linear Programing solvers that showed slight improvements at the cost of significantly longer run times.