Bitcoin Mempool Linearization

• URL: http://arxiv.org/abs/2607.23787v1
• Date: Sun, 26 Jul 2026 18:04:28 GMT
• Title: Bitcoin Mempool Linearization
• Abstract summary: In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks.<n>This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering.<n>Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed.
• Score: 4.265773997354609
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, inducing dependency constraints among transactions in the mempool. At the same time, miners are economically incentivized to prioritize transactions with higher fee rates, measured as transaction fee per unit size. This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering that maximizes fee-rate efficiency while supporting efficient updates as the mempool evolves dynamically. The problem is characterized through a partition of transactions into disjoint dependency-respecting subsets ordered by decreasing aggregate fee rate, together with an equivalent LP formulation. Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed. Operating directly on the transaction dependency graph, SFL iteratively merges and splits chunks of transactions to refine a global ordering, and is guaranteed to terminate at an optimal solution. Evaluation on both synthetic and real-world Bitcoin mempool data shows that SFL consistently computes optimal linearizations with substantially lower runtime than competing approaches, including a method based on the parametric preflow algorithm of Gallo, Grigoriadis, and Tarjan. These results indicate that SFL provides a practical and scalable framework for transaction prioritization by decentralized miners in large and rapidly evolving mempools. SFL has also been incorporated into the Bitcoin Core codebase for transaction cluster linearization.

Related papers

• Eliminating Multi-GPU Performance Taxes: A Systems Approach to Efficient Distributed LLMs [61.953548065938385]
  We introduce the ''Three Taxes'' (Bulk Synchronous, Inter- Kernel Data Locality, and Kernel Launch Overhead) as an analytical framework.<n>We propose moving beyond the rigid BSP model to address key inefficiencies in distributed GPU execution.<n>We observe a 10-20% speedup in end-to-end latency over BSP-based approaches.
  arXiv  Detail & Related papers  (2025-11-04T01:15:44Z)
• Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection [15.381969851183527]
  We consider an input sequence of transactions over $p$ parties.<n>Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected.<n>We output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels.
  arXiv  Detail & Related papers  (2025-08-20T08:34:20Z)
• Efficient Blockchain-based Steganography via Backcalculating Generative Adversarial Network [105.47203971578871]
  We propose a generic blockchain-based steganography framework (GBSF)<n>The sender generates the required fields such as amount and fees, where the additional covert data is embedded to enhance the channel capacity.<n>Based on GBSF, we design a reversible generative adversarial network (R-GAN)<n>We propose R-GAN with Counter-intuitive data preprocessing and Custom activation functions, namely CCR-GAN.
  arXiv  Detail & Related papers  (2025-06-19T04:43:41Z)
• Neonpool: Reimagining cryptocurrency transaction pools for lightweight clients and IoT devices [2.493740042317776]
  Neonpool is an innovative transaction pool optimization using bloom filter variants.<n>It verifies and forwards transactions with over 99.99% accuracy and does not necessitate a hard fork.<n>Neonpool is ideally suited for lightweight cryptocurrency clients and for resource-constrained devices such as browsers, systems-on-a-chip, mobile or IoT devices.
  arXiv  Detail & Related papers  (2024-12-18T03:19:19Z)
• HAFLQ: Heterogeneous Adaptive Federated LoRA Fine-tuned LLM with Quantization [55.972018549438964]
  Federated fine-tuning of pre-trained Large Language Models (LLMs) enables task-specific adaptation across diverse datasets while preserving privacy.<n>We propose HAFLQ (Heterogeneous Adaptive Federated Low-Rank Adaptation Fine-tuned LLM with Quantization), a novel framework for efficient and scalable fine-tuning of LLMs in heterogeneous environments.<n> Experimental results on the text classification task demonstrate that HAFLQ reduces memory usage by 31%, lowers communication cost by 49%, improves accuracy by 50%, and achieves faster convergence compared to the baseline method.
  arXiv  Detail & Related papers  (2024-11-10T19:59:54Z)
• Generative Blockchain: Transforming Blockchain from Transaction Recording to Transaction Generation through Proof-of-Merit [5.801684954657074]
  generative blockchain aims to transform conventional blockchain technology by combining transaction generation and recording. Central to our design is a novel consensus mechanism, Proof-of-Merit (PoM) We demonstrate PoM on a ride service on-demand platform, where the task of solving complex transaction-generating problems is delegated to a pool of independent problem solvers.
  arXiv  Detail & Related papers  (2024-08-23T20:51:10Z)
• Fast and Secure Decentralized Optimistic Rollups Using Setchain [1.1534313664323634]
  Layer 2 optimistic rollups (L2) are a faster alternative that offer the same interface in terms of smart contract development and user interaction. We propose a decentralized L2 optimistic rollup based on Setchain, a decentralized Byzantine-tolerant implementation of sets.
  arXiv  Detail & Related papers  (2024-06-04T13:45:12Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• Sparse Decentralized Federated Learning [35.32297764027417]
  Decentralized Federated Learning (DFL) enables collaborative model training without a central server but faces challenges in efficiency, stability, and trustworthiness.<n>We introduce a sparsity constraint on the shared model, leading to Sparse DFL (SDFL), and propose a novel algorithm, CEPS.<n> Numerical experiments validate the effectiveness of the proposed algorithm in improving communication and efficiency while maintaining a high level of trustworthiness.
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• TxAllo: Dynamic Transaction Allocation in Sharded Blockchain Systems [37.22526235663589]
  This paper focuses on the transaction allocation problem to reduce the number of cross-shard transactions. A deterministic and fast allocation scheme TxAllo is proposed to dynamically infer the allocation of accounts. For a blockchain with 60 shards, TxAllo reduces the cross-shard transaction ratio from 98% to about 12%.
  arXiv  Detail & Related papers  (2022-12-22T10:22:31Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• AdaPool: Exponential Adaptive Pooling for Information-Retaining Downsampling [82.08631594071656]
  Pooling layers are essential building blocks of Convolutional Neural Networks (CNNs) We propose an adaptive and exponentially weighted pooling method named adaPool. We demonstrate how adaPool improves the preservation of detail through a range of tasks including image and video classification and object detection.
  arXiv  Detail & Related papers  (2021-11-01T08:50:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.