Metering

Given a set of operations and a corresponding set of costs for each operation we can deterministically run computation for any number of cost units by summing up the costs on the execution of each operation. We call the cost units here "gas" and it stands as a estimation for computational time.

Metering in WASM

The following has been implemented here

Metering by Branch

To meter Webassembly we first define all the operation that can cause branches.

`const branching_ops = new Set(['end', 'br', 'br_table', 'br_if', 'if', 'else', 'return', 'loop'])`

We also define a map that contains each opcode and its associated cost. We will refer to this as the cost table. The Default cost table is defined here

``````cost_table = {
'op': cost
}
``````

Lastly we need a metering statement, we will uses

``````i64.const <cost>
call \$meter
``````

And a metering function `\$meter`. The meter function has a signature of `(type (func (param i64)))`. Internally this function should keep a running sum and if that sum grows larger than a given threshold, end the program's execution. The metering function can be imbedded in the binary itself or can use wasm's import to define it externally.

Then given an array of opcodes we iterate the array and divided into segments that start with one of the `branching_ops`

``````const code = [...opcodes]
const segments = []
let current_segment = []

for (let op in code) {
current_segment.push(op)
if (branching_ops.has(op)) {
segments.push(current_segment)
current_segment = []
}
}
``````

Then for each segment we calculate the sum of the operations. At the beginning for each segment we then append a metering statement.

``````metered_segments = segments.map(segment => {
let cost_of_segment = segment.reduce((sum, op) => {
return sum + cost_table[op]
}, 0)

return getMeterStatement(cost).concat(segment)
})
``````

Lastly we concatenate all the metered segments together

``````metered_code = metered_segments.reduce(a, b => {
return a.concat(b)
},[])
``````

Special metering: memory

Metering memory makes use of the separate memory system of WebAssembly: - the module parameter `memory` - the two instructions: - `grow_memory` - `current_memory`

Memory size is expressed in pages, where a page is 65536 bytes.

The module parameter specifies the initial page count and an optional maximum page count the module cannot exceed. The currently available page count can be queried via `current_memory` and new pages can be allocated via `grow_memory`. Read more about memory in the the WebAssembly design.

Gas needs to be charged for the initial allocated pages as well as any increase of pages via `grow_memory`.

Initial memory allocation

The cost of pre-allocated memory should be counted before instantiating the module.

Increasing memory

Any calls to `grow_memory` needs to be prepended with a call for metering.

Examples

The following examples assume we have a cost table that defines all operations to have the cost of 1

Basic

``````(module
(fun
i64.const 1 ;; +1
drop        ;; +1
end         ;; +1
)
)
``````

This code can be transformed to

``````(module
(type (func))
(type (func (param i64)))

(import "ethereum" "useGas" (func \$meter (type 1)))
(func (type 0)
i64.const 5 ;; 3 +  2 the cost of metering
call \$meter
i64.const 1
drop
end
)

``````

Conditionals

``````(module
(func \$fac (param i64) (result i64)
(if i64
(i64.lt_s (get_local 0) (i64.const 1))
(then (i64.const 1))
(else
(i64.mul
(get_local 0)
(call \$fac
(i64.sub
(get_local 0)
(i64.const 1)))))))
(export "fac" (func \$fac)))
``````

This code can be transformed to

``````(module
(type \$type0 (func (param i32) (result i32)))
(type \$type1 (func (param i32)))
(import \$meter "metering" "usegas"  (param i32))
(export "fac" \$func1)
(func \$func1 (param \$var0 i32) (result i32)
i32.const 211
call \$meter
get_local \$var0
i32.const 1
i32.lt_s
if i32
i32.const 180
call \$import0
i32.const 1
else
i32.const 420
call \$meter
get_local \$var0
get_local \$var0
i32.const 1
i32.sub
call \$func1
i32.mul
end
)
)
``````

Future Work

More efficient metering algorithms can be defined. For example if we can prove that an `end` is impossible to jump to it doesn't need to be segmented. The tradeoff here is the complexity for implementing these algorithms.