## Summary

A new way to distribute epoch rewards across multiple blocks is proposed to
address the current performance problems associated with the reward
distribution in a single block at the start of the epoch.

## Motivation

The distribution of epoch rewards at the start block of an epoch becomes a
significant bottleneck due to the rising number of stake accounts and voting
nodes on the network.

To address this bottleneck, we propose a new approach for distributing the
epoch rewards over multiple blocks.


## Detailed Design

The major bottleneck for epoch reward distribution is to distribute rewards to
stake accounts. At the time of writing, there are approximately 550K active
stake accounts and 1.5K vote accounts on Solana Mainnet Beta. Given the
relatively small number of vote accounts, it makes sense to keep vote rewards
distribution mechanism unchanged. They can still be distributed efficiently at
the first block of the epoch boundary. This reduces the impact of rewards for
vote account and also simplifies the overall changes, and let us focus on
solving the primary bottleneck - Stake Rewards. Only Stake rewards are going to
be distributed out over multiple blocks.

In the new stake rewards distribution approach, we will separate the
computation of rewards from the actual distribution of rewards at the epoch
boundary by dividing the process into two distinct phases:

   1. rewards calculation phase - during which the epoch rewards for all
      activate stake accounts are computed and distribution chunks are scheduled.

   1. rewards distribution phase - during which the calculated epoch rewards
      for the active stake accounts are distributed.

### Rewards Calculation

Reward calculation phase computes all the rewards that need to be distributed
for the active stake accounts, and partitions the reward into a number of
chunks. Each of the chunks will be distributed in a separate block in the
`reward distribution phase`.

To help track and verify the reward distribution in the next phase, two new
sysvar accounts are introduced: (a) `EpochRewardHistory` sysvar account and (b)
`RewardReserve` sysvar accounts. These sysvar accounts are updated at the
boundary blocks (i.e. first and last blocks) in the reward calculation phase.
More details of these two sysvar accounts are described in the following
sections.

The reward computation phase lasts *exactly* for `N` block heights since
the beginning of the epoch. When reaching block height `N` after the start
block of the `reward calculation phase`, the bank will mark it the end the
`reward calculation phase`.

On Solana Mainnet Beta, the 90% cut-off of the epoch reward computation time
for all the nodes is around 40 seconds for the ~550K active stake accounts.
This is approximately 1000 blocks at the cluster's average block rate (40ms
per block). Therefore, a conservative value of 1,000 is chosen for `N`.

At the end of the `reward calculation phase`, aka. `Epoch_start + N` block
height, the reward computation process is "barrier synchronized" with the bank
replay process. The bank replay process won't replaying any blocks after
`Epoch_start+N` unless the reward computation has completed. If the reward
calculation is slow and hasn't complete the computation at block-height
`Epoch_start + N`, the bank replay process will block and wait until the reward
computation is finished, before processing any blocks with height greater than
`N`.

After the full rewards result is calculated, the result is partitioned into
distribution chunks, which will be distributed during the `reward distribution`
phase.

To ensure that each block distributes a subset of the rewards in
a deterministic manner for the current epoch, while also randomizing the
distribution across different epochs, the partitioning of all rewards will be
done as follows. First, a new key is generated for each reward by hashing the
account's public key with the epoch number (i.e. sha256 hash from
solana_sdk::program::hashv). Then, the rewards are sorted by the new key and
divided into `M` bins. This process will ensure that the reward distribution is
deterministic for the current epoch, while also introducing a degree of
randomness between epochs.

To minimize the impact on block processing time during the reward distribution
phase, the number of additional accounts stored per tick will be limited to 64.
Given that each block is 64 ticks long, a total of 4,096 accounts can be
distributed per block. The total number of blocks needed to distributed rewards
is given by the following formula to avoid using floating point value
arithmetic:

```
M = ((4096 - 1)+num_stake_accounts)/4096
```

### `EpochRewardHistory` Sysvar Account

`EpochRewardHistory` sysvar account maintains a history of epoch rewards. The
internal format of `EpochRewardHistory` is an array of `RewardHistoryEntry`,
where each entry corresponds to the reward for one particular epoch. The
maximum depth of the history is chosen to be the same as the depth of stake
history for consistency, which is 512.

The layout of `EpochRewardHistory` sysvar is shown in the following pseudo code.

```
struct RewardHistoryEntry {
   total_reward_in_lamport: u64,          // total rewards for this epoch
   distributed_reward_in_lamport: u64,    // already distributed reward amount
   root_hash: Option<Hash>,               // hash computed from all EpochRewardReserves
}

type EpochReward = (Epoch, RewardHistoryEntry);

struct RewardHistory {
   rewards: [EpochReward; 512],
}
```

The `EpochRewardHistory` is updated at the start of the first block of the
epoch (before any transactions are processed), as both the total epoch rewards
and vote account rewards become available at this time. Once the vote account
rewards have been distributed, a `RewardHistoryEntry` will be added to the
`EpochRewardHistory` array with the total amount of rewards and the amount
distributed, which is equal to the sum of the vote account rewards. If the
length of the history array exceeds the maximum depth (512), the oldest entries
will be removed from the array (i.e., "popped").

The `root_hash` is the hash of all the `EpochRewardReserve` accounts hashes.
Initially, at the start of the epoch's first block, the `root_hash` is set to
None. Once all the `EpochRewardReserve` accounts are filled and the reward
computation phase is complete, the `root_hash` is calculated by hashing all the
`EpochRewardReserve` hashes.

```
root_hash = Hash(EpochRewardReserve[..].reserve_hash)



                     +-------------+
                     |             |
                     |  root_hash  |
                     |             |
                     +------+------+
                            |
    +--------------+--------+-----------+
    |              |                    |
+---+----+   +-----+--+             +---+-----+
|reserve |   | reserve|   ......    | reserve |
| hash   |   |  hash  |             |  hash   |
+--------+   +--------+             +---------+

```

### `EpochRewardReserve` Sysvar Account

`EpochRewardReserve` sysvar account tracks the reward to be distributed for one
particular block in the `reward distribution phase`.

The address for a particular `EpochRewardReserve` account is derived from the
base Sysvar RewardReserve address and u64 block height for the corresponding reward
distribution block during the reward distribution phase, i.e.
`address = hash("SysvarRewardReserve11111111111111111111111111111", block_height)`.


```
crate::declare_sysvar_id!("SysvarRewardReserve11111111111111111111111111111", EpochRewardReserve);

struct EpochRewardReserve {
   reserve_hash: Hash,
}
```

The account balance of `RewardsReserve` is equal to the total amount (in
lamports) of all rewards to be distributed in a block. The `reserve_hash` is
computed from the rewards in the block as follows.

```
reserve_hash = hash([(stake_account_key, reward_amount)])
```

At the end of reward computation phase, M `EpochRewardsReserve` sysvar
accounts are updated, where `M` corresponds to how many blocks will be in
the reward distribution phase, which is described in the next section.


### Reward Distribution

Reward distribution phase happens right after reward computation phase and
lasts for `M` blocks. Each of the `M` blocks is responsible for distributing
the reward from one partition of the rewards stored in the `EpochRewardReserve`
account, the one at the address
`hash("SysvarRewardReserve11111111111111111111111111111", block_height)`.

During the reward distribution phase, for the block at `block_height`, the
rewards will be distributed from the `EpochRewardReserve` sysvar account with
the address of "hash(`SysvarRewardReserve11111111111111111111111111111111`,
block_height). Once all rewards have been distributed, the balance of the
EpochRewardReserve account should be reduced to 0.

Before each reward distribution, the `EpochRewardReserve` account's balance
is checked to make sure there is enough balance to distribute the reward. After a
reward is distributed, the balance in `EpochRewardReserve` account is decreased
by the amount of the reward that was distributed. The hash of reward account
address and reward amount is accumulated when rewards are distributed. After all
the rewards are distributed from the reserve account for the block, the hash
computed from all the rewards distribution is verified against the hash stored
in the `EpochRewardReserve` account to make sure they match.

During the reward distribution phase, there is a "root accumulator hash" that
starts empty and is gradually filled by adding each hash of a
`EpochRewardReserve`. The distribution process continues until the "root
accumulator hash" matches the "root hash" stored in `EpochRewardHistory`. At this
point, the reward distribution for the current epoch is complete and we can
safely assume that there will be no further distributions for the remainder of
the epoch.

### Restrict Stake Account Access

To avoid the complexity and potential rewards in unexpected stake accounts,
stake programs are disabled during the epoch reward period.

Any transaction that invokes staking program during this period will fail with
a new unique error code - `StakeProgramUnavailable`.

That means all updates to stake accounts have to wait until the rewards
distribution finishes.


### Snapshot and Cluster Restart

Due to the fact that rewards are paying over multiple blocks, snapshots, which
are taken during reward distribution phase, need to store the reward
calculation result.

The bank snapshot data file inside snapshot archives will have a new optional
field, `Option<RewardCalculationResult>`, at the end. All snapshots taken during
the reward period will have this field populated.

When a node restart from those snapshots, it will pick up the epoch reward
calculation result and resume the left-over reward distribution.

## Impact

There are the two main impacts of the changes to stake accounts during the
epoch rewarding phase.

The first impact is that stake accounts will see their rewards being credited a
few blocks later in the epoch than before.

The second impact is that users will not be able to update their stakes during
the epoch reward phases, and will have to wait until the end of the epoch
reward period to make any changes.

Nonetheless, the overall amount of time that the user must wait before
receiving and updating their stake rewards should be roughly equivalent to what
they are now experiencing on the current mainnet beta, since the prolonged
first block time at the epoch boundary effectively obstructs the user's access
to those stake accounts during that time.

## Security Considerations

Epoch rewards in a blockchain system are an important component that helps to
incentivize network participants to secure the network and maintain its
operations.

Although the proposed new approach does not alter the economics of the reward
system, it does impact and modify various components of the validators. As a
result, unforeseen issues/bugs could arise, leading to differences in rewards.
Consequently, any modifications to the epoch reward code must be carefully
evaluated and thoroughly tested before rollout.

The addition of sysvar accounts can provide some additional safeguards to
prevent large capital changes, but it is important to note that they do not
eliminate all risks associated with changing epoch rewards.

## Backwards Compatibility

This is a breaking change.  The new epoch calculation and distribution approach
will not be compatible with the old approach.

Partitioned Epoch Reward Distribution