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.

Bitcoin Logo

TLDR

Join Our Newsletter

We’ll email you summaries of the latest discussions from authoritative bitcoin sources, like bitcoin-dev, lightning-dev, and Delving Bitcoin.

Explore all Products

ChatBTC imageBitcoin searchBitcoin TranscriptsSaving SatoshiBitcoin Transcripts Review
Built with 🧡 by the Bitcoin Dev Project
View our public visitor count

We'd love to hear your feedback on this project?

Give Feedback