Scalable Reward Distribution with Changing Stake Sizes
This post is an addendum to the excellent paper Scalable Reward Distribution on the Ethereum Blockchain by Batog et al.^{1} The outlined algorithm describes a pullbased approach to distributing rewards proportionally in a staking pool. In other words, instead of pushing rewards to each stakeholder in a forloop with $O(n)$ complexity, a mathematical trick enables keeping account of the rewards with $O(1)$ complexity and distributing only when the stakeholders decide to pull them. This allows the distribution of things like rewards, dividends, Universal Basic Income, etc. with minimal resources and huge scalability.
The paper by Bogdan et al. assumes a model where stake size doesn’t change once it 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 both the deposit and the accumulated rewards. This would rarely be the case in real applications, as participants would want to increase or decrease their stakes between reward distributions. To make this possible, we need to make modifications to the original formulation and algorithm. Note that the algorithm given below is already implemented in PoWH3D.
In the paper, the a $reward_t$ is distributed to a participant $j$ with an associated $stake_j$ as
where subscript $t$ denotes the values of quantities at distribution of reward $t$ and $T$ is the sum of all active stake deposits.
Since we relax the assumption of constant stake, we rewrite it for participant $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, because it’s not constant. Instead, we introduce the following 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}^{i1}b_j$ on the LHS, distribute the multiplication, modify the index $i \leftarrow i1$ on the first term, separate the last element of the sum from the first term and combine the remaining sums since they have the same bounds.
We assume $n+1$ rewards represented by the indices $t=0,\dots,n$, and apply the identity to total reward to obtain
Recalling the authors’ definition of the sum
and defining the change in stake between rewards $t1$ and $t$
we can write
This result is similar to the one obtained by the authors in Equation 5. However, instead of keeping track of $S$ at times of deposit for each participant as is the case with $S_0$ from the paper, we keep track of
In this case, positive $\Delta stake$ corresponds to a deposit and negative corresponds to a withdrawal. $\Delta stake_{j,t}$ is zero if the stake of participant $j$ remains constant between $t1$ and $t$. We have
The modified algorithm requires the same amount of memory, but has the advantage of participants being able to increase or decrease their stakes without withdrawing everything and depositing again.
Furthermore, a practical implementation should take into account that a
participant can withdraw rewards at any time.
Assuming $P_{j,n}$ is represented by a mapping P[]
which is
updated with each change in stake size
P[address] = P[address] + change*S
we can update P[]
upon a complete withdrawal of $j$’s total accumulated
rewards:
P[address] = stake[address]*S
which sets $j$’s rewards to zero.
The pseudocode for the modified algorithm is given below. The following methods are exposed:
DepositStake
to deposit or increase a participant stake.Distribute
to fan out reward to all participants.WithdrawStake
to withdraw a participant’s stake partly or completely.WithdrawReward
to withdraw all of a participant’s accumulated rewards.
Algorithm 1: Constant Time Reward Distribution with Changing Stake Sizes
function Initialization();
begin
T = 0;
S = 0;
stake = {};
P = {};
end
function DepositStake(address, amount);
Input: increase the stake of _address_ by _amount_
begin
if address not in stake then
stake[address] = 0;
P[address] = 0;
end
stake[address] = stake[address] + amount;
P[address] = P[address] + S*amount;
T = T + amount;
end
function Distribute(r);
Input: Reward _r_ to be distributed proportionally to active stakes
begin
if T != 0 then
S = S + r/T;
else
revert();
end
end
function WithdrawStake(address, amount)
Input: decrease the stake of _address_ by _amount_
Output: returns the withdrawn _amount_
begin
if address not in stake then
revert();
end
if amount > stake[address] then
revert();
end
stake[address] = stake[address]  amount;
P[address] = P[address]  S*amount;
T = T  amount;
return amount
end
function WithdrawReward(address)
Input: withdraw the rewards of _address_
Output: _amount_ withdrawn
begin
if address not in stake then
revert();
end
reward = stake[address]*S  P[address]
P[address] = stake[address]*S
return reward
end
Conclusion
With a minor modification, we improved the user experience of the Constant Time Reward Distribution Algorithm first outlined in Batog et al., without changing the memory requirements.

Batog B., Boca L., Johnson N., Scalable Reward Distribution on the Ethereum Blockchain, 2018. ↩