This post is an addendum to the excellent paper Scalable Reward Distribution on the Ethereum Blockchain by Batog et al.¹ 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 $\text{reward}_t$ is distributed to a participant $j$ with an associated $\text{stake}_j$ as

\[\text{reward}_{j,t} = \text{stake}_{j} \frac{\text{reward}_t}{T_t}\]

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$:

\[\text{reward}_{j,t} = \text{stake}_{j, t} \frac{\text{reward}_t}{T_t}\]

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

\[\text{total_reward}_j = \sum_{t} \text{reward}_{j,t} = \sum_{t} \text{stake}_{j, t} \frac{\text{reward}_t}{T_t}\]

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:

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

\[\boxed{ \sum_{i=0}^{n}a_i b_i = a_n \sum_{j=0}^{n} b_j - \sum_{i=1}^{n} \left( (a_i-a_{i-1}) \sum_{j=0}^{i-1} b_j \right) }\]

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. $\square$

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

\[\text{total_reward}_j = \text{stake}_{j, n} \sum_{t=0}^{n} \frac{\text{reward}_t}{T_t} - \sum_{t=1}^{n} \left( (\text{stake}_{j,t}-\text{stake}_{j,t-1}) \sum_{t=0}^{t-1} \frac{\text{reward}_t}{T_t} \right)\]

We make the following definition:

\[\text{reward_per_token}_t = \sum_{k=0}^{t} \frac{\text{reward}_k}{T_k}\]

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

\[\Delta \text{stake}_{j,t} = \text{stake}_{j,t}-\text{stake}_{j,t-1}.\]

Then, we can write

\[\text{total_reward}_j = \text{stake}_{j, n}\times \text{reward_per_token}_n - \sum_{t=1}^{n} \left( \Delta \text{stake}_{j,t} \times \text{reward_per_token}_{t-1} \right)\]

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

\[\text{reward_tally}_{j,n} := \sum_{t=1}^{n} \left( \Delta \text{stake}_{j,t} \times \text{reward_per_token}_{t-1} \right)\]

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

\[\text{total_reward}_j = \text{stake}_{j, n} \times\text{reward_per_token}_n - \text{reward_tally}_{j,n}\]

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 $\text{reward_tally}_{j,n}$ is represented by a mapping reward_tally[] which is updated with each change in stake size

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

we can update reward_tally[] upon a complete withdrawal of $j$’s total accumulated rewards:

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 methods are 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.

class PullBasedDistribution:
    "Constant Time Reward Distribution with Changing Stake Sizes"

    def __init__(self):
        self.total_stake = 0
        self.reward_per_token = 0
        self.stake = {}
        self.reward_tally = {}

    def deposit_stake(self, address, amount):
        "Increase the stake of `address` by `amount`"
        if address not in self.stake:
            self.stake[address] = 0
            self.reward_tally[address] = 0

        self.stake[address] = self.stake[address] + amount
        self.reward_tally[address] = self.reward_tally[address] + self.reward_per_token * amount
        self.total_stake = self.total_stake + amount

    def distribute(self, reward):
        "Distribute `reward` proportionally to active stakes"
        if self.total_stake == 0:
            raise Exception("Cannot distribute to staking pool with 0 stake")

        self.reward_per_token = self.reward_per_token + reward / self.total_stake

    def compute_reward(self, address):
        "Compute reward of `address`"
        return self.stake[address] * self.reward_per_token - self.reward_tally[address]

    def withdraw_stake(self, address, amount):
        "Decrease the stake of `address` by `amount`"
        if address not in self.stake:
            raise Exception("Stake not found for given address")

        if amount > self.stake[address]:
            raise Exception("Requested amount greater than staked amount")

        self.stake[address] = self.stake[address] - amount
        self.reward_tally[address] = self.reward_tally[address] - self.reward_per_token * amount
        self.total_stake = self.total_stake - amount
        return amount

    def withdraw_reward(self, address):
        "Withdraw rewards of `address`"
        reward = self.compute_reward(address)
        self.reward_tally[address] = self.stake[address] * self.reward_per_token
        return reward

# A small example
addr1 = 0x1
addr2 = 0x2

contract = 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 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. ↩