Merkle tree and proofs for distributor
Merkle tree is a tree in which every leaf node represents the hash of the data block and every non-leaf node is the hash of its child node.
For the construction of the Merkle tree for distributors, a hash is generated for the address and amount to be distributed to that address for every leaf. After that by the successive hash of the leaf nodes, the Merkle root is generated. For the above diagram, hashes of all the addresses and their amount are computed as Hₐ Hᵦ and so on. By successive hashing, we get the Merkle root H(ABCDEFGHIJKLMNOP).
Now the question here that arises is what are the proofs and how do we verify that a hash is one of the leaves of the Merkle tree using proofs and Merkle root? For explaining that, let's take an example for a hash H(K). While constructing the Merkle root for H(K), we first added the hash of H(K) and H(L) to form H(KL). Then H(IJ), H(MNOP), and H(ABCDEFGH) were added successively to the hash to compute Merkle root. Here, the list of blue highlighted blocks i.e, H(L), H(IJ), H(MNOP), and H(ABCDEFGH) act as the proof for H(K). These hashes are passed to the smart contract and the Merkle root is re-computed with these proofs and the leaf H(K). If the computed Merkle root and original Merkle root match then we can verify that the hash is a genuine leaf of the Merkle tree.
Now let's look at the Scilla contract and see how is it done in the smart contract itself.
This is a transition to claim the LMR by providing proof of inclusion in Merkle root. Claim ADT consists of 3 values i.e, epoch number, leaf, and proof. The epoch number is basically an index that Zilswap uses to determine the week of reward. The leaf is composed of account and amount that are hashed to generate the leaf of the Merkle tree and the proof which is the list of hash required by the leaf to construct Merkle root.
First, the hash of the leaf with the amount is calculated by the lash_leaf function. hash_leaf is util that can be found in the DistributorLib library. It hashes the amount and concats account address and amount hash together to form the leaf of the Merkle tree for which the claim operation is run.
In this transition, the IsUnclaimed procedure is used to verify that the user hasn't claimed using the same leaf before. After that VerifyInclusion is used to verify the leaf of the Merkle root.
In this procedure, the hash_leaves function is used which is another util from Distributor lib. It is used for successive hashing of the leaf hash and the proofs and generating the Merkle root as explained earlier. @list_foldl is used to iterate in the proof list from the left.
After that the merkle root and computed merkle root are compared and thrown an error if the proof isnot valid. If it is valid, the operations continue and the reward amount is transferred to the address which is in the Claim transition.
You can have a more detailed look at this contract in
The last part of the distributor is the use of the backend for generating Merkle roots and storing Merkle proofs. We store the merkle proofs for each leaf in backend while generating the merkle root and fetch before we make the claim transaction in smart contract. The APIs that are used in the Zilswap distributor to do so are listed below.
For generating merkle root:
/epoch/generateFor fetching the proof of address:
/distribution/data/{address}The data model used to store these proofs data for distribution can be see in models.rs which looks like
Since it uses SHA256 for hashing, we can implement this functionality in any other languages apart from RUST as well.
