AltBn128 estimations

[jakmeier]

Before stabilizing alt_bn128 support as introduced in #3971, we need confidence in its gas costs.

The feature adds 3 cryptographic host functions that operate on a specific pairing-friendly elliptic curve.(See https://github.com/ethereum/EIPs/blob/master/EIPS/eip-196.md for details on the alternative Barreto-Naehrig curve.)

As far as the esimtation is concerned, these are just three new host functions names alt_bn128_g1_sum alt_bn128_pairing_check and alt_bn128_g1_multiexp. They all use variable-length array of elements as input. We charge base cost once per host function call plus additional cost per element.

We use https://github.com/zcash-hackworks/bn for implementing the cryptographic computations.

Right now, we estimate by setting up the contract runtime and measuring the cost holistically. This means the estimation also measures the cost for copying memory between host and guest. We currently do not subtract that in our estimations, thus we are effectively paying twice for that cost.

We could just subtract these costs but this has its own problems. (We would have to subtract an optimistic case of memory loading, to get a pessimistic estimation of the host function call, which leads to weird results.)

But I suggest to instead to rewrite estimations to directly call functions in runtime/near-vm-logic/src/alt_bn128.rs without the runtime. This way, we can measure exactly the cost of the cryptographic work and all other costs can be estimated independently.

Current Numbers Overview

The base costs of current estimation are very close to the nightly protocol parameters. Suggesting there is no immediate reason to change them. (But we could probably lower them with improved estimations)

	Current Parameter [Ggas]	Gcloud time [Ggas]	Icount [Ggas]	max(time,gcloud) * 3	before/after
alt_bn128_g1_multiexp_base	713.0069295	193.345	228.403373475	685.210120425	1.04056683964002
alt_bn128_g1_sum_base	3.175314375	0.819	0.847071384	2.541214152	1.2495264802854
alt_bn128_pairing_check_base	9685.508901	2597.21	3003.737638475	9011.212915425	1.07482854882063

The per element costs used to be charged per byte. We have to update them either way, even if we do not improve the estimation code.

Estimating for per-element cost should just increase these parameters by a factor equal to the number of bytes per element.
(edit: This is the case for everything, including alt_bn128_g1_sum, after fixing an off by 10x error)

	Current per byte Parameter [Ggas]	Element size	Adjusted parameter to element [Ggas]	Gcloud time [Ggas]	Icount [Ggas]	max(time,gcloud) * 3	before/after
alt_bn128_g1_multiexp_element	3.335092461	96	320.168876256	83.443	101.818287597	305.454862791	1.04817082737055
alt_bn128_g1_sum_element	0.076218543	65	4.954205295	1.26	1.478547968	4.435643904	1.11690776068213
alt_bn128_pairing_check_element	26.575188546	192	5102.436200832	1344.62	1586.906068472	4760.718205416	1.07177866461981

[jakmeier]

@matklad here are some numbers for the atl_bn costs

We could go ahead with the above numbers to stabilize the feature. But I think the costs per element would be more pessimistic than necessary. Would it make sense to spend the time to change estimations, as outlined above?

(Btw, if this is not too urgent, I think this could even be labled as good-first-issue. Once I explain to a potential contributor how to run estimations, it should not be that tricky to write an estimation that uses the cryptographic methods directly.)

[matklad]

But I suggest to instead to rewrite estimations to directly call functions in runtime/near-vm-logic/src/alt_bn128.rs without the runtime.

I think this applies to pretty much every host function we have, so, if we want to fix this, it's probably best to fix all costs at once in the same way. For alt_bn128, it's best to stay consistent with the current way of doing things.

There's also a question of whether this is a good idea -- I kinda like the "holistic" approach to measuring costs, as it guarantees that we are not missing anything. It does lead to slight overcharging. But we don't care about overcharging per-se I think, we only care about overcharging for the costs which actually matter. So, I don't see as a strong argument to do this work.

[jakmeier]

I take this as, we do not care about reducing the costs further before we stabilize the feature. So it shouldn't be a blocker for stabilization, which was my main concern. I will just have to submit a PR which updates costs to reflect elements and not bytes. Will do this after we have a new runtime config format. :) (If I get through with that soon enough)

There's also a question of whether this is a good idea -- I kinda like the "holistic" approach to measuring costs, as it guarantees that we are not missing anything. It does lead to slight overcharging. But we don't care about overcharging per-se I think, we only care about overcharging for the costs which actually matter. So, I don't see as a strong argument to do this work.

While I agree with your points, it still bugs me. We charge things very specifically (e.g. for copying bytes to host) but then estimate as if that is not charged separately. I feel like we should either simplify how we charge gas by removing a bunch of parameters, or commit to actually estimating those parameters such that they make sense. But not now, future Jakob can do that once he has nothing better to do, if he doesn't change his mind until then...

[jakmeier]

Landing #6787 closes this.

Possible changes to improve estimations are more general and should not be tracked in this issue.