ERC20 snapshot using Merkle Trees
Token contracts which implement more features than just implementing the token logic are bound for vulnerabilities. If one is exposed, the contract will have to be redeployed. This immediately raises the question: what if we want to redeploy a token contract? How do we give the users their tokens back? The solution I propose here is that all users who had tokens at the snapshot can now retrieve their tokens themselves and hence pay for their own gas. Proving that they had their tokens does not need a centralized trusted setup, they only need to connect to an archive Ethereum node.
Uploading the entire storage
A logical way to do snapshot tokens is to setup a new contract and simply giving the users their tokens back, given a snapshot at a certain block (before the exploit happened). However, this means that the owner of this contract has to pay a lot of gas. It also raises the question if it is necessary to refund users dust amount of tokens. They probably intended to move all their tokens out of the wallet, but instead just left a few. Is it ethical to not give those users their tokens back?
For every storage write, 20k gas is used, which is about the same amount of gas which you use if you send ETH to another address (which costs 21k gas). Hence, if 1000 addresses would need to get a refund of tokens, at least 20M gas has to be used, which at the time of speaking are 2.5 full blocks and we completely ignore the gas used on other logic which is being executed, such as paying for call data and memory management, which will yield much more in gas costs!
The server solution
Another way to solve the problem is to setup a centralized server which gives users a signed message, showing that the server allows them to “mint” their old tokens back to themselves. The user can now upload a transaction to the chain where they also provide this signature. This means that the user has to pay for gas and also means that only the users who wish to get their tokens back will go on-chain, reducing the network load.
However, this has two glaring problems. The first is that the server itself has the power to mint themselves any amount of tokens, which immediately means the value of the token is coupled to trusting that the server never mints themselves a huge load of tokens. The second is that the server has to be online so users can ask the server for a new signature. If the server goes down after a year and an user still wants to claim their tokens, they will then find out it is impossible because the claim time is over.
The Merkle Tree solution
As seen above, the two solutions both have a problem: the first stresses the network a lot and the second centralizes the token supply. The Merkle Tree solution allows users to claim their tokens at any point: the only thing they need is a connection to an archive Ethereum node.
A Merkle Tree is an efficient way to show that a subset of data was part of a larger dataset. This is exactly what we need here: we want to show that a combination of an address and a balance is part of the larger dataset, namely the snapshot. Let’s see how this works.
In Figure 1 a simple Merkle Tree consisting of 4 accounts is shown. What is done first is hashing the data, which in this case is the address of an account and their balance. This results, for example, for account A in Hash A. Now to move further down the tree we also need to know Hash B and then Hash(A,B) where both hashes (32 bytes long each) are concatenated and then hashed. This results in Hash(AB). To get the Merkle Root we also need to know Hash(CD) and then Hash(AB,CD) together (hence concatenating the hash of AB and the hash of CD and then hashing the result) to get the Merkle Root.
Hence in order to get the Merkle Root you first need to know the entire dataset (all accounts and their balances) and then following this protocol so every time you get one level “deeper” into the Merkle Tree. At the end you only have one hash, which is the Merkle Root, which we can now use to prove that certain accounts and balances were part of this snapshot. The Merkle Root is thus uploaded to a new ERC20 contract on-chain.
The beauty of this is that if you need to prove that some data is part of a Merkle Root you only need a very small amount of data: you only need to know the other hashes so in the end you get the Merkle Root.
Note that forging this data is impossible, because this implies you can create a new hash which then hashes to something which is known. This immediately breaks the hash function, because it implies you can invert the hash function. Changing a tiny fraction of the input data will result into a completely different Merkle Root, a property of hash functions called the avalanche property.
Let’s take a look at how proving that a certain account with a certain balance was part of this snapshot. In Figure 2 we try to prove that block F (which is the hash of the account F and the balance at the snapshot) is part of the dataset. We can only it prove if we know the hashes which end up at the Merkle Root (shown in orange in Figure 2). Retrieving the necessary data can be done from any archive Ethereum node. We simply query all balances of the contract at that point, create our own Merkle Tree and now get the necessary data from there. Of course, it is easier to give the users the entire database file so they can calculate their own proofs, or setup a server which just gives users the proof which they have to upload. The point is, however, that it is clear that the proof can always be retrieved if the user has a connection with an archive node, which essentially decentralizes the support of the snapshot.
To end up at the Merkle Root we hence need to know what hashes F to EF: hence we need to know hash E. To go to EFGH we need to know hash GH and to know how to go from GH to the Merkle Root we need ABCD. Hence these four hashes prove that F is part of the snapshot!
Verifying in the contract
To let an user claim their tokens, they call the “claim” function, which accepts any account (other accounts are free to claim tokens for other addresses too), their balance, and a list of hashes plus their order. Note that it is necessary to know in what order we hash: if we hash(EF) this is different than hash(FE).
At the start, the contract hashes the account and the balance. This should result in hash F. Now the provided hashes on the list are traversed and are hashed in the order which the user provides. If only one item is left, this should be the Merkle Root. The user then gets these tokens on their balance and their account is marked as “claimed” so the user cannot transfer tokens and re-claim the tokens.
Discussion
This solution shows the power of Merkle Trees. However, it is debatable if this is an elegant solution. In the end, if you compare the gas usage to the “simple” solution where the owner immediately stores all data in the contract, then this gas usage is higher provided all addresses claim their tokens. This is because there is an overhead in logic, plus an extra storage slot is written to store that an user has claimed their tokens.
However, if the token has a lot of “dust” addresses it might result in less gas usage as users who have almost no tokens have no reason to claim them. This hence filters out writes to storage which are unnecessary at that point.
I hope this has shown you the power of Merkle Trees and have maybe given you some inspiration to create something cool with them!
A proof of concept is available at https://github.com/jochem-brouwer/ERC20Snapshot
