Hardcore Gas Savings in NFT Minting (Part 3): Save $30,000 in Presale Gas Using Bit Manipulation

Photo by Glenn Carstens-Peters on Unsplash

This series has a Part 1 and Part 2. If you see a paywall, click here.

In a public mint, people can generally mint as many NFTs as they want to, either by minting over and over or by colluding with other buyers. This is undesirable in a private sale (sometimes known as a whitelist) where each member on the list is guaranteed a specified number of mints. A typical workflow would look something like this in solidity:

(Please note that this does not include the optimizations listed in Part 1 for the sake of brevity. Don’t actually use this code! It doesn’t have require messages!)

This workflow should look familiar to anyone who has programmed an NFT before. After we implement all the optimizations in Part 1 and Part 2, there is still one more thing to do.

The culprit for unnecessarily high gas costs here is amountMintedSoFar[msg.sender]++ . That variable is a mapping from the addresses to how many that user has minted so far and we want to make sure it doesn’t exceed their allocation.

Although this should be an obvious solution for any seasoned programmer (hash maps have a notorious reputation that they are always the correct answer at an interview), mapping addresses to integers has a drawback when used on Ethereum.

By way of review, if we have a mapping mapping (address => uin256) myMap , the operation myMap[myAddress] += 1 costs 20,000 gas when it is executed the first time, because setting a zero value to non-zero in Ethereum costs that much. Non-zero to non-zero is much cheaper at 5,000 gas. So myMap[myAddress] += 1 costs 5,000 gas if the uint value inside is not zero.

Also, as a review, the translation to gas cost to dollars is as follows:

cost in $ = gas used × gas price (gwei) × ETH price ($) / 1 Billion

You can get the current gas price from sites like etherscan or ethgasstation.

Incrementing a storage variable from zero to non-zero is one of the most expensive Ethereum operations. It’s roughly how much it takes to make an Ether transfer, which is enough to buy a very expensive coffee in early 2022. Here is the math carried out with typical numbers:

20,000 × 100 gwei × $3,800 / 1 Billion = $7.6

We can save the user a lot of gas if we instead set the mapping manually for each address we think is going to mint a token during the presale. In that case, the code would look like this.

This will be much cheaper for the user because setting non-zero storage to a non-zero value costs 5,000 gas, which is 75% cheaper!

But the problem is, now the contract owner has to pay 20,000 gas for each address she wants to add to the presale! Let’s say we have a presale of 5,000 pieces. This will cost 100 Million Gas. Assuming a gas price of 100 Gwei and an Ether price of $3,800, the total cost to set the mapping for all those users will cost her at least $38,000, not including the extra overhead! And there will be overhead, because, at this time of writing, an Ethereum block only allows for 30 Million Gas in a single block, so that’s a lot of transactions to break up all of the presale allocations into manageable batches over many Ethereum blocks.

So either the owner pays a new car’s worth of gas prices, or five thousand users waste a luxury coffee’s worth of Ethereum. Is there a better way?

balanceOf doesn’t work here

In Part 1, we used balanceOffrom the ERC721 library during public mint to make sure no one mints more than a certain number of pieces in one transaction. For review, balanceOf from the ERC721 specification tells you how many tokens an address owns. This is more like a rate limiter than an absolute restriction because people can just use a different wallet in parallel to get around the restriction.

BalanceOf won’t work during a presale because people can mint, transfer the piece to another wallet to lower their balance, and then mint again. So one enterprising individual could technically mint the entire presale allocation.

We don’t care about this in the public sale because we cannot stop sibyl attacks as noted in Part 1. But for a private sale, this could be a real problem!

The Better Way

A mapping allows us to store an effectively unlimited number of addresses, but we don’t actually need that capability! In reality, what we are doing is ensuring that the 5,000 pieces we promised will in fact be available to the said buyers.

Theoretical Information Limit

All we really care about is if a particular NFT has been claimed or not. We only need one bit to store this information. If we want to keep track of 5,000 pieces, we only need 5,000 bits or 625 bytes to store this information. This amounts to 21 storage units in Ethereum (a storage unit is 32 bytes). 21 storage units would cost the owner $160 to set using the economic assumptions from earlier, which is a big improvement over $38,000!

Imagine we could somehow say User 1 is promised bits 0,1,2, User 2 is promised bit 3, user 3 is promised bit 4 and 5, etc. The presale list would look like this

| User  | Amount Promised |
+-------+-----------------+
| User1 | 3               |
| User2 | 1               |
| User3 | 2               |
...

Mapping addresses to bits

We don’t want to use another mapping to go from address to bit number, of course, because that would defeat the purpose of this exercise!

Back in Part 2, we noted that using ECDSA signatures is the most efficient way to add an address to a presale, allow list, or airdrop.

So instead of just signing the address, we can sign both the address and the bit number they are assigned to. We will then have 5000 bits that are already set to 1. Now the table looks like such:

| User  | Amount Promised | Signatures (ticket to presale)
+-------+-----------------+-----------------------------------------
| User1 | 3               | sig(User1,0), sig(User1,1), sig(User1,2)
| User2 | 1               | sig(User2,3)
| User3 | 2               | sig(User3,4), sig(User3,5)
...

We only allow the transaction if the user can submit a valid combination of 1) Their address; 2) the ticket number; 3) the signature that corresponds to these. We call this triplet a “ticket” in this article. So someone who can mint three pieces has three tickets.

After they use their ticket, the smart contract sets the bit corresponding to the ticket number to zero. This operation only costs 5,000 gas (because we change a non-zero storage to non-zero, assuming there are other non-zero bits in the storage slot). The EVM doesn’t allow us to only write one bit of storage, you can only write in 32 byte increments. So we would have to find the 32 byte slot where the bit in question is and flip it, leaving the other 255 bits unchanged. The user never has to set storage from zero to non-zero and pay the 20,000 gas fee. Instead, we pay $160 to set 5,000 bits to one ($160 in gas) and sign all the addresses and ticket numbers off-chain (no gas cost).

Show Me the Code!

If you want to follow along, you can paste the above code into remix.ethereum.org, set the optimizer to 1000 as discussed in Part 1, and put a ticket number of your choice into the function call for claimTicketorBlockTransaction (ticket number 10 in this case).

According to remix, this costs 26,960 gas.

Don’t forget we have to subtract the 21,000 gas that it costs to call a function from outside the smart contract. So our cost was 5,960 gas paid by the buyer. That’s a big improvement over 20,000 gas! There is still room to optimize the code, but I want to keep the code simple for now because there is a lot to explain!

Explaining the Code

Line 7 and 8

uint256 private constant MAX_INT = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;

uint256[3] arr = [MAX_INT, MAX_INT, MAX_INT];

The variable arr is storing 3 sets of 256 bits all set to 1. (If you are feeling really bored, you can convert the hex number and see it equals 2²⁵⁶ minus 1).

This is to set each of the bits to one, signifying the ticket is not claimed yet. We’ve arbitrarily chosen 768 tickets (3 × 256) to keep this simple.

Line 11

require(ticketNumber < arr.length * 256)

We check that the ticketNumber is actually contained in our set of bits. Since the array here is of length three, and each slot holds 256 bits, we can have up to 768 tickets (although of course, we could make the array longer if wanted).

Line 12 and 13

uint256 storageOffset = ticketNumber / 256;
uint256 offsetWithin256 = ticketNumber % 256;

If we receive a ticketNumber 0–255, we know they are in the zeroth slot in th arrray. That is what the variable storageOffset does. Let’s say we are looking at ticket number 258. In that case, we know we are in slot 1 (the middle slot), and the 3rd bit from the end (3 % 256 = 3). Thus, for bit 258, storageOffset = 1 and offsetWithin256 = 3.

This code helps us land in the right place with our long row of 1s.

Line 14

storedBit = (arr[storageOffset] >> offsetWithin256) & uint256(1);

What we do is look at the 256 bits stored in the slot in question, and shift them to the right by storageOffsetWithin256 units. So if arr[storageOffset] contains 000...01000 , and we shift right by 3 units, it will look like 000...00001 .

This puts the bit in question is at the rightmost part of the 256 bits. We then do a bitwise and with 000…0001 (uint256(1))to zero out everything to the left of the bit in question. If the last bit after shifting is 1, storedBit will be 1 and vice versa.

Line 15

require(storedBit == 1, "already taken");

If this bit hasn’t been used before, storedBit will equal 1 and the code will not revert. If the bit was already set to zero, the code will revert. This prevents the user from re-using the ticket.

Line 16

arr[storageOffset] = arr[storageOffset] & ~(uint256(1) << offsetWithin256);

Finally, to set the bit to zero, we take 000..0001, i.e. uint256(1), and shift it left by the appropriate amount. We wanted to flip ticket 258 again to signify it is claimed. So we shift 000..0001left by 3 units to achieve 000..01000 . Then, we do a bit flip with ~ to turn the mask into 111..10111 . By doing a bitwise & with the storage variable, we will zero out the bit at the position where the zero is and leave the other bits unchanged.

How would this look in the presale code?

function presale(
    bytes calldata signature, uint256 ticketNumber) external payable {
        // ... other require statements
        require(verifySig(msg.sender, ticketNumber, signature));

        claimTicketOrBlockTransaction(ticketNumber, msg.sender);

        _mint(msg.sender, totalSupply());
}

Again, we are skipping optimization for the sake of clarity.

For 5,000 presales, you can imagine that we have 5,000 signatures. For someone to claim their presale, their address from metamask is matched with one of their tickets on the web app to find their signature, which is sent to the function presale along with the ticketNumber.

In verifySig we validate that the signature really signs the combination of msg.sender and ticketNumber . Then, we claim ticketNumber by setting the bit to zero then minting.

This is admittedly a slightly more complicated way of doing things. But is it worth the immense savings? I think so! Complexity, in isolation, is undesirable. Complexity is relative and not absolute.

Remember, if you want to limit how many NFTs a user buys during presale, you have to track that in storage somewhere.

Shortcut If All Presale Allocations are Equal

It’s worth noting that Azuki NFT had a clever solution for storing the amount minted so far as a 128-bit number in the same slot ofbalanceOf within ERC721 (Code here, line 366 in file 4). During mint, when balanceOf is incremented, the amount the user minted so far is updated in the same slot (remember, two uint128 variables can sit in the same uint256 slot). If everyone has the same presale limit, this is a very good solution. However, if the presale limit changes per address, you will need to store that somewhere, and you will again fall back to having to update a mapping that may be quite large. If your presale has a fixed number per address, their solution will be easier to implement.

Can we do better?

The fundamental ideas are in place. For those not interested in the inner workings of the Ethereum Virtual Machine, feel free to skim to the conclusion. But for those who like to polish things…

Let’s go over the stuff we can tweak (this should be a review from Part 1).

arr[storageOffset] is read from storage twice
The require statement already protects us from integer overflow, so we can put the math inside an unchecked block

Here is the new result:

That’s 220 gas saved from the last test, but there is still room for more.

Another Deep Dive Into Solidity Storage

We’ve already discussed how storage gas costs depend on whether we set a value from zero to non-zero and non-zero to non-zero. We now discuss how our array from earlier is actually getting stored.

Reading the docs on EVM storage layout is worthwhile: but I’m going to summarize the key points here. Each smart contract keeps fixed-sized storage values in a sequence of 32 byte slots. Imagine we have a contract like this:

contract Storage {

    uint256 public var1; // sits in storage slot 0
    uint256 public var2; // sits in storage slot 1
    uint128 public var3; // sits in storage slot 2 with offset 0
    uint128 public var4; // sits in storage slot 2 with offset 1
    uint256[3] = [1,1,1] // takes up slots 3, 4, and 5

256 bits is the same as 32 bytes, so var1 and var2 it takes up an entire storage slot. var3 and var4 both sit in slot 2 because two 128 bit numbers can both fit in a 256-bit slot.

Using Assembly

Most of the time, the Solidity compiler is reasonably smart, and using assembly won’t save gas. In this situation, however, we can actually save a little.

At the risk of sounding condescending (sorry!), if you aren’t 100% comfortable using assembly, and you haven’t robustly tested the code, please hold off using it in production! Assembly gives you more opportunities to unwittingly shoot yourself in the foot. Nonetheless, I’m keeping this section because I think it is interesting and I’m sure there are people who will benefit from it. Assembly is not evil. Just a tool to use under the right circumstances.

We don’t technically need arrays here, because all we care about is the bits in consecutive storage slots. Let’s do a couple of tricks:

Rather than using an array which adds management overhead, let’s use an ugly but more effective sequence of uint256 . Since the array length is intrinsically hardcoded, this doesn’t functionally change anything except get rid of the array bookkeeping. We basically want a sequence of 762 bits set to 1 in a row, and while an array accomplishes this, a sequence of uint256 at their max value does it with less overhead.
Since we hardcoded the list of bits, the require that validates the ticketNumber isn’t too large can be hardcoded too. This also saves some overhead of arr.length .
Rather than indexing an array with storageOffset , we will get the slot of the first variable with assembly and add the storageOffset to that so that we land in the right slot . Then we will sload the variable just as if we were loading a regular 256-bit storage slot.

Here is the code for plugging into remix:

Overall, that saves us ~300 gas, which isn’t a whole lot for one transaction. But over the course of thousands of users, this is actually quite a bit of ether saved.

And the Savings Are…

The fundamental trick here is that setting a storage slot from 0 to 1 costs 20,000 gas, but so does setting storage from 0 to a number where all 256 bits are 1. This lets us allocate a presale for 256 addresses for the price of one. The second trick is creating an implicit mapping from an address to a particular bit index by signing both the address and the bit index (ticketNumber).

If we allocate 5,000 users, we have to set 21 storage units to all ones to have enough bits. (21 x 256 = 5,376). That’s equivalent to 21 cups of expensive coffee which is manageable. If we allocate 5,000 users individually with a mapping, that’s 5,000 of those costly joes, equal to the cost of a fresh Mercedes Benz. That money would either come from the seller, or collectively paid by the buyers, but it comes out of someone’s ETH wallet.

Conclusion

In Part 3, we kill two birds with one stone: we have a mechanism to see if the user is on the presale list using a public signature, and we track how many they have minted on a per-user basis using bits.

The suggestions in this series are not meant to be prescriptive. You need to decide on your own what is appropriate for your project. As always, DYOR. Best of luck!

Want to Connect?

Join my 4 month solidity bootcamp: rareskills.io/curriculum

Follow me on twitter: twitter.com/jeyffre

Check out my Udemy courses: https://www.udemy.com/user/jeffrey-scholz/