Determinism & WASM

Published in

Haderech_DEV

4 min readApr 27, 2022

Determinism vs Non-determinism

In mathematics, computer science and physics, a deterministic system is a system in which no randomness is involved in the development of future states of the system.A deterministic model will thus always produce the same output from a given starting condition or initial state [1]
A nondeterministic programming language is a language which can specify, at certain points in the program (called “choice points”), various alternatives for program flow. Unlike an if-then statement, the method of choice between these alternatives is not directly specified by the programmer; the program must decide at run time between the alternatives, via some general method applied to all choice points. A programmer specifies a limited number of alternatives, but the program must later choose between them. (“Choose” is, in fact, a typical name for the nondeterministic operator.) A hierarchy of choice points may be formed, with higher-level choices leading to branches that contain lower-level choices within them. [2]

The reason why determinism is important in Blockchain as replicated state machine

A State Machine begins at the State labeled Start. Each Input received is passed through the transition and output function to produce a new State and an Output. The State is held stable until a new Input is received, while the Output is communicated to the appropriate receiver. This discussion requires a State Machine to be deterministic: multiple copies of the same State Machine begin in the Start state, and receiving the same Inputs in the same order will arrive at the same State having generated the same Outputs.
…
Determinism is an ideal characteristic for providing fault-tolerance. Intuitively, if multiple copies of a system exist, a fault in one would be noticeable as a difference in the State or Output from the others. [3]

WASM as Blockchain contract engine

How is the EVM Designed? Why Is It Inefficient? Big Architecture Size Traditional computers contain instruction sets that function on inputs of 32 or 64-bit sizes. The EVM is different and special because it is a 256-bit computer, which was deliberately designed this way due to the ease of dealing with Ethereum’s hash algorithm, which explicitly generates a 256-bit output. Precompile Bloat The problem with precompiles is that they keep adding bloat and complexity to a VM instead of fixing the core problem: the inefficiency and poor design of the current instruction set and specification. [4]
WebAssembly, developed by the W3C, is in the words of its creators a “compilation target.” Developers don’t write WebAssembly directly; they write in the language of their choice, which is then compiled into WebAssembly bytecode. The bytecode is then run on the client — typically in a web browser — where it’s translated into native machine code and executed at high speed. [5]
WebAssembly is a platform agnostic binary format, meaning that it will run the same instructions across whatever machine it is operating on. Blockchains need determinacy in order to have reliable state transition updates across all nodes in the peer-to-peer network without forcing every peer to run the same exact hardware. Wasm is a nice fit for reliability among the possibly diverse set of machines. Wasm is both efficient and fast. The efficiency means that it can be uploaded onto the chain as a blob of code without causing too much state bloat while keeping its ability to execute at near-native speeds. [6]

more: The War on Virtual Machines: WASM vs. EVM

Non-determinism in WASM

• Except when otherwise specified, when an arithmetic operator returns NaN, there is nondeterminism in determining the specific bits of the NaN. However, wasm does still provide the guarantee that NaN values returned from an operation will not have 1 bits in their fraction field that aren’t set in any NaN values in the input operands, except for the most significant bit of the fraction field (which most operators set to 1). • Except when otherwise specified, when an arithmetic operator with a floating point result type receives no NaN input values and produces a NaN result value, the sign bit of the NaN result value is nondeterministic. Fixed-width SIMD may want some flexibility 🦄
In SIMD.js, floating point values may or may not have subnormals flushed to zero.
In SIMD.js, operators ending in “Approximation” return approximations that may vary between platforms [7]

Efforts to solve non-determinism issue in Blockchains

eos-vm

Given that all programs on the blockchain must be deterministic, floating point operations are of particular interest to us. Because of the non-deterministic nature of rounding modes, NaNs and denormals, special care has to be made to ensure a deterministic environment on all supported platforms. This comes in the form of “softfloat”, a software implementation of IEEE-754 float point arithmetic, which is constrained further to ensure determinism. If this determinism is not required, hardware based floating point operations are still available through a compile time define. [8]

refer to interpret_visitor from eos_vm

CosmWasm

Cosmwasm blocks float operators from gatekeeper by config allow_floats.

Wasmer & canonicalize-NaN

NaN canonicalization is available for all Wasmer backend s now. NEAR is using to overcome the only non-deterministic aspect of floats in Wasm and seems to be happy with it. [9]

canonicalize_nan() sets canonical nan if nan is used : x86_64/arm_64

Following operators calls canonicalize_nan():