Utilizing Bitmaps to dramatically save on Gas

A simple pattern which can save you a lot of money

As you may know the most expensive operation in Ethereum is storing data (SSTORE). So you should always look for ways to reduce the storage requirements. Let's explore a particularly useful one: Bitmaps.

How to implement a simple Bitmap

Let's assume we want to store 10 boolean values. Usually you would implement this with a simple bool array:

// SPDX-License-Identifier: MIT
pragma solidity 0.8.0;

contract BitmapTest {
    bool[10] implementationWithBool;

    function setDataWithBoolArray(bool[10] memory data) external {
        implementationWithBool = data;
    }

    function readWithBoolArray(uint256 index) external returns (bool) {
        return implementationWithBool[index];
    }
}

Now with the Bitmap the implementation can be changed to a uint10 instead of the bool array. The uint10 would be represented by 10 bits in storage.

For example here are some decimals numbers represented in bits.

  •        0: 0000000000
  •        1: 0000000001
  •   512: 0100000000
  •   729: 1011011001
  • 1023: 1111111111

We can take advantage of this bit-representation with some additional math. To get the n-th bit of this uint, we can use bit-wise operations.

Let's take the number 729. With a bool array to read the 4th bool value, it's just an array[4]. For the bitmap we can instead create a second number by shifting 1 towards the left using the left-shift operator <<.

  • 1 << 4 = 0000000001 << 4 = 0000010000


Now using the bitwise AND operator &, we get the value of the n-th bit (counting from 0):

  • 729 & (1 << 4) = 1011011001 & 0000010000


Which results in

  • 1011011001 &
  • 0000010000 =
  • 0000010000
Bit Off

As long as this result is above 0, the n-th bit in the original number was 1. So now we can implement the Bitmap:

// SPDX-License-Identifier: MIT
pragma solidity 0.8.0;

contract BitmapTest {
    uint256 implementationWithBitmap;

    function setDataWithBitmap(uint256 data) external {
        implementationWithBitmap = data;
    }
    
    function readWithBitmap(uint256 indexFromRight) external returns (bool) {
        uint256 bitAtIndex = implementationWithBitmap & (1 << indexFromRight);
        return bitAtIndex > 0;
    }
}

Choosing a Bitmap size

As you might have noticed, we chose uint256 in the above implementation. While a uint10 is technically enough, this would actually result in higher gas-costs than using the uint256. This is because the EVM operates on 32 bytes registers (256 bits) and anything below that requires additional conversion.

So should you always choose uint256?

No, it depends on your use case. With a single uint256, you can represent 256 bits. So would the data you want to store fit into a 256 boolean array? If yes then go ahead and use a single uint256.

If not, for example if the boolean array can grow arbitrarily large, then pack the bitmap itself into an array. We'll explore both options with an example at the end.

Gas Costs Comparisons

Let's first look at the gas costs difference in our 10-bit example. With the original boolean array, the transaction execution costs were:

  • setDataWithBoolArray:  140,583 gas
  • readWithBoolArray:               1,281 gas

Now with  the bitmap, we can greatly improve on that:

  • setDataWithBitmap: 78,043 gas
  • readWithBitmap:             1,129 gas

Use Case 1: Setting Boolean Flags

Now to our first example use case. Boolean flags are commonly used to activate certain options in the system.

Let's say you build a DEX like Uniswap where you have automatically triggered trades. You could activate certain settings depending on where the trade comes from. So for example you could have flags like

  • NO_FEES
  • SENDING_FEES_TO_GOVERNANCE
  • DELAY_TRADE_EXECUTION

The options will likely not exceed 256, so you can easily store those in a single uint256.

Use Case 2: List of participants

You may want to payout rewards to anyone who has participated in your contracts. This could be an arbitrary large list. You could save each individual participant in a mapping, or instead utilize the bitmap with a uint256 array.

// SPDX-License-Identifier: MIT
pragma solidity 0.8.0;

contract ParticipatedWithBitmap {
    uint256[] public participantsBitmap;

    function setParticipants(uint256[] memory participantsBitmap_) external onlyOwner {
        participantsBitmap = participantsBitmap_;
    }
    
    function hasParticipated(uint256 bitmapIndex, uint256 indexFromRight) external view returns (bool) {
        uint256 bitAtIndex = participantsBitmap[bitmapIndex] & (1 << indexFromRight);
        return bitAtIndex > 0;
    }
}

Markus Waas

Solidity Developer

More great blog posts from Markus Waas

  • Zeppelin

    Openzeppelin Contracts v4 in Review

    Taking a look at the new Openzeppelin v4 Release

    The Openzeppelin v4 contracts are now available in Beta and most notably come with Solidity 0.8 support. For older compiler versions, you'll need to stick with the older contract versions. The beta tag means there still might be small breaking changes coming for the final v4 version, but you can...

  • Loan

    EIP-3156: Creating a standard for Flash Loans

    A new standard for flash loans unifying the interface + wrappers for existing ecosystems

    As we've discussed last week, flash loans are a commonly used pattern for hacks. But what exactly are they and how are they implemented in the contracts? As of right now each protocol has its own way of implementing flash loans. With EIP-3156 we will get a standardized interface. The standard was...

  • Zero

    Tornado.cash: A story of anonymity and zk-SNARKs

    What is Tornado.cash, how to use it and the future

    With the recent Yearn vault v1 hack from just a few days ago, we can see a new pattern of hacks emerging: Get anonymous ETH via tornado.cash . Use the ETH to pay for the hack transaction(s). Use a flash loan to decrease capital requirements. Create some imbalances given the large capital and...