It always seems impossible until it’s done. — Nelson Mandela

Introduction

Any financial application with a minimum of complexity will need some decimal support and multiplications to calculate things like interest. In the case of CementDAO we needed logarithms to implement the transaction fee curve that steers its cryptocurrency basket towards the desired configuration.

Solidity supports integers but no decimals, so we coded a fixed point arithmetic contract, made it safe against overflow, and tested it extensively. It underpins the CementDAO deployment in Ropsten.

The Fixidity contract is available from the CementDAO github with a MIT license, please feel free to use it and build upon it.

Implementation

In order to code this we went from the simplest to the most complexarithmetic functions, implementing overflow assertions, mathematically finding the limits of the functions and testing for any special cases like zero, one, n, n plus one, limit minus one, limit and limit plus one. Higher order functions were implemented to reuse lower order ones.

Digits

The maximum representable integer in 256 bits has 76 digits, and we arbitrarily decided to allocate 24 digits to the decimal part and the other 52 to the integer part. We considered that to be a fair choice in terms of capabilities, as it allows multiplication of larger numbers in exchange of precision loss of very small fractional parts. Changing the number of decimals is possible just by recalculating the constants in the contract.

Conversion

If you would have a decimal number or a float and would like to convert it to a fixed point representation you would displace the comma to the right a fixed number of positions, or “digits”. As a mathematical operation this is newFixed(x) = x * 10**digits. When you do this with a decimal number you have to discard any remaining decimals after the conversion, but since we are working with Solidity (which doesn’t have decimals) this isn’t an issue for us.

To convert back from fixed point you do the inverse operation, fromFixed(x) = x / 10**digits, being mindful that very small fixed point numbers would get rounded off to zero.

The contract offers a few useful functions to convert between different fixed point representations, for example from 24 to 18 digits.

Overflow in Conversion

Conversion to fixed point will overflow if the number being converted has more integer digits that fit in the bits reserved for them in the fixed point representation. If max_int256 == 2**255–1, then max_newFixed = max_int256 / 10**digits.

Likewise if min_int256 == (-1)*2**255, min_newFixed = min_int256 / 10**digits. Note that there is one more negative number than positive numbers in the int256.

In FixidityLib the conversion functions will revert if you try to convert a number above those limits, but you should implement your own safeguards in your contracts to warn users early enough that they are dealing in numbers too large for the contract.

function newFixed(int256 x)
        public
        pure
        returns (int256)
    {
        assert(x <= max_newFixed());
        assert(x >= min_newFixed());
        return x * fixed_1();
    }

A number that will come useful in many cases is fixed_1, the fixed point representation of 1, which can be expressed as fixed_1 = 10**digits. As you can see, converting to and from fixed point representation is the same as multiplying and dividing by fixed_1.

To extract the integer and decimal parts of a fixed point number you can use the same shortcut. Integer(x) = (x/fixed_1)*fixed_1 — Please be aware that integer(x) returns the integer part of x but still in fixed point representation, so it is the same as replacing all decimal digits with zeros. To retrieve just the decimal part we can use Fractional(x) = x % fixed_1.

function integer(int256 x) public pure returns (int256) {
        return (x / fixed_1()) * fixed_1(); // Can't overflow
    }
    function fractional(int256 x) public pure returns (int256) {
        return x - (x / fixed_1()) * fixed_1(); // Can't overflow
    }

Using a struct instead of int256

One of the earliest pieces of feedback we got is that using a struct for our fixed point values instead of int256 would be much safer, and we agree. Such a struct would be something like:

Struct Fixed {
        int256 value;
        uint8 digits; // Inefficient, but possibly necessary
    }

Using a struct would help any application using the Fixidity library to make much more robust applications, it is certainly confusing that an int256 can be both a normal integer or a fixed point number, with no way of knowing which except by analysing the program flow. However, we haven’t yet coded it, as adding the struct to the Fixidity library would create a bit of internal complexity, and we can manage for our specific use case. We welcome contributions in this aspect as in any other. Regardless, we may make this change the next time we implement anything with fixed point arithmetic.

Addition and subtraction

Addition operations between fixed point numbers are identical to normal integers and no additional care is required to keep track of integer and decimal parts. The only tricky bit is that they can overflow and that max_int + 1 == min_int. Addition of negative numbers means that you need to be careful of overflowing from the lower end as well.

The usual overflow protection mechanism is x + y = z; assert(z — y = x), but that doesn’t work in the complement to two representation of solidity, and gave me a bit of a headache.

At the end you can protect yourself against overflow with a bit of logic:

Only the addition of two positives can overflow through the top.
Only the addition of two negatives can overflow through the bottom.
The addition of a negative and a positive can never overflow.
The addition of a negative or a positive to zero can never overflow.
The addition of two positives cannot overflow by an amount greater than abs(min_int).
The addition of two different negatives cannot overflow by an amount greater than abs(max_int).
If an overflow occurs the result will be zero or have the opposite sign to what would be expected.

With these rules we just need to assert as follows:

function add(int256 x, int256 y) public pure returns (int256) {
        int256 z = x + y;
        if(x > 0 && y > 0) assert(z > x && z > y);
        if(x < 0 && y < 0) assert(z < x && z < y);
        return t;
    }
function subtract(int256 x, int256 y) public pure returns (int256) {
        return add(x,-y);
    }

Multiplication and Division

The multiplication operation is conditioned by the fact that a number in fixed point representation is actually the following combination:

fixed(x) = numbers_to_left_of_comma(x)*10**digits() + numbers_to_right_of_comma(x)

In the following formulas, this is written as x = x1*fixed1 + x2.

When multiplying two fixed point numbers though we need to be conscious that the comma needs to stay in the right spot and if we simply multiply the numbers we will get the wrong result and be very likely to overflow at the same time:

x = x1*fixed_1 + x2
y = y1*fixed_1 + y2
x * y = (x1*fixed_1 + x2) * (y1*fixed_1 + y2)
x * y = ((x1*fixed_1) * (y1*fixed_1)) + ((x1*fixed_1) * (y2)) + ((y1*fixed_1 * x2)) + (x2 + y2)

To keep the comma in the right place the first term of the decomposition needs to be swapped from (x1*fixed_1) * (y1*fixed_1) to (x1*y1)*fixed_1, which at the same time makes overflows less likely.

We still need to test for overflow. This is because x1*y1 will be greater than max_int if, for example, both x1 and y1 are greater than sqrt(max_int). We are also multiplying the result by fixed_1 which presents another chance for overflow.

For the multiplication case the traditional overflow check works:

x * y = z; assert(z / y = x)

Which leaves the solidity code as:

int256 x1 = integer(x) / fixed_1();
        int256 x2 = fractional(x);
        int256 y1 = integer(y) / fixed_1();
        int256 y2 = fractional(y);
 
        int256 x1y1 = x1 * y1;
        if (x1 != 0) assert(x1y1 / x1 == y1);
      
        int256 fixed_x1y1 = x1y1 * fixed_1();
        if (x1y1 != 0) assert(fixed_x1y1 / x1y1 == fixed_1());
        x1y1 = fixed_x1y1;

The rest of the terms of the multiplication don’t need adjustment for the comma, but we still need to check for overflow at each internal multiplication or addition operations, since all of them can overflow.

function multiply(int256 x, int256 y) public pure returns (int256) {
    if(x == 0 || y == 0) return 0;
    if(y == fixed_1()) return x;
    if(x == fixed_1()) return y;
    // Separate into integer and fractional parts
    // x = x1 + x2, y = y1 + y2
    int256 x1 = integer(a) / fixed_1();
    int256 x2 = fractional(a);
    int256 y1 = integer(b) / fixed_1();
    int256 y2 = fractional(b);
    // (x1+x2) * (y1+y2) = (x1*y1) + (x1*y2) + (x2*y1) + (x2*y2)
    int256 x1y1 = x1 * y1;
    if (x1 != 0) assert(x1y1 / x1 == y1); // Overflow x1y1
    // x1y1 needs to be multiplied back by fixed_1
    int256 fixed_x1y1 = x1y1 * fixed_1();
    if (x1y1 != 0) assert(fixed_x1y1 / x1y1 == fixed_1());
    x1y1 = fixed_x1y1;
    int256 x2y1 = x2 * y1;
    if (x2 != 0) assert(x2y1 / x2 == y1); // Overflow x2y1
    int256 x1y2 = x1 * y2;
    if (x1 != 0) assert(x1y2 / x1 == y2); // Overflow x1y2
    x2 = x2 / mul_precision();
    y2 = y2 / mul_precision();
    int256 x2y2 = x2 * y2;
    if (x2 != 0) assert(x2y2 / x2 == y2); // Overflow x2y2
    // result = fixed_1()*x1*y1 + x1*y2 + x2*y1 + x2*y2/fixed_1();
    int256 result = x1y1;
    result = add(result, x2y1); // Add checks for overflow
    result = add(result, x1y2); // Add checks for overflow
    result = add(result, x2y2); // Add checks for overflow
    return result;
}

Once the multiplication operation is ready, we can just code the division as x / y = x * (1/y); knowing that 1/y > y and therefore can’t overflow. We still need to keep the comma in the right place, though:

function reciprocal(int256 x) public pure returns (int256) {
        assert(x != 0);
        return (fixed_1()*fixed_1()) / x; // Can't overflow
    }

We introduced an assert to stop divisions by numbers above fixed_1()*fixed_1() as that would make reciprocal(x) = 0 and revert the division.

function divide(int256 x, int256 y) public pure returns (int256) {
        if(y == fixed_1()) return x;
        assert(y != 0);
        assert(y <= max_fixed_divisor());
        return multiply(x, reciprocal(y));
    }

How did we test it?

Correct testing was the most important part of this implementation. Most of our initial function assumptions and implementations were wrong and we only discovered this through testing. It is notoriously difficult to carry in your mind all the rules about managing the comma, and even harder to understand when and how operations overflow. In total, tests produced three times as much code as the library itself.

When implementing tests our policy was to write a test for each assert, a test for the assumed limits just before a function overflows, and another test to verify behaviour on overflow. We thought that writing clear constants for safe operation was critical, and in a way these tests were all about the safe operation limits. A good example are the tests for the add function:

/**
 * @dev a+b. If any operator is higher than max_fixed_add() it
 * might overflow.
 * In solidity max_int256 + 1 = min_int256 and viceversa.
 * Test add(max_fixed_add(),max_fixed_add()) returns max_int256()-1
 * Test add(max_fixed_add()+1,max_fixed_add()+1) fails
 * Test add(-max_fixed_sub(),-max_fixed_sub()) returns min_int256()
 * Test add(-max_fixed_sub()-1,-max_fixed_sub()-1) fails
 * Test add(max_int256(),max_int256()) fails
 * Test add(min_int256(),min_int256()) fails
 */

For the multiply function we had code additional tests, because an overflow can happen in each one of the internal operations so we needed to debug all the combinations of integer and fractional versus the other integer and fractional. See below, this one was a bastard.

/**
 * @dev a*b. If any of the operators is higher than   
 * max_fixed_mul() it might overflow.
 * Test multiply(0,0) returns 0
 * Test multiply(max_fixed_mul(),0) returns 0
 * Test multiply(0,max_fixed_mul()) returns 0
 * Test multiply(max_fixed_mul(),fixed_1()) returns max_fixed_mul()
 * Test multiply(fixed_1(),max_fixed_mul()) returns max_fixed_mul()
 * Test combinations of (2,-2), (2,2.5), (2,-2.5) and (0.5, -0.5)
 * Test multiply(
 *   fixed_1()/mul_precision(),
 *   fixed_1()*mul_precision()
 * )
 * Test multiply(max_fixed_mul()-1,max_fixed_mul()) 
 *   equals multiply(max_fixed_mul(),max_fixed_mul()-1)
 * Test multiply(max_fixed_mul(),max_fixed_mul()) 
 *   returns max_int256()
 * Test multiply(max_fixed_mul()+1,max_fixed_mul()) fails
 * Test multiply(max_fixed_mul(),max_fixed_mul()+1) fails
 */

Conclusion

We didn’t know how difficult would it be, so we did it. And we had so much fun doing so.

Now we have a contract that we can use and trust to code financial applications in Solidity, and we are proud and confident enough to release it to the public, knowing that others will find it useful as well.

Please feel free to provide any feedback about this library, I’m sure there must still be some bug or edge case hidden somewhere where we couldn’t find it.

CementDAO is now live on Ropsten, so join in and take Fixidity for a spin!

Thanks

To Gadi Guy for coding the initial library at https://github.com/extraterrestrial-tech/fixidity

To the CementDAO Team: Brendan Quinn (1A1Z), Edan Yago (1A1Z), David Carvalhão (Vigil365), Pierre Martin (Vigil365), Bernardo Vieira(TechHQ), and Sergio Pereira (TechHQ).

Hackernoon Archive April 22nd, 2019

Bitcoin Bear Market Diaries Volume 19 Max Keiser

@piratebeachbumPirate Beachbum

Fixed point math in Solidity

@albertocuestacanadaAlberto Cuesta Cañada

Startups: Pulse Surveys are Dumb.

@i_am_brennanBrennan McEachran