Merkle Airdrops and Bitmaps: Gas-Efficient Token Claims

You're launching a token. 10,000 wallets are eligible to claim. Each address gets a specific amount. Each address can only claim once.

How do you build this on-chain without burning through storage?

The Problem

The two things you need to track:

1. Who is eligible and how much they get
2. Who has already claimed

Both cost gas. The question is how much.

Table of Contents

1. The Problem
2. The Naive Approach
3. Merkle Trees: Verify Without Storing
   • The Leaf Format
4. Bitmaps: Track Claims in 40 Slots Instead of 10,000
   • Reading the Bitmap
   • Writing the Bitmap
   • Why This Saves Gas
5. The Full Contract
   • Adding a Deadline
6. OpenZeppelin's Bitmap Library
7. Other Approaches
   • Push-Based Batch Transfers
   • Signature-Based Claims (EIP-712)
   • ZK Storage Proofs
8. L1 vs L2: Different Tradeoffs
9. Takeaways

---

The Naive Approach

Store every eligible address on-chain and use a mapping to track claims:

// Don't do this
mapping(address => uint256) public eligibleAmounts;
mapping(address => bool) public hasClaimed;

function claim() external {
    require(eligibleAmounts[msg.sender] > 0, "Not eligible");
    require(!hasClaimed[msg.sender], "Already claimed");

    hasClaimed[msg.sender] = true;
    token.transfer(msg.sender, eligibleAmounts[msg.sender]);
}

Two problems:

Eligibility storage is expensive. Populating eligibleAmounts for 10,000 addresses means 10,000 storage writes. Each zero-to-nonzero SSTORE costs 22,100 gas (post-EIP-2929). That's 221,000,000 gas just to set up the list. At 30 gwei, roughly 6.6 ETH in gas fees before anyone has claimed anything.

Claim tracking is wasteful. mapping(address => bool) uses one full storage slot per user. 10,000 slots for 10,000 users. Each slot is 32 bytes, but you're only storing one bit of information: claimed or not.

Merkle Trees: Verify Without Storing

A Merkle tree lets you commit to a dataset with a single 32-byte hash, then verify any individual entry against that hash.

You build the tree off-chain. Take all 10,000 (index, address, amount) tuples, hash each one into a leaf, then pair leaves up and hash them together, layer by layer, until you get one root hash.

        Root Hash (stored on-chain: 32 bytes)
       /          \
    Hash AB      Hash CD
    /    \       /    \
  Leaf A  Leaf B  Leaf C  Leaf D

Store only the root on-chain. That's one storage slot instead of 10,000.

When a user claims, they submit a proof: the sibling hashes along the path from their leaf to the root. The contract hashes upward and checks if it reaches the stored root. If it does, the user is in the original list.

For 10,000 entries, the proof is about 14 hashes (log2(10,000) ≈ 14). That's 14 × 32 = 448 bytes of calldata. Cheap compared to storing the full list.

The Leaf Format

Uniswap's MerkleDistributor, the reference implementation most protocols fork, hashes leaves like this:

bytes32 node = keccak256(abi.encodePacked(index, account, amount));

Each claimant gets a sequential index (0 through 9,999). The index serves double duty: it identifies the leaf and maps to the bitmap position for claim tracking (more on that next).

OpenZeppelin's merkle-tree library recommends double hashing to prevent second-preimage attacks:

bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));

Why double hash? In a Merkle tree, internal nodes are hashes of two child hashes. If an attacker can craft a leaf that looks like an internal node, they can forge a valid proof for data that was never in the original list. Double hashing ensures leaves and internal nodes have different structures, making this impossible.

Bitmaps: Track Claims in 40 Slots Instead of 10,000

Now for tracking who has claimed.

A mapping(address => bool) uses one storage slot per address. One slot holds 256 bits, but a bool only uses one. That's 255 bits wasted per claim.

A bitmap packs 256 boolean flags into a single uint256. Each user gets an index, and one bit at that index tracks their claim status: 0 means unclaimed, 1 means claimed.

mapping(uint256 => uint256) private claimedBitMap;

For 10,000 users: ceil(10,000 / 256) = 40 storage slots. Compare that to 10,000 slots with a bool mapping.

Reading the Bitmap

To check if user at index i has claimed:

function isClaimed(uint256 index) public view returns (bool) {
    uint256 wordIndex = index / 256;
    uint256 bitIndex = index % 256;
    uint256 word = claimedBitMap[wordIndex];
    uint256 mask = (1 << bitIndex);
    return word & mask == mask;
}

wordIndex picks which of the 40 slots to look at. bitIndex picks which bit within that slot. One SLOAD, one bitwise AND.

Writing the Bitmap

To mark a user as claimed:

function _setClaimed(uint256 index) private {
    uint256 wordIndex = index / 256;
    uint256 bitIndex = index % 256;
    claimedBitMap[wordIndex] = claimedBitMap[wordIndex] | (1 << bitIndex);
}

Bitwise OR flips the target bit to 1 without touching any other bits in the slot.

Why This Saves Gas

The savings come from how SSTORE pricing works.

Post-EIP-2929 gas costs for storage writes:

Operation	Gas Cost
SSTORE: zero to nonzero (cold)	22,100
SSTORE: nonzero to nonzero (cold)	5,000
SSTORE: nonzero to nonzero (warm)	2,900

With mapping(address => bool), every claim writes false → true. That's a zero-to-nonzero write: 22,100 gas per claim. Every single one.

With a bitmap, the first claim in each 256-user group writes zero to nonzero (22,100 gas). Every subsequent claim in that group flips a bit in an already-nonzero slot: 5,000 gas per claim.

For 10,000 users claiming in separate transactions:

mapping(address => bool):
  10,000 × 22,100 = 221,000,000 gas for storage writes

Bitmap:
  40 × 22,100 (first claim per word) = 884,000
  9,960 × 5,000 (subsequent claims)  = 49,800,000
  Total                              = 50,684,000 gas

That's roughly 77% less gas on storage operations across all claims. The first 40 claimants pay full price. The remaining 9,960 get the discount.

The Full Contract

Here's what the Uniswap pattern looks like assembled. This is based on the actual MerkleDistributor contract:

contract MerkleDistributor {
    address public immutable token;
    bytes32 public immutable merkleRoot;

    mapping(uint256 => uint256) private claimedBitMap;

    event Claimed(uint256 index, address account, uint256 amount);

    constructor(address token_, bytes32 merkleRoot_) {
        token = token_;
        merkleRoot = merkleRoot_;
    }

    function isClaimed(uint256 index) public view returns (bool) {
        uint256 wordIndex = index / 256;
        uint256 bitIndex = index % 256;
        uint256 word = claimedBitMap[wordIndex];
        uint256 mask = (1 << bitIndex);
        return word & mask == mask;
    }

    function claim(
        uint256 index,
        address account,
        uint256 amount,
        bytes32[] calldata merkleProof
    ) external {
        require(!isClaimed(index), "Already claimed");

        // Verify the merkle proof
        bytes32 node = keccak256(abi.encodePacked(index, account, amount));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), "Invalid proof");

        // Mark as claimed
        _setClaimed(index);

        // Transfer tokens
        IERC20(token).safeTransfer(account, amount);
        emit Claimed(index, account, amount);
    }

    function _setClaimed(uint256 index) private {
        uint256 wordIndex = index / 256;
        uint256 bitIndex = index % 256;
        claimedBitMap[wordIndex] = claimedBitMap[wordIndex] | (1 << bitIndex);
    }
}

On-chain storage: one bytes32 for the root, 40 slots for the bitmap. That's 41 storage slots for 10,000 users.

The tree itself, all 10,000 leaves and their proofs, lives off-chain. A frontend or API serves the proof to each user when they claim. The contract only verifies.

Adding a Deadline

Uniswap also ships a MerkleDistributorWithDeadline variant. After a set timestamp, unclaimed tokens can be swept back by the owner:

function sweep(address token_, address target) external onlyOwner {
    require(block.timestamp >= endTime, "Too early");
    IERC20(token_).safeTransfer(target, IERC20(token_).balanceOf(address(this)));
}

Useful when you don't want tokens locked forever because some wallets never claim.

OpenZeppelin's Bitmap Library

You don't need to write bitmap logic from scratch. OpenZeppelin's BitMaps.sol provides a tested implementation:

import {BitMaps} from "@openzeppelin/contracts/utils/structs/BitMaps.sol";

contract MerkleDistributor {
    using BitMaps for BitMaps.BitMap;
    BitMaps.BitMap private _claimed;

    function isClaimed(uint256 index) public view returns (bool) {
        return _claimed.get(index);
    }

    function _setClaimed(uint256 index) private {
        _claimed.set(index);
    }
}

Same gas profile, less room for off-by-one errors.

Other Approaches

Merkle + bitmap is the standard pull-based pattern. But it's not the only option.

Push-Based Batch Transfers

Instead of users claiming, the sender pushes tokens to all recipients directly. GasliteDrop does this with heavy inline assembly optimization: manual memory management, pointer arithmetic, skipping Solidity's ABI encoding overhead.

The tradeoff: the sender pays all gas upfront. On L1 with 10,000 recipients, that's expensive. On L2s (Base, Arbitrum, Optimism) where gas is cheap, push-based is often simpler and costs less overall since there's no merkle tree to build, no proofs to serve, and no frontend claim flow to maintain.

Signature-Based Claims (EIP-712)

The project signs an EIP-712 typed message authorizing each user's claim. The contract verifies the signature with ecrecover.

ECDSA verification costs roughly 29,000 gas. Merkle proof verification for 10,000 entries costs roughly 30,000 gas (14 hashes × ~2,100 gas for keccak256). Similar ballpark, but signatures don't scale as cleanly: you need to pre-generate and store one signature per user, and if the signing key is compromised, all pending claims are at risk.

This pattern is more useful for gasless claims where a relayer submits the transaction on behalf of the user.

ZK Storage Proofs

The newest approach. Axiom V2 lets users prove eligibility from historical on-chain state using ZK proofs. No off-chain list needed: the protocol defines criteria (e.g., "swapped on Uniswap before block X"), and users generate proofs that they meet them.

Verification costs 200,000-400,000 gas per claim. For a simple "here's a list of 10,000 addresses" airdrop, this is overkill. But for retroactive distributions where eligibility depends on complex on-chain history, it removes the need to generate and maintain a list entirely.

L1 vs L2: Different Tradeoffs

On Ethereum L1, storage is expensive. The Merkle + bitmap approach saves real money: 40 slots vs 10,000 for claim tracking, 1 slot vs 10,000 for the eligibility list.

On L2s, storage and execution are 10-100x cheaper. Some protocols skip the bitmap entirely and use mapping(address => bool) because the gas difference is negligible, and the code is simpler. Others skip the pull model altogether and use push-based batch transfers.

Pick based on where you're deploying. The Merkle + bitmap pattern gives you the best gas profile on L1. On L2, simplicity might win.

Takeaways

Merkle trees replace on-chain storage with off-chain proofs. One 32-byte root on-chain, proofs served from a frontend. 10,000 addresses verified with 41 storage slots.

Bitmaps pack 256 claim flags per slot. 10,000 users in 40 slots instead of 10,000. After the first claim per word, subsequent claims cost 5,000 gas instead of 22,100.

The Uniswap MerkleDistributor is the reference implementation. Most airdrop contracts in production are forks or variations of this pattern.

Double-hash your leaves. OpenZeppelin recommends keccak256(bytes.concat(keccak256(abi.encode(...)))) to prevent second-preimage attacks against the Merkle tree.

Consider your chain. L1 benefits heavily from this optimization. L2 might not need it.