A more gas efficient earnings calculation approach

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 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_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 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 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
3 Likes

I overall like the mechanism and how an orchestrator operating under normal conditions should greatly reduce costs for its delegators to claim rewards.I also believe the math checks out.

Figure out how to handle the fact that the fees for a winning ticket that is redeemed in round n+2

If I remember correctly, currently we use a ticket’s creation round to assign the fees but if delegators have already called claim earnings for a round they will miss out on any subsequent fees from redeemed tickets for that round.

I believe we use the creationRound instead of currentRound because if the transcoder is no longer active in currentRound the fees can’t be assigned properly due to the feeshare not being initiated on the EarningsPool for that round.

Wonder if we could do something similar to reward() though whereby we will use the currentRound to assign fees to the earningsPool and use the last known feeShare for the orchestrator when it is no longer active.

Using currentRound means we would never be assigning fees to rounds that have already passed so then handling that is no longer a concern.

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 would imply that an orchestrator has not called reward() though, correct ?

Assuming here that the orchestrator would store these values by calling reward() each round (which I think seems the most reasonable implementation wise).

So that would also mean that there are no rewards to be paid out for the rounds that didn’t happen, meaning we’d only have to worry about paying fees at that point. I feel like we can calculate the fees and rewards for the round up to which the last cumulative values are stored and then loop from that point on.

I’m not sure if this matters or not, but I didn’t see any mention of the RewardShare or FeeCut (and the fact that it can change from round to round) factored into the math. Perhaps it’s just abstracted within the cumulative factors?