Linearization post-processing (O(n^2) fancy chunking)

Implementation
2

Hmm, I’ve mostly been thinking of linearisation and chunking as synonyms – you never do one without the other, and once you’re done you only deal with chunks, not individual txs.

Feels to me like it might be possible to build up chunks from ancestor scoring directly (so create a graph of single-tx chunks; merge the chunks that cpfp each other greedily by ancestor fee rate; update anc fee rates as you go, which may result in other chunks cpfp’ing newly merged chunks; then sort the resulting chunks by their final score), but trying to write it down, it doesn’t seem much simpler compared to the approach you’re suggesting.

I think a simple-ish case this still wouldn’t catch is:

graph BT
    A[A: 8]
    B[B: 0, vsize=5x]
    C[C: 12; afr=10] --> A
    D[D: 48; afr=8] --> A
    E[E: 48; afr=8] --> A
    D --> B;
    E --> B;

(ie A,C,D,E are all the same size, B is 5x that size, A pays 8 in fees, C pays 12 in fees, etc)

The ancestor linearisation is A,C,B,D,E (picking C then D then E), and (I think) the new algorithm would produce a single chunk with score 12.89, but it would be more optimal to generate ABDE,C with scores 13 and 12.

Think that’s just saying “this isn’t optimal in all cases” though, which isn’t really news.

4 Likes