search

tronprotocol / tips

TRON Improvement Proposals
229 stars 203 forks source link

TIP-635: Optimize Reward Withdrawal To Improve TPS #635

Closed halibobo1205 closed 7 months ago

halibobo1205 commented 10 months ago

Simple Summary

This TIP aims to optimize the algorithm of the voting reward withdrawal in Phase1 (since TIP-53, before TIP-465 took effect) to improve the TPS of such transactions.

Abstract

There are currently two phases of the TRON protocol voting reward:

Due to the poor performance of the current Phase1 voting reward withdrawal algorithm, when a user who has Phase1 reward initiates the transactions triggering the algorithm, the performance of the network would degrade.

This TIP proposes a scheme that optimizes the relevant calculation complexity to O(1) for Phase1 without an additional reward withdrawal logic, greatly optimizing the calculation performance of Phase1 reward and improving the TPS.

Motivation

Performance

According to statistics, there are currently about 160k users on the TRON mainnet who have Phase1 rewards to be withdrawn. By comparing the performance of the Phase1 reward algorithm before and after optimization in the test environment, it is expected that this optimization plan can improve performance by >20 times.

User Reward

The current Phase1 voting reward withdrawal uses truncation at the end of the decimal, resulting in the current actual value being slightly smaller than the expected value. The optimized algorithm will adopt higher calculation accuracy, and the calculation value will be closer to the expected values. At the same time, the difference in results before and after optimization will be controlled within 1 TRX, which will have almost no impact on the TRX inflation of the entire network and user rewards.

Specification

Glossary

In Phase1 and Phase2, the calculation logic of voting reward for a single SR vote is as follows:

userReward(s) = for i range [startCycle, newRewardCycle) {
  userReward(s) += userVote(s)/totalVote(i, s) * totalReward(i,s) 
}
userReward(s) = userVote(s) * (accumulateRewardPerVote[newRewardCycle - 1,s] - accumulateRewardPerVote[endCycle - 1,s])

Phase1.algorithm1 uses iterative calculations for each maintenance[startCycle, endCycle) and does an accumulation in the final, and the algorithm complexity is O(n).

Phase2.algorithm directly multiplies the userVote(s) and the delta between the accumulateRewardPerVote[startCycle-1, s] and accumulateRewardPerVote[endCycle-1, s], and the algorithm complexity is O(1). For more information please refer to TIP-465.

The Phase1.algorithm2 remains the same as the Phase2.algorithm. Based on the previous analysis, this optimization includes the following steps:

  1. Pre-calculate rewardViSet, and persist it into rewardViStore.
  2. Using phase1OptProposal to control whether the phase1.algorithm2 should be adopted.
  3. After the phase1OptProposal is passed, the reward calculation of the transactions involved in Phase1 will use phase1.algorithm2, which will use the rewardViSet to calculate the result with O(1) performance. The difference between phase1.algorithm1 and Phase1.algorithm2 is within 1 TRX.

Note: The voting reward withdrawal can be triggered by the following transactions:

Rationale

Impacts on Ecology

Data Consistency

This optimization affects the voting reward calculation logic and the consensus. Therefore, a proposal is needed to control the optimization to ensure data consistency on the chain.

Pre-calculation of rewardViSet

To minimize the impact on node performance, pre-calculation is executed asynchronously. However asynchronous tasks often have some state synchronization problems, so the execution logic of pre-calculation tasks needs to be described in detail here.

  1. RewardViCalService: This service will start with the node. It is responsible for detecting whether the newRewardCalculationAlgorithmProposal is enabled for every 3s.
    1. if enabled: execute calculateRewardViTask asynchronously
      1. calculateRewardViTask has been completed based on the finishFlag.
        1. completed: stop the monitor service, then return
        2. not completed: start calculateRewardViTask and wait for complete, stop monitor service, then return
    2. not enabled: enter the next detection
  2. CalculateRewardViTask:
    1. calculate SR single vote accumulated reward value from the maintenance period TIP-53 took effect to TIP-465 took effect
    2. store rewardViSet into RewardViStore, the data composition is consistent with TIP-465
    3. write finishFlag

Transaction Execution

Check if there is any Phase1 voting reward

  1. if there is: check if phase1OptProposal is activated
    1. activated: check if the calculateRewardViTask is completed
      1. completed: transaction adopts Phase1.algorithm2.
      2. not completed: blocked and waiting for the calculateRewardViTask to be completed, and the transaction adopts Phase1.algorithm2.
    2. not activated: the transaction adopts Phase1.algorithm1
  2. if there is not: the transaction adopts Phase2.algorithm

Backward Compatibility

According to the above sections, this optimization has no compatibility issues. Please note that if any third party implements an off-chain voting reward estimation algorithm individually, please adapt these changes promptly.

tomatoishealthy commented 9 months ago

Sounds great, looking forward to future developments

CarlChaoCarl commented 9 months ago

Will the difference in results before and after optimization lead to hard forks or data inconsistencies?

@halibobo1205

lxcmyf commented 9 months ago

Note: The voting reward withdrawal can be triggered by the following transactions:

  • VoteWitnessContract
  • UnfreezeBalanceContract
  • UnfreezeBalanceV2Contract
  • WithdrawBalanceContract

@halibobo1205 Will these transaction types involve code changes?

jwrct commented 9 months ago

@halibobo1205 What problems will exist on the Tron network if this optimization is not implemented and the current logic is maintained?

jwrct commented 9 months ago

One more question, in the logic of transaction execution, in scenario 1.i.b, will blocking make the node unavailable, for example, producing blocks, processing blocks, processing other transactions, etc.?

KrisdiaPaul commented 9 months ago

I wonder if I voted in phase 1, and have rewards in both phase 1 and phase 2, if I withdraw all the rewards, is it calculated by phase1.algorithm only? And then I will have new rewards only in phase 2, if I withdraw the new rewards again, is it calculated by phase1.algorithm too?

halibobo1205 commented 9 months ago

Will the difference in results before and after optimization lead to hard forks or data inconsistencies?

@CarlChaoCarl Yes, a hard fork is required.

halibobo1205 commented 9 months ago

I wonder if I voted in phase 1, and have rewards in both phase 1 and phase 2, if I withdraw all the rewards, is it calculated by phase1.algorithm only? And then I will have new rewards only in phase 2, if I withdraw the new rewards again, is it calculated by phase1.algorithm too?

@KrisdiaPaul phase 1 is calculated by phase1.algorithm , phase 2 is calculated by phase2.algorithm. if you withdraw the new rewards again, there is no reward in phase 1, because after TIP-465, there is no reward in phase 1.

halibobo1205 commented 9 months ago

One more question, in the logic of transaction execution, in scenario 1.i.b, will blocking make the node unavailable, for example, producing blocks, processing blocks, processing other transactions, etc.?

There is a very low probability that it will occur, it will not occur under normal conditions, and the calculation task will take about 5 minutes, which is more than enough time for the new proposal to take effect.

halibobo1205 commented 9 months ago

@halibobo1205 What problems will exist on the Tron network if this optimization is not implemented and the current logic is maintained?

@jwrct The TPS of the related transactions may be unstable.