delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Posted on: November 29, 2023 19:01 UTC

The theorem in discussion addresses the optimization of transaction linearization by reordering a sequence of transactions while maintaining the internal order of good and bad transactions.

It asserts that moving all good transactions, which merge into a single chunk with feerate $f$, to the beginning of the linearization will result in an improved or equivalent linearization.

The proof begins by stating that no chunk within any reordering of the same set of transactions can have a feerate greater than $f$. This is based on the premise that if such a chunk did exist, it would require a subset of transactions with a combined feerate higher than $f$, which contradicts the initial conditions since the good transactions alone form a chunk with exactly feerate $f$.

An algorithm is presented to iteratively move the good transactions to the front of the linearization. The process involves computing chunks, identifying the last chunk containing good transactions, and then reordering that chunk to move the good transactions to its beginning. This reordering either maintains the original chunk's feerate or improves it by potentially splitting the chunk into smaller ones. The algorithm guarantees progress towards the goal of moving all good transactions to the front unless they are already positioned there.

The method ensures that when all good transactions are at the start of the linearization, the feerate of this first chunk must be exactly $f$. This is because the chunk starting with good transactions has a feerate greater than or equal to $f$ and since no other chunk can have a higher feerate, the chunk in question must have a feerate precisely equal to $f$. Consequently, there can only be one such chunk, and it must be at the very beginning of the linearization. Once this state is reached, the optimization is complete as all good transactions are positioned at the front with their chunk being the first in the linearization.