# Optimising the most gas efficient whitelist contract in Yul

By [0xMonsoon](https://paragraph.com/@0xmonsoon) · 2023-02-01

---

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](https://blog.openzeppelin.com/the-state-of-smart-contract-upgrades/#metamorphic-contracts) 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](https://www.evm.codes/precompiled#0x05?fork=grayGlacier) 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](https://www.rareskills.io/post/solidity-rsa-signatures-for-aidrops-and-presales-beating-ecdsa-and-merkle-trees-in-gas-efficiency).

### The challenge

[https://twitter.com/RareSkills\_io/status/1615863541818613761](https://twitter.com/RareSkills_io/status/1615863541818613761)

Rareskills posted a [challenge](https://twitter.com/RareSkills_io/status/1615863541818613761) 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](https://gitcoin.co/issue/29685) page of the contest mentioned that they would be judging based on the gas utilisation of the `verifySignature` [function](https://github.com/RareSkills/RSA-presale-allowlist/blob/c1c070499d2d75e7efae05a28f44feba7d00d4cb/contracts/Rsa.sol#L106) for a 1024 bit signature.

### Let’s start

_Disclaimer: All the code is in Yul._

**Preaparing Calldata for** `0x05`

![The 0x05 precompile takes six inputs from memory. All the arguments would need to be loaded into memory in the given order.](https://storage.googleapis.com/papyrus_images/3532b8152810f8cc6b5601b49e1baef3e4dca683f2416d1bb00c5a51dc9afca1.png)

The 0x05 precompile takes six inputs from memory. All the arguments would need to be loaded into memory in the given order.

![Loading the byte sizes of B, E and M into memory](https://storage.googleapis.com/papyrus_images/791924c5ae534846335a2bfff3c7f2a63bc662ce7094ec7a5395eecce13e9e64.png)

Loading the byte sizes of B, E and M into memory

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](https://betterprogramming.pub/solidity-tutorial-all-about-memory-1e1696d71ee4) 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.

![Loading signature (B), exponent (E) and modulus(M) into memory](https://storage.googleapis.com/papyrus_images/9b78c137498960ecd4119899c40151001d06198c2194516e9c2d9c1ffe1a9ba2.png)

Loading signature (B), exponent (E) and modulus(M) into memory

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**

![Staticcall takes six arguments from the stack](https://storage.googleapis.com/papyrus_images/a98ce1684bf2ce7961380fb15bee589393c90405b979d766f057597cd25763a0.png)

Staticcall takes six arguments from the stack

![Calling the 0x05 precompile](https://storage.googleapis.com/papyrus_images/dc904091be170fea046489f56d91f7e516a9e5329e2e93a2b65f3f9ba207e913.png)

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**

![Checking if the return data is valid](https://storage.googleapis.com/papyrus_images/e7e4e5df436f380cf729c0f9c2b1d8095c78be1e513512137d9dfa1700bfcaa5.png)

Checking if the return data is valid

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**

![Checking if the signature is valid](https://storage.googleapis.com/papyrus_images/729c4a858085422e3c09f66eff32fc8f3237d5ff826235da9fd06f4cdc6f3ed5.png)

Checking if the signature is valid

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](https://github.com/RareSkills/RSA-presale-allowlist/compare/c1c0704...afd3b94).

### Results

![Gas test results](https://storage.googleapis.com/papyrus_images/23922e73ed8d6bc9fceaa731d1b5c2675837fdf088e489b09821af40cf32753a.png)

Gas test 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](https://twitter.com/0xmonsoon) for more optimizoor and security things.

---

*Originally published on [0xMonsoon](https://paragraph.com/@0xmonsoon/optimising-the-most-gas-efficient-whitelist-contract-in-yul)*