delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Posted on: December 3, 2023 20:17 UTC

Prefix-intersection merging is a process that involves working with two linearizations, $L_1$ and $L_2$.

It begins by identifying an optional identical prefix in both linearizations. The focus then shifts to finding the highest-feerate prefix for each linearization, denoted as $P_i$ for $L_i$, where $i$ belongs to the set {1,2}. It's crucial to ensure that $R(P_1)$, the feerate of the highest prefix in $L_1$, is greater than or equal to $R(P_2)$. If this condition isn't met initially, the inputs are swapped.

The next step is to pinpoint the highest-feerate prefix within the intersection of $L_2$ and $P_1$, labeled as $C$. Upon determining $C$, it is outputted and subsequently removed from both $L_1$ and $L_2$. After this removal, the process recommences with the remaining elements of the linearizations.

This approach focuses on the intersection of the highest-feerate prefix of one linearization with the other, instead of considering both directions. Importantly, this method maintains the integrity of the "as good as both inputs" proof. Fuzz testing suggests that employing this simplified version does not degrade the results. While currently there is no formal proof confirming the equivalence of this simplified algorithm to more complex versions, the simplicity and correctness suggest that it may be acceptable for use.