This post is an addendum to the excellent paperScalable Reward Distribution on the Ethereum Blockchain by Batog et al.1The outlined algorithm describes a pull-based approach to distributing rewardsproportionally in a staking pool. In other words, instead of pushingrewards to each stakeholder in a for-loop with $O(n)$ complexity, amathematical trick enables keeping account of the rewards with $O(1)$complexity and distributing only when the stakeholders decide to pull them. Thisallows the distribution of things like rewards, dividends, Universal BasicIncome, etc. with minimal resources and huge scalability.

The paper by Bogdan et al. assumes a model where stake size doesn’t change onceit is deposited, presumably to explain the concept in the simplest way possible.After the deposit, a stakeholder can wait to collect rewards and then withdraw boththe deposit and the accumulated rewards.This would rarely be the case in real applications, as participants would wantto increase or decrease their stakes between reward distributions. To make thispossible, we need to make modifications to the original formulation andalgorithm. Note that the algorithm given below is already implemented inPoWH3D.

In the paper, the a $\text{reward}_t$ is distributed to a participant $j$ with anassociated $\text{stake}_j$ as

where subscript $t$ denotes the values of quantities at distribution of reward$t$ and $T$ isthe sum of all active stake deposits.

Since we relax the assumption of constant stake, we rewrite it forparticipant $j$’s stake at reward $t$:

Then the total reward participant $j$ receives is calculated as

Note that we can’t take stake out of the sum as the authors did, becauseit’s not constant.Instead, we introduce the following identity:

Identity: For two sequences $(a_0, a_1, \dots,a_n)$ and $(b_0, b_1, \dots,b_n)$, we have

Proof: Substitute $b_i = \sum_{j=0}^{i}b_j - \sum_{j=0}^{i-1}b_j$ on theLHS. Distribute the multiplication. Modify the index $i \leftarrow i-1$ on thefirst term. Separate the last element of the sum from the first term andcombine the remaining sums since they have the same bounds. $\square$

We assume $n+1$ rewards represented by the indices $t=0,\dots,n$, andapply the identity to total reward to obtain

We make the following definition:

and define the change in stake between rewards $t-1$ and $t$:

Then, we can write

This result is similar to the one obtained by the authors in Equation 5. However,instead of keeping track of $\text{reward_per_token}$ at times of deposit for each participant, we keep track of

In this case, positive $\Delta \text{stake}$ corresponds to a deposit and negativecorresponds to a withdrawal. $\Delta \text{stake}_{j,t}$ is zero if the stake ofparticipant $j$ remains constant between $t-1$ and $t$. We have

The modified algorithm requires the same amount of memory, but has theadvantage of participants being able to increase or decrease their stakeswithout withdrawing everything and depositing again.

Furthermore, a practical implementation should take into account that aparticipant can withdraw rewards at any time.Assuming $\text{reward_tally}_{j,n}$ is represented by a mappingreward_tally[] which isupdated with each change in stake size

reward_tally[address]=reward_tally[address]+change*reward_per_token

we can updatereward_tally[] upon a complete withdrawal of $j$’s total accumulatedrewards:

reward_tally[address]=stake[address]*reward_per_token

which sets $j$’s rewards to zero.

A basic implementation of the modified algorithm in Python is given below. The following methodsare exposed:

• deposit_stake to deposit or increase a participant stake.
• distribute to fan out reward to all participants.
• withdraw_stake to withdraw a participant’s stake partly or completely.
• withdraw_reward to withdraw all of a participant’s accumulated rewards.

Caveat: Smart contracts use integer arithmetic, so the algorithm needs to be modified to be used in production. The example does not provide a production ready code, but a minimal working example to understand the algorithm.

classPullBasedDistribution:"Constant Time Reward Distribution with Changing Stake Sizes"def__init__(self):self.total_stake=0self.reward_per_token=0self.stake={}self.reward_tally={}defdeposit_stake(self,address,amount):"Increase the stake of `address` by `amount`"ifaddressnotinself.stake:self.stake[address]=0self.reward_tally[address]=0self.stake[address]=self.stake[address]+amountself.reward_tally[address]=self.reward_tally[address]+self.reward_per_token*amountself.total_stake=self.total_stake+amountdefdistribute(self,reward):"Distribute `reward` proportionally to active stakes"ifself.total_stake==0:raiseException("Cannot distribute to staking pool with 0 stake")self.reward_per_token=self.reward_per_token+reward/self.total_stakedefcompute_reward(self,address):"Compute reward of `address`"returnself.stake[address]*self.reward_per_token-self.reward_tally[address]defwithdraw_stake(self,address,amount):"Decrease the stake of `address` by `amount`"ifaddressnotinself.stake:raiseException("Stake not found for given address")ifamount>self.stake[address]:raiseException("Requested amount greater than staked amount")self.stake[address]=self.stake[address]-amountself.reward_tally[address]=self.reward_tally[address]-self.reward_per_token*amountself.total_stake=self.total_stake-amountreturnamountdefwithdraw_reward(self,address):"Withdraw rewards of `address`"reward=self.compute_reward(address)self.reward_tally[address]=self.stake[address]*self.reward_per_tokenreturnreward# A small exampleaddr1=0x1addr2=0x2contract=PullBasedDistribution()contract.deposit_stake(addr1,100)contract.distribute(10)contract.deposit_stake(addr2,50)contract.distribute(10)print(contract.withdraw_reward(addr1))print(contract.withdraw_reward(addr2))

Conclusion

With a minor modification, we improved the user experience of the Constant TimeReward Distribution Algorithmfirst outlined in Batog et al., without changing the memory requirements.