I’ve made a number of posts on the topic, but it’s explained at least in:
- Introduction to cluster linearization (more accessible)
- Cluster mempool definitions & theory (more theory)
Summarized very briefly:
- A linearization is any topological ordering for the transactions in a cluster (i.e., parents always go before children).
- The fee-size diagram for a linearization of a cluster is the convex hull through the points whose (x,y) are the (size,fee) of all prefixes of the linearization. The line sections of the diagram correspond to chunks of the linearization: groups of transactions which “pay for each other” (which can be seen as a generalization of CPFP).
- A linearization L_1 is at least as good as a linearization L_2 for the same cluster if the diagram of L_1 is nowhere below the diagram of L_2. The intuition is that we don’t know ahead of time how much of the cluster we’ll be able to include in a block (when considering clusters in isolation), so we want something that is good “everywhere” - the diagram tells us (roughly, ignoring the fact that the convex-hulling makes it approximate) how good a linearization is for every possible prefix that gets included.
- There is a proof that by this definition, at least one optimal linearization for every cluster exists, which means a linearizations that is at least as good as every other linearization for the cluster. In other words, making the convex-hull approximation is sufficient to simplify the problem enough so that a globally optimal linearization always exists, abstracting away the fact that we don’t know ahead of time how much of a cluster will be included in a block.
One way of constructing an optimal linearization is by finding the highest-feerate topologically-closed subset of the cluster, moving it to the front of the linearization, and then continuing with what remains of the cluster. GGT uses another approach, by subdividing the cluster into smaller and smaller portions, which end up being the chunks.