Proposal: Improve MSM performance using GPU

[FoodChain1028]

General Grant Proposal - Mopro-22

• Project: Improve MSM performance using GPU #23

Project Overview 📄

Overview

Enhance the performance on proving speed using GPU on mobile phone.

Refer to following for detail

• Proving with GPU on mobile oskarth/mopro#22

Project Details

• Use ark-msm as baseline and compare benchmarks of other zprize works on real device.
• Reproduce the benchmarking with laptop/server GPU.
• Experiment and understand the details on how to use GPU on mobile proving.
• Enable the msm scheme run on iOS device with GPU acceleration.
• Optimize the MSM execution with mobile specific works such as parallel computation.
• Provide documention and instructions to how to enable GPU acceleration in proving process on mobile.

MileStone Details

For milstone 1 & 2, we will focus on integrating the algorithms into mopro and benchmark the performance using arkwork msm (which is already integrate in the project from previous work) as baseline.

Regarding milstone 3, we will try to optimize the msm algorithm on Apple chip using its GPU API called Metal. And in the fourth milestone, we will benchmark our work in mopro to see if our work has a better performance than the others.

Team 👥

Team members

• Names of team members

  • Fu-Chuan Chung
  • Moven Tsai

• Discord handle

  • foodchain1028
  • moventsai

• Email

  • [email protected]
  • [email protected]

Team's experience

• Fu-Chuan Chung
  • PSE ZK Summer Open-source Contribution Program Fellow
• Moven Tsai
  • PSE ZK Summer Open-source Contribution Program Fellow

Team Code Repos

• mopro

Development Roadmap 🔩

Overview

• Total Estimated Duration: 9 week
• Full-time equivalent (FTE): 1.0666666667
• Estimated start date: Mar 1st 2024
• Total Estimated Working Hours: 384 hours

Milestone 1: Integrate other zprize works with ark_msm as baseline and benchmark them on iOS device.

• Estimated Duration: 2 week
• Estimated delivery date: Mar 15th 2024
• FTE: 1.2
• FTE for us: 24 + 24

Milestone 2: Introduce the laptop/server GPU to accelerate the proving and reproduce the benchmarking.

• Estimated Duration: 1 week
• Estimated delivery date: Mar 24th 2024
• FTE: 0.8
• FTE for us: 16 + 16

Milestone 3: Experiment on how to use GPU on iOS and enable the msm scheme run on iOS device with GPU acceleration.

• Estimated Duration: 4 week
• Estimated delivery date: Apr 24th 2024
• FTE: 1.2
• FTE for us: 24 + 24

Milestone 4: Optimized the MSM performance with mobile specific works

• Estimated Duration: 2 week
• Estimated delivery date: May 8th 2024
• FTE: 0.8
• FTE for us: 16 + 16

Deliverables and Specifications

0a. Codebase

We plan to integrate msm optimizations for mobile built in Zprize (or find other implementations in GPU acceleration like Ingonyama - icicle) in mopro project. Moreover, we tend to conduct an experiment for optimizing an MSM algorithm designed for Apple Chip.

Afterwards, we will benchmark these integration with arkwork-msm to observe the result in both laptops and real IOS devices.

milestone involved: all

0b. Documentation

We commit to ensuring exhaustive documentation of all modifications undertaken. This will involve the provision of detailed operational guidelines within the README.md file for the utilization of the tool. Additionally, we will refine and augment the instructions for incorporating other msm-work into the benchmarks. This enhancement is aimed at bolstering future experimental endeavors and facilitating extensions.

milestone involved: all

0c. Testing Guide

We will try to optimize some algorithms to accelerate the process on msm running on IOS GPU. In addition, we aim to integrate more MSM GPU optimization implementations and benchmark these operations running on IOS GPU.

The test guides would be written in the report in each milestone.

milestone involved: all

0d. MSM Algorithms Integration

MSM optimized algorithm on mobile GPU

• nistath: in Rust
• Trapdoor-Tech: in Rust, Java

milestone involved: all

Reference

0e. iOS Mobile Architecture

We aim to harness Apple's GPU architecture and Metal API, custom-optimizing MSM algorithms to exploit parallel processing and compute shaders. This approach guarantees better performance, energy efficiency, and security in msm computations on iOS devices.

milestone involved: 3 & 4

Additional Information ➕

zprize 2022 msm acceleration on mobiles are mainly conducted on Samsung Galaxy A13 5G (SoC MediaTek Dimensity 700
(MT6833) and the MSM implementation were over BLS12-377 G1 curve.

Milestone Reports

• mopro 22 milestone 1 report
• mopro 22 milestone 2 report
• mopro 22 milestone 3 report
• mopro 22 milestone 4 report

Reference

• zprize 2022 msm on mobile acceleration
• Ingonyama - icicle : as a reference to implement in Metal API.
• Pippenger: in Rust
• Metal Document

[FoodChain1028]

Hi, @oskarth and @NOOMA-42, we have finished the proposal of improve MSM performance on mobile GPU. Please have a look

[Mirror-Tang]

Ingonyama - icicle‘s support for HALO2 is not very good. I have communicated with their team and tested it, and they only support Gnark well. I suggest using other open source solutions. If needed, I will provide assistance for the project.