Fixed Point Arithmetic support

nventuro · March 7, 2019, 6:54pm

We've received multiple requests for a fixed point math library in OpenZeppelin (e.g. here). For those that are not familir with this concept, it basically boils down to scaling an integer so that a certain (fixed) number of decimals are included, e.g. a value of 100 would represent the number 1.00 if using two decimals, and multiplying 100 by 200 would yield 200 (1.00 * 2.00 = 2.00). This is particularly useful when dealing with decimals on systems that have no floating point support, but allow for large integers (e.g. on 32-bit microcontrollers, and especially on the EVM). You can read more about it here.

Given that fixed-point arithmetic is quite a low-level primitive, I don't think we should aim for full-fledged support, since the potential for misuse is quite large due to the unfamiliarity of developers with this concept, and the difficulty of handling different number types without getting them mixed up (e.g. regular integers and custom fixed-point representations).

Because of this, and given that the usefulness of fixed-point support in the context of Ethereum usually comes from a need to calculate fractions of values (like in PaymentSplitter here), I propose implementing a simpler, easier-to-use library, where the only supported operation is calculating a percentage of a number, i.e. answering questions such as 'how much is 75.6% of x?'.

This could be done in a number of ways, e.g. with a function that receives a regular integer and a percentage number (scaled by some factor so that decimals are included - a percentage of 5000 could stand for 50.00%, 5023 for 50.23%, etc.), and returns both the requested fraction and the remainder, which may be useful to avoid leftovers (e.g. if a value is split into three fractions of 33.33%, 0.01% will be left unclaimed) - thanks @frangio for this suggestion!

I'd love to hear everyone's thoughts about this!

IvanTheGreatDev · March 7, 2019, 10:25pm

Hey nventuro!

I agree, a general fixed point math library may have it’s risks, although I’d definitely support some sort of library to support fractions! Like you said there are quite a few ways to go about it but I think that’s something the community would really appreciate

hritzdorf · March 12, 2019, 3:55pm

Hey @nventuro,

thanks so much for bringing it up. We see a lot of rounding-related issues. Therefore, it is a timely issue to discuss.

About your proposal:

I am generally in favor of a limited implementation.
Do you know what the status of this is on the solidity level? Described here. A solidity-level solution might be more desirable.
Your implementation seems to do the following:

function percentageOf(uint x, uint basisPoints) internal returns (uint) {
    return x.mul(basisPoints).div(10000);
}

While it is generally a good approach that might be helpful for developers to know, why would you want to use such an approach in the PaymentSplitter? As you said there might easily be a 0.01% remainder which is considerably larger than the remainder that the current implementation of PaymentSplitter has.

Thanks.

albertocanada · March 13, 2019, 11:23am

Hi @nventuro,

I work for CementDAO and we happen to have implemented a fixed point math library for solidity, with support for basic arithmetic including multiplication and division, as well as logarithms. We have implemented it with full protection for overflows, found the numerical limits for safe operation, and tested all functions extensively (probably more than 100% coverage).

We are planning to release this library as open source when we release CementDAO, but if you would be interested in having a look we would be happy to facilitate that. It would be awesome if we could have your feedback and advice on how to make the library more useful for the community.

Thanks!

frangio · March 13, 2019, 3:48pm

That's cool @albertocanada!

This sounds interesting. Would you mind sharing a few more details?

frangio · March 13, 2019, 3:55pm

To be clear, PaymentSplitter doesn't have a remainder that results from numerical error. The only remainder is that which cannot be split between the shareholders. There's very simple scenarios where this happens: if you and me are splitting payments 50-50, and we receive 3 wei, there is 1 wei that we can't split, so it will stay in the contract. It's always very few wei that will remain. Even then, it's possible to "top up" the contract balance so that it is fully emptied.

This is how percentages should be always done IMO, and we should try to give tools for people to replicate that in their contracts. I'm not sure how much this approach can be generalized, though.

Because of that, my main interest in this thread is collecting examples where percentages and/or fixed point were needed, to evaluate how different possible libraries would help.

albertocanada · March 13, 2019, 4:02pm

With each arithmetical operation we made sure it throws on overflow.

Additionally to that we calculated what are the bounds within which an arithmetical operation won’t overflow. For example we know that add will overflow (and throw) if the result is greater than 2**255-1 (we are using int256). From this we can assert that all add operations where both operands are smaller than (2**255-1)/2 will never throw.

We implemented those limits because sometimes you might not want to wait to see if an operation throws and instead stop the user at the frontend when it’s going towards a risky situation so that you have a more predictable experience.

hritzdorf · March 13, 2019, 6:45pm

Thanks. I agree. Sorry for my misunderstandable post. PaymentSharer is indeed a good example.

The medium post below might be a good example. We have seen a number of implementations based on this post:

nventuro · March 13, 2019, 8:02pm

I haven't been following development closely, but seriously doubt this is a pressing concern for them, considering they're working on much more generally useful features.

BrendanChou · March 14, 2019, 12:19am

This would be useful for many projects yes. Rather than using basis points (4 decimal places) using 18 decimal places seems to be the standard for many protocols including Maker and dYdX

albertocanada · March 14, 2019, 11:57am

There are a number of approaches with regards to how many decimal places. If you are going to do arithmetic with currencies then using as many decimal points as your fractional monetary unit makes sense. That would be 2 decimals for dollars, 18 decimals for bitcoin.

If you are going to do more complex arithmetic (we had to do logarithm curves) then the more decimals you use the more precision you get for iterative methods (log, exp, sqrt). Our initial setup was for 36 decimals to get a really good approximation of the curves.

We only included limited support for operating on fixed point numbers of different decimals, because we didn’t need more, but it would be relatively easy to pack an uint8 denoting the decimals used into a Struct that represents the fixed point value. That way a fixed point library would be flexible enough for applications needing any number of decimals.

3sGgpQ8H · April 9, 2019, 9:15pm

We just released Solidity library for signed 64.64-bit fixed point math, i.e. for binary rather than decimal fixed point: https://github.com/abdk-consulting/abdk-libraries-solidity
It has basic arithmetic, exponentiation, logarithm, square root, etc.

bakasura980 · April 19, 2019, 1:50pm

Hey,
My team in LimeChain had to implement sqrt/power/ln functions in order to run the Bonding Curve concept.
The problem with these functions in solidity is actually the missing double type (The big pain ) That is why we gave a chance to Vyper.

And here are the results:

SQRT Function:

Vyper already has an integrated sqrt function thanks to @Perseverance(Github name) -> returns up to 10 digits fraction
If you want to have more accurate result in terms of fraction a.k.a more than 10 digits accuracy, you can check: https://github.com/LimeChain/bonding_mathematics/blob/master/contracts/Math/SQRT_HFP.py

Example:
sqrt(2) => 14142135623
sqrt_hfp(2, 18) -> 1414213562373095048

LN Function: (Natural logarithm)
You can calculate ln of a number with high precision (up to 10 digits fraction)
The code:

github.com

andytudhope/Recollections/blob/master/vyper/math/math.vy

# In order to precisely calculate ln we are using Arithmetic–geometric mean approach
# The formula:
#   ln(x) = pi / 2 * M(1, 4/s) - m * ln(2) where M denotes the arithmetic-geometric mean of 1 and 4/s, and s = x * 2^m
# ...
# We have chosen m = 19 => 2^19 = 524288 and 19 * ln(2) = 1316979643063896087892741


@public
@constant
def big_ln(x: decimal) -> decimal:

    pi: decimal = 31415926535897932384626433832795028.0
    a: decimal = 100000000000000000000.0
    # Here we are using (max(1.0 / x, x) because:
    # if x < 1 => ln(0.1) = -ln(1/0.1) = -ln(10)
    g: decimal = 400000000000000000000.0 / (max(1.0 / x, x) * 524288.0)

    for i in range(9):
        temp: decimal = a
        a = (a + g) / 2.0

This file has been truncated. show original

POWER Function:
You can power a number with high precision (up to 10 digits fraction)

The limits:
Let’s say we have x^y where x is the Number and y is the Exponent

The biggest Number is 9999999999999.9999999999 with an approximation of 9999999970066.393832446 (the real result is: 9999999970066.393835878 )
9999999999999.9999999999 ^ 0.9999999999 = 9999999970066.393832446 (the real result is: 9999999970066.393835878 )
Exponent should be in range: [ 0 < Exponent < 1 ]
Gas cost => approximately 367806 gas = 0.30527 USD

Hint: If you want to power a number with exponent > 1 you can do:

2.13 ^ 9.82 = 2.13 ^ 9 * exp(2.13 ^ 0.82)

Keep in mind that 2.13 ^ 9 gives inaccurate result due to Vyper decimal size limit (Underflow)

The code:

github.com

andytudhope/Recollections/blob/master/vyper/math/math.vy

# In order to precisely calculate ln we are using Arithmetic–geometric mean approach
# The formula:
#   ln(x) = pi / 2 * M(1, 4/s) - m * ln(2) where M denotes the arithmetic-geometric mean of 1 and 4/s, and s = x * 2^m
# ...
# We have chosen m = 19 => 2^19 = 524288 and 19 * ln(2) = 1316979643063896087892741


@public
@constant
def big_ln(x: decimal) -> decimal:

    pi: decimal = 31415926535897932384626433832795028.0
    a: decimal = 100000000000000000000.0
    # Here we are using (max(1.0 / x, x) because:
    # if x < 1 => ln(0.1) = -ln(1/0.1) = -ln(10)
    g: decimal = 400000000000000000000.0 / (max(1.0 / x, x) * 524288.0)

    for i in range(9):
        temp: decimal = a
        a = (a + g) / 2.0

This file has been truncated. show original

And finally… here is a code snippet of how to run vyper functions from solidity contract:

contract TestingVyperLN {
    
    uint256 public result;

    function calcLN(address vyperMath, uint256 number) public {
        
        address vyperContract = vyperMath;
        
        (bool success, bytes  memory data) = vyperContract.call(abi.encodeWithSignature("ln(uin256)", number));
        require(success);
        
        // Convertion from bytes to uint
        uint lnResult;
        assembly {
            lnResult := mload(add(data, add(0x20, 0)))
        }
        
        result = lnResult;
    }
}

3sGgpQ8H · April 27, 2019, 5:58pm

Library I mentioned in my previous comment is able to calculate sqrt, x^y, and ln x in Solidity with 64-bit precision (about 18 decimals) and uses less gas:

sqrt: less then 2K gas
2^x: less than 2K gas
log2 x: about 10K gas
ln x: about 10K gas

x^y is calculated as 2^(y * log2 x) and thus consumes about 12K gas.

asselstine · January 11, 2020, 12:37am

Nice library!

I’m trying it out ABDKMathQuad and it’s the first fixed point lib to calculate what I need correctly.

The Github repo is such a mystery though- where are the tests?

3sGgpQ8H · January 11, 2020, 7:13am

Strictly speaking, ABDKMathQuad is a floating point library rather than fixed point. Anyway, glad to know that you found the library helpful.

The library is being developed by ABDK Consulting using proprietary methodology and tools, those ABDK uses for all its projects, and only the final result is published on GitHub. Tests will not be useful without the tools needed to run them, thus tests are not published.

albertocuestacanada · January 30, 2020, 10:38am

Hi @3sGgpQ8H

Great job with ABDKMath. I created an earlier alternative but your library was so much better that I didn’t continue development.

I’ve recommended using ABDKMath several times, and my clients have always rejected it on the basis of the non-standard license. Have you considered releasing it under MIT or Apache?

albertocuestacanada · February 24, 2020, 10:15pm

Hi all.

I coded a minimal library for fixed point math arithmetic, focused on token operations.

This should be enough for most developers out there. Most people in DeFi just want to calculate simple proportions of token amounts. If you need logarithms and things like that there are other options above.

Since I realized that everyone is used to ether and wei (which is a fixed point representation of its own) I made the library consistent with that, so it is harder to misuse.

The whole thing is about 50 lines, there can’t be many bugs in there. It uses SafeMath for overflow, so in a way it is a nice extension of it.

I’d love to hear what you think of it.

asselstine · March 5, 2020, 8:25pm

Nice to see the library uses 18 places rather than 24

albertocuestacanada · March 5, 2020, 8:53pm

For simple things works great

Topic		Replies	Views
Designing Fixed Point Math in OpenZeppelin Contracts General	30	11054	May 15, 2021
Best practice for handling percentages Support	1	1835	March 30, 2020
Best practice for fix point math and decimal conversion Security design	2	2983	July 27, 2020
Will there be an OpenZeppelin Contracts implementation of exponentiation by squaring algorithm? General	3	1630	March 20, 2020
I develped a perspective 3D graphic rendering algorithm fully in solidity, Maybe the first Showcase solidity	12	850	May 15, 2023

Fixed Point Arithmetic support

Related topics