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 rewards earned since round m.
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 round m.
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.
A More Efficient Calculation Approach
The recurrence relation for a delegator’s stake in round n can be rewritten 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 rewritten as follows:
f_n = f_{n  1} + s_{n  1} \frac{F_n}{S_n}
f_m = f_m
The rewritten 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_mx
x = \frac{F_{m + 1}}{S_{m + 1}} +(1 + \frac{R_{m + 1}}{S_{m + 1}}) \frac{F_{m + 2}}{S_{m + 2}} + (1 + \frac{R_{m + 1}}{S_{m + 1}}) (1 + \frac{R_{m + 2}}{S_{m + 2}}) \frac{F_{m + 3}}{S_{m + 3}} + \ldots + (1 + \frac{R_{m + 1}}{S_{m + 1}}) \ldots (1 + \frac{R_n}{S_n}) \frac{F_n}{S_n}
Cumulative Reward and Fee Factors
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 (since 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}
Thus, 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.
Using Cumulative Reward and Fee Factors
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}{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. not loops) for a delegator.
Cumulative Rewards and Fees for Orchestrators
The recurrence relation for an orchestrator’s stake in round n can be expressed as:
s_n = s_{n  1} + R_n \frac{s_{n  1}}{S_n} + g_n
s_m = s_m
Note the additional g_n term that is not present in the recurrence relation for a delegator’s stake. g_n is the orchestrator’s share of rewards minted during round n based on its commission rate.
The recurrence relation for an orchestrator’s fees in round n can be expressed as:
f_n = f_{n  1} + s_{n  1} \frac{F_n}{S_n} + h_n
f_m = f_m
Note the additional h_n term that is not present in the recurrence relation for a delegator’s fees. h_n is the orchestrator’s share of fees generated during round n based on its commission rate.
Given these relations, we can use the follow earnings calculation approach for orchestrators.
An orchestrator stores cumulativeRewards and cumulativeFees which are calculated as:
cumulativeRewards = cumulativeRewards + R_n \frac{s_{n  1}}{S_n} + g_n
cumulativeFees = cumulativeFees + s_{n  1} \frac{F_n}{S_n} + h_n
Then, an orchestrator’s stake in round n can be calculated as:
s_n = s_m + cumulativeRewards
f_n = f_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 coexist 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 will be addressed in the LIP

Translate the algorithm described in this post into code and describe the actual changes required in the BondingManager contract This will be addressed in the LIP