Using Merkle Proof for OffChain Referral Networks
A polished version of this article was published in Medium by 2key Network
2key Network
2key Network is a blockchainbased referral network intended to reward referrers through smart contracts. Referrals progress through the network thanks to people sharing them through their regular browsers. Therefore, 2key generates offchain cryptographically signed links, which propagate among users without reaching the blockchain. Upon conversion, a user submits the signed link to the smart contract. The smart contract rewards the chain of referrers as represented in the signed link. The smart contract is deployed per referral campaign by the campaign initiator, depositing a referral reward, as an amount of cryptocurrency, from which the smart contract will later pay the referrers.
The Influence Graph
A campaign conducted over the 2key network starts with a source seeding, and proceed through referrals. The graph of referrals from the source seeding is called the influence graph. Each node in the graph is called an influencer. The node which makes an actual conversion, such as purchasing a product, is called a converter. A referrer leading to conversion is to be rewarded from the campaign budget. Not only is the referral leading to the conversion is to be rewarded but also referrals that had some impact on anyone leading to the conversion.
Building the Referral Graph OffChain
The 2key web application for campaign management operates in a fully decentralized model. It listens for past events and displays the campaign progress based on these events.
The generic code for this is:
await this.contract.getPastEvents("Transfer", {
fromBlock: this.blockNumber,
toBlock: blockNumber,
}).then(function(evtData){
})
The Transfer
event is the transfer of a referral token called an ARC.
Merkle Proofs
Merkle proofs have been suggested as a way to snapshot ERC20 contracts. As detailed in ERC20 Snapshotter using Merkle Proofs, a snapshot server periodically filters past events as in the code above and builds a tree of the balances of tokens. Each leaf node in the tree is an account with its balance in the contract. A Merkle tree is built by having each internal node in the tree be a hash of its direct descendants in the tree. The whole snapshotting operation is decentralized as anyone can run such code.
The contract owner deploys a backup contact into which one writes the root of the Merkle tree together with the block number at which the snapshot was taken in order to build the tree.
Now, any user can claim its tokens from the backup contract, given an address and a balance, and a Merkle proof. The Merkle proof is a path from the root of the tree to the leaf node representing the balance of the address. The users can run the same snapshot algorithm and compute the Merkle proof for their balance. The backup contract, given the Merkle proof, can verify the user has indeed the claimed balance.
OpenZeppelin Merkle Proof contract is a recent implementation of this idea.
One caveat is that we need to preagree and publish the sorting order of the leaf nodes used to construct the Merkle tree.
Merkle Proofs for Referrals
Consider the referral path from the source seeding to a converter, it establishes a natural temporal order of referrals. Let us take the sequence of addresses along the path, and build a Merkle tree whose sequence of leaves from left to right is this sequence of addresses. The root of the Merkle tree is a hash that uniquely identifies the referral path.
Each influencer on the path can compute a Merkle proof for its presence on the path if the whole path is known.
So if a converter, upon conversion writes the root of the Merkle tree to the campaign smart contract, each influencer presenting a Merkle proof to the smart contract, can be rewarded in accordance.
The missing piece is how to make this path to the converter generally available. As a Merkle tree is based on the whole path the converter, while each referrer on the way is aware only of the path to it. Well, if we write the path to IPFS, and the converter will store in the contract the IPFS hash together with the Merkle Root, we have all the information needed.
Let the campaign contract emit a Convert
event on each conversion, and include the IPFS hash in the event parameters. The influencer can listen to Convert
event, retrieve the referral path that leads to the conversion from IPFS using the IPFS hash from the event. If upon examining the referral path, the influencer finds itself on the path, it computes the Merkle proof for itself. That is, the Merkle proof for the leaf node representing the influencer address.
The influence will make a claim
call to the campaign contract, and pass the Merkle proof as a parameter to the call.
The contract, inheriting from the OpenZeppelin Merkle Proof contact referenced above, would verify the proof. If verified the influencer will be paid a reward.
A New Trust Balance
This new approach based on Merkle proofs places the trust on the converter. The converter is supposed to truthfully write the path to IPFS, and the Merkle Root to the contract. In contrast, the signed link approach, relying on cryptographic signatures is completely trustless.
Can this be expected to be a reasonable case? We believe it depends on the relative value of the reward and the payout for a conversion. If the payout is much larger than the rewards, as is often the case, a converter will be willing to bear the risk.
Can We Tilt the Trust Balance?
What if we incentivize the influencers to write things to the contract while a referral process is going on? Such that an influencer before proceeding with the referral does like a converter, writes a path to an IPFS file, and sends the Merkle Root of the path to the contract together with the IPFS hash.
Assume even one influencer, at the middle of the road between the source seeding and the converter, writes the information on the referral path up to it to the contract.
In such a case, we can tilt the balance of trust such that less trust is placed on the converter. Consider an influencer on a referral path from the source seeding to the influencer that sent information to the contract. Such an influencer can be verified by two Merkle proofs, written to the contract by:

An influencer following this influencer it in the referral path

The converter
The Two Factor Verification Incentive Model
An influencer providing a Two Factor Verification can be rewarded an amount which is larger than that rewarded to the influencer verified by the second proof above only.
This incentive will incentivize the influencers to spend the gas to write Merkle roots and IPFS hashes to the contract.
Conclusion
We believe Merkle proofs provide a new optimistic trustless approach to referrals, where a twofactor verification is good enough for most situations.
One of the goals of 2key Network is to accumulate across campaigns a reputation model of influencers to be used in making referral decisions and computing referral rewards. Merkle proofs with appropriate incentives statistically increase the probability of more complete accumulation of credible information. As each two factor verification, provides an additional credible data point to be added to the graph.