Future Nonce DoS Vulnerability in Cross-Domain Messaging (XDM)

[vexr]

Disclaimer

This vulnerability analysis is based on my review of the Autonomys Network Subspace codebase. While every effort has been made to ensure accuracy and completeness, the complexity of this project means there may be mitigating factors, design considerations, or protective mechanisms that were not identified during this analysis.

If you identify any inaccuracies, oversights, or existing mitigations that affect the validity of this vulnerability report, please provide feedback. The goal of this document is to improve the security and robustness of the Autonomys Network, and constructive input is greatly appreciated.

Executive Summary

A critical vulnerability exists in the Autonomys Network’s cross-domain messaging system that allows an attacker to severely degrade cross-chain communication at minimal cost. By exploiting the future nonce allowance mechanism, an attacker can occupy all 256 available future nonce slots with valid messages, causing legitimate transactions to fail and forcing users into a race condition where they must spam attempts to have any chance of getting their messages through.

Vulnerability Description

The Issue

The messenger pallet allows messages with nonces up to 256 ahead of the current expected nonce (MAX_FUTURE_ALLOWED_NONCES = 256). Messages must be processed in strict sequential order - nonce 0, then 1, then 2, etc. An attacker exploits this by maintaining all 256 nonce slots occupied at all times, preventing legitimate users from obtaining any nonce.

Attack Mechanism:

1. Attacker submits messages with nonces 0-255 (all valid messages)
2. Legitimate users try to send a message but all nonces up to 255 are taken - their transactions fail
3. As nonce 0 is processed, attacker immediately submits a message with nonce 256
4. The pattern continues: attacker maintains nonces [N to N+255], all slots are always full
5. Result: Legitimate users must spam transaction attempts hoping to win the race for a freed nonce

Concrete Impact on Users:

• Legitimate transactions consistently fail with “nonce already used” errors
• Users must spam hundreds/thousands of attempts to have any chance of success
• Even with aggressive retry strategies, success depends on beating the attacker’s automation
• Users waste fees on failed transaction attempts

The Race Condition:
When nonce 0 is processed, there’s a brief window where nonce 256 becomes available. However:

• The attacker’s automated system monitors for processed messages
• It immediately submits a new message claiming nonce 256
• Legitimate users (especially manual ones) have virtually no chance of winning this race
• Even automated legitimate systems struggle against a dedicated attacker

Why This Is Dangerous

1. Complete Service Denial: The channel becomes effectively unusable as legitimate transactions consistently fail

2. Low Cost Attack: The attack requires minimal AI3 tokens to execute and maintain

3. Critical Infrastructure Impact: This completely blocks essential operations:

   • Token transfers between chains become impossible
   • Smart contract interactions across domains fail
   • Domain operator communications are blocked
   • All cross-chain protocol messages fail
   • Farmers cannot bridge earned AI3 to EVM domains for trading, breaking the core economic model

4. Forces Spam Behavior: Legitimate users must spam thousands of transaction attempts, wasting fees on failures

5. Network Congestion Amplification: The forced spam behavior creates additional network load, making the situation worse

6. Plausible Deniability: Attacker’s messages are all valid, making the attack hard to distinguish from legitimate high-volume usage

7. No Effective Countermeasure: Current fee structure makes this attack economically sustainable indefinitely

Technical Analysis

Block Space Constraints

• Maximum Block Length: 5,242,880 bytes (5 MiB)
• Normal Dispatch Ratio: 75%
• Available for Normal Extrinsics: 3,932,160 bytes (3.75 MiB)

XDM Message Structure

A typical CrossDomainMessage consists of:

pub struct CrossDomainMessage<CBlockNumber, CBlockHash, MmrHash> {
    pub src_chain_id: ChainId,        // ~4 bytes
    pub dst_chain_id: ChainId,        // ~4 bytes  
    pub channel_id: ChannelId,        // ~4 bytes
    pub nonce: Nonce,                 // 32 bytes (U256)
    pub proof: Proof<...>,            // 1-5 KB (includes MMR and storage proofs)
    pub weight_tag: MessageWeightTag, // ~100 bytes
}

Estimated message size: 2-6 KB per message (average ~4 KB)

Messages Per Block Calculation

Theoretical maximum (if block contains only XDM messages):

• Available space: 3,932,160 bytes
• Average message size: 4,096 bytes
• Maximum messages per block: ~960 messages

However, practical limits are much lower due to:

• Weight limits (computational time constraints)
• Other transactions competing for block space
• Base relay_message weight: 37,070,000 weight units (plus additional weight for message processing)

Fee Calculation

From the codebase:

• TransactionWeightFee = 100_000 * SHANNON (per weight unit)
• XdmFeeMultiplier = 5
• Base relay_message weight = 37,070,000 weight units (plus message-specific weight)

Cost per message (base weight only):

Base fee = 37,070,000 × 100,000 Shannon = 3,707,000,000,000 Shannon
With 5x multiplier = 18,535,000,000,000 Shannon
≈ 0.000018535 AI3 per message

Note: Additional byte fees apply based on message size, but the weight fee dominates.

Attack Cost Analysis

Single Channel Attack

Initial attack cost (256 messages):

256 messages × 0.000018535 AI3 = 0.00474496 AI3

Maintenance cost (assuming ~10 messages/minute to maintain the block):

10 messages/minute × 60 minutes × 0.000018535 AI3 = 0.011121 AI3/hour

Long-term costs:

• 1 day: 0.267 AI3
• 1 week: 1.87 AI3
• 1 month: ~8.12 AI3

Ten Channel Attack

Initial attack cost (256 messages × 10 channels):

2,560 messages × 0.000018535 AI3 = 0.0474496 AI3

Maintenance cost (100 messages/minute across all channels):

100 messages/minute × 60 minutes × 0.000018535 AI3 = 0.11121 AI3/hour

Long-term costs:

• 1 day: 2.67 AI3
• 1 week: 18.7 AI3
• 1 month: ~81.2 AI3

Economic Viability

The attack is economically viable because:

• The cost to completely deny service is minimal
• An attacker can sustain the attack almost indefinitely
• The damage (complete service denial) far exceeds the attack cost
• Legitimate users waste fees on failed attempts, making their costs higher than the attacker’s
• The attacker has a significant advantage with automated systems vs manual users
• There’s no mechanism to increase fees based on channel congestion
• The attack is indistinguishable from legitimate high-volume usage

Mitigation Options

The primary solution is dynamic pricing based on channel congestion. Simply reducing MAX_FUTURE_ALLOWED_NONCES would not solve the problem - an attacker can maintain a rolling window at any limit.

1. Dynamic Fee Adjustment Based on Channel Utilization

Implement a fee multiplier that increases as the channel fills with unprocessed messages:

fn calculate_dynamic_fee_multiplier(channel: &Channel) -> u32 {
    let pending_messages = channel.next_outbox_nonce - channel.latest_processed_nonce;
    let utilization = pending_messages * 100 / channel.max_outgoing_messages;
    
    match utilization {
        0..=25 => 1,      // Normal fee
        26..=50 => 5,     // 5x fee
        51..=75 => 20,    // 20x fee
        76..=90 => 100,   // 100x fee
        _ => 500,         // 500x fee for nearly full channels
    }
}

2. Future Nonce Gap Premium

Charge exponentially higher fees based on how far ahead a message’s nonce is from the current processing position:

fn calculate_future_nonce_fee(current_nonce: Nonce, message_nonce: Nonce) -> Balance {
    let nonce_gap = message_nonce - current_nonce;
    if nonce_gap <= 10 {
        base_fee
    } else {
        // Exponential increase for large gaps
        base_fee * 2u128.pow((nonce_gap / 10) as u32)
    }
}

This makes maintaining a 256-message buffer exponentially expensive, while legitimate users submitting messages with small nonce gaps pay normal fees.

3. Combined Approach

The most effective solution combines both mechanisms:

• Channel utilization fee prevents filling the outbox
• Nonce gap fee prevents maintaining large future nonce buffers
• Together they make the attack economically unviable while minimizing impact on legitimate users

Conclusion

This vulnerability represents a critical threat to the Autonomys Network’s cross-chain communication infrastructure. The attack creates a race condition where legitimate users must compete with an attacker’s automated system for nonce slots, with virtually no chance of success. The low cost and complete service denial make it an attractive attack vector that could be exploited to completely halt cross-chain operations.

The current design effectively allows an attacker to monopolize a public resource (nonce space) at minimal cost, forcing legitimate users to waste resources on failed attempts. Implementation of dynamic fee mechanisms based on both channel utilization and nonce gap distance is strongly recommended to make this attack economically unviable.

[Jim-Autonomys]

This is an exemplary report vexr, thanks for contributing!

Give us some time to triage with the engineers but it reads like a potential vulnerability to me.

[ved]

Hi @vexr

Thank you for the report.

Unfortunately, this attack vector does not exist. Let me elaborate more on this.

Future nonce check on XDM messages is included to ensure relayers does not submit too many XDM messages coming from the src_chain on dst_chain’s tx pool. What runtime does here is to allow a maximum of 256 messages per block per src_chain per channel so that remaining block space is available for the other XDMs and user related transactions.

The reason why there is no attack vector here is these nonces are not regular user transaction nonces but rather XDM message nonces.
When a user submits a transfer request from src_chain to dst_chain, that message gets a specific nonce in an incrementing order. Once the block in which this message was included is confirmed, relayers will pick the message and submit to dst_chain.

All this while other kinds of extrinsics will continue to be included in the block based on their account nonce.

So when the block is confirmed, there could multiple XDMs that needs to be relayed and relayer ideally can submit all of them. If there are 10,000 for example, it can submit all of them but entire block space is taken by these messages itself and starve the regular user transactions.

Currently all the operators of given src_chain are acting as relayers and any one of them can pick these messages and in any order of nonces and submit them. Future nonce check also ensures that malicious relayers does not submit all 9999 messages and does not submit the first message and these 9999 remain the tx_pool. We avoid this by lowering the maximum allowed nonce and keep the tx_pool relatively free.

Also note, anyone can submit these messages and these messages does not have any cost. In the extreme case where no relayers are submitting messages, other users can manually construct and submit these messages to get XDM processing going.

I hope this helps in your understanding. Please let me know if you have any further questions

[uuliao]

I admire what Vexr has done. At least I can’t. This is not a task that ordinary miners can complete. It can also be seen through this matter. A brave man will be found under a heavy reward. Through rewards, one can achieve results that ordinary people are unwilling or unable to achieve. At the same time, we also hope that the official team will consider increasing the reward amount for The Watcher’s Oath. I think The Watcher’s Oath is more meaningful than XDM test or Staking test.

[vexr]

Thanks @ved for the clarification. I appreciate you explaining the distinction between XDM message nonces and user transaction nonces - that’s a key detail I missed. The relayer architecture and how it prevents tx pool flooding makes more sense now.

Good to understand that these protections are about managing block space rather than user-facing constraints. This helps me better understand the system design for future analysis.

I’ll keep looking for vulnerabilities in the Autonomys Network with this context in mind. Thanks for taking the time to review.