Exponential Growth in Solidity with Fixed-Point Math

Overview

1. Why Fixed-Point Math is Useful in Solidity
2. Approaches to Compounding
3. When to Use Each Approach

Why Fixed-Point Math is Useful in Solidity

If you’ll take my word for it, fixed-point math allows for a more accurate calculation of processes such as compounding interest, exponential token vesting, even radioactive decay if you like. You can skip to the code examples.

If you would like to understand why yourself, I have to introduce you to some math to really show you why fixed-point math in Solidity is useful, especially when using some open-source libraries that facilitate it. So, here’s my practical understanding.

This equation represents a single term in a geometric sequence for exponential growth:

It compounds the initial value $y_0$ such that compounding happens after each iteration. Meaning, for an r value of 1.05, the first term in the sequence will yield a $y_n$ value of $y_0$, but the exponent will kick in for the second, yielding $1.05 * y0$. For this $r$ value of 1.05 (any $r > 1$), the sum of the sequence terms would result in exponential growth, for $r = 1$, the growth would be linear, and for $0 < r < 1$, there’d be exponential decay. Such a summation of sequence terms would look like this for four terms representing four compounds:

Fortunately, the pen-and-paper magicians of yesteryear have figured out that the sum a geometric series containing $n$ terms can be expressed as a single equation, commonly expressed as:

Where $a_1$ is the initial amount to be compounded (equivalent to $y_0$ above, just a naming convention).

Given this foundation, here’s a simplified example of using compounding to vest tokens exponentially, and the pitfall faced in vanilla Solidity - that it does not allow for use of floating point numbers. To illustrate the problem, I’ll vest 137 tokens daily over three days with 13% compounding per iteration, so $a_0 = 137$, $n = 3$, and $r = 1.13$.

However, if I want to calculate this on-chain at the same scale, i.e. 137 tokens, not 137e18 tokens, $r$ has to be truncated. The expression becomes:

With some handling of the $r = 1$ case (linear growth), is still quite a ways from the true value. The solution to this in Solidity is fixed-point math, which means, in essence, adding zeros to the end of a number to increase precision of operations. For example, if I want to split 100 tokens (just 100 not 100e18) into thirds and have an error tolerance of 0.1% of the total amount, I would multiply the 100 tokens by maybe 1e4 to increase precision, which allocates (“fixes”) four digits to the fractional part of the 100 tokens.

Now, the 100 tokens are expressed as 100e4, so when this is divided by three, I get 333333. All three thirds add to 999999 units now, which is equivalent to 99.9999 tokens in the original terms.

This is how Ether and ERC20 tokens work. They usually have 18 decimals, so if one has 1 ether, they have 1e18 wei, the unit in which the math is actually done to deal with fractional ether.

In short, if more precision is needed, add more zeros to the end of the number and assert that those added zeros hold the fractional part of the original number.

There are libraries which facilitate fixed-point math in Solidity, allowing for both gas-efficient math, as well as ability to do math directly with fractional numbers, which could not be done with default Solidity types. The libraries I’ll touch on are ABDKMath64x64 and PRBMath, and will compare their use to more straightforward Solidity implementations.

In short, the main difference between the two libraries is that ABDKMath64x64 utilizes signed 64.64-bit fixed-point numbers, while PRBMath utilizes signed 59.18-decimal fixed-point and unsigned 60.18-decimal fixed-point numbers. This N.N notation indicates the number of bits allocated to the integer and fractional parts of the number, respectively. The reason I mention this is because the range of numbers that can be computed in each library is limited by both the bit distribution between integer and fractional parts, as well as whether signed or unsigned integers are used.

Approaches to Compounding

(Remix workspace can be accessed here, so you can give these a try)

I considered 4 approaches to calculating the sum of the geometric series above for any combination of a, r, and n which would result in $S_n <$ type(uint256).max:

1. Inbuilt Solidity, Each Geometric Series Term In-Loop
2. Inbuilt Solidity, Expression for Sum of Geometric Series
3. ABDKMath64x64, Expression for Sum of Geometric Series
4. PRBMath, Expression for Sum of Geometric Series

I tested them each with the condition of $a = 10000e18$, $r = 1.005$, $n=365$ to simulation the vesting of 10000 tokens, each additional unlock compounding daily at a rate of 0.5%.

This combination yields $S_n = 10349305566862491615165029.368287 \approx 1.0359e25$ in floating point math. This serves as the reference value against which the Solidity outputs are to be measured.

Inbuilt Solidity, Each Geometric Series Term In-Loop

• Output: $S_n = 10349305566862491615102801$
• Error: 62228.368287 or 6.01e-20% of reference
• Gas Consumed: 249850

// For 0 through n sum the terms of a_n = a_0*(1+r)^(n-1)
function calculateExponentialLoopSolidity(
    uint256 a,
    uint256 n,
    uint256 radd
) public pure returns (uint256) {
    //numerator of growth rate: (radd + 1e18) / 1e18 
    uint256 growthRateNumerator = radd + DENOMINATOR;
 
    if (n == 0) {
        return 0;
    }
 
    uint256 total = a; // Initial amount vested at the start
    uint256 current = a;
 
    for (uint256 i = 1; i < n; i++) {
        // Calculate the amount for the current interval
        current = (current * growthRateNumerator) / DENOMINATOR;
 
        // Accumulate the total amount
        total += current;
    }
 
    return total;
}

Inbuilt Solidity, Expression for Sum of Geometric Series

• Output: $S_n = 10349305566862490604000000$
• Error: 1011165029.368287 or 9.77e-16% of reference
• Gas Consumed: 181378

function calculateExponentialGeomSeriesSolidity(
    uint256 a,
    uint256 n,
    uint256 rAdd
) public pure returns (uint256) {
    if (rAdd == 0 || n == 0) {
        return a * n;
    } else {
        // Convert inputs to fixed-point format
        // by multiplying by DENOMINATOR
        uint256 aScaled = a * DENOMINATOR;
        uint256 r = (rAdd + DENOMINATOR);
 
        // Initialize the sum of the series
        uint256 S_n = 0;
 
        // Calculate r^n and the sum S_n = a * (r^n - 1) / (r - 1)
        uint256 rToN = DENOMINATOR; // r^0 = 1
        for (uint256 i = 0; i < n; i++) {
            rToN = (rToN * r) / DENOMINATOR;
        }
 
        // Avoid division by zero when r == 1
        if (r != DENOMINATOR) { 
            S_n = (aScaled * (rToN - DENOMINATOR)) / (r - DENOMINATOR);
        } else {
            S_n = aScaled * n;
        }
 
        // Convert the result back to a normal number
        return S_n / DENOMINATOR;
    }
}

ABDKMath64x64, Expression for Sum of Geometric Series

• Output: $S_n = 10349305566862000000000000$
• Error: 491615165029.368287 or 4.75e-13% of reference
• Gas Consumed: 6432

function calculateExponentialABDK(
    uint256 a,
    uint256 n,
    uint256 radd
) public pure returns (uint256) {
    if (radd == 0) {
        return a * n;
    } else {
        uint256 scaleFactor = 10 ** SCALE_DECIMALS;
 
        //scale input s.t. result < type(uint64).max
        int128 aScaled = ABDKMath64x64.divu(a, scaleFactor);
 
        //calculate growth rate as (radd + DENOMINATOR) / DENOMINATOR
        int128 r = ABDKMath64x64.divu(radd + DENOMINATOR, DENOMINATOR);
 
        int128 rToN = r.pow(n);
        
        // Calculate the sum of S_n = a * (r^n - 1) / (r - 1)   
        int128 seriesSum = aScaled.mul(
            rToN.sub(ABDKMath64x64.fromInt(1))
        ).div(
            r.sub(ABDKMath64x64.fromInt(1))
        );
 
        //return the rescaled output
        return uint256(seriesSum.toUInt()) * scaleFactor;
    }
}

PRBMath, Expression for Sum of Geometric Series

• Output: $S_n = 10349305566862491092000000$
• Error: 523165029.368287 or 5.06e-16% of reference
• Gas Consumed: 6612

function calculateExponentialPRB(
    uint256 _firstIntervalAccrual,
    uint256 _elapsedIntervals,
    uint256 _growthRateProportion
) public pure returns (uint256) {
    if (_growthRateProportion == 0 || _elapsedIntervals == 0) {
        return _firstIntervalAccrual * _elapsedIntervals;
    } else {
        UD60x18 a = wrap(_firstIntervalAccrual);
 
        // Calculate the growth rate as a UD60x18 fixed-point number
        UD60x18 r = div(
            wrap(_growthRateProportion + DENOMINATOR),               
            wrap(DENOMINATOR)
        );
 
        // Calculate r^n
        UD60x18 rToN = powu(r, _elapsedIntervals);
 
        // Calculate the sum of S_n = a * (r^n - 1) / (r - 1)   
        UD60x18 S_n = div(
            mul(a, sub(rToN, wrap(DENOMINATOR))), 
            sub(r, wrap(DENOMINATOR))
        );
 
        return unwrap(S_n);
    }
}

So, while there is some precision loss by using a direct approximation of the sum of the series, rather than iteratively calculating the sum of the terms of the series, there is a massive gas-savings advantage in utilizing these two fixed-math libraries, and the errors are quite low for all approaches anyway.

I was thinking, wouldn’t it be possible in vanilla Solidity to directly (rather than iteratively) calculate the sum of the series via the formula for $S_n$? And for the above case, it would not be feasible. In this case, no - the $r^n$ term would quickly cause overflows for uint256. The low level magic of the two discussed libraries allows for direct calculations of such formulas, using their custom types for fixed-point numbers.

When to Use Each Approach

Generally, use ABDKMath64x64 or PRBMath, or another library rather than vanilla Solidity (FixedPointMathLib, Fixidity…). They work with lower-level Solidity/assembly to do fixed-point math, usually, much more gas-efficiently, the advantage becoming greater the higher the value of $n$ is.

If in need of signed numbers or high precision, go with ABDKMath64x64, and if working with token amounts as I showed above, I’d probably go with PRBMath, though it does specify it’s not been audited, and is newer than ABDKMath64x64. I say this because I found that the main downside to working with ABDKMath64x64 was having to further scale token amounts so that the final result would fit within $2^{63} - 1 = 9223372036854775807 \approx 9.2e18$. Any result beyond 9.2 tokens would require addition of zeros, and loss of some precision. That being said it could certainly be more precise in other scenarios within the bounds of int64.

Happy mathing, and I hope you make some use of my journaling of learning this myself.