With a good algorithm, you can simultaneously solve several problems associated with smart contracts that work with large lists of user addresses. You can’t add a list of several thousand addresses to a contract and allow this set of addresses to do something in that contract. The blockchain tries to save every single byte, so it would be too expensive to have so much data there.
To solve this problem, the contract code needs to be able to determine whether a given address is whitelisted. If the verification is successful, the required action can be performed. The proposed solution is quite simple: the contract only stores one number(merkle-root) and it is the customer’s obligation to prove that the address is whitelisted. The algorithm was proposed by the brilliant cryptographer Merkle and widely used in almost all decentralised software to ensure the integrity of data sets.
A common practice is to issue your own token and send it in small quantities to tens of thousands of addresses that have, for example, at least 1 ETH in their wallets. This type of spam is currently a popular way of promoting tokens. Not many people like someone’s unknown tokens appearing in their wallet. However, projects need this and airdrop orders are very popular. This is usually done in the following old-fashioned way (based on Ethereum, but it is also suitable for other blockchains that use smart-contracts, including EOS):
This approach consists in simply iterating over a large list of addresses and sending tokens to each of them. In decentralised systems, this push strategy is usually far from the best; it is expensive, generates security vulnerabilities and is, in fact, just spam. The disadvantages can be described in slightly more detail as follows:
However, there is a much simpler solution, common for decentralised networks, that delegates most of the computational tasks to the client-side software. In this case, access control is based on the Merkle tree, which is a very convenient data structure that allows the contract to store just one fixed-size number (merkleRoot) with information about all the data in this tree (for example, a huge list of recipient addresses). It doesn’t involve any magic: the client application provides information, proving that the address is in the list of allowed addresses, by itself. To do this it performs relatively complex calculations and eliminates the need for the contract to view a huge list of addresses. If you are interested in cryptocurrencies, then you should already know about the Merkle tree; if you don’t, then you should find out about it, as this structure is very useful for solving many problems.
I also mentioned the ACL, or Access Control List, that refers to file systems: this is a way to specify the rights to an object in the form of a list of accounts and access types. I use this term to show that this algorithm is suitable for creating huge ACLs that provide access to a certain contract feature to millions of accounts. To do this, save a single number in the contract to make sure the account is in the list.
But let’s focus on the scheme including airdrop, as it is now extremely popular in the market and is a simple and clear example of smart contracts with large ACLs.
I hope you already know what a smart contract is (as well as a token contract) and understand how it works. As you know, a smart contract is first deployed onto the Ethereum network and receives its own address and balance, after which the smart contract accepts and processes incoming transactions.
In the merkle-airdrop scheme, tokens are not distributed using an address list, instead users ‘claim’ their tokens themselves by sending a transaction to the contract and paying a fee. The secret is that users add special data to the transaction allowing the contract to easily verify that they are whitelisted, and the contract does not have to store the list itself. In this case, the contract is the most cost-effective, because it needs only one (!) number for an address list of any (!) size — this is the essence of this great algorithm. Such a contract is also extremely simple to launch, and it does not require any support after launch; moreover, this simplicity also ensures maximum safety when used. We will discuss these aspects later.
The scheme with a merkle-airdrop contract works approximately as follows:
In general, merkle-proof can be described as ‘the path from the user’s address to the merkle-root through the branches of the Merkle tree’. This requires quite complex calculations and extra data, which we took out of the contract and saved the most expensive resource in the blockchain — storage. The merkle-proof consists of log2(N) hashes (rounded up to the nearest whole number). The size of each hash corresponds to the size of the merkle-root, which we saved in the airdrop contract. So the user must provide 10 hashes for a list of 1,024 addresses, but only 32 hashes for about 4 billion addresses. The protocol for creating and presenting the proof is the basic feature of the contract, which makes it possible to store a minimum amount of information to confirm that certain data belong to a very large list. Moreover, the larger the list is, the greater your benefits will be.
In fact, the contract also provides for the ability to pick up unused tokens, update the merkle root, and impose time limits, such as prohibiting the issue of tokens after a certain period of time. After a simple modification, the contract will be able to issue an arbitrary number of tokens to each address; in this case, the file will store not only the addresses of the recipients, but also the necessary amounts of tokens. In addition, you will need to slightly modify the function to check merkle-proof, however, the general algorithm remains almost unchanged.
Let’s describe the advantages and disadvantages of the above method compared to traditional script-based distribution.
There are no secrets in this algorithm, and the contract storage savings are offset by the intensive operations of client-side applications to verify that addresses belong to the list. This approach clearly demonstrates the difference between the models of using smart contracts in comparison with traditional centralised systems.
The advantages of the traditional scheme for distributing tokens using a script are just simple and clear workflows. In addition, the developer needs to make much more effort to run the usual airdrop compared to the publication of a merkle-airdrop contract. Moreover, the running script should be monitored to take appropriate measures if the operation is interrupted in the middle of the list or the funds to pay the transaction fee have been exhausted; you also need to make sure that no one can steal private key used by the script to sign transactions. And if you have a file with addresses, you do not need a developer at all. You don’t have to be a developer to deploy such a contract, it can be done very simply by using public services.
Merkle-ACL is not the single solution, there are other good “claim” algorithms with simpler logic, more effective from smart contracts view. For example when a user presents the “pre-signed right to claim tokens” that he found in public whitelist. But from the user’s view, this way is harder, because the contract owner has to build a huge whitelist and sign every line with the proper secret key. Yeah, there is no “free” features in programming.
In addition to the basic smart contract, a complete DApp for the merkle-airdrop has some implementation specifics. The merkle-airdrop scheme delegates a large number of operations to the code in the user’s browser, which, for example, must create a merkle proof after processing the entire address list. The list of addresses should be stored somewhere publicly, and for the user this procedure should be no more difficult than uploading a file to the server.
Therefore, our merkle-airdrop constructor for the Smartz.io platform allows you to upload the address list into IPFS and provide this list to the client. In addition, we have developed special JS widgets to work with the file of the address list in IPFS. In the final version of DApp, we plan to store IPFS information directly in the contract to have 100% of the data for airdrop in the blockchain. At the moment, we have released a fully functional beta version and we’re working on next usability improvements. We are also developed a merkle-airdrop constructor for EOS tokens, as it has a similar interface and internal logic.
In general, the trend for increasing the complexity of the client code takes place in all state-of-the-art solutions, and the merkle tree is only the first of such interesting algorithms. Other schemes such as ring signatures, zkSNARKs, state channels, etc. also require complex browser-side calculations, so Smartz is preparing to implement large and complex JS components in constructor interfaces on the client side. And we recommend that you also get involved in this process.
The main ‘advantage’ of traditional list-based token distribution is that this scheme allows you to send tokens even to those users who do not want to receive them. In addition, there are such damn features that involve sending so few tokens that the exchanges do not even allow transactions to be made with them and users are forced to put up with the presence of such ‘leftovers’ on their addresses, as they cannot get rid of them.
The concept of an airdrop, when a company distributes part of its system tokens to the community, is of course extremely important for the projects’ lifecycle. But we believe that this solution is not all user-friendly and is wholly inefficient. Moreover, DApps tend to implement the ‘pull’ instead of the ‘push’ concept; this means that it is the network users who are the initiators and supervisors of business processes, so the approaches when someone centrally imposes something on tens of thousands of users are gradually fading into the past.
Let’s sum up brief advantages of the Merkle airdrop:
You can already try to deploy the contract of Merkle Airdrop using a specific template on Smartz platform. Beware to have the contract deployed MetaMask browser extension or Trust Wallet for mobile are required. For Solidity techies: the source code of this smart contract is available on GitHub, see the link below.