Investigate approaches for improved modelling of predicted gas prices

[bvrooman]

Problem overview

Currently, the model for gas prices is determined by performing rudimentary checks on a linear regression:

benches/src/bin/collect.rs:

    let near_linear = linear_regression * NEAR_LINEAR;
    let expected_type = if (linear_regression - first.amount()).abs() < near_linear
        && (linear_regression - last.amount()).abs() < near_linear
    {
        Type::Linear
    } else if first.price() > last.price() {
        Type::Logarithm
    } else {
        Type::Exp
    };

Furthermore, the regression calculated on the benchmark data is discarded and not used when predicting prices; rather, we generate a new linear model by taking the first sorted point as the base and "worst-case scenario" data point as the slope. Generally, this model results in decently accurate costs at the lower end the input domain, but highly overestimated costs at the higher end of the input domain.

The other models (logarithmic and exponential) do not translate well into linear costs. At the same time, recent opcode benchmarks demonstrate that these types of functions are not modelled by any existing opcode and are thus defunct.

We outline goals of a desired gas pricing model:

• A model that gives "reasonably" accurate gas cost predictions based on the benchmarks. The closer the line models the benchmarked data, the better
• A model that leans towards overpricing costs rather than underpricing as a security measure against DoS exploits
• A model that makes costs low enough to make the network attractive to users

Solution:

• Standardize on what data is fed into benchmarks: Because data points have equal weight when calculating regressions, linear distance between points is most appropriate. Currently, the distance between data points is (arbitrarily) exponential, skewing the results.
• Investigate the use of a different regressions to identify the type of function latent in the data: linear, quadratic, logarithmic, exponential, etc. Compare the regressions to find the best models: the best models will have a strong fit (i.e. a close-to-1 r-squared value).
• Introduce different models of cost resolution based on the type of predictive model identified by comparing regressions.