Determinism of the library

[angrymouse]

Hey! Is it possible to create fully deterministic sandbox from this library? (So that same code will always give same result with same input, even if code authors try to get different results). Assuming exposing only asyncified function (no callbacks or promises) and not exposing any non-deterministic functions, would there be some other ways to produce non-determinism?

[justjake]

I don't think the Javascript bits of the library introduce non-determinism into the VM. You should double-check the Emscripten module initialization code for your preferred variant.

As far as behavior of the upstream quickjs interpreter, I don't understand the underlying code enough to give a confident answer. You can try asking folks at quickjs-ng quickjs-ng issues, the upstream bellard/quickjs issues or the mailing list

[angrymouse]

Thank you! Will do.

[Lohann]

@angrymouse I think just for the fact that all numbers in javascript are IEEE-754 float, I don't think is possible to guarantee determinism across different machines without emulate all numbers (which can make it very slow):
https://gafferongames.com/post/floating_point_determinism/

[josephrocca]

I think just for the fact that all numbers in javascript are IEEE-754 float, I don't think is possible to guarantee determinism across different machines without emulate all numbers (which can make it very slow)

Maybe I'm missing your point, but floating point operations within WebAssembly are deterministic.¹

I think wasm libs will generally be deterministic so long as:

1. The host code inits the web assembly module with the same features enabled (since different runtimes support different features).
2. "Relaxed SIMD" is not used, threads (with shared memory) are not used, and potentially other features added in the future (which are explicitly known to be non-deterministic).
3. The host code sends it exactly the same data - i.e. careful about stringification, or other processing that happens on the data in the host runtime before passing it into the wasm module. (I think this is what this github issue is about, to be clear)

https://github.com/WebAssembly/design/blob/main/Nondeterminism.md

In this case of quickjs-emscripten, assuming Date, and Math.random (and similar? I can't think of any others) are patched, then I think the only possible issue is the NaNs.

¹ Though apparently the "sign bit of the NaN result value" can differ across machines. See above Nondeterminism.md link. Also the dfinity team apparently adds code which normalizes NaNs in wasm, though I'm not sure if that's at the wasm runtime level, or the wasm bytecode level.

[josephrocca]

I just discovered this other thread and I've tested Lohann's code. I can confirm that quickjs-emscripten doesn't have this issue. I've tested on about 10 different devices, including different OS and CPU architecture.

I can replicate this difference in normal JavaScript (i.e. in browser console):

let nan = new Float32Array([0.0, 1.0, NaN, 0.0]);
nan[1] = nan[1] / nan[3];
nan[0] = nan[0] / nan[3];
nan[3] = nan[0] / nan[0];
let uint8 = new Uint8Array(nan.buffer);
console.log(Array.from(uint8));
// apple silicon: [0, 0, 192, 127, 0, 0, 128, 127, 0, 0, 192, 127, 0, 0, 192, 127]
// amd x86_64:    [0, 0, 192, 255, 0, 0, 128, 127, 0, 0, 192, 127, 0, 0, 192, 255]

But if I run that same code inside QuickJS, then across all machines I always get:

[0, 0, 192, 127, 0, 0, 128, 127, 0, 0, 192, 127, 0, 0, 192, 127]

So it appears that we can make QuickJS fully deterministic by just using something like this before any other code is executed:

const originalDate = Date;
globalThis.Date = class extends originalDate {
  constructor(...args) {
    return args.length ? new originalDate(...args) : new originalDate(Date.__currentMsSinceEpoch);
  }
  static now() {
    return Date.__currentMsSinceEpoch;
  }
};
Date.__currentMsSinceEpoch = 0;
delete globalThis.performance;
globalThis.performance = {now:Date.now};

Math.random = ((seedStr) => { // https://stackoverflow.com/a/47593316/993683
  function xfnv1a(k) {
    for(var i = 0, h = 2166136261 >>> 0; i < k.length; i++) {
      h = Math.imul(h ^ k.charCodeAt(i), 16777619);
    }
    return function() {
      h += h << 13; h ^= h >>> 7;
      h += h << 3;  h ^= h >>> 17;
      return (h += h << 5) >>> 0;
    }
  }
  let seed = xfnv1a(seedStr);
  let a = seed();
  return function() {
    let t = a += 0x6D2B79F5;
    t = Math.imul(t ^ t >>> 15, t | 1);
    t ^= t + Math.imul(t ^ t >>> 7, t | 61);
    return ((t ^ t >>> 14) >>> 0) / 4294967296;
  }
})("a seed string...");

[Lohann]

When running Javascript using WebAssembly the non-deterministic behavior depends on the runtime, some runtimes may do NaN canonicalization, others don't.

• Feature suggestion: strict "deterministic mode" WebAssembly/design#582 (comment)

There's compiled WebAssembly, like Wasmer, Wastime, Liftof, etc.. and interpreted webassembly like Wasm3 and Wasmi. Deterministic or non-deterministic behavior vary based on how each compiler optimize wasm code, or how they handle IEEE-754 float operations.

[Lohann]

I came to this topic evaluating the feasibility of using javascript in the Blockchain environment, which all code is considered adversarial and any source of non-determinism can be used to cause Split Brain and consensus issues.

Most use-cases aren't so strict, I still don't recommend the usage Javascript as smart-contract runtime, not just because of determinism issue, but also because of unpredictable computational complexity to execute things like regex... but for other applications it's ok.