# General Grant Proposal - Mopro-22

* **Project:** Improve MSM performance using GPU [#23](https://github.com/privacy-scaling-explorations/acceleration-program/issues/23)

[TOC]

## Project Overview :page_facing_up:

### 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](https://github.com/oskarth/mopro/issues/22#issue-1966449914)

### 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 :busts_in_silhouette:

### Team members
* Names of team members
* Fu-Chuan Chung
* Moven Tsai

* Discord handle
* foodchain1028
* moventsai

* Email
* [e-mail]
* [e-mail]

### Team's experience
* [Fu-Chuan Chung](https://github.com/FoodChain1028)
* PSE ZK Summer Open-source Contribution Program Fellow
* [Moven Tsai](https://github.com/moven0831)
* PSE ZK Summer Open-source Contribution Program Fellow

### Team Code Repos
* [mopro](https://github.com/oskarth/mopro)

## Development Roadmap :nut_and_bolt:

### Overview
* **Total Estimated Duration:** 9 week
* **Full-time equivalent (FTE):** Workload of an employed person ([see](https://en.wikipedia.org/wiki/Full-time_equivalent))
* **Estimated start date:** Mar 1st 2024
* **Total FTE:** 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](https://github.com/z-prize/2022-entries/tree/main/open-division/prize7-msm-mobile) (or find other implementations in GPU acceleration like [Ingonyama - icicle](https://github.com/ingonyama-zk/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](https://github.com/nistath/zprize-mobile-msm/tree/b57d6097296b2a6e21374ebf9e785bf27259375e): in `Rust`
- [Trapdoor-Tech](https://github.com/Trapdoor-Tech/TrapdoorTech-zprize-mobile-harness/tree/c86b415cbc305f2a255aac2bfb0afd841cad2804): 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 :heavy_plus_sign:
[zprize 2022](https://github.com/z-prize/2022-entries/tree/main/open-division/prize7-msm-mobile) 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](/ZCxFpQ8AROyYGTl5GLqAGQ)
- [mopro 22 milestone 2 report](/YtTVJUArRmWrdvaTza2LGg)
- [mopro 22 milestone 3 report](/v8WPAG8-RsCANrbv_seSXw)
- [mopro 22 milestone 4 report](/6aYxLgNZTaGG4gbXkZUlCw)

## Reference
- [zprize 2022 msm on mobile acceleration](https://github.com/z-prize/2022-entries/tree/main/open-division/prize7-msm-mobile)
- [Ingonyama - icicle](https://github.com/ingonyama-zk/icicle/blob/main/wrappers/rust/icicle-curves/icicle-bn254/src/msm/mod.rs) : as a reference to implement in Metal API.
- [Pippenger](https://github.com/arkworks-rs/algebra/blob/master/ec/src/scalar_mul/variable_base/stream_pippenger.rs): in `Rust`
- [Metal Document](https://developer.apple.com/documentation/metal/)