An O(1) Dynamic Reward Rate Distribution Algorithm for Smart Contracts

This paper presents an algorithm for efficient decentralized distribution of rewards among pool participants with a variable reward rate based on the amount of reward tokens to be distributed, which achieves O(1) time complexity. The proposed algorithm is particularly useful for yield farming projects on Ethereum blockchain, where gas constraints make it impractical to distribute rewards at every block. The paper demonstrates the efficiency and scalability of the proposed algorithm and presents some potential use cases for its application in smart contracts.

1. Introduction

Decentralized finance (DeFi) has emerged as one of the most exciting and rapidly growing sectors in the blockchain ecosystem. DeFi protocols enable users to perform financial transactions such as lending, borrowing, trading, and staking in a decentralized and trustless manner. One of the core features of DeFi protocols is the ability to distribute rewards to participants in exchange for their contribution to the network, such as providing liquidity, staking tokens [1], or performing governance functions [2].

Reward distribution is a critical component of many DeFi protocols, and its efficient and fair implementation is essential for the sustainability and growth of these projects. However, designing an optimal reward distribution algorithm is not a trivial task, and several challenges need to be addressed, including gas constraints, varying reward rates, and the need to scale to a large number of participants.

Several algorithms have been proposed to address these challenges, but most of them suffer from significant limitations. For example, Scalable Reward Distribution on the Ethereum Blockchain (Batog, Boca & Johnson, 2018) [3] is only suitable for very fine grained distribution (e.g. every block), which is not feasible for most projects due to gas constraints. Synthetix’s StakingRewards [4] contract and Sushi’s MasterChief [5] both assume constant time interval or reward rate, which does not work for yield farming projects with variable token rewards.

In this paper, we propose a novel algorithm for decentralized reward distribution in smart contracts that overcomes these limitations while retaining O(1) time complexity. Our algorithm can handle variable reward rates based on the amount of reward tokens needed to be distributed and is particularly useful for yield farming projects that have long time intervals between token distributions. We also discuss the implementation of our algorithm as an Ethereum smart contract and also compare our approach with other existing algorithms and highlight it’s advantages.

2. Related Work

Reward distribution is a well-studied problem in the context of blockchain-based systems, and several algorithms have been proposed to address it. In this section, we provide an overview of the related work on reward distribution in smart contracts.

2.1. Constant Reward Rate Algorithms

Several DeFi protocols use constant reward rate algorithms for reward distribution. For example, Sushiswap’s MasterChief [5] contract assumes a constant reward rate, which means that the rate of token rewards is fixed and does not change over time. Although constant reward rate algorithms are simple and easy to implement, they do not work well for yield farming projects with variable token rewards.

2.2. Time-Based Algorithms

Another class of reward distribution algorithms is based on time intervals. These algorithms distribute rewards at fixed time intervals, such as daily or weekly. However, time-based algorithms suffer from several limitations, such as the inability to handle variable time intervals, the need for manual intervention to adjust the distribution frequency, and the potential for reward accumulation and loss due to missed intervals. As an example, Synthetix’s StakingRewards [4] algorithm belongs to this category.

2.3. Off-Chain Algorithms

Off-chain distribution algorithms, such as those using Merkle trees [6][7], have become popular for efficient reward distribution. They store reward distribution information off-chain and use cryptographic proofs for verification, reducing gas costs and increasing security. However, they may require additional infrastructure and coordination between off-chain and on-chain components. Also if the off-chain storage and calculation of such an algorithm is controlled by a single entity e.g. centralized server, then it would be a centralized solution.

2.4. Block-Based Algorithms

Some reward distribution algorithms are based on assumption that the rewards are distributed every time a new block is added to the blockchain. While block-based algorithms can provide scalable and optimal reward distribution, they suffer from gas constraints and are not a practical solution for most DeFi projects. An example of such an algorithm is Scalable Reward Distribution on the Ethereum Blockchain (Batog, Boca & Johnson, 2018) [3]. This algorithm does not track the time when participants enter the pool and therefore does not work well with long distribution intervals. Participants could join the pool just before reward distribution and receive rewards they did not earn.

2.5. Our Solution

While several algorithms have been developed to handle reward distribution in smart contracts, most of them suffer from significant limitations. Our proposed algorithm overcomes these limitations and achieves O(1) time complexity, making it an efficient and scalable solution for reward distribution in DeFi protocols.

3. Reward Distribution Algorithm

We will begin by outlining the key components of the algorithm:

• Deposit(amount) : This function enables participants to deposit their tokens into the pool, updating their stake and the total amount of tokens deposited.
• Withdraw(amount) : This function allows participants to withdraw tokens from their stake, updating their stake and the total amount of tokens remaining in the distribution pool.
• CollectReward(amount) : This function allows participants to collect their reward from the pool, which is calculated based on their stake, the duration their tokens have been in the pool, and the distributions they participated in.
• Distribute(reward) : This function distributes rewards among participants. The contract utilizes a pullbased system to maintain constant time complexity. Participants must subsequently call CollectReward to receive their rewards.

To prevent the issue described in the section 2.4, the algorithm must also track the times at which participants made deposits. Several challenges make calculating rewards a participant should receive a non-trivial task:

1. A participant can make an unlimited number of deposits and withdrawals at different blocks and with varying amounts.
2. An infinite number of distributions with varying reward amounts can occur at different time intervals.

3.1. Participant’s Reward After a Single Distribution

To determine a participant’s reward after a single distribution, we must consider the chronological order of all deposit, withdrawal, and distribution events. Let T₁, T₂, …, Tₙ be the sum of all active stakes at each block t₁, t₂, …, tₙ n which a deposit or withdrawal occurred, where n is the block at which reward is distributed. A participant i would have stakeᵢ,₁, stakeᵢ,₂, …, stakeᵢ,ₙ at each such block depending on their deposits and withdrawals.

Let’s assign names to the following expressions:

Participant i will receive a reward of:

We can accumulate totalDepositAge on each deposit and withdrawal, making it possible to compute (2) in constant time on i’s collection of rewards. Since the stake of i is constant over the interval in which no deposits or withdrawals were made by them, we can rewrite (1) as:

Here, Lᵢ represents the number of deposits and withdrawals made by participant i and Aᵢ,ₚ represents the block i made action p. We can also accumulate depositAgeᵢ for participants on their deposits and withdrawals allowing us to compute (4) in constant time. Therefore, we can compute rᵢ in constant time as well.

3.2. Participant’s Reward After Multiple Distributions

Let us consider the case in which participant i deposits their stake before distribution d and holds it for multiple distributions d, d + 1, …, D. Their reward R would be:

After the first distribution d, participant i will receive a reward of (3). If m > d their stake would remain constant:

We can store the last distribution D on each new distribution and store the next distribution d for each participant i on each of their actions making it possible to calculate rewardAgePerDepositAgeD−rewardAgePerDepositAged in constant time.

We can also calculate rd,ᵢ in constant time by storing rewardd/totalDepositAged for each distribution d and multiplying it by depositAgeᵢ on i’s collection of rewards. Therefore it is also possible to compute Rᵢ in constant time.

3.3. Other Cases

Every other case can be modeled by adding multiple (11) expressions together and substituting d for the next distribution after i’s last action. The algorithm remains constant time because we can accumulate i’s rewards on each of their actions.

4. Notes

1. The Withdraw and CollectReward functions can be merged into a single function for simplicity and efficiency.

2. The current algorithm does not support compounding rewards, but there is potential for future development.

3. Participants who staked their tokens during a given distribution interval will earn rewards, even if they did not have an active stake at the time of the reward distribution. For example, if they withdrew their tokens before distribution, they will still receive their rewards after the distribution. This is an expected behavior because the described algorithm aims to provide fair reward distribution to all participants.

4. The algorithm is designed to be loop-free, ensuring efficient and scalable reward distribution.

5. Author Information

This algorithm was developed for the Uno.Farm [8] yield farming protocol. Uno.Farm [8] is an example of the successful implementation of the algorithm described in this paper and utilizes it to distribute rewards from third-party staking pools among participants.

6. Conclusion

This paper proposed a novel algorithm for efficient and decentralized reward distribution in smart contracts. The proposed algorithm overcomes several limitations of existing algorithms by handling variable reward rates based on the amount of reward tokens needed to be distributed while retaining O(1) time complexity. In the context of DeFi protocols, efficient and fair reward distribution is crucial for their sustainability and growth. The proposed algorithm provides a promising solution to address the challenges of gas constraints, varying reward rates, and scaling to a large number of participants. It can contribute to the development of a more robust and efficient DeFi ecosystem.

References

[1] Vogelsteller, F. & Buterin, V. (2015). ERC: Token standard 20. Retrieved from https://github.com/ethereum/EIPs/blob/master/EIPS/eip-20.md.

[2] Buterin, V. (2014). A next-generation smart contract and decentralized application platform. Ethereum white paper. Retrieved from https://ethereum.org/en/whitepaper/.

[3] Batog, B., Boca, L., & Johnson, N. (2018) Scalable reward distribution on the Ethereum blockchain. DappCon, Berlin, Germany, Aug. 2018.

[4] Synthetix. (2021). StakingRewards Contract. Retrieved from https://github.com/Synthetixio/synthetix/blob/develop/contracts/StakingRewards.sol.

[5] SushiSwap. (2021). MasterChef Contract. Retrieved from https://github.com/sushiswap/sushiswap/blob/master/protocols/masterchef/contracts/MasterChefV2.sol.

[6] Merkle, R. C. (1988). A Digital Signature Based on a Conventional Encryption Function. Advances in Cryptology — CRYPTO ’87. Lecture Notes in Computer Science. Vol. 293. pp. 369–378.

[7] Uniswap. (2020). MerkleDistributor contract. Retrieved from https://github.com/Uniswap/merkle-distributor/blob/master/contracts/MerkleDistributor.sol.

[8] Uno.Farm. Yield farming aggregator protocol. https://uno.farm/.

Written by

Ivan Menshchikov (Juglipaff)
Roman Vinogradov (sapph1re)

Special thanks to Anton Dementyev