Cluster mempool definitions & theory

[sipa]

@murch

I assume you are defining it on a graph so that you can have a chunking across multiple clusters

Right. I’ve added a paragraph to elaborate on why that is.

@murch

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.

Chunks, as defined here, are sets; they don’t have an internal ordering. I’ve gone back and forth in my thinking whether sets or sequences are better. The advantage of sets is that at the chunking level, you don’t need to care about distinct intra-chunk linearization orderings. The disadvantage is that converting back from chunkings to linearizations isn’t as natural.

@murch

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?

Let me think a bit more about that.

@murch

Should this perhaps be restricted to topologically valid reorderings?

Done.

@murch

This should be “in chunk j of L”.

Fixed.

@murch

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

Agreed, done.

@murch

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

I’ve formalized this a bit more, selecting the ordering before the function definition.

@murch

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.

Consider the following cluster:

graph BT
   T0["B: 7"] --> T1;
   T1["A: 1"];
   T2["D: 5"] --> T3;
   T3["C: 3"];
   T4["E: 1"] --> T0;
   T4 --> T2;

• The linearization [ACDBE] has chunking [ACDB,E]
• The linearization [ABCDE] has chunking [AB,CD,E]

As defined so far, both linearizations are equivalent (because their diagram coincides), and optimal. Yet still, chunk ACDB contains two disconnected components. The point of this theorem is showing that in an optimal linearization, chunks are still not necessarily connected, but this is only possible if the connected components all have the same feerate (4 in this example).

What I want to get to here, but haven’t really fleshed out, is a stronger notion of optimality than defined so far, which also requires all chunks to be connected - and that every graph has such a very-optimal linearization too.

Actually, now that you bring it up, I realize that’s not as strong as we’d want yet. Even with requiring connected chunks, it’s still possible that optimal chunkings contain chunks with equal-feerate subsets, so I guess very-optimality should instead be “optimal diagram, and chunks cannot contain topologically-valid strict subsets with equal feerate as the chunk itself” or so?