An overview of the cluster mempool proposal

An overview of the cluster mempool proposal

Original Postby sdaftuar

Posted on: February 22, 2024 10:31 UTC

The discussion focuses on the validation costs associated with Replace-By-Fee (RBF) transactions, highlighting the need to set limits to prevent these costs from becoming excessively high.

RBF transactions differ from non-RBF transactions in two main aspects. Firstly, they necessitate re-clustering and re-linearizing all clusters affected by evictions. Re-clustering is identified as an operation with a complexity of (O(n)) in relation to the number of transactions, while re-linearization has a complexity that can roughly be estimated as (O(n^2)) for the number of transactions within a single cluster. Secondly, validating RBF transactions involves comparing feerate diagrams of old and new clusters, an operation linear in the number of chunks within the two diagrams. The number of chunks is limited by the number of transactions in the clusters from which these diagrams are derived.

Current RBF rules, as outlined in BIP 125, restrict the total number of transactions that can be evicted by a single replacement to 100. This limitation suggests a potential strategy for managing validation costs in clustered mempools by capping the number of direct conflicts a single transaction can have at 100, and likewise limiting clusters to a maximum of 100 transactions. Such limitations would effectively control the extent of extra linearizations to 100 and reduce the size of a feerate diagram comparison to 10,000 entries. However, the effectiveness of these measures will become clearer with further benchmarking. Future adjustments may involve more precise calculations to determine the actual number of clusters being re-linearized and the number of entries in the feerate diagram, thereby setting bounds based on specific numbers to ensure the cost of validating a single transaction remains reasonable.