OneSwap Series 3 - Arithmetic Operations in Solidity

Arithmetic Operations in Solidity

Different from well-known virtual machines in the industry, such as JVM and WebAssembly, EVM does not support the basic data types commonly applied in programming languages, for example, int, long, char, float, and double, but only one basic data type, the 256-bit-long integer. Such a design makes sense to some extent, for example:

1. The output of the hash function is generally 256 bits
2. 256-bit-long integers are used in the calculation of the elliptic curve
3. 256-bit-long integers can be used to implement rational numbers. In most scenarios, it can replace floating-point numbers and avoid the platform dependency of floating-point calculations.
4. EVM is a VM for interpretation and execution. The interpretation costs are more than the integer calculation. Calculation using 256-bit integers may not be much slower than that with 64-bit integers.

But in this case, it is necessary to design a special programming language (such as Solidity and Vyper) for the EVM, which brings everyone a workload of learning and understanding. Let's first learn what basic data types Solidity provides.

Integer Types in Solidity

Solidity supports signed integers and unsigned integers with a length of 8*N (1<=N<=32). The type name is int or uint followed by the length, such as int8, int16, int64, int112, int256, uint32, uint128, and uint256. If with no length followed by int and uint, the length is 256 by default.

How does Solidity implement shorter integers such as int8, int16, int64, int112, uint32, and uint128 with byte codes? It is very simple: in the memory and the stack, these shorter integers occupy the same space as a 256-bit integer, without saving any space; after completing a calculation, just use the "AND" operation to clear the useless bits in high digits.

In a word, short integers do not save memory or stack space; on the contrary, they require more steps in the calculation. Therefore, we should avoid using short integers as much as possible—with one exception: when using Storage, we should apply short integers to save space. We will introduce how to save storage space in another article in this series.

The integer operations supported by Solidity, the corresponding operators, and their gas consumption are shown in the following table:

Operation category	Operator	Gas
Add and subtract	+,-	3
Comparison	==, !=, >, <, >=, <=	3
Bit field calculation	&, \	,!, ^, >>, <<	3
Multiplication and division and modulo	*, /,%	5
Power	**	10+50*(the number of bytes of the result)

Integer Overflow and SafeMath

As we know, when integers are represented in two's complement, the following overflow problems will occur:

1. Add two integers a and b of length N. The result needs to be represented in N+1 binary digits. If the result is forcibly truncated to N digits, it may be smaller than both a and b
2. Subtract one of the positive integers a and b of length N from the other, and the result may be negative. If the result is interpreted as a positive integer forcibly, then it may be a number larger than both a and b
3. Multiply two positive integers a and b of length N together, and the result may require 2*N binary bits to accommodate

When Solidity performs arithmetic calculations on integers of various lengths, the result data produced is the same as the input data in length, making overflow possible in certain scenarios. Overflows often lead to serious program errors. For example, BEC suffered billions of losses in market value due to a [multiplication overflow error](https://medium.com/@peckshield/alert-new-batchoverflow-bug-in-multiple-erc20-smart-contracts-cve-2018- 10299-511067db6536). To terminate the operation of the program when an error occurs, many projects choose the SafeMath library, including the Oneswap project:

import "./libraries/SafeMath256.sol";

abstract contract OneSwapERC20 is IOneSwapERC20 {
    using SafeMath256 for uint;
...

The SafeMath256 library is imported here and applied to the 256-bit unsigned integer type uint. This library is only applicable to 256-bit unsigned integers. If you need SafeMath libraries of other lengths, please consider the following questions:

1. Is this necessary? As shorter integers will consume more Gas in the calculation, the best choice is to explicitly convert the short integers to 256-bit integers, and then explicitly convert them back after the calculation.
2. If you have to do this, you can refer to this article

SafeMath256 and similar libraries follow some simple rules, including:

1. If the sum of addition is larger than any one of the addends, there is no overflow
2. The minus should be less than or equal to the minuend
3. The quotient of the multiplication, divided by the multiplicand, should be equal to the multiplier
4. The denominator of division and modulo operation cannot be zero

If the input parameter violates these rules, the function in SafeMath256 will revert.

The using SafeMath256 for uint in the above code enables uint type data in the current contract to call functions in SafeMath256 with an object-oriented syntax. For example:

    uint  public override totalSupply;
    mapping(address => uint) public override balanceOf;
    function _mint(address to, uint value) internal {
        totalSupply = totalSupply.add(value);
        balanceOf[to] = balanceOf[to].add(value);
        emit Transfer(address(0), to, value);
    }

The totalSupply.add(value) is actually equivalent to SafeMath256.add(totalSupply, value). The syntactic sugar provided by solidity allows us to write more concise code.

With SafeMath, the code is more secure, but in order to check the rules, you will pay more Gas, and the EVM bytecode will swell further. Therefore, during a series of continuous calculations, if the input data has only a limited number of digits for sure, we can carefully analyze whether arithmetic overflow occurs in each calculation step to determine where ordinary Solidity operators can be applied soundly. Such a technique is widely used in OneSwap, for example:

        uint stockAmount;
        if(isBuy) {
            uint a = ctx.remainAmount/*112bits*/ * priceInBook.denominator/*76+64bits*/;
            uint b = priceInBook.numerator/*54+64bits*/ * ctx.stockUnit/*64bits*/;
            stockAmount = a/b;
        } else {
            stockAmount = ctx.remainAmount/ctx.stockUnit;
        }
        if(uint(orderInBook.amount) < stockAmount) {
            stockAmount = uint(orderInBook.amount);
        }
        require(stockAmount < (1<<42), "OneSwap: STOCK_TOO_LARGE");
        uint stockTrans = stockAmount/*42bits*/ * ctx.stockUnit/*64bits*/;
        uint moneyTrans = stockTrans * priceInBook.numerator/*54+64bits*/ / priceInBook.denominator/*76+64bits*/;

Here we use native multiplication and division operators, not the SafeMath library. The comments in the code indicate the maximum possible length of the data. According to the analysis, the multiplication overflow will not occur when the length is the maximum. There is only one require statement here, which checks the length of the effective digits of stockAmount. After checking, you can safely assume that its length does not exceed 42. If SafeMath is used, each multiplication and division sign will bring a require statement, and the gas consumption will increase significantly.

Thinking in Rational

EVM and Solidity do not support floating point numbers, which does bring some inconvenience. The floating-point number is a special kind of rational numbers, and its denominator must be an integer power of two. Rational numbers can do the same job as floating-point numbers. A rational number consists of an integer numerator and an integer denominator, which means that it occupies two integers's space.

OneSwap trading pairs return three prices when querying prices: the price of selling one, the price of buying one, and the price of the AMM pool. Each price is represented by a numerator and a denominator, and that involves a total of 6 integers, as shown below:

    function getPrices() external override returns (
        uint firstSellPriceNumerator,
        uint firstSellPriceDenominator,
        uint firstBuyPriceNumerator,
        uint firstBuyPriceDenominator,
        uint poolPriceNumerator,
        uint poolPriceDenominator)

OneSwap uses a 32-bit decimal floating-point number as the compressed representation of the price. When it is "decompressed", it forms a rational price, which is represented by the following structure:

// A price presented as a rational number
struct RatPrice {
    uint numerator;   // at most 54bits
    uint denominator; // at most 76bits
}

When calculating the rate, OneSwap uses BPS (Base Points) to indicate the rate, the value of which will be calculated as: variable feeBPS recorded in OneSwapFactory divided by 10,000. For example, feeBPS=50, then the fee rate is 50/10000=0.5%.

When using rational numbers, pay special attention to the significant digits. When OneSwap calculates the amount of Token exchange with the AMM fund pool, it needs to calculate: reserveStock*(sqrt(numerator/denominator)-1), where numerator/denominator is a rational number slightly greater than 1. With floating-point numbers, this expression can be directly calculated, because the sqrt of floating-point numbers can return a floating-point number slightly larger than 1 as input. But in Solidity, if you directly calculate according to this expression, the result of numerator/denominator will be 1, and the final result will be 0, which is unacceptable.

To ensure that there are enough significant digits, we adjust the expression to: reserveStock*(sqrt(numerator*2**64/denominator)-1)/2**32, and the corresponding code is as follows:

        numerator = numerator * (1<<64);
        uint quotient = numerator / denominator;
        uint root = Math.sqrt(quotient); //root is at most 110bits
        uint diff =  root - (1<<32);  //at most 110bits
        result = reserveStock * diff;
        result /= (1<<32);

The quotient here will be a number greater than 2**64, and the root of the square root will be greater than 2**32. There are enough digits to ensure the accuracy of the final result.

Rounding

In C language, we use the floor function to round-down floating-point numbers, the ceil function to round-up, and the round function for rounding-off. Solidity does not support floating-point numbers. How can we achieve similar effects? When performing integer division, the remaining part will be discarded, which is equivalent to rounding down. Therefore, when we need to round down, just use the native division operator.

Rounding up can be achieved with the following techniques:

        uint fee = (amountToTaker * feeBPS + 9999) / 10000;

In OneSwap, this line of statements is applied to calculate the transaction fee. amountToTaker is the token that Taker is supposed to get. By multiplying it and feeBPS, we can get the transaction fee that should be deducted. As we mentioned earlier, the transaction fee rate is actually a rational number: feeBPS/10,000. How to round up the result of multiplying it and a rational number? Just add "denominator minus one" to the numerator, and then perform normal division.

With a similar principle we can round the rational number a/b: (a+b/2)/b.

When designing smart contracts, we would rather profit at other's expense than being taken advantage of in terms of rounding. According to this principle, we should round down numbers if it helps; if not, we should round up; rounding is rarely used as it cannot tell who will be benefited.

ERC20 Tokens on Ethereum often use 18 decimal digits of precision. In this case, the rounding error can bring me negligible benefits of no more than 10^-18 tokens. So it is not that unfair to others.

Gradual Accuracy Loss

We mentioned earlier that when OneSwap calculates the amount of Token exchange with the AMM fund pool, it needs to calculate the square root. To ensure accuracy, first we need to multiply the numerator by 2**64. However, this multiplication may cause arithmetic overflow!

Is it possible to use the overflow-proof multiplication function in SafeMath256? Although this can ensure that the program will not make mistakes in arithmetic calculations, it also refuses to provide services for users under some normal circumstances, rudely rolling back transactions yet costing Gas without yielding the expected results.

We cannot assert that in most cases the numerator must be less than 2**192. We are not sure that all situations that cause overflow after the numerator is multiplied by 2**64, are caused by malicious attackers. So we need to work out a way to make sure the square root can be calculated normally even if the numerator is greater than or equal to 2**192, even at the cost of precision..

If the numerator and denominator are divided by the N power of 2 in the meantime, the value of the rational number remains unchanged. If in the binary representation of the numerator and denominator, the lowest N bits are all zeros, we can safely shift the numerator and denominator to the right by N bits. If the lowest N bits are not zero but we also shift the numerator and denominator to the right at the same time, it will cause a loss of precision. Fortunately, such loss will be negligible. The following is an example with Python. We can see that whether the lowest 36 bits are zero or not has little effect on the final result.

>>> 0xfedcba9876543210987654321*(1<<64)/0x123456789abcdef0123456789
258254417031933725993L
>>> 0xfedcba9876543210000000000*(1<<64)/0x123456789abcdef0000000000
258254417031933725999L

Based on this observation, we can tentatively shift the numerator and denominator to the right at the same time until the numerator is small enough that there will be no overflow after it is multiplied by 2**64. The code of OneSwap is like below:

        while(numerator >= (1<<192)) {
            numerator >>= 16;
            denominator >>= 16;
        }
        require(denominator != 0, "OneSwapPair: DIV_BY_ZERO");
        numerator = numerator * (1<<64);

There is still a require statement, but it will only roll back the transaction when the numerator and denominator differ by more than 2**128 times, which is almost impossible. Now we can be sure that for most cases, this code can be executed normally, while under some special circumstances, it will harm precision a little bit.

Table Lookup

As we mentioned earlier, the gas consumption of the power is "10+50*(the number of bytes of the result)", which is relatively large. Taking the common ERC20 token accuracy of 18 as an example, the result of 10**18 needs to be represented by 8 bytes, so the gas consumption of the expression 10**18 is 10+50*8=410 , equivalent to hundreds of ordinary arithmetic operations.

When the exponent of the power is not that large, you can use the table lookup method to calculate the power. For example, OneSwap uses the following two functions to help calculate the power operation during the "decompression" of 32-bit decimal floating-point numbers:

    // 10 ** (i + 1)
    function powSmall(uint32 i) internal pure returns (uint) {
        uint x = 2695994666777834996822029817977685892750687677375768584125520488993233305610;
        return (x >> (32*i)) & ((1<<32)-1);
    }

    // 10 ** (i * 8)
    function powBig(uint32 i) internal pure returns (uint) {
        uint y = 3402823669209384634633746076162356521930955161600000001;
        return (y >> (64*i)) & ((1<<64)-1);
    }

The 256-bit integer x in the above code is composed of eight 32-bit integers, and powSmall selects the i-th 32-bit integer; and y is composed of four 64-bit integers, from which powBig selects the i-th 64-bit integer. With x and y calculated in advance, it can be guaranteed that powSmall(i)==10 ** (i + 1), and powBig(i)==10 ** (i * 8).

Taylor Expansion

Solidity does not directly support square root operations. The sqrt function in the Math library used by Uniswap and OneSwap uses Babylonian Algorithm to accurately calculate the square root. The Babylonian algorithm is a special case of Newton's iterative method used for square rooting. It requires a lot of loop iterations to get an accurate result. Therefore, it consumes much Gas, often more than 4,000 Gas.

Considering that the rational number numerator/denominator, which is rooted here, is a value slightly greater than 1, we are sure that it is less than 1.25 most of the time. So here we can use Taylor expansion to speed up the calculation. We just expand to the third term, which can yield good enough accuracy. After expanding the square root function to the third term around 1.0, we get:

$$\sqrt{1+\tau}-1 = \frac{1}{2}\tau - \frac{1}{8}\tau^2 + \frac{1}{16}\tau^3$$

Expressing $\tau$ in the above formula as a rational number x/(2**64), we get the following code:

            numerator = numerator * (1<<64);
            uint quotient = numerator / denominator;
            uint x = quotient - (1<<64);
            uint y = x*x;
            y = x/2 - y/(8*(1<<64)) + y*x/(16*(1<<128));
            result = reserveStock * y;
            result /= (1<<64);

This code completes the calculation of reserveStock*(sqrt(numerator/denominator)-1) with much less Gas.

What if the range of possible values ​​of rational number numerator/denominator is relatively large in the application, say, in the interval [1,10]? At this time, we can divide this interval into several segments according to a geometric sequence, such as eight segments: [1.0, 1.33], [1.33, 1.78], [1.78, 2.37], [2.37, 3.16], [3.16, 4.22], [4.22, 5.62], [5.62, 7.50], and [7.50, 10.0]. Perform Taylor expansion in each segment, and then record the coefficients of Taylor expansion in each segment in a table. During the calculation, first judge which segment the digit may fall in, and then use the look-up table method mentioned above to get the coefficients.

For all complex functions that accepts real numbers, such as trigonometric functions, natural logarithms, and hyperbolic functions, this "piecewise look-up table + Taylor expansion" method could be applied to quickly obtain results with sufficient accuracy. Taylor expansion can fit the characteristics of any function, enabling the calculation of any complex function, even without floating-point numbers in Solidity.

Conclusion

In this article, we first introduced the integer types supported by Solidity and the calculations performed on these integers, and then explained the problem of calculation overflow and solutions. Then, for the weakness that Solidity does not support floating-point numbers, we mentioned several remedies: using rational numbers instead of floating-point numbers; simulating the rounding of floating-point numbers; ensuring sufficient significant digits within the limit of 256-bit without causing overflow; and calculating complex functions with the least Gas consumption by the look-up table method and Taylor expansion.