Background
The gas cost of earnings calculations in the BondingManager contract currently grows linearly with the number of rounds since a delegator’s lastClaimRound
which is the last round that the delegator claimed earnings through (either manually via the claimEarnings()
tx or automatically via a bonding, unbonding or fees withdrawal tx).
This post explores a more efficient calculation approach to avoid linear gas cost growth with the number of rounds since a delegator’s lastClaimRound
.
Current Calculation Approach
Consider an individual delegator delegated to a specific orchestrator starting at round m. The delegator starts earning reward and fee shares in round m + 1.
Let s_n be the delegator’s stake in round n which includes all reward shares earned since the delegator started staking.
Let S_n be the orchestrator’s total stake in round n which includes all rewards earned since the orchestrator’s activation round.
Let R_n be the delegators’ share of rewards minted by the orchestrator in round n.
Let f_n be the delegator’s fees in round n which includes all fees earned since the delegator started staking.
Let F_n be the delegators’ share of fees generated by the orchestrator in round n.
A delegator’s stake in round n, assuming that the delegator did not bond/unbond since round m, can be represented by the following recurrence relation:
s_n = s_{n - 1} + R_n \frac{s_{n - 1}}{S_n}
s_m = s_m
This relation expresses that a delegator’s stake in round n is equal to the delegator’s stake in round n - 1 plus the delegator’s share of the rewards minted by the orchestrator in round n which is calculated pro rata based on the delegator’s contribution to the orchestrator’s total stake in round n.
A delegator’s fees in round n, assuming that the delegator did not bond/unbond since round m, can be represented by the following recurrence relation:
f_n = f_{n - 1} + F_n \frac{s_{n - 1}}{S_n}
f_m = f_m
This relation expresses that a delegator’s fees in round n is equal to the delegator’s fees in round n - 1 plus the delegator’s share of the fees earned by the orchestrator in round n which is calculated pro rata based on the delegator’s contribution to the orchestrator’s total stake in round n.
Since the delegator delegated to the orchestrator in round m, the stake and fees relations can be expanded as follows:
s_n = s_m + R_{m + 1} \frac{s_m}{S_{m + 1}} + R_{m + 2} \frac{s_{m + 1}}{S_{m + 2}} + \ldots + R_{n} \frac{s_{n - 1}}{S_n}
f_n = f_m + F_{m + 1} \frac{s_{m}}{S_{m + 1}} + F_{m + 2} \frac{s_{m + 1}}{S_{m + 2}} + \ldots + F_n \frac{s_{n - 1}}{S_n}
The current earnings calculation approach computes each term in the above expressions in a loop with each iteration of the loop requiring a certain number of contract storage reads. As a result, the gas cost of calculating these earnings increases as n - m increases.
A More Efficient Calculation Approach
The recurrence relation for a delegator’s stake in round n can be re-written as follows:
s_n = s_{n - 1} (1 + \frac{R_n}{S_n})
s_m = s_m
The recurrence relation for a delegator’s fees in round n can be re-written as follows:
f_n = f_{n - 1} + s_{n - 1} \frac{F_n}{S_n}
f_m = f_m
The re-written stake and fees relations can be expanded as follows:
s_n = s_m (1 + \frac{R_{m + 1}}{S_{m + 1}}) (1 + \frac{R_{m + 2}}{S_{m + 2}}) \ldots (1 + \frac{R_n}{S_n})
f_n = f_m + s_m [ \frac{F_{m + 1}}{S_{m + 1}} + \frac{F_{m + 2}}{S_{m + 2}} (1 + \frac{R_{m + 1}}{S_{m + 1}}) + \frac{F_{m + 3}}{S_{m + 3}} \prod\limits_{m + 1}^{m + 2} (1 + \frac{R_i}{S_i}) + \ldots + \frac{F_n}{S_n} \prod\limits_{m + 1}^{n}{(1 + \frac{R_i}{S_i})} ]
Cumulative Reward and Fee Factors for Delegators
Given these updated relation expansions, we can use the following earnings calculation approach:
For each round n, an orchestrator stores a cumulativeRewardFactor and a cumulativeFeeFactor which are calculated as:
cumulativeRewardFactor_{n} = cumulativeRewardFactor_{n - 1} (1 + \frac{R_n}{S_n})
cumulativeFeeFactor_n = cumulativeFeeFactor_{n - 1} + cumulativeRewardFactor_{n - 1} \frac{F_n}{S_n}
Since F_n can be updated multiple times for round n (an orchestrator can redeem multiple winning tickets for a round), cumulativeFeeFactor could be updated multiple times in a round. We can support this with the following approach:
Let v_i be the face value of the i th winning ticket redeemed by an orchestrator for round n.
F_n = \sum{v_i}
We can express cumulativeRewardFactor_{n - 1} \frac{F_n}{S_n} as:
\sum{cumulativeRewardFactor_{n - 1} \frac{v_i}{S_n}}
Given the above expression, assuming that the initial value of cumulativeFeeFactor_n is cumulativeFeeFactor_{n - 1}, every time an orchestrator redeems a winning ticket for round n we can add cumulativeRewardFactor_{n - 1}\frac{v_i}{S_n} to cumulativeFeeFactor_n.
Additionally, note that:
- If R_n = 0 then an active orchestrator did not mint rewards for round n and cumulativeRewardFactor_n = cumulativeRewardFactor_{n - 1}. This implies that in order to account for the fact that an active orchestrator may not mint rewards in certain rounds, a lastRewardRound that tracks the last round that the orchestrator minted reward should be tracked.
- If F_n = 0 then an active orchestrator did not earn fees for round n and cumulativeFeeFactor_n = cumulativeFeeFactor_{n - 1}. This implies that in order to account for the fact that an active orchestrator may not earn fees in certain rounds, a lastFeeRound that tracks the last round that the orchestrator earns fees should be tracked.
For a delegator that delegated to the orchestrator in round m, its stake in round n can be calculated as:
s_n = s_m \frac{cumulativeRewardFactor_n}{cumulativeRewardFactor_m}
The delegator’s fees in round n can be calculated as:
f_n = f_m + s_m \frac{cumulativeFeeFactor_n - cumulativeFeeFactor_m}{cumulativeRewardFactor_m}
Since the cumulativeRewardFactor and cumulativeFeeFactor can be read for each round, the above calculations can be done without a constant number of operations (i.e. no loops) for a delegator.
Cumulative Rewards and Fees for Orchestrators
An orchestrator earns rewards and fees in a few ways:
- Earns a pro rata share of the rewards minted and fees generated in a round based on its self-delegated stake relative to its total stake
- Earns a pro rata share of the rewards minted and fees generated in a round based on its cumulative staked rewards (i.e. from the reward cut it takes each round which are automatically staked) relative to its total stake
- Takes a portion of the rewards minted in a round based on its reward cut
- Takes a portion of the fees generated in a round based on its fee share
We can calculate the reward and fee shares for 1 using the calculations already mentioned for delegators.
We can calculate the reward and fee shares for 2, 3 and 4 as follows:
Let y_n be the cumulative rewards earned by the orchestrator in round n.
Let z_n be the cumulative fees earned by the orchestrator in round n.
The recurrence relation for an orchestrator’s cumulative rewards in round n can be expressed as:
y_n = y_{n - 1} + R_n \frac{y_{n - 1}}{S_n} + g_n
y_m = y_m
g_n is the orchestrator’s share of rewards minted during round n based on its reward cut.
The recurrence relation for an orchestrator’s fees in round n can be expressed as:
f_n = f_{n - 1} + y_{n - 1} \frac{F_n}{S_n} + h_n
f_m = f_m
h_n is the orchestrator’s share of fees generated during round n based on its fee share.
Given these relations, we can use the follow earnings calculation approach for orchestrators:
An orchestrator stores cumulativeRewards, activeCumulativeRewards and cumulativeFees which are calculated as:
activeCumulativeRewards = cumulativeRewards
Note: That this update needs to be done during a round before the updates to cumulativeRewards and cumulativeFees because the updates to cumulativeRewards in the round are not considered active (i.e. eligible for reward/fee shares).
cumulativeRewards = cumulativeRewards + R_n \frac{cumulativeRewards}{S_n} + g_n
cumulativeFees = cumulativeFees + activeCumulativeRewards \frac{F_n}{S_n} + h_n
We can update cumulativeFees with each winning ticket redeemed by the orchestrator with the same approach described for cumulativeFeeFactor.
Then, an orchestrator’s stake in round n can be calculated as:
s_n = s_m \frac{cumulativeRewardFactor_n}{cumulativeRewardFactor_m} + cumulativeRewards
And an orchestrator’s fees in round n can be calculated as:
f_n = f_m + s_m \frac{cumulativeFeeFactor_n - cumulativeFeeFactor_m}{cumulativeRewardFactor_m} + cumulativeFees
TODOs
-
Figure out how to handle the fact that the fees for a winning ticket that is redeemed in round n + 2 can count for round n- This is now addressed above.
-
Figure out how this calculation approach can co-exist with the older calculation approach which will still be required for rounds during which cumulativeRewardFactor and cumulativeFeeFactor data is not stored for an orchestrator- This is addressed in LIP-36
-
Translate the algorithm described in this post into code and describe the actual changes required in the BondingManager contract- This is addressed in LIP-36