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

© 2024 Solidity Dev Studio. All rights reserved.

This website is powered by Scrivito, the next generation React CMS.