Util: Wasm modules for crypto

[s1na]

This is a spin-off discussion from ethereumjs/ethereumjs-util#195 which aims to assess whether it makes sense to use Wasm modules for crypto.

The arguments for this approach being that WebAssembly is now available everywhere (node & browsers) in comparison to node-gyp bindings (used by the keccak and secp256k1) which is (as the name suggests) only available in node (in browser a native JS code is executed).

What remains to be seen is how the performance of an efficient Wasm module compares against the node-gyp bindings and native JS code.

[s1na]

I did a simple benchmark (not sure about accuracy) for keccak:

• keccak lib (with node-gyp binding) hovers around 20-30 us per hash computation
• keccak/js is around 150-160 us
• keccak256_rhash.wasm ewasm precompile is around 260-280 us including instantiation of the module, and 40-42 us excluding instantiation
• Rust ewasm keccak256 precompile is around 1,5 ms (including instantiation)

The precompile result also includes instantiation of the Wasm module and could potentially have overhead due to calling host functions for fetching input data, as seen in the source:

https://github.com/poemm/C_ewasm_contracts/blob/master/src/keccak256_rhash.c#L509-L521

I'll next try a simpler Wasm module (which doesn't call host functions).

[holgerd77]

👍

[s1na]

Slightly modified keccak256_rhash.wasm computes hashes in 10-20 us, which is slightly faster even than the native node-gyp binding. It's currently limited to inputs less than 128kb (which should be fine for most use-cases), but this can be fixed. So far I've only tested really simple inputs, I'll have to test more.

The gain comes from two sides:

• The wasm module now takes its input and a pointer to output directly as arguments of the _main function which avoids multiple EEI calls (downside being it's not ewasm-compatible anymore)
• Instantiation of the module constituted most of the time taken. Thanks to immense help from @poemm, we managed to avoid re-initializing the module every time (by zeroing out relevant parts of memory and avoiding a mutable global variable). This is the js code for calling the wasm module.

[holgerd77]

Oh, that sounds very promising, great!

[holgerd77]

What does this mean "not eWASM compatible any more? So can't this be used in the VM any more for an eWASM VM? This would be a major downside, wouldn't it?

[s1na]

By that I meant it cannot be used as an ewasm precompile (it doesn't adhere to the contract interface.

I don't think it's a major downside, because our use case here is just computing the hash, and we don't want to use this module as a contract. It can be used anywhere webassembly is supported (also in the VM).

[holgerd77]

Ah ok, thanks for the clarification! 😄

[alcuadrado]

@s1na those results look great!

The only thing that caught my attention is that every call to keccak operates in the same buffer now. Can this be problematic when used with WebWorkers? Does WebAssembly have threads?

It's currently limited to inputs less than 128kb (which should be fine for most use-cases), but this can be fixed.

There are some 10MB+ txs in the official test suite. Would that mean that this module has to retain 10MB of memory once loaded?

[poemm]

There are some 10MB+ txs in the official test suite. Would that mean that this module has to retain 10MB of memory once loaded?

You are 100% correct. The naive way to resolve the 128kb limit is to let Wasm memory grow arbitrarily large, which we have code to do. But (i) the Wasm spec doesn't allow shrinking memory and (ii) Wasm modules live forever. But the spec does discuss implementations having freedom to free resources once they are no longer needed -- this depends on the implementation.

A possible solution: The keccak256 algorithm loops over 136 byte blocks of the input. So perhaps we can give it many blocks at a time, and hopefully hashing time dominates the call overhead. This is complicated because the 400 byte keccak256 context must be retained between calls, either in the wasm module's memory (making it stateful), or passed and saved with each call. Maybe slowdowns are negligible if we allow up to ~1000 blocks at a time.

Does WebAssembly have threads?

Threads are a post-MVP feature proposal.

[alcuadrado]

Another solution can be to reuse the wasm instance for hashing buffers up to X bytes and use new ones for larger ones. This way the module would only retain ~X bytes.

I'd say that a relatively small X works for the vast majority of the cases.

[s1na]

I was thinking of the same thing. Or use a new instance after memory of the old instance has grown up to X. Should work for most of the use cases. I assume those 10Mb+ txes are worst-case scenarios rather than what's often used on mainnet?

[alcuadrado]

The block gas limit is about 8 million gas now and non-zero calldata bytes cost 68 gas. So it's impossible to use more than 128kb in a single tx today.

UPDATE: I should double check this. Maybe it's possible if it's full of 0s.

[alcuadrado]

I just found this: https://github.com/bitauth/bitcoin-ts
It has wasm versions of secp256k1, ripemd160, sha256, sha512, and sha1

[poemm]

I just found this: https://github.com/bitauth/bitcoin-ts
It has wasm versions of secp256k1, ripemd160, sha256, sha512, and sha1

The wasm for sha256 seems to be compiled from rust, https://github.com/bitauth/bitcoin-ts/blob/master/wasm/hashes/sha256/src/lib.rs .

[s1na]

I just found this: https://github.com/bitauth/bitcoin-ts
It has wasm versions of secp256k1, ripemd160, sha256, sha512, and sha1

Had a quick look at their secp256k1, it seems to have most of the functionality we need. Although I'm not sure about a few things. Do we use the compressed or uncompressed format for keys? There also seems to be a few variants for signature encoding, e.g. compact, DER. Not sure which one we're using. After I figure these out, I could write a wrapper similar to secp256k1-node and we can benchmark them.

Apart from secp256k1, we could potentially use sha256 and ripemd160 for the precompiles, but in my opinion they have lower priority compared to keccak256.

[poemm]

Apart from secp256k1, we could potentially use sha256 and ripemd160 for the precompiles

Another option is using the C_ewasm_contracts repo linked above which has several implementations of sha256 compiled to Wasm. Porting ripemd160 may be easy since it is part of rhash, where keccak256 and sha256 were ported from. The repo also has an attempt at porting libsecp256k1, which works when compiled to native but breaks when compiled to Wasm.

Had a quick look at their secp256k1, it seems to have most of the functionality we need. Although I'm not sure about a few things. Do we use the compressed or uncompressed format for keys? There also seems to be a few variants for signature encoding, e.g. compact, DER. Not sure which one we're using.

Appendix F of the yellowpaper should have answers. I forgot the details, but I used this appendix when attempting to port libsecp256k1 to Wasm. Also, I looked at Geth code which also uses libsecp256k1.

[holgerd77]

I guess this still might be a thing, so I'll keep for now.

[holgerd77]

Hi @paulmillr, circling you in here (into a very old issue), what is your idea on WASM for the crypto stuff?

[paulmillr]

@holgerd77 seems like a bad idea. How do you verify the stuff you're downloading is good, and not malware? NPM doesn't have signed code.

1. The compiled code could be replaced with malware completely.
2. Developer machines could get infected and produce "malware" with useful code, they won't even know it's happening. This happened recently in Swift ecosystem
3. All cryptographic primitives are fast enough to be used without wasm in web3 apps. By fast I mean "lots of operations to fit in one 120fps frame" (8.3ms). The only exception to this is bls12-381. Pairing takes 20 milliseconds in js. With low-level libs it could be 20-50x faster.
4. Wasm takes a lot of space, it's binary.
5. Security-wise it still won't matter because of gc and jit in js code.

If NPM gets signed code in place and you'll be able to verify it, and there would be infra for reproducible builds, then it would be better.

For the record: noble-hashes achieves 1.1 million sha256() operations per second with pure js. That's without loop unrolls! We can do faster, if needed.

@s1na mentioned 10-20 microseconds for wasm. So in this case sha256 takes 888ns/op. 14-25x faster

[holgerd77]

@paulmillr great, this is a lot of useful insight to put this in some perspective. 🙂 Thanks a lot for this detailed write-up. 🙏

Will close here for now.