A more gas efficient earnings calculation approach

Protocol
#1

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

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

An orchestrator earns rewards and fees in a few ways:

  1. 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
  2. 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
  3. Takes a portion of the rewards minted in a round based on its reward cut
  4. 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}{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
  • Translate the algorithm described in this post into code and describe the actual changes required in the BondingManager contract
3 Likes
#2

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.

#3

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?

#4

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.

That’s one benefit of using the ticket’s creationRound. The other reason for using the ticket’s creationRound is because fees ideally should go to delegators staked to the orchestrator in the round that a ticket was created since the delegator’s stake helped the orchestrator get selected for work.

While technically a ticket’s creationRound can be at most currentRound - 2, in practice tickets are usually going to be redeemed in the round that they are created so assigning fees to rounds that have already passed may not be that big of a problem.

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.

Yeah that is what I’m thinking - use the old earnings calculation algorithm up to the first round that cumulative values are stored for the orchestrator and then use the new earnings calculation algorithm from then on which doesn’t require any additional looping.

#5

I updated the OP to address this - see the section on “Cumulative Rewards and Fees for Orchestrators”.