Solidity RSA signatures for aidrops and presales: Beating ECDSA and Merkle Trees in Gas Efficiency By and Suthan Somadeva Michael Burke Introduction Creating a contract that gives certain addresses permissions goes by several names: airdrops, presale, whitelist, allowlist, and so forth. But the essence of the idea is there is a set of addresses that have special permission to buy a high-demand token for a desirable price (sometimes free). There are three established solutions for this: mappings, Merkle trees, and ECDSA signatures. The relative merits of these approaches have already been , so we will summarize the results: discussed elsewhere ECDSA Signature Verification (Gas: 29,293) using Merkle proofs (Gas: 30,517, 128 addresses) A mapping presale works when the seller enters the addresses of the customers into a mapping that goes from address to boolean to note if the address is privileged or not. The mapping is set to false after the buyer completes the transaction. This ensures only addresses that are marked true can make a purchase. This is very gas efficient for the buyer, but the seller could allow-listing thousands of addresses, (it will cost at least 22,100 gas to add an address to the allowlist). spend millions of gas Because of this, Merkle Trees and ECDSA signatures (using the precompile , or better yet, the published by OpenZeppelin), are often preferred to mappings. The gas cost (for the buyer) of executing the ECDSA signature verification is 29,293 gas. This includes the 21,000 to initiate the transaction, so the ECDSA cost is 8,293. Note that this includes reading the signing address from storage, but this cost is necessary or we won’t be able to invalidate signatures. ecerecover more secure wrapper around it Merkle Trees vary in cost based on tree size (larger trees require larger Merkle proofs), but if over 1,000 addresses are in the Merkle tree, it will cost at least 32,000 gas (or more) to verify the address. This cost is clearly inferior to ECDSA. The goal, then, is to beat ECDSA which costs 8,293 gas. To keep solutions apples-to-apples, the alternative solution must: Be able to nullify allow-listed addresses. Merkle trees can change their root, ECDSA , can change their signing address, and mappings can set the value to false. Not impose a substantial cost burden on the seller the way mappings do Cost less than 8,200 gas for the buyer (including a storage load) Not be compromised on security Prerequisites To understand the proposed methodology, the reader should be familiar with the following subjects: Precompiled smart contracts ( , ) recommended reading stackexchange Metamorphic contracts ( , ) introduction recommended reading Access lists ( ) recommended reading How to use digital signatures and their appropriate use cases in blockchain applications How gas cost is computed, especially as it relates to calldata, opcodes, storage, and memory usage. The RSA Algorithm If we want to substantially beat ECDSA, we need to find a different cryptographic algorithm that allows for the proof of set membership. ECDSA is actually the newer, cooler version of the original digital signature algorithm, RSA. ECDSA relies on discrete logarithms over elliptic curves being hard (hence the name – elliptic curve digital signature algorithm). RSA (named after its authors, Rivest, Shamir, Adleman) relies on large integers being hard to factor. In terms of age, RSA was published in the 1970s, but ECDSA became a formal specification in the early 2000s. We will not explain RSA in detail here, but some prerequisites are in order. The signer picks two large prime numbers p and q, and multiplies them together to produce n. This is the first part of the public key. Second, the signer picks a small prime (can be hardcoded to for our usecase), and publishes the pair as the public key. Behind the scenes, the signer computes n e 3 (n, e) t = (p - 1) * (q - 1)
d = t^(-1) % n The number is the private key. If an adversary could decompose into and , then computing would be trivial. But it is known that . To sign a message, the signer hashes the message to get and raises to the power . That is, d n p q d integer factorization is hard m h h d s = h(m) ^ d % n The signer then publishes as the message and signature. (m, s) The verifier then hashes and raises it to the power . Remember, and are the public key. If and only if m e mod n e n s == s ^ e % n then the signature is valid for the public key . Note that if is extremely large, then the probability that by random chance is vanishingly small. If the equality checks out, then we know the signature is valid for the public key. (n, e) n s == s ^ e % n To do this in Ethereum, we would simply sign an address as s = buyerAddress ^ d % n and the smart contract would verify msg.sender == s ^ e % n Using only 256 bits is unsafe We say “factoring integers is hard” but clearly this implies that the number must be large enough. For example, 33 is composed of two prime numbers and is trivial to decompose. Thankfully, we have real-world benchmarks of what the state-of-the-art can accomplish in the . RSA Factoring Challenge To clarify, the number of “bits” refers to the size of the public key. Therefore, when we say “RSA 2048”, this means the number n, the modulus, has 2048 bits. When comparing key sizes, it’s important to remember that each additional bit doubles the size of the number. So 700 bits is exponentially more secure than 350 bits, not twice as secure. The largest key to be cracked (factored) so far had 829 bits, and it required a modern supercomputer to do it. The team utilized approximately 2700 CPU core-years, using a 2.1 GHz Intel Xeon Gold 6130 CPU. The cheapest 16 core CPU on AWS costs $0.40 cents per hour, so the cost to crack this key is in the order of $9.4 million dollars. Even assuming generous discounts from the cloud provider, the cost is in the millions. Modular arithmetic with more than 256 bits in Solidity Ethereum only supports 32-byte data types, so by default, we cannot carry out s ^ e % n Thankfully, the Ethereum blockchain added a precompiled contract in specifically to support modular arithmetic. To use it, the base, exponent, and modulus must be loaded into memory in abi encoded format. Then the contract living at address is invoked. EIP 198 0x05 Storing the public key becomes a bit of an issue if you use a secure amount of bits. If the key size is 1024 bits, that necessitates 4 storage slots. To read the public key out of storage would be four operations, for a total of 8,400 gas. This by itself is already less efficient than the ECDSA solution benchmarked above. SLOAD If we use immutable variables, this cost is largely eliminated, but this creates a weakness if we cannot retroactively remove someone from the presale. In traditional ECDSA or Merkle Trees, we would just replace the signing address or the Merkle Root. This isn’t possible if we use an immutable variable. However, storing the public key in the bytecode instead of storage is the key idea. Reading an external contract’s bytecode ( ) costs 2,600 gas, which is far less than the 8,400 gas of reading each part of the public key in four pieces. EXTCODECOPY To invalidate a public key, we could simply create a new contract, and update a storage variable to point to the new address. But that adds back an additional 2,100 gas. It turns out, it is possible to store the external contract’s address (whose bytecode stores the public key) in an immutable variable, but still invalidate the public key by mutating the external smart contract’s bytecode. Invalidating the public key with the metamorphic contract pattern A smart contract is created by loading the deployment bytecode into memory, then returning the range of the bytecode which contains the runtime code. See more . here When a smart contract is created with the command, the address of the contract can be predicted in advance. The address is calculated from the combination of salt, the deployer, and the initialization bytecode. If the contract self-destructs, then a new contract at the same address can be deployed. create2 Note that the address is a function of the initialization code, not the deployed code. It is possible to deploy different bytecode by having the initialization code load a different runtime code. By self-destructing and redeploying with the same initialization code but a different deployment code, the bytecode of the contract can mutate. Therefore, we can have a smart contract whose first bytes are for self-destructing under a certain condition, but the rest of the bytes are just the RSA public key. k Because the address is determined in advance, we can store the address of this metamorphic contract in an immutable variable. We can from that address when we need the public key. To replace the public key, we instruct the contract to , then deploy a new contract to that address. EXTCODECOPY selfdestruct Saving an additional 100 gas with access lists added a new type of transaction that allows the user to specify in advance which addresses and storage slots will be accessed. This allows the nodes to prefetch those values from storage, thus speeding up execution time. Using an access list transaction when calling an external contract can save 100 gas. Note that this saving does not apply when a smart contract accesses its own storage variable. Because this RSA presale airdrop design relies on an external contract to store the public key, then using an access list is appropriate. EIP 2930 Benchmarks: Gas cost vs key size Most of the gas cost comes from having very large calldata as a result of large signatures. If the key size is set to 1024 bits, then the call data will be 128 bytes. Each byte costs 16 gas, so the total gas cost just to have calldata that large is 2,048 gas. Compared to most other use cases, ours uses a considerable amount of memory, and Ethereum charges for this. Why this saves gas relative to ECDSA The benchmarks make it clear that the larger the key (and hence the signature), the larger the gas cost. Our design exploits the fact that the precompile assigns a low price to raise numbers to low power. The cost of executing the precompiled contract under those conditions at is only a few hundred gas compared to thousands for executing the precompile for ECDSA. 0x05 Choosing a key size Although a key with 829 bits has been factored in, it requires a modern supercomputer to do so. For applications such as airdropping lower-value tokens or putting NFTs on a presale, an attacker does not have the incentive to spend six figures to a million dollars to factor a public key and obtain an NFT in a presale. The most expensive Ethereum tokens at this time of writing ( and ) cost approximately $100,000 a piece, so for the vast majority of applications, it is not economical for an attacker to try to factor the public key. Fidenza Bored Ape Yacht Club Remember, each bit doubles the difficulty of factoring the integer, so as of 2022, most low-value token presales are probably safe with 896 bits. In this case, saving users over 2,500 gas compared to ECDSA is compelling. Key Size Benchmarks This was conducted with Solidity compiler version 0.8.17 with the optimizer set to 1 million RSA-896 (Gas: 27,040) RSA-960 (Gas: 27,115) RSA-1024 (Gas: 27,311) RSA-2048 (Gas: 29,901) Conclusion We present a novel method for assigning addresses to a presale or airdrop that is more efficient than the known solutions today. By combining the modular exponentiation precompile with the metamorphic contract pattern and the access list transaction, we can validate secure RSA signatures on-chain in a gas-efficient manner. Our work is only a proof of concept at this stage. Developers are advised to use caution using the code in production. This project was created by and as part of the . The code implementation and unit tests are on . Suthan Somadeva Michael Burke RareSkills Solidity Bootcamp github Also published here.

Too Long; Didn't Read

Discover Saakuru: Web3 Mass-Adoption with 0-FEES

Using Solidity RSA Signatures for Presales and Airdrops

Too Long; Didn't Read

RareSkills

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Using Solidity RSA Signatures for Presales and Airdrops

Too Long; Didn't Read

RareSkills

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES