Designing Fixed Point Math in OpenZeppelin Contracts

General
1

Due to popular demand (including @albertocuestacanada, @asselstine and @BrendanChou), we've been exploring the space of fixed-point math libraries to come up with a robust yet flexible design that is appropriate for most use cases. The current plan is to include such a library in the v3.1 release of OpenZeppelin Contracts, a couple weeks from now.

Regarding scope, our initial thoughts are to limit support to add, sub, mul and div. Implementation of functions such as pow, sqrt or log is often heavily dependent on the chosen underlying implementation, and we'd rather get this right first instead of being too ambitious in the feature set. These are great candidates for v3.2 though!

Design Decisions

Our goal is for this library to be as useful to as many users as possible, and here's where we'd like your help in making certain critical design decisions. All feedback is welcome!

For the time being, this is what I'm considering:

  • 256 bit word size
  • Fixed number of 18 decimals
  • Support for signed numbers

Below are in-depth discussions on different aspects of the library, explaining my understanding on each of them and why I think the values above are what makes the most sense. Unsurprisingly, @albertocuestacanada's DecimalMath is very similar - he's quite good at this :slight_smile:

1. Fixed or Programmable Decimals

Fixed-point arithmetic relies on all numbers being multiplied by a large number that represents the value '1' (often called unit). This unit value is what determines how many decimals can be represented, and is critical when converting to and from fixed point, and when performing any operation other than addition and subtraction.

There are two general approaches here: have a single, constant value for unit which applies to all fixed-point numbers in the library, or make its functions parametrized over unit.

A single value makes the library simpler, easier to use, and cheaper in terms of gas, but the choice of unit might not be a one-size-fits-all. Making it parametric would imply higher gas costs not only in execution but also storage (due to the need to store unit), and we'd also have to restrict unit to a range of sensible values. Testing and correctness become harder in this scenario.

Overall, given that the word size of the EVM is so large (256 bits) I think we'll be able to pick a constant unit value good enough for all reasonable use cases. I'd like to hear arguments for the parametric approach however, especially if they come from projects that are already working this way.

2. Decimal or Binary Decimals

The unit value determines the smallest number that can be represented with a fixed-point number. Given this, it'd be natural to use a power of ten, leaving us with clear picture of how many decimal places our numbers have. This is what Ethereum numbers (both ETH itself and most tokens) do: their values are displayed as if they had a unit value of 10^18 (though they are not fixed point!).

Alternatively, we can have unit be a power of two. This has two big benefits:

  • We can use shifts instead of multiplications and divisions, which are cheaper in gas (see note at the end!)
  • The numbers are easier to reason about regarding ranges and overflow protection, making the library simpler/safer

The downside is our numbers will no longer behave like decimal point numbers. For example, if unit = 2^2 = 4, then the smallest number would be 0.25, not 0.1 or 0.01. I'd argue however that this value will be so small that this won't be an issue.

3. Decimals and Word Size

If we go down the fixed unit value route, then we need to choose what this value is, and how much space to allocate for our number and its decimal places.

Regarding total size, I think the only two reasonable options are 256 or 128 bits. The reason why someone would pick 128 are twofold: it removes the need for an intermediate overflow check on mul, and it allows for cheaper storage by packing two 128 bit numbers in a single storage slot. This is the approach followed by ABDK.

The obvious benefit behind 256 bits is a much larger range of representable values. We'd need to perform an additional intermediate overflow check, but the upside is so big this is to me clearly the better choice. I'd love to hear more reasoning behind 128 bits though! @3sGgpQ8H

For a decimal unit, 18 decimal places is a reasonable choice: even if tokens and ETH only use these decimals for display purposes, math is often already done on them as if they were fixed point. For powers of two, 10^18 is about ~2^60, and indeed 2^64 seems to be a popular choice here (again, this is ABDK's chosen value).

4. Sign

Finally, we'd need to decide between signed and unsigned numbers. Given that the whole point behind this is to allow for more sophisticated math, signed seems like a no-brainer.

What We Need From You

In addition to sharing thoughts about the low-level details of the library based on the information above, it'd be super valuable to us if you could share information regarding your usage of fixed-point math, including:

  • why you need it (exchange rates? computing interest?)
  • what you're currently using to solve this (Fixidity? ABDK? did you roll your own?)
  • what you expect to get from the OpenZeppelin Contracts fixed-point library

Thanks a lot to everyone for being a part of this!

6 Likes
2

I have to say that was pleasant to read.

4 Likes
3

I found this list of token decimal breakdown by percentage (https://github.com/ethereum/EIPs/issues/724#issuecomment-333155336). I looked at the original list and it seems like there aren’t any tokens with more than 18 decimals.

Here’s the breakdown if you don’t want to follow the link:

 decimals  Percent of tokens
      0        10% 
      1        0.5% 
      2        3.1% 
      3        1.5% 
      4        1% 
      5        1% 
      6        2.6% 
      7        0.5% 
      8        21% 
      9        3.6% 
      10       0.5% 
      11       0% 
      12       1.5% 
      13       0% 
      14       0% 
      15       0.5% 
      16       1.5% 
      17       0% 
      18       51%
2 Likes
4

I would just note, that token decimals have nothing to do with fixed point math, as all token amounts are actually integers, and decimals property is just a hint for UI regarding how to present token amounts to a user.

3 Likes
5

Good point, thanks for pointing that out! I edited the post to add a few comments about tokens and ETH only being displayed as if they had 18 decimal places.

1 Like
6

Main advantage of using 128-bit words is that we don’t need to handle intermediate numbers wider than 256 bits when implementing scaled multiplication and division. For 256-bit words, intermediate result would not be guaranteed to fit into EVM word, so wider numbers have to be used and operations such as 256-bit * 256-bit = 512-bit, and 512-bit / 256-bit = 256-bit have to be implemented.

2 Likes
7

Thanks for the mention @nventuro! :nerd_face:

sign
I think that support for signed integers is important. We didn’t implement it in DecimalMath and took us a very short time to realize that they are needed often when you start doing math.

If the implementation depends on SafeMath, that might imply extending SafeMath to signed integers as well.

binary vs. decimal
I initially thought that binary would be much more efficient than decimal, and in fact ABDK uses binary and was 10x cheaper in gas terms than Fixidity. However, DecimalMath seems to have similar gas costs to ABDK so I’m not so sure anymore.

If binary might be cheaper, decimal is definitely clearer and easier. I’d suggest doing a gas comparison to see how much better is binary.

decimals and word size
An int128 can hold a range about (-10^38, 10^38). If used to hold currency amounts that use wei than means quantities of up to 10^20 ether. That’s about a hundred quintillion ether, which is way more that should be ever needed. I’m sure that double precision and floating point numbers are used more to have lots of decimal digits than to have lots of integer digits.

So we don’t really need all the digits in an uint256 for fixed point math. If we are going to have 18 decimals and the library is going to have some internal representation of fixed point numbers (like Fixidity), using int128 and ABDK overflow detection method is not a bad option.

fixed or programmable
Programmable decimals are not something that is going to be useful often. If using an internal representation the only use would be to exchange precision for range which is a very advanced feature that I don’t know if anyone would ever use. Another downside of programmable decimals is that using constants is not possible, and constants save you a lot of gas (check ABDK again).

other questions

  • What have I used this for? Exchange rates, token proportions (same thing, really), and compound interest. Always DeFi.
  • What did I use? All of them! :smiley:
  • What do I expect from OpenZeppelin? Ease of use first, gas efficiency second, advanced features third.
3 Likes
8

References to Ether/Wei or token decimals are misleading, as both, ether and token amounts are actually integers when measured in base units, and it is generally accepted best practice to always use integers for money amounts.
Real use cases to be considered for fixed point numbers are: interest rates, compound interest ratios, bonding curve bid/ask prices, exchange rates etc, but not raw money amounts.
There is also a use case when 256-bit integer money amount has to be multiplied by fractional (fixed-point in our case) factor producing 256-bit integer result. This use case should be treated separately from fixed-point math, as it is cross-type math.

4 Likes
9

It is true that it is best practice to use a lossless format for money amounts. That means that using floating point for money amounts is not a good idea. Likewise when using a binary fixed point format as ABDK does, it’s best to be disciplined and not use it for money amounts.

However, if you use an internal representation with a decimal base for fixed point math, as done in Fixidity, there is no information loss and therefore you can store money amounts in fixed point types. A reason to do this is to avoid multiple type conversions and cross-type operations. Those result in complex code when using the library, and a large codebase for the library itself. I don’t see a downside except a potentially higher gas use.

On the rest, I agree. The natural use cases for fixed point math are rates, ratios, prices, etc. The convenience use cases are raw money amounts but that might only be acceptable with a lossless format.

I think I’m leaning towards a decimal representation in this library. A binary representation I think will lead to more complex code, and has more potential for misuse since it shouldn’t be used for money.

2 Likes
10

Also tagging community members for their input:
@MicahZoltu, @hritzdorf, @bakasura980, @glowkeeper

11

Yes please!

I use fixed point maths for exchange rates within Enervator. Originally, I tried rolling my own (from memory, I found division tough), then resorted to using ABDK. However, it’s still not right - I am aware of at least one bug.

…so a working (and very well documented) library would be welcome.

1 Like
12

I’m excited for this.

Usage

We use fixed point libraries to calculate exchange rates and fractions.

Desired Features

  • Signed
  • Cheap gas

Suggestions

Instead of making the question Fixed vs Programmable number of decimal places, why not just create a pure library that allows users to pass the units? That way you can create a lib for the fixed 18 and a separate lib for programmable. Might be worth the little extra call data gas in order to have that flexibility.

Can’t wait to see it!

2 Likes
13

Feedback on Twitter:

14

@asselstine, I noticed that OpenZeppelin already has a SignedSafeMath library, so I extended DecimalMath to support signed operations. I also added user-defined units at the suggestion of one of my devs.

If we don’t find a solution that fits all use cases, maybe it will be useful for you.

2 Likes
15

Looks good! I’ll give it a spin.

2 Likes
16

I would like to see the argument against waiting for, or assisting with the development of, Solidity's built-in fixed point numbers. https://solidity.readthedocs.io/en/latest/types.html#fixed-point-numbers

Fixed point numbers are not fully supported by Solidity yet. They can be declared, but cannot be assigned to or from.

fixed / ufixed : Signed and unsigned fixed point number of various sizes. Keywords ufixedMxN and fixedMxN , where M represents the number of bits taken by the type and N represents how many decimal points are available. M must be divisible by 8 and goes from 8 to 256 bits. N must be between 0 and 80, inclusive. ufixed and fixed are aliases for ufixed128x18 and fixed128x18 , respectively.

IMO having native language support is superior to library support, and since it is already on the roadmap my gut says that it isn't worth the effort to write a library only to have it soon™ replaced by language-level fixed point numbers.

I know engineering resources aren't fungible, but it may be worth asking if we you could spend a similar amount of engineering effort getting fixed point code in Solidity finished rather than engineering a Solidity library?

3 Likes
17

In my understanding, we should separate language support for fixed point numbers into two tiers:

  1. Support for fixed-point data type. This includes type name, storage, calling, and ABI conventions for it and (which is very important) literals syntax.
  2. Support for fixed-point operations. This includes conversions to other type, comparisons, and arithmetic.

The letter tier is less important, as even for integers people often use SafeMath library instead of native operations, and the former tier could be implemented after some library will make certain fixed-point format fe-facto standard.

1 Like
18

I think there has been talk about adding safe math to Solidity natively (e.g., overflow flag and/or error). If the belief is that this is far off (and perhaps even further off for fixedpoint numbers) then a library is probably worth it. Has anyone reached out to the Solidity team to get a feel for their timeline on these things?

1 Like
19

Hi @MicahZoltu,

There is talk of overflow protection for Solidity 0.7

1 Like
20

Thanks everyone for your replies and suggestions! These are extremely useful to us when considering our roadmap.

Division is quite cheap, since the DIV opcode only costs 3 gas. I did some quick tests on Remix and gas cost seems to be dominated by other factors, making both options perform equally well. Given this I'd go with decimals as well.

Remix analysis

Consider the following contract:

pragma solidity ^0.6.0;

contract Math {
    function div(uint256 value, uint256 divisor) public pure returns (uint256) {
        return value / divisor;
    }
    
    function shift(uint256 value, uint256 bits) public pure returns (uint256) {
        return value >> bits;
    }
}

Calling div(500, 32) externally costs 332 gas (including calldata decoding!), and shift(500, 5) costs 338 gas. If you however remove the second argument and make it a constant, shift becomes cheaper by ~30 gas, apparently due to more efficient encoding of the constant in the bytecode.

Absolutely. If the suggestion will be to not store money amounts in fixed point representation, I think it might be very useful to add the following functions:

  • mul(int, fixed) -> int: useful when computing interest, applying exchange rates, etc.
  • div(int, int) -> fixed: useful to compute exchange rates and other ratio-like values

From my talks with them, their current priority is having Yul be an IR for Solidity, which is expected to improve bytecode generation across the board. However, this might not be finished even before the year is out. Additionally, they've decided multiple times not to add native support for features that can be covered by libraries.

Considering this, and the fact that there is alredy demand for such a library, I think the best course of action is to move forward with this proposal. If they end up extending fixed point support in the feature, hopefully usage of this library will help guide that design process.

2 Likes