FairSide contest - gpersoon's results

Handle

gpersoon

Vulnerability details

Impact

The performance (gas usage) of the current arctan implementation is: arctan(ONE) ~ 5126 Gas (with solidity 0.6.8) The main cause of the gas usage is due to the library ABDKMathQuad which implements IEEE 754 quadruple-precision binary floating-point numbers However the arctan approximation has a relative low precision.

The PDF higher_order_approximations.pdf in the following article: https://www.researchgate.net/publication/258792323_Full_Quadrant_Approximations_for_the_Arctangent_Function_Tips_and_Tricks shows different formulas for the approximation for arctan, which have a higher precision than the current implementation. https://www.researchgate.net/profile/Xavier-Girones-2/publication/258792323_Full_Quadrant_Approximations_for_the_Arctangent_Function_Tips_and_Tricks/links/5fdc7f5745851553a0c8b801/Full-Quadrant-Approximations-for-the-Arctangent-Function-Tips-and-Tricks.pdf

The third order approximation is: arctan(x) ∼ π/2 * sgn(x)φ(abs(x)) φ(x) = { ax + x^2 + x^3 } / { 1 + (a+1)x + (a+1)x^2 + x^3 } a=0.6399276529

I've made an implementation (see below), which takes a lot less gas: arctan_uint(1 * precision) ~ 574 Gas (with solidity 0.6.8)

The implementation takes a different approaches to floating points: it multiples all numbers by precision. The precision factor can be adjusted as long as all temporary variables stay below 2^256 (the max value of an uint)

Proof of Concept

pragma solidity 0.6.8;

contract Test{ uint constant precision=10**30; uint constant pi=3.1415926535E30; uint constant pidiv2=pi/2; uint constant a1=0.6399276529E30; uint constant aplus1=1.6399276529E30;

function arctan_uint(uint x) public pure returns (uint) { uint xsquare = xx/precision; uint xtriple = xsquare * x/precision; uint aplus1x = aplus1 * x/precision; uint top = a1 * x/precision + xsquare + xtriple; // ax + x^2 + x^3 uint bottom = precision + aplus1x + aplus1xx/precision + xtriple; // 1 + (a+1)x + (a+1)x^2 + x^3 return pidiv2top/bottom; }

function test_arctan_uint() public pure returns (uint){ return arctan_uint(precision); }
}

Tools Used

Recommended Mitigation Steps

Define which resolution is required and take the necessary formula from the higher_order_approximations.pdf document. Change the math library to a simple "precision" based implementation (as shown above). This will also require adapting other code. Also set the "precision" constant to the required precision and adjust the constants to the required number of decimals.