Nonce Management

Overview

Nonces (numbers used once) prevent replay attacks by ensuring each signed order can only be executed once. Frontier Chain uses timestamp-based nonces that enable parallel order submission while maintaining strong replay protection.

Key Features:

• Timestamp-Based: Millisecond-precision Unix timestamps

• Parallel Submissions: No sequential ordering required

• 100-Nonce Window: Tracks highest 100 nonces per user

• Time Bounds: Valid within 2-day past to 1-day future

• Per-User Tracking: Independent nonce spaces for each user/agent

---

How Nonces Work

Basic Concept

Without Nonces:

User signs order: "Buy 1 BTC at $90,000"
→ Order executes
→ Attacker copies signature
→ Attacker submits same signed order
→ Order executes again! (replay attack)

With Nonces:

User signs order: "Buy 1 BTC at $90,000, nonce: 1678901234567"
→ Order executes, nonce recorded
→ Attacker copies signature
→ Attacker submits same signed order
→ Rejected! Nonce already used

---

Timestamp-Based Nonces

Why Timestamps?

Traditional sequential nonces (0, 1, 2, 3...) require strict ordering:

Problem with Sequential:
Order 1 (nonce 5) arrives
Order 2 (nonce 3) arrives → Rejected! (lower than 5)
Order 3 (nonce 4) arrives → Rejected! (lower than 5)

Only increasing nonces accepted → Kills parallel submission

Timestamp nonces allow parallel submission:

With Timestamps:
Order 1 (nonce 1678901234567) arrives → Accepted
Order 2 (nonce 1678901234568) arrives → Accepted (parallel)
Order 3 (nonce 1678901234569) arrives → Accepted (parallel)

All unique timestamps → All accepted → Parallel submission works!

---

Nonce Format

Millisecond Unix Timestamp:

Current time: March 15, 2024, 10:30:45.678 UTC
Unix timestamp: 1678901445678

Nonce value: 1678901445678  (milliseconds since epoch)

Generation (JavaScript):

const nonce = Date.now();  // Current time in milliseconds
// Example: 1678901445678

Generation (Python):

import time
nonce = int(time.time() * 1000)  # Milliseconds
# Example: 1678901445678

Generation (Rust):

use std::time::{SystemTime, UNIX_EPOCH};

let nonce = SystemTime::now()
    .duration_since(UNIX_EPOCH)
    .unwrap()
    .as_millis() as u64;

---

Nonce Validation Rules

Uniqueness Check

Rule: Nonce must not exist in user's 100-nonce window

User's nonce history: [1678901234567, 1678901245678, ...]

New order nonce: 1678901234567
→ Rejected! Already used

New order nonce: 1678901256789
→ Accepted! Not in history
→ Added to history

---

Minimum Nonce Check

Rule: Nonce must be higher than lowest stored nonce

User's 100 nonces:
Lowest:  1678900000000
Highest: 1678901234567

New order nonce: 1678899999999
→ Rejected! Lower than minimum

New order nonce: 1678901000000
→ Accepted! Higher than minimum

Purpose: Prevents very old nonces from being used after window rotates

---

Time Bounds Check

Past Bound: Within 2 days of current time

Current time: 1678901234567
Two days ago: 1678901234567 - (2 * 24 * 60 * 60 * 1000)
            = 1678728034567

Nonce: 1678700000000
→ Rejected! Too old (>2 days ago)

Nonce: 1678800000000
→ Accepted! Within 2 days

Future Bound: Not more than 1 day in future

Current time: 1678901234567
One day ahead: 1678901234567 + (1 * 24 * 60 * 60 * 1000)
             = 1678987634567

Nonce: 1679000000000
→ Rejected! Too far in future (>1 day)

Nonce: 1678950000000
→ Accepted! Within 1 day

---

100-Nonce Window

Why 100 Nonces?

Memory Efficiency:

• Only store most recent 100 nonces

• Older nonces automatically dropped

• Prevents unbounded growth

• O(1) insertion/lookup with BTreeSet

Practical Capacity:

• 100 unique millisecond timestamps

• 100ms minimum spacing needed

• Effective capacity: 10 seconds of continuous submissions

• More than sufficient for high-frequency trading

---

Window Management

Insertion:

Current window (size 100): [nonce1, nonce2, ..., nonce100]

New nonce arrives: nonce101
→ Add nonce101
→ Window now size 101
→ Remove oldest (nonce1)
→ Window back to size 100

Automatic Cleanup:

// From codebase
user_nonces.insert(nonce);
while user_nonces.len() > 100 {
    let min = *user_nonces.iter().next().unwrap();
    user_nonces.remove(&min);
}

---

Per-User Nonce Tracking

Independent Nonce Spaces

Each user (and each agent) has independent nonce tracking:

Structure:

User A → [nonce_a1, nonce_a2, ..., nonce_a100]
User B → [nonce_b1, nonce_b2, ..., nonce_b100]
Agent X → [nonce_x1, nonce_x2, ..., nonce_x100]

Benefits:

User A uses nonce 1678901234567 → Accepted
User B uses nonce 1678901234567 → Also accepted!
→ Different users, different nonce spaces
→ No conflicts

---

Agent Nonce Tracking

Each agent wallet has its own nonce tracker:

Main Wallet → NonceTracker 1
Agent Wallet A → NonceTracker 2
Agent Wallet B → NonceTracker 3

All independent!
→ Parallel submissions from different agents
→ No coordination needed

---

Replay Attack Prevention

Scenario: Attacker Captures Signature

1. User signs order with nonce 1678901234567
2. Order submitted and executes successfully
3. Nonce 1678901234567 recorded in user's history
4. Attacker captures signed order (eavesdropping)
5. Attacker tries to submit same order
6. System checks nonce 1678901234567
7. Already in history → Rejected!
8. Replay attack prevented

---

Scenario: Attacker Modifies Nonce

1. Attacker captures signed order
2. Attacker changes nonce to new value
3. Attacker submits modified order
4. System verifies signature
5. Signature invalid! (data modified)
6. Order rejected
7. Attack prevented (signature binds nonce to order)

---

Parallel Order Submission

High-Frequency Trading

Timestamp nonces enable parallel submissions:

Time: 10:30:45.100 → Submit order (nonce: ...45100)
Time: 10:30:45.150 → Submit order (nonce: ...45150)
Time: 10:30:45.200 → Submit order (nonce: ...45200)
Time: 10:30:45.250 → Submit order (nonce: ...45250)

All submitted in parallel:
→ All have unique timestamps
→ All accepted
→ No waiting for sequential order
→ High-frequency trading enabled

---

Multiple Agents

Different agents can submit in parallel:

Agent A at 10:30:45.100 → nonce ...45100 → Accepted
Agent B at 10:30:45.100 → nonce ...45100 → Also accepted!
→ Different nonce trackers
→ No conflict
→ Parallel execution

---

Best Practices

Nonce Generation

Do:

• Use current timestamp in milliseconds

• Generate fresh nonce for each order

• Use system time (Date.now(), time.time() * 1000)

• Add small random offset if submitting multiple orders per millisecond

Don't:

• Reuse nonces

• Use sequential counters

• Generate nonces far in future

• Use hardcoded values

---

Example: Multiple Orders Same Millisecond

// If submitting multiple orders in same millisecond:
const baseNonce = Date.now();
const order1Nonce = baseNonce;
const order2Nonce = baseNonce + 1;  // Add 1ms
const order3Nonce = baseNonce + 2;  // Add 2ms

// All unique, all accepted

---

Common Issues

"Nonce Already Used"

Cause: Submitting order with previously used nonce

Solutions:

1. Generate new timestamp: Date.now()

2. Don't reuse nonces

3. Check nonce isn't in recent history

4. Ensure clock is synchronized

---

"Nonce Too Low"

Cause: Nonce lower than minimum in 100-nonce window

Solutions:

1. Use current timestamp (not old value)

2. Check system clock is correct

3. Don't use cached/stored nonces

4. Generate fresh nonce

---

"Nonce Too Old"

Cause: Nonce more than 2 days in past

Solutions:

1. Check system clock is accurate

2. Use Date.now() not stored value

3. Synchronize system time (NTP)

4. Don't use very old nonces

---

"Nonce Too Far in Future"

Cause: Nonce more than 1 day ahead

Solutions:

1. Check system clock is accurate

2. Don't add large offsets to timestamp

3. Synchronize system time

4. Use actual current time

---

Edge Cases

Clock Skew

Problem: Different clocks may differ slightly

Mitigation:

• 1-day future bound provides buffer

• 2-day past bound provides buffer

• Validators use their own clocks

• Small skew (<1 minute) not an issue

---

Millisecond Collisions

Problem: Two orders same millisecond

Solutions:

1. Add small offset (+1ms, +2ms)

2. Most systems have microsecond precision

3. Rare in practice

4. Even if collision, different signatures

---

Window Rotation

Scenario:

Submit order with nonce N
→ Accepted, added to window
→ Submit 100 more orders
→ Window rotates, nonce N dropped
→ Submit order with nonce N again
→ Accepted! (no longer in window)

Protection:

• Time bounds prevent this

• Nonce N now >100 milliseconds old

• Would need 100+ orders in 100ms to trigger

• 1000+ orders/second needed

• Beyond typical use case

• Time bounds provide additional protection

---

Technical Implementation

Data Structure (from codebase)

pub struct NonceTracker {
    // BTreeSet for sorted, efficient operations
    nonces: HashMap<UserId, BTreeSet<u64>>,
}

Operations:

• Insert: O(log n)

• Contains: O(log n)

• Remove minimum: O(log n)

• All efficient for 100-item window

---

Validation Algorithm

pub fn validate_nonce(
    &mut self,
    user: UserId,
    nonce: u64,
    current_time: u64,
) -> Result<(), NonceError> {
    let user_nonces = self.nonces.entry(user).or_default();

    // 1. Check uniqueness
    if user_nonces.contains(&nonce) {
        return Err(NonceError::NonceAlreadyUsed);
    }

    // 2. Check minimum
    if let Some(&min_nonce) = user_nonces.iter().next() {
        if nonce <= min_nonce {
            return Err(NonceError::NonceTooLow);
        }
    }

    // 3. Check time bounds
    let two_days_ms = 2 * 24 * 60 * 60 * 1000;
    let one_day_ms = 24 * 60 * 60 * 1000;

    if nonce < current_time.saturating_sub(two_days_ms) {
        return Err(NonceError::NonceTooOld);
    }

    if nonce > current_time.saturating_add(one_day_ms) {
        return Err(NonceError::NonceTooFarInFuture);
    }

    // 4. Add and maintain window
    user_nonces.insert(nonce);
    while user_nonces.len() > 100 {
        let min = *user_nonces.iter().next().unwrap();
        user_nonces.remove(&min);
    }

    Ok(())
}

---

Comparison: Sequential vs Timestamp Nonces

Sequential Nonces

How They Work:

Nonce 0 → Accepted
Nonce 1 → Accepted
Nonce 2 → Accepted
Nonce 1 → Rejected (already used)
Nonce 3 → Accepted
Nonce 2 → Rejected (too low)

Limitations:

• Must submit in order

• No parallel submissions

• Network delays cause problems

• Nonce gaps break submission

---

Timestamp Nonces (Our Approach)

How They Work:

Nonce 1678901234567 → Accepted
Nonce 1678901234568 → Accepted (parallel)
Nonce 1678901234569 → Accepted (parallel)
Nonce 1678901234567 → Rejected (duplicate)
Nonce 1678901234570 → Accepted

Advantages:

• Parallel submissions work

• Order doesn't matter

• Network delays tolerated

• High-frequency trading enabled

---

Conclusion

Timestamp-based nonces provide robust replay protection while enabling high-frequency trading. The combination of unique timestamps, time bounds, and per-user tracking creates a secure, performant nonce management system.

Key Takeaways:

• Use millisecond timestamps as nonces

• Each user/agent has independent nonce space

• 100-nonce window prevents replay attacks

• Time bounds add additional protection

• Enables parallel order submission

Next Steps:

EIP-712 SigningAgent WalletsAuthentication