Gas cost estimates incorrect due to rounding in calc_mem_gas()

Submitted by obront.

Relevant GitHub Links

https://github.com/vyperlang/vyper/blob/b01cd686aa567b32498fefd76bd96b0597c6f099/vyper/utils.py#L191-L193

Summary

When memory is expanded, Vyper uses the calc_mem_gas() util function to estimate the cost of expansion. However, this calculation should round up to the nearest word, whereas the implementation rounds down to the nearest word. Since gas costs for memory expansion increase exponentially, this can create a substantial deviation as memory sizes get larger.

Vulnerability Details

When Vyper IR is being generated, we estimate the gas cost for all external functions, which includes a specific adjustment for the memory expansion cost:

# adjust gas estimate to include cost of mem expansion
# frame_size of external function includes all private functions called
# (note: internal functions do not need to adjust gas estimate since
mem_expansion_cost = calc_mem_gas(func_t._ir_info.frame_info.mem_used)  # type: ignore
ret.common_ir.add_gas_estimate += mem_expansion_cost  # type: ignore

This calc_mem_gas() function is implemented as follows:

def calc_mem_gas(memsize):
    return (memsize // 32) * 3 + (memsize // 32) ** 2 // 512

As we can see on EVM.codes, the calculation should be:

memory_size_word = (memory_byte_size + 31) / 32
memory_cost = (memory_size_word ** 2) / 512 + (3 * memory_size_word)

While both implementations use the same formula, the correct implementation uses memory_size_word as the total number of words of memory that have been touched (ie the memsize is rounded up to the nearest word), whereas the Vyper implementation rounds down to the nearest word.

Impact

Gas estimates will consistently underestimate the memory expansion cost of external functions.

Tools Used

Manual Review, EVM.codes

Recommendations

Change the calc_mem_gas() function to round up to correctly mirror the EVM's behavior:

def calc_mem_gas(memsize):
-   return (memsize // 32) * 3 + (memsize // 32) ** 2 // 512
+   return (memsize + 31 // 32) * 3 + (memsize + 31 // 32) ** 2 // 512

vyperlang / vyper