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 pull-based approach to distributing rewards proportionally in a staking pool. In other words, instead of pushing rewards to each stakeholder in a for-loop 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}^{i-1}b_j$ on the LHS, distribute the multiplication, modify the index $i \leftarrow i-1$ 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 $t-1$ 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 $t-1$ 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.

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