Cluster mempool definitions & theory

Cluster mempool definitions & theory

Posted on: February 27, 2024 16:07 UTC

In the discussion, a methodical approach to optimizing transaction lists by manipulating their order based on feerate is explored.

The focus is on starting with an optimal list, denoted as $L_{opt}$, and strategically adjusting it by reordering prefixes that share the same feerate characteristics with another list, $L$. This reordering is done to expedite the comparison process by immediately addressing segments where the feerate differs between the two lists. The premise relies on the assumption that for effective optimization, it's sufficient to concentrate on portions of the lists where the feerate is distinctly different right from the start. By identifying and moving these coinciding prefixes to the forefront of $L_{opt}$, the process simplifies the task to dealing only with the remaining segments where actual discrepancies in feerate occur.

The argument unfolds with a detailed examination of how to handle these prefixes, identified as $p$, which could potentially be made up of multiple chunks from $L$. The methodology varies depending on the composition of $p$. If $p$ does not contain any chunks, there's no alteration needed. However, when $p$ consists of a single chunk that matches the feerate of $L_{opt}$'s initial chunk, applying what is referred to as the gathering theorem directly yields the desired outcome. The real challenge arises when $p$ encompasses multiple chunks. In such scenarios, the solution involves a repetitive application of both the gathering theorem, to move a chunk of $p$ to the beginning of $L_{opt}$, and the stripping theorem, which effectively ignores the just-moved segment, thereby streamlining the comparison process. Through this iterative approach, the essence of the argument is conveyed in a manner that emphasizes practical understanding over formal exposition, suggesting that the informal explanation provided offers clearer insights into the optimization strategy being proposed.