[ethresear.ch] [Execution Layer Research] Storage-optimized replay protection: from hash => bool to packed flag lanes, and can the protocol offer better?

A growing class of protocols needs to persist one tiny fact per event, forever: this nullifier is spent, this nonce is used, this session share is settled. Privacy pools write a nullifier per withdrawal. Unordered nonce schemes (Permit2’s nonceBitmap, EIP-4337-style two-dimensional nonces) write replay flags because they cannot guarantee sequenced nonces. Machine-scale settlement (DePIN connectivity, bandwidth, compute) writes a mark per settled session. Call all of it what it is: replay protection, and its cost is pure storage. ZK batching has made the compute side nearly free: one proof verifies thousands of signatures or membership checks at flat cost. The flags are what no longer compress.

The progression every protocol rediscovers.

Worst case, and still the most common shape:

mapping(bytes32 => bool) used;   // one flag, one slot
// every flag: ~22,100 gas (20,000 zero-to-nonzero + 2,100 cold access), state forever

This is what nullifier sets look like: the key is a hash, so no two flags ever share a slot, and nothing amortizes.

First optimization, 256 flags per word, when flag ids are dense:

mapping(uint256 => uint256) bitmap;   // key = flagId >> 8, bit = flagId & 255
// first flag in a word: ~22,100; each later flag: ~5,000 (2,100 access + 2,900 reset, own tx)

This is Permit2’s nonceBitmap and the 4337 pattern.

Second optimization, break the word into lanes when one operation involves several parties: key => u256 split into four u64 pages (or eight u32, the geometry is a deploy-time choice), one lane per operation, one bit per party. Concrete shape: a connectivity session lasting about 15 minutes, relayed across 8 independent operators, each of which settles its own share and must be prevented from settling it twice:

one u256 storage slot, key = H(entity, seq >> 2)

 seq:      4k+3         4k+2         4k+1         4k
        |-- lane 3 --|-- lane 2 --|-- lane 1 --|-- lane 0 --|
 bits:  | 63 ...... 0| 63 ...... 0| 63 ...... 0| 63 ...... 0|
                                                      ^
                                     bit i = operator i settled
                                     its share of session 4k

 example: session 4k settled by operators 0, 2 and 5 so far:
        |000...000   |000...000   |000...000   |000..100101 |

contract SessionFlags {
    // 4 sessions per word; each session owns a 64-bit lane;
    // operator i on the session's path owns bit i of its lane
    mapping(bytes32 => uint256) private words;

    error AlreadySettled();

    function markSettled(uint64 entity, uint64 seq, uint8 opIndex) internal {
        require(opIndex < 64);
        bytes32 key  = keccak256(abi.encodePacked(entity, seq >> 2));
        uint256 bit  = uint256(1) << ((seq % 4) * 64 + opIndex);
        uint256 word = words[key];
        if (word & bit != 0) revert AlreadySettled();
        words[key] = word | bit;  // first bit in a word ~22,100 gas; every later bit ~5,000
    }
}

The arithmetic across the progression, for 4 sessions x 8 operators = 32 flags: naive hash => bool costs 32 x 22,100 = ~707,200 gas. The lane layout costs one fresh write plus 31 cheap ones, ~22,100 + 31 x 5,000 = ~177,100, about 44,300 per session, roughly 75% less. Dense single-party bitmaps sit in between.

To ground the terms: entity is a client. seq is that client’s operation counter, and entity + seq names one operation. The operator index is whichever party participated in serving it: a DePIN operator, a relayer, whatever a given protocol’s serving side looks like. The session picture above is just a visual image of why the problem is being raised; the pattern itself is general. One honest caveat: seq is not guaranteed ordered. It usually increments cleanly, but gaps happen, and a gap strands lane bits, so the savings degrade with sloppy sequencing. That is a workable tradeoff rather than a flaw: clients that skip wildly can be priced, reputation-weighted, or simply not served, and when clients increment properly, every participant serving the same client lands in the same word and the savings compound across all of them.

But notice where the progression stops. The geometry is fixed at deployment: pick 64-bit lanes and a 70-operator session does not fit, while an 8-operator session wastes 56 bits. Hashed keys scatter, so co-location only works when ids are sequential by construction, which is exactly what nullifiers can never be. And no matter the layout, every flag after the first costs about 5,000 gas to flip one pre-assigned, append-once bit in a word that already exists, and the first flag always carries a full fresh slot. I am sure better layouts than fixed lanes exist, but packing geometry can only approach those two floors, never go under them; only the schedule can.

It is about to get worse, not better. The state-growth discussion is pushing toward pricing new state higher (and the stateless-tree gas models in the EIP-4762 direction raise fresh-touch costs in witness terms). Every design above leans on exactly the charges being repriced upward. Apps can keep packing harder, but the ceiling is one word, and past that the only escape is handing flag-writing to a large aggregator who batches across many users, which quietly reintroduces a trusted summarizer in exactly the systems built to not have one.

The usual answer, and why it does not close the gap. “Keep the flags off chain, post a root.” But a root is not a settlement; it is a promise that must later be claimed. Claiming against a root means proving membership or non-membership at claim time, and that proof’s generation, calldata, and verification gas land on the same protocol’s users, just later and on the claim path. The storage write you saved reappears as claim-side cost, so lifecycle gas for the protocol as a whole is not obviously lower. And whoever maintains the set behind the root becomes exactly the summarizer this class of system is trying not to need. Roots move the cost; a better-priced write would remove it.

The ask: storage offered for this use case. Could the execution layer support replay flags directly, priced for what they are? This is an EVM question, not an L1 question: the schedule and state model are inherited by most L2s and L3s, so an execution-layer improvement here lands on every layer running the EVM at once. Possible shapes:

1. Shared flag words as a primitive. An append-once bit-set type: setting a previously zero bit in an existing word is priced near its marginal cost rather than as a general SSTORE. The 5,000-gas bit flip above is the target.
2. Span allocation. A contract declares a region of N contiguous slots; allocation pays the branch cost once, writes inside pay leaf cost. The stem/page structure of Verkle-style and binary trees already groups neighboring leaves under a shared branch, so the structural discount will exist; this would expose it deliberately instead of leaving it as an implementation detail of witness pricing.
3. Bulk access. SSTORE/SLOAD variants or a precompile writing k values under one stem for one access charge.
4. Restricted-semantics pricing generally. Append-once bitmaps, monotonic counters, insert-only sets: bounded, predictable state transitions, never general read-modify-write. Calldata and blobs are priced below state precisely because their semantics are restricted; is the same argument available here? Note nullifiers are the hard case: random hashes get nothing from locality or word-sharing, but an insert-only set primitive would serve them directly.

Questions.

1. Within one word, is there anything better than fixed lanes? Variable-width pages, rank/select-style indexing, or other layouts that waste fewer bits when party counts vary, without the geometry being frozen at deployment?
2. Under EIP-4762-style pricing, is designing storage layout around stem boundaries a sane strategy or an abuse of an implementation detail?
3. Could restricted-semantics writes justifiably be priced below general SSTORE, or does any cheaper persistent-write path fight state-growth repricing head on?
4. Any EVM chain, L2 or L3 can move faster than mainnet on this. Is any of them already pricing storage locality or offering bulk or append-once storage ops, and what did they learn?
5. If state repricing lands without anything like this, is the honest conclusion that per-event flags simply do not belong in EVM state, and if so, where do they belong that does not end in a trusted summarizer?

The stake is who gets to batch. Proofs made verification cheap for everyone; flag storage is still priced so that only whoever aggregates the most users per word gets the amortization. A primitive that lets a small operator pack flags at the same marginal cost as a giant is the decentralization-preserving version of this optimization, on whichever layer it ships.