delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Posted on: December 5, 2023 19:47 UTC

The discussion revolves around the comparison of two linearization algorithms, bestPi and the original PiMerge, in terms of their performance and output.

The sender leans toward using the original PiMerge algorithm since the performance difference between the two is not substantial enough to warrant a change. Moreover, the sender highlights that merging processes are not necessarily commutative; this characteristic becomes apparent when dealing with linearizations that have different initial chunks at equal feerates.

A specific example is provided to illustrate this point. Five transactions labeled A through E, all the same size but having different fees, are processed through both linearizations resulting in varied outcomes. Two different chunked sequences are generated from each linearization algorithm (L1 and L2). When merged, each pair (L1 with L2, and L2 with L1) produces a distinct sequence and chunking. This supports the argument that the choice of linearization can influence the outcome even if the subsets have the same feerate.

The sender initially suggests that selecting smaller sizes as a tie-breaker when equal-feerate chunks are encountered could be beneficial within the algorithms, as it might prevent the accidental merging of such subsets. However, a counterexample is then edited into the message, demonstrating a scenario where the chosen tie-breaker indeed affects the fee-size diagram. The counterexample clearly shows how different merging orders (Merge(L1,L2) versus Merge(L2,L1)) lead to distinct chunkings, implying that the choice of tie-breaker in this context does matter. This insight may influence future considerations on how to handle equal-feerate situations within linearization algorithms.