Hardcore Gas Savings in NFT Minting (Part 2): Merkle Trees vs Signatures
Part one of this series is here. If you are seeing a paywall, click this link.
When tokens are airdropped, or private sales are conducted (sales where only selected addresses are allowed to purchase a token or mint an NFT), there are three popular mechanisms for allowing only a selected list of addresses to buy:
- storing the addresses in a mapping
- signing the addresses with a private key and verifying the signature on-chain
- using Merkle proofs
Here is what the alternatives look like in solidity:
In the first function, we check if the caller is a member of the allowList mapping. In the second two, the caller sends some proof that msg.sender is permitted to conduct the transaction.
The experiment is simple. Which of these three methods is the best from a gas cost perspective?
Merkle Tree Mechanics
I’m going to assume the reader already knows how Merkle Trees work, but I need to do a quick review for the sake of the benchmark. A fantastic explanation can be found here.
A Merkle tree takes a proposed member and a proof that the member is in the set. Each member is a leaf in a (balanced) binary tree, and the proof is the sequence of hashes of the sibling nodes such that the Merkle root can be reconstructed by “hashing your way to the root. ” If the hash at the root matches the hash of the sequences, then the candidate is indeed a member.
It is important to note here is that the bigger the pool of allowed addresses, the longer the proof will be, logarithmic with the height of the tree. So having 32 addresses on an allowed list requires a proof length of 5, 256 requires 8, and 4096 requires a length of 12 etc. For this benchmark, we use 4096 since that is roughly how many addresses would be added to the presale in a typical NFT launch.
Public Signature Mechanics
For a public signature, the address of the buyer is hashed and the hash is signed by a private key. The smart contract knows the public key of the signer, and it uses the hash of the address and the provided signature to know if it really was signed by the private key. If it was, then the user is allowed to purchase. Unlike Merkle trees, this mechanism is not affected by the number of addresses added to a presale or airdrop.
Methodology and Results
The solidity compiler was set to an optimization level of 1000 per experiment from the previous post. Hardhat was used to measure the gas costs. You can clone the repository here: https://github.com/DonkeVerse/PrivateSaleBenchmark
To put these numbers into context, remember that initiating an Ethereum transaction costs 21,000 gas. So you’ll need to subtract that value to see the cost that is attributed to the allow list mechanism. In the table below, we used 4096 addresses for testing.
Predictably, using mapping is the cheapest because all you have to do is read from storage. However, each address to add to the presale costs 20,000 gas of storage. This becomes extremely expensive when there are thousands of addresses. Then there is a risk that the operator spends ETH to add an address to the allowed list, but the customer doesn’t purchase and the expense is lost. If you set the allowedList mapping to zero after the user mints the token, the gas cost will be even lower because the EVM refunds setting storage to zero. The new gas cost in this case is 21,598 down from 23,424. That’s basically unbeatable because a transaction cannot go below 21,000. This will no doubt make for a happier customer, but keep in mind in the grand scheme of things, more Ether gets burned and sacrificed to the miners. It costs 20,000 gas to add an address, but only ~2,000 is saved at mint. Thus, 18,000 gas worth of Ethereum was vaporized. On the other hand, signatures required sacrificing about 8,293 gas worth of Ethereum. This is less wasteful in the long run.
Merkle Tree cost as a function of the number of addresses
Merkle Trees clearly lose when there are 128 addresses or more. They are only efficient compared to signatures when there are 127 or fewer addresses in the Merkle Tree. Because the addresses were randomly generated, there can be a slight variance in the gas measurement.
+---------------------+----------------------+
| Number Of Addresses | Merkle Tree Gas Cost |
+---------------------+----------------------+
| 16 | 27,862 |
| 32 | 28,732 |
| 64 | 29,636 |
| 128 | 30,517 |
| 256 | 31,389 |
| 512 | 32,284 |
| 1,024 | 33,195 |
| 2,048 | 34,036 |
| 4,096 | 34,906 |
| 8,192 | 35,801 |
| 16,384 | 36,746 |
+---------------------+----------------------+Does the Signing Address Affect the Gas Cost?
By experimenting with different addresses (thanks to Honest NFT at Convex Labs for the suggestion!) we found one that saved about 12 gas compared to the typical. It seems that adding leading zeros isn’t the cause of the savings.
+---------------------------------------------+----------+
| Public Key | Gas Cost |
+---------------------------------------------+----------+
| 0x2132bC228dcAe17EE18Bbf078FA48FB12d90C015 | 29273 |
| 0x0D9A6F68f2A49DBa6e8991e64c3173088c25a566 | 29261 |
| 0x00c53Da2e09bc19c02bb56aE480eEa48081E8bF2 | 29273 |
| 0x000C6a093B079Bd237079213881Ce9DD8283c9FC | 29281 |
| 0x00008Eb5Faf23B93c85Fa87BBA3641e3E20475C4 | 29273 |
| 0x00000e71C7532da2f6Fe9d10942f25C565E0b045 | 29273 |
+---------------------------------------------+----------+Alternative methods
One solution that jumps out, but turns out to not be viable is a bloom filter (and its relatives, the XOR filter and ribbon filter). Bloom filters are probabilistic sets where the return “maybe in the set” or “definitely not in the set.” The issue is that an adversary can keep trying different addresses until they find an address that is “maybe in the set.” Even if the bloom filter is set to have an extremely low false-positive rate, the adversary won’t have trouble finding an exception with the aid of a GPU.
Another solution that falls short is using public signatures but with fewer bits, but this would not be able to use the opcode ECRECOVER.
Here are some complicated solutions that might be worth exploring. We have not done any benchmarks, so take with a grain of salt.
- zk-snarks. The zero-knowledge isn’t interesting, but the succinct part is. If the gas costs of tornado.cash (which uses zk-snarks) are any indicator, this won’t work but it’s worthy of mention.
- Verkle Trees are like Merkle Trees but have a constant size proof
- Some tree/trie that allows encoding in bitwise form. If all the addresses could be stored in a long sequence of bits, and proving membership is just traversing the bits a certain way
- Patricia Tries or Radix Trees. An address can be encoded as a sequence of hex symbols or a sequence of bits. So if there is a way to encode the tree in bit form, this may be viable.
- A bitwise Trie with bitmap is interesting since bitwise operators can save a lot of gas
Conclusion
Use signatures for presale and airdrops with over 127 participants. Otherwise, use Merkle trees.
In the future, hopefully, an even more efficient scheme can be researched and developed.
Part 3 of the series, where we track not only if the user is in the presale, but how many pieces they can mint, is here.
Want to Connect?Join my 4 month solidity bootcamp rareskills.ioFollow me on twitter twitter.com/jeyffreCheck out my Udemy courses! https://www.udemy.com/user/jeffrey-scholz/