# Cluster mempool definitions & theory

**URL:** <https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool\
**Created:** [November 17, 2023, 2:40am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202 "2023-11-17T02:40:41Z")\
**Posts on this page:** 1\
**Showing post:** 6

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [December 11, 2023, 1:16am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/6 "2023-12-11T01:16:32Z")

</div>

> [@sipa](#):
>
> I don’t think there is an objective reason to want the smallest ones first.

Oh, actually, I think you want the smallest ones last, if anything? (Or is my guess for getting mildly better performance out of greedy knapsack selection off the mark?)

Is this about optimising for the last few transactions in a block, or choosing a canonical ordering so there’s less uncertainty/ambiguity, or something else?

You can’t get a strictly unique “perfect” linearisation, since if you have txs A, B, C, C spending A and B, and A,B having equal fee and size, but lower feerate than C, then [ABC] and [BAC] are equally good linearisations. You could break the tie by resorting to your arbitrary order R\_2, of course, but that’s still picking a winner arbitrarily…

Your definition of opt seems weird? Shouldn’t that just be \operatorname{opt}(G) = L\_G + \operatorname{opt}(G \setminus S\_G) where S\_G is the highest-feerate subset of G and L\_G is the first valid linearisation of S\_G?

I would have proven the uniqueness claim non-constructively: set f(L) = |\{L\_2 | L \ge L2\}|. Pick a linearisation L\_x where f(L\_x) \ge f(L) for all L. If this value equals the count of all linearisations, then L\_x \ge L for all L, so L\_x is an optimal linearisation. If it’s not the case, then there is some L\_y where L\_x \not\ge L\_y, so calculate L\_z = \operatorname{merge}(L\_x, L\_y) which gives us L\_z \ge L\_x but also L\_z \ge L\_y. But for any L where L\_x \ge L, L\_z \ge L by transitivity, so f(L\_z) \gt f(L\_x) which contradicts our choice of L\_x.

---

_[View the full topic](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202)._
