Storage-optimized replay protection: from hash => bool to packed flag lanes, and can the protocol offer better?

Introduction

Many emerging Ethereum applications—privacy pools, permit‑style nonce schemes, and large‑scale DePIN settlements—must record a tiny, immutable fact for each event: a nullifier spent, a nonce used, or a session settled. The cost of this "replay‑protection" is pure storage. While zero‑knowledge proof verification has become cheap, the flags themselves still consume a lot of gas because each flag is typically stored as an independent `bool` in a separate slot.

From Naïve Booleans to Packed Bitmaps

The baseline: `mapping(bytes32 => bool)`

• One storage slot per flag.
• First write costs ~22 k gas (20 k for a zero‑to‑non‑zero SSTORE + 2 k cold access).
• No amortisation—every flag pays the full price.

First optimisation: dense bitmaps

When flag identifiers are sequential, a contract can use a bitmap: ```solidity mapping(uint256 => uint256) bitmap; // flagId >> 8 => word, bit = flagId & 255 ```

• The first flag in a word still costs ~22 k gas.
• Each subsequent flag in the same word costs ~5 k gas (read + bit‑flip).
• This is the pattern used by Permit2 and EIP‑4337.

Second optimisation: lane‑based packing

For multi‑party operations, a 256‑bit word can be split into lanes (e.g., four 64‑bit lanes). Each lane represents a distinct session, and each bit inside a lane marks a specific operator’s settlement: ```solidity mapping(bytes32 => uint256) words; // one word per 4 sessions × 8 operators ```

• One fresh write (~22 k) plus cheap flips (~5 k each) yields ~75 % gas reduction compared with the naïve approach.
• The savings depend on tight sequencing; gaps leave unused bits, reducing efficiency.

The Remaining Bottleneck

Even with lane‑based packing, the first flag in a word always incurs the full SSTORE cost, and every additional flag still costs ~5 k gas. The geometry (lane size, number of lanes) is fixed at deployment, so protocols with variable party counts either waste bits or overflow.

Why the EVM cannot go further on its own

• Random keys – Nullifiers are cryptographic hashes; they never collide, so they cannot benefit from co‑location.
• Monotonic writes – All flags are append‑only, never cleared, but the current SSTORE pricing treats them as generic writes.
• State‑growth repricing – Proposals like EIP‑4762 increase the cost of fresh storage touches, making the first‑write penalty even steeper.

A Call for Primitive‑Level Support

To break the ceiling, the execution layer could expose a dedicated storage primitive for append‑only bit‑sets:

1. Append‑once bit‑set type – Setting a zero bit in an existing word would be priced at its marginal cost (~5 k gas) without the initial 22 k overhead.
2. Span allocation – Contracts declare a contiguous region of slots; the allocation pays the fresh‑touch cost once, and subsequent bit flips are cheap.
3. Bulk write precompile – A precompile that writes many bits under a single access charge, useful for aggregators without re‑introducing trust.
4. Restricted‑semantics pricing – Similar to calldata, an insert‑only set could be priced lower because its state transition is monotonic and bounded.

These primitives would let small operators achieve the same marginal cost as large aggregators, preserving decentralisation while keeping gas usage low.

Open Questions for the Community

• Variable‑width lanes – Can we design a layout that dynamically adapts to the number of participants without fixing lane size at deployment?
• Stem‑based pricing – Under EIP‑4762, is it safe to align storage layout with Verkle stems, or does that misuse an implementation detail?
• Existing solutions – Have any L2/L3 chains already introduced locality‑aware or bulk storage ops, and what lessons can we draw?
• Long‑term placement – If cheap on‑chain flags remain impossible, where should replay‑protection live (e.g., off‑chain roots with provable claims) without re‑introducing trusted summarizers?

Practical Takeaway

Current best practice is to pack flags into shared words and use lane‑based layouts where possible. However, the real breakthrough requires an EVM‑level primitive that treats append‑only bit flips as a distinct, cheaper operation. Until such a primitive exists, protocol designers must balance sequencing discipline, lane geometry, and potential off‑chain aggregation to keep replay‑protection costs manageable.