ICME WebGPU MSM

An implementation of the cuZK paper in Rust for Multi-Scalar Multiplication (MSM) over the BN254 curve for WebGPU.

For an introduction to ZK proving using WebGPU, see this recent post by zkSecurity.

This work is built upon the existing ZPrize 2023 submission by Tal Derei and Koh Wei Jie. Their documentation will largely serve as a documentation for this implementation, too.

Further reads on the optimisations applied:

• Optimizing Montgomery Multiplication in WebAssembly by Koh Wei Jie.
• Optimizing Barrett Reduction: Tighter Bounds Eliminate Redundant Subtractions by Suneal Gong.
• Signed Bucket Indexes for Multi-Scalar Multiplication (MSM) by drouyang.eth.

Test

For $2^{16}$ MSMs:

wasm-pack test --chrome --test test_webgpu_msm_cuzk_16

For $2^{17}$ MSMs:

wasm-pack test --chrome --test test_webgpu_msm_cuzk_17

For $2^{18}$ MSMs:

wasm-pack test --chrome --test test_webgpu_msm_cuzk_18

For $2^{19}$ MSMs:

wasm-pack test --chrome --test test_webgpu_msm_cuzk_19

For $2^{20}$ MSMs:

wasm-pack test --chrome --test test_webgpu_msm_cuzk_20

Future work

• Implement cuzk on other curves.

• Implement cuzk on other libraries other than halo2curves, such as arkworks.

• Explore the trade-off between the running time and the extra storage space needed by parallel Pippenger algorithm on webGPU as the paper Elastic MSM suggests.