Adding MSM for WebGPU

[Alberto Centelles (Acentelles)]

ICME have open sourced a WebGPU implementation for BN254 (other curves can be added):
https://github.com/ICME-Lab/msm-webgpu

For 2^20 MSMs, it brings a 10x improvement in performance.

Computing MSM on WebGPU is asynchronous. This means that any function that calls wgpu msm will need to be async, too.

One option is to have a wasm_32 variant for each of these functions. Another is to make all of these functions async regardless of the backend. Another one may be using WebWorkers, but I don't know much about it.

I don't think blocking approaches work. For example, pollster::block_on doesn't work for wasm_32, since the runtime is single-threaded and blocking it freezes the environment (e.g. the browser). In any case, despite the seemingly small change, I wanted to discuss which approach would be best for this codebase.

[Srinath Setty (srinathsetty)]

Could we add a feature flag and then depending on the future flag we make the methods have appropriate signatures?

Would that work?

[Alberto Centelles (Acentelles)]

Yes, but one needs to make so many changes that it becomes quite messy. You can get an idea from this PR.

My suggestion is to create a separate repo/clone (e.g. nova-web or nova-wasm) that keeps up to date with Nova but it is targeting the web. If you try to keep both variants in the same codebase it will lead to a lot of duplication.

[Srinath Setty (srinathsetty)]

Instead of propagating async to the entire call stack, can we make a blocking call to the webgpu at the lowest layer (e.g., from code in src/provider/msm.rs)?

For example, in tokio one could:

tokio::runtime::Runtime::new()?
.block_on(async_routine())

The code hosting this does not have to be async even though it is calling async_routine that is marked async.

Could we make this work for your context?

[Alberto Centelles (Acentelles)]

I don't think so, wasm runtimes in browsers run on a single thread, and you cannot block the main thread waiting for a Promise. So even tokio::Runtime::new().block_on(...) will panic or hang.