---
title: "Scalable Reward Distribution with Changing Stake Sizes"
date: 2019-02-24
canonical: https://solmaz.io/2019/02/24/scalable-reward-changing/
license: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/)
---

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](https://etherscan.io/address/0xb3775fb83f7d12a36e0475abdd1fca35c091efbe).

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

```python
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:

```python
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.

```python
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](http://batog.info/papers/scalable-reward-distribution.pdf), 2018.