029.md

Festive Mint Platypus

Medium

Tx to buyVote can run out of gas if the value if the diff between maxVotesToBuy and minVotesToBuy is too high.

Summary

Linearly checking for the right value of votes to purchase based on the buy amount by decrementing one vote at a time is extremely gas expensive also makes the tx unpredictable in volatile gas markets possible causing OOG errors and reverts. The loop is technically unbounded as it directly proportional to the maxVotes count.

The affected party in this denial of service is the user.

Root Cause

In ReputationMarket:457 we see that the logic to decide how many votes to add is done by looping from the maximum allowed votes all the way down 1 by 1 until the fee is covered.

This puts a user who passes UINT256::MAX as maxVotes simply because they are expecting to buy up all the votes possible given their buyAmount. The protocol currently handles it poorly causing this tx to run out of gas really quickly as the value increases. This makes the likelihood low but the impact high.

Internal Pre-conditions

N/A

External Pre-conditions

N/A

Attack Path

When the function ReputationMarket::buyVote is called with a really high maxVotesToBuy allowed parameter and very low minVotesToBuy and buyAmount

Impact

The user looses the trade as tx becomes unpredictable in gas volatile markets. It becomes especially frustrating if the voting market is also volatile at the same time period and a user who is willing to buy max possible trust tokens undergoes a OOG error effectively a denial of service

PoC

Add the following test suite in this test file.

  describe('POC:oog', () => {
    it('increases gas cost with `maxVotes` possibly denying user from getting votes', async () => {

      let previousGasCost = 0n;

      // User's intention is to buy at least 5 votes in the transaction
      const actualVotesToBuy = 5n;
      const actualVotesCost = DEFAULT.buyAmount * actualVotesToBuy;


      let count = 6; // We'll try 6 different values for maxVotes
      for (let maxVotesToBuy = actualVotesToBuy; count-- > 0; maxVotesToBuy = maxVotesToBuy * 2n) {
        const { gas } = await userA.buyVotes({
          // Due to market fluctuation, user is willing to buy a lot maximum votes with that same buyAmount)
          votesToBuy: maxVotesToBuy, // This parameter actually represents `maxVotes` (check the util file if you want)

          // The following variables are set to constants
          buyAmount: actualVotesCost,
          minVotesToBuy: actualVotesToBuy,
        });
        if (previousGasCost > 0n) {
          console.log(
            "Gas cost for buying", maxVotesToBuy, "is", gas, ". Difference: ", Number(gas.valueOf()) - Number(previousGasCost.valueOf())
          );
        }
        previousGasCost = gas;
      }

      /*
       *  OUTPUT:
       *  Gas cost for buying 10n is 775939n . Difference:  104993
       *  Gas cost for buying 20n is 2606557n . Difference:  1830618
       *  Gas cost for buying 40n is 6245843n . Difference:  3639286
       *  Gas cost for buying 80n is 13565953n . Difference:  7320110
       *  Gas cost for buying 160n is 27838718n . Difference:  14272765
       *
       */
    });
  });

Mitigation

Replace Linear Search with Binary Search in buyVote.

Time complexity of O(log n) is much closer to constant than it is to O(n). That should drastically improve predictability and gas price.

So,

For an intuition of how it would work is that, consider a number scale from 0 to maxvotes. One end we have maxVotes + 1 which would be too expensive, so won't work. On the other end you have 0 votes which will work. So it's about finding the sweet spot by always visiting the middle value and deciding which half to choose to explore the good portion

bad: MaxVotes + 3 bad: MaxVotes + 2 bad: MaxVotes + 1

. . . . good: 2 good: 1 good: 0