TIP-1009: Expiring Nonces

Abstract

TIP-1009 introduces expiring nonces, an alternative replay protection mechanism where transactions are valid only within a specified time window. Instead of tracking sequential nonces, the protocol uses transaction hashes with expiry timestamps to prevent replay attacks. This enables use cases like gasless transactions, meta-transactions, and simplified UX where users don't need to manage nonce ordering.

Motivation

Traditional sequential nonces require careful ordering—if transaction N fails or is delayed, all subsequent transactions (N+1, N+2, ...) are blocked. This creates friction for:

1. Gasless/Meta-transactions: Relayers need complex nonce management across multiple users
2. Parallel submission: Users cannot submit multiple independent transactions simultaneously
3. Recovery from failures: Stuck transactions require explicit cancellation with the same nonce

Expiring nonces solve these problems by using time-based validity instead of sequence-based ordering. Each transaction is uniquely identified by its hash and is valid only until a specified validBefore timestamp.

Specification

Nonce Key

Expiring nonce transactions use a reserved nonce key:

TEMPO_EXPIRING_NONCE_KEY = uint256.max (2^256 - 1)

When a Tempo transaction specifies nonceKey = uint256.max, the protocol treats it as an expiring nonce transaction.

Transaction Fields

Expiring nonce transactions require:

Validity Window

The validBefore timestamp must satisfy:

now < validBefore <= now + MAX_EXPIRY_SECS

Where:

• now is the current block timestamp
• MAX_EXPIRY_SECS = 30 seconds

Transactions with validBefore in the past or more than 30 seconds in the future are rejected.

Replay Protection

Replay protection uses a circular buffer data structure in the Nonce precompile:

Storage Layout

contract Nonce {
    // Existing 2D nonce storage
    mapping(address => mapping(uint256 => uint64)) public nonces;           // slot 0
 
    // Expiring nonce storage
    mapping(bytes32 => uint64) public expiringNonceSeen;                    // slot 1: txHash => expiry
    mapping(uint32 => bytes32) public expiringNonceRing;                    // slot 2: circular buffer
    uint32 public expiringNonceRingPtr;                                     // slot 3: buffer pointer
}

Circular Buffer Design

The circular buffer has a fixed capacity:

EXPIRING_NONCE_SET_CAPACITY = 300,000

This capacity is sized for 10,000 TPS × 30 seconds = 300,000 transactions, ensuring entries expire before being overwritten.

Algorithm

When processing an expiring nonce transaction:

1. Validate expiry window: Reject if validBefore <= now or validBefore > now + 30

2. Replay check: Read expiringNonceSeen[txHash]

   • If entry exists and expiry > now, reject as replay

3. Get buffer position: Read expiringNonceRingPtr, compute idx = ptr % CAPACITY

4. Read existing entry: Read expiringNonceRing[idx] to get oldHash

5. Eviction check (safety): If oldHash != 0:

   • Read expiringNonceSeen[oldHash]
   • If expiry > now, reject (buffer full of valid entries)
   • Clear expiringNonceSeen[oldHash] = 0

6. Insert new entry:

   • Write expiringNonceRing[idx] = txHash
   • Write expiringNonceSeen[txHash] = validBefore

7. Advance pointer: Write expiringNonceRingPtr = ptr + 1

Pseudocode

function checkAndMarkExpiringNonce(
    bytes32 txHash,
    uint64 validBefore,
    uint64 now
) internal {
    // 1. Validate expiry window
    require(validBefore > now && validBefore <= now + 30, "InvalidExpiry");
 
    // 2. Replay check
    uint64 seenExpiry = expiringNonceSeen[txHash];
    require(seenExpiry == 0 || seenExpiry <= now, "Replay");
 
    // 3-4. Get buffer position and existing entry
    uint32 ptr = expiringNonceRingPtr;
    uint32 idx = ptr % CAPACITY;
    bytes32 oldHash = expiringNonceRing[idx];
 
    // 5. Eviction check (safety)
    if (oldHash != bytes32(0)) {
        uint64 oldExpiry = expiringNonceSeen[oldHash];
        require(oldExpiry == 0 || oldExpiry <= now, "BufferFull");
        expiringNonceSeen[oldHash] = 0;
    }
 
    // 6. Insert new entry
    expiringNonceRing[idx] = txHash;
    expiringNonceSeen[txHash] = validBefore;
 
    // 7. Advance pointer
    expiringNonceRingPtr = ptr + 1;
}

Gas Costs

The intrinsic gas cost for expiring nonce transactions includes:

EXPIRING_NONCE_GAS = 2 * COLD_SLOAD_COST + WARM_SLOAD_COST + 3 * WARM_SSTORE_RESET
                   = 2 * 2100 + 100 + 3 * 2900
                   = 13,000 gas

Included operations:

• 2 cold SLOADs: seen[txHash], ring[idx] (unique slots per tx)
• 1 warm SLOAD: seen[oldHash] (warm because we just read ring[idx] which points to it)
• 3 SSTOREs at RESET price: seen[oldHash]=0, ring[idx], seen[txHash]

Excluded operations (amortized):

• ring_ptr SLOAD/SSTORE: Accessed by almost every expiring nonce tx in a block, so amortized cost approaches ~200 gas. May be moved out of EVM storage in the future.

Why SSTORE_RESET (2,900) instead of SSTORE_SET (20,000) for seen[txHash]:

• SSTORE_SET cost exists to penalize permanent state growth
• Expiring nonce data is ephemeral: evicted within 30 seconds, fixed-size buffer (300k entries)
• No permanent state growth, so the 20k penalty doesn't apply

Transaction Pool Validation

The transaction pool performs preliminary validation:

1. Verify nonceKey == uint256.max
2. Verify nonce == 0
3. Verify validBefore is present
4. Verify validBefore > currentTime (not expired)
5. Verify validBefore <= currentTime + MAX_EXPIRY_SECS (within window)
6. Query expiringNonceSeen[txHash] storage slot to check for existing entry

Transactions failing these checks are rejected before entering the pool.

Interaction with Other Features

2D Nonces

Expiring nonces and 2D nonces are mutually exclusive:

• nonceKey = 0: Protocol nonce (standard sequential)
• nonceKey = 1..uint256.max-1: 2D nonce keys
• nonceKey = uint256.max: Expiring nonce mode

Access Keys (Keychain)

Expiring nonces work with access key signatures. The validBefore provides an additional security boundary—even if an access key is compromised, transactions signed with it become invalid after the expiry window.

Fee Tokens

Expiring nonce transactions pay fees in TIP-20 fee tokens like any other Tempo transaction.

Invariants

Must Hold

Invariant Tests

These invariants are tested in the Foundry invariant test suite (TempoTransactionInvariant.t.sol):

Test Cases

1. Basic flow: Submit transaction, verify execution, attempt replay (should fail)

2. Expiry validation:

   • validBefore in past → reject
   • validBefore = now → reject
   • validBefore = now + 31 → reject
   • validBefore = now + 30 → accept

3. Nonce validation:

   • nonce = 0 → accept
   • nonce > 0 → reject

4. Required fields:

   • validBefore missing → reject
   • nonceKey != uint256.max → not expiring nonce (uses 2D nonce rules)

5. Post-expiry replay: Submit tx, wait for expiry, submit same tx with new validBefore (should succeed)

6. Buffer eviction: Fill buffer, verify old entries are evicted when expired

7. Concurrent transactions: Submit multiple transactions with same validBefore, verify all succeed

Benchmark Results

Benchmarks were run to measure state savings from expiring nonces compared to 2D nonces.

Key Findings

Controlled Benchmark (100k transactions at 5k TPS)

The ~107 bytes per transaction overhead includes MPT node overhead, MDBX metadata, and RLP encoding.

Scaling Projections

After the circular buffer fills, expiring nonces maintain constant storage while 2D nonces grow by ~100 bytes per transaction.

Open Questions

Safety Check for Buffer Eviction

The current implementation includes a safety check that reads expiringNonceSeen[oldHash] before evicting an entry from the ring buffer. This check verifies the entry is actually expired before overwriting.

Rationale for keeping the check:

• Protects against unexpected TPS spikes that could cause the buffer to fill with valid entries
• Defense-in-depth: prevents replay attacks if capacity assumptions are violated
• Cost is only incurred in the rare case when eviction is needed

Rationale for removing the check:

• The buffer is sized (300k entries) to guarantee entries expire before being overwritten at 10k TPS
• Removes 1 SLOAD (2,100 gas) from the critical path
• Simplifies the algorithm

Current decision: Keep the check but exclude it from gas accounting (charged as if it won't trigger in normal operation).

Question: Should this safety check be:

1. Kept with current gas accounting (not charged for the extra SLOAD)?
2. Removed entirely, trusting the capacity sizing?
3. Kept and fully charged (add 2,100 gas to EXPIRING_NONCE_GAS)?

Buffer Capacity Sizing

The current capacity of 300,000 assumes:

• Maximum 10,000 TPS sustained
• 30 second expiry window

Question: Should the capacity be configurable per-chain or hardcoded? What happens if TPS requirements increase significantly?

Transaction Hash Computation

The transaction hash used for replay protection must be computed before signature recovery.

Question: Should the spec explicitly define the hash computation (which fields, encoding) or reference the Tempo Transaction spec?