Atomic metering

[axic]

This is a discussion we had with @wanderer at Devcon3. This is an attempt to determine upper bounds in metering.

In short the proposal is that functions can be annotated (probably through a custom section) marking them atomic. In this case, they only have a single useGas statement at the beginning of the body which will deduct the entire gas cost. (Likely this custom section would also contain this value.) As a result these functions cannot fail executing once started.

Now if the given function contains unbounded loops then they cannot be marked atomic and the metering contract would reject them.

[pepyakin]

1. What do you mean by unbounded loops? Is there bounded loops, and if so do you have an idea how to detect them?
2. Do functions that contain conditional branching eligible for such kind of metering? If so then what amount of gas would be deducted? Is it maximum or is there a refund, or what happens if there is not enough gas for one branch but enough for another?
3. Do these functions have to be leaf functions?

[axic]

Is there bounded loops, and if so do you have an idea how to detect them?

Say the loop counter is a constant. i.e. it could unrolled.

Do functions that contain conditional branching eligible for such kind of metering?

If atomic metering is enabled for such functions then the more expensive branch is considered.

Do these functions have to be leaf functions?

As long as all called functions are atomic, they don't need to be leafs.

[eira-fransham]

The restriction on bounded loops will make this a total pain in the ass for developers. Remember, we're not operating on source, we're operating on compiled bytecode. It may not be clear to developers what source-level change would allow their code to compile to a constant loop of the form that we are able to detect. Plus, it means that it's now essentially impossible to compile your code without optimisations (since even for a constant LLVM will often emit code to store the constant to a local and then reload it in debug mode).

That being said, I'm not necessarily against this idea in theory.

[axic]

To clarify: this is an option, which doesn't need to be enforced everywhere.

The reason we discussed it at Devcon3 was in a different design context, where it is extremely beneficial. In the case of ewasm it could be beneficial when working with precompiles to determine an upper bound cost for the precompile.

[gballet]

The restriction on bounded loops will make this a total pain in the ass for developers. Remember, we're not operating on source, we're operating on compiled bytecode. It may not be clear to developers what source-level change would allow their code to compile to a constant loop of the form that we are able to detect. Plus, it means that it's now essentially impossible to compile your code without optimisations (since even for a constant LLVM will often emit code to store the constant to a local and then reload it in debug mode).

Presumably those precompiles are going to be written in a fairly low-level language, and audited by us at the assembly-level anyway. I agree this is annoying however I don't believe it's a showstopper.

[lrettig]

The reason we discussed it at Devcon3 was in a different design context, where it is extremely beneficial

Which context was this? Context would be helpful in understanding the motivation here.

[eira-fransham]

To clarify: this is an option, which doesn't need to be enforced everywhere.

The reason we discussed it at Devcon3 was in a different design context, where it is extremely beneficial. In the case of ewasm it could be beneficial when working with precompiles to determine an upper bound cost for the precompile.

For precompiles and other trusted code this could definitely be useful, it would also just be an interesting project to analyse the complexity of a Turing-incomplete subset of WebAssembly. It's still of questionable usefulness, however, since the precompiles will almost certainly not be compiled to Wasm, they'll just be in assembly since they're trusted. Even if you did compile it to Wasm using something like Substrate's runtime system, the gas price returned by the analysis would not be applicable to the actual runtime of the function since you can do more aggressive compilation of untrusted code than trusted code. The untrusted code is probably going to be interpreted to start with and even if you compile it you can't compile aggressively because of compiler bombs, so you either have incompatible gas pricing or you have to intentionally gimp the performance of your trusted code.

Besides, if it's for precompiles, this doesn't need to be a function-level annotation. It can be an offline process whose output is then baked into the program, similar to how precompiles are handled right now.

Presumably those precompiles are going to be written in a fairly low-level language, and audited by us at the assembly-level anyway. I agree this is annoying however I don't believe it's a showstopper.

To be fair, I wouldn't consider the PITA factor to be a show-stopper even in the case of it being for untrusted code.

[pepyakin]

@axic ok thanks it makes sense now.
Although, for non-leafs it might be more complicated since they can form cycles.

[lrettig]

Please add metering label here, I cannot