chaduke - noCircularLinkage() might fail to detect circles in the tree

[sherlock-admin]

chaduke

medium

noCircularLinkage() might fail to detect circles in the tree

Summary

noCircularLinkage(A, B) can detect circles that A is involved, but fail to detect the presence of circles of the whole tree in which A is not involved. As a result, when there is a circle in other branches of the tree, the function will get into infinite recursion and revert due to out of gas. The function will fail to detect when there is a circle in another branch that A is not part of.

Vulnerability Detail

The main issue of noCircularLinkage(A, B) is that it assumes: if there is a circle in the tree, then A must be involved. However, circles might exist in various branches, not just in the branch of A.

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

In the following code POC, we show that five tophats 1, 2, 3, 4, 5, when there is a cycle 2->3->4->5->3, and 1 is not involved, then noCircularLinkage(1, 2) will fail to detect the circle and revert due to infinite recursion.

 function testCircularLinks() public {
        uint32 TopHat1 = 1;
        uint32 TopHat2 = 2;
        uint32 TopHat3 = 3;
        uint32 TopHat4 = 4;
        uint32 TopHat5 = 5;
  
        uint id1 = utils.buildHatId(1 << 224, 1);
        uint id2 = utils.buildHatId(2 << 224, 2);
        uint id3 = utils.buildHatId(3 << 224, 3);
        uint id4 = utils.buildHatId(4 << 224, 4);
        uint id5 = utils.buildHatId(5 << 224, 5);
        assertFalse(utils.isTopHat(id1));
  
        utils.linkTree(TopHat1, id2);
        utils.linkTree(TopHat2, id3);
        utils.linkTree(TopHat3, id4);
        utils.linkTree(TopHat4, id5);
        utils.linkTree(TopHat5, id3);
  
        vm.expectRevert();  
        utils.noCircularLinkage(TopHat1, id2);
    }

Impact

noCircularLinkage() might fail to detect circles in the tree.

This might create circular management and confuse the power hierarchy in an organization. In addition, many functions (those that use recursions) will revert due to out of gas since they depend on the the property that there is no circle in the tree. For example, getHatLevel() will revert when there is a circle in the tree.

Code Snippet

See above

Tool used

VSCode

Manual Review

Recommendation

• record each tophat domains that have been visited, when a tophat domain is visited again, then we detect the presence of a circle.

[spengrah]

This is not a duplicate of #96 since it deals with circular admins rather than a DOS/stack-too-deep issue stemming from recursion.

[spengrah]

I'm still thinking this through, but I think that we can rely on the fact that if there is an undetectable circle then there will be infinite recursion, which (as noted) will result in a revert. While not as clean as bubbling up the CircularLinkage error, that should ensure that no circular links can be created.

TODO:

• check the hypothesis that undetected circles will result in reverts, ie because of infinite recursion. cc @zobront
• add note in natspec/docs that noCircularLinkage will revert if there is an undetectable circle (and that this is a good thing)

[spengrah]

Upon further inspection, I don't think this is an issue because it would not be possible to enter into this scenario in the first place. In the poc test above, utils.linkTree(TopHat5, id3) would fail because it itself is creating a circle, so we would never get to the purported issue.

[cducrest]

Escalate for 10 USDC

This scenario cannot happen, because noCircularLinkage() is called by _linkTopHatToTree every time a link is created. Even though it only checks for circular linkage involving the newly created link, it is sufficient as it will be run for every link created. It cannot be that the tree has a circular linkage in another branch because noCircularLinkage() would have been called when that other branch was been created.

[sherlock-admin]

Escalate for 10 USDC

This scenario cannot happen, because noCircularLinkage() is called by _linkTopHatToTree every time a link is created. Even though it only checks for circular linkage involving the newly created link, it is sufficient as it will be run for every link created. It cannot be that the tree has a circular linkage in another branch because noCircularLinkage() would have been called when that other branch was been created.

You've created a valid escalation for 10 USDC!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[hrishibhat]

Escalation accepted

Not a valid issue
Not a valid duplicate of #96
And the above-mentioned scenario with noCircularLinkage is not possible as shown in the comments from both Sponsor and Escalation

[sherlock-admin]

Escalation accepted

Not a valid issue
Not a valid duplicate of #96
And the above-mentioned scenario with noCircularLinkage is not possible as shown in the comments from both Sponsor and Escalation

This issue's escalations have been accepted!

Contestants' payouts and scores will be updated according to the changes made on this issue.