Gas Price Overestimation Due to Incorrect Standard Deviation Calculation.

[howlbot-integration[bot]]

Lines of code

https://github.com/code-423n4/2024-06-thorchain/blob/e3fd3c75ff994dce50d6eb66eb290d467bd494f5/bifrost/pkg/chainclients/ethereum/ethereum_block_scanner.go#L281-L289

Vulnerability details

Impact

If the standard deviation is underestimated due to the missing (n - 1) division, the calculated gas price (mean + 3x standard deviation) may be higher than necessary. This can result in overpaying for gas and wasting resources. @>/bifrost/pkg/chainclients/ethereum/ethereum_block_scanner.go#L282-L289

// compute the standard deviation of cache
std := new(big.Int)
for _, fee := range e.gasCache {
    v := new(big.Int).Sub(fee, mean)
    v.Mul(v, v)
    std.Add(std, v)
}
std.Quo(std, big.NewInt(int64(e.cfg.GasCacheBlocks)))
std.Sqrt(std)

The issue is that the standard deviation is being calculated incorrectly. The correct formula for standard deviation is.

std = sqrt(sum((x - mean)^2) / (n - 1))

However, in the code, the division by (n - 1) is missing. Instead, it divides by n (which is e.cfg.GasCacheBlocks).

Proof of Concept

Suppose the gas prices in the cache are as follows: [100, 120, 110, 130, 90]. The correct calculations would be:

mean = (100 + 120 + 110 + 130 + 90) / 5 = 110
variance = ((100 - 110)^2 + (120 - 110)^2 + (110 - 110)^2 + (130 - 110)^2 + (90 - 110)^2) / (5 - 1) = 250
standard deviation = sqrt(250) ≈ 15.81

However, with the missing (n - 1) division, the incorrect calculation would be:

variance = ((100 - 110)^2 + (120 - 110)^2 + (110 - 110)^2 + (130 - 110)^2 + (90 - 110)^2) / 5 = 200
standard deviation = sqrt(200) ≈ 14.14

As a result, the estimated gas price would be:

• Correct: 110 + 3 * 15.81 ≈ 157.43
• Incorrect: 110 + 3 * 14.14 ≈ 152.42 The difference in the estimated gas prices can lead to the impacts mentioned above, such as overpaying or underpaying for gas and inconsistent behavior.

Tools Used

Vs

Recommended Mitigation Steps

By dividing by (e.cfg.GasCacheBlocks - 1) instead of e.cfg.GasCacheBlocks, the standard deviation will be calculated correctly using the unbiased estimator.

// compute the standard deviation of cache
std := new(big.Int)
for _, fee := range e.gasCache {
    v := new(big.Int).Sub(fee, mean)
    v.Mul(v, v)
    std.Add(std, v)
}
std.Quo(std, big.NewInt(int64(e.cfg.GasCacheBlocks-1))) // Divide by (n - 1)
std.Sqrt(std)

Assessed type

Math

[the-eridanus]

adding sponsor disputed: the standard deviation formula for samples does have (N-1) in the denominator, but for populations it has (N) in the denominator. Since the updateGasPriceFromCache is considering all gas prices currently in the cache, the population standard deviation formula seems more appropriate.

[c4-judge]

trust1995 marked the issue as unsatisfactory: Invalid

[trust1995]

Sponsor explained the conscious choice to use (N) for the denominator.