The evolution of Airdrop

Airdrop is a popular way to distribute project tokens to the community. So popular that it quite often led to congestion in the Ethereum network and, later in the EOS. The result happened to be the same: a huge bump in commissions prices for transactions.

Last year, such a mechanic, which was used to vote on the FCoin exchange, led to dire consequences for the entire Ethereum network. In this article, we discuss the modifications that can be applied to airdrop mechanism.

A good algorithm allows you to solve several problems with smart contracts, which operate with large lists of user addresses. The fact is that putting a list of even several thousand addresses in a contract and allowing this set of addresses to do something in the contract will not work out directly — the blockchain saves every byte and it is too expensive.

To solve the problem, it is necessary to determine in the contract code whether this address belongs to the list of “good” addresses. If yes, then allow the desired action. Now, a new method that is suggested allows you to quite simply solve this problem, holding in the contract only one number. The brilliant cryptographic algorithm of Ralph Merkle is widely used in almost any decentralized software to ensure the integrity of data sets.

Airdrop and ACL (Access Control List)

There is a bad practice nowadays— to release your token and send out small quantities to tens of thousands of addresses that have, for instance, at least 1 ETH on the balance or it may be any other parameter or a definition of a targeted group of addresses. Such spam recently became extremely popular to promote your own tokens. Very few people like the appearance on their balance of someone’s unknown tokens. However, projects need this, and orders for airdrops are becoming more and more popular. This is usually done in the old fashioned way, like this (using Ethereum, for instance, but other blockchains with contracts, EOS, for example) are also suitable:

• Parse a blockchain and find a lot of addresses for the specified criteria;
• The next step is to create an address where enough tokens are stored for distribution to everyone from the list, or provide a token in the contract to create (mint) the required number of tokens to a given address (when sending a transaction from a special preferred address);
• You have to make sure you load enough gas to pay the fees for each shipment of tokens to the user;
• After that they launch a mailing script that iterates through the addresses and for each creates a transaction that transfers (or passes) the tokens to the specified address.

That is, it’s just going through a pile of addresses and sending out tokens to everyone. In decentralized systems, such a push strategy is usually quite lame, expensive, creates security holes, and in general is spam. Among its shortcomings:

• A lot of money is spent on commissions (the more addresses, the higher the commission). In addition, at the time of mailing, commission amounts can grow, because the load on the network grows, the cost of the transaction grows too;
• Mailing requires writing a script that will send transactions, and the secret key is sewn up in the script, which gives access to a heap of tokens;
• It is necessary to program the newsletter and be able to continue from the place where everything broke.
• In this case, there is a much simpler solution, which, as is customary in decentralized networks, gives most of the work to software on the client side. This is access control using the Merkle tree — an extremely convenient data structure to store only one fixed-size number (merkleRoot) in the contract that contains information about all the data included in the tree (about a huge list of recipients, for example).

There is no magic here: information proving that the address is on the list of allowed addresses, the client code provides on its own, doing relatively large calculations, and eliminating the contract from having to view a huge list of addresses. The structure of the Merkle tree is extremely useful for a variety of tasks.

So, this algorithm is suitable for creating huge ACL (Access Control List), which allow providing access to a certain function of the contract for millions of accounts. To do this, you need to write in the contract a single number to verify that the account belongs to the list.

Consider a scheme with airdrop, since It is now extremely popular in the market and is a simple and demonstrative example of smart contracts with large ACLs.

DApp scheme

To begin with, it is worth recalling that the smart contract is first deposited into the Ethereum network, after which it receives its own address and balance on the network, and then it accepts and processes incoming transactions within itself.

In the Merkle-airdrop scheme, tokens are not sent to addresses, and users themselves “request” their tokens by sending transactions to the contract and paying a commission. The secret is that users add data to the transaction, allowing the contract to easily check whether they are in the “good” address list, and the list itself is not necessary to remember the contract. The contract itself is extremely economical, it needs only one number for a list of addresses of any size — this is the essence of this excellent algorithm. And such a contract is extremely easy to run, after which it does not require any support at all, and due to this simplicity, it is also extremely safe to use. But we’ll get back to these moments a little later.

Smart Contract

Here is how the whole scheme works with the Merkle-airdrop contract:

• A token contract is deployed on the network (or is already present there).
• It creates a list of addresses that are allowed to “request” their tokens. The list is generated based on the blockchain analysis, compiled on the website or otherwise.
• All addresses are placed in one rather massive file that will be available publicly at a certain URL. For example, you can put it in the IPFS protocol, but you can use any method to upload a file and then read it from the client browser.
• A script is “thrown at the file”, which of all the addresses it contains builds a Merkle tree, and it receives a single hash, Merkle root. This root is the main parameter of our contract that will issue tokens.
• Contract merkle-airdrop should also be deployed on the network. When laying out, he remembers Merkle root and the address of the contract token so that he can transfer this token to the recipients.
• A large number of tokens are put on the balance of the airdrop contract (by a regular transfer), sufficient to issue to all participants on the list.
• Now the airdrop contract has an outside available claim-tokens-by-merkle-proof function, which accepts Merkle-proof for input from the user — proof that the user is in that very big “good” address list.
• If the proof is correct, the contract performs transfer() from its address and translates the tokens to the user.

A User

And this is what happens on the client’s browser (all operations are performed by client-side JavaScript right on the DApp page):

They find their address in the “good” list, which is publicly posted somewhere on the Web (for example, in IPFS) and makes sure that he has the right to tokens.

The Merkle tree builds from all the addresses in the list, and from it gets the same merkle-proof, which is a few numbers (hashes), their number depends on the size of the list, but compared to it is very small, for example, for ~ 100,000 addresses is enough ~ 17 hashes (size merkle-proof: log₂N, where N is the number of elements).

Sends a transaction to the contract that calls the claim-tokens-by-merkle-proof function and sends the received merkle-proof to it. The contract remains to verify the proof (using the saved merkle-root) and transfer () tokens if the proof is correct.

The contract remembers who he issued tokens to prevent re-issuance.
In general terms, merkle-proof can be described as “the path that can be passed from the user’s address on the Merkle tree to the merkle-root itself.” This is quite a serious computational work and superfluous data that we have thus taken out of the contract, saving the most expensive essence in blockchain — storage.

Merkle-proof proof consists of log₂N hashes (rounded up to the whole). Each hash is the same size as the merkle-root, which we recorded in the airdrop contract. That is, for the list of 1024 addresses, the user must provide 10 hashes, and for ~ 4 billion addresses — only 32 hashes. It is in the protocol for building and presenting evidence that the main feature of the contract is hidden — storing a minimum amount of information to determine if some data belongs to a very large list. And the bigger the list, the greater the gain.

In reality, the contract is supplemented by the ability to pick up unused tokens, update merkle root and impose time limits, for example, prohibit the issuance of tokens after some time. The contract is easily finalized to distribute an arbitrary number of tokens to each address, in this case not only the recipient addresses are stored in the file, but also the necessary amounts of tokens and the function for checking merkle-proof is slightly modified, but the general algorithm does not change much.

Pros and Cons of merkle-airdrop

Separately, it is possible to highlight the advantages and disadvantages of the above method compared to the traditional mailing script:

Pros:

• A transaction requesting tokens costs little gas, and this number is a constant depending on the size of the white list;
• After the launch of the contract, it does not require the slightest support, all activity is provided by users;
• Allows you to work with lists of almost arbitrary size with minimal blockchain storage.

Cons:

• It is necessary to lay out the public list of addresses somewhere;
• The client code needs to view all the addresses in the “white” list and execute a rather resource-intensive code.

There are no secrets in this algorithm, such again from the memory of the contract is generously “paid for” by the operation of the code on the client side to verify the membership in the list. This approach extremely successfully demonstrates the difference in the patterns of use of smart contracts in comparison with traditional centralized systems.

The traditional mailing of tokens by the script in response can counterpose only a simple and clear scheme of work. And the developer’s efforts to launch the usual airdrop are several times higher than the effort to display the merkle-airdrop contract, the running script must be monitored so that it does not fall off in the middle of the list, so that it does not run out of funds for transaction fees, ensure that no one steals the key with which the script signs transactions. Plus, if you have a file with addresses, you don’t really need a developer — it is extremely easy to implement such a contract using public services.