Solution for FIO Staking Math Issues
Background
After FIO Staking was initially developed as part of FIP-21, the following issues have been identified:
Rapidly growing ROE issue - in certain conditions, Rate of Exchange (ROE) may grow to extremely high values, causing significant rounding issues and overflow potential.
Rounding issues impacting user experience - in certain conditions user may receive smaller number of FIO than they staked.
Use of floating point calculations in blockchain should be avoided, because due to rounding, calculations and comparisons may vary depending on compiler, optimizations, or architecture used.
Solution
ROE freeze
ROE will now be frozen, when total number of FIO tokens staked is less than 1M FIO. This will be accomplished by permanently storing last known values of Combined Token Pool (CTP) and Global Staking Rewards Point (GSRP) and only updating it when more than 1M FIO is staked. This will effectively postpone the payout of reward, but not its accrual and will ensure proper accounting of all tokens. Specifically:
CTP and GSRP will be initialized to 0.
Two new global variables will be tracked and will represent the last “valid” CTP (LCTP) and GSRP (LGSRP) values.
LCTP will be initialized to 1,000,000,000,000,000 (which the minimum staked amount to activate staking, or 1M FIO).
LGSRP will be initialized to 2,000,000,000,000,000 (which is double LCTP).
ROE will be computed by dividing LSTP by LGSRP.
If total tokens staked are >= 1M FIO AND activation date passed LCTP and LGSRP will be updated every time CTP and GSRP changes.
If total tokens staked are < 1M at any time OR activation date not passed, LCTP and LGSRP will be not be updated when CTP and GSRP changes.
Fixed-point arithmetic
All Staking calculations will use fixed-point arithmetic, meaning only int multiplication and division will be used. ROE will no longer be computed or stored as an interim variable, but instead the target calculation will be completed. See below for Sample C++ code example of staking and unstaking using fixed-point arithmetic.
Interim variables
In order to avoid overflow on interim variables, which are upscaled to higher values to accommodate fixed-point arithmetic, uint128 variables will be used.
Rounding
In fixed-point arithmetic a result of division is an int and a remainder. Therefore any operation will always “round down”. For example 83 / 21 will produce 3 and remainder 20. Since 83 / 21 in floating point math will produce 3.95 a desired result would be 4. To achieve this the remainder (20) is compared to denominator divided by 2 (21 / 2 = 10). If it is same or higher the result of the original calculation is increased by 1 (3+1 = 4).
It is important to note that rounding errors will still occur, but would be less pronounced. Therefore it is critical that underflow checks are performed.
Underflow checks
In rare cases rounding can result in more units being subtracted than is available which can cause underflow. To prevent this the following checks are implemented and throw an exception:
On unstake
Subtracting from CTP
If more being subtracted than available throw exception
Subtracting from GSRP
If more being subtracted than available throw exception
Subtracting from User’s SRP
If more being subtracted than available throw exception
Subtracting from User’s staked SUFs
If more being subtracted than available throw exception
Analysis and Testing
Sample C++ code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Staking unstake example with rounding
#include <iostream>
#include <string>
typedef unsigned __int128 uint128_t;
int main()
{
uint64_t lctp = 1003835500000000; // Last Combined Token Pool
uint64_t lgsrp = 2000000000000000; // Last Global Staking Reward Points
const uint128_t mult = 1000000000000000000; // mult constant is a multiplier factor to be used in int division. An int will be first multiplied by the mult before it's divided to ensure high precision.
// Stake SUFs
uint64_t stake = 3000000000000; // Amount of tokens to be staked
std::cout << "Staking " << stake << " SUFs \n";
uint128_t interim_mult_lctp = (uint128_t) lctp * mult; // LCTP is multiplied by mult and stored as interim variable
uint128_t interim_mult_lctpBYlgsrp = interim_mult_lctp / (uint128_t) lgsrp; // interim variable interim_mult_lctp is now divided by LGSRP
uint128_t interim_mult_stake = (uint128_t) stake * mult; // Amount of SUFs to stake is now multiplied by mult and stored as interim variable
uint128_t got_srp_big = interim_mult_stake / interim_mult_lctpBYlgsrp; // The 2 interim variables are now divided to produce number of SRPs to award
// Round instead of truncate
uint128_t rem_got_srp_big = interim_mult_stake % interim_mult_lctpBYlgsrp;
if (rem_got_srp_big >= (interim_mult_lctpBYlgsrp / (uint128_t) 2)) {
got_srp_big++;
}
uint64_t got_srp = (uint64_t) got_srp_big; // This just converts from uint128 to uint64. Not sure if this is needed
std::cout << "Got " << got_srp << " SRPs \n";
// Unstake SUFs... I mean SRPs
uint64_t user_srps = 1990000000000000; // Number of SRPs held by specific user
uint64_t user_staked_suf = 995000000000000; // Number of SUFs staked by specific user
uint64_t unstake = 1000000000000; // Number of SUFs to be unstaked
// First we need to determine how many SRPs need to be unstaked, since we only get SUF as input
uint64_t srps_unstake;
if (unstake == user_staked_suf) {
srps_unstake = user_srps; // If all SUFs then all SRPs
} else {
uint128_t interim_mult_unstake = (uint128_t) unstake * mult; // unstake sufs are multiplied by mult and stored as interim variable
uint128_t interim_suf_share = (uint128_t) interim_mult_unstake / (uint128_t) user_staked_suf; // the interim variable is divided by staked sufs to get upscaled share of srp
uint128_t interim_srps_unstake_upscaled = interim_suf_share * (uint128_t) user_srps; // user's SRPs are multiplied by upscaled share of SUFs being unstaked to produce upscaled SRPs to unstake
uint128_t interim_srps_unstake = interim_srps_unstake_upscaled / mult; // SRPs are downscaled by dividing by multiplier
// Round instead of truncate
uint128_t rem_interim_srps_unstake = interim_srps_unstake_upscaled % mult;
if (rem_interim_srps_unstake >= (mult / (uint128_t) 2)) {
interim_srps_unstake++;
}
srps_unstake = (uint64_t) interim_srps_unstake; // This just converts from uint128 to uint64. Not sure if this is needed
}
std::cout << "Unstaking " << srps_unstake << " SRPs \n";
uint128_t interim_usrplctp = (uint128_t) srps_unstake * (uint128_t) lctp; // SRPs being unstaked are multiplied by LCTP first
uint128_t got_suf_big = interim_usrplctp / (uint128_t) lgsrp; // Then are divided by LGSRP
// Round instead of truncate
uint128_t rem_got_suf_big = interim_usrplctp % (uint128_t) lgsrp;
if (rem_got_suf_big >= ((uint128_t) lgsrp / (uint128_t) 2)) {
got_suf_big++;
}
// Take 90% of reward
uint128_t topay;
uint128_t reward = got_suf_big - (uint128_t) unstake;
if (reward > 0) {
uint128_t reward10 = reward / (uint128_t) 10;
// Round instead of truncate
uint128_t rem_reward10 = reward % (uint128_t) 10;
if (rem_reward10 >= ((uint128_t) 10 / (uint128_t) 2)) {
reward10++;
}
reward = reward - reward10;
topay = unstake + reward;
} else topay = reward;
uint64_t got_suf = (uint64_t) topay; // This just converts from uint128 to uint64. Not sure if this is needed
std::cout << "Got " << got_suf << " SUFs \n";
}
Interim variables
The following is an analysis of each interim variable overflow probability using variable names from above example. The analysis is performed using existing system constrains, e.g. FIO token max supply.
Maximum values of variables:
uint64_t: 9,223,372,036,854,775,807
uint128_t: 340,282,366,920,938,463,463,374,607,431,768,211,455
lctp | uint64_t | Last Combined Token Pool | Cannot overflow. This variable will never exceed circulating supply of SUFs, which is 1,000,000,000,000,000,000 and within uint64_t limits. |
lgsrp | uint64_t | Last Global Staking Rewards Point | Cannot overflow. Since LCTP is initialized to 1,000,000,000,000,000 and LGSRP to 2,000,000,000,000,000, it means that the maximum supply of SRPs can never exceed half of circulating supply of SUFs, or 500,000,000,000,000,000. Since the ROE can only go up, fewer and fewer SRPs will be minted going forward. |
mult | uint128_t | Upscaling multiplier constant used to upscale int to accommodate division. It’s initialized to 1,000,000,000,000,000,000 | Cannot overflow. This constant never changes and is within limits of uint128_t |
interim_mult_lctp | uint128_t | lctp * mult | Cannot overflow. Maximum value of interim_mult_lctp is max value of lctp * max value of mult, which is: 1,000,000,000,000,000,000 * 1,000,000,000,000,000,0001,000,000,000,000,000,000 = 1,000,000,000,000,000,000,000,000,000,000,000,000 which is within limits of uint128_t |
interim_mult_lctpBYlgsrp | uint128_t | interim_mult_lctp / lgsrp | Cannot overflow. Since this variable is a quotient of a division where interim_mult_lctp is the dividend, it will never exceed interim_mult_lctp which is within limits of uint128_t |
interim_mult_stake | uint128_t | tokens being staked * mult | Cannot overflow. Maximum value of interim_mult_stake is max value of circulating supply of SUFs * mult, which is the same as interim_mult_lctp and therefore within limits of uint128_t |
got_srp_big | uint128_t | interim_mult_stake / interim_mult_lctpBYlgsrp | Cannot overflow. Since this variable is a quotient of a division where interim_mult_stake is the dividend, it will never exceed interim_mult_stake which is within limits of uint128_t |
rem_got_srp_big | uint128_t | interim_mult_stake % interim_mult_lctpBYlgsrp | Cannot overflow. Since this variable is the the remainder of a division where got_srp_big is the dividend, it will never exceed got_srp_big which is within limits of uint128_t |
interim_mult_unstake | uint128_t | tokens being unstaked * mult | Cannot overflow. Maximum value of interim_mult_unstake is max value of circulating supply of SUFs * mult, which is the same as interim_mult_stake and therefore within limits of uint128_t |
interim_suf_share | uint128_t | interim_mult_unstake / user_staked_suf | Cannot overflow. Since this variable is a quotient of a division where interim_mult_unstake is the dividend, it will never exceed interim_mult_unstake which is within limits of uint128_t |
interim_srps_unstake_upscaled | uint128_t | interim_suf_share * user_srps | Cannot overflow. Maximum value of max interim_suf_share is 1,000,000,000,000,000,000 and that’s because a user can never unstake more tokens than they have staked, which means max circulating supply of SUFs * mult / max circulating supply of SUFs. Maximum value of user_srps is same as lgsrp or 500,000,000,000,000,000 Therefore max value of interim_srps_unstake_upscaled is 1,000,000,000,000,000,000 * 500,000,000,000,000,000 = 500,000,000,000,000,000,000,000,000,000,000,000 which is within limits of uint128_t |
interim_srps_unstake | uint128_t | interim_srps_unstake_upscaled / mult | Cannot overflow. Since this variable is a quotient of a division where interim_srps_unstake_upscaled is the dividend, it will never exceed interim_srps_unstake_upscaled which is within limits of uint128_t |
rem_interim_srps_unstake | uint128_t | interim_srps_unstake_upscaled % mult | Cannot overflow. Since this variable is the the remainder of a division where interim_srps_unstake_upscaled is the dividend, it will never exceed interim_srps_unstake_upscaled which is within limits of uint128_t |
interim_usrplctp | uint128_t | srps_unstake * lctp | Cannot overflow. Maximum value of srps_unstake is max circulating supply of SUFs or 1,000,000,000,000,000,000 Max value of lctp is half of max circulating supply of SUFs or 500,000,000,000,000,000 Therefore max value of interim_usrplctp is 1,000,000,000,000,000,000 * 500,000,000,000,000,000 = 500,000,000,000,000,000,000,000,000,000,000,000 which is within limits of uint128_t |
got_suf_big | uint128_t | interim_usrplctp / lgsrp | Cannot overflow. Since this variable is a quotient of a division where interim_usrplctp is the dividend, it will never exceed interim_usrplctp which is within limits of uint128_t |
rem_got_suf_big | uint128_t | interim_usrplctp % lgsrp | Cannot overflow. Since this variable is a quotient of a division where interim_usrplctpis the dividend, it will never exceed interim_usrplctp which is within limits of uint128_t |
Modeling
An Excel model has been used to replicate the C++ math and evaluate for overflow, underflow, and rounding issues.
This model requires XLPrecision Excel add-on.