delvingbitcoin

LIMO: combining the best parts of linearization search and merging

LIMO: combining the best parts of linearization search and merging

Posted on: April 25, 2024 12:14 UTC

The process described focuses on optimizing transaction linearization through a novel construction method.

Initially, a starting linearization, denoted as $L$, is selected. The core of the methodology lies in iterating over the remaining transactions within $L$. During each iteration, two specific sets, named $S_1$ and $S_2$, are computed. These sets are characterized by their high fee rates and topological validity, ensuring that they adhere to certain desirable properties for transaction processing.

To determine the optimal set for appending to the output linearization, a comparison is made among various permutations of the initial and computed sets. Specifically, the permutations considered include the original linearization $L$, modifications of $L$ based on $S_1$ and $S_2$, and the intersection of $S_1$ and $S_2$. The selection criterion for the highest-feerate set, denoted by $b$, involves evaluating these permutations under the function $\Pi(Q)$, where $Q$ represents each permutation in question. The chosen set $b$ is then appended to the output linearization, signifying its priority or suitability based on the defined criteria.

Following the selection and appending of $b$ to the output, it is removed from the initial linearization $L$. This process of computation, selection, appending, and removal repeats until there are no transactions left in $L$. Additionally, the described approach is noted to generalize beyond the specific case of two sets, indicating its applicability to scenarios involving three or more variants. This generalization suggests a flexible framework capable of adapting to different configurations or requirements in the context of transaction linearization.