BitSong
Search
K

Merkledrop

Abstract

This document specifies the merkledrop module of the BitSong chain.
The merkledrop module enables the BitSong chain to support the ability to simply create custom token airdrops on chain. In this sense, any user can realize a custom airdrop for his community.
Fantokens owners can use this module to airdrop their new minted fantokens to their fans. Similarly, also tokenholders are enabled to create airdrop for any occasion (e.g., as the result of a competition).

Merkledrop

Based on the Merkle Tree data structure, the merkledrops are very performant airdrops for the BitSong community.
It is possible to identify each merkledrop through its id and the module allows the users involved to autonomously claim tokens in the temporal window between the StartHeight and the EndHeight blocks.
Thanks to the merkledrop module, users on BitSong can:
  • manage merkledrop, create and claim them;
  • build applications that use the merkledrops API to create completely new custom airdrops.
Features that may be added in the future are described in Future Improvements.

Concepts

Merkledrop

Merkledrops are basically airdrop (i.e., crypto projects sending free tokens to the communities in a bid to encourage adoption). They are based on the usage of the Merkle Tree. Thanks to the features of these data structure (i.e., a binary tree where each non-leaf node is the hash of its childs) they are particularly efficient in space usage and during the verification process (as explained in the Verification process).
A merkledrop is characterized by:
Attribute
Type
Description
id
uint64
It is an integer that identify the drop. It is assigned automatically by the module.
merkle_root
string
It should correspond to the hash root of the merkledrop.
start_height
int64
It is the block height value at which the drop allows the user to claim the tokens. It should be greater or equal to the current block height (the one where the transaction is included) and, if the user pass (as parameter) a value lower than the minimum available, it will be automatically set to the current block height. Moreover, there exists an upper bound for this value, that corresponds to the value of the actual block height + 100000.
end_height
int64
It is the block height value where the merkledrop is considered expired and an automatic withdrawal is executed if part of the tokens were not claimed. This value must be greater than the start_height and lower than a maximum value of start_height + 5000000.
denom
string
It corresponds to the denom of the token to drop.
amount
string
It is the total amount of token to drop.
claimed
string
It corresponds to the value of claimed tokens from the users. At the beginning it is 0 and is increased at each claim.
owner
string
It is to the address of the wallet which is creating the merkledrop.

Merkle Tree

The Merkle Tree is a data structure discovered by Ralph Merkle in 1979. In such a tree, every node (aka leaf) is labelled with the hash of a data block, and every non-leaf node is labelled with the hash of the of its child nodes. A simple example is depicted in the figure below, while more information can be found on wikipedia.

Verification process

The verification process corresponds to check if the proofs received are valid. In this sense, since it is used a merkle tree, it is possible to check whether the proof belongs to the merkledrop without having to deal with all the data that make up the tree. An exmaple of verification process is depicted in the figure below.
More specifically, in this example, G block of data is provided and, its hash can be simply calculated. Starting from this, it is possible to verify the correctness of the data by only using 4 proofs, since thanks to these hash values it is possible to calculate the merkle root and compare it with the value saved on the blockchain. In particular, by calculating HG, together with HH, it is possible to calculate HGH. This value can be used to calculate, together with the proof HEF, the value of HEFGH. This value allows, together with HABCD to calculate HABCDEFGH that, with HIJKLMNOP, allows to determine the merkle root. This value can be compared with the one saved on the blockchain to verify if the user can claim the tokens he says to own. Thanks to this approach, it is possible to save only the merkle root value on the blockchain and receive the proofs by the user.
This approach works thanks to the features of the hashing functions (in this implementation it is used the sha-256). In particular, it plays an important role the avalanche effect (i.e., a small change to the message should correspond to an high change in the hash result).

State

The merkledrop module keeps track of LastMerkledropId, Merkledrops, Indexes and Parameters.
LastMerkledropId: Uint64,
Merkledrops: []types.Merkledrop,
Indexes: []*types.Indexes,
Params: types.Params

LastMerkledropId

This value is an integer that corresponds to the number of merkledrops already created. It is used at the creation of a new merkledrop as its id.

Merkledrops

The state contains a list of Merkledrops. They are airdrop configuration, and their state information is:
  • Id that corresponds to the identifier of the merkledrop. It is an uint64, automatically incremented everytime a new merkledrop is created;
  • MerkleRoot, that represent the root hash (in hex format) of the merkle tree containing the data of the airdrop;
  • StartHeight, that is the block height value at which the drop allows the user to claim the tokens;
  • EndHeight, which corresponds to the block height value where the merkledrop is considered expired and an automatic withdrawal is executed if part of the tokens were not claimed;
  • Denom, which corresponds to the denom of the token to drop;
  • Amount, that is the total amount of token to drop;
  • Claimed which corresponds to the value of claimed tokens from the users. At the beginning it is 0 and is increased at each claim;
  • Owner which is to the address of the wallet which is creating the merkledrop.
type Merkledrop struct {
Id uint64
MerkleRoot string
StartHeight int64
EndHeight int64
Denom string
Amount sdk.Int
Claimed sdk.Int
Owner string
}

Indexes

To perform the check operations, a list of index is also stored in the state for each merkledrop.
type Indexes struct {
MerkledropId uint64
Index []uint64
}

Params

In the state definition, we can find the Params. This section corresponds to a module-wide configuration structure that stores system parameters. In particular, it defines the overall merkledrop module functioning and contains the creationFee for the merkledrop. Such an implementation allows governance to decide the creation fee, in an arbitrary way - since proposals can modify it.
type Params struct {
CreationFee sdk.Coin
}

Messages

Messages (msgs) are objects that trigger state transitions. Messages are wrapped in transactions (txs) that clients submit to the network. The BitSong SDK wraps and unwraps merkledrop module messages from transactions.

MsgCreate

The MsgCreate message is used to create a new merkledrop. It takes as input Owner, MerkleRoot, StartHeight, EndHeight, and Coin. The value of the block height at which the drop become available (the starting block) must be greater or equal to the block height where the transaction is included. For this reason, if the users select 0 as StartHeight it will be automatically set to the current block height (the one where the transaction is included). Moreover, there exists an upper bound for this value, that corresponds to the value of the actual block height + 100000. This choice derives from a design pattern that avoid the generation of spam merkledrop. At the same time, the EndHeight value, which corresponds to the block height where the merkledrop can be considered expired and the withdrawal is executed if part of the tokens were not claimed. This value must be greater than the StartHeight and lower than a maximum value of StartHeight + 5000000. The Coin is made up of the denom of the token to distribute and the amount, which corresponds to the sum of all the tokens to drop. Once the module has verified that the owner address is valid and that the merkletree root is a hexadecimal character string, it deduct the creation fee from the owner wallet and send the coin (the amount of token to drop), from the owner address to the module. At this point, the LastMerkleDropId is increased and the merkledrop is created, by assigning zero to the claimed value (since at the creation time, no one claimed any token). They are added three indexes:
  • on the merkledrop_id;
  • on the owner;
  • on the end_height.
These indexes improve the query operations and some process described in the end_block operations. An event of type EventCreate is emitted at the end of the creation process.
type MsgCreate struct {
Owner string
MerkleRoot string
StartHeight int64
EndHeight int64
Coin sdk.Coin
}

MsgClaim

The MsgClaim message is used to claim tokens from an active merkledrop. It takes as input Sender, MerkledropId, Index, the Amount to claim, and a list of Proofs. In such a scenario, verified the validity of the sender address and the existence of the merkledrop by the ID, if the airdrop is currently active (i.e., its start block height is lower than the current block height and its end block height is greater than the current one), the module verifies if the sender already claimed his tokens (by querying at an index). In case he didn't, the module proceeds retriving the merkletree root for the merkledrop from the chain and verifies the proofs (as described in the verification process). After tese verifications, the module only checks if the coin the sender wants to claim are available, and send those tokens from the module to the sender wallet. At this point, the claim is stored through its index, the claimed tokens are added to the actually claimed amount and, if all the drops are claimed with this operation, the merkledrop is cleaned by the state. An event of type EventClaim is emitted at the end of the claim process.
type MsgClaim struct {
Sender string
MerkledropId uint64
Index uint64
Amount sdk.Int
Proofs []string
}

End-Block

Each abci end block call, the operations to update the pending merkledrops are specified to execute. More specifically, since each merkledrop is characterized by an EndHeight (i.e., the block height at which the airdrop expires), the module can verify at each block if there is any expired merkledrop at that particular time. To perform the operations, the module is able to retrive the the merkledrops ids by the EndHeight and to process those drops. In particular, for each retrived merkledrop they are executed the withdraw of the unclaimed tokens and then, the merkledrop is cleaned by the state.

Withdraw

If at the the EndHeight block the merkledrop is still in the store, it means that not all the tokens were claimed. For this reason, the module automatically performs a withdraw of the unclaimed tokens to the owner wallet. In particular, the module verifies if the total amount is lower than the claimed amount, calculates the balance as the unclaimed tokens (i.e., the total amount - the claimed one). This amount is sent to the owner wallet and a corresponding event of type EventWithdraw is emitted.

Delete completed merkledrop

Once the merkledrop ended and its unclaimed tokens have been withdrawn, it is possible to clean indexes and store from the drop. More specifically, it is removed by the list of merkledrop per owner, all the indexes linked to its id are deleted together with the merkledrop object in the store.

Events

The merkledrop module emits the following events:

EventCreate

Type
Attribute Key
Attribute Value
message
action
/bitsong.merkledrop.v1beta1.MsgCreate
bitsong.merkledrop.v1beta1.EventCreate
owner
{owner}
bitsong.merkledrop.v1beta1.EventCreate
merkledrop_id
{merkledrop_id}

EventClaim

Type
Attribute Key
Attribute Value
message
action
/bitsong.merkledrop.v1beta1.MsgClaim
bitsong.merkledrop.v1beta1.EventClaim
merkledrop_id
{merkledrop_id}
bitsong.merkledrop.v1beta1.EventClaim
index
{index}
bitsong.merkledrop.v1beta1.EventClaim
coin
{coin}

EventWithdraw

Type
Attribute Key
Attribute Value
bitsong.merkledrop.v1beta1.EventWithdraw
merkledrop_id
{merkledrop_id}
bitsong.merkledrop.v1beta1.EventWithdraw
coin
{coin}

Parameters

Merkledrop module parameters.
Key
Type
Value
CreationFee
sdk.NewInt64Coin
{"denom": "ubtsg", "amount": "100000000"}

Client

Transactions

The transactions commands allow users to create and claim for merkledrops.
bitsongd tx merkledrop --help

create

bitsongd tx merkledrop create [account-file] [output-file] \
--denom=ubtsg \
--start-height=1 \
--end-height=10 \
--from=<key-name> -b block --chain-id <chain-id>

claim

bitsongd tx merkledrop claim [merkledrop-id] \
--proofs=[proofs-list] \
--amount=[amount-to-claim] \
--index=[level-index]
--from=<key-name> -b block --chain-id <chain-id>

Query

The query commands allow users to query the merkledrop module.
bitsongd q merkledrop --help

detail by id

bitsongd q merkledrop detail [id]

if index and id have been claimed

bitsongd q merkledrop index-claimed [id] [index]

params

bitsongd q merkledrop params