DeFiHardhat
12,000 USDC
View results
Submission Details
Severity: low
Invalid

ncorrect Calculation of nth Roots for Large Values and Non-Square Roots

Summary

The nthRoot function use the Newton-Raphson method to compute the nth root of a given number a.
This function has a flaw in handling large values and roots that are not perfect squares, particularly when n is not equal to 2, 4, 8, or 16. The key issues arise from an inappropriate initial guess and potential overflow during computations.

Vulnerability Details

the bug in in the nthRoot Function, i do test that pertains to the handling of large numbers and roots other than squares .
And The initial guess (x_0 = 10) is not adaptive to the value of a or n. In cases where a is extremely large (such as 10181018) or where n is not 2, this guess does not approximate the true root closely enough to ensure efficient or accurate convergence through the Newton-Raphson method.
also the scaling operation (10 ** n) * a used to enhance precision can lead to significant overflows or computational inaccuracies when n is large or a is very large, which severely impacts the subsequent root calculation steps.
this line is causeing the issue :

uint256 a0 = (10 ** n) * a;

when n or a is large is introduces a risk of overflow and here the multiplication can exceed the limits of uint256, leading to incorrect values being fed into the root calculation here :

uint256 xNew = 10;
uint256 x;
while (xNew != x) {
x = xNew;
uint256 t0 = x ** (n - 1);
if (x * t0 > a0) {
xNew = x - (x - a0 / t0) / n;
} else {
xNew = x + (a0 / t0 - x) / n;
}
}

here is a scenario as poc that i use in test :

  • Value of aa: 10181018 (a very large number)

  • Root nn: 3 (cube root)
    Expected Result:

  • The exact cube root of 10181018 is 106=1000000106=1000000.
    Obtained Result:

  • The computed cube root was approximately 86707649579163.286707649579163.2.
    Discrepancy:

  • The expected result is 10000001000000, but the computed result is 86707649579163.286707649579163.2, which is significantly off the mark.

  • This discrepancy show a failure in the function's algorithm to correctly handle cases where the number aa is large, and the root nn is not a square root.

  • The root causes identified from the function's implementation and test results are:
    The fixed initial guess of x0=10x0​=10 is not suitable for all cases, especially when the true root is vastly different from this guess. For 10181018, starting the iteration from 10 leads to inaccurate iterations that do not converge effectively to the true root.
    The iteration formula used in the Newton-Raphson method, xnew=x−xn−an⋅xn−1xnew​=x−n⋅xn−1xn−a​, relies heavily on the initial guess being somewhat close to the true root. When the guess is far from the true root, as in this case, the formula can converge slowly or inaccurately, leading to substantial errors in the final result.
    The multiplication of aa by 10n10n can lead to precision issues or even overflow

Impact

the erroneous calculations is lead to financial discrepancies in contracts, that affecting balances, payouts, or token distributions.
This compromises the reliability and accuracy of any financial mechanisms within the contract.

Tools Used

manual review

Recommendations

adjusting the initial guess and removes the scaling that led to potential overflow and replacing it with safer checks

Updates

Lead Judging Commences

giovannidisiena Lead Judge about 1 year ago
Submission Judgement Published
Invalidated
Reason: Incorrect statement
Assigned finding tags:

Informational/Invalid

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.