Cluster mempool definitions & theory

[murch]

@sipa

Definition. A chunking C = (c_1, c_2, \ldots, c_n)C=(c1,c2,…,cn)C = (c_1, c_2, \ldots, c_n) for a given graph G is a list of sets of transactions (called chunks) of G such that:

• The chunks c_icic_i form a partition of G (no overlap, and their union contains all elements).
• Every prefix of chunks is topological (\cup_{i=1}^{k} c_i∪ki=1ci\cup_{i=1}^{k} c_i for k=1 \ldots nk=1…nk=1 \ldots n are topological subsets of GGG). Thus, a transaction’s parent can appear in the same chunk as the transaction itself or in an earlier chunk, but not in a later chunk.
• The feerates of the sets are monotonically decreasing. Thus, the consecutive prefices of chunks form the highest, second-highest, … feerate topological prefices.

I assume you are defining it on a graph so that you can have a chunking across multiple clusters, but it seems to me that this definition would only require that the topology is valid at the chunk borders and would not require the transactions to be topological within the chunks. I think it would be correct if you said “every prefix of the chunking is topological” instead of “every prefix of chunks is topological”.

@sipa

Theorem. The corresponding chunking is a valid chunking, and is unique. The same chunking is obtained regardless of what order of merge operations is used. Thus, we can talk about the corresponding chunking \operatorname{chunks}(L)chunks(L)\operatorname{chunks}(L) of a linearization LLL. [no proof yet]

@sipa

For other values it linearly interpolates between those points.

Would it perhaps be sufficient that a feerate diagram has exactly one “convex hull” for a geometric proof? E.g. if we draw all transactions separately in the feerate diagram instead of their chunks, could we use the approach you use in the gathering theorem to show that all possible subgroupings will always be below the convex hull?

@sipa

Theorem. The chunk reordering theorem: reordering a linearization with changes restricted to a single chunk results leaves it at least as good.

Should this perhaps be restricted to topologically valid reorderings?

@sipa

Let e_j = c_j \cap Sej=cj∩Se_j = c_j \cap S for j=1 \ldots nj=1…nj=1 \ldots n, the SSS transactions in chunk iii of LLL. Note that this is distinct from d_jdjd_j because e_jeje_j follows the chunk boundaries of LLL, while d_jdjd_j follows the boundaries of L[S]L[S]L[S].

This should be “in chunk j of L”.

@sipa

Let \zeta_j = \cup_{i=j+1}^{n} e_iζj=∪ni=j+1ei\zeta_j = \cup_{i=j+1}^{n} e_i for j = 1 \ldots nj=1…nj = 1 \ldots n, the SSS transactions after the first jjj chunks of LLL.

Maybe “all remaining transactions of S after the first j chunks of L” would be clearer.

@sipa

Let SSS be the highest-feerate subset of GGG. If there are multiple, choose an arbitrary but consistent to order them.

“choose an arbitrary but consistent way/approach/method/criteria/something to order them”?

@sipa

Theorem. In an optimal linearization/chunking, the corresponding chunks have connected components whose feerate is all the same. This is trivially true if the chunks are all connected. Proof If not, the chunks could be split in two, which would improve the diagram.

Linebreak missing before the Proof.

I find that phrasing a bit confusing. What do you mean with “have connected components whose feerate is all the same”? I assume you are referring to the optimal linearization consisting only of chunks that cannot be split further by reordering, i.e. that any valid reordering would not lead to a different chunking, but the “have connected components whose feerate is all the same” makes me think that you are postulating that there are two chunks with the same feerate.