# 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:** 16

<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 26, 2023, 4:58am UTC](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209/16 "2023-11-26T04:58:04Z")

</div>

(I’m finding it hard to work out a decent way of comparing diagrams that doesn’t get lost in details really quickly. Perhaps the problem is that I really only want to compare orderings of a given set of transactions after chunking them, not compare two orderings of potentially two different sets of transactions with arbitrary groupings)

Anyway, I guess the general case I’m going for here is

\epsilon\_n + \delta\_j \ge \gamma\_j + \zeta\_j

Those are comprised of the exact same txs, ie d\_1, .., d\_j and e\_1, .., e\_n, but in different orders. The QED step is setting j=n giving \zeta\_j=\emptyset, and thus R\_1 + (L\_2 - R\_1) = \epsilon\_n + \delta\_n \ge \gamma\_n = L\_2. \ge is a diagram comparison after chunking the txs, and +, \sum are concatenation.

The initial step for j=0 is easy: \delta\_0 = \gamma\_0 = \emptyset and \epsilon\_n = \zeta\_0 by construction.

The inductive step is to show \epsilon\_n + \delta\_{j+1} \ge \gamma\_{j+1} + \zeta\_{j+1}. To show that, we have:

\begin{align} \epsilon\_n + \delta\_{j+1} &= (\epsilon\_n + \delta\_j) + d\_{j+1} \\ &\ge (\gamma\_j + \zeta\_j) + d\_{j+1} \\ &= \gamma\_j + (e\_{j+1} + \zeta\_{j+1}) + d\_{j+1} \\ &\ge \gamma\_j + e\_{j+1} + (d\_{j+1}) + \zeta\_{j+1} \\ &\ge \gamma\_j + (c\_{j+1}) + \zeta\_{j+1} \\ &= \gamma\_{j+1} + \zeta\_{j+1} \end{align}

Note that this chain is from best linearisation to worse. Steps are:

- inductive hypothesis
- moving d\_{j+1} after \zeta\_{j+1} improves things (observe that \zeta\_{j+1} has a higher feerate than any chunk)
- reordering the chunk c\_{j+1} into e\_{j+1} + d\_{j+1} doesn’t make things worse

Not sure how to properly formalise those steps yet, but I think they’re okay.

---

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