Gas Efficient Square Root Calculation with Binary Search Approach

An Ethereum Improvement Proposal (EIP) introducing a gas-efficient method for computing square roots in Solidity using a binary search algorithm, aiming to reduce gas consumption for contracts that require such computations.

Vulnerability Detail

The vulnerability does not pertain to security but rather to efficiency. qv-base strategy contracts, especially often require square root computations. The widely adopted Babylonian method, based on Newton’s approach, consumes varying amounts of gas depending on the input size. The proposed binary search method provides a more consistent and in many cases, a more gas-efficient way to compute square roots, especially for larger input sizes.

Impact

Based on EIP-7054 and my local tests from 1E+18 values there is around 5.3x gas optimization, and because in QVBaseStrategy.sol input of _sqrt function alwats multiplied with 1E+18 value, there is possible a lot of gas optimization by switching to Square Root Calculation with Binary Search Approach.

Code Snippet

QVBaseStrategy.sol

https://github.com/sherlock-audit/2023-09-Gitcoin/blob/main/allo-v2/contracts/strategies/qv-base/QVBaseStrategy.sol#L487C1-L497C6

https://github.com/sherlock-audit/2023-09-Gitcoin/blob/main/allo-v2/contracts/strategies/qv-base/QVBaseStrategy.sol#L499C2-L535C1

Tool used

Forge Manual Review

Recommendation

Consider implementing the binary search-based square root function to optimize gas usage.

sherlock-audit / 2023-09-Gitcoin-judging