Build WASM prover / module

[HarryR]

For any of the SNARK circuits, we should be able to build a WebAssembly module which:

• exports prove / verify functions
• allows loading proving key from HTTP backend

This seems fairly straightforward, using the current cmake project, to build target webassembly using Emscriptem, without modifying any of the C++ code heavily.

References:

• https://developers.google.com/web/updates/2018/03/emscripting-a-c-library
• https://github.com/adevaykin/minimal-cmake-emscripten-project
• https://stackoverflow.com/questions/37747205/cmake-project-for-emscripten#37869647
• https://kripken.github.io/emscripten-site/docs/porting/files/index.html
• https://kripken.github.io/emscripten-site/docs/porting/files/Synchronous-Virtual-XHR-Backed-File-System-Usage.html
• http://forums.4fips.com/viewtopic.php?f=3&t=1201
• https://kripken.github.io/emscripten-site/docs/compiling/Building-Projects.html
• http://kripken.github.io/emscripten-site/docs/optimizing/Optimizing-Code.html?highlight=optimisation
• "Use llvm-lto when compiling from bitcode to JavaScript: --llvm-lto 1. This can break some code as the LTO code path is less tested."

This will need to be a separate repo which uses the ethsnarks repo as a sub-module.

[barryWhiteHat]

@Schaeff can you link to some of your work on this?

[HarryR]

This will just be cross-compiling using Emscriptem, it looks very straightforward. That will enable it to run in Chrome 57+ on Android and Desktop, iOS, Edge Mobile etc.

See:

• https://www.chromestatus.com/feature/5453022515691520
• https://developer.mozilla.org/en-US/docs/WebAssembly#Browser_compatibility

However, Chrome seems to have a memory limit of about 2gb for webassembly modules, I fear that without #3 this limit will be hit very quickly, and even then it may be highly problematic.

[HarryR]

So, I have a work-in-progress repo which uses Emscripten to build the ethsnarks repo (as well as libgmp, openssl & boost).

There are a few broken things though:

• File IO doesn't seem to work well, ios.is_open is returning false
• Memory limit is 2gb (signed 16 bit integer, upper bound 32767)

Executable sizes are very reasonable:

• hashpreimage_cli.js - 234kb
• hashpreimage_cli.wasm - 989kb
• miximus_genKeys.wasm - 767kb
• verify.js - 230kb
• verify.wasm - 652kb

I'm going to add some more test executables to the repo which do end-to-end tests to see if I can get the SHA256-full circuit proving and then verifying under webassembly without reaching the memory limit.

This will let me compare the performance versus native x86_64 code to see if that's a significant issue. The biggest problem is probably going to be speed of the mpz_t structure from libgmp. I'm not sure if I built it with 32bit or 64bit limbs, but I heard that long long in webassembly is slow as there's no native support in asm.js or webassembly.

Staying under the 2gb limit is gonna be ... challenging, especially with larger circuits, but it's doable.

verify.wasm.gz
verify.js.gz
miximus_genKeys.wasm.gz
miximus_genKeys.js.gz
hashpreimage_cli.wasm.gz
hashpreimage_cli.js.gz

[barryWhiteHat]

So cool! These tools are gonna be really useful.

[Schaeff]

Hi @HarryR sounds very cool, tagging @lucasvo who has been looking at similar things

[HarryR]

Only two modifications need making to libsnark:

• in basic_radix2_domain_aux.tcc remove the empty asm volatile chunks. - they only contain a /* pre-inner */ and /* post-inner */ - Emscripten checks for empty asm() statements and ignores them, but doesn't consider comments.
• in profiling.cpp in get_nsec_cpu_time, clock_gettime isn't supported, so need to add if defined(_MSC_VER) || defined(__EMSCRIPTEN__) return 0; rather than just _MSC_VER

However, the wasm build is dog slow.

Also in Call to r1cs_to_qap_instance_map_with_evaluation throws then catches a bunch of exceptions (for unknown reasons), but continues running.

I made a test which, in one go creates a mod_hashpreimage, creates keypair, proves something, then verifies the proof.

Time for test_hashpreimage native build:

• generating proving key: 18.6s
• generating proof: 4.4438s
• verifying proof: 0.0419s

Times for test_hashpreimage WASM build:

• generating proving key: 817s (48x slower)
• generating proof: 216s (48x slower)
• verifying proof: 1.8s (42x slower)

That'a significant decrease in speed... like very significant.

test_hashpreimage.wasm.gz
test_hashpreimage.js.gz

run with: node test_hashpreimage.js after gunzipping the two.

Now I have a baseline I can start experimenting with optimisations.

1. Increase mp_limb_t from unsigned long (32 bit) to unsigned long long (64bit)
2. Increase to -O3, add -flto etc.
3. ... then what? I think it's unlikely that's going to reduce the prove time enough.

I will push up my ethsnarks-emscripten repo soon after I can reproduce the build process in a scriptable way.

[HarryR]

After building GMP with 64bit limbs, cleaning up the ethsnarks-emscripten repository, and running the next set of tests, the results are:

• generating proving key: 829s
• generating proof: 205s
• verifying proof: 1.5s

It doesn't seem, for WASM, that there's much difference between 32bit limbs and 64bit limbs. Everything is just slow....

Anyway, all the stuff needed to build is at: https://github.com/HarryR/ethsnarks-emscripten