Beanstalk: Dive Into Basin

Summary

Newton-raphson methods can lead to large changes between iterations, since the magnitude of change is dependent on the derivative of the curve at that point, which can be very low, leading to very high changes. This can lead to underflows due to the large deviations, which will cause the function to revert.

Vulnerability Details

The NR method formula is given as:

So if the derivative of the function is very high, the correction factor f/f' can be very high. High enough that it can exceed x_n and lead to a negative result. This case is not handled by the code in the nthRoot function, and leads to frequent reverts.

The code first estimates a starting value of 10. It then iterates until the new and old guesses converge, and updates the guess value. It takes into consideration if the actual root is above or below the current guess, and shifts the solution accordingly.

If the current guess x's power is above the actual value a0, the guess is updated down. So some value is subtracted from it, following the NR method. However, if the value is too high, the subtraction can lead to a negative value, which will cause the function to revert.

So if (x-a0/t0)/n is larger than x, the code reverts.

This is the case when calculating the cube root of 183170186729404119539492883022829059658.

A fuzzing suite was developed using recon (https://getrecon.xyz/) which uses the medusa fuzzer. The suite indicated a failure due to overflow of the nthRoot function, and the following case was shown to revert.

This shows the inability of the function to handle all inputs. This library is in scope of this audit, and has a function which reverts on expected inputs. Thus this is a high severity vulnerability.

Impact

The library function in scope for this audit reverts on expected inputs. If this function is used for actual markets, it can lead to DOS of the system if the reserves are made to match conditions for which the library is unable to find a root via external donations. Thus this is a high severity issue.

Tools Used

Foundry, Medusa, Recon

Recommendations

In case the (x-a0/t0)/n is larger than x, the code should check this condition to prevent an underflow. The new guess xNew can either be set to 0 (which can lead to infinite loops), or be set to a percentage reduced guess, like xNew = 0.5*x. Changing the guess like this on a smooth curve like x^n will lead to a different value of the derivative, and will allow the function to converge smoothly over multiple attempts instead of crashing via underflow.

Note: The fuzzing suite developed to check the math functions can be shared on request.