1# Mempool design and limits
2
3## Definitions
4
5We view the unconfirmed transactions in the mempool as a directed graph,
6with an edge from transaction B to transaction A if B spends an output created
7by A (i.e., B is a **child** of A, and A is a **parent** of B).
8
9A transaction's **ancestors** include, recursively, its parents, the parents of
10its parents, etc.  A transaction's **descendants** include, recursively, its
11children, the children of its children, etc.
12
13A **cluster** is a connected component of the graph, i.e., a set of
14transactions where each transaction is reachable from any other transaction in
15the set by following edges in either direction. The cluster corresponding to a
16given transaction consists of that transaction, its ancestors and descendants,
17and the ancestors and descendants of those transactions, and so on.
18
19Each cluster is **linearized**, or sorted, in a topologically valid order (i.e.,
20no transaction appears before any of its ancestors). Our goal is to construct a
21linearization where the highest feerate subset of a cluster appears first,
22followed by the next highest feerate subset of the remaining transactions, and
23so on[1]. We call these subsets **chunks**, and the chunks of a linearization
24have the property that they are always in monotonically decreasing feerate
25order.
26
27Given two or more linearized clusters, we can construct a linearization of the
28union by simply merge sorting the chunks of each cluster by feerate.
29
30For any set of linearized clusters, then, we can define the **feerate diagram**
31of the set by plotting the cumulative fee (y-axis) against the cumulative size
32(x-axis) as we progress from chunk to chunk. Given two linearizations for the
33same set of transactions, we can compare their feerate diagrams by
34comparing their cumulative fees at each size value. Two diagrams may be
35**incomparable** if neither contains the other (i.e., there exist size values at
36which each one has a greater cumulative fee than the other). Or, they may be
37**equivalent** if they have identical cumulative fees at every size value; or
38one may be **strictly better** than the other if they are comparable and there
39exists at least one size value for which the cumulative fee is strictly higher
40in one of them.
41
42For more background and rationale, see [2] and [3] below.
43
44## Mining/eviction
45
46As described above, the linearization of each cluster gives us a linearization
47of the entire mempool. We use this ordering for both block building and
48eviction, by selecting chunks at the front of the linearization when
49constructing a block template, and by evicting chunks from the back of the
50linearization when we need to free up space in the mempool.
51
52## Replace-by-fee
53
54Prior to the cluster mempool implementation, it was possible for replacements
55to be prevented even if they would make the mempool more profitable for miners,
56and it was possible for replacements to be permitted even if the newly accepted
57transaction was less desirable to miners than the transactions it was
58replacing. With the ability to construct linearizations of the mempool, we're
59now able to compare the feerate diagram of the mempool before and after a
60proposed replacement, and only accept the replacement if it makes the feerate
61diagram strictly better.
62
63In simple cases, the intuition is that a replacement should have a higher
64feerate and fee than the transaction(s) it replaces. But for more complex cases
65(where some transactions may have unconfirmed parents), there may not be a
66simple way to describe the fee that is needed to successfully replace a set of
67transactions, other than to say that the overall feerate diagram of the
68resulting mempool must improve somewhere and not be worse anywhere.
69
70## Mempool limits
71
72### Motivation
73
74Selecting chunks in decreasing feerate order when building a block template
75will be close to optimal when the maximum size of any chunk is small compared
76to the block size. And for mempool eviction, we don't wish to evict too much of
77the mempool at once when a single (potentially small) transaction arrives that
78takes us over our mempool size limit. For both of these reasons, it's desirable
79to limit the maximum size of a cluster and thereby limit the maximum size of
80any chunk (as a cluster may consist entirely of one chunk).
81
82The computation required to linearize a transaction grows (in polynomial time)
83with the number of transactions in a cluster, so limiting the number of
84transactions in a cluster is necessary to ensure that we're able to find good
85(ideally, optimal) linearizations in a reasonable amount of time.
86
87### Limits
88
89Transactions submitted to the mempool must not result in clusters that would
90exceed the cluster limits (64 transactions and 101 kvB total per cluster).
91
92## References/Notes
93[1] This is an instance of the maximal-ratio closure problem, which is closely
94related to the maximal-weight closure problem, as found in the field of mineral
95extraction for open pit mining.
96
97[2] See
98https://delvingbitcoin.org/t/an-overview-of-the-cluster-mempool-proposal/393
99for a high level overview of the cluster mempool implementation (PR#33629,
100since v31.0) and its design rationale.
101
102[3] See https://delvingbitcoin.org/t/mempool-incentive-compatibility/553 for an
103explanation of why and how we use feerate diagrams for mining, eviction, and
104evaluating transaction replacements.
105