delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Original Postby ajtowns

Posted on: December 4, 2023 08:44 UTC

In the process of optimizing transaction ordering within a block, a programmer explores a scenario where post-processing may not improve transaction selection.

The example includes six transactions, labeled A through E, and an additional parent transaction P. These transactions vary in size and fee rate, with P being 100vB at 0 sat/vb and the others being 10kvB each, with fee rates of 50, 30, 10, 80, and 0 sat/vb respectively. Transactions A and D are dependent on the output from P.

The programmer outlines a series of steps to illustrate that despite post-processing efforts, the optimal order of transactions is not achieved. Initially, two lists, L1 and L2, are created to simulate different transaction sequences, with associated chunks and their corresponding fee rates. In both arrangements, transaction P is prioritized due to its dependency linkage with A and D. Through a comparison between the two lists, it's observed that when repeating the process by prioritizing transactions with equal fee rates, the result is an inefficient sequencing of transactions.

The following sequence L=PADBCE results after several iterations, where transactions are compared and ordered based on their fee rates and dependencies. Throughout this example, the post-processing steps marked with asterisks demonstrate an attempt to reorganize the transaction sequences for better optimization. Despite these efforts, the issue remains that a low-fee parent transaction can impact the ordering significantly, leading to a suboptimal outcome even after post-processing. This example serves as a critical analysis of the limitations inherent in certain post-processing strategies within transaction selection algorithms.