tip: 465
title: new reward calculation algorithm
author: [email protected]
discussions-to: https://github.com/tronprotocol/tips/issues/465
status: Final
type: Standards Track
category : Core
created: 2022-09-21
The new reward algorithm is used to reduce the time-consuming of reward calculation. It has been implemented in TIP-271, but the corresponding proposal has not been passed, so a proposal that only contains this algorithm is made independently.
Analyzing the existing reward algorithm of the code, the reward calculation time is proportional to the number of maintenance periods after the user votes. When there are many maintenance periods, the transaction execution takes a long time. This paper details the optimized reward algorithm.
The current reward algorithm records the user's latest voting witness and the corresponding number of votes. Each maintenance period records the witness's revenue and total votes. For the user‘s reward, it is necessary to calculate a reward share for each voting witness per maintenance period, in which the time complexity O (maintenance period * vote witness number), increases linearly with the number of maintenance period rounds. As a result, it sometimes takes more than 1s to extract rewards-related transactions, which reduces the transaction volume of production blocks. The above problems can be recorded by accumulating the rewards per vote for each maintenance period, simplifying the cross-cycle calculation, and reducing the time complexity to O (number of vote witnesses)
TIP-271, which is mainly based on TVM support contract voting, comes with a new reward algorithm. It was not passed in the voting of the 2021-10 No. 70 proposal, so an independent proposal was made.
In order to quickly calculate the multi-maintenance period rewards, the cumulative per-ticket rewards are introduced:
public void setWitnessVi(long cycle, byte[] address, BigInteger value) {
put(buildViKey(cycle, address), new BytesCapsule(value.toByteArray()));
}
This records the accumulated rewards per ticket during a maintenance period. The reward per ticket during the current maintenance period equals the witness reward during the maintenance period/number of tickets, and the cumulative reward per ticket is the prefix sum of the reward per ticket during the maintenance period.
The prefix sum algorithm is a preprocessing algorithm that can quickly find the interval sum of an array. Through the prefix sum algorithm, the time complexity of the maintenance period interval summation on a single witness is reduced to O(1), which avoids the long-time execution of extracting rewards.
This proposal contains a hard fork upgrade, and older versions cannot check and process transactions that contain this proposal. Users should upgrade to the new version, otherwise, they will fork with the upgraded node.
The test cases of TIP-271 are modified and reused, mostly, the testRewardAlgorithmNo series of test cases in the VoteTest class.
During the maintenance period, the accumulated per-ticket rewards are calculated and recorded. The cumulative reward per ticket of witness in the current maintenance period equals the sum of the reward per ticket in the current maintenance period and the accumulated reward per ticket in the previous maintenance period; in the first maintenance period when the proposal takes effect, the cumulative reward per ticket equals the reward per ticket in the maintenance period.
Store the accumulated per-ticket rewards for each witness per maintenance period,
long curCycle = dynamicPropertiesStore.getCurrentCycleNumber();
consensusDelegate.getAllWitnesses().forEach(witness -> {
delegationStore.accumulateWitnessVi(curCycle, witness.createDbKey(), witness.getVoteCount());
});
Calculate and store accumulated per-ticket rewards,
public void accumulateWitnessVi(long cycle, byte[] address, long voteCount) {
BigInteger preVi = getWitnessVi(cycle - 1, address);
long reward = getReward(cycle, address);
if (reward == 0 || voteCount == 0) { // Just forward pre vi
if (!BigInteger.ZERO.equals(preVi)) { // Zero vi will not be record
setWitnessVi(cycle, address, preVi);
}
} else { // Accumulate delta vi
BigInteger deltaVi = BigInteger.valueOf(reward)
.multiply(DECIMAL_OF_VI_REWARD)
.divide(BigInteger.valueOf(voteCount));
setWitnessVi(cycle, address, preVi.add(deltaVi));
}
}
-
The system will check and claim any unclaimed reward when voting.
-
Calculation of the Reward,
a. use the old algorithm if the maintenance period is earlier than the new algorithm is applied b. for the part of the maintenance period after the new algorithm is applied, for each voting witness, calculate the sum of the reward of the intervals, 1. for each single voting witness, the reward equals the accumulated per-ticket reward of the time interval multiplied by voting tickets
Calculate the reward,
private long computeReward(long beginCycle, long endCycle, AccountCapsule accountCapsule) {
if (beginCycle >= endCycle) {
return 0;
}
long reward = 0;
long newAlgorithmCycle = dynamicPropertiesStore.getNewRewardAlgorithmEffectiveCycle();
if (beginCycle < newAlgorithmCycle) {
long oldEndCycle = Math.min(endCycle, newAlgorithmCycle);
for (long cycle = beginCycle; cycle < oldEndCycle; cycle++) {
reward += computeReward(cycle, accountCapsule);
}
beginCycle = oldEndCycle;
}
if (beginCycle < endCycle) {
for (Vote vote : accountCapsule.getVotesList()) {
byte[] srAddress = vote.getVoteAddress().toByteArray();
BigInteger beginVi = delegationStore.getWitnessVi(beginCycle - 1, srAddress);
BigInteger endVi = delegationStore.getWitnessVi(endCycle - 1, srAddress);
BigInteger deltaVi = endVi.subtract(beginVi);
if (deltaVi.signum() <= 0) {
continue;
}
long userVote = vote.getVoteCount();
reward += deltaVi.multiply(BigInteger.valueOf(userVote))
.divide(DelegationStore.DECIMAL_OF_VI_REWARD).longValue();
}
}
return reward;
}