---
tags: pvf, wasm
---

# Deterministic PVF Metering

> **Disclaimer**: This is an ongoing resarch. Don't get too hyped just yet.

## Intro

Gas metering is known from Ethereum world. Executing contracts code consumes gas. A block can contain a limited amount of gas.

Historically, we assumed that gas metering in wasm introduces a fair amount of overhead. The experiments showed slowdowns at least 50% compared to no metering and some data suggested up to 200% slowdown. And this is already on top of 2x in wasm vs. native code known in folklore.

This made us to avoid relying on gas metering. It looked like we could get away by relying on timeouts.

- **Substrate** does not care that much about time thanks to the state transition function being fully trusted. It's up to the runtime author to make sure the Runtime's consumption of time is in check. Primarily this is achieved by FRAME's weight mechanism. Weight is roughly equivalent to time, on average time spent on the reference hardware anyway. As we speak weight becomes multi-dimensional, but the point still holds.

- **Polkadot** needs to execute parachain validation functions. Those execute on relay chain validators and tell whether a given parablock is valid. PVFs are supplied by the parachain authors and are not trusted. To prevent infinite loops PVFs are executed with a deadline timer. If the deadline is reached, the parablock is considered invalid and discarded.

One may point out that this may lead to consensus divergence and will be right. We mitigate it by introducing different timeouts for different stages of parablock inclusion. During the backing stage the validators allow 2 seconds for PVF execution. During the following approvals stage there is a more lenient limit of 6 seconds.

Timing limits served us well. However, recent problems with parachains has lead us to start questionioning that approach.

Turned out that some validators would run relay chain validators on weak hardware to increase their profitability. That has lead to those slow validators not being able to finish PVF execution in time and thus into thinking that the corresponding parablock is not valid. The rest of the network considered the parablock valid. Such consensus divergence leads to disputes followed by slashing of the minority. One mitigation that could be deployed is [Time Disputes](https://github.com/paritytech/polkadot/pull/1656). It is a pretty complex mechanism though.

This could further be exploited with a malicious PVF. Imagine an innocuous PVF that accepts a number N as a parameter. The PVF performs some amount of work N times. Then that PVF is fed with parablocks that gradually increase this number. At some point a part of nodes will inevitably start timing out the PVF due to natural differences in the performance between all nodes.

> There is actually a lot of sources of variability.
>
> - **Hardware**: The modern CPUs vary a lot. Different instruction sets, microarchitecture, sizes of caches can lead to enourmous differences on different workloads.
>
> Some machines have hyper-threading which virtualize cores. Nodes can also run on virtual machines, where the underlying hardware can be shared with other customers.
>
> - **Software**: A node can be subjected to a varying amount of work. It can perform several PVF executions in parallel. There can be a network usage spike.
>
> The activity outside of the node can also affect the performance of the wasm execution. Memory pressure can lead to swapping. Paging back can take significant time.
>
> Finally, the wasm compiler version can also affect the performance significantly.
>
> We can be sure that the performance varies significantly.

To wreck havoc, such a PVF would need first to pass the backing stage. That is plausible since the attacker has virtually unlimited number of attempts. A puppet backing group can also help.

Malicious PVFs was thought of something far fetched at least until parathreads arrive. It becomes less looming though as we are nearing the time when they are introduced. Not to mention that a similar condtion can arise in a legit PVF. Also, at the time of writing, there is not much demand for parachain slots. The latest bid for the slot is $60k and only 12 hours left until the candle runs out. Therefore, the problem becomes more urgent.

Those reasons made us to revisit the idea of gas metering. Since the initial experience with metering, wasmtime gained a builtin support for fuel[^1] metering. It is still slow, with up to 40% of slowdown on my contrived benchmarks.

[^1]: gas and fuel metering are synonyms

Thankfully, we had an observation that helped to find a way more efficient solution to metering. We don't need to stop at the exact point where the gas ran out, we just need to know if the PVF finished in a given number of steps what matters.

Next we will look into the implementation details. Feel free to skip.

## Technical Details

### Vanilla Implementation

Let's examine how is the current wasmtime fuel metering implementation worked.

A naive way to implement fuel metering is to insert a snippet of code that increments a fuel counter and checks it if it is overflown. This is a very brute force approach and can be improved significantly by a one weird trick.

Any program[^2] is made of if statements, loops and calls. We can decompose any program into a control-flow graph.

[^2]: well, without GOTOs anyway.

For example, the following program

do {
  if (a) {
     // then block
  } else {
     // else block
  }
} while (b);
return;

can be represented as the following CFG.


The boxes in that chart represent a straight line code that does not contain any branches within it. If the execution gets into a block it executes completely and then leaves to one of the outgoing blocks. This representation allows us to insert the gas checks only at the block boundries. The number of checks required drops from the number of operations to the number of blocks.

Each instrumented block would gain a piece of code similar to:

fuel -= 1337;
if (fuel < 0) throw;

Another trick, roughly is to insert only the increment part at each block. The compare-and-throw part can be inserted at loop backedge and when a function returns.

This is how wasmtime manages to lower the slowdown to "only" ≈40%.

The cost of those checks are coming from the fact that the fuel variable have to be loaded from and stored to memory. Even though the conditional branch should be correctly be predicted to not to be taken, it still has some cost. Finally, extra space is required to store those checks which makes instruction caches less effective.

### Proposed Implementation

The crux of the idea for speeding up is to remove all the checks and leave only the minimum extra code. Specifically, the absolutely required part is to increment the fuel counter. The check if the counter reached negative numbers can be performed asynchronously.

The asynchronous interrupt can be implemented via various means. On Linux/Unix, signals can be used. A custom signal may be raised on a thread that executes wasm. It then extracts the current value of fuel and terminates the execution if the fuel counter is negative.

That obviously does not work if the async check happened, when the thread was executing non-wasm code. Rust or C or whatever other code happened to be executed from wasm does not know about any fuel. Therefore, the signal handler must ensure that the thread was in the wasm code.

Suppose that's the case. What's next? We still need to somehow extract the fuel counter in the handler. We could compute where the variable that contains fuel is stored for each instruction[^3]. Alternatively, we could bluntly reserve a dedicated register to only store fuel. That takes the register from being used elsewhere, but that disproportionally simplifies the implementation.

[^3]: that's how the format intended for debugging, DWARF, works. It is considered to be complex.

Now that the signal handler ensured it's in wasm and extracted the fuel counter, it checks if the counter is negative and if so initiates a trap, which unwinds the stack up until the nearest call into wasm from Rust.

Since the interruption is based on a timer almost certainly the out-of-gas condition will be caught with a delay. Obvious implication is that the actual execution time will vary based on the frequency of async fuel checking. Also, if the OOG happened then the contents of the wasm sandbox are non-deterministic since the number of steps performed by the wasm is not deterministic. That is fine, since we discard the wasm instance. The wasm code can also run out of gas but still manage to successfully return. In that case, the execution is deemed to OOG.

The wasm execution can only be interrupted if it is in wasm. However, this is fine since we flush and do a sync check during calling to non-wasm code.

## Discussion

A prototype shows the slowdown hovering in the 0-5% range. A rough consensus seems to indicate that this is considerably lower than what we are willing to accept to solve the aforementioned problems in Polkadot.

Shawn Tabrizi suggested that we use metering for runtime execution in Substrate instead of weights. It changes the game so that we might be able to get rid of weight benchmarks. A big win here is for the runtime authors experience. We shift the burden of benchmarking of every bytecode and host function cost to Substrate, instead of every runtime writer writing their own benchmarks for each extrinsic.

If we were to abandon the weight benchmarks and switch to fuel metering completely, then the extrinsics/dispatchables won't have any knowledge of fuel they can consume beforehand. Thus, this would require the extrinsics to supply the maximum fuel they are willing to spend. In addition to that, it's not entirely clear how do we implement the dispatching of extrinsics.

1. One option is to introduce an abilitity to do nested calls, similar to [try..catch](https://github.com/paritytech/substrate/issues/2980). The problem with that is the delayed detection of OOG.

Imagine a PVF initiates a nested call with low fuel. The callee would just loop until it runs out of gas. The OOG condition will only be detected after around ≈1/F, where F is the async polling frequency.

One way to mitigate that would be to charge the caller for ≈1/F worth of fuel. Others include limiting the minimum number of fuel and number of nested calls possible per the PVF run.
1. Checkpointing. A construction similar to try..catch, but instead of creating a new instance, the current instance will be forked. In case a trap or OOG happens, the state of runtime is rolled back to the nearest checkpoint. The state includes the wasm memory, the storage, the allocator state (could be avoided by embedding the allocator inside of the wasm), and other properties and explicitly excludes the fuel counter.

Interesting effect is that the fuel counter from the perspective of the wasm code is always deterministic, since it is counted inline.

So far this looks as a clear win. However, there are several drawbacks.

- Metering fixes the number of steps executed by PVF, leaving the execution time to float.

This solves the aforementioned issues, but introduces others. Ideally, the gas amount would correspond to the execution time approximatelly. However, execution time variability discussed is not going away. That means that the each unit of gas will be either slower or faster than the real time.

If it is faster, then more instructions executed could be fit into the same time window. That means we don't utilize underlying hardware enough. If it is slower, then the execution will take more time than estimated by gas. Hopefully not too long or else it's a DoS vector. That requires fuel costs to be as accurate as possible.

- The proposed mechansim is complex. It requires usage of low-level and not portable OS facilities. It also relies on specific way code is generated.

It is also hard to test. It is not trivial to trigger an interrupt at a specific location.