delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Posted on: December 1, 2023 21:31 UTC

The "gathering theorem" posits that when transactions within a linearization are bifurcated into 'good' and 'bad' subsets, the recombination of these subsets will yield a feerate diagram that is at least as favorable as the original.

This assertion builds upon the geometrical analysis of transaction sets using concepts from a proof sketch provided by ajtowns.

To demonstrate this theorem, one considers a linearization, (L), and identifies a topologically valid subset of transactions deemed 'good' ((G)). The theorem examines the linearizations (L_G) (only good transactions) and (L_B) (the bad ones) derived from (L) and posits that the linearization comprising (L_G + L_B) will be equal to or better than (L) in terms of feerate efficiency. The proof employs geometric representations of the sizes and fees of transaction subsets to illustrate this point.

Analyzing the theorem involves understanding the relationships between the sizes, fees, and feerates of the subsets created by partitioning (L) into chunks and their intersections with (G). The crux of the argument lies in showing that for any given chunk, the feerate of the set of 'good' transactions extending from that chunk onwards is always greater than or equal to the highest chunk feerate of (L). This property ensures that when visualized on a 2D diagram, the points representing the cumulative sizes and fees of the good transactions combined with bad transactions up to any chunk form a curve that underestimates the true feerate diagram for (L_G + L_B).

Further examination reveals that the underestimate curve for (L_G + L_B) never dips below the concave function representing (L). This is because each segment of the underestimate curve maintains a slope that is equal to or steeper than the corresponding segment of (L)'s curve. Consequently, one can conclude that the recombined linearization of good and bad transactions does not degrade the feerate efficiency compared to the original linearization.

Additionally, it's highlighted that the requirement for (L_G) to form a single chunk with a feerate greater than or equal to the highest chunk feerate (f) can be relaxed. Instead, it may only be necessary for the lowest chunk feerate of (L_G) to meet this criterion. This generalization would lead to additional points being added to the underestimate curve but would still ensure that the curve remains above or coincident with the diagram for (L), thus preserving the validity of the gathering theorem.