RandomWASM

[samholmes]

What changes to RandomX hash algorithm would be necessary to remove the advantage of running the hash algorithm in native implementation over WASM?

A modified RandomX hash algorithm could be called RandomWASM. It would be designed to be an WebAssembly-first implementation of an ASIC-resistant algorithm. RandomWASM would be able to achieve comparable performances in WASM as a native binary for the same hardware. This design would allow for web applications to implement ASIC-resistant hash algorithms with security peace of mind. Is this pursuit feasible?

I'd imagine removing the inefficient instruction sets from the RandomX when executed in WASM. Secondly, removing the memory requirements of that RandomX has in full-mode. RandonWASM would operate with memory requirements that fit the constraint of a web environment.

The purpose of this algorithm is a web-compatible ASIC-resistant algorithm. It may not be viable to mine Monero or other cryptocurrencies which deploy RandomX as their hash algorithm, but it would open up the potential for other cryptocurrencies and crypto-projects which would deploy RandomWASM.

What are the list of instruction sets to remove/replace from RandomX which would make RandomWASM?

[l1mey112]

I would be thrilled to answer your question, I've thought about this a lot.

Instructions/RandomX VM execution

My original thought was that VM execution was dominated by waiting for the JITted WASM VM code to compile, but its only around ~2% of the total execution time, but as intended, the slowness is the in the actual execution (#1).

const jit_wm = new WebAssembly.Module(scratch.subarray(0, jit_size)) // <- right here!
const jit_wi = new WebAssembly.Instance(jit_wm, jit_imports)
const jit_exports = jit_wi.exports as { d: () => void }
jit_exports.d() // <- real slowness here!

$ INSTRUMENT=2 make pkg-randomx.js/dataset.wasm pkg-randomx.js/vm.wasm && NOMAKE=1 INSTRUMENT=2 scripts/build.ts && node examples/randomx.js
┌─────────┬────────────────────┬──────┬─────────┐
│ (index) │ name               │ time │ percent │
├─────────┼────────────────────┼──────┼─────────┤
│ 0       │ 'scratchpad init'  │ 0.9  │ '1.5%'  │
│ 1       │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 2       │ 'vm iteration'     │ 7.5  │ '12.2%' │
│ 3       │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 4       │ 'vm iteration'     │ 6.6  │ '10.7%' │
│ 5       │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 6       │ 'vm iteration'     │ 7.7  │ '12.5%' │
│ 7       │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 8       │ 'vm iteration'     │ 7.1  │ '11.6%' │
│ 9       │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 10      │ 'vm iteration'     │ 7.2  │ '11.7%' │
│ 11      │ 'wasm compilation' │ 0.2  │ '0.3%'  │
│ 12      │ 'vm iteration'     │ 7.3  │ '11.8%' │
│ 13      │ 'wasm compilation' │ 0.1  │ '0.2%'  │
│ 14      │ 'vm iteration'     │ 7.7  │ '12.4%' │
│ 15      │ 'wasm compilation' │ 0.1  │ '0.2%'  │
│ 16      │ 'vm iteration'     │ 7.3  │ '11.8%' │
│ 17      │ 'scratchpad hash'  │ 1    │ '1.6%'  │
└─────────┴────────────────────┴──────┴─────────┘

I'd imagine removing the inefficient instruction sets from the RandomX when executed in WASM. Secondly, removing the memory requirements of that RandomX has in full-mode. RandonWASM would operate with memory requirements that fit the constraint of a web environment.

[...]

What are the list of instruction sets to remove/replace from RandomX which would make RandomWASM?

There are things you can safely remove, the AES usage (softaes.c), use of all 4 IEEE-754 rounding modes (semifloat.c), 128-bit multiplies (mulh.c), and so on. Removal of those should constitute a linear decrease of die space on some hypothetical ASIC. You could easily replace AES with something like ChaCha20.

Possibly meaningful: Extract out hot parts of VM body and implement as another function to give the runtime a chance to optimise its body. We are spending ~10ms per virtual machine execution, we can surely spare some time for the runtime to hot swap the body.

Execution time is dominated by VM execution, which is what you want. A JS runtime cannot replace a function with an optimised one during its execution, so we're left with absolutely zero VM executions that are optimised (in the prof output, a star *function is optimised).

#1

I tested a configuration that separated main RandomX VM into a loop and a function called in the loop body instead of one large function (2 functions instead of 1 function). My original consensus for having one big function was that it would save time on WASM compilation, as there isn't enough time to perform optimisations. I was right anyway, the JavaScript VM will never optimise our functions beyond a baseline JIT.

Possibly meaningful optimisations:

JIT: Improvements to scheduling of virtual machine instructions. It is possible to reorder instructions to place them close to eachother, without using any local.* instructions. This will improve baseline JITs register allocation (RA), and may improve subpar JITs RA.

#1

If a RandomWASM or improved RandomX.js were to be created, the WASM code JITted for the RandomX VM body needs to be implemented smarter using fewer instructions (use a linear topological sort of bundles of instructions with inputs and outputs than can be threaded together, to avoid loads and stores from local registers).

Though, I doubt this will be as meaningful compared to relaxing the memory requirements.

Memory Requirements

Every single a VM iteration, the inner loop body executes 2048 times (RANDOMX_PROGRAM_ITERATIONS). Every single loop the dataset is accessed once, executing 8 SuperscalarHash programs.

This is very slow. In any case, the memory requirement for efficient mining is incredibly high so RandomX.js opts to mine in verification mode which executes the 8 SuperscalarHash programs every time instead of precomputating the entire dataset ahead of time.

The Cache -> SuperscalarHash -> Precompute Dataset model of RandomX is a pretty great innovation doing a lot of the heavy lifting resisting against ASICs. To remove this would make your RandomX derivative be much, much weaker to ASICs.

I do not have a solution to this that would balance ASIC resistance and allow for efficient JS execution. However, gutting this and just keeping the purely instruction based JIT is what is used for client puzzles such as Equi-X (tevador/equix) and Tor's POW (v1). Who knows, this actually might be an okay tradeoff.

Conclusion

In conclusion, if I had to guess what we needed to gut/change for RandomWASM, it would probably be:

1. Improve the JIT, simplify the VM body.
2. Remove the dataset, keep the scratchpad memory requirement.
3. Remove AES, use of IEEE-754 rounding modes, and 128-bit multiplies.
4. Keep VM chaining, but reduce the VM chains to maybe 4.
5. Augment or completely change the instruction set, utilise more integer SIMD, change the VM specification and registers in use.

Keep in mind, with some or all of these changes native code will still always beat RandomWASM without fail, with absolute lowest case probably being 30-40% quicker. But, that cost is amortised if you threw this code on 100 webpages each with a thousand users you evil bastard /j.

Let me know any points or counterpoints, I'd be happy to converse about this.

I suggest anyone interested wanting to comment should skim the RandomX design document: design.md.