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.

Construction of Merkle tree from leaves.

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.

Claim transition in Distributor

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.

hash_leaf

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.

VerifyInclusion Procedure in Distributor

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.

hash_leaves

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/generate

For 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

Distribution model

Since it uses SHA256 for hashing, we can implement this functionality in any other languages apart from RUST as well.

--

--

--

Publication where developers building on top of zilliqa blockchain share their learnings.

Recommended from Medium

Shift: Phoenix has successfully been integrated with the Shift blockchain

DeFiFarms: World’s First DeFi Ecosystem with NFT Protocol Farming on Binance Smart Chain

Shift: Development of Proof-of-spacetime algorithm announced

Recap: The first phase of GDAO AMA with INTCHAIN

VeChain: Blockchain-powered Solution to Your Problems?

Getting Started with Enterprise Blockchain Development with tutorial + hackathon videos

So It Begins: Countdown to Launch of Star Atlas Token Sale on FTX, Raydium and Apollo-X

Community Update — June 15, 2019

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Bibek Koirala

Bibek Koirala

A blockchain dev | Zilliqa Developer Ambassador | RedChillies Labs, Inc. | Pastel Soft | JS Security Technologies | AART

More from Medium

Could not resolve com.google.vr:sdk-audio:1.200.0

The Internet Protocol: Explained

Setting up your company to release apps on the Google Play Store

Developing on Golem #3 — Running your own Python Code on a provider