How to linearize your cluster

Let B be the highest-feerate subset including inc, and excluding exc, ignoring topology. We’re trying to prove that pot = B.

B must have the property that for any t \in und it is the case that t \in B if and only if \operatorname{feerate}(t) > \operatorname{feerate}(B), for the simple reason that if it didn’t, and there was a t \not\in B with higher feerate than B, you could add it to B, and improve it further. Similarly, if there was a t \in B with lower feerate than B, it could be removed from it to improve it.

Furthermore, this property defines B, in the sense that there is only one subset (including inc and excluding exc) that satisfies that property. Imagine we had distinct B_1 and B_2 that both satisfy the property. Without loss of generality, assume that B_2 is the bigger one, so B_1 \subset B_2. The set of transactions t \in B_2 \setminus B_1 have \operatorname{feerate}(t) \leq B_1, otherwise they would be included in B_1. Thus, \operatorname{feerate}(B_2) \leq \operatorname{feerate}(B_1), because B_2 does include these transactions. But these transactions also have a \operatorname{feerate}(t) > \operatorname{feerate}(B_2) because of the property above, and thus also \operatorname{feerate}(t) > \operatorname{feerate}(B_1), so they should have been included in B_1, a contradiction.

Thus, if we can show that pot satisfies the property, it must be the case that pot = B.

We know that B must consist of inc plus some prefix of und (when considered in decreasing-feerate order), which matches how pot is constructed. And it must be the same, because if the last transaction had feerate \leq than pot's, it wouldn’t have been included. If the next not included transaction had feerate > than pot's, it would have been included.

1 Like