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

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