(Only digested part of the above so far)
Note that R_1 \leq P_1.
Why? Moving part of P_1 to the front could put a higher feerate new chunk up front.
M_{PI}(L_1,L_2)
What is PI?
FWIW, my (incomplete) proof sketch is as follows:
- Assume that the following holds: moving transactions to the front of a linearization such that they form a new chunk, while leaving the internal ordering within moved and non-moved transactions the same, is a non-worsening of the diagram if the new chunk’s feerate is >= the original first chunk’s feerate. (
no proofEDIT: see proof here) - Also assume that reordering the transaction within one chunk can never worsen the diagram (worst case the chunk set remains the same, best case it splits in multiple parts).
- The prefix-intersection merging algorithm can be seen as starting with two linearizations L_1 and L_2, and in each step moves some transactions to the front of both. Each step is a non-worsening of the diagram of both, and in the end, both linearizations are identical. That resulting linearization is thus better or equal than each of the inputs. To see why each step is a non-worsening:
- WLOG, assume the intersection found is a subset of L_1's first chunk, in the order of transactions of L_2. (swap the linearizations if not)
- The change applied to L_1 is just a reordering of its first chunk, which is fine.
- The change applied to L_2 is moving a new chunk to the front, of feerate at least that of its original first chunk (if not, that chunk would have been chosen instead), leaving the order within moved and non-moved transactions the same. This is fine.
- Afterwards, both linearizations start with the same transactions (at least one, so progress is made), so we can continue with just the distinct suffix.