--- id: TIP-1077 title: Expiring Nonce Time Wheel description: Replaces the expiring nonce ring pointer with a bounded time-wheel replay table sized for 20k TPS and a 5-minute expiry window. authors: Brian Picciano, Tanishk Goyal status: Draft related: TIP-1000, TIP-1009, TIP-1060, TIP-1073 protocolVersion: TBD --- # TIP-1077: Expiring Nonce Time Wheel ## Abstract This TIP replaces TIP-1009's expiring nonce circular buffer with a fixed time-wheel replay table and increases the maximum expiring nonce validity window from 30 seconds to 5 minutes. `valid_before` selects one of 301 reusable time buckets, and the sender-scoped transaction replay hash directly selects a deterministic probe path inside that bucket. The table is sized at 131,072 cells per bucket, for 39,452,672 total cells. A fully populated table is 1.18 GiB of cell values, or 2.35 GiB when counted as `(storage slot, storage value)` pairs. ## Motivation The current expiring nonce ring design keeps replay state bounded, but every accepted transaction updates a global append structure. The common steady-state path reads and writes several storage locations: `seen[hash]`, `ring[ptr]`, `seen[old_hash]`, and the ring pointer. The global pointer also complicates payload-builder prewarming because the storage slot touched by a transaction depends on how many expiring nonce transactions came before it in the block. The time wheel keeps replay state bounded without a global append pointer. The common path is a read and write of one replay-table cell derived from transaction contents, so the builder can prewarm the first cell directly from `(replay_hash, valid_before)`. Replay cells use a reserved direct storage range rather than Solidity mapping layout, so probing a cell does not require a mapping-slot hash. Increasing the validity window to 5 minutes gives partners and relayers more flexibility around submission, batching, and network delay without requiring them to continuously refresh signatures inside a 30 second window. ## Assumptions 1. Expiring nonce transactions use the TIP-1077 validity window: `block.timestamp < valid_before <= block.timestamp + 300`. 2. Block timestamps are monotonically nondecreasing across canonical blocks. 3. Replay hashes are uniformly distributed enough that bucket positions are random for operational sizing. Adversaries can grind transaction contents, so probe exhaustion remains a consensus error rather than an impossible case. 4. The target load for this parameter set is 20,000 expiring nonce transactions per second, sustained over the 5-minute validity window. 5. Traffic is assumed to be roughly constant over the 300 valid `valid_before` seconds. A workload that intentionally concentrates all transactions into one exact `valid_before` second is still accepted probabilistically, but has higher collision pressure. 6. Expiring nonce replay cells are bounded temporary protocol state. They do not pay TIP-1000 permanent new-slot pricing on first touch and do not mint or consume TIP-1060 storage credits. If the target TPS assumption is exceeded for long periods, collision frequency and probe-exhausted rejections increase. A future TIP can raise `EXPIRING_NONCE_BUCKET_CAPACITY` without changing the replay algorithm. ## Threat Model Users and relayers are untrusted. They may replay old signed transactions, submit many independent expiring nonce transactions with the same `valid_before`, or grind transaction contents to seek cell collisions. Builders and validators are untrusted for transaction ordering but trusted to execute the canonical state transition rules. A block containing a replay, an expired expiring nonce transaction, or a transaction whose probe path is exhausted is invalid. --- # Specification ## Constants ```text PRE_TIP_1077_MAX_EXPIRY_SECS = 30 EXPIRING_NONCE_MAX_EXPIRY_SECS = 300 EXPIRING_NONCE_BUCKET_COUNT = 301 EXPIRING_NONCE_BUCKET_CAPACITY = 131_072 EXPIRING_NONCE_MAX_PROBES = 32 EXPIRING_NONCE_CELL_COUNT = 39_452_672 EXPIRING_NONCE_CELL_BASE_SLOT = 0x387ee7e371ffafdf29537b927a83c9af016eb1493da1fe163fab229fa2400000 EXPIRING_NONCE_CELL_END_SLOT = 0x387ee7e371ffafdf29537b927a83c9af016eb1493da1fe163fab229fa499ffff EXPIRING_NONCE_CELL_SLOT_DOMAIN = "tempo.expiringNonceCells.v1" EXPIRING_NONCE_FINGERPRINT_BITS = 192 ``` `EXPIRING_NONCE_MAX_EXPIRY_SECS` increases TIP-1009's maximum expiry from 30 seconds to 300 seconds. `PRE_TIP_1077_MAX_EXPIRY_SECS` is used only by the hardfork migration dual-check for old ring entries. `EXPIRING_NONCE_BUCKET_COUNT` MUST be greater than `EXPIRING_NONCE_MAX_EXPIRY_SECS`. `EXPIRING_NONCE_BUCKET_CAPACITY` MUST be a power of two. `EXPIRING_NONCE_CELL_COUNT` MUST equal `EXPIRING_NONCE_BUCKET_COUNT * EXPIRING_NONCE_BUCKET_CAPACITY`. `EXPIRING_NONCE_CELL_BASE_SLOT` is the fixed direct-range base derived from `keccak256(EXPIRING_NONCE_CELL_SLOT_DOMAIN)` by clearing the low 22 bits. `EXPIRING_NONCE_CELL_END_SLOT` is `EXPIRING_NONCE_CELL_BASE_SLOT + EXPIRING_NONCE_CELL_COUNT - 1`. The domain documents how the range was selected; implementations MUST use the fixed constants and MUST NOT compute this hash while processing transactions. ## Storage Layout The Nonce precompile keeps the existing 2D nonce mapping and reserves a direct replay-cell storage range: ```solidity contract Nonce { mapping(address => mapping(uint256 => uint64)) public nonces; // slot 0 // Slots 1, 2, and 3 are reserved for the pre-TIP-1077 expiring nonce // seen mapping, ring mapping, and ring pointer. } ``` Replay cells are not stored in a Solidity-style mapping. For `cell_id` in `[0, EXPIRING_NONCE_CELL_COUNT)`, the corresponding storage slot is: ```text cell_slot = EXPIRING_NONCE_CELL_BASE_SLOT + cell_id ``` The inclusive slot range `[EXPIRING_NONCE_CELL_BASE_SLOT, EXPIRING_NONCE_CELL_END_SLOT]` is reserved forever for expiring nonce replay cells. Future Nonce precompile fields MUST NOT be assigned inside this range. Mapping-derived slots are assumed collision-resistant under the same Keccak preimage assumptions as Solidity mapping layout. Each replay cell stores: ```text cell = valid_before_u64 || replay_fingerprint_192 ``` where: ```text stored_valid_before = high 64 bits of cell stored_fingerprint = low 192 bits of cell fingerprint = low 192 bits of H ``` A zero storage word has `stored_valid_before == 0` and is reusable. Slots 1, 2, and 3 MUST remain reserved forever unless a later hardfork explicitly migrates or clears the old ring state. Reusing those slots for unrelated fields risks reading stale pre-fork data. ## Cell Selection Let: ```text H = sender-scoped expiring nonce replay hash V = tx.valid_before T = block.timestamp ``` `H` MUST be the canonical protocol-computed replay hash, `keccak256(encode_for_signing || sender)`. It is not user-provided input. The transaction first chooses its time bucket: ```text bucket = V % EXPIRING_NONCE_BUCKET_COUNT ``` It then chooses a deterministic probe path inside that bucket: ```text home = uint32_be(H[0..4]) % EXPIRING_NONCE_BUCKET_CAPACITY step = (uint32_be(H[4..8]) | 1) % EXPIRING_NONCE_BUCKET_CAPACITY ``` For probe `i`: ```text position_i = (home + i * step) % EXPIRING_NONCE_BUCKET_CAPACITY cell_id_i = bucket * EXPIRING_NONCE_BUCKET_CAPACITY + position_i slot_i = EXPIRING_NONCE_CELL_BASE_SLOT + cell_id_i ``` `step` is forced odd so that, with power-of-two bucket capacity, the probe path can cycle through the bucket instead of being trapped in a smaller divisor-sized subset. Since `EXPIRING_NONCE_BUCKET_CAPACITY` is a power of two, implementations MAY use bit masks instead of modulo operations for `home`, `step`, and `position_i`. ## Replay Algorithm An expiring nonce transaction MUST satisfy the TIP-1009 transaction constraints as updated by this TIP: ```text tx.nonce_key == TEMPO_EXPIRING_NONCE_KEY tx.nonce == 0 V is present T < V <= T + EXPIRING_NONCE_MAX_EXPIRY_SECS ``` Then the Nonce precompile executes: ```text fingerprint = H[8..32] for i in 0..EXPIRING_NONCE_MAX_PROBES: cell_id = cell_id_i slot = EXPIRING_NONCE_CELL_BASE_SLOT + cell_id word = sload(slot) stored_v = high_64_bits(word) stored_f = low_192_bits(word) if stored_v != V: sstore(slot, V || fingerprint) accept if stored_f == fingerprint: reject ExpiringNonceReplay continue reject ExpiringNonceSetFull ``` `stored_v != V` is safe to overwrite because the bucket count is larger than the expiry window. Two different `valid_before` values in the same bucket differ by at least 301 seconds, while expiring nonce transactions are live for at most 300 seconds. `ExpiringNonceSetFull` means the transaction's own deterministic probe path is full of different live fingerprints for the same `valid_before`. Under the time-wheel design this is local congestion, not global table exhaustion. ## Gas Pricing Expiring nonce bookkeeping is charged as explicit AA intrinsic regular gas, not by relying on dynamic metering inside the precompile storage provider. The common first-cell path is one cold read and one reset-price write: ```text EXPIRING_NONCE_BASE_GAS = COLD_SLOAD_COST + WARM_SSTORE_RESET = 2_100 + 2_900 = 5_000 ``` For an accepted transaction, let `probes` be the number of replay cells read before the transaction is accepted. Implementations MUST charge: ```text EXPIRING_NONCE_GAS(probes) = EXPIRING_NONCE_BASE_GAS + (probes - 1) * COLD_SLOAD_COST = probes * 2_100 + 2_900 ``` Examples: | Probe count | Expiring nonce gas | | ---: | ---: | | 1 | 5,000 | | 2 | 7,100 | | 32 | 70,100 | This charge intentionally does not apply TIP-1000 permanent new-slot pricing to first-touch replay cells. Expiring nonce cells are bounded temporary protocol state, not user-created permanent state. The maximum table footprint is capped by `EXPIRING_NONCE_BUCKET_COUNT * EXPIRING_NONCE_BUCKET_CAPACITY`. The replay insertion function MUST return the accepted probe count, and the EVM handler MUST charge the formula above explicitly as regular gas while keeping replay-cell writes exempt from TIP-1000/TIP-1060 state accounting. With the chosen capacity and the 20k TPS sizing assumption, the expected accepted transaction reads about 1.085 cells and pays about 5,179 gas for TIP-1077 replay bookkeeping. No expiring nonce insertion or later overwrite mints or consumes TIP-1060 storage credits. The time-wheel lookup performs no Keccak beyond the canonical replay hash `H`. If `H` has already been computed by transaction validation or pool deduplication, deriving `bucket`, `home`, `step`, `fingerprint`, `cell_id`, and `slot` requires only slicing and arithmetic: ```text steady-state lookup keccaks after H = 0 steady-state lookup keccaks total = 1, if H must be computed ``` During the temporary hardfork migration dual-check, implementations still perform the old `expiringNonceSeen[H]` mapping lookup until `old_seen_cutoff`; that compatibility check adds one old mapping-slot hash and one extra cold read during the migration window only. Transactions accepted during that window therefore pay: ```text EXPIRING_NONCE_MIGRATION_GAS(probes) = EXPIRING_NONCE_GAS(probes) + COLD_SLOAD_COST = EXPIRING_NONCE_GAS(probes) + 2_100 ``` ## Parameter Selection At 20,000 expiring nonce transactions per second and a 5-minute validity window, the live replay set is: ```text 20_000 * 300 = 6_000_000 records ``` The time wheel does not size one bucket for all 6 million live records. With constant load across the 300 valid `valid_before` seconds, each exact `valid_before` bucket receives about 20,000 records: ```text 6_000_000 / 300 = 20_000 records per live bucket ``` The bucket count must be greater than the maximum expiry window so that two different `valid_before` values in the same bucket cannot both be live: ```text minimum bucket count = EXPIRING_NONCE_MAX_EXPIRY_SECS + 1 = 300 + 1 = 301 ``` The wheel has two independent dimensions: - `EXPIRING_NONCE_BUCKET_COUNT` separates expiry seconds. It only needs to be greater than the maximum expiry window, so 301 buckets covers a 300 second window. - `EXPIRING_NONCE_BUCKET_CAPACITY` controls collision probability within one exact `valid_before` second. This value must be a power of two so the odd probe step can cover every cell in the bucket. Rounding the time-bucket count from 301 to 512 would not reduce same-second collisions: each exact `valid_before` second would still use one bucket with 131,072 cells. It would only reserve 211 additional time buckets, increasing the 131,072-cell full-table footprint from 2.35 GiB to 4.00 GiB. The table below models random hash placement inside one bucket. `Slot+value bloat` counts the full logical table as `(storage slot, storage value)` pairs: ```text slot+value bytes = 301 buckets * cells_per_bucket * 64 ``` | Cells per bucket | Load at 20k TPS | First-cell collisions per 20k txs | Avg probes per tx | Max slot+value bloat | | ---: | ---: | ---: | ---: | ---: | | 16,777,216 | 0.12% | ~12 | 1.0006 | 301.00 GiB | | 1,048,576 | 1.91% | ~190 | 1.0097 | 18.81 GiB | | 524,288 | 3.81% | ~377 | 1.0196 | 9.41 GiB | | 262,144 | 7.63% | ~744 | 1.0402 | 4.70 GiB | | 131,072 | 15.26% | ~1,451 | 1.0851 | 2.35 GiB | | 65,536 | 30.52% | ~2,764 | 1.1931 | 1.18 GiB | | 32,768 | 61.04% | ~5,030 | 1.5442 | 602.00 MiB | | 25,000 | 80.00% | ~6,233 | 2.0118 | 459.29 MiB | | 20,000 | 100.00% | ~7,358 | unstable | 367.43 MiB | | 16,384 | 122.07% | ~8,450 | overloaded | 301.00 MiB | This TIP chooses 301 time buckets and 131,072 cells per bucket. The bucket count is the minimum that preserves the cheap expiry proof for a 300 second window, and the cell count keeps the per-`valid_before` load at 15.26% with an average accepted path of about 1.085 probes at 20k TPS. Smaller tables reduce the maximum footprint but increase average reads and tail risk. In particular, 65,536 cells per bucket would halve the footprint to 1.18 GiB but double load to 30.52%, and 32,768 cells per bucket pushes load above 60%, where probe length and probe-exhaustion risk become much more sensitive to traffic bursts or adversarial hash selection. Larger tables reduce collisions but mostly buy marginal latency improvement at the cost of much larger bounded state. The 16,777,216-cell parameter explored in implementation experiments has negligible collisions but a 301 GiB slot+value full-table footprint with a 5-minute window. ## Hardfork Migration Before this TIP activates, expiring nonce replay state is stored in the TIP-1009 ring layout: ```text slot 1: expiringNonceSeen[hash] -> expiry slot 2: expiringNonceRing[index] -> hash slot 3: expiringNonceRingPtr ``` At the activation block: 1. New expiring nonce insertions MUST use the direct replay-cell slot range `[EXPIRING_NONCE_CELL_BASE_SLOT, EXPIRING_NONCE_CELL_END_SLOT]`. 2. The old ring pointer, ring mapping, and seen mapping MUST NOT be updated. 3. Slots 1, 2, and 3 MUST remain reserved. 4. Payload-builder prewarming MUST switch to the time-wheel first-cell slot. 5. Expiry-window validation MUST switch from `block.timestamp + 30` to `block.timestamp + 300`. Transactions with `valid_before` more than 30 seconds but no more than 300 seconds in the future are valid only in blocks at or after activation. The transaction pool can keep deduplicating expiring nonce transactions by `H`. Today it also uses the unique `expiringNonceSeen[H]` slot to notice when a pooled transaction was included. With TIP-1077 there is no unique per-transaction slot: each transaction has a probe path through shared replay cells, and another transaction may write a different fingerprint into one of those cells. If the pool keeps inclusion tracking from state updates, it should watch the probe-path cells and remove a transaction only when the written word is that transaction's exact `V || H[8..32]` value, not merely because a watched cell became non-zero. To preserve replay protection across the hardfork boundary, implementations MUST perform a temporary dual replay check: ```text activation_timestamp = timestamp of the first block executing TIP-1077 old_seen_cutoff = activation_timestamp + PRE_TIP_1077_MAX_EXPIRY_SECS if block.timestamp <= old_seen_cutoff: reject if old_expiringNonceSeen[H] > block.timestamp always: check and mark the TIP-1077 time-wheel cell ``` The old ring only contains transactions accepted under TIP-1009's 30 second maximum expiry, so the dual-check cutoff uses `PRE_TIP_1077_MAX_EXPIRY_SECS` rather than the new 300 second window. After `old_seen_cutoff`, every transaction recorded only in the old ring layout must have expired, so the old seen mapping is no longer needed for replay validation. The hardfork does not need to enumerate or delete old ring state. The old slots become orphaned reserved state. A later state-cleanup hardfork MAY clear them, but replay safety does not depend on that cleanup. ## Alternatives Considered ### Keep The Circular Ring The ring has a small bounded footprint and was simple to reason about at lower TPS. A 300,000-entry ring supports roughly 10k TPS over a 30 second window. At 20k TPS over a 5-minute window, the ring must grow to at least 6,000,000 live entries. Because the design stores both `ring[index] -> hash` and `seen[hash] -> expiry`, that is roughly 12 million storage words before database overhead. The larger issue is not only size: every accepted transaction still depends on a global insertion pointer and performs multiple replay and eviction storage operations. A pointer that lands on a still-live entry can also create global backpressure until time advances. ### Plain Mapping With Cleanup A plain mapping: ```text expiringNonceSeen[hash] = expiry ``` is the simplest replay data structure. It removes the ring pointer and has a cheap replay lookup. It is not self-bounded. Solidity-style mappings are not enumerable, so expired entries require an external index, offchain block scanning, or a protocol cleanup service. At 20k TPS, cleanup must eventually delete 20,000 entries per second. If cleanup mints transferable storage credits, it creates gas-token-like incentives unless the original transaction prepaid the full future credit and cleanup execution cost. If cleanup is subsidized by the protocol, the cost is hidden rather than removed. This TIP rejects the plain mapping design because expiring nonce replay safety should not depend on a high-throughput cleanup market or service. ### Plain Mapping With TIP-1073-Style Refunds The mapping design can be paired with prepaid cleanup budget and permissionless pruning, similar to temporary access-key state. That model is better than transferable credits because the refund is bounded and same-transaction. It is still a poor fit for expiring nonces because each expiring nonce transaction creates exactly one future cleanup item. Cleanup becomes a second write-heavy transaction stream at the same order of magnitude as user traffic. Access-key pruning has low volume and long TTLs. Expiring nonce replay state has high volume and a 5-minute TTL. The time wheel handles that by reusing cells without explicit deletion. ### Hash Modulo Fixed Table A fixed table indexed by: ```text index = replay_hash % capacity ``` does not provide enough capacity without probing. With one slot per index, two different live transactions that map to the same index cannot both be accepted. At 20k TPS, the 5-minute live window contains about 6,000,000 records, so a 300,000-slot table is overloaded. Adding probing makes the design closer to the time wheel, but without the cheap time-bucket proof. The implementation must read occupied cells and compare expiries to determine whether they are reusable. The time wheel instead makes `stored_valid_before != current_valid_before` a proof of expiry inside the selected bucket. ### More Time Buckets With One Cell Each Increasing the number of time buckets does not increase active throughput when each bucket has one cell. Only 300 `valid_before` seconds are live at once, so one cell per bucket allows at most about 300 live expiring nonce transactions before collisions force rejection. Bucket count provides expiry separation. Bucket capacity provides throughput within one expiry second. Both are required. ### Solidity-Style Replay Cell Mapping The time wheel could store cells in a flat Solidity-style mapping: ```text expiringNonceCells[cell_id] = valid_before || fingerprint ``` This keeps the storage layout familiar, but every probed cell requires computing `keccak256(cell_id || mapping_slot)` before the `SLOAD`. At the chosen capacity, the expected accepted transaction reads about 1.085 cells, so mapping layout would add about 1.085 Keccak computations per accepted transaction on average and up to 32 in the worst probe path. The direct slot range preserves the same bounded table and probe behavior while making each probe slot derivable with integer addition. ### Larger Time Wheel A larger time wheel reduces collisions and makes first-cell prewarming more reliable. The 16,777,216-cell-per-bucket design has an expected first-cell collision rate near zero at 20k TPS. Its cost is a much larger bounded state footprint: 301 GiB when counted as slot+value pairs. It also creates a long first-touch period where most transactions write previously empty cells. This TIP chooses a smaller 2.35 GiB slot+value footprint and accepts a modest average probe rate instead. # Observability No new EVM events are required. Expiring nonce replay protection is a consensus validity rule, and emitting an event for every replay-cell write would add unnecessary receipt volume. Nodes SHOULD expose metrics for: | Metric | Purpose | | --- | --- | | `expiring_nonce_probe_count` | Distribution of probes per accepted transaction | | `expiring_nonce_first_cell_hit_total` | Common-path hit rate for builder prewarming | | `expiring_nonce_probe_exhausted_total` | Collision or attack pressure | | `expiring_nonce_replay_total` | Replay rejection rate | | `expiring_nonce_old_seen_replay_total` | Replays caught by the hardfork migration dual-check | | `expiring_nonce_cells_touched_total` | Approximate growth toward the bounded table footprint | # Invariants 1. **No replay.** A sender-scoped expiring nonce replay hash with a live `valid_before` MUST NOT be accepted twice. 2. **Hardfork replay continuity.** A transaction included before activation and still live after activation MUST be rejected by the migration dual-check. 3. **Expiry bounds.** Transactions with `valid_before <= block.timestamp` or `valid_before > block.timestamp + 300` MUST be rejected. 4. **Bucket expiry proof.** Within a bucket, `stored_valid_before != tx.valid_before` MUST imply the stored record is not live. 5. **Collision handling.** A live collision with a different fingerprint MUST probe the next deterministic cell, up to `EXPIRING_NONCE_MAX_PROBES`. 6. **Probe exhaustion.** If all probed cells contain different live fingerprints for the same `valid_before`, the transaction MUST be rejected with `ExpiringNonceSetFull`. 7. **Bounded state.** New replay state MUST be limited to `EXPIRING_NONCE_BUCKET_COUNT * EXPIRING_NONCE_BUCKET_CAPACITY` cells in the reserved direct slot range. 8. **No explicit cleanup dependency.** Replay correctness MUST NOT depend on offchain pruning, MEV services, or TIP-1060 storage credits. 9. **No nonce mutation.** Expiring nonce transactions MUST NOT increment protocol nonces or 2D nonces. 10. **Storage layout hygiene.** Old ring slots 1, 2, and 3 MUST remain reserved after activation, and future Nonce precompile fields MUST NOT overlap the direct replay-cell slot range.