Fix the gas formula for Ristretto255 multi-scalar multiplication

[wrwg]

Problem

With the current gas formula (here) for Ristretto255 multi-scalar multiplication (an operation with input of variable size n) , we are under-charging with a charge rate below 60% when n>200.

The formula is currently $g(n)=9420000\cdot \lfloor\frac{n}{\lfloor\log_2(n+1)\rfloor}\rfloor+6000\cdot n$, which does not match the underlying implementation here (2-phased; linear when n is large enough).

NOTE: the charge rate will keep going down as n grows, since the actual cost will go up linearly in n while the calculated gas increase sub-linearly. E.g., when n=100000 the gas charged is 59475000000 while the gas consumed is ~134878368300, charge rate being 44%.

The n-by-nanoseconds_executing curves look like below. (ns sampled is the benchmark datapoints from cargo bench -p aptos-crypto -- vartime_multiscalar_mul; ns predicted is the gas charged divided by gas_per_ns=205.41 , where gas_per_ns is approximated by benchmarking SHA2-256 on a x86/64 machine and comparing the execution time with its gas formula).

The SHA256 curve below shows that gas_per_ns=205.41 is a good estimate, given that SHA256 gas formula is supposed to be $g(n)=(50n+3000)\times 20$.

Proposed changes

The proposed formula is $g(n)=\begin{cases}k_0n+b_0, n<190\k_1n+b_1, n\ge 190\end{cases}$ where:

• $k_0=23755666$
• $b_0=85091092$
• $k_1=14009578$
• $b_1=3874443420$

This formula gives the following curves under gas_per_ns=205.41

[github-actions[bot]]

This issue is stale because it has been open 45 days with no activity. Remove the stale label or comment - otherwise this will be closed in 15 days.