In the Web3 space, it is common practice to have sales for tokens to addresses that have been whitelisted off-chain. There are three common on-chain verification mechanisms to validate these users, enabling them to receive the tokens.

The three on-chain verification methods (including gas costs of optimiser set to 1,000 runs):

• storing the address in a mapping (Gas: 23,424)

  • The issues with the mapping is it is very expensive for the seller to store all the addresses.

• ECDSA Signature Verification (Gas: 29,293)

• using Merkle proofs (Gas: 30,517 if we whitelist 128 addresses)

This made using ECDSA Signature Verification for whitelisting the most gas efficient method till now. Students at the Rareskills bootcamp created a novel and more gas efficient way of allowing projects to whitelist buyers for a presale or an airdrop.

Gas cost of the new method

• RSA 896 bit Metamorphic (Gas: 27,040)

• RSA 960 bit Metamorphic (Gas: 27,115)

• RSA 1024 bit Metamorphic (Gas: 27,311)

• RSA 2048 bit Metamorphic (Gas: 29,901)

Even when using a 1024 bit key, you can expect to save 2000 gas.

Before diving into to further optimising the codebase, let’s get a 30000 ft view of how the method works.

The novel method

This new approach utilises signature verification but uses the RSA algorithm instead of ECDSA. The team will sign a message (typically the address of the recipient) off-chain and this message gets verified on chain. RSA is an older algorithm and its keys are larger in size than ECDSA. RSA public keys are usually greater than 700 bits.

Storing, lets say, a 1024 bit public in contract storage to verify the signatures would require four storage slots. Cold read from the four storage slots alone would have cost 20000 gas. As each ethereum transaction has a fixed cost of 21000 this would have resulted in the transaction using over 41000 gas.

The solution here is to store the public key in the contract bytecode. But storing the public key in the whitelist contract bytecode itself would prevent updating whitelist members as that require changing the public key.

This is where metamorphic contracts come in. Bytecode of metamorphic contracts can be changed by using a mix of CREATE2 and SELFDESTRUCT. A metamorphic contract can be used to store the public key for the whitelist contract.

After retrieving the public key from the metamorphic contract, the signature is verified with the help of the arbitrary precision modulo exponentiation precompile at 0x05. The need for using this precompile arises because the EVM cannot load numbers greater than 256 bits onto the stack and RSA public keys are typically greater in size.

You can read a detailed article on this method here.

The challenge

Rareskills posted a challenge on twitter inviting people to optimise the codebase further. Reading metamorphic contracts, assembly and gas optimisations in the same tweet, naturally got me interested.

The gitcoin page of the contest mentioned that they would be judging based on the gas utilisation of the verifySignature function for a 1024 bit signature.

Let’s start

Disclaimer: All the code is in Yul.

Preaparing Calldata for 0x05

This snippet of the code on the left is storing the lengths of the signature (Bsize), exponent (Esize), and modulus (Msize) in memory.

It was storing these value from 0x80 in memory. This is where the free storage pointer would be at that moment. This is how memory should be handled when using inline assembly — by using memory from the location that the free memory pointer points to and then updating the free memory pointer.

But in our case, the control never transfers to solidity after the end of the assembly block, so its safe to override the memory conventions of solidity. Remember, the reservation of the first 128 bytes of memory is a solidity convention not an EVM rule.

So, we can start storing data straight from the 0x0 byte. This will eventually save us gas as memory expansion is expensive in EVM. Subtracting 0x80 from the memory locations from the left and simplifying will result in the code on the right.

To save an additional one unit of gas we can use returndatasize() instead of writing 0x0 in line 1 above. returndatasize() will return zero as no external call has been made yet in the current execution context. returndatasize() costs two units of gas while PUSH1 0x0 will cost three.

In the snippet on the left, the signature, exponent, and modulus in memory are being stored in memory. On the right, I have subtracted 0x80 from all memory locations, inlined the value of modPos and used msize() instead of the numeric value of the maximum memory size.

Using msize() saves 1 gas over using PUSH1.

Calling the 0x05 Precompile

Here, the 0x05 precompileis being called, with the prepared calldata. The precompiled contract will return us an address that we will later verify against the msg.sender.

The first two arguments for the staticcall are gas and address.

The third arguments instructs the EVM to copy calldata from the given offset in memory and the fourth argument informs the EVM the byte size to copy. As calldata was stored from the 0x0 byte, we can use returndatasize() to push zero onto the stack. We use msize() as the fourth argument as it returns the highest memory location.

The fifth and sixth argument instructs the EVM to store the returndata to the given offset in memory. As we don’t need the calldata anymore, we can store the returndata from the 0x0 byte, so we use returndatasize() to push zero onto the stack. For the return size argument, we pass the size of the signature.

Checking the return data

Its the same loop on both the sides, only difference being the loop on the right is optimised to utilise fewer opcodes per iteration. The goal here is to ensure that only the last 32 bytes in the returndata contains non-zero values and as we can only load 32 bytes at a time from memory, we are checking in 32 byte chunks. Since, the return data is an address and addresses are 20 bytes, all leading bytes should be zeroes.

Verifying the results

In the last part of the function, we check if the last 20 bytes of the returndata is equal to the address of the msg.sender.

True and false in EVM is a non-zero and zero value respectively. I have replaced 0x01 with codesize() as that is one gas cheaper and is certain to be non-zero. Further I have removed the mstore(0x00, 0x00) from the false case as we have already verified in the loop above that this memory location will be zero, else the EVM would have reverted.

Thats it, this is the end of the verifySignature function. I have made more gas optimisations in other unrelated business logic functions which I am reading up to the reader to figure out. All changes are here.

Results

How much gas did we shave off?

Using clever gas optimisations and some Yul magic, we brought the gas cost for a 1024 bit key down to 27138. This is a reduction of 173 units of gas. For an NFT collection with 5000 whitelist spots, we would save the users nearly a million units in gas collectively.

Conclusion

Well, this challenge was fun! Follow me on twitter for more optimizoor and security things.