Gas-Optimized Nullifier Storage in Solidity: From hash=>bool to Packed Flag Lanes

To store replay-protection flags cheaply in Solidity — the “already spent” marks behind nullifiers, nonces, and settlements — pick by access shape: a mapping(bytes32 => bool) costs about 22,100 gas per flag and never amortizes; a dense bitmap (the Permit2 and ERC-4337 approach) packs 256 flags per storage slot at roughly 5,000 gas each; packed flag lanes fit several parties into a single slot for multi-party settlement.

That is the short answer. The longer one matters because the wrong choice here is a recurring tax your users pay on every transaction, forever, and it almost never shows up in a functional test. It shows up in your gas bill and, eventually, in your audit report. Here’s the full progression, the real numbers at each step, and an honest read on when to hire someone who has built this before rather than deriving it yourself the week before an audit.

Why replay protection is a storage cost, not a compute cost

A growing class of protocols has to persist one tiny fact per event, permanently: this withdrawal is spent, this nonce is used, this session share is settled. Privacy pools write a nullifier — a one-time marker that stops the same secret being reused — per withdrawal. Unordered nonce schemes like Permit2 and ERC-4337 write replay flags because they can’t guarantee transactions arrive in order. Machine-scale settlement (DePIN networks for connectivity, bandwidth, or compute) writes a mark per settled session.

Call all of it what it is: replay protection, and its cost is almost pure storage. That’s worth internalizing before you optimize anything. Zero-knowledge proofs — cryptographic batching that lets one proof verify thousands of signatures at a flat cost — have made the compute side nearly free. The flags are what no longer compress. You’ve driven verification cost to the floor and the storage write is now the whole bill. Optimizing your proof system further is polishing the cheap half.

The baseline everyone starts with, and why nullifiers never get cheaper

The most common shape, and the worst case, is one boolean per key:

mapping(bytes32 => bool) used;   // one flag, one slot
// every flag: ~22,100 gas, state lives forever

That 22,100 gas is 20,000 for writing a slot from zero to non-zero plus 2,100 for touching it cold. Here’s the trap: because the key is a hash, no two flags ever land in the same storage slot. Nothing is adjacent to anything. Nothing amortizes. Every nullifier you will ever write costs the full fresh-slot price.

You can’t engineer around this with packing. Random hash keys scatter by design — that scattering is what makes a nullifier unforgeable and unlinkable. So if your protocol’s “spent” marks are keyed by hash, as privacy-pool nullifiers always are, packing tricks give you nothing. The only lever is a different kind of data structure (an insert-only set), not a cleverer bitmap. That caveat matters: it decides half the framework below.

The bitmap jump: how Permit2 and ERC-4337 cut 75%

When flag IDs are dense and sequential rather than random, you can pack 256 of them into a single 256-bit word:

mapping(uint256 => uint256) bitmap;   // key = flagId >> 8, bit = flagId & 255
// first flag in a word: ~22,100 gas; each later flag: ~5,000

Permit2’s nonceBitmap and the ERC-4337 nonce pattern work exactly this way. The first flag in a fresh word pays full freight. Every subsequent flag that lands in that already-written word costs about 5,000 gas — the 2,100 cold-access charge plus a 2,900 reset. That’s the difference between a 22,100-gas write and a 5,000-gas write, and across a busy account it compounds into real money.

If you’re building a wallet or a signature scheme with counter-based nonces, this is the pattern, and you should not be inventing it. It’s battle-tested, running in production at enormous volume, and copying it correctly costs less than auditing your own variant.

Packed flag lanes: several parties in one storage slot

The third step is for a specific shape: one operation that several parties each have to settle exactly once. Split a 256-bit word into lanes — say four 64-bit lanes — give each operation a lane, and give each party one bit in that lane.

Picture a DePIN connectivity session relayed across 8 independent operators, each settling its own share and each needing to be stopped from settling twice:

contract SessionFlags {
    // 4 sessions per word; each session owns a 64-bit lane;
    // operator i owns bit i of its session's 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 ~22,100 gas; later bits ~5,000
    }
}

The arithmetic tells the story. For 4 sessions × 8 operators = 32 flags, the naive hash => bool approach costs 32 × 22,100 = about 707,200 gas. The lane layout costs one fresh write plus 31 cheap ones: ~22,100 + 31 × 5,000 = about 177,100 gas, roughly 44,300 per session — about 75% less.

One caveat worth flagging: the sequence counter isn’t guaranteed to increment cleanly. Gaps strand lane bits, so sloppy sequencing erodes the savings. That’s a priceable tradeoff, not a flaw — clients that skip wildly can be charged more or simply not served — but it’s the kind of detail that decides whether your 75% holds in production or evaporates.

Which pattern fits your protocol?

Match the pattern to how your protocol actually touches state, not to whichever one looks cleverest:

• Hash-keyed, one party (privacy-pool nullifiers): random keys can’t be packed. Don’t fight it with bitmaps. The honest optimization is an insert-only set structure, and you should expect the write cost to stay near the fresh-slot floor.
• Sequential, one party (ERC-4337 nonces, Permit2): dense bitmap. Use the existing, audited pattern. This is the clearest case for not building custom.
• Multi-party settlement (DePIN sessions, multi-relayer paths): packed flag lanes, with lane width chosen for your typical party count. Pick 64-bit lanes and a 70-party operation won’t fit; an 8-party operation wastes 56 bits. That geometry is frozen at deployment, so get it right the first time.

And a prediction worth planning around: the Ethereum state-growth debate is pushing toward pricing new state higher, and the stateless-tree direction (the EIP-4762 line of work) raises the cost of touching fresh slots. Every pattern above leans on exactly the charges being repriced upward. Packing will matter more next year, not less — and an L2 or L3 will almost certainly ship a cheap append-once storage primitive before mainnet does, because any EVM chain can move faster than mainnet on this and the win lands on every layer running the same virtual machine.

Should you build this yourself or bring in a team that’s shipped it?

Be honest about where the line sits. If your need is standard counter-based nonces, don’t build — lift the Permit2 or ERC-4337 bitmap pattern, keep your variance to zero, and spend your audit budget elsewhere. Re-deriving a known pattern just buys you a novel bug.

Build custom only when your access shape is genuinely unusual: multi-party settlement, lane geometry that has to survive variable party counts, or nullifier sets where the real question is which insert-only structure to use. That’s where the lane width, the sequencing policy, and the behavior under state repricing interact in ways a functional test never exercises — and where an auditor will find the slot-collision or the stranded-lane griefing vector you missed. Getting this reviewed by people who’ve shipped and audited gas-optimized Solidity before costs far less than discovering the flaw after launch, when the storage layout is immutable and users are already paying the tax.

The trap is deriving a packing scheme under audit-deadline pressure. If your protocol’s economics hinge on per-event flag cost — and for privacy pools, unordered nonces, and machine-scale settlement they do — treat the storage layout as an architecture decision, not an implementation detail, and scope it honestly before you write the contract.

FAQ

Q: What is the cheapest way to store nullifiers in Solidity? A: For random hash-keyed nullifiers, there is no packing win — keys scatter across storage by design, so each write stays near the ~22,100-gas fresh-slot floor. The genuine optimization is an insert-only set structure rather than a bitmap. Bitmaps and packed lanes only help when flag IDs are sequential or a single operation involves several parties.

Q: Why does a mapping(bytes32 => bool) cost so much gas? A: Each flag writes a fresh storage slot from zero to non-zero (~20,000 gas) plus a cold-access charge (~2,100 gas), for about 22,100 gas, and because hash keys never collide, no two flags share a slot. Nothing amortizes, so every flag pays full price and the state persists forever.

Q: When should I use packed flag lanes instead of a dense bitmap? A: Use lanes when one operation must be settled once by each of several parties — multi-relayer DePIN settlement is the classic case. A dense bitmap fits single-party sequential flags like wallet nonces. For a 4-session, 8-operator example, lanes cut gas roughly 75% versus the naive mapping, per the source’s figures.

Key Takeaways

• Treat replay-protection storage as an architecture decision made before you write the contract — the layout is immutable after deployment and the cost is a permanent per-transaction tax.
• If you only need counter-based nonces, copy the Permit2 or ERC-4337 bitmap pattern instead of inventing one; novelty here buys bugs, not savings.
• Random hash-keyed nullifiers resist all packing — budget for near-full-price writes and look at insert-only set structures rather than bitmaps.
• Packed flag lanes are the right tool specifically for multi-party settlement, but lane width is frozen at deploy time, so size it for your real party distribution.
• Expect state costs to rise as repricing lands, which raises the payoff of getting this right — book a smart contract architecture review before an audit deadline forces the decision for you.