# Merging incomparable linearizations

**URL:** <https://delvingbitcoin.org/t/merging-incomparable-linearizations/209>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool, mempool\
**Created:** [November 19, 2023, 4:12am UTC](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209 "2023-11-19T04:12:15Z")\
**Posts on this page:** 1\
**Showing post:** 9

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [November 24, 2023, 10:21am UTC](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209/9 "2023-11-24T10:21:08Z")

</div>

- Assume you have a function C(L) that takes a linearisation L and splits that into P\_L, T\_L where P\_L is the first chunk, and T\_L is the rest of the linearisation. If L is non-empty, P\_L is non-empty also; however T\_L may be empty.
- Assume you can calculate L - X where L and X and the result is just L with the transactions in X removed
- We say that A \le B by doing a feerate diagram comparison and noting B is has a higher or equal feerate at all points.

I think prefix-intersection merging, M(L\_1, L\_2) is equivalent to:

- Take P\_1, T\_1 = C(L\_1) and P\_2, T\_2 = C(L\_2)
- Reorder the transactions in P\_1 to match the order they appear in L\_2, call this P^\prime\_1, and then calculate R\_1, X\_1 = C(P^\prime\_1). Note that P\_1 \le R\_1.
- Calculate R\_2, X\_2 in the same way from P\_2.
- Choose the highest feerate chunk from R\_1, R\_2:
  - If R\_1 is the highest, then: M(L\_1, L\_2) = R\_1 + M(X\_1 + T\_1, L\_2-R\_1)
  - Otherwise: M\_{PI}(L\_1, L\_2) = R\_2 + M(L\_1-R\_2, X\_2 + T\_2)

For the case where R\_1 is highest, then M(L\_1, L\_2) = M(R\_1 + X\_1 + T\_1, L\_2) and L\_1 \le R\_1 + X\_1 + T\_1.

The question is whether L\_2 \le R\_1 + (L\_2-R\_1), noting that the transactions in R\_1 that we’ve removed from L\_2 maintain their order, and have an equal or higher feerate than the original best chunk.

Consider each chunk from L\_2, call them c\_1, c\_2, c\_3, \dots, c\_n. Then define d\_i = c\_i - R\_1, and e\_i = c\_i - d\_i. In that case R\_1 = e\_1 + e\_2 + e\_3 + \dots + e\_n (because R\_1 is the first chunk of P^\prime\_1 which had its transactions put in the same order as L\_2).

Define:

\begin{align} \gamma\_j &= \sum\_{i=1}^j c\_i \\ \delta\_j &= \sum\_{i=1}^j d\_i \\ \epsilon\_j &= \sum\_{i=1}^j e\_i \\ \zeta\_j &= \sum\_{i=j+1}^n e\_i \\ \end{align}

We see L\_2 = \gamma\_n, and R\_1 + (L\_2 - R\_1) = \epsilon\_n + \delta\_n and \epsilon\_n = \epsilon\_j + \zeta\_j. Note that the feerate of \zeta\_j is greater or equal to the feerate of R\_1 = \epsilon\_n in all cases – otherwise those transactions would not have been included in R\_1 when calculating the chunk.

Consider total size of \gamma\_j, S(\gamma\_j) and its total fee F(\gamma\_j). Note that the feerate diagram of L\_2 is made up of the pairs S(\gamma\_j), F(\gamma\_j).

If we consider \epsilon\_j + \delta\_j then we simply have S(\epsilon\_j + \delta\_j) = S(\gamma\_j) and F(\epsilon\_j + \delta\_j) = F(\gamma\_j).

Now consider \epsilon\_j + \delta\_j + \zeta\_j – for which the feerate diagram at position S(\gamma\_j) is at least F(\epsilon\_j + \delta\_j), ie at least F(\gamma\_j). But we know \zeta\_j has a higher fee rate than any chunk in \epsilon\_j + \delta\_j, so the feerate diagram of \epsilon\_j + \zeta\_j + \delta\_j is an improvement. That gives \gamma\_j \le \epsilon\_n + \delta\_j, and choosing j=n gives L\_2 = \gamma\_j \le \epsilon\_n + \delta\_n = R\_1 + (L\_2 - R\_1). QED?

---

_[View the full topic](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209)._