Unlike well-known virtual machines such as the JVM and WebAssembly, EVM does not support the basic data types commonly used in programming languages such as int, Long, char, float, double, etc. Instead, it supports only one basic data type, the 256-bit long integer. Such EVM design also has certain rationality, for example:
- The output of a hash function is typically 256 bits
- When calculating elliptic curves, use long integers of 256 bits
- Using 256-bit long integers to implement rational numbers can replace floating point numbers in most scenarios and avoid the platform-dependence of floating point computation
- EVM is the VM that interprets the execution. The interpretation itself is more expensive than integer computation, and using 256-bit integers is not necessarily much slower than 64-bit integers
However, specific programming languages (e.g. Solidity, Vyper) had to be designed for EVM, creating a learning and understanding effort. Let’s start with a look at what basic data types Solidity provides.
Integer types in Solidity
Solidity supports signed and unsigned integers of length 8*N (1<=N<=32) with type names int or uint followed by length, e.g. Int8, int16, int64, int112, int256, uint32, uint128, uint256, If not followed by a length (int, uint), then the default length is 256.
At the bottom level, how does Solidity implement int8, INT16, int64, INT112, uint32, uint128, etc., shorter integers? It’s simple: these shorter integers take up exactly the same amount of memory and stack space as 256-bit integers, with no savings; After a calculation, the “and” operation is used to clear the bits that are not needed.
In summary, short integers do not save memory and stack space; instead, they require more steps in computation. Therefore, we should avoid using short integers whenever possible — with one exception: when using Storage, we should use short integers to save space. This series of articles covers saving Storage space.
The integer arithmetic supported by Solidity, the corresponding operators and their Gas consumption are shown in the following table:
| Computing category | operator | Gas |
|---|---|---|
| Add and subtract | +, – | 3 |
| To compare | = =,! =, >, <, >=, <= | 3 |
| A domain calculation | &, |,! , ^, >>, << | 3 |
| Multiplication, division and modulo | *, /, % | 5 |
| chengfang | 支那 | 10+50* Number of bytes resulting |
Integer overflow problem and SafeMath
We know that the following overflow problems occur when using binary complement to represent integers:
- The sum of two integers a and b of length N requires N+1 bits to represent the result. If the result is truncated to N bits by force, it will be smaller than both a and B
- The result of subtracting two positive integers a and b of length N is likely to be a negative number. If the result is forced to be interpreted as a positive integer, it will be a larger number than both a and B
- The product of two positive integers A and b of length N may require 2*N binary bits to accommodate
When Solidity performs arithmetical calculations on integers of various lengths, the resulting data is produced with the same length as the input data, allowing overflow to occur in certain scenarios. Overflows often lead to serious programming errors. BEC, for example, lost billions in market value because of a multiplicative overflow error. In order to terminate a program in the event of an error, many projects, including Oneswap, choose to use the SafeMath library:
import "./libraries/SafeMath256.sol"; abstract contract OneSwapERC20 is IOneSwapERC20 { using SafeMath256 for uint; .Copy the codeHere we import the SafeMath256 library and apply it to the 256-bit unsigned integer type uint. This library is available only for 256-bit unsigned integers. If you need SafeMath libraries of other lengths, consider:
- Is that necessary? Because shorter integers consume more Gas during the calculation, the best option is to explicitly convert the short integer to a 256-bit integer first and then explicitly convert it back after the calculation is complete
- If you must do so, you can refer to this article
SafeMath256, and libraries like it, work according to some simple rules, including:
- If the sum of addition is smaller than any of the addends, no overflow occurs
- The subtraction should be less than or equal to the minuend
- The quotient of multiplication, divided by the multiplied, should be equal to the multiplied
- The denominator of division and modulo operations cannot equal zero
If an input parameter violates these rules, functions in SafeMath256 revert.
Using SafeMath256 for uint allows SafeMath256 functions to be called using an object-oriented syntax for data of type Uint in the current contract. 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);
}
Copy the codeHere totalSupply. Add (value) is the equivalent of writing safemath256. add(totalSupply, value) syntax sugar for solidity, let’s make the code even shorter.
With SafeMath, the code is more secure, but more Gas is expended for rule checking, and EVM bytecode is bloated. Therefore, when we are doing a series of successive calculations, if we can be sure that the input data only has a finite number of digits, we can identify where it is safe to use the normal Solidity operator by carefully analysing whether arithmetic overflows occur at each calculation step. In OneSwap, this technique is used extensively, as in the following code:
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*/;
Copy the codeThe native multiplication and division operators are used, not the SafeMath library. The comments in the code indicate the maximum possible length of the data. According to the analysis, the overflow of multiplication will not occur at the maximum length. There is only one require statement, which checks the length of the significant bits for stockAmount, and after that, it is safe to assume that it is no longer than 42. With SafeMath, each multiplier and divisor brings in a require statement, and Gas consumption increases significantly.
Thinking in Rational
EVM and Solidity do not support floating point numbers, which does cause some inconvenience. A floating point number is a special kind of rational number whose denominator must be an integer power of two. If we think in terms of rational numbers, we can achieve the same effect as using floating point numbers. A rational number consists of an integer numerator and an integer denominator, indicating that it requires two integers.
When the OneSwap trading pair queries for prices, it returns three prices: the sell price, the buy price, and the AMM pool price, each represented by a numerator and a denominator, with a total of six integers, as shown in the following code:
function getPrices() external override returns (
uint firstSellPriceNumerator,
uint firstSellPriceDenominator,
uint firstBuyPriceNumerator,
uint firstBuyPriceDenominator,
uint poolPriceNumerator,
uint poolPriceDenominator)
Copy the codeOneSwap uses a 32-bit decimal floating-point number as a compressed representation of Price, which, when “unzipped,” forms a Rational Price represented by the following structure:
// A price presented as a rational number
struct RatPrice {
uint numerator; // at most 54bits
uint denominator; // at most 76bits
}
Copy the codeOneSwap uses Base Points (BPS) when calculating its rates, and the variable feeBPS recorded in OneSwapFactory is divided by 10000. For example feeBPS=50, then the rate is 50/10000=0.5%.
When using rational numbers, special attention should be paid to the problem of significant digits. OneSwap computes Token exchanges with AMM pools by calculating: reserveStock*(SQRT (numerator/denominator)-1), where numerator/denominator is a rational number slightly greater than 1. If floating-point support is available, this expression can be evaluated directly, because floating-point SQRT can normally accept floating-point numbers slightly larger than 1 as input. In Solidity, however, numerator/denominator would result in 1 and would end up with 0 directly following this expression, which is definitely not true.
To ensure that we have enough significant bits, we adjust the expression to: reserveStock*(SQRT (numerator*2**64/denominator)-1)/2**32, which corresponds to the following code:
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);
Copy the codeThe quotient here will be a number greater than 2**64. Root will be greater than 2**32. There are enough digits to make the final result exact.
Pawning Mechanism
In C, we use the floor function to round down floats, the ceil function to round up, and the round function to round. Solidity does not support floats. How can we achieve similar effects? When dividing integers, the remainder is discarded, equivalent to rounding down. So when we want to round down, we just write the division sign.
Rounding up can be done with the following technique:
uint fee = (amountToTaker * feeBPS + 9999) / 10000;
Copy the codeOneSwap uses this statement to calculate the transaction fee. AmountToTaker is the Token that the Taker is entitled to receive, multiplied by fee feeBPS to receive the transaction fee that shall be deducted. As we mentioned earlier, the transaction rate is actually a rational number: feeBPS/ 10,000. So how do I do the rounding up of a rational number? You just add “denominator minus one” to the numerator and do normal division.
Similarly, the rational numbers a/b can be rounded :(a+b/2)/b.
Smart contracts are often designed with the rounding principle of “I want to take advantage of them, and they can’t collect my wool”. According to this principle, if it’s good for me to round down, I go down; If it’s good for me to round up, it goes up; Rounding is rarely used because it is not in anyone’s favor.
The ERC20 tokens on Ethereum tend to be in 18-digit decimal, so the rounding error that “I” can take is 10-18 tokens at most, which is extremely low value, so it’s not that unfair to others.
• Maintain Gradual Accuracy Loss as far as possible
As we mentioned earlier, OneSwap computates the number of tokens exchanged with the AMM fund pool by calculating the opening square, and for the opening calculation to be accurate, the numerator needs to be multiplied by 2**64. However, arithmetic overflow is possible with this multiplication!
Is it possible to use SafeMath256’s overflow proof multiplication function? While this ensures that the program does not make arithmetic errors, it also refuses to serve the user under normal circumstances, brutally rolls back the transaction, and leaves the user handing over Gas without getting the desired result.
Because we cannot assert that the vast majority of cases molecules must be less than 2 * * 192, not assert that all lead to molecular multiplied by 2 * * 64 an overflow condition, after all is caused by malicious users to attack system, so still have to think of a way to, in the case of molecules is greater than or equal to 2 * * 192, also calculate properly prescribe, even lose some accuracy.
If you divide the numerator and the denominator by 2 to the NTH, the rational number stays the same. If the lowest N bit in the binary representation of the numerator and the denominator is zero, then we can safely shift the numerator and the denominator N to the right. If the lowest N bits are not zero, but we also move both the numerator and denominator to the right, then there is a loss of precision. Fortunately, the loss of precision is small. Here is an example from Python, where we can see that the lowest 36 bits are zero or not zero, and it makes little difference to the final result.
>>> 0xfedcba9876543210987654321* (1<<64) /0x123456789abcdef0123456789
258254417031933725993L
>>> 0xfedcba9876543210000000000* (1<<64) /0x123456789abcdef0000000000
258254417031933725999L
Copy the codeBased on this observation, we can tentatively shift both the numerator and denominator right at the same time until the numerator is small enough to be multiplied by 2**64 without spilling over. In OneSwap code, it reads like this:
while(numerator >= (1<<192)) { numerator >>= 16; denominator >>= 16; } require(denominator ! = 0, "OneSwapPair: DIV_BY_ZERO"); numerator = numerator * (1<<64);Copy the codeThere is still a require statement, but it only rolls back the transaction if the numerator and denominator are more than 2**128 times different, which is almost impossible. Now we can be sure that for the vast majority of cases, this code will execute normally, but for some special cases, there will be a slight loss of precision.
Table Lookup
As mentioned earlier, the Gas consumption of power is “10+50* bytes of result”, which is a relatively large consumption. Taking the common ERC20 token precision 18 as an example, the result of 10**18 takes 8 bytes to represent, so the Gas consumption of 10**18 is 10+50*8=410, which is equivalent to hundreds of ordinary arithmetic operations.
When the power of a power is not particularly large, look-up tables can be used to calculate the power of a power. For example, OneSwap uses the following two functions to help calculate the power of a power during the “unpacking” 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);
}
Copy the codeThe 256-bit integer x in the code above is a combination of eight 32-bit integers from which powSmall picks the ith 32-bit integer; Y is a combination of four 64-bit integers, of which powBig picks the ith 64-bit integer. By calculating x and y in advance, we can guarantee that powSmall(I)==10 ** (I + 1) and powBig(I)==10 ** (I * 8).
Taylor expansion
Solidity does not directly support square root calculations. The SQRT function in the Math library, used by Uniswap and OneSwap, uses the Babylonian algorithm to compute square roots exactly. Babylonian algorithm is a special case of Newton’s iterative method when it is applied to square root. It requires many iterative steps to obtain accurate results, so its Gas consumption is relatively high, often more than 4000.
Given that the square root of the rational number numerator/denominator here is a value slightly greater than 1, it can be assumed that most of the time it is less than 1.25. So here we can use Taylor expansion to speed things up, and just go to the third term, and the accuracy is good enough. Expand the square root function to the third term near 1.0, and get:
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);
Copy the codeThis code completes the calculation of reserveStock*(SQRT (Numerator /denominator)-1) with very little Gas.
What if, in our application, the rational numerator/denominator has a large possible value range? For example, it is in the interval [1,10]. At this point, we can divide the interval into several segments according to the geometric sequence, for example, 8 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], [7.50, 10.0]. Do Taylor expansion inside each segment, and then record the Coefficients of Taylor expansion in each segment in a table; When calculating, first determine which section falls in, and then use the table lookup method mentioned above to take out the coefficient.
All complex functions that evaluate real numbers, such as trigonometric functions, natural logarithms, hyperbolic functions, etc., can be quickly obtained with sufficient precision using this “piecewise table lookup + Taylor expansion” method. Taylor expansion can fit the characteristics of any function, guaranteeing that we can perform calculations of any complex function, even when Solidity lacks floating-point support.
conclusion
In this article we start with an introduction to the types of integers supported by Solidity and the calculations that can be performed on them, followed by an explanation of the problems with calculation overflows and how to avoid them. Then, to address Solidity’s lack of floating-point support, several solutions are presented: using rational numbers instead of floating-point numbers; How to simulate rounding of floating point numbers; How to ensure enough significant bits without overflow in the limit of 256 bits total length; Using look-up table method and Taylor expansion, the complex function is calculated with minimum Gas consumption.
原文: OneSwap Series 3- find Arithmetic Operations in Solidity…
OneSwap Chinese community