Allarious - [Medium][Gas/Stack Management] Recursive functions are used regularly and can increase gas usage quadratically or might face stack too deep

[sherlock-admin]

Allarious

medium

[Medium][Gas/Stack Management] Recursive functions are used regularly and can increase gas usage quadratically or might face stack too deep

Summary

Recursive functions are used throughout the code, while these are a good way to handle certain situations, they can lead to quadratically increasing gas usage if used carelessly.

Vulnerability Detail

In solidity, gas usage of memory allocation is increased quadratically by design, this is to avoid using extreme amounts of memory to do certain tasks. However, throughout the code, there are many recursive functions which recursively use memory to achieve an answer. However, it is a good idea to consider memory and stack uses on various calls, as extensive use of these resources can make the functions uncallable in certain states.

In the code snippet below, we created 6 topHats and one child hat for each, we connected each tree to each other, and ran the function getAdminAtLevel(hatId, 0) to see how gas effects each run. The output for each adding level was as below:

  1594
  3466
  6025
  9280
  13231
  17875

While the increase from first to second level was 1872, the increase in the last two levels was 4644! This value can increase much more and make getAdminAtLevel(hatId, 0) and the functions that use in uncallable.

While this is only one example of the functions, many other functions are also using recursive algorithms that can increase the gas and stack usage.
Another danger is the error stack too deep, it should be noted that solidity only has a stack which is 1024 words deep. using more than that can cause errors.

Impact

Recursive functions can become uncallable.

https://github.com/Hats-Protocol/hats-protocol/blob/fafcfdf046c0369c1f9e077eacd94a328f9d7af0/src/HatsIdUtilities.sol#L151-L160

Code Snippet

contract PoCTests is TestSetup {

    function setUp() public override {
        setUpVariables();

        hats = new Hats(name, _baseImageURI);
    }

    function test_quadraticMemoryRecursive() public {
        uint256 topHatIdOne;
        uint256 topHatIdTwo;
        uint256 topHatIdThree;
        uint256 topHatIdFour;
        uint256 topHatIdFive;
        uint256 topHatIdSix;
        
        topHatIdOne = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");
        topHatIdTwo = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");
        topHatIdThree = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");
        topHatIdFour = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");
        topHatIdFive = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");
        topHatIdSix = hats.mintTopHat(topHatWearer, "tophat", "http://www.tophat.com/");

        uint256 hatIdOne;
        uint256 hatIdTwo;
        uint256 hatIdThree;
        uint256 hatIdFour;
        uint256 hatIdFive;
        uint256 hatIdSix;

        vm.startPrank(topHatWearer);
        hatIdOne = hats.createHat(topHatIdOne, "hat", _maxSupply, _eligibility, _toggle, false, "");
        hatIdTwo = hats.createHat(topHatIdTwo, "hat", _maxSupply, _eligibility, _toggle, false, "");
        hatIdThree = hats.createHat(topHatIdThree, "hat", _maxSupply, _eligibility, _toggle, false, "");
        hatIdFour = hats.createHat(topHatIdFour, "hat", _maxSupply, _eligibility, _toggle, false, "");
        hatIdFive = hats.createHat(topHatIdFive, "hat", _maxSupply, _eligibility, _toggle, false, "");
        hatIdSix = hats.createHat(topHatIdSix, "hat", _maxSupply, _eligibility, _toggle, false, "");

        hats.requestLinkTopHatToTree(hats.getTopHatDomain(topHatIdTwo), hatIdOne);
        hats.requestLinkTopHatToTree(hats.getTopHatDomain(topHatIdThree), hatIdTwo);
        hats.requestLinkTopHatToTree(hats.getTopHatDomain(topHatIdFour), hatIdThree);
        hats.requestLinkTopHatToTree(hats.getTopHatDomain(topHatIdFive), hatIdFour);
        hats.requestLinkTopHatToTree(hats.getTopHatDomain(topHatIdSix), hatIdFive);

        hats.approveLinkTopHatToTree(hats.getTopHatDomain(topHatIdTwo), hatIdOne);
        hats.approveLinkTopHatToTree(hats.getTopHatDomain(topHatIdThree), hatIdTwo);
        hats.approveLinkTopHatToTree(hats.getTopHatDomain(topHatIdFour), hatIdThree);
        hats.approveLinkTopHatToTree(hats.getTopHatDomain(topHatIdFive), hatIdFour);
        hats.approveLinkTopHatToTree(hats.getTopHatDomain(topHatIdSix), hatIdFive);
        vm.stopPrank();

        uint256 gasBefore;
        uint256 gasAfter;

       // I should have written these in a loop :"-) Anyways...

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdOne, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdTwo, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdThree, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdFour, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdFive, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);

        gasBefore = gasleft();
        hats.getAdminAtLevel(hatIdSix, 0);
        gasAfter = gasleft();
        console.log(gasBefore - gasAfter);
    }
}

Tool used

Manual Review

Recommendation

Use the recursive functions carefully, it is recommended by the solidity documents to use loops instead of recursive functions as much as possible.

Memory is more costly the larger it grows (it scales quadratically).

Calls are limited to a depth of 1024, which means that for more complex operations, loops should be preferred over recursive calls.

https://docs.soliditylang.org/en/v0.8.19/introduction-to-smart-contracts.html

Duplicate of #96