Combined summary - Merging incomparable linearizations

Combined summary - Merging incomparable linearizations

The focus of the study is to create an optimal transaction linearization by merging existing ones.

Linearizations are compared using fee-size diagrams, with the goal of achieving a linearization that is never worse and sometimes better than others. The Best-chunk merging algorithm was initially considered but found to have limitations, as it may not always improve the result and has complexity $\mathcal{O}(n^2)$. It could also fail to take advantage of common subsets in both input linearizations.

To overcome these issues, the Intersection merging algorithm was proposed, which considers intersections of highest-feerate prefixes. Despite improvements, this method still did not guarantee better outcomes. A more advanced technique, the Prefix-intersection merging algorithm, expands the search to all prefix intersections between two linearizations. This method suggests focusing on intersections involving the best chunk of at least one linearization and maintains the same complexity of $\mathcal{O}(n^2)$ while providing consistently better or at least comparable results to the inputs.

However, proof of the absolute superiority of this algorithm is lacking, and its non-associative nature when merging presents additional challenges. An example demonstrated how different merging sequences can result in varying outcomes, highlighting the nuanced complexity of the process. The discussion also touches upon post-processing's limitations in addressing certain scenarios, such as when transactions have arranged feerates.

A geometric approach introduced the gathering theorem, asserting that a new diagram based on a subset of transactions will always be above or equal to the original if the subset forms a single chunk with a feerate greater than or equal to the highest chunk feerate of the original linearization. This theorem uses visual representations to validate the improved outcome of the new linearization.

The exploration concludes that if an underestimate of a linearization diagram lies on or above another linearization's diagram, then it is superior or equivalent. The concept of average feerate versus individual chunk feerate was examined, with a preference for higher fee diagrams as indicators of superior linearization. There was also a mention of the necessity to include the initial case in proofs, and the effectiveness of horizontal line segments in determining optimal solutions.

Additionally, the ability to visualize feerates through plotting was discussed, with a Google Spreadsheet provided for experimentation. The method for constructing non-optimal feerate diagrams for combined good and bad subsets was shown to result in better linearizations when optimally chunked. Furthermore, merging post-processed linearizations was highlighted, showing that further post-processing might improve outcomes, as illustrated using Mermaid syntax.

Finally, an algorithm was described to optimize transaction ordering by initially chunking the present linearization into sections with unique feerates and then rearranging chunks to prioritize good transactions. Reordering within a chunk can only maintain or enhance the arrangement, and progress is made by moving good transactions to the beginning unless they are already there. The completion condition is an ideal state where a chunk starts with all its good transactions at a specific feerate 'f', indicating an optimal ordering.

Discussion History

sipaOriginal Post
November 29, 2023 19:01 UTC
November 29, 2023 22:15 UTC
November 30, 2023 19:01 UTC
November 30, 2023 19:30 UTC
November 30, 2023 19:51 UTC
November 30, 2023 20:03 UTC
November 30, 2023 20:16 UTC
November 30, 2023 23:17 UTC
December 1, 2023 21:31 UTC
December 2, 2023 22:12 UTC
December 3, 2023 18:44 UTC
December 3, 2023 20:17 UTC
December 4, 2023 06:42 UTC
December 4, 2023 06:45 UTC
December 4, 2023 08:44 UTC
December 4, 2023 08:56 UTC
December 4, 2023 13:45 UTC
December 4, 2023 13:51 UTC
December 4, 2023 21:36 UTC
December 5, 2023 16:33 UTC
December 5, 2023 19:47 UTC