TIP-465: New reward calculation algorithm

[bladehan1]

tip: 465
title: new reward calculation algorithm
author:  bladehan@163.com
discussions-to: https://github.com/tronprotocol/tips/issues/465
status: Final
type: Standards Track 
category : Core
created: 2022-09-21

Simple Summary

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.

Abstract

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.

Motivation

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.

Specification

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.

Rationale

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.

Backwards Compatibility

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.

Test Cases

The test cases of TIP-271 are modified and reused, mostly, the testRewardAlgorithmNo series of test cases in the VoteTest class.

Implementation

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));
    }
  }      

1. The system will check and claim any unclaimed reward when voting.

2. 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;
  }

[Phoenix-Fragrant]

good

[bladehan1]

Close this issue as it is implemented by GreatVoyage-v4.6.0.
Check TIP detail at TIP-465
Check implementation PR at tronprotocol/java-tron#4694