Improve MSM performance using GPU

[vivianjeng]

• moved from https://github.com/zkmopro/mopro/issues/79
• Part of #22

Problem

We want to optimize the performance of MSM on mobile devices using GPU. This will be the groundwork for the enhancement of the mobile proving system.

Details

• Use ark-msm as a baseline and compare benchmarks of other MSM algorithms (e.g. ZPrize works) on real devices.
  • Rust works (primary)
    • nistath
    • Trapdoor-Tech
    • Pippenger
  • Others (backlog)
    • Ingonyama - icicle: for CUDA
    • yyTeam: Mainly using C
    • gnark: implemented in GO
• Reproduce the benchmarking with laptop/server GPU.
• Experiment and understand the details of how to use GPU on mobile proving.
  • Aim for Apple GPU Metal framework first. Then, backlog CUDA and OpenCL.
  • Important steps for integrating a GPU-friendly proving system in #22 as well
• Enable the msm scheme to run on iOS devices with GPU acceleration.
• Optimize the MSM execution with mobile-specific works such as parallel computation.
• Provide documentation and instructions to how to enable GPU acceleration in the proving process on mobile.

Acceptance criteria

• Integrate an MSM algorithm with GPU acceleration and mobile-specific enhancements.
• Suitable for future works about integrating the MSM algorithm into the actual proving system.