Asymmetric Mempool DoS Security: Formal Definitions and Provable Secure Designs

Asymmetric Mempool DoS Security: Formal Definitions and Provable Secure Designs

Speakers: Wanning Ding, Full Stack Security Lab, Syracuse University; Yuzhe Tang; Yibo WangSyracuse

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=G1xl1WaljmU

Overview

In the fast-evolving landscape of blockchain technology, the mempool (memory pool) serves as a critical staging area for unconfirmed transactions. It acts as a buffer where transactions await selection by validators to be included in a new block. This talk, presented by Wanning Ding from the Full Stack Security Lab at Syracuse University, delves into the often-overlooked yet profoundly impactful issue of Asymmetric Mempool DoS (Denial-of-Service) attacks. These attacks exploit vulnerabilities in how mempools are managed, threatening the economic stability and operational integrity of blockchain networks by preventing legitimate transactions from being processed and denying validators their rightful revenue.

The core contribution of this research is the introduction of a formal economic security definition for public memory pools, coupled with the design of the first provably economically secure mempool management policy. The presenters highlight a persistent "arms race" between attackers, who develop increasingly sophisticated multi-step exploits like MP Fuzz, and developers, who respond with reactive, piecemeal patches. This work aims to fundamentally shift this dynamic by providing a robust, theoretically grounded defense mechanism. By offering a provable solution, the researchers seek to end this cycle of vulnerability and patch, ensuring the resilience of blockchain systems against a critical class of DoS attacks.

The significance of this work extends to nearly all public blockchain systems, including major networks like Bitcoin and Ethereum, which rely heavily on mempools for transaction propagation and block construction. A compromised mempool can lead to severe consequences, ranging from user frustration due to stalled transactions to significant financial losses for validators and a general erosion of trust in the network's reliability. By formalizing the problem and proposing a provably secure design, this research offers a vital step towards building more resilient and economically stable decentralized infrastructures.

Background

▶ Watch: Introduction to Mempool DoS and the problem statement (0:00)

The journey of a transaction in a blockchain network follows a well-defined lifecycle. Initially, a user creates a transaction (e.g., a cryptocurrency transfer or a smart contract interaction) and broadcasts it to the network. This transaction then lands in the mempool of various network validators (or miners). The mempool acts as a temporary holding area, a buffer of unconfirmed transactions, awaiting inclusion in a block. Validators continuously monitor their mempools, selecting transactions – typically based on factors like transaction fees and age – to build new blocks. Once a block is successfully mined and confirmed by the network, the transactions within it are considered finalized. This fundamental process underpins the operation of most popular blockchain systems, including Bitcoin and Ethereum.

The integrity and availability of the mempool are paramount for the healthy functioning of a blockchain. If a mempool becomes "out of service" due to an attack, the implications are severe: validators cannot select transactions, leading to a loss of potential revenue, and legitimate users are unable to conduct trades or execute operations, severely degrading the network's utility. This vulnerability has historically been a target for malicious actors.

The talk frames the history of mempool attacks as an ongoing "arms race." Early attacks, characterized as "first-generation," were often single-step exploits designed to disrupt mempool operations. Examples cited include techniques like deter and me purge, which likely aimed to flood mempools or selectively remove transactions. These initial attacks were often mitigated by quick code patches and reactive updates by developers. However, this led to the emergence of "second-generation" attacks, such as MP fuzz. These newer attacks are more sophisticated, often involving multiple steps, exploiting complex interactions, or leveraging specific transaction properties to achieve their denial-of-service objectives, circumventing previous patches. The continuous cycle of attack and patch highlights a fundamental lack of a provably secure, foundational defense mechanism. The researchers argue that to effectively end this arms race, a formal, provable security framework is required, which is precisely what their work aims to deliver.

The term asymmetric in the context of these DoS attacks suggests that attackers can achieve disproportionate impact with relatively low cost or effort. This asymmetry often arises from exploiting the complex state transitions and dependency structures within a blockchain's transaction processing, allowing a few carefully crafted malicious transactions to disrupt a large volume of legitimate activity or cause significant economic damage to validators.

Key Findings

▶ Watch: Formal economic security definition for mempools (3:30)

The research presented in this talk delivers several critical advancements in the field of blockchain security, specifically addressing the long-standing challenge of mempool-based Denial-of-Service attacks.

Firstly, the team introduces the first formal economic security definition for public memory pools. This definition moves beyond simple availability metrics, focusing instead on the economic guarantees provided to validators and users. It establishes a lower bound for the total fees (or, practically, the total price) that should be present in the final state of a mempool after any sequence of adversarial actions, relative to its initial state. This formalization provides a rigorous benchmark against which mempool designs can be evaluated for their resilience against economic manipulation.

Secondly, and as a direct response to this formal definition, the talk presents the first provably economic secure memory pool design. This novel policy, termed the Ancestor Minimum Price (AMP) policy, represents a paradigm shift from reactive patching to proactive, mathematically verifiable security. By incorporating transaction dependencies and their associated costs into the eviction logic, AMP aims to prevent malicious actors from strategically evicting valuable or critical transactions.

Thirdly, the efficacy of the AMP policy was not merely theoretical. The researchers implemented their design by retrofitting Geth, a prominent Ethereum client, with the new policy. This practical implementation allowed for real-world evaluation of AMP's performance under attack scenarios.

Finally, the empirical evaluation demonstrated the robustness of the AMP policy. By replaying known eviction attacks, the researchers showed that while standard Geth implementations suffered a complete loss of revenue, the Geth client equipped with the AMP policy successfully mitigated these attacks, maintaining consistent revenue for validators. This practical validation underscores the potential of their provably secure design to significantly enhance the resilience of existing blockchain infrastructure.

Technical Deep Dive

▶ Watch: Demonstration of an insecure price-only policy (4:00)

The core of this research lies in understanding the mechanics of mempool eviction attacks and proposing a provably secure countermeasure. The talk meticulously details the problem and the proposed solution: the Ancestor Minimum Price (AMP) policy.

The Eviction Attack Explained

The presenters illustrate a classic eviction attack scenario:

1. A benign user sends Transaction Zero (Tx0) to the memory pool. Validators, aiming for revenue, would typically select Tx0 and execute it to generate a block, thereby earning fees.
2. An attacker intervenes by sending Transaction One (Tx1) before the block generation process. Crucially, Tx1 is designed to be invalid (e.g., spending non-existent funds, an invalid signature, or a replay attack), but it's crafted to appear attractive to the mempool's default sorting mechanism, often by having a high fee or price.
3. Tx1 "beats" Tx0 in priority, potentially causing Tx0 to be evicted or simply ignored if the mempool has limited capacity and prioritizes Tx1.
4. When validators attempt to build a block, they might select Tx1 due to its high apparent priority. However, upon execution, Tx1 is found to be invalid. Consequently, the validator is forced to generate an empty block, resulting in zero revenue. The legitimate user's Tx0 is excluded, leading to a denial of service.

The attacker's capability is further elaborated: they can send multiple transactions (Tx1, Tx2) in different orders (e.g., Tx1 then Tx2, or Tx2 then Tx1). The attack is successful if, regardless of the order, the final revenue drops to zero.

Formal Security Definition

To address this, the researchers propose a formal security definition. For any final state (S12 or S21, representing the state after Tx1 then Tx2, or Tx2 then Tx1), there must be a lower bound for the total fees. This lower bound, denoted as GS, is dependent on the initial state S of the mempool.

A key challenge in this definition is that the precise execution order of transactions within the mempool cannot be known beforehand. To overcome this, the definition shifts from relying on "fees" (which are only realized post-execution) to using price as an estimate for the lower bound. This is a practical and necessary adaptation for real-time mempool management.

Baseline Policy: Price-Only Policy

The talk first examines a common baseline policy: the price-only policy. This policy admits transactions solely based on their price, prioritizing higher-priced transactions and evicting lower-priced ones if the mempool is full.

Consider an example:

• Mempool contains Tx1 (from Alice, nonce 1, price 1) and Tx2 (from Alice, nonce 2, price 100). Tx2 is a child transaction dependent on Tx1 (i.e., Tx1 must be confirmed before Tx2 can be validly executed).
• A new transaction, Tx3 (from Bob, nonce 1, price 10), arrives, and the mempool is full.

Under the price-only policy:

• Tx1 has the lowest price (1).
• Tx3 (price 10) attempts to enter.
• The policy would evict Tx1 because it has the lowest price.
• Consequence: If Tx1 is evicted, Tx2 (price 100), which depends on Tx1, becomes invalid or unexecutable. The total effective price in the mempool decreases dramatically from 1 + 100 = 101 (if both Tx1 and Tx2 were processed) to only 10 (just Tx3). This scenario demonstrates that a price-only policy is not secure enough as it fails to account for crucial transaction dependencies, making it vulnerable to eviction attacks that target parent transactions.

Proposed Design: Ancestor Minimum Price (AMP) Policy

To overcome the limitations of the price-only policy, the researchers propose the Ancestor Minimum Price (AMP) policy. This policy introduces a more sophisticated scoring mechanism for transactions:

1. Transaction Score: Every transaction is assigned a score. This score is calculated as the minimum ancestor price.

• For a transaction that has no parents in the mempool (like Tx1 in our example, if it's the first in a sequence), its score might effectively be its own price, or a predefined baseline.
• For a child transaction (like Tx2), its score is the price of its direct parent. In our example, Tx2's parent is Tx1, which has a price of 1. Therefore, Tx2 is assigned a score of 1. This ties the "value" of a child transaction to the "cost" of its foundational parent.

1. Eviction Logic: When a new transaction arrives and the mempool is full, the AMP policy decides which transaction to evict based on these scores:

• It evicts the transaction with the lowest score.
• Crucially, the transaction selected for eviction must be a child transaction. This constraint ensures that parent transactions, which are often prerequisites for entire chains of subsequent transactions, are protected from arbitrary eviction. By only evicting children, the policy attempts to preserve the integrity of transaction dependency graphs as much as possible.

Revisiting the example with AMP:

• Mempool has Tx1 (Alice, nonce 1, price 1) and Tx2 (Alice, nonce 2, price 100).
• Tx1 has no parent in the mempool (or is the root of its chain). Let's assume its score is its own price: 1.
• Tx2 has Tx1 as its parent. Its score is the price of Tx1, which is 1.
• Tx3 (Bob, nonce 1, price 10) arrives.
• Now, Tx3 wants to enter. Comparing scores of child transactions: Tx2 has a score of 1.
• The AMP policy would evict Tx2 (score 1) instead of Tx1. This prevents the critical parent Tx1 from being removed. While Tx2 is evicted, Tx1 remains, preserving the possibility for Alice to resubmit Tx2 later or for other transactions dependent on Tx1 to still be processed.
• The researchers claim that by using AMP, the "total score now increases" and, more importantly, the "total price is never less than the total score." This ensures that the lower bound for the final state's total price, as defined, is met, thus providing the desired economic security. The policy prioritizes the preservation of economically valuable transaction chains by protecting their foundational components.

Demo / Proof of Concept

▶ Watch: How Ancestor Minimum Price policy prevents attacks (5:30)

To validate the practical efficacy of their Ancestor Minimum Price (AMP) policy, the researchers undertook a robust demonstration and proof of concept. They implemented their novel mempool management logic by retrofitting Geth, a widely used client for the Ethereum blockchain. This choice of Geth is significant as it represents a real-world, production-grade blockchain client, lending considerable weight to the experimental results.

The experimental setup involved deploying the modified Geth client (referred to as "AP" for Ancestor Price policy) and comparing its performance against a standard, unmodified Geth client (referred to as "Gas," likely representing its default gas-price-based policy). Both clients were subjected to replayed eviction attacks. These attacks were designed to mimic the sophisticated, multi-step scenarios that could reduce validator revenue, as described in the technical deep dive.

The primary metric for evaluation was the validation revenue generated over a period of 90 blocks. This metric directly reflects the economic impact of the mempool policy under both normal and adversarial conditions. The results, as presented in the talk, painted a clear picture:

• Under no attack conditions: The modified Geth client ("AP") exhibited comparable revenue to the standard Geth client ("Gas"). This indicates that the AMP policy does not introduce undue overhead or negatively impact performance when the network is operating normally.
• Under eviction attacks: The standard Geth client ("Gas") proved to be unsecure, with its revenue plummeting to zero. This stark outcome underscores the severe economic vulnerability of current mempool designs to targeted DoS attacks.
• Under eviction attacks with AMP: The Geth client retrofitted with the AMP policy ("AP") successfully mitigated the attack. Critically, its revenue did not decrease, demonstrating its resilience and effectiveness in preserving validator income even in the face of active threats.

This empirical validation on a widely used blockchain client provides strong evidence that the Ancestor Minimum Price policy is not just a theoretical construct but a practical, implementable solution that can significantly enhance the economic security of blockchain mempools against sophisticated DoS attacks.

Defensive Implications

▶ Watch: Evaluation results: secure policy maintains revenue (6:00)

The research on Asymmetric Mempool DoS security and the Ancestor Minimum Price (AMP) policy carries profound defensive implications for the entire blockchain ecosystem. The findings suggest a critical shift in how mempools should be designed and managed, moving beyond simplistic fee-based prioritization to a more sophisticated, dependency-aware approach.

Firstly, the most direct implication is that blockchain clients, particularly those for major networks like Ethereum (as demonstrated with Geth) and potentially Bitcoin, should seriously consider adopting mempool policies akin to AMP. The current reliance on simple price-only or gas-price-only eviction mechanisms leaves validators and users vulnerable to economically devastating attacks. Integrating AMP or similar provably secure designs into core client software would provide a foundational layer of defense that is currently lacking.

Secondly, validators (miners, block producers) need to understand that optimizing for immediate transaction fees alone is insufficient. They must prioritize transactions not just by their individual price, but by considering the dependencies between transactions and the overall "ancestor minimum price" of a transaction chain. This means recognizing that a seemingly low-fee parent transaction might be crucial for unlocking the value of many high-fee child transactions. Protecting these foundational transactions becomes paramount to ensuring long-term revenue stability and network health.

Thirdly, this work underscores the necessity of moving from reactive patching to proactive, provably secure designs. The "arms race" described by the speakers is unsustainable and costly. By providing a formal economic security definition and a design that is provably secure against a class of attacks, the research offers a blueprint for breaking this cycle. Future blockchain protocol designs and client implementations should incorporate such rigorous security guarantees from the outset, rather than waiting for vulnerabilities to be exploited before developing ad-hoc fixes.

Finally, the findings highlight the importance of network-wide adoption. While a single validator implementing AMP would be more secure, the full benefits of such a policy are realized when a significant portion of the network's validators adopt it. This could lead to a more stable and predictable transaction environment, reducing the success rate of mempool manipulation attempts and bolstering overall network resilience. Efforts should be made to standardize such policies or at least make them configurable options within popular client software, accompanied by clear guidance on their benefits.

Key Takeaways

• Mempool Denial-of-Service (DoS) attacks, particularly asymmetric eviction attacks, pose a significant and ongoing threat to the economic security and operational stability of public blockchain networks.
• Traditional mempool management policies, which primarily prioritize transactions based on individual price or gas fee, are inherently vulnerable to these attacks, potentially leading to zero revenue for validators and denial of service for users.
• The research introduces the first formal economic security definition for public memory pools, establishing a quantifiable lower bound for total transaction value that should be maintained under adversarial conditions.
• The proposed Ancestor Minimum Price (AMP) policy is the first provably economically secure mempool design. It assigns a score to each transaction based on its minimum ancestor's price and prioritizes evicting low-score child transactions to preserve critical parent transactions and their dependencies.
• Empirical validation through retrofitting Geth, a leading Ethereum client, demonstrated AMP's effectiveness: while standard Geth clients suffered complete revenue loss under eviction attacks, the AMP-equipped client successfully mitigated these attacks, maintaining consistent validator revenue.
• The work advocates for a fundamental shift in blockchain security, urging developers and validators to adopt proactive, provably secure mempool management policies like AMP, moving away from reactive patching to build more resilient and economically stable decentralized systems.

About the Speaker(s)

The primary presenter for this work was Wanning Ding, representing the Full Stack Security Lab at Syracuse University. The research was a collaborative effort, undertaken with their advisor, Dr. Yuzhe Tang, and other colleagues within the lab at Syracuse University. Their work focuses on enhancing the security and resilience of blockchain systems, particularly in critical areas like transaction processing and mempool management.